When does a non-empty CRT residue set meet a short interval?
问题内容
Let $m_1,\ldots,m_s$ be pairwise coprime positive integers, and let
$$ M=\prod_{i=1}^s m_i. $$
For each $i$, let $A_i$ be a non-empty proper subset of residue classes modulo $m_i$. Define the CRT-allowed residue set $S \pmod M$ by
$$ S=\{x \pmod M : x \pmod {m_i} \in A_i \text{ for every } i\}. $$
By the Chinese remainder theorem,
$$ |S|=\prod_{i=1}^s |A_i|, $$
so $S$ is non-empty as a subset of residue classes modulo $M$.
My question is about the local version.
Let
$$ I=[a,a+L-1] $$
be a specific interval of integers, possibly much shorter than $M$.
What additional hypotheses are needed to guarantee that
$$ I\cap S\neq \varnothing? $$
Equivalently, when can one pass from the full-period CRT fact
$$ S\neq \varnothing \pmod M $$
to the local conclusion that a particular interval $I$ contains an integer whose residues lie in all the allowed sets $A_i$?
One obvious sufficient condition is in terms of the largest gap between consecutive representatives of $S$ modulo $M$. If $G(S)$ denotes this largest gap, then every interval of length greater than $G(S)$ meets $S$.
My questions are:
- Is this the standard way to formulate the problem?
- Is there standard terminology for $G(S)$ in this general CRT setting?
- Are there known general bounds for $G(S)$ in terms of the moduli $m_i$ and the sizes or structure of the sets $A_i$?
- Is this considered a Jacobsthal-type problem, a covering congruence problem, or something else?
Any references or corrections to the formulation would be appreciated.
回答 (0)
暂无回答记录。