On Dehn Functions of Infinite Presentations of Groups

We introduce two new types of Dehn functions of group presentations which seem more suitable (than the standard Dehn function) for infinite group presentations and prove the fundamental equivalence between the solvability of the word problem for a group presentation defined by a decidable set of defining words and the property of being computable for one of the newly introduced functions (this equivalence fails for the standard Dehn function). Elaborating on this equivalence and making use of this function, we obtain a characterization of finitely generated groups for which the word problem can be solved in nondeterministic polynomial time. We also give upper bounds for these functions, as well as for the standard Dehn function, for two well-known periodic groups. In particular, we prove that the (standard) Dehn function of a 2-group Γ of intermediate growth, defined by a system of defining relators due to Lysenok, is bounded from above by C₁x² log₂ x, where C₁ > 1 is a constant. We also show that the (standard) Dehn function of a free m-generator Burnside group B(m, n) of exponent n ≥ 2⁴⁸, where n is either odd or divisible by 2⁹, defined by a minimal system of defining relators, is bounded from above by the subquadratic function x^19/12. Received: September 2007, Revision: March 2008, Accepted: March 2008     

Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups

A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo-natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T, while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10.     

On the complexity of the word problem for automaton semigroups and automaton groups

In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are generated by partial, yet invertible automata. We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSpace-complete word problem. We also show that there is an automaton group for which the word problem with a single rational constraint is PSpace-complete. Additionally, we provide simpler constructions for the uniform word problems of these classes. For the uniform word problem for automaton groups (without rational constraints), we show NL-hardness. Finally, we investigate a question asked by Cain about a better upper bound for the length of a word on which two distinct elements of an automaton semigroup must act differently.A detailed listing of the contributions of this paper can be found at the end of this paper.     

The word problem for some uncountable groups given by countable words

We investigate the fundamental group of Griffiths? space, and the first singular homology group of this space and of the Hawaiian Earring by using (countable) reduced tame words. We prove that two such words represent the same element in the corresponding group if and only if they can be carried to the same tame word by a finite number of word transformations from a given list. This enables us to construct elements with special properties in these groups. By applying this method we prove that the two homology groups contain uncountably many different elements that can be represented by infinite concatenations of countably many commutators of loops. As another application we give a short proof that these homology groups contain the direct sum of ℵ₀² copies of Q. Finally, we show that the fundamental group of Griffiths? space contains Q.     

The conjugacy problem for Dehn twist automorphisms of free groups

A Dehn twist automorphism of a group G is an automorphism which can be given (as specified below) in terms of a graph-of-groups decomposition of G with infinite cyclic edge groups. The classic example is that of an automorphism of the fundamental group of a surface which is induced by a Dehn twist homeomorphism of the surface. For , a non-abelian free group of finite rank n, a normal form for Dehn twist is developed, and it is shown that this can be used to solve the conjugacy problem for Dehn twist automorphisms of . Received: February 12, 1996.     

Covering the alternating groups by products of cycle classes

Given integers k,l?2, where either l is odd or k is even, we denote by n=n(k,l) the largest integer such that each element of An is a product of k cycles of length l. For an odd l, k is the diameter of the undirected Cayley graph Cay(An,Cl), where Cl is the set of all l-cycles in An. We prove that if k?2 and l?9 is odd and divisible by 3, then . This extends earlier results by Bertram [E. Bertram, Even permutations as a product of two conjugate cycles, J. Combin. Theory 12 (1972) 368-380] and Bertram and Herzog [E. Bertram, M. Herzog, Powers of cycle-classes in symmetric groups, J. Combin. Theory Ser. A 94 (2001) 87-99].     

Limits of commutative triangular systems on locally compact groups

