The symmetric group theory of natural numbers

Question

Sometimes it is not easy to formulate a correct question. Here is a better version of this question (I still do not know if it is optimal, but it is better than the previous one).

We say that a set $X$ of natural numbers is symmetric group definable if there exists a first order formula $\theta$ in the group signature such that a symmetric group $S_n$ satisfies $\theta$ if and only if $n\in X$. Of course finite sets and sets with finite complements are symmetric group definable. It is not completely trivial to find any infinite set of natural numbers with infinite complement which is symmetric group definable. But it is not a difficult exercise to show that the set of numbers $n$ such that either $n$ or $n-1$ is prime is such a set.

Question. Is any of the following sets symmetric group definable?

1) the set of even numbers

2) the set of prime numbers

A more vague question Is there a characterization of the Boolean algebra of symmetric group definable sets?

Update Noam D. Elkies' answer below shows that the Boolean algebra contains many sets. Noah Schweber's answer of the previous question suggests looking at the computational complexity of $X$. Clearly, checking whether $n$ belongs to a symmetric group definable set $X$ takes time at most $(n!)^k$ where $k$ is the number of quantifiers in the corresponding formula $\theta$. So we have a couple of even better questions.

Question 1 Is the converse true, that is every set of numbers recognizable by deterministic a Turing machine in time $\le (n!)^k$ for some $k$ symmetric group definable? Here the size of a number $n$ is $n$ that is we consider the unary representation of natural numbers.

Question 2 Let us replace $S_n$ by, say, $SL_n(\mathbb{F}_2)$ and similarly define $SL_n(\mathbb{F}_2)$-definable sets of numbers. Will the Boolean algebra of all $SL_n(\mathbb{F}_2)$-definable sets coincide with the Boolean algebra of all deterministic polynomial time decidable sets of natural numbers?

Question 3 Can the statements that "Primes are in P" be proved this way?

Answer 1

It's possible to embed within the theory of the permutation group $S_n$ the theory of second-order arithmetic for numbers between $0$ and $n-1$. Using this we can construct propositions corresponding to any property of $n$ that can be determined by a Turing machine with resource bound that roughly corresponds to a maximum of $\sqrt {n}$ steps. With additional quantifiers we can add a finite amount of alternation to this complexity class and get a PH-like complexity class.

As Noam Elkies points out, for $n > 6$ simple transpositions are characterized by a first-order property. To be self-contained, I'll repeat his definition: $g$ is a simple transposition if $g^2 = 1$ and for any conjugate $g'$ of $g$, the order of $g g'$ is either $1$, $2$, or $3$.

Next, it is possible to encode a point in the underlying set acted on by the permutation group (that is, a point in $[n] = \{1, 2, \dots, n\}$) as pair of simple transpositions $(g_0, g_1)$ such that $g_0 g_1$ has order $3$, which represent the unique point which is transposed on both $g_0$ and $g_1$. The pairs $(g_0, g_1)$ and $(h_0, h_1)$ represent the same point if and only if for each $i \in \{0, 1\}$ and $j \in \{0, 1\}$ the product $g_i h_j$ is either the identity or order $3$. Next, given a permutation $g$ and a point $x$ encoded by $(h_0, h_1)$, the action of $g$ on $x$ is encoded by $(g^{-1} h_0 g, g^{-1} h_1 g)$. Seeing as we can quantify over all the points and compare points for equality, any two-sorted formula involving both permutations and points can be translated into an equivalent formula involving only permutations. Therefore I can freely incorporate points into my language for defining properties.

Permutations can also encode sets of points: Given a permutation $g$, define $Q (g)$ to be the set of all points not fixed by $g$. Then the sets $Q (g)$ for all $g \in S_n$ vary over all subsets of $[n]$ other than the ones with a single point. Then if $\phi (X)$ is a formula with a variable $X$ representing a subset of $X$, we can translate the quantifier $\forall X. \phi (X)$ into $\forall g \in S_n. \phi 45 (Q (g)) \land \forall x \in [n]. \phi (\{x\})$, where $\phi (Q (g))$ means we replace all instances of $y \in X$ with $g (y) \neq y$, and $\phi (\{x\})$ means we replace all instances of $y \in X$ with $x = y$. The formula $\exists X. \phi (X)$ is translated similarly. Therefore we can also add subsets of $[n]$ into our language.

I define that $g_0$ is cyclically contained in $g_1$ if for every point $x$ either $g_0 (x) = x$ or $g_0 (x) = g_1 (x)$. Equivalently, the cyclic decomposition of $g_0$ is a subset of the cyclic decomposition of $g_1$, not counting fixed points as cycles. Then a cycle can be defined as a permutation that is not the identity and such that every permutation cyclically contained in it is either equal to it or equal to the identity. A maximal cycle is a cycle without any fixed points.

