# Looping through zeroes in polynomials

Question.

If $p$ is a polynomial of degree $n$ with $p(\alpha)=0$, what do we know of the polynomial $q$ (with degree $n-1$) such that the numbers $(q^k(\alpha))_{k=1}^n$ contain all of the zeroes of $p$?

Here I denote $q(q(\cdots q(\alpha)))=q^k(\alpha)$.

Notes.

We know for a fact such $q$ exists, since there always exists a polynomial of degree $n-1$ through $n$ given points. $q$ is not unique, however, since there are multiple permutations we can put the zeroes in.

Examples.

For linear $p$ (write $p(x)=a_1x+a_0$), this is obvious; $q(x)=\tfrac{-a_0}{a_1}=\alpha$ suffices. If $p(\alpha)=0$, then $q(\alpha)=\alpha$ indeed are all the zeroes of $p$.

If $p$ is quadratic, write $p(x)=a_2x^2+a_1x+a_0$, and have $p(\alpha)=0$ again; now $q(x)=\frac{-a_1}{a_2}-x$.

If $p$ is cubic, write $p(x)=a_3x^3+a_2x^2+a_1x+a_0$. This is where I get stuck, since the roots of cubic equations aren't expressions that are easy to work with.

Attempts.

First I see (denote the (not necessarily real) zeroes by $z_1,z_2,\cdots,z_n$) that $z_1+\cdots+z_n=\frac{-a_{n-1}}{a_n}$ and $z_1z_2\cdots z_n=\frac{(-1)^na_0}{a_n}$. We can produce similar expressions for the other coefficients, but I doubt this is useful; they're not even solvable for $n>4$. We also have (given $z_1$) $$-a_nz_1^n=a_{n-1}z_1^{n-1}+\cdots+a_1x+a_0$$ with which we can reduce every expression of degree $n$ or larger in $z_1$ to an expression of degree $n-1$ or smaller.

For $n=3$ (let's do some specific examples), we could write $q(x)=b_2x^2+b_1x+b_0$, and take for example $p(x)=x^3-x-1$. Then, if $\alpha$ is a zero of $p$, then $\alpha^3=\alpha+1$, and so $q(\alpha)^3=q(\alpha)+1$, which is

$$(b_2\alpha^2+b_1\alpha+b_0)^3=b_2\alpha^2+b_1\alpha+b_0+1$$

working out the constant terms gives $b_2^3+b_1^3+b_0^3+6b_0b_1b_2=b_0+1$ which isn't very useful either.

Please, enlighten me. Has there been done work on this subject, am I missing something obvious, or perhaps you see something that I missed?

• For $n=3$ and $p$ with all roots real, see math.stackexchange.com/questions/1767252/…. – lhf Mar 14 '17 at 10:03
• Your justification for the existence of $q$ does not convince me. I think you need $p$ irreducible and some Galois theory. – lhf Mar 14 '17 at 10:06
• @lhf $q$ always exist but the field its coefficients are in depends on the galois group of $p$ – mercio Mar 14 '17 at 10:08
• $p$ doesn't need to be irreducible as I found a corresponding $q$ for quadratic $p$, and quadratic polynomials are never irreducible – vrugtehagel Mar 14 '17 at 10:09
• @lhf, that's interesting. Because it has a root with multiplicity $2$, of course $q(0)=0$ and $q(q(0))=1$ isn't possible. We can however simply pick $q(x)=-\tfrac12x^2+-\tfrac12x+1$ to have $q(0)=1$ and $q(q(1))=0$ – vrugtehagel Mar 14 '17 at 10:47

For any sequence of $n$ distinct (complex) numbers $\alpha_1 \ldots \alpha_n$, there is a unique interpolating polynomial $Q$ of degree $n-1$ with $P(\alpha_i) = \alpha_{i+1}$.

In the generic case, the coefficients of $Q$ are in $\Bbb Q[\alpha_i, \delta^{-1}]$, where $\delta = \prod_{i<j} (\alpha_i - \alpha_j)$ (to be more precise, $\delta Q \in \Bbb Z[\alpha_i]$)

In the case where the $\alpha_i$ are roots of a polynomial $P$ with no repeated roots, then for any $n$-cycle $\sigma$, $Q_\sigma$ is defined over the splitting field of $P$, but sometimes it is defined over a smaller field.

If $G$ is the Galois group of $P$, the action of $G$ on the $Q_\sigma$ corresponds to its action on the set of $n$-cycles by conjugation.

If $K = \Bbb Q(a_i)$ is the field of definition of $P$ and $L_\sigma$ is the field of definition of $Q_\sigma$ for an $n$-cycle $\sigma$, then $[ L_\sigma : K ]$ is exactly the size of the orbit of $\sigma$ under this conjugation action. Since the normalizer of an $n$-cycle in $S_n$ is the subgroup of $S_n$ generated by the $n$-cycle, we have that the subgroup of $G$ fixing the $n$-cycle is $G_\sigma = G \cap \langle \sigma \rangle$, and then $L_\sigma = \Bbb Q(\alpha_i)^{G_\sigma}$, and finally $[L_\sigma : K] = |G| / |G_\sigma|$

For example, if $n=2$, there is only one $2$-cycle, so there is only one $Q$, and $L= K$ which means that there are formulas for the coefficients of $Q$ in terms of the $a_i$.

If $n=3$, there are two $3$-cycles. If $G \not \subset A_3$ then $G$ will switch them so you will get an orbit of size $2$, so the coefficients of $Q$ will be in a degree $2$ extension of $K$. If $G \subset A_3$ then $G$ won't switch them, which tells you that in this case $L_\sigma = K$. In fact you have formulas for the two $Q$ in terms of the $a_i$ and $\delta = \pm \sqrt \Delta$ (and you switch between the two $Q$ by switching the sign of $\delta$)

If $n=4$, there are $3! = 6$ $4$-cycles, living in $6/\phi(4) = 3$ different cyclic subgroups of order $4$, so lots of stuff can happen. In the worst case, $G = S_4$ and they are all defined in $3$ different (non-normal) extensions of order $6$ of $K$. $S_4$ is still solvable so if you really want to you can get formulas for $Q$ with square roots and cube roots.

If $n \ge 5$ well then $G$ may not even be solvable anymore so you won't have those formulas anymore.

The only way you can have $L_\sigma = K$ is when $|G_\sigma| = |G|$, which means $G \subset \langle \sigma \rangle$, and for this to happen $G$ has to be cyclic too (not necessarily of order $n$ if $P$ is not irreducible, though).

Let $\alpha=\alpha_1, \alpha_2, \ldots, \alpha_m$ be the distinct roots of $p$.

Choose a permutation $\sigma$ of $1,2,\dots,m$ without fixed points. For instance, an $m$-cycle such as $(12\cdots m)$.

Let $q$ be the unique polynomial such that $q(\alpha_i)=\alpha_{\sigma(i)}$. That will work, but won't have degree $n-1$.

• This is quite trivial though, I my question is more about what we know about $q$ besides the property we defined it with – vrugtehagel Mar 14 '17 at 11:05