show/hide this revision's text 4 added 1988 characters in body

Note: As I finished writing 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 am about to saywrote, but I'll go ahead with it.

The case $k=2:$ I think K=2$ wWe will see that for the problem when $k=2$ the sharp result provided can be reduced to this: find subsets $ab A \gt a|B|+b|A|+\max(a,b)$ (or something like 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 that any interval the set of length residues $ (a-|A|)(b-|B|)+1$ suffices r \bmod ab$ with $r \bmod{a} \in A$ and $r \bmod{b} \in B.$

It seems plausible, and turns out to be sure the case, that there the minimum is an integer frequently achieved by taking $m$ in 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 \mod bmod a \in A$ and $m \mod 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 clearer belowprecise, this is the only examples example which require this length have the form $A=\{0,b,2b,\cdots (s_1-1)b\} \mod a$ and requires an interval that long.

In any case, we always need to take at least $B=\{0,a,2a, \cdots,(s_2-1)a\} \mod b$ where a+b-s_1-s_2+1$ consecutive integers to be sure to have an $s_1,s_2$ are the desired sizes of m$ as above. This is because we can choose the sets 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 we have a set of B$ so as to also exclude $|A||B|=s_1s_2$ integers (or residues ab-s_1 \cdots ab-s_1-s_2.$ If $\mod ab$) a+b-s_1-s_2 \le a$ then this is best possible and we want the largest gap (plus $1$) of integers there are $\mod ab$ which misses \binom{s_1+s_2}{s_1}$ ways to do thisset. The claim is that the extreme example is (for For slightly larger $s_1,s_2$ not too large with respect a+b-s_1-s_2$ it may be possible to $a,b$) usually the integers $ab(\frac{i_1}{a}+\frac{i_2}{b})$ for $0 \le i_k \lt s_k$ eliminate two things with some of our choices for $k=1,2.$ I briefly mention A$. However the other extre later onoptimum 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 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,2\} \{0,17\}=\{0,2\} \mod 5$ and $\{0,5,10\} \mod 17$ (chosen using $5 \mod 17$ and $17 \mod 5$) 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$

