Let $a$, $b$ be two coprime natural numbers. Let $A \subseteq \{0,1,\ldots, a-1\}$ and $B \subseteq \{0,1,\ldots,b-1\}$ be two nonempty sets, which we think of as sets of residues mod $a$ and $b$ respectively.
I would like to know if anyone has ever seen (or knows a proof for) the following result: that any interval of $(a – |A| + 1)(b – |B| + 1)$ consecutive integers contains a number $x$ such that $x$ mod $a$ is in $A$, while $x$ mod $b$ is in $B$.
Actually, I do have a proof of this result, but it's complicated, and I have no proof for the $k$-variate case. To be precise the $k$-variate case is the following: we have $k$ natural numbers $a_1, \ldots, a_k$ that are pairwise coprime, and nonempty sets of residues $A_1, \ldots, A_k$ where $A_i$ is a set of residues mod $a_i$. The question is to show that any interval of at least
$$
(a_1 – |A_1| + 1)(a_2 – |A_2| + 1)\cdots (a_k – |A_k| + 1)
$$
consecutive integers contains an integer $x$ such that $x$ mod $a_i$ is in $A_i$ for $i = 1, \ldots, k$. The case $k = 1$ is obvious, for the case $k = 2$ I have a proof, and for $k \geq 3$ I only have a partial result, namely that the statement holds as long as the interval length mentioned above is strictly greater than
$$
\sum_i \prod_{j\ne i} a_j.
$$
Would be grateful if people could tell me what they know about this problem, or their insights. Thanks!
Best Answer
[Edited again mostly to spell out why the $m_j \bmod a$ are distinct.]
Yes, the desired result is true for all $k$. The following proof is elementary but possibly more algebraic than expected (apparently some kind of variant of the "polynomial method" in combinatorics, though with no need for anything as advanced as the "combinatorial Nullstellensatz"). This would make for a good Putnam B-6 problem; indeed I wouldn't be surprised if this question has already been used for such a competition.
Let $a_1,\ldots,a_k$ be pairwise coprime positive integers, and set $a = \prod_{i=1}^k a_i$. For each $i$ let $A_i$ be a nonempty subset of ${\bf Z} / a_i {\bf Z}$, and let $Z_i$ be the complement of $A_i$ in ${\bf Z} / a_i {\bf Z}$. Let $A \subseteq {\bf Z} / a {\bf Z}$ consist of the residues $n \bmod a$ such that $n \bmod a_i \in A_i$ for each $i$. Let $Z$ be the complement of $A$ in ${\bf Z} / a {\bf Z}$, consisting of the residues $n \bmod a$ such that $n \bmod a_i \in Z_i$ for some $i$.
We claim:
Proposition. This set $Z$ cannot contain a run of $$ N := \prod_{i=1}^k (a_i - |A_i| + 1) = \prod_{i=1}^k (|Z_i| + 1) $$ consecutive residues $\bmod a$.
Proof: Let $w \in {\bf C}$ be a primitive root of unity of order $a$, so that $w_i := w^{a/a_i}$ is a primitive root of unity of order $a_i$ for each $i$. Set $W_i := \lbrace w_i^n | n \in Z \rbrace$, a set of size $|Z_i|$, and $P_i(X) := \prod_{x \in W_i} (X-x)$, which is thus a polynomial of degree $|Z_i|$. Then for any $n \bmod a$ we have $n \in Z$ iff $$ 0 = \prod_{i=1}^k P_i(w_i^n) = P(w^n), $$ where $P$ is the polynomial defined by $$ P(X) := \prod_{i=1}^k P_i(X^{a/a_i}). $$ Because each $P_i(X^{a/a_i})$ is the sum of at most $|Z_i|+1$ monomials, their product $P$ is the sum of at most $\prod_{i=1}^k (|Z_i|+1) = N$ monomials, say $$ P(X) = \sum_{j=1}^N c_j X^{m_j}. $$ The $N$ exponents $m_j$ are the integers of the form $a \sum_{i=1}^k b_i/a_i$ with $0 \leq b_i \leq |Z_i|$. Since each $|Z_i| < a_i$ (this is where we use the hypothesis $A_i \neq \emptyset$) and the $a_i$ are pairwise coprime, it follows that these $m_j$ have pairwise distinct residues $\bmod a$.
We claim, then, that for each $n \bmod a$ at least one of $P(w^n), P(w^{n+1}), \ldots, P(w^{n+N-1})$ is nonzero. Suppose not. Then $(c_1,\ldots,c_N)$ would be a nonzero solution of the $N \times N$ linear system $$ \sum_{j=1}^N w^{m_j (n+k)} c_j = 0 \phantom{\infty} (k=0,1,\ldots,N-1). $$ Hence $(w^{-nm_1^{\phantom.}} c_1^{\phantom.}, \ldots, w^{-nm_N^{\phantom.}} c_N^{\phantom.})$ would be a nonzero vector in the kernel of the Vandermonde matrix with entries $(w^{m_j})^k$. But then some two $w^{m_j}$ would coincide, contradicting our observation that the residues $m_j \bmod a$ are distinct. This completes the proof.
P.S. Note that we do not even need the formula for the determinant of a Vandermonde matrix, only the fact that it is invertible, which can be obtained by interpreting the kernel of the transposed matrix as the space of polynomials of degree less than $N$ that vanish at the $N$ distinct points $w^{m_j}$.