Prime Polynomial Pickle

Suppose $f(x)$ is of degree $n \leq p-1$ and is equal to $\displaystyle \sum_{i=0}^n a_ix^i$ . Then $f(2x) - f(x) = \displaystyle \sum_{i=0}^n (2^i - 1)a_ix^i$ . Consider this polynomial mod $p$ . By Lagrange's theorem (in number theory), since this polynomial has degree at most $n \leq p-1$ , then this polynomial has at most $p-1$ roots mod $p$ if the polynomial is not $0$ mod $p$ . But we know that this polynomial is equal to $0$ for all integers $x$ , so this polynomial has $p$ roots mod $p$ . Therefore, this polynomial is equal to $0$ mod $p$ , i.e. all its coefficients are $0$ mod $p$ . So we have $p | (2^i - 1)a_i$ , i.e. $p | 2^i-1$ or $p | a_i$ for all $0 \leq i \leq n$ .

We shall ignore the case $p=2$ for the moment. Let $d$ be the order of $2$ mod $p$ , so $d | p-1$ by Fermat's little theorem ( $p | 2^{p-1}-1$ ) and Lagrange's theorem (in group theory). Also, we have $2^m \equiv 1 \pmod{p}$ iff $d | m$ , so $p | 2^i-1$ iff $i$ is a multiple of $d$ . So, when $i$ is a multiple of $d$ (including $i=0$ ), we can have any of the $p$ possibilities for $a_i$ , but when $i$ is not a multiple of $d$ , then $p | a_i \Rightarrow a_i = p$ . So we have altogether $p^{\lfloor\frac{n}{d}\rfloor + 1}$ ways. The degree $n$ of the polynomial $f(x)$ may vary, so the total number of polynomials that we are looking for is $\displaystyle \sum_{n=0}^{p-1} p^{\lfloor\frac{n}{d}\rfloor + 1}$ . Letting $p - 1 = kd$ for some positive integer $k$ , we can see that this expression simplifies to $p^{k+1} + d \cdot \displaystyle \sum_{j=1}^k p^j = p^{k+1} + \frac{dp(p^k-1)}{p-1}$ . We want this to be strictly greater than $p \cdot 2^{p-2}$ , so dividing by $p$ , we get $p^k + \frac{d(p^k-1)}{p-1} > 2^{p-2}$ .

If $p+1$ is not a power of $2$ , then $p+1 \neq 2^d$ . But $2^d \equiv 1 \pmod{p}$ , so $2^d > 2p$ . Then $2^{p-1}=(2^d)^k > (2p)^k=2^kp^k \Rightarrow 2^{p-2} > 2^{k-1}p^k$ . But $2^{p-2} < p^k + \frac{d(p^k-1)}{p-1} \leq p^k +(p^k-1) < 2p^k$ , so $2p^k>2^{k-1}p^k \Rightarrow k=1$ . When $k = 1$ , then $d = p-1$ so $p^k + \frac{d(p^k-1)}{p-1} > 2^{p-2}$ becomes $2p - 1 > 2^{p-2}$ , i.e. $8p>2^p+4$ . We can easily prove by induction that $p > 6$ will not work since $8 \times 6 < 2^6 + 4$ . Therefore, $p$ is at most $5$ . We have assumed that $p \neq 2$ , and since $3+1$ is a power of $2$ , the only solution for $p$ in this case is $p = 5$ . When $p = 5$ , we have $d = 4$ and $k = 1$ , so it clearly satisfies the inequality.

