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](https://math.stackexchange.com/questions/560383/defining-irreducible-polynomials-recursively-how-far-can-we-go/571929) (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$? 
> 
> 
> 



Large gaps between consecutive irreducible polynomials with small heights
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$.


