# Symmetric group action on squarefree polynomials

The following dynamical system on polynomials comes mostly from idle curiosity, but I hope it is of some interest.

Background Fix some natural number $n$. Let $P$ be the quotient of the polynomial ring $\mathbb{Z}[x_1,\ldots,x_n]$ by the ideals $\lbrace(x_j^2=x_j)~|~1\leq j \leq n\rbrace$.

Let $\Sigma(n)$ denote the symmetric group on $n$ elements and note that it acts on $P$ by permuting the variables. The polynomials $P'$ fixed by all $\sigma \in \Sigma(n)$ are sums and products of the symmetric polynomials and we can enumerate them by monomial degree. That is, the subring $P' \subset P$ is generated by the basic polynomials $S_1 = x_1 + \ldots + x_n$, $S_2 = x_1x_2 + \ldots + x_{n-1}x_n$ and so forth, with $S_n = x_1x_2\ldots x_n$.

Consider the function $s:P \to P'$ defined as follows. $s$ takes a polynomial $p \in P$ to $$\prod_{\sigma \in \Sigma(n)}\sigma(p).$$ Also consider a function $e:P' \to P$ defined by sending the basic symmetric polynomial $S_j$ to its corresponding $x_j$ and extending the domain to all of $P'$ via $\mathbb{Z}$-linearity.

The "dynamical system" I'm interested in comes from the self-map $f = e\circ s: P \to P$.

Example Consider $n = 2$ and $p = x_1$. Then, $s(p) = x_1x_2 = S_2$ and so $f(p) = e(S_2) = x_2$. Then, $f^2(p) = e \circ s(x_2) = e(x_1x_2) = x_2 = f(p)$. Thus, $p$ lies in the basin of attraction of the fixed point $x_2$. On the other hand, if you start with $p = 2x_1+x_2$ then the orbit of $p$ is $$2x_1 + x_2 \to 2x_1 + 5x_2 \to 10x_1 + 29x_2 \to \ldots$$

Question What can be said about the behavior of $f:P \to P$ in terms of fixed points, periodic orbits, etc. for arbitrary $n$?

Update Contrary to what was stated in the prior versions of this question, neither $s$ nor $e$ is a ring homomorphism.

-
Your map e is not a ring homomorphism. The ring P' is generated by the element $S_1$. The quotient that identifies $S_{n-1}$ with $S_n$ is known to be isomorphic to the subalgebra of the group algebra of the symmetric group generated by the top-to-random shuffle operator with $1/nS_1$ mapping to this operator. – Benjamin Steinberg Jul 27 '12 at 16:55
Fair enough, I have updated the question to just call e a function. That being said, I don't see how $P′$ is generated by $S_1$ alone. How on earth do you get $2S_2$ from $S_1$ without having $\sqrt{2} \in\mathbb{Z}$? – Vidit Nanda Jul 27 '12 at 17:36
$S_k=S_1^k/k!$ in this ring, because the other terms vanish. Your system sends $x_1\dots x_k$ to a multiple of itself and projects everything else onto the space generated by those guys. It's basically a diagonal matrix. – Will Sawin Jul 27 '12 at 18:16
It is generated by $S_1$ over Q. I didn't read carefully enough that you were working over Z. – Benjamin Steinberg Jul 27 '12 at 19:00
To make a comment about the problem posed in the question: There are three obvious fixed points: $p=0$, $p=1$ and $p=x_n$. I believe those are all, but I got stuck trying to prove this. I think I proved that all other fixed points, the existence of which I doubt, must have the form $1-x_1+c_2x_2+\ldots+c_nx_n$ for certain $c_i\in\mathbb Z$. One more obvious observation is that the polynomials such that the constant term and the coefficients of $x_1,\ldots,x_k$ are all zero form an $f$-stable subspace (in some sense neighborhoods of the fixed point $x_n$). – Florian Eisele Jul 27 '12 at 22:21

Interesting things happen if you reduce this dynamical system modulo some integer $N$.

This makes sense because your map $s$ is compatible with reduction modulo $N$, and your map $e$ is $\mathbf{Z}$-linear, so $f$ induces a map $f_N : P_N \to P_N$ with $P_N = P \otimes \mathbf{Z}/N\mathbf{Z}$.

In the case $N=2$, what is the map $f_2$? Note that $P_2 = \mathbf{F}_2[x_1,\ldots,x_n]/(x_1^2-x_1,\ldots,x_n^2-x_n)$ can be identified with the ring of functions $\mathbf{F}_2^n \to \mathbf{F}_2$ (every such function is polynomial!). This ring is in bijection with the powerset of $\mathbf{F}_2^n$ : we can map any subset of $\mathbf{F}_2^n$ to its characteristic function. Now, the map $s_2: P_2 \to P_2$ has a very natural interpretation : it maps a subset $A$ of $\mathbf{F}_2^n$ to the subset $\cap_{\sigma \in \Sigma(n)} \sigma(A)$. Also, by definition, the image of $e_2 = e \otimes \mathbf{F}_2$ is contained in the set of affine hyperplanes of $\mathbf{F}_2^n$ (together with $\emptyset$ and $\mathbf{F}_2^n$).

So we want to determine which affine hyperplanes are fixed by $f_2$. This is not obvious at first sight, since the map $e_2$ doesn't seem to have a nice interpretation like $s_2$. But luckily, some linear algebra over $\mathbf{F}_2$ shows that there are only $6$ possibilities for $s_2(H)$ where $H$ is an affine hyperplane of $\mathbf{F}_2^n$. Namely $s_2(H)=H$ when $H$ is symmetric, and $s_2(H)$ can only be $\emptyset$, $\{0\}$, $\{1\}$ or $\{0,1\}$ otherwise. Here $0$ resp. $1$ denotes the constant vector $(0,\ldots,0)$ resp. $(1,\ldots,1)$. It's possible to compute the image by $e_2$ of these subsets, and after some computations we find that the only fixed points of $f_2$ are the polynomials $0$, $1$, $x_n$, together with $1+x_1+\cdots+x_{n-1}$ when $n$ is odd.