On a locally compact group G, if , for some probability measuresv _n and μ onG, then a sufficient condition is obtained for the set to be relatively compact; this in turn implies the embeddability of a shift of μ. The condition turns out to be also necessary when G is totally disconnected. In particular, it is shown that ifG is a discrete linear group over R then a shift of the limit μ is embeddable. It is also shown that any infinitesimally divisible measure on a connected nilpotent real algebraic group is embeddable.     

On the word problem and the conjugacy problem for groups of the formF/V(R)

LetF be a free group with at most countable system of free generators, letR be its normal subgroup recursively enumerable with respect to , and let be a variety of groups that differs from and for which the corresponding verbal subgroupV of the free group of countable rank is recursive. It is proved that the word problem inF/V(R) is solvable if and only if this problem is solvable inF/R, and if , then there exists anR such, that the conjugacy problem inF/R is solvable, but this problem is unsolvable inF/V(R) for any Abelian variety (all algorithmic problems are regarded with respect to the images of under the corresponding natural epimorphisms). Translated fromMatematicheskie Zametki, Vol. 61, No. 1, pp. 3–9, January, 1997. Translated by M. I. Anokhin     

Group Embeddings with Algorithmic Properties

We show that every countable group H with solvable word problem can be subnormally embedded into a 2-generated group G which also has solvable word problem. Moreover, the membership problem for H < G is also solvable. We also give estimates of time and space complexity of the word problem in G and of the membership problem for H < G.     

On the cycling operation in braid groups

The cycling operation is a special kind of conjugation that can be applied to elements in Artin’s braid groups, in order to reduce their length. It is a key ingredient of the usual solutions to the conjugacy problem in braid groups. In their seminal paper on braid-cryptography, Ko, Lee et al. proposed the cycling problem as a hard problem in braid groups that could be interesting for cryptography. In this paper we give a polynomial solution to that problem, mainly by showing that cycling is surjective, and using a result by Maffre which shows that pre-images under cycling can be computed fast. This result also holds in every Artin-Tits group of spherical type, endowed with the Artin Garside structure.On the other hand, the conjugacy search problem in braid groups is usually solved by computing some finite sets called (left) ultra summit sets (left-USSs), using left normal forms of braids. But one can equally use right normal forms and compute right-USSs. Hard instances of the conjugacy search problem correspond to elements having big (left and right) USSs. One may think that even if some element has a big left-USS, it could possibly have a small right-USS. We show that this is not the case in the important particular case of rigid braids. More precisely, we show that the left-USS and the right-USS of a given rigid braid determine isomorphic graphs, with the arrows reversed, the isomorphism being defined using iterated cycling. We conjecture that the same is true for every element, not necessarily rigid, in braid groups and Artin-Tits groups of spherical type.     

Tail asymptotics for service systems with transfers of customers in an alternating environment

This study examines service systems with transfers of customers in an alternating environment. We model the service system as a two-server two-parallel queue (primary and auxiliary queues), that has various applications especially in manufacturing and healthcare systems. We establish a sufficient stability condition, and based on the censoring technique, we provide sufficient conditions under which the stationary distribution possesses an exactly geometric tail along the direction of the queue length in the primary queue.     

A minimal Cantor set in the space of 3-generated groups

We construct and study a family of 3-generated groups parametrized by infinite binary sequences w. We show that two groups of the family are isomorphic if and only if the sequences are cofinal and that two groups cannot be distinguished by finite sets of relations. We show a connection of the family with 2-dimensional holomorphic dynamics.      

Convergence in L p -norm of Fourier series on the complete product of quaternion groups with bounded orders

A well-known result for Vilenkin systems is the fact that for all 1 p ∞ the n-th partial sums of Fourier series of all functions in the space Lpconverge to the function in Lp-norm.This statement can not be generalized to any representative product system on the complete product of finite non-abelian groups,but even then it is true for the complete product of quaternion groups with bounded orders and monomial representative product system ordered in a specific way.     

Analysis of the escape in systems with four exit channels

