Could the orbit of $0$ through a polynomial be dense in $\mathbb R$? Could we construct a polynomial $P(x)\in\mathbb R[x]$ such that the sequence $(x_n)$ which is given by $x_0=P(0)$ and $x_{n+1}=P(x_n)$ for any $n\ge0$, is dense in $\mathbb R$ ?. 
I guess the answer is no, but I could not prove it. 
 A: The theory of iteration of polynomial functions is well understood. It is usually studied in the complex plane, but its methods and results apply to the real line.
To answer your question:

No orbit under the iteration of a polynomial is dense in the real line.

Indeed:


*

*An orbit of a point under the iteration of a polynomial $P(x)$ either remains bounded forever or escapes to infinity.

*The set of starting points whose orbit is bounded form a compact set, called the filled Julia set.
Explicitly, if $P(x)=a_d x^d + \cdots +a_1 x + a_0$, then all orbits starting outside the circle of radius $R = \dfrac{1+|a_d|+\cdots+|a_0|}{|a_d|}$ centered at the origin escape to infinity, a bound given by Douady.
Therefore, an orbit can be dense at most inside a compact interval. This does happen: $P(x)=x^2-2$ with $x_0=0$ is an example.
All this is the elementary part of the theory.
For this and much more, see the classic books The Beauty of Fractals and The Science of Fractal Images, and the surveys by Blanchard, Milnor, and Devaney and Keen.
A: This is, indeed, impossible. Let's split the treatment into several cases.


*

*If $P(x)$ is quadratic or higher, then the ratio $P(x)/x\to\pm\infty$ when $x\to\pm\infty$. Consequently there exists a real number $M>0$ such that $|P(x)/x|>2$ whenever $|x|>M$. If $P$ were to produce a dense sequence, then there exists an $n$ such that $x_n\in[M,M+1)$. But it follows that $|x_m|>2M$ for all $m>n$, so the sequence contains only finitely many numbers in the interval $[-2M,2M]$.

*If $P(x)=ax+b$ is a linear polynomial with $|a|>1$, then the same argument goes thru with factor $2$ replaced with $(|a|+1)/2$.

*If $P(x)=ax+b$ with $|a|<1$, then $P(x)$ is a contraction with a single fixed point.

*If $P(x)=x+b$, then it produces an arithmetic progression with interval $b$. This is not a dense subset.

*If $P(x)=-x+b$, then $P(P(x))$ is of the form handled in case 4, and we get an arithmetic progression and its reflected copy.



As I suggested in a comment, the polynomial $P(x)=2x^2-1$ produces a sequence that is dense in the interval $[-1,1]$. A key property of this polynomial is that $P(\cos x)=\cos 2x$ for all $x$. BUT, for this to work we do need to be able to freely choose the starting point $x_0$.
Consider the following number, written in base two
$$
z=0.01\,00011011\,000001010011100101110111\,\ldots.
$$
That is,in the fractional part  we first have all the single bit sequences, "0" and "1", followed by all the sequences of two bits, followed by all the sequences of three bits et cetera.
If we denote by $\{x\}$ the fractional part of a real number then, by construction, the set
$$
A(z)=\left\{\{2^nz\}\,\bigg\vert\, n\in\Bbb{N}\right\}
$$
is a dense subset of $[0,1]$. This is because any finite sequence of bits will appear as the most significant part of $\{2^nz\}$ for some $n$.
If we set $x_0=\cos (2\pi z)$, then it follows by induction that
$$
x_n=\cos(2\pi 2^nz)=\cos(2\pi\{2^nz\}).
$$
Therefore the sequence $(x_n)_{n\in\Bbb{N}}$ is dense in $[-1,1]$.
A: Constant polynomial - obviously the orbit is not dense.  
Degree 1 - also fairly obviously not dense.  
Degree 2 or more: 
For the moment, I will assume that the coefficient of the highest power of $x$ is positive.  Since the degree is greater than 1, by order type arguments, there will be a point beyond which it is greater than the linear polynomial $2x$.  If the orbit never exceeds this limit then clearly it is not dense.  If it does exceed it then after the first point beyond the limit, it will at least double for each iteration and hence cannot be dense.  
If the coefficient of the highest power is negative, we can simply look at every second point.  
