We shall prove that the only such polynomials decompose into linear factors of form $4x-a^2$. Clearly, such polynomials satisfy the conditions. Now, suppose that $f$ satisfies the condition. We suppose that $f$ is irreducible, otherwise look at all irreducible factors.Let $g(x)=f(n^2)$ Assume that $p|g(k)$. We can asume $0\leq k \leq \frac p2$, since obviously $g(p\pm k)\equiv g(k)$ $(mod$ $p)$. Then, $p \leq 2k+r$, for some $r$. So we have either $k=\frac p2, k=\frac{p-1}2, \ldots,k=\frac{p-r}2$. We know that infinitely many prime number divide some of $g(n)$, therefore for some $0\leq j \leq r$ there are infinitely many primes $p$ for which $p|g(\frac{p-j}2)$. This implies that $p|g(-\frac j2)$ for infinitely many $p$, so $g(-\frac j2)=0$, thus $2x+j|g(x^2)$, and also $2x-j|g(x^2)$, so $4x^2-j^2|g(x)$, so $4x-j^2|f(x)$. As $f$ is irreducible, $f=4x-j^2$. QED

This is Harazi's? Nice.

iura wrote: We know that infinitely many prime number divide some of $g(n)$ Why is that? I hope that this question doesn't seem THAT dumb...

This is a known problem already discussed in the forum. For example, suppose that there are a finite number of primes $p_1,\ldots,p_r$ dividing some $p(x)$. Let $p_i^{r_i}|p(x_i)$. Choose $x\equiv x_i$ $(mod$ $p_i^{r_i+1}$ $)$ then we see that $p_i^{r_i+1}$ doesn't divide $p(x)$, hence $p(x)< \prod p_i^{r_i+1}$. But we can choose infinitely many such $x$ which implies that $p$ is constant. Happy Easter!

Sorry for sounding unintelligent, but what is this question asking me to do??

This reminds me heavily of IMO 2008 # 3... just focus on the prime first and find the $n$ rather than vice-versa. If $f$ is the (possibly empty) product of linear factors of the form $4n-a^2$, then it satisfies the condition. We will prove no other polynomials work. In what follows, assume $f$ is irreducible and nonconstant. It suffices to show for every positive integer $c$, there exists a prime $p$ and a nonnegative integer $n$ such that $n \le \tfrac{p-1}{2} - c$ and $p$ divides $f(n^2)$ Firstly, recall there are infinitely many odd primes $p$, with $p>c$, such that $p$ divides some $f(n^2)$, by Schur's Theorem. Looking mod such a $p$ we can find $n$ between $0$ and $\tfrac{p-1}{2}$ (since $n^2 \equiv (-n)^2 \pmod p$). We claim that only finitely many $p$ from this set can fail now. For if a $p$ fails, then its $n$ must be between $\tfrac{p-1}{2} - c$ and $\tfrac{p-1}{2}$. That means for some $0 \le k \le c$ we have \[ 0 \equiv f\left( \left(\frac{p-1}{2}-k\right)^2 \right) \equiv f\left( \left( k + \frac12 \right)^2 \right) \pmod{p}. \]There are only finitely many $p$ dividing \[ \prod_{k=1}^c f\left( \left( k+\frac12 \right)^2 \right) \]unless one of the terms in the product is zero; this means that $4n-(2k+1)^2$ divides $f(n)$. This establishes the claim and finishes the problem.