In this paper, we have performed a numerical investigation of the escape of a particle from two different dynamical systems with the same number of exit channels. We have chosen specific values of the parameters of the systems so that the openings of the potential well in both systems are approximately of the same size. We have found that, in the galactic system, the distribution of the times of escape follows a sequential pattern that has never been detected before. Moreover, we have proved that this pattern is directly related to the geometry of the stable manifolds to the Lyapunov orbits located at the openings of the potential. Finally, we have shown that the different nature of the two systems affects the way the escape occurs, due to the difference in the geometry of the manifolds to the Lyapunov orbits in both systems.     

On the construction of irreducible characters in p-blocks with normal metacyclic defect groups

The author carries out a detailed study of p-blocks with normal metacyclic defect groups provided that p is odd and the defect groups are splitting and nonabelian.In particular,the author constructs all the irreducible ordinary and modular characters in this type of blocks.As a by-product,k(B) and l(B) are obtained.     

On the characterization of the controllability property for linear control systems on nonnilpotent,solvable three-dimensional Lie groups

In this paper we show that a complete characterization of the controllability property for linear control system on three-dimensional solvable nonnilpotent Lie groups is possible by the LARC and the knowledge of the eigenvalues of the derivation associated with the drift of the system.     

Centers for the Kukles homogeneous systems with even degree

For the polynomial differential system $\dot{x}=-y$, $\dot{y}=x +Q_n(x,y)$, where $Q_n(x,y)$ is a homogeneous polynomial of degree $n$ there are the following two conjectures done in 1999. (1) Is it true that the previous system for $n \ge 2$ has a center at the origin if and only if its vector field is symmetric about one of the coordinate axes? (2) Is it true that the origin is an isochronous center of the previous system with the exception of the linear center only if the system has even degree? We give a step forward in the direction of proving both conjectures for all $n$ even. More precisely, we prove both conjectures in the case $n = 4$ and for $n\ge 6$ even under the assumption that if the system has a center or an isochronous center at the origin, then it is symmetric with respect to one of the coordinate axes, or it has a local analytic first integral which is continuous in the parameters of the system in a neighborhood of zero in the parameters space. The case of $n$ odd was studied in [8].     

On the existence of isotropic forms of semi-simple algebraic groups over number fields with prescribed local behavior

This note is a follow-up on the paper [A. Borel, G. Harder, Existence of discrete cocompact subgroups of reductive groups over local fields, J. Reine Angew. Math. 298 (1978) 53-64] of A. Borel and G. Harder in which they proved the existence of a cocompact lattice in the group of rational points of a connected semi-simple algebraic group over a local field of characteristic zero by constructing an appropriate form of the semi-simple group over a number field and considering a suitable S-arithmetic subgroup. Some years ago A. Lubotzky initiated a program to study the subgroup growth of arithmetic subgroups, the current stage of which focuses on “counting” (more precisely, determining the asymptotics of) the number of lattices of bounded covolume (the finiteness of this number was established in [A. Borel, G. Prasad, Finiteness theorems for discrete subgroups of bounded covolume in semi-simple groups, Publ. Math. Inst. Hautes Études Sci. 69 (1989) 119-171; Addendum: Publ. Math. Inst. Hautes Études Sci. 71 (1990) 173-177] using the formula for the covolume developed in [G. Prasad, Volumes of S-arithmetic quotients of semi-simple groups, Publ. Math. Inst. Hautes Études Sci. 69 (1989) 91-117]). Work on this program led M. Belolipetsky and A. Lubotzky to ask questions about the existence of isotropic forms of semi-simple groups over number fields with prescribed local behavior. In this paper we will answer these questions. A question of similar nature also arose in the work [D. Morris, Real representations of semisimple Lie algebras have Q-forms, in: Proc. Internat. Conf. on Algebraic Groups and Arithmetic, December 17-22, 2001, TIFR, Mumbai, 2001, pp. 469-490] of D. Morris (Witte) on a completely different topic. We will answer that question too.