If $p+1$ is a power of $2$ (i.e. $p$ is a Mersenne prime), then $2^q = p+1$ for some prime $q$ (putting $p = 2^q -1$ lets us see immediately that $q$ is prime when $p$ is prime). But $2^q \equiv 1 \pmod{p}$ , so $d | q$ . But $q$ is prime and $d \neq 1$ for all primes $p > 2$ , so $d = q$ and we have $2^d = p+1$ . So we want $p^k + \frac{d(p^k-1)}{p-1} > 2^{p-2}$ . Let's consider the stricter inequality $p^k > 2^{p-2}$ and we shall prove that this is true for all Mersenne primes. Observe that $\begin{aligned} p^k > 2^{p-2} &\Leftrightarrow (2^d-1)^k>2^{p-2} \\ &\Leftrightarrow 2(2^d-1)^k>2^{p-1}=(2^d)^k \\ &\Leftrightarrow \frac{(2^d-1)^k}{(2^d)^k} > \frac{1}{2} \\ &\Leftrightarrow (1-\frac{1}{2^d})^k > \frac{1}{2}. \\ \end{aligned}$ By Bernoulli's inequality, since $k \geq 1$ and $-\frac{1}{2^d} > -1$ , we have $(1-\frac{1}{2^d})^k \geq 1+k(-\frac{1}{2^d})$ . So it suffices to show that $1+k(-\frac{1}{2^d}) > \frac{1}{2}$ . So we have $\begin{aligned} 1+k(-\frac{1}{2^d}) > \frac{1}{2} &\Leftrightarrow \frac{k}{2^d} < \frac{1}{2} \\ &\Leftrightarrow \frac{p-1}{d \cdot 2^d} < \frac{1}{2} \\ &\Leftrightarrow \frac{2^d - 2}{d \cdot 2^d} < \frac{1}{2} \\ &\Leftrightarrow 2^d - 2 < d \cdot 2^{d-1}. \\ \end{aligned}$ The final statement is obviously true because $d \geq 2$ as established earlier. Therefore, we can conclude that all Mersenne primes satisfy the property in the question.

Finally, we would need to look at $p = 2$ . If $f(x) = 1$ and $f(x) = 2$ , then $f(2x) - f(x) = 0$ for all $x$ and it is divisible by $2$ . Moreover, when $f(x) = 2x + 1$ or $f(x) = 2x + 2$ , we must have $f(2x) - f(x) = 2x$ which is divisible by $2$ for all $x$ . So there are at least $4$ such polynomials as described in the question, and since $4 > 2 \cdot 2^{2-2}$ , we count $p=2$ as well.

Combining our results, we know that the primes $p$ that satisfy the conditions in the question must be $2, 5$ or a Mersenne prime. For the Mersenne primes, we want $p < 1000$ , so we just need to look at $2^s - 1$ for all primes $s$ not more than $9$ . This corresponds to $2^2 - 1 = 3$ , $2^3 - 1 = 7$ , $2^5 - 1 = 31$ and $2^7 - 1 = 127$ which are all primes, so the answer we are looking for is $2 + 3 + 5 + 7 + 31 + 127 = 175$ .

We can rewrite the problem by considering polynomials with coefficients modulo $p$ , and the condition that for all residues $x$ modulo $p$ , $f(2x)=f(x)$ in the field ${\mathbb Z/p{\mathbb Z}}.$ However, every such polynomial of degree $k\leq p-1$ should be counted $(p-k)$ times, one for each degree from $k$ to $p-1.$ If $p=2$ , then this condition is equivalent to $f(0)=f(1)$ . There are two polynomials modulo $p$ satisfying this condition: $0$ and $1$ . They correspond to four polynomials with integer coefficients: $2,$ $2x+1,$ $1,$ $2x+1.$ This is strictly greater than $2\cdot 2^{2-2}=2,$ so $p=2$ works.

Now we assume that $p$ is odd. Multiplication by $2$ modulo $p$ permutes residues modulo $p$ . Suppose $k$ is the smallest positive integer such that $2^k \equiv 1 \pmod p$ . Then the set of all non-zero residues modulo $p$ consists of $\frac{p-1}{k}$ cycles, with the ratio of any two elements of each cycle being a power of $2.$ The property $f(2x)\equiv f(x)\pmod p$ is equivalent to $f$ having the same values modulo $p$ on all elements in each cycle. By the Lagrange Interpolation Formula (Polynomial Interpolation Theorem) in ${\mathbb Z}/p{\mathbb Z}$ , for each assignment of values of $f(x)$ modulo $p$ there is exactly one polynomial modulo $p$ of degree at most $p-1$ . So the number of modular polynomials satisfying the given conditions is $p^{\frac{p-1}{k}+1}$ (the "+1" is for the choice of the value at $0$ ). Therefore, the number of integer polynomials is from $p^{\frac{p-1}{k}+1}$ to $p^{\frac{p-1}{k}+2}.$