First note that by Schur's theorem, the set of prime divisors of $f(n^2)$ is infinite as $n$ ranges over positive integers. Take some $p$ in this set. Then there exists some $m$ such that \[f(m^2) \equiv f(r^2) \equiv f((p-r)^2)\equiv 0 \pmod{p}\] where $m \equiv r \pmod{p}$ and $0 \le r \le p-1$. Now since evidently one of $r,p-r$ is less than $\frac{p}{2}$, we see that there are infinitely many integral $n$ such that $f(n^2)$ has a prime divisor greater than $2n$. Now if the sequence $p(f(n^2))-2n$ is bounded above, there exists an odd positive integer $k$ such that there are infinitely many integral $n$ with $p(f(n^2))-2n=k$. This means that $2n+k \mid f(n^2)$ for infinitely many integral $n$, implying that $2x+k \mid f(x^2)$. Now since $f(0) \neq 0$, we see that $2x-k \mid f(x^2)$ as well. Now note that if $g(x)$ is some irreducible factor of $f(x)$, then $g(x^2)$ satisfies the conditions of the problem as well, since $p(f(n^2)) \ge p(g(n^2))$, so $g(x^2)=4x^2-k^2 \implies g(x)=4x-k^2$ for all irreducible $g$, factors of $f$. Now all that remains is to check that all such $f$ work, which can be seen by writing \begin{align*}f(n^2) &=g_1(n^2) \cdot g_2(n^2) \cdots g_m(n^2)\\ &=(2n+k_1)(2n-k_1) \cdots (2n+k_m)(2n-k_m)\end{align*} and noting that $p(f(n^2))-2n \le \max(k_i)$ so we are done. $\Box$

I can't agree more with v_Enhance about the IMO 2008 P3 part. :p.The first idea which came to mind while solving this was the $n^2+1$ problem. :p However,can this be generalized by replacing $p(f(n^2))$ with $p(f(n^{2k}))$ and $p-2n$ with $p-2kn$. ?

Call a polynomial $f\in\mathbb{Z}[X]$ bad if the sequence \[S_f:=\{p(f(n^2))-2n\}_{n\ge 0}\]grows arbitrarily large. Our goal is to find all not bad polynomials. First, note the following lemma. Lemma: If a polynomial $g$ is bad, then any multiple of $g$ is also bad. Proof: Suppose $f=gh$ is a multiple of some bad $g$. The key observation is that $p(g(m)h(m))\ge p(g(m))$, so all elements of $S_f$ are at least as large as those of $S_g$. Since $S_g$ grows arbitrarily large, then so does $S_f$. $\blacksquare$ We now focus our attention on irreducible polynomials $f$. Claim: If $f$ is irreducible, not constant, and not a multiple of $4x-a^2$ for some integer $a$, then $f$ is bad. Proof: Fix any positive integer $M$. We'll show that there exists some prime $p$ such that \[\frac{p-1}{2}-n>M\]and $p\mid f(n^2)$, which clearly finishes. Since $f$ is not constant, by Schur's theorem, there exist infinitely many primes dividing $f(n^2)$ for some $n$. Furthermore, since $f$ is not a multiple of $4x-a^2$, the rational numbers \[f(1^2/4),f(3^2/4),f(5^2/4),\ldots\]are all non-zero. Now, pick $p$ larger than the numerators of $f(1^2/4),f(3^2/4),\ldots,f((2M+1)^2/4)$ and $p\mid f(n^2)$ for some $n$. From this, we see that \[p\nmid f\left(\left(\frac{p-1}{2}-r\right)^2\right)\]for all $0\le r\le M$, so by reducing $n$ mod $p$ and possibly replacing it with $n-p$, we can force $n<\frac{p-1}{2}-M$, as desired. This completes the proof of the claim. $\blacksquare$ Combining the lemma and the claim, we see that the only polynomials that stand a chance of being not bad are ones that are a constant times a product of a bunch of polynomials of the form $4x-a^2$. Suppose $f$ is such a polynomial. We see that $4n^2-a^2=(2n-a)(2n+a)$, so all prime factors of $f$ are bounded above by $2n+C$ for some sufficiently large constant $C$, which means $S_f$ is bounded above by $C$. So the answer is polynomials which factor completely into factors of the form $4x-a^2$.

