How many relations of length $n$ can exists in a group without enforcing shorter relations? - MathOverflow

How many relations of length $n$ can exists in a group without enforcing shorter relations?

2011-02-17T14:22:37Z

Let $G$ be a group with two generators. Suppose that all non-trivial words of length less or equal $n$ in the generators and their inverses define non-trivial elements in $G$.

Question: How many of the $4\cdot 3^{n}$ words of length $n+1$ in the generators and their inverses can at most be trivial in $G$?

I am interested in the growth of this number as $n$ grows. From what I understand from the Gromov's theory of random groups, a choice of relations of length $n+1$ will (almost surely as $n \to \infty$) not enforce shorter relations if one chooses $$3^{\left(\frac{1}2 - \varepsilon\right) \cdot n}$$ relations of length $n+1$ at random. (This result is related to small cancellation theory which applies to randomly choosen relations. The exponent $1/2$ which appears is related to the birthday paradox. It ensures that with high probability one does not chose relations which have large overlap.) However, I would not know how to prove it or even locate it in the literature. Can someone confirm this?

Question: Can one do better than $3^{\left(\frac{1}2 - \varepsilon\right)\cdot n}$ (as $n \to \infty$) with a concrete sequence of groups rather than using random groups?

Answer by Gerhard Paseman for How many relations of length $n$ can exists in a group without enforcing shorter relations?

2011-02-17T20:46:07Z

Let w be a word (on the alphabet of the two letters plus two more symbols for the formal inverse) of length n+1. If this word is trivial, then cyclic permutations of this word are trivial and one also gets relations of the form letter = word in length n by taking a different letter out of the word and formally inverting, and rearranging the word appropriately.

When you do this you can group the cyclic permutations intp four groups (or two if you do the proper inversions). This allows you to build up lists of which words are equal. You can then do cancellation to build up shorter relations. Once you have two words of length n/2 being equal (let me assume n even for simplicity), you can now form a trivial word of length n contradictory to your premise.

Starting with K words of length n+1 no two of which are cyclically similar, one can develop K'(n+1) distinct words into two different groups. (There may be conflation and K' may be less than K; for the moment assume we are lucky and that K' = K.) If one of those groups has two words beginning (say) with the same string of n/2 letters, then you get a contradictory word, so the groups must each be smaller than 4^(n/2), giving a rough estimate of K'(n+1) <= 2 * 2^n, and more work may show that K might be of the same order as K'.

Not a full answer, and some combinatorics left to be done (for example ruling out the cases that two words have the same prefix and suffix with combined length of n/2), but I hope this line of thought helps.

Gerhard "Ask Me About System Design" Paseman, 2011.02.17

Answer by Roland Bacher for How many relations of length $n$ can exists in a group without enforcing shorter relations?

2011-05-13T08:01:06Z

The following trick inspired by Burnside groups can perhaps be made into something interesting (but probably smaller then $3^{1/2-\epsilon}$):

Suppose $n+1$ has a fairly small divisor $k$ (I ignore if $k=2$ already works) and choose a subset $S$ of words of length $(n+1)/k$ in $\langle a,b\rangle$. If no word of $S$ can be cyclically reduced and if the words of $S$ satisfy a suitable no-small-cancellation property (in particular, $\langle S\rangle$ should be the free group on $S$), then the free Burnside group on $S$ has no relation shorter than $n+1$ (with respect to the length induced as a subgroup of $\langle a,b\rangle$). The quotient of $\langle a,b\rangle$ by the Burnside-relations induced by $S$ should now have no relations smaller than $n+1$. Indeed, cyclically reducedness of the elements in $S$ shows that the relations $g^{(n+1)/k},g\in S$ are cyclically reduced and the small cancellation property shows that all other relations are larger. The problem amounts thus to finding a suitable large set $S$.

(I guess that this is also more or less the idea underlying Paseman's answer.)