long enough interval of integers to solve a simultaneous congruence

Question

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!

Answer 1

[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}$.

Answer 2

Nice question! Maybe Jacobsthal's function might interest you. If the $a_i$s are all distinct primes, and the $A_i$s are the non-zero residue classes modulo the $a_i$s, the best known bounds for Jacobsthal's function, due to Iwaniec and Vaughan, will definitely help your $k$-variate case. The relevant publications are:

H. Iwaniec, On the error term in the linear sieve, Acta Arithmetica 19 (1971), 1--30.

R. C. Vaughan, On the order of magnitude of Jacobsthal's function, Proc. Edinburgh Math. Soc. 20 (1976-7), 329--331.

Answer 3

Note: After starting this I realized from your condition involving $\sum_i \prod_{j\ne i} a_j$ that you may have anticipated most of what I wrote, but I'll go ahead with it.

The case $K=2$ wWe will see that the problem when $k=2$ can be reduced to this: find subsets $A \subset b\mathbb{Z}$ and $B \subset a\mathbb{Z}$ with $|A|=s_1$ , $|B|=s_2$ and $\max A+B \bmod{ab}$ as small as possible. Here $a \lt b$ are coprime integers while $s_1 \lt a$ and $s_2 \lt b$ are positive integers and $X+Y=\{x+y \mid x \in X, y\in Y\}.$ Note that $A+B \mod ab$ is the set of residues $ r \bmod ab$ with $r \bmod{a} \in A$ and $r \bmod{b} \in B.$

It seems plausible, and turns out to be the case, that the minimum is frequently achieved by taking $A=\{0,b,2b,\cdots,(s_1-1)b\}$ and $B=\{0,a,2a,\cdots,(s_2-1)a\}$. If we do not reduce $\bmod ab$ then the $s_1s_2$ integers range from $0$ to $t=(s_1-1)b+(s_2-1)a$ and are separated by $s_1s_2-1$ gaps, some perhaps of size $0$ but none larger than $b-1$. In the event that $t \lt ab,$ the reduction does not change $A+B.$ and we have one final gap $\mod ab$ of length $ab-t.$ Then any interval of $ab-t+1=ab-(|B|-1)a-(|A|-1)b+1$ consecutive integers contains a member $m$ with $ m \bmod a \in A$ and $m \bmod b \in B$ (This was the problem as given.) The bound is sharp for those parameters provided that $ab-t+1 \ge b-1.$ In a sense to be made precise, this is the only example which requires an interval that long.

In any case, we always need to take at least $a+b-s_1-s_2+1$ consecutive integers to be sure to have an $m$ as above. This is because we can choose the elements which will not be in $A$ so as to exclude $ab-1,ab-2,\cdots,ab-s_1$ and then choose elements to not be in $B$ so as to also exclude $ab-s_1 \cdots ab-s_1-s_2.$ If $a+b-s_1-s_2 \le a$ then this is best possible and there are $\binom{s_1+s_2}{s_1}$ ways to do this. For slightly larger $a+b-s_1-s_2$ it may be possible to eliminate two things with some of our choices for $A$. However the optimum solutions in these cases appear to have this nature.

Larger $k:$For the generalization to larger $k$ the situation is about the same (see below if needed for the notation): Suppose $a_1 \lt a_2 \lt \cdots \lt a_k.$ Before reducing $\mod a=\prod a_i $, the integers $a_1a_2\cdots a_k(\sum_1^k\frac{i_j}{a_j})$ with $0 \le i_j \lt s_j$ range from $0$ to $t=a_1a_2\cdots a_k\sum\frac{s_j-1}{a_j}$ and have gaps of length bounded by $\prod_2^k a_i.$ Provided that $t \lt \prod a_i$, The set is unchanged by the reduction and is followed by a gap of length $(\prod a_i)-t.$ I think that this gives the longest possible gap provided that it is greater than $\prod_2^k a_i.$ This amounts to taking sets where $A_i$ consissts of $s_i$ mutiples of $\prod_{j \ne i}a_j$.

