Define $x\_0=0$ and $x\_{i+1} = F(x\_i)$ for all integers $i \ge 0$, where $F(x)$ is a polynomial with integral coefficients such that $x\_{i}\rightarrow\infty$ as $i$ grows large.
Suppose $l(p)$ is the least positive integer such that $p|x\_{l(p)}$ for some prime $p$.


Then if we let
$$P\_{(0<\alpha<1)} = \{ p\in \mathbb{P}\mid l(p)<p^{\alpha}\}$$ where $\mathbb{P}$ is the set of primes and also $P\_{\alpha}(x)$ is the set of primes belonging to $P\_{\alpha}$ which are less than $x$ , do we have any result proving a strong upper bound on the cardinality of set $P\_{\alpha}(x)$ for some large parameter $x$?


In particular, I want to know if for $\alpha=\frac{1}{2+\epsilon}$ we have $P\_{\alpha}(x)=O(\frac{x}{(\log{x})^{1+\gamma}})$ for two constants $\epsilon>0$ and $\gamma>0$?


**P.S Sorry MO users my earlier post had some errors so I am reposting it.**



do we have any result proving a strong upper bound on the cardinality of set $P_{\alpha}(x)$ for some large parameter $x$?
As pointed out already in the comments, you need extra assumptions to ensure that you get the behavior you want. I shall comment under such assumptions.


Consider the simplest case of $F$ a linear polynomial, say for instance $F\_e(x):=ex+(e-1)$ for a fixed $e \in \mathbb N$. Then you are asking for the multiplicative order $\ell\_e(p)$ of $e$ modulo $p$.


In this case, the answer is that your ansatz is known under GRH, otherwise there is no known way to go beyond the $1/2$ exponent.


The best paper to reference for this is [Kurlberg&Pomerance 2004](https://arxiv.org/pdf/math/0405120.pdf). In the first pages, they survey known results on $P\_\alpha(x)$. The best unconditional theorem gives the bound for $\alpha=1/2-o(1)$, while for $1/2-\varepsilon$ you need RH for certain Kummer extensions; the closest to what you are seeking is I believe in [Pappalardi](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.8.6190&rep=rep1&type=pdf), but the methods trace back to Hooley's work on Artin's conjecture.


So, although nothing is known besides these $F$, the natural guess would of course be that for any reasonable $F$ you can get as far as $1/2-o(1)$ unconditionally and prove your desired bound under some form of RH. Still, extending the result from the "Artin" setting of multiplicative orders to the cousin problem of iterates of polynomials would be an absolutely noteworthy task and by no means easy. To search for other works that prove the basic results and analogies, you can start from [my survey](http://www.seminariomatematico.polito.it/rendiconti/78-1/Tron.pdf) (last section).