An example 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$ (which since it can be done 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 1 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 istead instead I raised $|B|$ to $15$ 14$ then I would have four different ways to use a one row and 3 columns to eliminat eliminate $80,81,82,83$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.$

  • $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$-A_i+c.$

    • 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\cdot0+4,5 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 fact 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 row column $0$ along with $s_2$ multiples of $a_1$ in column row $0$ along with and all their $s_1s_2$ pairwise sumsand . If $(s_1-1)b+(s_2-1)a$ is reasonably less than $ab$ then we should just take the gap from rows and columns with the largest of these to $0$. At best that largest sum is $(s_1-1)a_2+(s_2-1)a_1$. Of course there are situations such smallest values on the left and top. In cases as the above with $a_1=5,a_2=6,s_1=s_2=4$ when (s_1-1)a_2+(s_2-1)a_1$ greater than, or only slightly less than $(s_1-1)a_2+(s_2-1)a_1 \gt a_1a_2.$ Then ab-1$ it is better to rule out using rows and columns so as to exclude the largest gap will, of course, not be negative in sizeentries. But I think that it will be no larger than $\max(a_1,a_2)$

    Experimental results: With the consideration of equivalence classes from the first remark one 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.$ Thid 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.$

    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.
    show/hide this revision's text 3 added 785 characters in body

    The case $k=2:$ I think that for $k=2$ the sharp result is provided $ab \gt a|B|+b|A|+\max(a,b)$ (with a few exceptionsor something like that) is that an any interval of length $(a-|A|)(b-|B|)+1$ suffices to be sure that there is an integer $m$ in that interval with $m \mod a \in A$ and $m \mod b \in B$. In a sense made clearer below, in most cases the only examples which require this length have the form $A=\{0,b,2b,\cdots (s_1-1)b\} \mod a$ and $B=\{0,a,2a, \cdots,(s_2-1)a\} \mod b$ where $s_1,s_2$ are the desired sizes of the sets $A$ and $B.$ So we have a set of $|A||B|=s_1s_2$ integers (or residues $\mod ab$) and we want the largest gap (plus $1$) of integers $\mod ab$ which misses this set. The claim is that the extreme example is (for $s_1,s_2$ not too large with respect to $a,b$) usually the integers $ab(\frac{i_1}{a}+\frac{i_2}{b})$ for $0 \le i_k \lt s_k$ for $k=1,2.$ The exceptions seem to be cases such as $a-2 \le|A|.$ I briefly mention the other extre later on.

    An example 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$ (which can be done as easily 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 1 so best is to eliminate $79,84$ using the last row and $80,81,82,83$ using the four next to final columns. If istead I raised $|B|$ to $15$ then I would have four different ways to use a row and 3 columns to eliminat $80,81,82,83$

    Experimental results: With the consideration of equivalence classes from remark one 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.$ Thid seem to resemble the "other extreme" example above. I did not go past $\max{(s_1,s_2)}=5.$
    show/hide this revision's text 2 added 573 characters in body

    Note: As I finished writing this I realize realized from your condition involving $\sum_i \prod_{j\ne i} a_j$ that you may have anticipated most of what i I am about to say, but I'll go ahead with it.

    The case $k=2:$ I think that for $k=2$ the sharp result is (with a few exceptions) that an interval of length $(a-|A|)(b-|B|)+1$ suffices to be sure that there is an integer $m$ in that interval with $m \mod a \in A$ and $m \mod b \in B$. In a sense made clearer below, in most cases the only examples which require this length have the form $A=\{0,b,2b,\cdots (s_1-1)b\} \mod a$ and $B=\{0,a,2a, \cdots,(s_2-1)a\} \mod b.$ b$ where $s_1,s_2$ are the desired sizes of the sets $A$ and $B.$ So we have a set of $|A||B|=s_1s_2$ integers (or residues $\mod ab$) and we want the largest gap (plus $1$) of integers $\mod ab$ which misses this set. The claim is that the extreme example is usually the integers $ab(\frac{i_1}{a}+\frac{i_2}{b})$ for $0 \le i_k \lt s_k$ for $k=1,2.$ The exceptions seem to be cases such as $|A|=a-1$ For a-2 \le|A|.$

    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 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$ that is always true and it is usually true a_i)-t.$ I think that this gives the longest possible gap . The exceptions are when $t$ provided that it is quite large relative to greater than $\prod \prod_2^k a_i.$

    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.$ To move one step at a time through the integers $\mod 85$, keeping track of the residues mod $5$ and $17$ 17$, is to move at a slope of $-1$ wrapping around cyclically.

    If I choose the residues $\{0,2\} \mod 5$ and $\{0,5,10\} \mod 17$ (chosen using $5 \mod 17$ and $17 \mod 5$) 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$

    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 . 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$ say that $A_i$ is equivalent to any of the sets $A_i+c$ and $-A_i+c.$

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

    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\cdot0+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.$

    In fact 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 row $0$ along with $s_2$ multiples of $a_1$ in column $0$ along with all their sums and then we take the gap from the largest of these to $0$. At best that largest sum is $(s_1-1)a_2+(s_2-1)a_1$. Of course there are situations such as $a_1=5,a_2=6,s_1=_2=4$ a_1=5,a_2=6,s_1=s_2=4$ when $(s_1-1)a_2+(s_2-1)a_1 \gt a_1a_2.$ Then the largest gap will, of course, not be negative in size. But I think that it will be smaller no larger than $\max(a_1,a_2)$

    Experimental results: With the consideration of equivalence classes from remark one 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.$ I did not go past $\max{(s_1,s_2)}=5.$

    Geometry: The picture of a sloped trajectory in a sort of affine 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 a 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

    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}$ \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 miss be bounded away (by an appropriate amount in an appropriate metric) a set with some factored form and given size (or measure.) Although the possible details are not far from clear, perhaps one could consider not necessarily rational slopes and recruit results about Diophantine approximations. Perhaps the higher dimensional cases could be understood through simultaneous approximation.
    show/hide this revision's text 1