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.

  • $\begingroup$ Are you asking whether this holds for every single-variable polynomial with integer coefficients? $\endgroup$ – Jason Starr Nov 11 '16 at 12:54
  • $\begingroup$ Yes I believe it might be. But could be gravely mistaken by missing the obvious. $\endgroup$ – S. Pek Nov 11 '16 at 12:55
  • 3
    $\begingroup$ 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!$. $\endgroup$ – Jason Starr Nov 11 '16 at 13:39
  • 5
    $\begingroup$ 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. $\endgroup$ – Joe Silverman Nov 11 '16 at 13:56
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • 3
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 11 '16 at 16:54
  • $\begingroup$ Not that I know of... $\endgroup$ – José Hdz. Stgo. Nov 11 '16 at 17:09
  • 1
    $\begingroup$ @PietroMajer: You are absolutely right! $\endgroup$ – José Hdz. Stgo. Nov 11 '16 at 18:45
  • 2
    $\begingroup$ $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 :-) $\endgroup$ – Jyrki Lahtonen Nov 12 '16 at 5:50

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.