Return to Answer

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

The case $k=2:$ I think that for $k=2$ the sharp result provided $ab \gt a|B|+b|A|+\max(a,b)$ (or something like that) is that 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, 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.$ I briefly mention the other extre later on.

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

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

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$

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\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=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 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.$ Thid seem to resemble the "other extreme" example above. 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) 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.

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$

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

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

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.

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$ 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-2 \le|A|.$

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

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

The case $k=2:$ I think that for $k=2$ the sharp result provided $ab \gt a|B|+b|A|+\max(a,b)$ (or something like that) is that 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, 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.$ 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$

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

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

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

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.$ 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 the generalization to larger $k$ the situation is about the same, 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}$ followed by a gap of length $(\prod a_i)-t$ that is always true and it is usually true that this gives the longest possible gap. The exceptions are when $t$ is quite large relative to $\prod 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$ 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$ 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 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$ say that $A_i$ is equivalent to any of the sets $A_i+c$ and $-A_i+c.$

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

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

Geometry The picture of a sort of affine plane with two 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 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}$ It will follow a periodic trajectory and we might wonder how long a partial trajectory could be and miss a set with some factored form and given size (or measure.) Although the possible details are not clear, perhaps one could recruit results about Diophantine approximations. Perhaps the higher dimensional cases could be understood through simultaneous approximation.

Note: As I finished writing 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 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$ 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-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 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.$

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

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=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 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 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) 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.