Now let's go back to $\mathbf{Z}$. Obviously every fixed point $p$ of $f$ must reduce to a fixed point of $f_2$ mod $2$. Conversely, we have a kind of Hensel lemma : every fixed point of $f_2$ lifts to a unique fixed point of $f_{\mathbf{Z}_2} : P \otimes \mathbf{Z}_2 \to P \otimes \mathbf{Z}_2$. Here $f_{\mathbf{Z}_2}$ is defined by just replacing the base ring $\mathbf{Z}$ by $\mathbf{Z}_2$ in the definition of $f$.

This lifting property is a consequence of the following fact : $f$ is contracting for the $2$-adic topology on every ball $p_0+2P$ with $p_0 \in P$. Indeed, assume $p=p_0+2q$ with $q \in P$. Then

\begin{equation*} s(p) = \prod_{\sigma \in \Sigma(n)} p_0^\sigma + 2q^\sigma \equiv s(p_0)+2\sum_{\sigma} q^\sigma \cdot \prod_{\tau \neq \sigma} p_0^\tau \pmod{4} \end{equation*}

Now, observe that the stabilizer $H$ of $\overline{p_0} \in P_2$ in $\Sigma(n)$ is isomorphic to $\Sigma(m) \times \Sigma(n-m)$ for some $0 \leq m \leq n$, so in particular $\operatorname{card}(H) \geq 2$. This implies that $\prod_{\tau \neq \sigma} \overline{p_0}^\tau = s(\overline{p_0})$ in $P_2$. Furthermore $\sum_{\sigma} \overline{q}^\sigma = 0$ since the stabilizer of $\overline{q} \in P_2$ has even order. It follows that $s(p) \equiv s(p_0) \pmod{4}$. The same argument shows that $p \equiv p_0 \pmod{2^m}$ implies $s(p) \equiv s(p_0) \pmod{2^{m+1}}$, so $s$, and thus $f$, is contracting.

It follows immediately that the only fixed points of $f$ in the balls $2P$, $1+2P$ and $x_n+2P$ are $0$, $1$ and $x_n$ respectively. It remains to consider the fixed point $1+x_1+\cdots+x_{n-1}$ with $n \geq 3$ odd. The corresponding fixed point of $f_{\mathbf{Z}_2}$ is obtained as the limit of $f^m(1+x_1+\cdots+x_{n-1})$ in $P \otimes \mathbf{Z}_2$ when $m \to \infty$.

EDIT This question is still surprising me. I thought this fixed point would not belong to $P$, but it does. In fact $1-x_1+x_2 -\cdots +x_{n-1} \in P$ is a fixed point of $f$ for any odd $n \geq 3$. This is because of the following identity in $P$

\begin{equation*} \prod_{\sigma \in \Sigma(n)} 1-x_{\sigma(1)}+x_{\sigma(2)}- \cdots +x_{\sigma(n-1)} = 1-S_1+S_2-\cdots+S_{n-1} \end{equation*} which is true because it's true for any choice of $x_1,\ldots,x_n \in \{0,1\} \subset \mathbf{Z}$ (both sides are $0$ except when $x_1=\cdots=x_n=0$).

To sum up, for $n \geq 2$ the only fixed points of $f$ are $0$, $1$, $x_n$, together with $1-x_1+x_2-\ldots+x_{n-1}$ for odd $n$.

By the same method, one might determine the periodic orbits of $f$. Since $f$ is contracting on each ball, each $f$-orbit reduces mod $2$ to a $f_2$-orbit with the same period. The only non-trivial orbit of $f_2$ is $\{1+x_1,1+x_1+\cdots+x_n\}$. Again, this non-trivial orbit lifts to a unique orbit in $P \otimes \mathbf{Z}_2$, but I don't know whether this orbit is in $P$. I guess the next step would be to determine all preperiodic points of $f$.

This method also suggests to study the analogous dynamical system on $P = \mathbf{Z}[x_1,\ldots,x_n]/(x_1^p-x_1,\ldots,x_n^p-x_n)$ for any prime $p$.

-
Thank you, this looks like a good approach. – Vidit Nanda Oct 21 '12 at 5:24
@Vel Nias : you're welcome, thanks for this interesting question. – François Brunault Oct 21 '12 at 23:54

It might be helpful to extend this system from $\mathbb Z$ to $\mathbb R$.

$x_n$ is always a fixed point.

For $n=2$, this is only the periodic orbit. This is because the equations are just $a_1^*=a_1a_2$, $a_2^*=a_1^2+a_2^2$ if we write $f=a_1x_1+a_2x_2$. Thus, on a periodic orbit, we have $a_2\geq 0$, and if $a_2$ ever gets above $1$ then it blows up. Meanwhile, the geometric mean of the $a_2$s must be $1$ to keep $a_1$ constant, so $a_2$ must be exactly $1$, so $a_1$ must be $0$.

In general, we can simplify the problem by considering the special case where the first several $x_i$ are $0$. For instance, $ax_{n-1}+bx_n$ gets sent to

$(a+b)^{(n-1)!(n-2)} (ab)^{(n-1)!}x_{n-1}+(a+b)^{(n-1)!(n-2)}( (a+b)^{2(n-1)!}-(ab)^{(n-1)!})x_n$

This doesn't seem to help.

-