Let $M$ be a natural number $M>1$. For every prime $p_i$ not dividing $M$ take an arithmetic progression $A_i=k_i+np_i$ , $n\geq 0$ such that $k_i>p_i^2/M$. Is there any $M$ and some choice of the $k_i's$ such that $\cup A_i= \mathbb{N}$ ?

CONJECTURE: There is not such choice for any $M$

  • MOTIVATION: It is not hard to see that if there is not such a choice for any $M$ Dirichlet's theorem in arithmetic progressions is an easy consequence. Of course this is much more general. We can modify many well known problems in this way.

For example ,to the previous question, if we take $2$ arithmetic progressions for each $p_i>M$, instead of $1$ with the same condition then we have something stronger than the twin prime conjecture and polignac's conjecture in general, If we take $3$ arithmetic progressions we have something stronger than the problem that infinitely many times exists every logical form with $3$ primes ( for example p, p+2,p+6), etc. To these problems it is enough to take infinitely many $M$, not all...

  • Secondly it is one of the easiest questions to this spirit and i want to know if we can say something about this kind of questions with known techniques. So

What kind of mathematical techniques we could use to reach this kind of problems?

-related to Covering $\mathbb{N}$ with prime arithmetic progressions

Can we compute the function of the length of the intervals that we can cover using the primes not dividing $M$ below some $x$ and compare it to the growth function of the number of the primes below some $x$ ?

  • Notice that even for the primes below $M$ the arithmetic progressions can start from $1$ , the first term of every $A_i$ for $p_i < M$ can be less than $p_i$ this changes and the first term of the $A_i's$ becomes larger and larger comparing with the $p_i's$

I am waiting for any help to this direction, thank you.

  • 1
    $\begingroup$ Was there any purpose of the last edit, except to increase visibility of the question (after only ten hours)? $\endgroup$
    – user9072
    Nov 26, 2011 at 17:39
  • $\begingroup$ i am expecting more mathematical comments... $\endgroup$ Nov 26, 2011 at 18:14
  • 5
    $\begingroup$ I will take your second comment as a general statement and not a response, so here is my advice: be patient. $\endgroup$
    – user9072
    Nov 26, 2011 at 18:51
  • $\begingroup$ Which values of $M$ have you already tried, or obtained "experimental" data for? $\endgroup$
    – Yemon Choi
    Nov 26, 2011 at 19:06
  • 2
    $\begingroup$ If you still have your email address with "minasteris" in it, I will be happy to reply in brief here and in more detail by email later. It is your right to edit your post as you wish; I am with quid in that your style of frequent edits with little content change shows (to me) some lack of patience. I too suggest waiting some time (days) between successive edits. During that time, you could write down your inspiration and motivation for this and your previous questions in some detail; I will be asking about that soon. Gerhard "Ask Me About Prime Gaps" Paseman, 2011.11.27 $\endgroup$ Nov 28, 2011 at 7:31

2 Answers 2


I can't resist some comments. I find it highly unlikely that what you ask is possible. The question seems a bit odd in that it is so specific when more basic questions are open.

In the following some estimates are rough and corrections are welcome. Let $p_i$ be the $i$th prime and $P_t$ the product of the first $t$ primes. For example $p_{10000}=104729$ and $P_{10000} \approx e^{104392.2}.$ This illustrates the estimate $\ln{P_t} \approx p_t.$

Define $h(t)$ to be the smallest $N$ so that out of every $N$ consecutive integers at least one is relatively prime to $P_t$. Equivalently, it is the largest $N$ such that some $N-1$ consecutive integers each have a prime divisor from among the first $t$ primes. Equivalent to that is that $h(t)$ is the largest $N$ such that there is a choice of $t$ residues $ k_{1t},\cdots ,k_{tt} $ with $\cup_1^t A_{it} \supset [1,N-1].$ where $A_{it}=k_{it}+np_i.$

According to this article $h(t) \gt (2e^{\gamma}+o(1))\frac{p_t\ln{p_t}\ln_3{p_t}}{ln_2^2{p_t}}$ where $\ln_j$ is the $j$-fold iterated logarithm. This lower bound seems reasonably close for $t \lt 50$ (the limit of knowledge at the time, and perhaps now). The best known upper bound is $h(t) \lt \ln^2(P_t).$ Using the estimate above that $\ln{P_t} \approx p_t$ we then get that $h(t) \lt p_t^2.$ I have seen it conjectured in a paper from 1976 that perhaps $h(t)=O(t^{1+\epsilon}).$ Note that $p_t \approx t\ln{t}=o(t^{1+\epsilon})$ I don't know how current that is. An off topic note is that sometimes one can find a longer interval of integers all enjoying a divisor from $p_1,\dots,p_{t-1},p_{t+1}$

With the notation above a weaker form of your question is

Is there an integer $M$ and system of residues $k_i$ such that for $A_i=k_i+np_i$ we have

  1. $\cup A_{i}=\mathbb{N}$

  2. With only finitely many exceptions, $k_i \gt \frac{p_i^2}{M}$

(I didn't get the motivation to require $p_i$ relatively prime to $M$. Was it just to forbid at least one prime?)

So the situation is that, as far as I know, no-one can say if $h(n) \gt \frac{p_t^2}{M}$ infinitely often, and there may even be reasons to doubt that. This is the case that you may completely change the residues each time you bring a new prime into play. In your case you want a single list of residues.Note that the choices which provide a good example for $h(n)$ may not be good for extending to $h(n+1)$.

$h(9)=39$ as shown by

$$2, 3, 2, 5, 2, 11, 2, 3, 2, 13, 2, 23, 2, 3, 2, 7, 2, 19, 2, 3, 2, 17, 2, 5, 2, 3, 2, 11, 2, 7, 2, 3, 2, 5, 2$$ $$ 13, 2, 3, 2, *, 2, *, 2, 3, 2, *, 2, *, 2, 3, 2, *, 2, 5, 2, 3, 2, 7, 2, *$$

This illustrates that $1+2n,2+3n,4+5n ,6+11n,10+13n,12+23n,16+7n,18+19n$ and $22+17n$ cover all the integers from $1$ to $67$ except for $40,42,46,48,52,60,66.$

The best we can do to extend this introducing the further primes $29,31,37,41,43$ is $h(10) \ge 42,h(11) \ge 46,h(12) \ge 48,h(13) \ge 52,h(14) \ge 60$ etc.The actual values are $46, 58, 66, 74, 90.$ But each requires a new selection of residues.

  • $\begingroup$ thank you for your answer, the motivation to require p_i relatively prime to M has to do with the relation to diriclhlet's theorem and the related questions. I am sorry but i cant ubderstand why this version of my question is weaker, in my opinion it is stronger because it is more easy (maybe) to prove that the A_i's cant cover all the naturals if every k_i is greater than p_i^2/M than for all except finitely... $\endgroup$ Dec 3, 2011 at 21:05
  • $\begingroup$ In your question you asked is there some M such that... then you should be able to use any larger M and maybe use a larger prime M which simply excludes one large prime. Anyway, it is a weaker requirement (since I left out relatively prime) so true it would be a stronger result but the answer is still probably no AND an even weaker requirement is to just have $h(n)$ bigger than p^2/M infinitely often. $\endgroup$ Dec 4, 2011 at 7:38
  • $\begingroup$ I have to admit that I don't see how a your first conjecture establishes Dirichlet's theorem in arithmetic progressions. Are you saying that if there was some prime p and an r with gcd(p,r)=1 yet no primes of the form pn+r (or only finitely many) then one could produce a counter example to your conjecture? $\endgroup$ Dec 4, 2011 at 7:43
  • $\begingroup$ Yes of course in this case we could have a counter example but if my first conjecture is true the Dirichlets theorem is a direct consequence. $\endgroup$ Dec 4, 2011 at 15:13
  • $\begingroup$ I think that if my conjecture is true then it means that something smaller than h(n) ( in the meaning that you dont use every prime ) is not bigger than p^2/M for every n . $\endgroup$ Dec 4, 2011 at 15:30

HINT: We first notice that if for every $(M,d)$ relatively prime there is at least one prime of the form $Mn+d$ then there are infinitely many primes of this form. The first number that every prime $p_i$ sieves is $p_i^2$ so $n_0 +1$ must be greater than $p_i^2/M$( where $n_0$ is the first number of the previous form that $p_i$ could sieve). If a prime divides $Mn+d$ for some number n it divides exactly $M(n+p_i)+d , M(n+2p_i)+d,etc.$. We can see that we have an arithmetic progression of the form $A_i=k_i+np_i$ where $k_i=n_0+1$ . Of course we can give more conditions for the $k_i's$ but the meaning of the question is :Can we prove Dirichlet's theorem using only this condition? This is the reason why my conjecture is a generalisation of Dirichlet's theorem.

Same reasoning gives the modification that I give in my question for the polignac's conjecture, etc.

  • $\begingroup$ I think Dirichlet proved a stronger result, namely that the primes are equidistributed in the invertible residue classes. $\endgroup$ Dec 6, 2011 at 12:21
  • 1
    $\begingroup$ yes thats true, but when we say diriclhets theorem in the elementary form we all know what we mean. $\endgroup$ Dec 6, 2011 at 13:57

Your Answer

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

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