Consider any nonconstant irreducible factor $g(x)$ of $f(x)$. First, let $P$ be the set of primes that divide $g(x^2)$ for some integer $x$. Lemma. $P$ is infinite. Proof. Suppose for contradiction that $P$ is finite. Let the polynomial $g_1(x)=g(x^2)$. If $g_1(0)=0$, then the lemma is obviously true. If $g_1(0)\neq 0$, let $g_1(x)=xg_2(x)+g_1(0)$, and take $x=x_0=(\max P)!g_1(0)$. Then $g_1(x_0)=g_1(0)\left((\max P)!g_2(x_0)+1\right)$, and any prime dividing $(\max P)!g_2(x_0)+1$ is larger than $\max P$, which is a contradiction. Therefore $P$ is infinite. Fix a positive integer $c$. The sequence being bounded implies that there doesn't exist a prime $p\in P$ such that $p\mid g(n^2)$ and $p\ge 2n+2c+1 \Longleftrightarrow n\le \frac{p-1}{2}-c$. Then since $n$ can be picked to lie in $[0,\frac{p-1}{2}]$, $p$ must divide $g((\frac{p-1}{2}-k)^2)$ for some $0\le k\le c$. Vary $p$ inside $P$, and since $P$ is infinite, by pigeonhole there exists $0\le k\le c$ such that infinitely many primes $p\in P$ satisfy \[0 \equiv g((\frac{p-1}{2}-k)^2) \equiv g((k+\frac{1}{2})^2) \pmod{p}.\]Hence $g((k+\frac{1}{2})^2)=0$ and the factor $(4x-(2k+1)^2)$ divides $g(x)$. Because $g$ is irreducible, $g(x)=4x-(2k+1)^2$. We conclude that $f(x)$ is the product of (possibly a constant) and factors in the form $4x-(2k+1)^2$ for integer $k$. It's clear that all such $f$ work since $f(x^2)$ factors into $\prod(2x-2k-1)(2x+2k+1)$.

The polynomials are all polynomials $f$ generated by choosing a set of odd nonnegative integers $a_1,\dots,a_m$, some nonzero integer $c$, and taking $f(x)=c\displaystyle\prod_{i=1}^m (4x-a_i^2)$. To check that all such polynomials work, note that for any $n$, we have \[p(f(n^2)) = \max \left(p(c),\max_{i=1}^m p(2x-a_i),\max_{i=1}^m p(2x+a_i)\right),\]so $p(f(n^2))-2n$ is bounded above by $p(c)+\max_{i=1}^m a_i$. Now, we show any solution $f$ is of this form. First, note we are done if $f$ is constant. Otherwise, by Schur's Theorem, there are infinitely many prime divisors of $f$. Pick such a prime $p > 2$ and let $n$ be the minimal nonnegative integer $n$ such that $p \mid f(n^2)$. Observe that if $m$ is such that $p \mid f(m^2),$ then so are $m-p, m+p,$ and $-m.$ Hence, we can ensure that $n\le p/2.$ Now, by the condition, we have $p-2n \le k$ for some constant $k,$ so $n \ge p/2 - c$ for some constant $c.$ Since there exist infinitely many such primes $p,$ there exists some constant $\ell$ such that $p \mid f((p/2-\ell)^2)$ for infinitely many primes $p.$ Note that $g(p) = f((p/2-\ell)^2)$ is a rational polynomial in $p$ with coefficients that are dyadic numbers. For any prime $p$ such that $p \mid g(p),$ we see that the constant coefficient of $g$ is divisible by $p$. This holds for infinitely many primes $p,$ so $g(p) = ph(p)$ for some polynomial $h.$ Now, note that the constant coefficient of $g(p), 0,$ must be equal to $f(\ell^2).$ Because $p$ is odd, $p/2-\ell = n$ is an integer implies $\ell$ is of the form $a/2$ for some nonnegative odd integer $a$. This implies that the minimal polynomial of $a^2/4=\ell^2$, $4x-a^2$, must divide $f$. Note that $f(x)/(4x-a^2)$ must also satisfy the same properties as $f$, so we can iteratively divide by expressions of the form $4x-a^2$ until we have a constant $f$, yielding the claimed solution set.

