# 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
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