# Polynomials vanishing modulo some integer $n$

It is well-known that a polynomial $q \in \mathbb Z[t]$ vanishes modulo $p$ only if it lies in the ideal $J_p$ generated by $p$ and $t^p-t$. This means that either the degree is large (at least $p$) or the coefficients are large (divisible by $p$).

Is there anything useful like this that one can say if a polynomial vanishes modulo $n$? For example, let $n=p_1 \cdots p_k$, where $p_1<\dots<p_k$ are different primes. (For me, this could be the list of all primes less than some number $x$ for example.) It is clear that if $q(t)$ vanishes modulo $n$, then $$q(t) \in J_{p_1} \cap \cdots \cap J_{p_k} = J_{p_1} \cdots J_{p_k}.$$ Examples are $q(t)=t\prod_{i=1}^k (t^{p_i-1}-1)$ or $q(t)=p_1 \cdots p_l$ or anything in the ideal generated by polynomials divisible for each $1 \leq i \leq k$ by either $p_i$ or $t^{p_i}-t$.

Question: Is it true that again either the degree must necessarily be large or some coefficient (or let's say that sum of absolute values of coefficients) must be large? Here, large could mean for example comparable with $\sum_{i} p_i$ or $n$.

It is easy to see that any polynomial $q(t) \in \mathbb Z[t]$ that vanishes modulo $n$ is such that $q(t)/n$ maps $\mathbb Z$ to $\mathbb Z$, and hence $$q(t) = \sum_{i} n a_i \binom{t}{i},$$ for some $a_i \in \mathbb Z$ - but I do not see how this helps. I also tried to apply Chebotarev density theorem (which together with the error analysis of Lagarias-Odlyzko gives a way to produce small primes modulo which a polynomial has to have a root), but the estimates are too coarse and do not seem to make efficient use of the assumptions on the polynomial.

EDIT: Motivated by a discussion with David Speyer below, let me formulate a more precise question:

Question: Let $f \in \mathbb Z[t]$ be a monic polynomial of degree $d$ that vanishes modulo all primes $\leq P$. Is it true that $d \log \|f\|_{\infty}$ cannot be much smaller than $P^2$?

Here, $\|f\|_{\infty}$ denotes the maximum of the absolute value of the coefficients of $f$.

• A bit unclear to me what you are looking for. Suppose $p$ and $q$ are primes with say $q$ of size about $p^2$. Then $(t^p-t)q$ is a polynomial that is zero mod $n=pq$, and the coefficients are of size at most $q=o(n)$, and the degree is $p = o(p+q)$. Does that qualify as a counterexample? – Lucia Aug 5 '15 at 14:33
• @Lucia: For example, I am interested in the case when $n$ is the product of the first $k$ primes. Are there any results expressing how complicated the polynomial has to be in terms of $k$? I would expect that either the product of a substantial set of primes contributes to the 1-norm (and then it has to be $\exp(Ck)$) or a substantial set of primes contributes to the degree (and then the degree has to be at least $Ck^2/\log(k)$. Something like this. – Andreas Thom Aug 5 '15 at 14:55

For a monic $q(t)$ vanishing mod $n$, the degree is at least the minimal $m=m(n)$ with $n|m!$. This follows from a description of all such polynomials given by Singmaster here : $$q(t)=r(t)S_m(t)+\sum_{k=0}^{m-1}a_k\frac{n}{gcd(k!,n)}S_k(t)$$ where $S_k(t)=(t+1)(t+2)...(t+k)$ and $r(t),a_k$ are arbitrary.

• Yes, I have seen this paper too. But does it help for the question? – Andreas Thom Aug 5 '15 at 13:59

As stated the answer is negative. Denote $N=lcm \{p_i-1|1\leq i \leq k\}$. Then $t^{N+1}-t$ is always divisible by $n$. But it may appear that $\sum (p_i-1)=N+N/2+\dots+N/k$, so it may be much greater than $N$.

But some another reasonable bound on degree/norm may hold.

• Fedor, is $LCM(p-1)_{p \leq P}$ really less then $\sum_{p \leq P} (p-1)$? I computed the ratio $LCM/\Sigma$ for the first $100$ primes, and got $6.45812*10^{54}$. – David E Speyer Aug 5 '15 at 21:39
• Even three Sophie German primes near $P$ would make this $LCM$ much larger than $\Sigma$. – David E Speyer Aug 5 '15 at 22:31
• @DavidSpeyer: He means to choose the $p_i$ carefully (e.g. via a Hardy-Littlewood-type tuples of linear forms conjecture) rather than take all primes below a large number, I think. Idle question: how large is lcm(p-1 for p<x)? Presumably it's superpolynomial in x via Linnik but I was wondering if a tighter estimate is known (e.g. \Omega(1)^{x^{1-\eps}} on Elliott-Halberstam or something). I admit I haven't thought about it carefully, so forgive me if the above is nonsense. – alpoge Aug 6 '15 at 2:12
• Yes, I mean special arrays of primes, of course. – Fedor Petrov Aug 6 '15 at 4:03

I thought I'd write out the bounds we can get from the pigeonhole principle. Let's say that I am working with the primes $\leq P$, with polynomials of degree $D$ and I want the largest coefficient to be at most $K$.

If $(K+1)^{D+1} > \prod_{p \leq P} p^p$, then this is possible by the pigeonhole principle: Just look at all polynomials of degree $D$ with coefficients in $[-K/2, K/2]$. Two of them must agree mod $p$ for all $p \leq P$; subtract them and win. We have $\prod_{p \leq P} p^p = \exp(P^2/2 + O(P^2/\log P))$, so this gives us roughly $K \approx \exp(P^2/(2D))$. If $D<P$, then we get a better bound by just using the pigeonhole for primes $\leq D$, and multiplying by $\prod_{D<p\leq P} p = \exp(P-D + O(P/\log P))$; the resulting bound is $K \approx \exp(D^2/(2D) + P-D) \approx \exp(P-D/2)$.

I'll point out that $\prod_{p \leq P} (t^{p-1} - 1)$ is probably worse than we would get by using pigeonhole with $D = \sum_{p \leq P} p-1 \approx P^2/(2 \log P)$. Pigeonhole gives $K \approx \exp(\log P) \approx P$. Multiplying out those binomials produces $2^{P/\log P}$ terms, of $P^2/(2 \log P)$ different different degrees, so some degree has at least $2^{P/(\log P)}/P^2$ terms contirbuting to it. There is no reason to expect better then square root cancellation, so we probably get about $\sqrt{2^{P/(\log P)}}/P$, much worse than $P$.

Editing note: I've removed some other computations which, after conversation with Andreas below, are clearly a dead end. That means the comments may not make much sense.

• Thanks a lot. I think you do not need Mignotte's result for this, since the least non-zero coefficient survives in a product. – Andreas Thom Aug 6 '15 at 9:58
• Substracting from $(x+1)(x+2)\cdots(x+P)$ a polynomial of the form $nq(t)$ with degree $\leq P-1$, one can bound the coefficients in $[-n/2,n/2]$ and obtain a monic example with 1-norm of size $P e^{P}$. – Andreas Thom Aug 6 '15 at 10:47
• Good point. I'll use this answer to edit in another computation; this one is a dead end. – David E Speyer Aug 6 '15 at 11:27
• @AndreasThom By the way, either I misunderstand you, or it isn't true that the least nonzero coefficient survives. The cyclotomic polynomial $\Phi_{105}$ has a coefficient of $2$, but it divides $t^{105}-1$. – David E Speyer Aug 6 '15 at 11:42
• By "least non-zero coefficient" I mean the non-zero coefficient of smallest degree. It is clear that in any product this will apear as a factor in the "least non-zero coefficient". The "least non-zero coefficient" of $\Phi_{105}$ is equal to $1$, so no problem. – Andreas Thom Aug 6 '15 at 11:48