WLOG assume $f$ is irreducible. Suppose its bounded above by $c$. So for every prime $p$ dividing $f(n^2)$, we have $p < 2n+c$. Pick one such prime, then we have that there is a number $\frac{p-c}{2} \le n \le \frac{p-1}{2}$ such that $p | f(n^2)$, because we can negate $n$ if needed. Suppose $n = \frac{p-k}{2}$. By PHP, since there are infinitely many primes, there is some $k$, say $z$, which is used infinitely many times. So we have $p | f \left( \left(\frac{p-z}{2}\right)^2 \right) \implies p | f \left(\frac{z^2}{4} \right)$ for infinitely many primes. Therefore, we must have this is $0$, so $4x - z^2$ is a factor of $f$ (note that $z$ is odd). Since we'd assumed $f$ irreducible initially, we get the entire solution set as $f(n) =c \prod_{i=1}^m (4n - (2z_i+1)^2)$ for any integers $z_i, c$, which indeed works. $\blacksquare$

before.

The answer is all polynomials of the form $f(x)=a(4x-a_1^2)(4x-a_2^2)\ldots(4x-a_k^2)$ for all $a_i$ odd, which clearly work. Note that if two polynomials $f,g$ satisfy then condition then $fg$ does too, and vice versa, so we only need to consider irreducible $f$. If $f(x) \neq 4x-a^2$ for some $a$, then I will show that for every positive integer $c$ there exists some $(n,p)$ with $n \leq \tfrac{p-1}{2}-c$ such that $p \mid f(n^2)$, which finishes. Indeed, suppose otherwise. By Schur's theorem there are infinitely many $p>c$ with $p \mid f(n^2)$ for some $n$ (treating $f(n^2)$ as a polynomial in $n^2$), so considering modulo $p$ there are infinitely many $p \mid f(n^2)$ with $p \leq \tfrac{n-1}{2}$ (as $n^2\equiv (p-n)^2 \pmod{p}$). As such, it suffices to show that there exist finitely many $0 \leq k<c$ with $$p \mid f\left(\left(\frac{p-1}{2}-k\right)\right) \iff p \mid f\left(\left(k+\frac{1}{2}\right)^2\right).$$This is equivalent to $$\prod_{k=0}^{c-1} f\left(\left(k+\frac{1}{2}\right)^2\right)$$having a finite number of prime divisors (that is, a finite number of primes $p$ such that the $\nu_p$ of the expression is positive), which is always true unless the expression equals zero. If it does, then there is some $k$ with $$f\left(\left(k+\frac{1}{2}\right)^2\right)=0 \implies x-\left(k+\frac{1}{2}\right)^2 \mid f(x) \implies 4x-(2k+1)^2 \mid f(x),$$which is of the form $4x-a^2$. We are done. $\blacksquare$

Mocking USAMO 2006 day 1 result p3: 90 mins, 7 seconds (fully scored :3) First note that for any polynomials $g,h$ we get $p(g(x)h(x)) \ge p(g(x))$ so if $g$ was a polynomial we are not looking for in this case then any $g \times h$ would also not hold, hence we can just wlog $f$ to be irreducible. Basically note that by Schur the set of primes diving $f(n^2)$ is infinite as we have $f(n^2) \ne 0$, so now let $n \equiv a \pmod p$ and note that $p \mid f(a^2)$ and $p \mid f((p-a)^2)$ but one of these is less than $\frac{p}{2}$ so there exists infinitly $m$ such that there is a prime divisor of $f(m^2)$ that is greater than $2m$ hence since $p(f(n^2))-2n$ is a sequence bounded above there must exist some odd $\ell$ such that $2n+\ell \mid f(n^2)$ for infinitly many $n$ so it holds that $2x+\ell \mid f(x^2)$, now set $x=\frac{p-\ell}{2}$ where $p$ is a arbitrary large prime to get that $p \mid f \left(\frac{\ell^2}{4} \right)$ which gives that $4x-\ell^2 \mid f(x)$ so $f(x)=4x-\ell^2$. Hence any polynomial that has only linear factors of the form $4x-b^2$ works thus we are done

