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?

  • $\begingroup$ For $n=1$ one can map both generators to the non-trivial element of $Z_2$ getting all $12$ elements of length $2$ trivial. For $n=2$ one can map one generator to a generator of $Z_5$ and the other to its square getting all $36$ elements of length $3$ trivial. Does anyone know the optimum for $n=3$? $\endgroup$
    – Someone
    Aug 19, 2011 at 16:05
  • $\begingroup$ @Someone: that doesn't work. If the generators are $a$ and $b$ then $a^3$ would be non-trivial. Indeed, if $a^3$ and $a^2b$ are both trivial in the group, then $a=b$, and so the word $ab^{-1}$ is trivial. $\endgroup$
    – Steve D
    Sep 30, 2011 at 17:32

2 Answers 2


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

  • $\begingroup$ "some combinatorics left to be done" seems to be the difficult part. Note that there is no algorithm to decide whether or not a given representation is a representation of the trivial group. $\endgroup$ Feb 18, 2011 at 8:06
  • $\begingroup$ Indeed, there is more to be done. However, if you are enforcing the relations, you can decide (for every set of n+1 words deemed trivial) what relations you want to hold, and (unless you are seeking lower bounds) may be able to get an upper bound on the number of trivial words of length n+1 that will force (contradict) one of the shorter words to be provably trivial. I would be surprised if one had a method for an exact upper bound. Also, if one just wants within order of magnitude, some combinatorics can be overlooked. Gerhard "What's a Googleplex Between Friends" Paseman, 2011.02.18 $\endgroup$ Feb 18, 2011 at 8:39

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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.