Proof writing: looking for help in precisely expressing an idea I have about combinations of pairs of distinct residue classes

Question

I am working on an idea which I would call "pairs of distinct residue classes for a given set of distinct primes" which is an attempt to count the number of possible combinations of residue classes in a given context.

Here is the set that I am trying to define below: $C_{P_{p_1,\dots,p_m}}(y,n)$

While it is quite clear in my head, expressing in precise terms has proven to be quite difficult for me.

Below is my attempt. I would greatly appreciate any questions or comments. :-)

• Let $y, p, n$ be integers with $p$ prime.

• Let $c_{p,i,j}(y)$ be a boolean function that is true if $y \not\equiv i \pmod p$ and $y \not\equiv j \pmod p$.

• Let $P_{p_1, \dots, p_m}$ be a set of triplets $\{p_1, i_1, j_1\}, \{p_2, i_2, j_2\}, \dots, \{p_m, i_m, j_m\}$ where each $p_k$ is distinct and each $i_k \not\equiv j_k \pmod {p_k}$

• Let $C_{P_{p_1,\dots,p_m}}(y,n)$ be a boolean function that is true if there exists $t$ such that $y \le t < y+n$ and for each triplet $\{p_k, i_k, j_k\}$ in $P_{p_1, \dots, p_m}$, it follows that $c_{p_k,i_k,j_k}(t)$ is true.

---

My interest here is counting the number of distinct values of $P_{p_1, \dots, p_m}$ where $C_{P_{p_1,\dots,p_m}}(y,n)$ is false.

For example, for $P_{5,7,11}$:

• if $n=1$, there are 7500 distinct set of triplets where $C_{P_{5,7,1}}$ is false.
• if $n=2$, there are 4530 distinct sets of triplets where it is false.
• if $n \ge 11$, there is no set of triplets where $C_{P_{5,7,1}}$ is false.

It appears to me that the number is the same regardless of $y$. This is the question that I am interested in exploring.

---

Edit:

Based on comments from antkam, I realized that my definition was not correct.

I have updated the definition of $c_{p,i,j}(y,n)$ to only be $c_{p,i,j}(y)$ and to be true when the value is not congruent to either $i$ or $j$.

I have also updated the definition of $C_{P_{p_1,\dots,p_m}}(y,n)$.

With these changes, I believe that my examples hold.

Answer 1

Comments + a potential proof

---

OK I think I understand what you're trying to do (based on the question text on 2019/10/10). If you don't mind, let me rephrase things a bit to use more descriptive language:

• Definition: A triplet $(p, i, j)$ with $p$ prime and $i \not\equiv j \pmod p$ is called a trap.

• Definition: An integer $y$ avoids the trap $T = (p, i, j)$ if $y \not\equiv i \pmod p$ and $i \not\equiv j \pmod p$

  • This is equivalent to your $c_{p,i,j}(y) = True$.

• Definition: A range of integers $[y, y+n)$ defeats a set of traps $P = \{T_1, T_2, \dots, T_m\}$ if there exists $t \in [y, y+n)$, i.e. $y \le t < y+n$, s.t. $t$ avoids each of the traps.

  • This is equivalent to your $C_P(y,n) = True$.

  • Note: the same $t$ must avoid all the traps. I.e. it is insufficient if some $t_1$ avoids $T_1$, and a different $t_2$ avoids $T_2$, etc.

  • Sanity check: if the set has only $1$ trap, then it is defeated whenever $n\ge 3, p \ge 3$, because the trap can only catch $2$ numbers and the range has $\ge 3$ numbers.

I hope you agree that the above is a valid re-wording. If so, then here are some observations which may interest you:

Claim: "Defeat" is a shift-invariant property, in the sense that if we shift the range, and also shift every trap by the same amount, that does not affect whether the range defeats the set of traps or not. To be more precise:

For any integer $a, [y, y+n)$ defeats $\{(p_1, i_1, j_1), \dots, (p_m, i_m, j_m)\}$ iff $[y+a, y+a+n)$ defeats $\{(p_1, i_1+a, j_1+a), \dots, (p_m, i_m+a, j_m+a)\}$

Proof: obvious. $t$ avoids $(p_k, i_k, j_k)$ iff $t+a$ avoids $(p_k, i_k + a, j_k + a)$.

Corrollary: I think this explains why the number of sets of traps of the form $P_{5,7,11}$ defeated by $[y, y+n)$ depends on $n$ but not on $y$.