Here is visual model I find helpful. The residues $\mod 5 \cdot 17=a_1 \cdot a_2$ are in an array with the $i_1,i_2$ entry congruent to $i_j \mod a_j.$ Note that each entry is the sum of the leftmost thing in its row and top thing in its column (a multiple of $17$ and a multiple of $5$.) To move one step at a time through the integers $\mod 85$, keeping track of the residues mod $5$ and $17$, is to move at a slope of $-1$ wrapping around cyclically.

If I choose the residues $\{0,17\}=\{0,2\} \mod 5$ and $\{0,5,10\} \mod 17$ this distinguishes two rows and three columns. The intersections are the six values indicated in red, giving gaps of lengths $4,4,6,4,4,57$

$\left[ \begin {array}{ccccccccccccccccc} \color{red}{0}&35&70&20&55&\color{red}{5}&40&75&25&60& \color{red}{10}&45&80&30&65&15&50\\\ 51&1&36&71&21&56&6&41&76&26& 61&11&46&81&31&66&16\\\ \color{\red}{17}&52&2&37&72&\color{red}{22}&57&7&42&77& \color{\red}{ 27}&62&12&47&82&32&67\\\ 68&18&53&3&38&73&23&58&8&43& 78&28&63&13&48&83&33\\\ 34&69&19&54&4&39&74&24&59&9& 44&79&29&64&14&49&84\end {array} \right] $

The set of gap lengths is unchanged if the six red integers are moved together horizontally and or vertically and/or reflected vertically and/or reflected horizontally. This is the same as replacing one or both of the sets $\{0,5,10\} \mod 17$ and or $\{0,2\} \mod 5$ by an equivalent one where a set $A_i$ of residues $\mod a_i$ is equivalent to any of the sets $A_i+c$ and $-A_i+c.$ Hence we can arrange to have the longest gap end at $0$

Examples at the other extreme Suppose I still use $a,b=5,17$ but I want to have $|A|=4$ and $|B|=13.$ Then in the array I can eliminate one row and 4 columns. If I want to have the largest gap end at $0$ (since it can as easily be made to end there as anywhere else) then I need to eliminate the last few (as many as possible) of the integers $77,78,79,0,81,82,83,84.$ However a row can only eliminate two of those and a column one so best is to eliminate $79,84$ using the last row and $80,81,82,83$ using the four next to final columns. If instead I raised $|B|$ to $14$ then I would have four different ways to use one row and 3 columns to eliminate $81,82,83,84.$ So it would seem that the best option in situations such as these is use the topmost rows (assuming that rows are longer than columns), see what was eliminated by the excluded rows and then use the columns to remove the largest residues still un-eliminated. So for $|A|=3$ and $|B|=11$ we can take $A=\{0,17,51\}$ eliminating (bottom to top) $74,79,84,73,78,83$ and take $B=\{0, 5, 10, 15, 20, 35, 40, 45, 50, 55, 70\}$ with the six excluded columns just sufficient to eliminate (left to right) $75,76,77,80,81,82.$ Note that in this case, $a1,a2,s1,s2=5,17,3,11$ so $a_1a_2=85$ but $(s_1-1)a_2+(s_2-1)a_1=2\cdot 17+10\cdot 5=84.$

Notation: Suppose that $a=[a_1,a_2,\cdots,a_k]$ is a list of $k$ pairwise coprime integers and $A=[A_1,\cdots,A_k]$ is a list where $A_i$ is a set of $s_i$ residues mod $a_i.$ Where no confusion arises we will also use $a$ to denote $\prod a_i$ and $s$ to denote both the list of sizes $s=[s1,\cdots,s_k]$ as well as the integer $\prod_1^ks_j$. There are $s$ integers $\mod a$ with $x \mod a_i \in A_i$ for all $1 \le i \le k.$ This defines $s$ gaps (some perhaps of length $0$) free of any integers from this set. Let $g(a,A)=g([a_1,\cdots,a_k],[A_1,\cdots,A_k])$ be the greatest length among these gaps and $g(a,s)$ the longest such for this list $a$ among all lists of residues with $|A_i|=s_i.$

