# On sentences true in all finite groups

Let $w$ be a group word with two variables $x$ and $y$. Is the sentence $(\forall x)(\exists y)w=1$ true in every group if it is true in every finite group? The same question about the sentence $(\exists x)(\forall y)w=1$.

• cmi.univ-mrs.fr/~coulbois/articles/equation.pdf gives an equation which has a solution in all finite groups but not in the free group. – Benjamin Steinberg May 24 '15 at 1:20
• @BenjaminSteinberg Can that example be used to answer the current question (with the particular $\Pi_2$ or $\Sigma_2$ forms using only two variables)? – Joel David Hamkins May 24 '15 at 1:23
• @JoelDavidHamkins, I am not sure whether it can be recoded – Benjamin Steinberg May 24 '15 at 1:37
• @Christian: what about $w=x^2$? or $w=x^n$ for any $n \in \mathbb Z$? or $w=y x y^{-1}$? All those words are $1$ for $x=1$ whatever the value of $y$. – Joël May 24 '15 at 3:26
• @Joel: Let me try to make more sense: if the word doesn't contain inverses (I wish the OP could clarify this point), then a $w$ that makes the second sentence true in all finite groups can't contain $y$ (obvious, because otherwise you could refute it in a sufficiently large cyclic group). With inverses, the situation should be similar, although it's not totally clear to me right now how to formulate this in a clean way. – Christian Remling May 24 '15 at 3:32

The answer is Yes for the second question, about $(\exists x)(\forall y)w=1$. Following Christian Remling's idea: If a sentence like $$\exists x(\forall y)(yxy^{-1}x^2y^{-9}\dots=1)$$ holds in all finite groups then it holds in $\mathbb Z/n\mathbb Z$ where it just says (for certain constants $a,b,c,d$) $$(\exists x)(\forall y)((a-b)x+(c-d)y=0).$$ The only way this can be true is if $c=d$. So the exponents of $y$ in $w$ add up to 0. In that case, the sentence is true in all groups because we can take $x=e$, the group identity (called 1 by the OP).

The answer is also Yes on Question 1. If $\forall x\exists y (w=1)$ holds in $\mathbb Z/n\mathbb Z$ then there it says $ax=by$, i.e., $b$ divides all $ax$, so $b$ divides $a$. But then in any group given $x$ we can take $y=x^{-a/b}$.

On the other hand, Wikipedia gives the following $\Pi^0_2$ sentence where the answer is No: given two elements of order 2, either they are conjugate or there is a non-trivial element commuting with both of them.

