# Integral polynomials dividing N!

Consider a polynomial $P(X)\in\mathbb Z[X]$. Is it true that $P(N)$ divides $N!$ for infinitely many integer $N$?

This question is motivated by the special case where $P(X) = X^2 + 1$ that appeared in a math olympiad.

I was wondering if anyone can point me to references of this question.

• Are you asking whether this holds for every single-variable polynomial with integer coefficients? – Jason Starr Nov 11 '16 at 12:54
• Yes I believe it might be. But could be gravely mistaken by missing the obvious. – S. Pek Nov 11 '16 at 12:55
• There are conjectures, e.g., by G. Martin, about the density of $N$ such that $P(N)$ is $N^{1/d}$-smooth. That might be enough to conclude that $P(N)$ divides $N!$. – Jason Starr Nov 11 '16 at 13:39
• I fixed the formatting and changed the wording a little. In the future, it would be better if you format your question using LaTeX. Two other comments. First, you said that "P(N) is a polynomial of finite degree". A polynomial, by definition, has finite degree. Second, it's best to distinguish the polynomial from its value. – Joe Silverman Nov 11 '16 at 13:56
• @LSpice Since the statement is clearly true for non-zero constant polynomials, I guess the OP was using "of finite degree" to mean "degree not equal to $-\infty$", where by convention the zero polynomial is assigned degree $-\infty$. (This is the right value if you want to define the $x$-adic absolute value to be $|f(x)|=e^{-\deg(f)}$.) But none-the-less, I think it's confusing to say "finite degree" instead of just saying that the polynomial is not the zero polynomial. – Joe Silverman Nov 11 '16 at 18:57

In general this is an open problem. A closely related problem (essentially equivalent) is to ask for the values $P(n)$ for $n$ of size $X$ to be $X$ smooth (i.e. composed only of primes below $X$). This is known for quadratic polynomials, but already open for general cubic irreducible polynomials. For some special polynomials (e.g. those of the form $ax^d+b$) such results are known, thanks to Schinzel, Balog and Wooley etc. For a description of related results, and more references, see this paper of Dartyge, Martin and Tenenbaum.

• I agree. To elaborate briefly on "essentially equivalent": once $P(n)$ is $x$-friable, the only other test to pass is that the power of $p$ dividing $P(n)$ is at most the power of $p$ dividing $n!$, for all primes $p$. It's easy to show that most numbers are almost squareefree—say, only $O(x/\log x)$ numbers up to $x$ have a square factor larger than $\log x$—and that only $O(x/\log x)$ numbers up to $x$ are divisible by $p^r$ where $p<\log x$ and $p^r > \log^2x$. One has to adapt this to the set of values of a fixed polynomial, which requires some bookkeeping, but the principles are the same. – Greg Martin Nov 12 '16 at 18:43

Wow! I have been thinking about this problem, too. I can prove that for every odd natural number $$d$$ there exists infinitely many $$n \in \mathbb{N}$$ such that $$n^{d}+1 \mid n!$$. Here you have my gorgeous proof of the case $$d=3$$ of the result (cf. https://oeis.org/A270441):

For every $$k \in \mathbb{N}$$ we have that

$$\begin{eqnarray*}(k^{6}+2k^{4}+k^{2}+1)^{3}+1 &=& (k^{2}-k+1)(k^{2}+2)(k^{2}+k+1) &\cdot& (k^{4}-k^{3}+2k^{2}-2k+1)(k^{4}+1)(k^{4}+k^{3}+2k^{2}+2k+1);\end{eqnarray*}$$

therefore, it follows that, for every $$k \in \mathbb{N} \setminus \{1\}$$, the natural number $$N_{k}:=k^{6}+2k^{4}+k^{2}+1$$ is such that $$N_{k}^{3}+1$$ divides $$N_{k}!$$. QED.

I have to finish something else now, but if you are interested in what I have mentioned, I may add more details about the result that I obtained later on.

• Do you have an algorithm to produce Q(k) such that P(Q(k)) is Q(k) smooth? Gerhard "Belt Sander Is Not Working" Paseman, 2016.11.11. – Gerhard Paseman Nov 11 '16 at 16:54
• Not that I know of... – José Hdz. Stgo. Nov 11 '16 at 17:09
• @PietroMajer: You are absolutely right! – José Hdz. Stgo. Nov 11 '16 at 18:45
• $N^3+1\mid N!$ is easy. See this question at Math.SE. If you can give an elementary answer to $N^5+1\mid N!$, my bounty offer there can be renewed :-) – Jyrki Lahtonen Nov 12 '16 at 5:50