For everything below, I will fix a maximal cycle $S$ and a point $O$. The lettering is intended to be suggestive of Peano arithmetic.

A permutation commutes with $S$ if and only if it is a power of $S$. I define the addition relation $x + y = z$ to mean that there exists a permutation $g$ which commutes with $S$ such that $g (O) = x$ and $g (y) = z$. I will denote by $x+y$ the unique point $z$ such that $x + y = z$.

I call a permutation $g$ linear if $g (x + y) = g (x) + g (y)$ for all $x$ and $y$. $x$ is call invertible if there is a linear permutation $g$ such that $g S (O) = x$. If $x$ is invertible I define the product $x \cdot y$ to be $g (y)$ for the unique such $g$. For an arbitrary $x$ I define $x \cdot y = z$ if there is a decomposition $x = x_0 + x_1$ or $x = x_0 + x_1 + x_2$ with $x_0, x_1, x_2$ all invertible and $z = x_0 \cdot y + x_1 \cdot y$ or $z = x_0 \cdot y + x_1 \cdot y + x_2 \cdot y$, respectively.

To define the order relation we can use subsets: I define $x < y$ if there is a subset $X \subseteq [n]$ such that

1. $S (x) \in X$.
2. If $a \in X$, then either $a = y$ or $S (a) \in X$.
3. $O \notin X$.

Using all of the definition above as tools it should be possible to define whether some tuple of subsets $X_0, \dots, X_{r-1}$ denote a Turing machine computation. With a naive encoding of the computation as a concatenation of the state of the Turing machine at every time step, it is necessary that the computation terminate before the spacetime resource usage is greater than a fixed multiple of $n$, where the spacetime resource usage is defined as the sum of the space usage over each time step. With this it should be possible to define "$X_0$ encodes the binary representation of $x$" whenever $x$ less than the square root of $n$, by giving the input $x$ in unary. The binary representation of $n$ can be determined via a formula $n = x \cdot y + z$ where $y$ is a power of $2$ (definable as in Peano arithmetic) and $z < y$ and given the binary representations of $x$ and $z$. Verifying $n = x \cdot y + z$ comes down to the identity $x \cdot y + z = O$ plus the claim that $x \cdot y$ doesn't overflow. $n$ can also be split into three components to give more leeway for constant and logarithmic factors. Giving the binary representation of $n$ as input to a Turing machine allows defining all properties that checkable by a Turing machine with these resource bounds.

More sophisticated encoding schemes, making full use of the information encoded by a permutation rather than just thinking of it as a subset, should lead to a higher computational capacity. Using alternating quantifiers $\forall Y_0 \exists Y_1 \forall Y_2 \dots \exists Y_{s-1}$ and including $Y_0, \dots, Y_{s-1}$ as inputs to the computation, it should be possible to define all properties within a PH-like complexity class where the final verification step is restricted to computations with this spacetime resource bound or whatever resource cost the more sophisticated encoding takes.

Answer 2

Suppose $n>6$. Then we give a "symmetric group definition" of the set $\{2 | n \}$. Since Mark Sapir already revealed in the comments how to define "$n$ or $n-1$ is prime", this also gives definitions of the set of primes (and of primes-plus-$1$).

First we give a first-order definition of simple transpositions. (This would not be possible for $n=6$ because simple and triple transpositions are equivalent under an outer automorphism of $S_6$.) Namely: $g$ is a simple transposition iff $g$ is of order $2$ and, for any conjugate $g'$ of $g$, the product $gg'$ has order $1$, $2$, or $3$.

We can then define involutions without fixed points: $g$ is such an involution iff for every simple tranposition $h$ the product $gh$ has order $2$ or $4$. (If an involution $g$ does have a fixed point $x$ then there's a simple transposition $h$ that switches $x$ with a non-fixed point, and then $gh$ has order $3$ or $6$ according as $g$ is a simple tranposition or not.)

Then $n$ is even iff $S_n$ has an involution without fixed points.

Answer 3

Almost the same first-order sentence that Noam used to define transpositions defines, in $SL_n(\mathbb F_2)$, a unipotent transvection (i.e. with a single $2\times 2$ Jordan block, and the rest $1 \times 1$).

The sentence is "$g$ has order $2$, and its product with any conjugate of itself has order at most $4$".

Indeed, if $g$ has order $2$ then $g$ is unipotent, with all Jordan blocks of size at most $2$. If it has one of size at most $2$ then $g$ times any conjugate of $g$ fixes a codimension two subspace, hence has order $1,2,3$, or $4$. On the other hand, if $g$ has $k$ Jordan blocks, we can view it as a unipotent matrix with a single Jordan block over $\mathbb F_{2^k}$, so using $$\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix} \begin{pmatrix} 1 & 0 \\ x & 1 \end{pmatrix}=\begin{pmatrix} 1+x & 1 \\ x & 1\end{pmatrix} $$ we can produce any conjugacy class in $SL_2(\mathbb F_{2^k})$, and in particular an element of order $2^k+1>4$.

I suspect from appropriate finite configurations of transvections one can define the disjoint union of the set of nonzero vectors and the set of nonzero linear functions (it is not possible to separate these because of the inverse-transpose automorphism) but I wasn't able to make it work yet.

Answer 4

We can define the set $P$ of primes. That is, there is a 1st order sentence in the language of groups that holds in $S_n$ iff $n$ is prime.

Indeed, as already mentioned by Noam, we can recognize the set $O$ of odd numbers. Next, I show below that we can recognize the set $I$ of elements $k$ such that either $k$ or $k-1$ is prime. Since $P=\{2\}\cup (O\cap I)$, we can recognize $P$.

Let check that we can recognize $I$ by a single sentence. For a group $G$ and $c\in G$ say that $G$ (or $c$) satisfies $R(c)$ if $c\neq 1$ and every nontrivial element in the centralizer of $c$ has an abelian centralizer. As a 1st-order sentence:

$$R(c)\Leftrightarrow c\neq 1\wedge \forall x,y,z:(x\neq 1 \wedge\; [x,c]=[x,y]=[x,z]=1)\Rightarrow [y,z]=1.$$

Then, in a symmetric group $S_n$, an element $c$ satisfies $R(c)$ if and only if $c$ is a $p$-cycle with $p$ prime and $p\in\{n,n-1\}$.

Indeed, the sole condition that $c$ has an abelian centralizer implies that it's a disjoint product of cycles of pairwise distinct length.

Assuming $R(c)$, if two lengths $\ge 2$ occur, then $c$ has some nontrivial power with nonabelian centralizer and hence $R(c)$ fails. So either $c$ is a $k$-cycle with $k\in\{n,n-1\}$. Again if $k$ is non-prime then $c$ has some nontrivial power with nonabelian centralizer and hence $R(c)$ fails.

Conversely, for $p$ prime and $n\in\{p,p+1\}$, a $p$-cycle $c$ satisfies $R(c)$ in $S_n$ (its centralizer being reduced to the subgroup it generates).

So the sentence $\exists c:R(c)$ characterizes, among those symmetric groups $S_n$, those for which either $n$ or $n-1$ is prime. (This is a $\exists\forall$-sentence.)

---

Comment on Mark's approach. Instead of $R(c)$, he uses $Q(c)$, which says that $c\neq 1$ and that any two nontrivial elements in the centralizer of $c$ are conjugate. Namely

$$Q(c)\Leftrightarrow c\neq 1\wedge \forall x,y:(x,y\neq 1 \wedge\; [x,c]=[y,c]=1)\Rightarrow \exists z:zxz^{-1}=y.$$

In symmetric groups $S_n$, $Q(c)$ and $R(c)$ are equivalent: these are precisely $p$-cycles when $p$ is prime and belongs to $\{n,n-1\}$.

Still, let's benefit of this alternative approach.

A first remark is that they differ in more general groups, and even in the closely related setting of alternating groups. For instance, observe that in $\mathrm{Alt}_p$ or $\mathrm{Alt}_{p+1}$, a p-cycle $c$ satisfies $R(c)$ but not $Q(c)$. So if we're rather interested in alternating groups (a number of people study ultraproducts of finite simple groups) then only the formula $R$ gives something (actually it seems that $\mathrm{Alt}_n$ satisfies $\exists c:R(c)$ iff $\{n,n-1,n-2\}$ contains a prime).

We can also try to modify $Q$ and define more things for symmetric groups. For instance we can consider $Q'(c)$ to mean that $c\neq 1$ and the centralizer of $c$ meets at most two conjugacy classes of elements of order $\ge 3$.

$$Q'(c)\Leftrightarrow c\neq 1\wedge \forall x,y,z:(x^2,y^2,z^2\neq 1 \wedge\; [x,c]=[y,c]=[z,c]=1)\Rightarrow$$ $$\exists t:txt^{-1}=y \vee tyt^{-1}=z\vee tzt^{-1}=x.$$

If I'm correct, $Q'(c)$ characterizes in $S_n$ $p$-cycles with $p$ prime in $\{n,n-1,n-2\}$ (and a few more elements if $n\le 6$). So, that $S_n$ satisfies $\exists c:Q'(c)$ characterizes those $n$ such that $\{n,n-1,n-2\}$ contains a prime.