International Journal of Algebra and Computation

We give a new upper bound for the growth of primitive conjugacy classes in torsion-free word hyperbolic groups.

Here we characterize the residually finite groups G which are the fundamental groups of a finite graph of finitely generated torsion-free nilpotent groups. Namely we show that G is residually finite if and only if for each edge group of the graph of groups the two edge monomorphisms differ essentially by an isomorphism of certain subgroups of the Mal'cev completion of the corresponding vertex groups.

We give some connections between various functions defined on finitely presented groups (isoperimetric, isodiametric, Todd–Coxeter radius, filling length functions, etc.), and we study the relation between those functions and the computational complexity of the word problem (deterministic time, nondeterministic time, symmetric space). We show that the isoperimetric function can always be linearly decreased (unless it is the identity map). We present a new proof of the Double Exponential Inequality, based on context-free languages.

Cunsheng Ding computed the linear complexity of generalized cyclotomic binary sequences of order 2 with respect to p², but made a mistake in his computation. These errors affect his main theorem seriously. We correct the errors and re-establish the main theorem.

One-relator presentations with torsion are characterized by relators which are proper powers of cyclically reduced words. Such groups have a spelling theorem which provides among other things a quick solution of the word problem. In this paper we consider other classes of one-relator presentations (which are necessarily torsion-free) with a similar spelling theorem.

We consider the problem, whose instance is a finite semigroup S and an identity I, and the question is whether I is satisfied in S. We show that the question concerning computational complexity of this problem is much harder, when restricted to commutative semigroups. We provide a relatively simple proof that in general the problem is co-NP-complete, and demonstrate, using some structure theory, that for a fixed commutative semigroup the problem can be solved in polynomial time. The complexity status of the general problem remains open.

We determine the minimal extension of the sequence <0,1,1,…,1,2>. This completes and extends the work of Koh, started in 1970, and solves Problem 15 in the survey on p_n-sequences and free spectra [4]. The results involve the investigation of some minimal expansions of semilattices.

We consider algebras over a field with generators x₁,x₂,…,x_n subject to square-free relations x_ix_j=x_kx_l in which every product x_px_q, p≠q, appears in one of the relations. The work of Gateva-Ivanova and Van den Bergh, motivated in particular by the study of set theoretic solutions of the Yang–Baxter equation, provided an important class of such algebras. In this special case the presentation satisfies the so-called cyclic condition that became an essential combinatorial tool in proving that these algebras share many strong ring theoretic properties of polynomial algebras in commuting variables. In this paper we describe the structure of algebras on four generators satisfying the cyclic condition. The emphasis is on some new unexpected features, not present in the motivating special classes.

The author shows that the class of groups which are syntactic monoids of deterministic context-free languages is closed under restricted standard wreath products with virtually free top groups. This provides an answer to a question of T. Herbst.

The Jacobson radical is one of the major tools used in the investigation of the structure of rings and ring constructions. Our main theorem gives a complete description of the Jacobson radicals of incidence rings of group automata for all finite nilpotent groups.

Let G=F/r^F be a group with a single defining relation, r∈F_km\F_k,m+1, F_ij the term of some polynilpotent series of the free group F. We prove: the factors of the corresponding polynilpotent series of the group G are torsion free if and only if r is not a proper power of any element of F modulo F_k,m+1. We also give a description of the lower central series of a group F/[R,R] when F/R is a nilpotent group with torsion free lower central factors.