# Divisibility chains and polynomials

Let $$P\in \Bbb{Z}[X]$$ be a polynomial with degree $$d>1$$.

It is conjectured that for all such $$P$$, their range for integer inputs $$R_P:=P(\Bbb{Z})$$ has finite intersection with the set of factorials $$\{n!:n\ge 0\}$$.

We say that $$P$$ is “good” if there does not exist some $$Q\in \Bbb{Z}[X]\setminus \{X\}$$ such that $$P \mid P\circ Q$$. Examples: if $$P=X^2$$ then $$Q=2X$$ shows $$P$$ isn’t good; if $$P=X^2-1$$, then $$Q=X^2$$ shows $$P$$ isn’t good.

I was curious if there are any counter-examples to the following stronger claim:

For all such good $$P$$, $$R_P$$ does not contain an infinite sequence $$a_1 where $$a_i \mid a_{i+1}$$ for $$i\ge 1$$. Or even stronger, there exists a constant $$C=C_P$$ so that $$R_P$$ does not contain divisibility chains longer than $$C$$.

Also, is there a nice characterization for when $$P$$ is good?

• You surely want to add some condition. E.g. if $P(x)=x^2-1$ you get an infinite divisibility chain by considering $P(2^{2^n})$. Sep 20 at 18:28
• @OfirGorodetsky ah, this thwarts my question. perhaps that is a reason why the case of $x^2-1$ is open for the factorial question. I guess I will amend the question. Sep 20 at 18:37
• Although my answer shows that any $P$ is a counter-example, maybe there is a modification for which there are no counter-examples, which is in between your notion (no infinite divisibility chain) and the factorial problem. For instance, requiring the infinite divisibility chain to satisfy a growth condition such as $a_{i+1}/a_i$ being at most $O(i^C)$ or even $e^{O(i)}$. My current counter-examples involve $a_{i+1}/a_i$ being huge (super exponential). Sep 20 at 19:24
• I agree there is a probably an interesting question there. however such a result would be incomparable with the factorial problem, since the conjecture is that $R_P$ only contains finitely many factorials (which could be absurdly spaced apart). Sep 20 at 20:41

Every $$P$$ is a counterexample. Indeed, given a polynomial $$P$$ consider the recursive sequence $$b_{n+1}=f(b_n)$$ where I take $$f(x)=x+P(x)$$, say. Then $$P(b_{n+1}) = P(b_n + P(b_n)) \equiv P(b_n) \equiv 0 \bmod P(b_n)$$ since $$x-y \mid P(x)-P(y)$$ in general. Setting $$a_n=P(b_n) \in R_P$$ this says that $$a_{n+1}$$ is divisible by $$a_n$$.
One can replace $$f$$ by more general polynomials. An important property of $$f$$ is that it permutes the roots of $$P$$.
• On the other hand, the same idea shows that no polynomial os good, as one can put $Q(x)=x+P(x)$. Sep 20 at 22:09