Size of the smallest group not satisfying an identity.

Question

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?

Here are some observations that have come from earlier discussions I have had about this question.

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.

Answer 1

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$

Answer 2

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 SL₂Z, Bou-Rabee concludes that for every word of length n in the free group F₂, there is a finite group of order O(n³) 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 PSL₂(F_q) has length at least (q-1)/3. Since the size of PSL₂(F_q) is order q³, this implies that every word of length at most n fails to be an identity in one single group PSL₂(F_q) of order O(n³)!

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 F₂ which is trivial in every finite group of order at most O(n^2/3). This improved on the lower bound of n^1/3 due to Bou-Rabee and McReynolds; I believe this is now the best lower bound known.