Generalising Dirichlet's theorem in arithmetic progressions-prime combinatorics

Question

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.

Answer 1

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.

Answer 2

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.