• Your argument allows to show a more general statement. Suppose a sentence $$\theta:=(\exists x_1\dots x_m)(\forall y_1\dots y_n)w(x_1,\dots ,x_m,y_1,\dots ,y_n)=1$$ is true in infinitely many finite cyclic groups. Then (1) $l_i=0$ for all $i$, where $l_i$ is the sum of exponents of $y_i$ in $w$; (2) $\theta$ holds in all abelian groups; (3) if $n=1$ then $\theta$ holds in all groups. Note that if $n>1$, it is not clear whether `$\theta$ holds in all finite groups' implies '$\theta$ holds in all groups'. In particular, for $\theta$ of the form $(\exists x)(\forall yz)w(x,y,z)=1$. – owb May 25 '15 at 1:35
• It suffices to prove 1, because it implies 2,3: put $x_i=1$ for all $i$. Let $k_i$ be the sum of exponents of $x_i$ in $w$. Then in abelian groups $\theta$ is equivalent to $$\phi:=(\exists x_1\dots x_m)(\forall y_1\dots y_n)x_1^{k_1}\dots x_m^{k_m}y_1^{l_1}\dots y_n^{l_n}=1.$$ In groups the sentence $\phi$ is equivalent to $$\psi:=(\forall y_1\dots y_n) y_1^{l_1}\dots y_n^{l_n}=1,$$ and hence to $\rho:=\bigwedge_i(\forall y) y^{l_i}=1$. The order of any finite cyclic group, in which $\rho$ holds, divides all $l_i$. Since there are infinitely many such cyclic groups, all $l_i=0$. – owb May 25 '15 at 1:53

This is true. Write $w(x,y)=x^{m_1}y^{n_1}\ldots x^{m_k} y^{n_k}$, with $m_j,n_j\in\mathbb Z$.

Suppose that your sentence fails in some infinite group. So $\forall y\: w(a,y)\not= 1$ in this group, for some $a$. Then in particular, taking $y=a^r$, we have that $a^{m+rn}\not=1$ for all $r\in\mathbb Z$, with $m=\sum m_j$, $n=\sum n_j$. This implies that $m+zn=0$ has no solution $z\in\mathbb Z$. But then $n$ does not divide $m$, and thus $m+zn\equiv 0\mod n$ can not be solved in $\mathbb Z_n$ either, or we have $n=0$, $m\not=0$. In either case, $\forall x\exists y\: w(x,y)=1$ already fails in a finite cyclic group (of order $n$, if $n\not=0$).

• This addresses only Question 1; also can you make it direct rather than indirect? +1 in any case – Bjørn Kjos-Hanssen May 24 '15 at 5:00
• @BjørnKjos-Hanssen: I don't think this is really indirect, it's just the way I worded it, and you had already answered the second question. I just noticed you also added exactly the same argument to your answer before me, I didn't see this originally, sorry. – Christian Remling May 24 '15 at 5:12
• @Cristian Remling: There is a small inaccuracy in your argument: '$m+zn=0$ has no solution $z\in \mathbb Z$' does not imply 'that $n$ has a prime factor that does not occur in $m$' (counterexample: $m=p$ and $n=p^2$, for a prime $p$). You claim: if $(\forall x)(\exists y) w(x,y)=1$ holds in all cyclic groups of prime orders then it holds in all groups. This is not true: for any prime $p$ and $w=x^py^{p^2}$ this sentence holds in every cyclic group of prime order but fails in the infinite cyclic group. – owb May 25 '15 at 1:29
• Here is a correct end of your argument: '$m+zn=0$ has no solution $z\in \mathbb Z$' implies that $n$ does not divide $m$, and hence $(\forall y) w(1,y)\ne 1$ and so $(\exists x)(\forall y) w(x,y)\ne 1$ hold in the cyclic group of order $n$. Thus if $(\forall x)(\exists y) w(x,y)=1$ holds in all cyclic groups then it holds in all groups. – owb May 25 '15 at 1:31
• @owb: Thanks, you are right, of course. I've incorporated your correction now. – Christian Remling May 25 '15 at 16:26

I put the following as answer as it does not fit within the limits of a comment, hoping that it could help. In fact, the free group is the limit of finite truncations. Below is the proposed method.

Let $k=\mathbb{F}_2$ be the usual galois field with two elements
integers, we consider

1. an infinite alphabet $X$ (denumerable is enough)
2. the set of noncommutative series $\mathcal{A}=k<<X>>>=k^{X^*}$ (i.e. all functions $X^*\rightarrow k$ with the convolution product)
3. the augmentation character $k<<X>>>\rightarrow k$ and its kernel $\frak{M}$ (series without constant term) and, for every finite subalphabet $\mathrm{F}\subset X$, the ideal $\frak{M}_\mathrm{F}$ of the series such that every monomial of the support contains at least a letter outside $\mathrm{F}$
4. the free group over $X$, $\Gamma=\Gamma(X)$
5. the group morphism $\mu : \Gamma\rightarrow 1+\frak{M}$ given by $$(\forall x\in X)(\mu(x)=1+x)$$ which is known to be into (Magnus transformation)
6. the quotients $\mathcal{A}_{n,\mathrm{F}}=k<<X>>>/(\frak{M}^n+ \frak{M}_\mathrm{F})$ (which are finite) and the surjective quotient morphisms $q_{n,\mathrm{F}} : k<<X>>>\rightarrow \mathcal{A}_{n,\mathrm{F}}$
7. the groups $\Gamma_{n,\mathrm{F}}$, images of $q_{n,\mathrm{F}}\circ \mu$ which are finite

... and if a word $w$ in the free group fails to be $1$ iff it fails to be $1$ in one of the finite groups $\Gamma_{n,\mathrm{F}}$.

An interesting alternative is to take a two letter alphabet $X=\{a,b\}$, an embedding $j$ of an infinitely generated free group as the subgroup generated by the set of conjugates $\{a^nba^{-n}\}_{n\geq 0}$, set $\mathcal{A}_n=k<<X>>>/(\frak{M}^n)$ take the surjective quotient morphisms $q_n : k<<X>>>\rightarrow \mathcal{A}_n$ and replace $q_{n,\mathrm{F}}\circ \mu$ by $q_n\circ \mu\circ j$.

• I don't really see, how do you relate the free group to what's true of all groups? – Bjørn Kjos-Hanssen May 24 '15 at 9:02
• @BjørnKjos-Hanssen: The sentences in question are positive, hence preserved by homomorphic images, and every group is a homomorphic image of a free group. One would need a free group over infinitely many generators for this to work, though. – Emil Jeřábek May 24 '15 at 14:41
• However, for the first sentence, the free group with one generator is enough: If $\forall x\exists y\: w=1$ holds in $\mathbb Z$ and $x\in G$ is given, map $1\mapsto x$ and take as $y$ the image (under this homomorphism) of the $y'\in \mathbb Z$ that exists by assumption. So the (first) sentence holds in all groups precisely if it holds in $\mathbb Z$. – Christian Remling May 24 '15 at 21:21
• @EmilJeřábek I think you are right. Then, I modified my text. Thanks. As I did it (too) quickly, I did not explore the fact that any free group can be embedded in a two generator free group. Vote +1 for Bjorn's answer – Duchamp Gérard H. E. May 25 '15 at 20:44

The posed questions can be naturally generalized as follows. Let $w$ be a group word with variables $\bar x, \bar y$, where $\bar x=(x_1,\dots ,x_m)$ and $\bar y=(y_1,\dots ,y_n).$ Is the sentence $(\forall\bar x)(\exists\bar y)w=1$ true in every group if it is true in every finite group? The same question about the sentence $(\exists\bar x)(\forall\bar y)w=1$.

It is known that there is a group word $w$ with $m=2$ and $n=4$ such that $(\forall\bar x)(\exists\bar y)w=1$ is true in all finite groups but false in some free group [T. Coulbois, A. Khelif, Equations in free groups are not finitely approximable, Proc. AMS 127 (1999), No. 4, 963--965]. So, in general, the answer to the first question is NO. I don't know whether the answer to the second question is NO, in general. Note that for all sentences of the form $(\forall\bar x)v(\bar x)=1$ the answer is YES, because free groups are residually finite.

The arguments suggested by Bjorn Kjos-Hanssen and Christian Remling show that for $m=n=1$ the answer is YES for both of the questions. This can be generalized as follows. Denote $\phi:=(\forall\bar x)(\exists\bar y)w=1$ and $\psi:=(\exists\bar x)(\forall\bar y)w=1$.

(1) If $\phi$ holds in all finite cyclic groups then (i) $\phi$ holds in all abelian groups, and (ii) if $m=1$ then $\phi$ holds in all groups.

(2) If $\psi$ holds in infinitely many finite cyclic groups then (i) $\psi$ holds in all abelian groups, and (ii) if $n=1$ then $\psi$ holds in all groups.

Note that in (1) "holds in all finite cyclic groups" cannot be replaced with "holds in infinitely many finite cyclic groups" because there is $\phi$ with $m=n=1$ such that $\phi$ holds in all cyclic groups of prime order but fails in the infinite cyclic group. It is easy to show that, for any prime $p$, $(\forall x)(\exists y)x^py^{p^2}=1$ is an example of such $\phi$.

The following questions remain open:

(a) Is the sentence $(\forall x_1x_2)(\exists y)w(x_1,x_2,y)=1$ true in every group if it is true in every finite group?

(b) Is the sentence $(\exists x)(\forall y_1y_2)w(x,y_1,y_2)=1$ true in every group if it is true in every finite group?

Here are proofs of statements (1) and (2). Denote by $k_i$ and $l_j$ the sums of exponents of $x_i$ and $y_j$ in $w$, respectively.

Proof of (1). Suppose $\phi$ fails in a group $G$. Then $(\forall \bar y)w(\bar a,\bar y)\ne 1$ holds in $G$ for some $m$-tuple $\bar a=(a_1,\dots ,a_m)$. First assume that $G$ is an additive abelian group. Then $$G\models(\forall \bar y)(\sum_i k_ia_i+\sum_jl_jy_j)\ne 0.$$ We show that $\phi$ fails in a finite cyclic group; this will give a proof of (1)(i).

First consider the case when all $l_j=0$; then some $k_i\ne 0$. Let, say, $k_1\ne 0$. Then, for any integer $q$ which does not divide $k_1$, the sentence $(\exists \bar x)(\forall \bar y)w(\bar x,\bar y)\ne 0$ holds in the group $\mathbb Z_q$: take as $\bar x$ the tuple $(1,0,\dots,0)$.

Now suppose that $l_i\ne 0$ for some $i$. Let $d$ be the greatest common divisor of all~$l_j$. Then $d$ does not divide some $k_i$. (Indeed, otherwise $\sum_i k_ia_i=da$ for some $a\in G$. Since $d=\sum_jl_jr_j$ for some integers $r_j$, we have $\sum_i k_ia_i=da=\sum_jl_jr_ja$, and so $$G\models \sum_i k_ia_i+\sum_jl_j(-r_ja)=0,$$ which contradicts to the choice of $\bar a$.) Let, say, $d$ does not divide $k_1$. Then the sentence $(\exists \bar x)(\forall \bar y)w(\bar x,\bar y)\ne 0$ holds in the group $\mathbb Z_d$: take as $\bar x$ the tuple $(1,0,\dots,0)$.

Now we prove (1)(ii). Suppose $m=1$; thus $(\forall \bar y)w(a_1,\bar y)\ne 1$ holds in $G$ and so in its cyclic subgroup generated by $a_1$. Since that subgroup is abelian, this implies that $\phi$ fails in a finite cyclic group.

Proof of (2). Suppose $\psi$ holds in infinitely many finite cyclic groups. It suffices to show that $l_j=0$ for all $j$. Indeed, in this case $(\forall \bar y)w(1,\dots ,1,\bar y)=1$ holds in any abelian group, and even in any group if $n=1$.

In abelian groups the sentence $\psi$ is equivalent to the sentence $$\theta:=(\exists \bar x)(\forall \bar y) x_1^{k_1}\dots x_m^{k_m}y_1^{l_1}\dots y_n^{l_n}=1.$$ In any group the sentence $\theta$ is equivalent to the sentence $$\tau:=(\forall y_1\dots y_n) y_1^{l_1}\dots y_n^{l_n}=1.$$ (Indeed, if $\tau$ is true then $\theta$ is true because we can put all $x_i=1$. If $\theta$ is true in a group, and $a_1,\dots ,a_m$ witness that, then $a_1^{k_1}\dots a_m^{k_m}=1$ because we can put all $y_i=1$; hence $\tau$ holds.) Clearly, in any group the sentence $\tau$ is equivalent to the sentence $\rho:=\bigwedge_i(\forall y) y^{l_i}=1.$ In particular, $\psi$ is equivalent to $\rho$ in finite cyclic groups. Therefore the order of any finite cyclic group in which $\psi$ holds divides all $l_i$. Since there are infinitely many such cyclic groups, all $l_i=0$.

• I have also edited my questions and added to them new questions that remained open. I have added another answer in order to present everything I now understand about the questions in the most general form. – owb May 28 '15 at 20:11
• Thanks for your advice. I have asked this as a new question. – owb May 28 '15 at 22:08
• New question: mathoverflow.net/questions/207887/… – Bjørn Kjos-Hanssen May 28 '15 at 22:57