Cases $p=3$ and $p=5$ can be checked directly, and both of them work. Here is the detailed argument for $p=5$ . Modular polynomials with given properties are of the form $c+d(x^4-1),$ where $c$ and $d$ are any residues modulo $5.$ If $d=0,$ we get constant polynomials, so each of them gives $5$ integer polynomials. If d\=1,2,3, or $4,$ then for any $c$ we get a degree four modular polynomial, which gives one integer polynomial. Altogether, we get $25+20=45$ integer polynomial, which is strictly greater than $5\cdot 2^{5-2}=40.$

We will assume now that $p\geq 7.$ Suppose $2^k-1=mp.$ We are going to prove that a prime $p$ works if and only if $m=1.$

Lemma 1. If $m=1$ , then the prime $p$ satisfies the condition of the problem.

Proof. We will prove that in this case $p^{\frac{p-1}{k}+1}>p2^{p-2}.$ Dividing by $p$ and taking to the power $k,$ this is equivalent to $p^{p-1}>2^{k(p-2)}.$ Because $m=1,$ $2^{k(p-2)}=(p+1)^{p-2}$ . Taking natural logarithm, our inequality is equivalent to $(p-1)\ln p > (p-2) \ln (p+1)$ . This is equivalent to $\ln p +(p-2)\ln p > (p-2)\ln (p+1),$ which is equivalent to $\ln p > (p-2) \ln(1+\frac{1}{p})$ . For all $x>-1$ , $\ln (1+x) \leq x,$ so $(p-2)\ln (1+\frac{1}{p}) \leq \frac{p-2}{p} < 1 < \ln p$

Lemma 2. If $p>5$ and $m>1,$ then $p^{\frac{p-1}{k}+2}\leq p\cdot 2^{p-2}.$

Proof. Suppose $\frac{p-1}{k}=l.$ First we consider the case $k\leq l.$ Then $\frac{p-1}{k}\geq k$ , so $p-1-\frac{p-1}{k}+k-1\leq p-2.$ So $2^{\frac{k-1}{k}(p-1)+(k-1)}\leq 2^{p-2}.$ Because $m\geq 2,$ $2^k=mp+1>2p,$ thus $2^{k-1}>p.$ So $p^{\frac{p-1}{k}+1} < 2^{p-2},$ as desired.

Now suppose $l\leq k.$ Then $\frac{p-1}{k}\leq \sqrt{p},$ thus it is enough to show that $p^{\sqrt{p}+1}\leq 2^{p-2}.$ Taking logarithms of both sides, we get $\log _2 p (\sqrt{p-1}+1)\leq p-2.$ This is equivalent to $\log_2 p \leq \sqrt{p-1}-1.$ One can check that this is true for primes $p\geq 67.$ So it remains to check the primes $p=11,13,17,19,23,29,37,41,43,53,59,61$ . It is not hard, but tedious, to find $k$ and $l$ in each case by repeated multiplication by $2$ (the job can be simplified greatly sometimes by the Fermat's theorem). We get $l=3$ for $p=43$ and $l\leq 2$ in all other cases. The required inequality is then very easy to check, we skip the details for the sake of brevity.

Therefore, the primes $p$ for which the condition is satisfied, are $p=2,$ $p=3,$ $p=5,$ and the primes $p\geq 7$ of the form $2^k-1$ . For $p<1000,$ we just need to check $k\leq 9$ . So we get the primes $2,3,5,7,31,127.$ Adding them up, we get $175.$