Search

Given a finitely generated group with generating set S , we study the cogrowth sequence, which is the number of words of length n over the alphabet S that are equal to the identity in the group. This is related to the probability of return for walks on the corresponding Cayley graph. Muller and Schupp proved the generating function of the sequence is algebraic when G has a finite-index-free subgroup (using a result of Dunwoody). In this work, we make this result effective for free products of finite groups: we determine bounds for the degree and height of the minimal polynomial of the generating function, and determine the minimal polynomial explicitly for some families of free products. Using these results we are able to prove that a gap theorem holds: if S is a finite symmetric generating set for a group G and if a n denotes the number of words of length n over the alphabet S that are equal to 1 then lim sup n a n 1 / n is either 1 , 2 or at least 2 2 . [ABSTRACT FROM AUTHOR]

Consider a nonstandard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over {0,1} without two consecutive 1. Given a set X of integers such that the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not X is a finite union of arithmetic progressions. We obtain a decision procedure for this problem, under some hypothesis about the considered numeration system. In a second part, we obtain an analogous decision result for a particular class of abstract numeration systems built on an infinite regular language. [ABSTRACT FROM AUTHOR]

A set of words over a finite alphabet is called an unavoidable set if every word of sufficiently long length must contain some word from this set as a subword. Motivated by a theorem from automata theory, we introduce the notion of an almost unavoidable set and prove certain asymptotic estimates for the size of almost unavoidable sets of uniform length. [ABSTRACT FROM AUTHOR]