1
$\begingroup$

Let $S$ be a finite set of integer, $n$ be a positive integer, $p_i$ denote the $i^{th}$ prime. Consider the set

$$\mathcal{P}_{S,n}:=\{x\mid0\leq x<\prod_{i=1}^np_i \text{ and }(\forall i\leq n, i>0)(\forall s\in S)\,x\not\equiv s\text{ (mod }p_i)\}$$

In other words, $\mathcal{P}$ is the set of naturals less than $\prod_{i=1}^np_i$ that, when taken mod $p_i$ for any $1\leq i\leq n$, are not congruent to any element of $S$. Using the Chinese Remainder Theorem, the exact number of elements in $S$ can be obtained as

$$|S|=\prod_{i=1}^n \big{(}p_i-|S\text{ (mod }p_i)|\big{)}$$

What is the length (or an estimate of the length) of the longest arithmetic progression in $\mathcal{P}_{S,n}$? For a fixed $S$, can the size of the longest arithmetic progression be estimated as $n$ tends to infinity?

$\endgroup$
1
$\begingroup$

If $p_i$ is not a factor of the common difference, then one of the first $p_i$ numbers in the arithmetic progression is congruent to $s\pmod{p_i}$, for any $s\in S$.
If all $p_i$ are factors of the common difference, then the common difference is a multiple of $\prod p_i$, and only one term fits inside $P_{S,n}$.
So the longest arithmetic progression possible has length $p_n-1$, and that is only possible when all the $s\in S$ are equivalent $\mod p_n$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.