8
$\begingroup$

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<a_2<\dots$ 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?

$\endgroup$
4
  • 2
    $\begingroup$ 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})$. $\endgroup$ Sep 20 at 18:28
  • $\begingroup$ @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. $\endgroup$ Sep 20 at 18:37
  • $\begingroup$ 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). $\endgroup$ Sep 20 at 19:24
  • $\begingroup$ 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). $\endgroup$ Sep 20 at 20:41

1 Answer 1

8
$\begingroup$

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$.

$\endgroup$
1
  • 3
    $\begingroup$ On the other hand, the same idea shows that no polynomial os good, as one can put $Q(x)=x+P(x)$. $\endgroup$ Sep 20 at 22:09

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.