13
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Lucia
    Aug 5, 2015 at 14:33
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 5, 2015 at 14:55

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, I have seen this paper too. But does it help for the question? $\endgroup$ Aug 5, 2015 at 13:59
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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}$. $\endgroup$ Aug 5, 2015 at 21:39
  • $\begingroup$ Even three Sophie German primes near $P$ would make this $LCM$ much larger than $\Sigma$. $\endgroup$ Aug 5, 2015 at 22:31
  • $\begingroup$ @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. $\endgroup$
    – alpoge
    Aug 6, 2015 at 2:12
  • $\begingroup$ Yes, I mean special arrays of primes, of course. $\endgroup$ Aug 6, 2015 at 4:03
4
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thanks a lot. I think you do not need Mignotte's result for this, since the least non-zero coefficient survives in a product. $\endgroup$ Aug 6, 2015 at 9:58
  • $\begingroup$ 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}$. $\endgroup$ Aug 6, 2015 at 10:47
  • $\begingroup$ Good point. I'll use this answer to edit in another computation; this one is a dead end. $\endgroup$ Aug 6, 2015 at 11:27
  • $\begingroup$ @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$. $\endgroup$ Aug 6, 2015 at 11:42
  • $\begingroup$ 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. $\endgroup$ Aug 6, 2015 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.