A few simple but useful observations

1. $g(a,A)$ is unchanged if we replace one or more sets $A_i$ by an equivalent set $A_i+c$ or $\-A_i+c.$

2. In the case $k=1$ we have $g([a_1],[s_1])=a_1-s_1$ from taking $A_1=\{0,1,2,3,\cdots,s_1-1\}$ and this is the unique solution up to the equivalence above.

3. If we consider instead of consecutive integers (an arithmetic progression with common difference $1$) arithmetic progressions with a common difference $d$ (which is coprime to $\prod a_i$) then there are the same values $g(a,s)$ due to the bijection which replaces each $A_i$ by $dA_i.$

Discussion: Now that we understand the simplest case $g(a_1,s_1)=a_1-s_1$ let's consider $g(a_1,s_1,a_2,1)$ We saw from the second remark that $g(a1,s1)=g(17,3)=14$ with the unique realization (up to the equivalence of the first remark) $A_1=\{0,1,2\}$ giving gaps $0,0,14.$ What if we consider now $g(17,3,5,1)?$ Then from the first remark we see that we may assume $A_2=\{0\}$ so that we will have some three red integers in the first row (row $0$) of the array above. As we move diagonally through the array we can imagine that we are actually staying on the first row and taking jumps of length $5$ Hence from the third remark the extreme case (up to equivalence) is $\{0,5,10\}$ with gaps $5\cdot 0+4,5 \cdot 0+4,5 \cdot 14+4=4,4,74.$ It does not seem that it would be hard to explain this more carefully to account for the general case of adding a new modulus $a_{k+1}$ with $s_{k+1}=1.$

To quickly repeat some comments above: In the case $k=2$ is fairly easy to handle all at once. We can shift so that the longest gap ends at $0$ which means that we select $0$ and $s_1-1$ other entries from row $0$ along with $s_2-1$ other entries from column $0$ so we have a set of $s_1$ multiples of $a_2$ in column $0$ along with $s_2$ multiples of $a_1$ in row $0$ and all $s_1s_2$ pairwise sums. If $(s_1-1)b+(s_2-1)a$ is reasonably less than $ab$ then we should just take the rows and columns with the smallest values on the left and top. In cases as the above with $(s_1-1)a_2+(s_2-1)a_1$ greater than, or only slightly less than $ab-1$ it is better to rule out using rows and columns so as to exclude the largest entries.

Experimental results: With the consideration of equivalence classes from the first remark it is possible to check small cases, For $k=2$ and $s_1=s_2=3$ the unique extreme example is the one I described except for $a_1=4,a_2=5$ when their are two solutions giving a maximal gap of $3$ and $a_1=4,a_2=7$ with a maximal gap of $6.$ For $s_1=s_2=4$ the largest exceptions are $a_1,a_2=5,14$ and $6,7.$ These seem to resemble the "other extreme" example above. I did not see any other behavior but I did not go past $\max{(s_1,s_2)}=5.$

Geometry: The picture of a sloped trajectory in a sort of discrete plane with two parallel classes of lines of lengths $a_1$ and $a_2$ generalizes in an easy way to boxes for $k=3.$ A more formal view might be built on the cyclic group of order $a_1a_2..a_k.$ Among the many subgroups consider the $2^k$ whose order is a multiple of some (or none or all) of the $a_i.$ Then the cosets of these form a system of "subspaces" which fall into parallel classes and are closed under intersection.

Approximation: Finally, I wonder about a continuous analog: Change the model to a unit square (or cube) traversed by a line of slope $\frac{-a_2}{a_1}$ (or in the direction $(1,\frac{-a_2}{a_1},\frac{-a_3}{a_1})$) It will follow a periodic trajectory and we might wonder how long a partial trajectory could be and be bounded away (by an appropriate amount in an appropriate metric) from a set with some factored form and given size (or measure.) Although the possible details are far from clear, perhaps one consider not necessarily rational slopes and recruit results about Diophantine approximations. Perhaps the higher dimensional cases could be understood through simultaneous approximation.