I was messing around with polynomials and their real roots when I, as recreational mathematicians do, asked myself the following random question:

Suppose I am given a polynomial $P(x)$. How can I find the number of real roots of the polynomial $P^{\circ n}(x)$, representing the n-fold composition of $P$ with itself (counting multiplicity)?

I started with the simple polynomial $P_1(x)=x^2-1$. This was an easy example, as it turned out that $P_1^{\circ n}(x)$ has $n+1$ real roots, which was simple to prove.

My next example was the polynomial $P_2(x)=x^2-2$. This one was more difficult, but I eventually determined that $P_2^{\circ n}(x)$ has $2F_{n+1}-2$ real roots, where $F_n$ represents the sequence of Fibonacci numbers with $F_0=F_1=1$.

In general, I am considering polynomials of the form $P_c(x)=x^2-c$. For $c$ less than $-1$, the iterates of this polynomial have no real roots, and for $c$ greater than $3$, the $n$th iterate of this polynomial seems to have $2^n$ real roots.

The polynomial with which I am stumped is $$P_{3/2}(x)=x^2-\frac{3}{2}$$ While I have been unable to derive a formula for the number of real roots of $P_{3/2}^{\circ n}(x)$, by observing the number of real roots for the first couple of iterations, I have come up with the remarkable conjecture that the number of real roots of the $n$th iterate is given by $2p(n)$, where $p(n)$ represents the number of partitions of $n$.

This conjecture, if true, would be truly amazing. How can I prove it?

NOTE: To prove the formulae I obtained for $P_1$ and $P_2$, I divided the real line up into intervals that the polynomials in question sent to one another, and from this I obtained a recursive formula for each. However, I cannot figure out how to nearly divide $\mathbb R$ into intervals in the same way.

  • 3
    $\begingroup$ This is a great question, but perhaps you could give a little more detail before folks start working on it. You say that you've checked the formula for "the first couple of iterations", but does that mean $n = 1, 2, 3$, or $n = 1, 2, \ldots, 10$? More? Something in between? If you look only up to $n = 7$, there's another perfectly good sequence in OEIS (oeis.org/A027383, the number of balanced strings of length $n$) that matches the data, for instance. $\endgroup$ – John Hughes Sep 29 '18 at 16:24
  • $\begingroup$ @JohnHughes I have checked up through $n=8$. $\endgroup$ – Franklin Pezzuti Dyer Sep 29 '18 at 16:30
  • $\begingroup$ For $n=9$ or $n=10$ $P_{3/2}^n(0)<0$ (as seen from a graph), but $P_{3/2}^n\to\infty$ as $x\to\infty$, so it has an odd number of positive roots, but both $p(9)$ and $p(10)$ are even. I believe $P_{3/2}^9$ has $29$ positive roots ($p(9)=30$). $\endgroup$ – rogerl Sep 29 '18 at 20:34

I am unable to reproduce your results for $c=2$. I evaluate $P_2^{\circ 4}(x)$ as $x^{16} - 16x^{14} + 104x^{12} - 352x^{10} + 660x^8 - 672x^6 + 336x^4 - 64x^2 + 2$, which has $16$ real roots rather than $2F_5-2 = 14$.

As for $c=\frac32$, I confirm your coincidence up to $n=8$, but after that it breaks down. I calculate the first ten values as 2, 4, 6, 10, 14, 22, 30, 44, 58, 82.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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