# The least number of quadratic polynomials needed to cover $[1,N]$

Let $r = r(N)$ denote the least number of quadratic polynomials $f_i \in \mathbb{Z}[x]$, $1 \leq i \leq r$, each with non-negative coefficients, such that for every integer $n \in [1,N]$, there exists $1 \leq i \leq r$ such that $n = f_i(m)$ for some integer $m \in \mathbb{N}$. Clearly, $r(N) \rightarrow \infty$, since for each quadratic polynomial $f$ with non-negative coefficient the set of integral values in $[1,N]$ that can be represented by $f$ is $O(N^{1/2})$, so for any number $c$, the set of values that can be covered by $f_1, \cdots, f_c$ is also $O(N^{1/2})$. This also shows that $r(N) \gg N^{1/2}$.

In fact, $r(N) = O(N^{1/2})$ as well, since the polynomials $f_1(x) = x^2, f_2(x) = x^2 + 1, \cdots, f_r(x) = x^2 + r$ with $r = N - \lfloor N^{1/2} \rfloor^2$ will cover cover $[1,N]$.

My question is what is the smallest positive value $c$ such that $r(N) \geq cN^{1/2}$ for all $N$ sufficiently large?

Thanks for any input.

• Maybe you could compute $r(N)$ for a few small values of $N$, and see whether the Online Encyclopedia of Integer Sequences has anything to say about the function. – Gerry Myerson Nov 5 '13 at 5:39
• If $N$ is a perfect square, doesn't your formula give $r=0$? – user25199 Nov 5 '13 at 8:41
• Carl, we're looking for a set of polynomials which hits EVERY integer between 1 and N, how can we hit anything without any polynomials? – Adam Hughes Nov 6 '13 at 6:55
• @Adam, exactly my point. Maybe I wasn't clear: There appears to be a problem with the equation $r=N-\lfloor N^{1/2}\rfloor^2$. – user25199 Nov 6 '13 at 8:01
• Ah, apologies, I thought you were suggesting that $r(N^2)=0$ based on the definition, I have no idea how I misread that so badly. – Adam Hughes Nov 11 '13 at 23:21

A special case of this problem has been studied in the literature (and I think this work will also cover the general version). Given $N$, what is the smallest set $B$ such that every $n\le N$ can be written as $a^2+b$ with $b\in B$. This was first raised by Erdos. Taking $B$ to be the numbers up to $2\sqrt{N}$ we see an upper bound of $2\sqrt{N}$. This remains the best known upper bound. In the other direction, it is clear that $B$ must at least have $\sqrt{N}$ elements, but it is possible to do better. The best in this direction is due to Javier Cilleruelo (see http://www.sciencedirect.com/science/article/pii/S0022314X83710498 ), who obtained the lower bound $(4/\pi+o(1)) \sqrt{N}$. Cilleruelo considers more generally the complements of $k$-th powers. The techniques there would also apply to this question, and I think give the same bounds. It's not clear what the right constant is; if all the elements in $B$ are $o(N)$ then $2\sqrt{N}$ elements are required, so maybe the upper bound is close to the truth.
That's not an answer too, just a result of a quick and naive computation: For $k\ge1$ let $n_k$ be the largest integer such that $r(n_k)=k$. Of course then $r(m)=k$ for all $n_{k-1}+1\le m\le n_k$. We have $n_1, n_2, \ldots = 1, 2, 6, 9, 13, 19, 23, 32, 32, 37, 45, 54, 61, 72, 82, 91, 101, 114, 128, 137\ldots$. And no, OEIS does not know this sequence ...
Counting the number of such polynomials which is $O(N^{1/2})$ gives a proof of Sierpinski's prime sequence theorem http://mathworld.wolfram.com/SierpinskisPrimeSequenceTheorem.html
and if you extend your question for polynomials of higher degree you can also extend Sierpinski's theorem for $n>2$ :
for any $M>0$ there exists a $t'$ such that $x^n+t',n\geq 2$ contains at least $M$ prime numbers.