Distribution of composite numbers

Question

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}$.***

Answer 1

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

Answer 2

The result is wrong. The major problem is that there is little control over the common elements of the sets A_i. I suggest coming up with simpler sets of conditions and checking relations between those before trying a conjecture.

Here is an example to show the density result is wrong. Condition 1 says A_i is a convex subset of kd_i for k ranging over positive integers. Let D be the product of all the d_i, and have D be the smallest member of each set A_i.

Condition 2 has all the d_i coprime to each other and to x; very well, we'll pick d_i from the set of primes greater than 100 and choose x to be 7.

To satisfy condition 3, we will let d=x= the number of members in each A_i. By condition 2), exactly one member out of each A_i is a multiple of x, and that member is not D.

Condition 4 is satisfied as any two of the A_i intersect in the singleton set containing D, which is not a multiple of x.

Now union A_i (I assume there are n such sets and n is at least 2) has 6n+1 members, n of which are multiples of x=7, which is more than 1/7.

One can tweak this example to get higher densities of multiples of x in the union. One needs more uniformity in the A_i as well as other conditions to reflect what is going on with the sieves. If you want to simplify current sieve theory, you might look at some texts on the subject. Harman, Iwaniec, Cojocaru and Murty, Tao's blog, are some of the names that come to mind.

Answer 3

I am afraid the weak version (at this writing) involving density being less than $1/(x-2)$ doesn't work either. Simply pick $d_i$ and $x$ near but less than $\sqrt{N}$, and arrange $K$ and $L$ so that $K \lt xd_1 \lt K +L \lt N$, and so that there are very few multiples of $d_i$, say $2$ or fewer, in the desired interval. Finally, limit $n$ so that the union has much fewer than $x-2$ elements. Then the density of multiples of $x$ in the union will be much greater than $1/(x-2)$. To forestall a similar and newer version of the conjecture, notice that this example can be tweaked in several directions in terms of the conjectural assumptions and the conjectural conclusion.

I ask that the poster find a different audience. A series of questions covering conjectures as posted here might find a better reception at math.stackexchange.com, primarily because there is an audience of people who would like to improve their skill at producing counterexamples. I feel that this problem and its rapid turnover with variations has worn out its welcome in this audience, without making progress on the basic issue. Alternately, have the poster preview their next MathOverflow question on meta.mathoverflow, so that something like the above can be prevented.

Gerhard "Sometimes Exploration Should Be Solitary" Paseman, 2015.05.07

Answer 4

I see that The Masked Avenger has probably already got an answer (21h ago at the time of this writing :-). Since I also got my counterexample(s) let me state it here. At least I think that my presentation is perhaps more direct.

Let harp $\ [a;b),\ $ where $\ 0<a<b\ $ are positive reals, be the set of reals $\ t\ $ such that $\ a<t<b,\ $ and $\ \frac ta\ $ is an integer (i.e. $\ a\,|\,t;\ $ the musical name harp stands for homogenous arithmetic progressions).

Let $\ n>2\ $ be an even integer. Consider the following two harps:

$$A\ :=\ [n-1;\, 2\!\cdot\!(n^2-1))$$ $$B\ :=\ [n+1;\, 2\!\cdot\!(n^2-1))$$

Also, let

$$\ C\ :=\ A\cup B$$

Let $\ x:=2,\ $ and

$$\ d_H\ :=\ \frac {\left|\,\{y\in H: x|y\}\,\right|}{\left|H\right|}$$

for arbitrary harp $\ H.\ $ Then:

$$d_A\ :=\ \frac n{2\cdot n+1}$$ $$d_B\ :=\ \frac{n-2}{2\cdot n -3}$$ $$d_C\ :=\ \frac{2\cdot n - 2}{4\cdot n-3}$$

and

$$d_B\ <\ d_A\ <\ d_C$$

for every even integer $\ n>2.$

    C O M M E N T S   to the present "version 1" and "version 2"

The text of the Question was modified several times (e.g. in my comments, which later I removed as unnecessary, I provided counterexamples to the VERY first two versions, posted before later versions). Thus let me add some comment which complement the present version (2015-05-07, 00:58 of my Ann Arbor time zone :-).

First of all, and this is extra which was not required by the Question: in my examples the values $\ d_i\ $ belong to the arithmetic progressions of the example. Thus I have satisfied a significantly sharper restriction (which to me was not obvious).

On the other hand, the assumption about values $\ d_i\ $ being prime was new to me. Nevertheless, in my examples it is satisfied each time when my values $\ d_i\ $ which are $\ n-1\ $ and $\ n+1\ $ are twins. Also m $\ x:=2\ $ is prime, and relatively prime to each of $\ d_i,\ $ as well as $\ d_i\ $ and $\ d_j\ $ are relatively prime whenever $\ i\ne j.$

The simplest specific example above is obtained for $\ n:=4.\ $; and then the two harps have $\ 9\ $ and $\ 5\ $ elements.

    C O M M E N T S   to "Last Version"

We get a counterexample also for the "Last Version"--just let $\ n:=4.\ $ The respective values of $\ M\ N\ $ are $\ M:=3\ $ and $\ N:=24.$