38
$\begingroup$

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

$\endgroup$
6
  • 8
    $\begingroup$ 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. $\endgroup$ May 24, 2015 at 1:20
  • $\begingroup$ @BenjaminSteinberg Can that example be used to answer the current question (with the particular $\Pi_2$ or $\Sigma_2$ forms using only two variables)? $\endgroup$ May 24, 2015 at 1:23
  • $\begingroup$ @JoelDavidHamkins, I am not sure whether it can be recoded $\endgroup$ May 24, 2015 at 1:37
  • $\begingroup$ @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$. $\endgroup$
    – Joël
    May 24, 2015 at 3:26
  • 2
    $\begingroup$ @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. $\endgroup$ May 24, 2015 at 3:32

4 Answers 4

32
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – owb
    May 25, 2015 at 1:35
  • $\begingroup$ 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$. $\endgroup$
    – owb
    May 25, 2015 at 1:53
21
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ This addresses only Question 1; also can you make it direct rather than indirect? +1 in any case $\endgroup$ May 24, 2015 at 5:00
  • $\begingroup$ @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. $\endgroup$ May 24, 2015 at 5:12
  • 2
    $\begingroup$ @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. $\endgroup$
    – owb
    May 25, 2015 at 1:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – owb
    May 25, 2015 at 1:31
  • $\begingroup$ @owb: Thanks, you are right, of course. I've incorporated your correction now. $\endgroup$ May 25, 2015 at 16:26
2
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ I don't really see, how do you relate the free group to what's true of all groups? $\endgroup$ May 24, 2015 at 9:02
  • 3
    $\begingroup$ @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. $\endgroup$ May 24, 2015 at 14:41
  • 1
    $\begingroup$ 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$. $\endgroup$ May 24, 2015 at 21:21
  • $\begingroup$ @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 $\endgroup$ May 25, 2015 at 20:44
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – owb
    May 28, 2015 at 20:11
  • $\begingroup$ Thanks for your advice. I have asked this as a new question. $\endgroup$
    – owb
    May 28, 2015 at 22:08
  • 1
    $\begingroup$ New question: mathoverflow.net/questions/207887/… $\endgroup$ May 28, 2015 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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