11
$\begingroup$

Suppose we start with $k$ primes $p_1,p_2,\ldots ,p_k$ (not necessarily consecutive) and a residue class for each prime $r_1,r_2,\ldots ,r_k$.
We denote the least integer not covered by the arithmetic progressions $r_i+m\cdot p_i$ as $r_{k+1}$ which is going to be the new residue class for a (random) prime $p_{k+1}$.
We proceed in this way "covering" the natural numbers (without changing the $r_i$'s.)
Question:Is it true that $\sum\limits_{n=1}^\infty\frac{1}{r_n}=+\infty$?

Motivation:
This would directly imply Dirichlet's theorem on primes in arithmetic progressions if we make use of this
Lemma:
Let $a_n$ be a sequence of natural numbers, strictly increasing with $\gcd(a_i,a_j)=1$.
Then if $\sum\limits_{n=1}^\infty\frac{1}{a_n}=+\infty$ then the sequence contains infinitely many prime numbers.

I tried to modify some proofs which show the divergence of $\sum\frac{1}{p}$ but without much success.
Thank you very much in advance!

EDIT: The primes are distinct and the residue classes are not reduced modulo $p$.Suppose we start with the primes $2,3,7$ and their residue classes are $(1)_2 , (2)_3 , (4)_7$ which means $r_1=1$, $r_2=2$ and $r_3=4$. The least number not covered by the progressions $1+2k , 2+3k , 4+7k$ is $6$.We define then $r_4=6$ and $6$ is going to be a new residue class for a new prime (random choice) let's say $p_4=17$.Then $r_5=10$ and we choose a new prime (Let's say $p_5=5$) and continue in this direction.
The $r_i$'s could be much greater than the $p_i$'s

$\endgroup$
  • 2
    $\begingroup$ How do you choose those "random" primes? Do you want this result to hold for each possible way to choose them? Are you assuming that each prime will be chosen eventually? $\endgroup$ – Federico Poloni Jan 2 '15 at 0:10
  • 1
    $\begingroup$ When you refer to the $r_i$'s as residue classes, do you mean that each is to be reduced modulo the corresponding $p_i$? (Thus, we construct $r_{k + 1}$, choose $p_{k + 1}$, and then replace $r_{k + 1}$ by its reduction?) $\endgroup$ – LSpice Jan 2 '15 at 0:45
  • 2
    $\begingroup$ @S.Carnahan: in his first comment, KG says the case $\sum\frac{1}{p_n}<+\infty$ is easy. If $\sum\frac{1}{p_n}=+\infty$ and $r_n\le p_n$ for all $n$, then also $\sum\frac{1}{r_n}=+\infty$. So I guess the case of interest is when many $r_n$ are possibly larger than $p_n$. $\endgroup$ – Pietro Majer Jan 2 '15 at 9:29
  • 3
    $\begingroup$ Don't know how to prove your claim, but I like the lemma... $\endgroup$ – Seva Jan 2 '15 at 11:43
  • 2
    $\begingroup$ I guess if $(a_j)_j$ are pairwise relatively prime and only contain $n$ primes, then $\sum_j1/a_j\le 1+ \sum_{j=1}^n 1/p_j + \sum_{j=1}^\infty 1/p_j^2<+\infty$ $\endgroup$ – Pietro Majer Jan 2 '15 at 19:59
1
$\begingroup$

The question makes sense if the r's are all positive. The answer is likely to be yes for the folllowing reason: if it were no, there would be an explicit sequence where the r's grow faster than O(1/f'(n)), where f(n) is smaller than any iterated log function, and thus smaller than log log log log log n., call this log5 n or g(n). Current lower bounds of the conceivable maximal growth rate of the r's are like 1/(g'(n) *( log3 n)^2), see recent work of Ford, Konyagin, Green, Maynard, and Tao. Having such a sequence of r's and p's would allow one to radically improve on this bound, for one could leverage this to find really large gaps between primes.

Of related interest may be Kanolds work in 1963-5 on such sequences of r's. If the r's grow slowly enough (something like n^(2-c)), one can get Linnik's theorem on the least prime in arithmetic progressions as well as a non-quantitative version of Dirichlet's Theorem through elementary means.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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