Set of quadratic expressions $nx^2+m$ whose union is all integers?

Question

Is there a set of quadratic equations whose union is equal to the counting integers (1,2,3,4...) but all pairs of intersections are empty. An example of linear equations which satisfy this is simply:

$$ \begin{align*} S_1 &= \{1,3,5,7,\ldots,2n+1\}\\ S_2 &= \{2,4,6,8,\ldots,2n+0\}\\[0.2in] S_1 \cup S_2 &= \{1,2,3,4,5,6,7,8,9,\ldots\}\\ S_1 \cap S_2 &= \varnothing \end{align*}$$

It is easy to construct these for linear functions, but is it impossible to do the same for functions of the form $f_{mn}(x)=nx^2+m$?

Answer 1

Proposition: Let $c\ne 0$ be any integer. Then there exists a multiplier $B\ge 1$ such that $(Bn)^2+c$ is never a square (inclusive of $0$) for any $n\ge 1$.

Proof: There are only finitely many ways to write $c$ as the product of two integers. Choose $B$ so that $2B$ exceeds the maximum difference between any complementary factors of $c$. Then $(m-Bn)(m+Bn) = c$ has no integer solutions with $n\ge 1$.

Lemma: Let $A$ be any finite set of integers, and $c \ne A$. There exists a $B\ge 1$ such that the set $\{(Bn)^2+c: n > 0\}$ is disjoint from the union of quadratic progressions $\{ n^2 + a : n \ge 0, a \in A \}$.

Proof: Apply the proposition to each value $c-a$, and take $B$ to be the LCM of all the (finitely many) multipliers so obtained.

Theorem: There exists an infinite sequence $(B_k, c_k) : k \ge 0$ with $B_k > 0$ such that the quadratic progressions $\{ B_k n^2 + c_k : n \ge 0 \}$ form a partition of $\mathbb N$.

Proof: Start with $(B_0,c_0) = (1,1)$. We proceed inductively: suppose that $(B_k, c_k)$ have been chosen for all $k<m$. By Steven Stadnicki's comment above, there exists a least element of $\mathbb N$ not yet covered: call it $c$. Necessarily, $c \ne c_k$ for any $k<m$. Now choose $c_m = c$ and $B_m$ according to the lemma (using $A = \{c_0,\ldots,c_{m-1}\}$). By construction $\{ B_m n^2 + c_m : n > 0 \}$ is disjoint from all previous progressions, and also $\{ B_m n^2 + c_m : n = 0 \}$ is disjoint by choice of $c$. Thus we may construct an infinite sequence $(B_k,c_k)$ in this manner. Finally, this is certain to cover all of $\mathbb N$ since we chose $c$ minimally, so that the first $m$ progressions necessarily cover $\{1,\ldots,m\}$.

Answer 2

Here's the outline of a proof that there exists a countable set of quadratics that partitions all the integers. There are a couple of small holes, but I think the idea should work.

The core idea is to build such a partition sequentially, adding a new quadratic $f_{n}(x)=a_nx^2+b_n$ while making sure that there's no possible way it can share any elements of its range with previous quadratics.

Specifically, start with $a_1=3, b_1=1$ and the quadratic $f_1(x)=3x^2+1$; then the range of $f_1$ is $S_1=\{1, 13, 28, \ldots\}$ and its complement is $C_1=\{2, 3, 4, 5, \ldots\}$.

Now, at each step $n$ we'll choose $b_n$ to be the smallest value of $C_{n-1}$; note that this ensures by induction that the smallest member of $C_n$ is $\gt n$ and thus that every number will fall into some $S_i$.

To make sure that we don't intersect any of our already-existing quadratics, we have to make sure that we never have $a_nx^2+b_n=a_iy^2+b_i$ for any $i\lt n$ and any integers $x,y$. But this is the same as the equation $a_nx^2=(b_i-b_n)+a_iy^2$. Note that this implies that $a_nx^2\equiv (b_i-b_n)\pmod {a_i}$. But now, if $\gcd(a_n, a_i)=1$ (and we can ensure this; in fact, we can ensure that $a_n$ is prime for all $n$) then this is the same as $x^2\equiv a_n^{-1}(b_i-b_n)\pmod{a_i}$; in other words, $a_n^{-1}(b_i-b_n)$ is a quadratic residue. But there are quadratic non-residues modulo every prime — so if we choose $a_n$ such that $a_n^{-1}(b_i-b_n)$ is a quadratic non-residue mod $a_i$, then we can be assured that the quadratics $a_nx^2+b_n$ and $a_ix^2+b_i$ will never cover the same integer. (This is where the hole is: we may have $b_n\equiv b_i\pmod {a_i}$, so that $(b_i-b_n)\equiv 0$ and there's no way of multiplying to get a quadratic non-residue. But I think a slightly smarter selection of the $a_i$ should be able to cover this gap.)

Now, this only defines $a_n$ (strictly speaking, $a_n^{-1}$) modulo $a_i$; but by the Chinese Remainder theorem (along with the fact that we've chosen all $a_i$ to be prime), we can choose $a_n$ to satisfy the congruences modulo all $a_i$ for $i\lt n$ simultaneously — and by Dirichlet's theorem on primes in arithmetic progressions, we can choose $a_n$ to not just satisfy the congruences but also to be prime itself. This lets us continue to the next $n$ in our iteration, and (in the limit) to cover all the natural numbers disjointly.