# Number of real roots of an iterated quadratic: $x^2-3/2$

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.

• 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. – John Hughes Sep 29 '18 at 16:24
• @JohnHughes I have checked up through $n=8$. – Franklin Pezzuti Dyer Sep 29 '18 at 16:30
• 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$). – 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.