# Size of the smallest group not satisfying an identity.

Given $F = F(x_0,\ldots,x_n)$ the free group on $n+1$ generators. Define a function $M: F\rightarrow \mathbb{N}$ such that $F(w) = l$, if the smallest group in which $w$ is not an identity is of size $l$.

My question is what the function $M$ looks like. Are there nice bounds?

0)if there is a subset of the generators appearing in $w$ where the sum of the exponents is nonzero, then you can use a cyclic group where the order of the group does not divide this sum of exponents as an example.

1) an upper bound of $F(w)$ is $|w|!$: you can by hand construct a permutation group in which the identity is not satisfied. (the fact that $M$ is welldefined is equivalent to the residual finiteness of the free group)

2) the function $M$ is unbounded: every finite group $G$ on $n+1$ generators corresponds to a finite index subgroup of $F$ (a group $W\subseteq F$ for which $G = F/W$; for each $G$ there are finitely many such $W$), and the intersection of finitely many finite index subgroups is still of finite index. So take all groups of size less then $k$, every word in the intersection of their corresponding finite index subgroups requires a group of size greater than $k$ to not be satisfied.

-
FYI: You're using $n$ to mean two different things. –  aorq Feb 11 '10 at 19:12
+1. Welcome to MO! It's a great problem. –  Joel David Hamkins Feb 11 '10 at 19:16
@Ryan: I think that "w is an identity in G" means "every homomorphism F --> G maps w to 1". E.g., "x y x^{-1} y^{-1} is an identity in G" means that G is abelian. –  Bjorn Poonen Feb 11 '10 at 21:01
btw, point 2 can be stated quickly using M(x^(n!))>n. –  George Lowther Feb 11 '10 at 21:57
It may be profitable to generalize the question: Given a (finitely generated) group $G$ and $1 \ne w \in G$ what is the cardinality, $F(G,w)$, of the smallest group $H$ with the property that there is a homomorphism $f : G \rightarrow H$ such that $f(w) \ne 1$. So, as a trivial observation, if $G$ is a finite simple group, then $F(G,w) = |G|$. –  Victor Miller Feb 11 '10 at 23:27

To make the question a little less open-ended while (I hope) retaining its spirit, let me interpret the question as asking for the rate of growth of the function $\mu(k)$ defined as the maximum of $M(w)$ over all nontrivial words $w$ of length up to $k$ in any number of symbols, where length is the number of symbols and their inverses multiplied together in $w$. (E.g., $x^5 y^{-3}$ has length $8$.) George Lowther observed that $M(x^{n!})>n$, so $\mu(n!)>n$. One can replace $n!$ by $\operatorname{LCM}(1,2,\ldots,n)$, which is $e^{(1+o(1))n}$, so this gives $\mu(k) > (1-o(1)) \log k$ as $k \to \infty$.

I will improve this by showing that $\mu(k)$ is at least of order $k^{1/4}$.

Let $C_2(x,y):=[x,y]=xyx^{-1}y^{-1}$. If $C_N$ has been defined, define $$C_{2N}(x_1,\ldots,x_N,y_1,\ldots,y_N):=[C_N(x_1,\ldots,x_N),C_N(y_1,\ldots,y_N)].$$ By induction, if $N$ is a power of $2$, then $C_N$ is a word of length $N^2$ that evaluates to $1$ whenever any of its arguments is $1$.

Given $m \ge 1$, let $N$ be the smallest power of $2$ such that $N \ge 2 \binom{m}{2}$. Construct $w$ by applying $C_N$ to a sequence of arguments including $x_i x_j^{-1}$ for $1 \le i < j \le m$ and extra distinct interdeterminates inserted so that no two of the $x_i x_j^{-1}$ are adjacent arguments of $C_N$. The extra indeterminates ensure that $w$ is not the trivial word. If $w$ is evaluated on elements of a group of size less than $m$, then by the pigeonhole principle two of the $x_i$ have the same value, so some $x_i x_j^{-1}$ is $1$, so $w$ evaluates to $1$. Thus $M(w)>m$. The length of $w$ is at most $2N^2$, which is of order $m^4$. Thus $\mu(k)$ is at least of order $k^{1/4}$.

I have a feeling that this is not best possible$\ldots$

-
Maybe the question is easier to understand when asked the other way around: What is the shortest nontrivial word that is identically 1 on all groups of size up to n? The construction above gives a word of length O(n^4). –  Bjorn Poonen Feb 12 '10 at 4:15

The asymptotic version of this question raised by Bjorn Poonen has been studied by Khalid Bou-Rabee for general groups, not just free groups. That is, given G a residually finite group, for each g we can ask: how large is the smallest finite group F which detects g, meaning there exists f: G -> F so that f(g) is nontrivial? Now fix a word metric on G, and ask how the maximum of this "detection number" grows as you consider words of length at most n.

See "Quantifying residual finiteness" and "Asymptotic growth and least common multiples in groups" (with Ben McReynolds) for his results. For example, as long as G is linear, the growth function is polylog, meaning asymptotically less than (log n)k for some k, if and only if G is virtually nilpotent.

To answer your question, by considering congruence quotients of SL2Z, Bou-Rabee concludes that for every word of length n in the free group F2, there is a finite group of order O(n3) where the word is not an identity. The same bound can be obtained uniformly as follows. Ury Hadad gives a lower bound in "On the shortest identity in finite simple groups of Lie type" which implies that the shortest identity in PSL2(Fq) has length at least (q-1)/3. Since the size of PSL2(Fq) is order q3, this implies that every word of length at most n fails to be an identity in one single group PSL2(Fq) of order O(n3)!

I learned this argument from Martin Kassabov and Francesco Matucci's paper "Bounding the residual finiteness of free groups". In it, they use a nice analysis of finite groups with elements of "large order" to construct a word of length n in the free group F2 which is trivial in every finite group of order at most O(n2/3). This improved on the lower bound of n1/3 due to Bou-Rabee and McReynolds; I believe this is now the best lower bound known.

-
In fact, the article giving the best lower bound is remarkably similar to the method I used in my answer! For example, to get $k^{1/3}$ instead of my $k^{1/4}$, just replace the $x_i x_j^{-1}$ by $1,x,x^2,\ldots$. To improve this to $k^{2/3}$ requires only a little more group theory to describe groups having an element of large order, as you mentioned, so that the sequence of powers can be terminated earlier. –  Bjorn Poonen Feb 13 '10 at 5:24