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.


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.

  • 2
    $\begingroup$ (1) If I understand correctly, the number of possible $P_{5,7,11}$ would be $5\times 4 \times 7 \times 6 \times 11 \times 10$, representing the choices of $i,j$ for each of $5,7,11$? (Or perhaps you restrict to $0 \le i < j < p$ in which case divide by $2$ for each $p$.) (2) When you say the number seems independent of $y$, you mean e.g. if $n=1$ then for any $y$ there are 7500 sets, but for different $y$ those would be different families of 7500 sets each, right? $\endgroup$ – antkam Oct 6 at 3:39
  • $\begingroup$ That's right. That's what I am trying to show. The count is the same even if the particular classes are different. $\endgroup$ – Larry Freeman Oct 6 at 3:44
  • $\begingroup$ Would you agree that $c_{5,i,j}(y,4) = True$ for any $i,j,y$? Coz with $4$ consecutive numbers you cannot avoid two different choices of $i,j \pmod 5$. This also means if $n \ge 4$ there is no set of triplets where $C_{P_{5,7,11}}$ is false, right? $\endgroup$ – antkam Oct 6 at 3:51
  • $\begingroup$ $c_{p,i,j}(y,p-1) =$ True for any $i,j,y,p$ Great point. I think that I have defined it incorrectly. Let me see what's wrong in my above definition. $\endgroup$ – Larry Freeman Oct 6 at 4:15
  • 1
    $\begingroup$ @toby, you ask a great question. Members who are very strong in answering questions will have a significantly higher reputation. Badges seem to be more a measure of activity. I am very active on the site. I am more a learner than an expert. :-) $\endgroup$ – Larry Freeman Oct 12 at 16:44

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

  • $\begingroup$ Thanks very much! I appreciate the time that you spent on this. $\endgroup$ – Larry Freeman Oct 10 at 22:44

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.