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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Nov 5 '13 at 5:39
  • 1
    $\begingroup$ If $N$ is a perfect square, doesn't your formula give $r=0$? $\endgroup$ – user25199 Nov 5 '13 at 8:41
  • $\begingroup$ 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? $\endgroup$ – Adam Hughes Nov 6 '13 at 6:55
  • 1
    $\begingroup$ @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$. $\endgroup$ – user25199 Nov 6 '13 at 8:01
  • $\begingroup$ 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. $\endgroup$ – 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 ...


This Not an answer but an observation about the question.
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.


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.