 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 1
1. Computing nilpotent quotients in finitely presented Lie rings
A nilpotent quotient algorithm for finitely presented Lie rings over \textbfZ (and \textbfQ) is described. The paper studies the graded and non-graded cases separately. The algorithm computes the so-called nilpotent presentation for a finitely presented, nilpotent Lie ring. A nilpotent presentation consists of generators for the abelian group and the products expressed as linear combinations for pairs formed by generators. Using that presentation the word problem is decidable in L. Provided that the Lie ring L is graded, it is possible to determine the canonical presentation for a lower central factor of L. Complexity is studied and it is shown that optimising the presentation is NP-hard. Computational details are provided with examples, timing and some structure theorems obtained from computations. Implementation in C and GAP interface are available.
2. On P_4-tidy graphs
We study the P_4-tidy graphs, a new class defined by Rusu [30] in order to illustrate the notion of P_4-domination in perfect graphs. This class strictly contains the P_4-extendible graphs and the P_4-lite graphs defined by Jamison & Olariu in [19] and [23] and we show that the P_4-tidy graphs and P_4-lite graphs are closely related. Note that the class of P_4-lite graphs is a class of brittle graphs strictly containing the P_4-sparse graphs defined by Hoang in [14]. McConnel & Spinrad [2] and independently Cournier & Habib [5] have shown that the modular decomposition tree of any graph is computable in linear time. For recognizing in linear time P_4-tidy graphs, we apply a method introduced by Giakoumakis in [9] and Giakoumakis & Fouquet in [6] using modular decomposition of graphs and we propose linear algorithms for optimization problems on such graphs, as clique number, stability number, chromatic number and scattering number. We show that the Hamiltonian Path Problem is linear for this class of graphs. Our study unifies and generalizes previous results of Jamison & Olariu ([18], [21], [22]), Hochstattler & Schindler[16], Jung [25] and Hochstattler & Tinhofer [15].
3. Lyndon factorization of the Thue-Morse word and its relatives
We compute the Lyndon factorization of the Thue-Morse word. We also compute the Lyndon factorization of two related sequences involving morphisms that give rise to new presentations of these sequences.
4. A direct bijective proof of the hook-length formula
This paper presents a new proof of the hook-length formula, which computes the number of standard Young tableaux of a given shape. After recalling the basic definitions, we present two inverse algorithms giving the desired bijection. The next part of the paper presents the proof of the bijectivity of our construction. The paper concludes with some examples.
5. E-unification by means of tree tuple synchronized grammars
The goal of this paper is both to give an E-unification procedure that always terminates, and to decide unifiability. For this, we assume that the equational theory is specified by a confluent and constructor-based rewrite system, and that four additional restrictions are satisfied. We give a procedure that represents the (possibly infinite) set of solutions thanks to a tree tuple synchronized grammar, and that can decide upon unifiability thanks to an emptiness test. Moreover, we show that if only three of the four additional restrictions are satisfied then unifiability is undecidable.
6. Descendants and ascendants in binary trees
There are three classical algorithms to visit all the nodes of a binary tree - preorder, inorder and postorder traversal. From this one gets a natural labelling of the n internal nodes of a binary tree by the numbers 1, 2, ..., n, indicating the sequence in which the nodes are visited. For given n (size of the tree) and j (a number between 1 and n), we consider the statistics number of ascendants of node j and number of descendants of node j. By appropriate trivariate generating functions, we are able to find explicit formulae for the expectation and the variance in all instances. The heavy computations that are necessary are facilitated by MAPLE and Zeilberger's algorithm. A similar problem comes fromlabelling the leaves from left to right by 1, 2, ..., n and considering the statistic number of ascendants (=height) of leaf j. For this, Kirschenhofer [1] has computed the average. With our approach, we are also able to get the variance. In the last section, a table with asymptotic equivalents is provided for the reader's convenience.
7. Special issue: 'Lie Computations'
This special issue is an outgrowth of the MEDICIS thematic workshop on Lie Computations that was held at the Centre International de Rencontres Mathématiques in Marseilles in November 1994. It was jointly sponsored by the Groupe de Recherche MEDICIS, the CIRM (Société Mathématique de France), and the European project INTAS 93-30.
8. Finely homogeneous computations in free Lie algebras
We first give a fast algorithm to compute the maximal Lyndon word (with respect to lexicographic order) of \textitLy_α (A) for every given multidegree alpha in \textbfN^k. We then give an algorithm to compute all the words living in \textitLy_α (A) for any given α in \textbfN^k. The best known method for generating Lyndon words is that of Duval [1], which gives a way to go from every Lyndon word of length n to its successor (with respect to lexicographic order by length), in space and worst case time complexity O(n). Finally, we give a simple algorithm which uses Duval's method (the one above) to compute the next standard bracketing of a Lyndon word for lexicographic order by length. We can find an interesting application of this algorithm in control theory, where one wants to compute within the command Lie algebra of a dynamical system (letters are actually vector fields).
9. Computations in finite-dimensional Lie algebras
This paper describes progress made in context with the construction of a general library of Lie algebra algorithms, called ELIAS (Eindhoven Lie Algebra System), within the computer algebra package GAP. A first sketch of the package can be found in Cohen and de Graaf[1]. Since then, in a collaborative effort with G. Ivanyos, the authors have continued to develop algorithms which were implemented in ELIAS by the second author. These activities are part of a bigger project, called ACELA and financed by STW, the Dutch Technology Foundation, which aims at an interactive book on Lie algebras (cf. Cohen and Meertens [2]). This paper gives a global description of the main ways in which to present Lie algebras on a computer. We focus on the transition from a Lie algebra abstractly given by an array of structure constants to a Lie algebra presented as a subalgebra of the Lie algebra of n×n matrices. We describe an algorithm typical of the structure analysis of a finite-dimensional Lie algebra: finding a Levi subalgebra of a Lie algebra.
10. BERGMAN under MS-DOS and Anick's resolution
Noncommutative algebras, defined by the generators and relations, are considered. The definition and main results connected with the Gröbner basis, Hilbert series and Anick's resolution are formulated. Most attention is paid to universal enveloping algebras. Four main examples illustrate the main concepts and ideas. Algorithmic problems arising in the calculation of the Hilbert series are investigated. The existence of finite state automata, defining thebehaviour of the Hilbert series, is discussed. The extensions of the BERGMAN package for IBM PC compatible computers are described. A table is provided permitting a comparison of the effectiveness of the calculations in BERGMAN with the other systems.
11. A Lie connection between Hamiltonian and Lagrangian optics
It is shown that there is a non-Hamiltonian vector field that provides a Lie algebraic connection between Hamiltonian and Lagrangian optics. With the aid of this connection, geometrical optics can be formulated in such a way that all aberrations are attributed to ray transformations occurring only at lens surfaces. That is, in this formulation there are no aberrations arising from simple transit in a uniform medium. The price to be paid for this formulation is that the Lie algebra of Hamiltonian vector fields must be enlarged to include certain non-Hamiltonian vector fields. It is shown that three such vector fields are required at the level of third-order aberrations, and sufficient machinery is developed to generalize these results to higher order.
12. Noncommutative symmetric functions III : Deformations of Cauchy and convolution algebras
This paper discusses various deformations of free associative algebras and of their convolution algebras. Our main examples are deformations of noncommutative symmetric functions related to families of idempotents in descent algebras, and a simple q-analogue of the shuffle product, which has unexpected connections with quantum groups, hyperplane arrangements, and certain questions in mathematical physics (the quon algebra, generalized Brownian motion).
13. An algorithm for analysis of the structure of finitely presented Lie algebras
We consider the following problem: what is the most general Lie algebra satisfying a given set of Lie polynomial equations? The presentation of Lie algebras by a finite set of generators and defining relations is one of the most general mathematical and algorithmic schemes of their analysis. That problem is of great practical importance, covering applications ranging from mathematical physics to combinatorial algebra. Some particular applications are constructionof prolongation algebras in the Wahlquist-Estabrook method for integrability analysis of nonlinear partial differential equations and investigation of Lie algebras arising in different physical models. The finite presentations also indicate a way to q-quantize Lie algebras. To solve this problem, one should perform a large volume of algebraic transformations which is sharply increased with growth of the number of generators and relations. For this reason, in practice one needs to use a computer algebra tool. We describe here an algorithm for constructing the basis of a finitely presented Lie algebra and its commutator table, and its implementation in the C language. Some computer results illustrating our algorithmand its actual implementation are also presented.
14. On the bialgebra of functional graphs and differential algebras
We develop the bialgebraic structure based on the set of functional graphs, which generalize the case of the forests of rooted trees. We use noncommutative polynomials as generating monomials of the functional graphs, and we introduce circular and arborescent brackets in accordance with the decomposition in connected components of the graph of a mapping of \1, 2, \ldots, n\ in itself as in the frame of the discrete dynamical systems. We give applications fordifferential algebras and algebras of differential operators.
15. Controllability of affine right-invariant systems on solvable Lie groups
The aim of this paper is to present some recent results on controllability of right-invariant systems on Lie groups. From the Lie-theoretical point of view, we study conditions under which subsemigroups generated by half-planes in the Lie algebra of a Lie group coincide with the whole Lie group.
16. BRST Charge and Poisson Algebras
An elementary introduction to the classical version of gauge theories is made. The shortcomings of the usual gauge fixing process are pointed out. They justify the need to replace it by a global symmetry: the BRST symmetry and its associated BRST charge. The main mathematical steps required to construct it are described. The algebra of constraints is, in general, a nonlinear Poisson algebra. In the nonlinear case the computation of the BRST charge by hand is hard. Itis explained how this computation can be made algorithmic. The main features of a recently created BRST computer algebra program are described. It can handle quadratic algebras very easily. Its capability to compute the BRST charge as a formal power series in the generic case of a cubic algebra is illustrated.