A generalization of primitive sets and a conjecture of Erdős

A generalization of primitive sets and a conjecture of Erdős, Discrete Analysis 2020:16, 13 pp.

Call a set $A$ of integers greater than 1 primitive if no element of $A$ divides any other. How dense can a primitive set be? An obvious example of a primitive set is the set ${\mathbb P}$ of prime numbers, which has the property that $\sum_{p\in {\mathbb P}}\frac 1{p\log p}<\infty$. (This follows easily from the prime number theorem, or even just Chebyshev’s theorem.) In 1935 Erdős proved that the same is true of all primitive sets. That is, if $A$ is a primitive set, then $\sum_{a\in A}\frac 1{a\log a}<\infty$.

We briefly sketch his very short argument. He starts with the observation that if $a$ is a positive integer and $P(a)$ is the largest prime factor of $a$, then
$$\prod_{p< P(a)}(1-1/p)\geq \frac c{\log P(a)}\geq\frac c{\log a}$$
for some absolute constant $c>0$. Thus, it is sufficient to prove that
$$\sum_{a\in A}\frac 1a\prod_{p<P(a)}(1-1/p)<\infty.$$
In fact, Erdős obtains an upper bound of 1 for this quantity.

Indeed, the expression $\frac1a\prod_{p<P(a)}(1-1/p)$ is the asymptotic density of the set of integers with $a$ as an initial divisor: that is, the set $ID(a)$ of integers $n$ divisible by $a$ such that $n/a$ is not divisible by any prime smaller than $P(a)$. More concretely, if $n$ has prime factorization $p_1^{r_1}p_2^{r_2}\dots p_k^{r_k}$, then an initial divisor of $n$ is a number of the form $p_1^{r_1}\dots p_{j-1}^{r_{j-1}}p_j^{s_j}$, where $j\leq k$ and $s_j\leq r_j$, so the initial divisors of $n$ are totally ordered by divisibility. Therefore, if $A$ is primitive, the sets $ID(a)$ with $a$ in $A$ are pairwise disjoint, from which it follows that the sum of their densities is at most 1.

In 1988 Erdős asked whether the primes are extremal for this result. That is, if $A$ is a primitive set, does the inequality
$$\sum_{a\in A}\frac 1{a\log a}\leq\sum_{p\in {\mathbb P}}\frac 1{p\log p}\qquad (1)$$
always hold? The right hand side is approximately 1.6366, and it is known (by a previous result of two of the authors of this paper) that the left-hand side is less than $e^\gamma\approx 1.781$, where $\gamma$ is the Euler–Mascheroni constant. However, a full resolution of the Erdős question appears to be out of reach*, so the authors answer a related question that turns out to be simpler, but still hard enough to be interesting. A $k$-primitive set is one where no member of the set divides the product of $k$ distinct others (so a primitive set is a 1-primitive set). In 1938 Erdős wrote a paper that proved that a 2-primitive set (which he called an A-sequence) has at most $\pi(n)+O(n^{1/3}/\log n)^2$ elements less than or equal to $n$, where $\pi(n)$ is the number of primes up to $n$. Thus, even though the 2-primitivity condition is much weaker than the divisibility conditions satisfied by the primes, a 2-primitive sequence cannot be much denser than the primes. (By contrast, a 1-primitive sequence can contain all $m$ with $n/2<m\leq n$.)

This paper proves that the primes are extremal for the analogue of the Erdős 1988 question for 2-primitive sets $A$. They actually show a stronger result, which is that if $A$ is a 2-primitive set and $\lambda\geq 0.7983$, then for every $x$,
$$\sum_{a\leq x}\frac 1{a^\lambda}\leq\sum_{p\leq x}\frac 1{p^{\lambda}}.$$
The case $\lambda=1$ implies that (1) holds by a simple argument using partial summation.

It has been shown that a result like this can hold for 1-primitive sets if and only if $\lambda$ is greater than a constant approximately equal to 1.14. The fact that it is false for $\lambda=1$ gives an indication of why the problem for 1-primitive sets is so much harder.

• Update February 2022. Remarkably, it appears that the full conjecture has now been solved by one of the authors of this paper. (Although it is not yet published, we have heard that it has been carefully checked by at least one expert other than the author.)