We'll prove that if $f$ isn't the product of linear factors of the form $4n - a^2$, then the sequence $(p(f(n^2)) - 2n)_{n \ge 0}$ is unbounded. Note that if $f, g$ satisfy the condition then $fg$ does too, so we can assume $f$ is irreducible. Let $\deg f = k$ and let $N$ be an integer such that $2^{2k}\cdot |f(x)| < Nx^{k+1}$ for all $x \ge \frac{1}{2}$. Since $f$ is non-constant, so by Schur's theorem there are infinitely many primes $p$ such that there exists $n$ such that $p \mid f(n^2)$. Let $p$ be a large prime and let $n$ be the smallest positive integer such that $p \mid f(n^2)$. As $p \mid f((p-n)^2)$, so $n < p - n$. Thus $2n < p$. Let $s = p - 2n$, then $n \equiv -\frac{s}{2}$, so $p \mid f(\frac{s}{2})$ and since $p$ is odd, so $p \mid 2^{2k} \cdot f(\frac{s}{2})$ and note that $2^{2k} \cdot f(\frac{s}{2})$ is an integer, so if $f(\frac{s}{2}) \neq 0$, then $p < 2^{2k}|f(\frac{s}{2})| < N \cdot (\frac{s}{2})^{k+1}$. Therefore $s > 2(\frac{p}{N})^{\frac{1}{k+1}}$, and since $p$ is large enough, thus $s$ can be arbitrarily large. So $f(\frac{s}{2}) = 0$ and $f$ is irreducible, so $f(x) = 4x - s^2$. Thus $f(x) = a(4x - a_1^2)(4x - a_2^2) \cdots (4x - a_k^2)$ for some odd integers $a_1, a_2, \dots, a_k$. $\blacksquare$

Oops (deleted this for a second originally since I wanted to double check that my claim didn't generalize to any known open conjectures) Claim: For any $C \ge 0$ and any irreducible real integer polynomial $f$ of degree at least $2$, $p(f(n)) \ge 2n + C$ holds infinitely many times. Proof. Fix an $n$. Let $\deg f = d$. We double count the following: \[ \sum_{i=1}^n \ln(f(i)) = d \sum_{i=1}^n \ln(i) + O(n) = dn \ln n + O(n). \]On the other hand, we can consider how much of the above sum each small prime should cover assuming for the sake of contradiction: \begin{align*} \sum_{p} \sum_{1 \le i \le n, p \mid f(i)} \ln(p) &= \sum_{p \le C\sqrt[d]{f(n)}} \sum_{1 \le i \le n, p \mid f(i)} \ln(p) \\ &\le \sum_{p \le C\sqrt[d]{f(n)}} t(p) \cdot \sum_{i=0}^{d} \left\lceil \frac{n}{p^i} \right\rceil \ln(p) + O(1) \\ &\le \sum_{p \le C\sqrt[d]{f(n)}} t(p) \cdot \frac{n}{p-1} \ln(p) + O(n) \\ \end{align*}where $t(p)$ is the number of roots of $f \pmod{p}$. By Chebotarev's density theorem we obtain the average value of $t(p)$ taken over primes less than $n$ approaches $1$. This means that by splitting the sum into intervals $[2^k, 2^{k+1})$ that the sum is at most \begin{align*} (1 + o(1)) \sum_{p \le C\sqrt[d]{f(n)}} \frac{n}{p} \ln(p) + O(n) &= (1 + o(1)) \sum_{p \le C\sqrt[d]{f(n)}} \frac{n}{p} \ln(p) + O(n) \\ &= (1 + o(1)) n \ln(n) + O(n). \end{align*}using the fact that $\sum_{p \le x} \frac{\ln(p)}{p} = \ln(x) + O(1)$. Since $d > 1$, for large $n$ we get $d > (1 + o(1))$ and thus a contradiction. $\blacksquare$ As such, if our original polynomial $f(x^2)$ doesn't factorize into linear parts, the result can't hold. These linear terms must be of the form $ax + b$ with $a \le 2$ for the result to hold, and if $ax + b \mid f(x^2)$ then $-ax + b \mid f(x^2)$ does as well, so $a \ne 1$ else $f(b^2) = 0$ and thus $a = 2$. This means $f$ must factorize as \[ C(4x^2 - a_1^2)(4x^2 - a_2^2) \dots (4x^2 - a_t^2) \]for some $t$, odd $a_i$, and some $C$, which can be seen to work.