I have moved this question to math.stackexchange.com. People who are interested in this question can discuss at :https://math.stackexchange.com/questions/1272431/distribution-of-composite-numbers
Motivation: I want to give an abstract formulation of Eratosthenes's Sieve and try to conject a property of Eratosthenes's Sieve. If this property are right, then I can use it to find a low bound of numbers of primes between any segment $[1,N]$ in the set of natural numbers, so this problem is connected to distribution of primes.
The following statements can be seen as conjectured properties of distribution of composite numbers.
- Version 1:
Let $A_1, \cdots, A_n$ be finite sets of natural numbers and $x>1$ is a natural number.
If the following conditions are satisfied:
$(1)$ each $A_i$ $(1\leq i\leq n)$ is an arithmetic sequence with common difference $d_i$ being prime number and each term being a multiple of $d_i$,
$(2)$ the common differences $d_i$ $(1\leq i\leq n)$ are coprime to each other and also they are coprime to $x$,
$(3)$ the density of multiples of $x$ in each $A_i$ $(1\leq i\leq n)$ is less than or equal to $1/d$ $(d\geq 1)$,
$(4)$ for any subset $J\subset [1,\cdots,n]$, the density of multiples of $x$ in $\bigcap_{j\in J}A_j$ is also less than or equal to $1/d$,
then the density of multiples of $x$ in $A_1\cup\cdots\cup A_n$ is also less than or equal to $1/d$.*
- Version 2:
Let $A_1, \cdots, A_n$ be finite sets of natural numbers and $x$ is a prime number.
If the following conditions are satisfied:
$(1)$ each $A_i$ $(1\leq i\leq n)$ is an arithmetic sequence with common difference $d_i$ being prime number and each term being a multiple of $d_i$,
$(2)$ the common differences $d_i$ $(1\leq i\leq n)$ and $x$ are distinct from each other,
$(3)$ the density of multiples of $x$ in each $A_i$ $(1\leq i\leq n)$ is less than or equal to $1/d$ $(d\geq 1)$,
$(4)$ for any subset $J\subset [1,\cdots,n]$, the density of multiples of $x$ in $\bigcap_{j\in J}A_j$ is also less than or equal to $1/d$,
then the density of multiples of $x$ in $A_1\cup\cdots\cup A_n$ is also less than or equal to $1/d$.*
Is this question easy for experts? I think the result should be right, but I can not prove it. I hope someone can give some hints to prove this conjecture or some counterexamples to improve this conjecture.
I am not very sure that the $(4)$ is implied by the conditions $(1),(2), (3)$. But indeed this condition is satisfied by the Eratosthenes's Sieve in which $d_i$s and $x$ are distinct primes. In order for insurance purposes, I add the $(4)$ condition.
——————————————————————————-
An example shows that the $(1)$ condition (especially, the first term of $A_i$ should be a multiple of $d_i$) is necessary:
$A=\{1,4,7,10,13,16\}$ with common difference $3$, $B=\{3,8,13,18,23,28\}$ with common difference $5$, $d=3$, $x=4$. $A\cup B=\{1,3, 4,7,8,10,13,16,18,23, 28\}$. Both densities of multiples of $x=4$ in $A$ and $B$ are $1/3$, the density of multiple of $x=4$ in $A\cup B$ is $4/11$ which is large than $1/3$.
The example of The Masked Avenger shows that it is better to suppose $d_i$ and $x$ to be prime numbers.
His example: $A_i=3^i\times \{1,2,3,4\}$, $d_i=3^i$, $x=4$.
————————————————————————————-
Since The Masked Avenger gives his ingenious answer and disproves the two statements above, I give the last version which is my original motivation.
- **Last version **:
Let $M,N$ be natural numbers, $d_i$ $(1\leq i\leq n)$ and $x$ are distinct prime numbers less than or equal to $\sqrt{M+N}$, $A_i=\{multiples\ of\ d_i\}\cap [N, N+M]$ $(1\leq i\leq n)$.
If the density of multiples of $x$ in each $A_i$ $(1\leq i\leq n)$ is less than or equal to $1/d$ $(d\geq 1)$,
then the density of multiples of $x$ in $A_1\cup\cdots\cup A_n$ is also less than or equal to $1/d$.*
—————————————————————————————
I am particularly grateful to The Masked Avenger and Włodzimierz Holsztyński for their ingenious counterexamples.
Now I give a weaker version about distribution of composite numbers. May be theire examples can also disprove this conjecture. But I need time to study their examples.
*** **weak version **:
Let $K,L,N$ be natural numbers and $K+L\leq N$. $d_i$ $(1\leq i\leq n)$ and $x$ are distinct prime numbers less than or equal to $\sqrt{N}$. $A_i=\{multiples\ of\ d_i\}\cap [K, K+L]$ $(1\leq i\leq n)$.
If $x>2， L> \sqrt{N}$, then the density of multiples of $x$ in $A_1\cup\cdots\cup A_n$ is less than or equal to $\frac{1}{x-2}$.***
*** ** version 5 **:
Let $N$ be a natural numbers. $d_i$ $(1\leq i\leq n)$ and $x$ are distinct prime numbers less than or equal to $\sqrt{N}$. $A_i=\{multiples\ of\ d_i\}\cap [1,N]$ $(1\leq i\leq n)$.
If $x>3$, then the density of multiples of $x$ in $A_1\cup\cdots\cup A_n$ is less than or equal to $\frac{1}{x-2}$.***
Best Answer
I would like to maintain my basic position on the other post: that this forum does not do well with questions that frequently change. Since the last version has hit rather close to home, I will remark on it separately, in the hopes that research on it will be more fruitful.
The last version I mention is at this writing called version 5. Rewriting it a little, it suggests that for any selection of $n$ primes $d_i$ less than $M$, and for any prime $x$ less than $M$, the number of multiples of $x$ less than $M^2$ which are also multiples of one or more of the $d_i$ do not get very frequent among such multiples. Specifically, $(x-2)M_x \lt M_d$, where $M_d$ is (the count of) the numbers less than $M^2$ which are multiples of one or more of the $d_i$, and $M_x$ is (the count of) that subset of $M_d$ which are multiples of $x$.
This version is likely to be true for two reasons: the subset which I will also call $M_d$ (a union of sets $A_i$ in the original formulation) is large enough to guarantee at least $M$ many members in it, and the conjectured density $1/(x-2)$ is weak enough that it is likely to hold. I do not have a proof of this version. I do want to point out a simple example to think of for counterexamples.
Let $d_i$ range over $2,3$, and $5$, and let us count multiples of $7$ starting from $1$. It gets boring quickly, so I will just note some of the changing ratios: (0,1), (0,9), (1,10) (for the multiple 14 occurring among the first 10 numbers not coprime to 30), (1,14), (2,15),(2,20),(3,21),(3,25),(4,26)! The point is that the members of the union are distributed sporadically enough that the fourth multiple of 7 among positive nontotatives of 30 occurs early enough that the ratio $M_x/M_d$ could get larger than 1/7.
How much larger? In the general case, I don't know exactly. Part of what I know is discussed in Bound the error in estimating a relative totient function, which is concerned with the excess of the actual number of coprimes in an interval compared with the expected number. (This excess corresponds to a deficit in the expected number of nontotatives, or the union of the poster's $A_i$.) Various of the conjectures in this question have touched on issues related with a deeper investigation of a problem I have been looking at for years. The best results available stem from analytic number theory; it is my hope that examining combinatorial approaches will shed some light on this and related problems, including the twin prime conjecture mentioned by the poster.
I recommend references in the MathOverflow question 88777 linked above for the poster, including the 2008 paper of Codeca and Nair mentioned in Alan Haynes's answer. I also ask for the poster's understanding in trying a different method for his/her inquiries. Using a different forum such as math.stackexchange.com may turn out to be fruitful, but understanding the accessible literature should be a first step. Fortunately, a lot of that literature is contained in the questions themselves, as well as reference to that literature. Your search may be quickly aided by using phrases and names from 88777.
Gerhard "Good Luck On Your Studies" Paseman, 2015.05.08