5
$\begingroup$

I am investigating the following sieve-like algorithm. Let $S_N=\{1,\dots,N\}$. For all primes $p$ with $p_0\leq p \leq M$, we remove from $S_N$ the following elements: all numbers $n\in S_N$ such that $\bmod(n, p) = A_p$ or $\bmod(n, p)= B_p$ with $0< A_p\leq B_p < p$. The choice of $M, A_p$ and $B_p$ is discussed later in this question. The resulting set, after these deletions, is denoted as $S(M, N)$. If $M$ is fixed (not depending on $N$), an obvious approximation for the number of elements in $S(M, N)$ as $N\rightarrow\infty$, is

$$P(M,N) =N\cdot\prod_{p_0\leq p \leq M}\Big(\frac{p-k}{p}\Big).$$

Here $k=2$ if $A_p\neq B_p$, otherwise $k=1$. The product is over primes only. The exact count for the number of elements in $S(M,N)$, is denoted as $C(M, N)$. The ratio $R(M, N) = P(M, N) / C(M,N)$ is the focus of this discussion, with very peculiar choices for $A_p, B_p$ and $M\equiv M_1(N)\equiv M_1 = O(\sqrt{N})$. While the ultimate goal is to prove that $C(M_1,N)\rightarrow\infty$ with the choices in question (which in turn would prove the twin prime conjecture), I am asking a much more modest question here.

With the choices described in the table below (except for the counter-example case), the following pattern emerges. Here $M$ is a function of $N$, though $N$ is assumed to be fixed, and large. The function $R(M,N)$, as a function of $M$, is unusually smooth and reaches a maximum at $M_0$ (in the twin prime case, $M_0\approx 3\sqrt{N}/2$). Then it slowly and smoothly decreases up to $M=M_2$, then rebound and eventually becomes infinite at some abscissa $M_3$ (in the twin prime case, $M_3=6N$). Between $M_0$ and $M_2$, an abscissa $M_1$ is called the critical point (in the twin prime case, $M_1=6\sqrt{N})$. Explanations are provided below.

$$ \begin{array}{|c|c|c|c|c|c|c|} \hline \mbox{Case} & p_0& k & M_1 & M_3 & A_p & B_p \\ \hline \mbox{twin primes}& 5 & 2 & 6\sqrt{N}& 6N & \lfloor p/6 + 1/2\rfloor & p-A_p\\ \mbox{cousin primes}& 5 & 2 &6\sqrt{N} & 6N & \lfloor p/6\rfloor & p-1-A_p\\ \mbox{primes}& 3 & 1 & 2\sqrt{N} & 2N & (p-1)/2 & (p-1)/2\\ \mbox{counter example}& 5 & 2 & 5\sqrt{N}& - & \lfloor p/5 + 1/2\rfloor & p-A_p\\ \hline \end{array} $$

The remaining of my discussion is articulated as follows:

  1. A chart illustrating the behavior of $R(M, N)$ for the prime numbers case, and why it is worth exploring this case
  2. My actual question
  3. Explanation as to why this is related to some conjectures (twin primes, in particular)
  4. Illustrating why the cases discussed here, are an exception rather than the rule, with the "counter-example" case being by far and large the most common case

1. Chart for $R(M,N)$

While it would be totally absurd to use my approach to prove that there are infinitely many primes (because you need Mertens third theorem to get the approximation $P(M_1,N) = O(N/\log N)$, the shape of the curve below is almost identical to that of the twin or cousin primes cases. In short, if you can answer my question for that particular case, answering the question for the twin or cousin primes is essentially the same. The nice thing about the primes is that we know there are infinitely many of them. So solving this via my approach could lead to a proof of the twin prime conjecture.

enter image description here

The top chart shows $R(M,N)=P(M,N)/C(M,N)$ for $N=200000$, the bottom one shows $C(M,N)-P(M,N)$. Only prime abscissa are shown. The X-axis represents $M$, with $M=M_1$ at the very right. The peak on the top chart is located at $M=M_0$. The curve is so smooth that except for the very few first value of $M$, it is either strictly increasing to the maximum, or strictly decreasing thereafter until $M=M_2$ (not shown on this chart as it stops at $M=M_1=2\sqrt{N})$.

2. My actual question

I have a few questions, ranging from less difficult to more difficult. Even an answer to the least difficult question will be accepted.

  1. Looking for references
  2. Is my approach sound? Do you see anything wrong?
  3. Are the patterns detected still true if $N$ is much larger?
  4. The shape of the curve is due to a very peculiar choice of $A_p$ and $B_p$. In most cases (see last section) the curve is very different. What are the conditions on $A_p$ and $B_p$ to get that kind of curve?
  5. Could the peak at $M_0$ shifts as $N$ increases, so that for $N$ large enough, $M_0 > M_1$? Do we always have $M_0 < M_1$?
  6. Prove that $M_0<M_1$ regardless of $N$ large enough, and in the case of the twin primes or cousin primes, $R(M_0,N)< N/\log^3 N$. That in itself would prove the twin prime conjecture (and same result for cousin primes), so I don't expect an answer to that question. Empirical evidence strongly suggests that $R(M_0,N)$ grows much more slowly, possibly like $O(\log N)$.

3. Connections to conjectures

The set $S(M_1, N)$, in the case of twin primes, cousin primes or primes, is a subset of some OEIS sequences mapping one-to-one (respectively) to twin primes, cousin primes or primes. It contains all the elements of these sequences less than $N$, except a few of them, the smallest ones. For instance, if $N = 3068200$ and we are dealing with twin primes, then $S(M_1, N)$ contains all the $99998$ elements of A002822 (mapping to the first $99998$ twin primes if you ignore $\{3, 5\}$) up to $3068165$, except for the first $215$ entries. Details can be found here.

The OEIS sequences associated with my sieve algorithm are as follows:

So if (say) the set $S(M_1,N)$ related to twin primes contains infinitely many elements, which it seems is guaranteed if $R(M_0, N) < N/\log^3 N$, then there are infinitely many twin primes.

The reason why $M_1$ is called the critical point is because when $M=M_1$, all the elements of $S(M, N)$ are elements of the corresponding OEIS sequence. If $M<M_1$, this is no longer true, and the number of elements in $S(M,N)$ is artificially inflated, resulting in a higher $R(M, N)$, culminating at $M=M_0$.

4. Counter-examples

This represents the immense majority of cases, for instance if you pick up $A_p$ or $B_p$ randomly. In this case $R(M, N)$ is much closer to $1$ as long as $M$ is not too large (suggesting it is easier to prove that $S(M_1,N)$ contains infinitely many elements as $n\rightarrow\infty$), but the behavior of $R(M, N)$, for fixed $N$ and as a function of $M$ is more erratic and unpredictable. See chart below as an example, corresponding to the "counter example" case in my table.

enter image description here

Compare this chart with the previous one.

Improve this question
$\endgroup$
3
  • $\begingroup$ I looked at $h(M,N)\equiv C(M,N)-C(M^*,N)$ as a function of $M$, when $N=200000$, for the primes case. Here $M^*$ is the next prime after the prime $M$. Starting at $M=631$ and at least up to $M=M_1=883$, we have $h(M,N)=1$. For twin primes, the situation is a bit more complicated. $\endgroup$
    – Vincent Granville
    Commented Sep 7, 2021 at 18:43
  • $\begingroup$ Let $p_1,p_2,\dots$ be the primes with $p_1=2$. If $N=p_1p_2\dots p_t$ and $p_s\leq p_t$, then $C(p_s,N)=p_1p_2\times\prod_{5\leq p \leq p_s}(p-2)\times \prod_{p_{s+1}\leq p \leq p_t} p$. This is true for the twin and cousin prime cases. The product is over primes. $\endgroup$
    – Vincent Granville
    Commented Sep 8, 2021 at 2:08
  • 1
    $\begingroup$ There may be a connection between the condition $A_{p}+B_{p}=p$ and the congruence requirements for $r$ to be a primality radius of $n$ in my question About Goldbach's conjecture. $\endgroup$
    – Sylvain JULIEN
    Commented Sep 11, 2022 at 16:19

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.