Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
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

2 Answers 2

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

share|improve this answer
    
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

I keep misreading this question.

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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