International Journal of Algebra and Computation

An element of a finitely generated non-Abelian free group F(X) is said to be filling if that element has positive translation length in every very small minimal isometric action of F(X) on an ℝ-tree. We give a proof that the set of filling elements of F(X) is exponentially F(X)-generic in the sense of Arzhantseva and Ol'shanskiı. We also provide an algebraic sufficient condition for an element to be filling and show that there exists an exponentially F(X)-generic subset consisting only of filling elements and whose membership problem has linear time complexity.

Attempts have been made to eliminate some potential counterexamples to the Andrews–Curtis conjecture using the combinatorial optimization methods of blind-search and the genetic algorithms meta-heuristic. Breadth-first search with secondary storage is currently the most successful method, which raises questions regarding the inferior performance of heuristic search. In order to understand the underlying reasons we obtain fitness landscape metrics for a number of balanced presentations and draw conclusions regarding the likely effectiveness of other meta-heuristics.

The aim of this paper is to characterize the formal power series which have purely periodic β-expansions in Pisot or Salem unit base under some condition. Furthermore, we will prove that if β is a quadratic Pisot unit base, then every rational f in the unit disk has a purely periodic β-expansion and discuss their periods.

We prove that a metric space with subexponential asymptotic dimension growth has Yu's property A.

It is known that the bounded Geodesic Length Problem in free metabelian groups is NP-complete [A. Myasnikov, V. Roman'kov, A. Ushakov and A. Vershik, The word and geodesic problems in free solvable groups, Trans. Amer. Math. Soc.362(9) (2010) 4655–4682] (in particular, the Geodesic Problem is NP-hard). We construct a 2-approximation polynomial time deterministic algorithm for the Geodesic Problem. We show that the Geodesic Problem in the restricted wreath product of a finitely generated non-trivial group with a finitely generated abelian group containing ℤ² is NP-hard and there exists a Polynomial Time Approximation Scheme for this problem. We also show that the Geodesic Problem in the restricted wreath product of two finitely generated non-trivial abelian groups is NP-hard if and only if the second abelian group contains ℤ².

Given a surface parametrization (non-necessarily birational) we provide a formula for computing the total degree of its generic offset. The formula essentially uses gcds and resultants of polynomials directly obtained from the input parametrization. In addition, it must be said that the formula is valid under the conjecture that not all offsets to a fixed rational (algebraic) surface pass though a fixed point; this was proved to be true in the curve case [Degree formulae for offset curves, J. Pure Appl. Algebra195(3) (2005) 301–335].

In this paper, we study the basic problem of counting independent sets in a graph and, in particular, the problem of counting antichains in a finite poset, from an algebraic perspective. We show that neither independence polynomials of bipartite Cohen–Macaulay graphs nor Hilbert series of initial ideals of radical zero-dimensional complete intersections ideals, can be evaluated in polynomial time, unless #P = P. Moreover, we present a family of radical zero-dimensional complete intersection ideals J_P associated to a finite poset P, for which we describe a universal Gröbner basis. This implies that the bottleneck in computing the dimension of the quotient by J_P (that is, the number of zeros of J_P) using Gröbner methods lies in the description of the standard monomials.

In the present paper we generalize the concept of groups with triality and apply it to the theory of the Moufang, Bol and Bruck loops. Such generalizations allow us to reduce certain problems from the loop theory to problems in the theory of groups.

We determine the integers a, b ≥ 1 and the prime powers q for which the word map w(x, y) = x^ay^b is surjective on the group PSL(2, q) (and SL(2, q)). We moreover show that this map is almost equidistributed for the family of groups PSL(2, q) (and SL(2, q)). Our proof is based on the investigation of the trace map of positive words.

Rauzy graphs of subshifts are endowed with an automaton structure. For Sturmian subshifts, it is shown that its transition semigroup is the syntactic semigroup of the language recognized by the automaton. An inverse limit of the partial semigroups of nonzero regular elements of their transition semigroups is described. If the subshift is minimal, then this inverse limit is isomorphic, as a partial semigroup, to the -class associated to it in the free pro-aperiodic semigroup.