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?

Improve this question
$\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$
    – Ofir Gorodetsky
    Commented Sep 20, 2022 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$
    – Zach Hunter
    Commented Sep 20, 2022 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$
    – Ofir Gorodetsky
    Commented Sep 20, 2022 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$
    – Zach Hunter
    Commented Sep 20, 2022 at 20:41

1 Answer 1

Reset to default
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$.

Improve this answer
$\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$
    – Ilya Bogdanov
    Commented Sep 20, 2022 at 22:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .