25
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ Are you asking whether this holds for every single-variable polynomial with integer coefficients? $\endgroup$
    – Jason Starr
    Commented Nov 11, 2016 at 12:54
  • $\begingroup$ Yes I believe it might be. But could be gravely mistaken by missing the obvious. $\endgroup$
    – S. Pek
    Commented Nov 11, 2016 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
    Commented Nov 11, 2016 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
    Commented Nov 11, 2016 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
    Commented Nov 11, 2016 at 18:57

2 Answers 2

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Nov 12, 2016 at 18:43
10
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Nov 11, 2016 at 16:54
  • $\begingroup$ Not that I know of... $\endgroup$
    – José Hdz. Stgo.
    Commented Nov 11, 2016 at 17:09
  • 1
    $\begingroup$ @PietroMajer: You are absolutely right! $\endgroup$
    – José Hdz. Stgo.
    Commented Nov 11, 2016 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
    Commented Nov 12, 2016 at 5:50

You must log in to answer this question.

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