For a prime gap of length at least $n$, a trivial upper bound for its first occurrence is $N=n!$ or $N=lcm(2,\dots,n)$. A bit better is $N=p_1\cdots p_n$ where $p_k$ is the $k$th prime, as then $N+2,\dots,N+(p_{n+1}-1)$ are all composite. In “real life” however, the first big gaps will occur much earlier, e.g. between $113$ and $127$, which is even below $ 2\cdot3\cdot5\cdot7=210$ (see http://oeis.org/A002386).
I won’t ask for better bounds for early occurrences. I rather have a corresponding question concerning irreducible polynomials. It started with a question on Math SE here (but note that I have 'reversed' the polynomials here for convenience of notation.)

For given $k$, we'll deal with integer polynomials $P=P(x)=a_nx^n+\cdots+a_1x$ such that $P,P+1,…,P+k-1$ are all reducible. Call such a polynomial a $k$-gap.
A trivial construction, corresponding somewhat to the initial one for prime gaps above, is $P=x(x+1)\cdots(x+k-1)+x$, so $P+j$ has a factor $(x+j)$. The downside of this construction is that the coefficients, i.e. the Stirling numbers, are growing much faster than $k$.

It seems however that $k$-gaps with very small (absolute) coefficients do exist, at least for $k=3,4,5,6$. For example, there is
a $4$-gap $P=x^4+x^3-3x^2-2x$,
a $5$-gap $P=x^5+x^4-4x^3-3x^2+4x$,
a $6$-gap $P=x^{10}-x^9-2x^8-2x^7-3x^6-x^5-x^4+x^3+2x^2+x$.
Note that I make no restriction on the degree of such a polynomial. I haven't yet found a $6$-gap with smaller degree.

For $k=3,4,5$ we even have $k$-gaps with all coefficients in $\lbrace-1,0,1\rbrace$. Examples:

a $3$-gap $P= x^5+x$
a $4$-gap $P= x^7-x^6-x^4+x^2+x$
a $5$-gap $P= -x^{12}+x^{11}-x^8-x^6+x^2+x$
(no such $6$-gap found yet.)

To ask a hopefully more feasible question than that:

Is there a construction that yields for any given $k$ a $k$-gap with relatively small coefficients, say $|a_j|< k$ for all $j$?


At the cost of having the degree be very large you can always choose a $k$-gap with coefficients in $\lbrace 0,1\rbrace$. Pick a large $n$ so that $n\equiv -j\pmod{p_j}$, for all $1\le j\le k$. Where $p_j$ is the $j$th prime. Let $P(x)=x^{a_1}+\cdots+x^{a_n}$ and choose the exponents $a_i$ by the chinese remainder theorem, so that they are all distinct and so that

  • Exactly $\frac{n+1}{2}$ of the $a_i$'s are odd, so that $P(x)+1$ is divisible by $x+1$.
  • Exactly $\frac{n+2}{3}$ of $a_i$'s are $1\pmod{3}$, and similarly for $2\pmod{3}$, so that $P(x)+2$ is divisible by $x^2+x+1$.
  • Similarly for other $j\le k$, have the exponents be equally distributed $\pmod {p_j}$ with $\frac{n+j}{p_j}$ in each non-zero residue, so that $P(x)+j$ is divisible by $x^{p_j-1}+\cdots +1$.
| cite | improve this answer | |
  • $\begingroup$ That's an ingenious construction! Thanks! $\endgroup$ – Wolfgang Nov 20 '13 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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