# The Erdős primitive set conjecture

A set of integers greater than 1 is **primitive** if no number in the set divides another. Erdős proved in 1935 that the series of $1/(n \log n)$ for $n$ running over a primitive set A is universally bounded over all choices of A. In 1988 he conjectured that the universal bound is attained for the set of **prime numbers**. In this research case study, Oxford's Jared Duker Lichtman describes recent progress towards this problem:

"On a basic level, number theory is the study of whole numbers, i.e., the integers $\mathbb{Z}$. Maturing over the years, the field has expanded beyond individual numbers to study sets of integers, viewed as unified objects with special properties.

A set of integers $A\subset \mathbb{Z}_{>1}$ is **primitive** if no number in $A$ divides another. For example, the integers in a dyadic interval $(x,2x]$ form a primitive set. Similarly the set of primes is primitive, along with the set $\mathbb{N}_k$ of numbers with exactly $k$ prime factors (with multiplicity), for each $k\ge1$. Another example is the set of **perfect numbers** $\{6,28,496,..\}$ (i.e. those equal to the sum of their proper divisors), which has fascinated mathematicians since antiquity.

After Euler's famous proof of the infinitude of primes, we know $\sum_p 1/p$ diverges, albeit "just barely" with \begin{align*} \sum_{p\le x}\frac{1}{p} \sim \log\log x. \end{align*} On the other hand, we know $\sum_p 1/p\log p$ **converges** (again "just barely"). Using the notation \begin{align*} f(A) := \sum_{n\in A}\frac{1}{n\log n}, \end{align*} we have $f(\mathbb{N}_1)<\infty$. In 1935 Erdős generalized this result considerably, proving $f(A) <\infty$ uniformly for all primitive sets $A$. In 1988 he further conjectured the maximum is attained by the **primes** $\mathbb N_1$:

**Conjecture 1**. $f(A) \leq f (\mathbb{N}_1)$ for any primitive $A$.

Note we may compute $f(\mathbb N_1) = \sum_p 1/p\log p \approx 1.6366$.

Since 1993 the best bound has been $f(A) < 1.84$, due to Erdős and Zhang. Recently, Carl Pomerance and I improved the bound to the following:

**Theorem 1**. $f (A) < e^\gamma \approx 1.78$ for any primitive A, where $\gamma$ is the Euler-Mascheroni constant.

Further $f(A) < f(\mathbb{N}_1)+0.000003$ if $2\in A$.

One fruitful approach towards the Erdős conjecture is to split up $A$ according to the smallest prime factor, i.e., for each prime $q$ we define $$A_q = \{ n \text{ in } A : n \text{ has smallest prime factor } q\}.$$

We say $q$ is **Erdős strong** if $f(A_q)\le f(q)$ for all primitive $A$. Conjecture 1 would follow if every prime is Erdős strong, since then $f(A) = \sum_q f(A_q) \le f(\mathbb{N}_1)$.

Unfortunately, we don't know whether $q=2$ is Erdős strong, but we showed that the first hundred million odd primes are all Erdős strong. And remarkably, assuming the **Riemann hypothesis**, over $99.999973\%$ of primes are Erdős strong.

**Primitive from perfection**

In modern notation, a number $n$ is **perfect** if $\sigma(n)=2n$ where $\sigma(n) = \sum_{d\mid n}d$ is the full sum-of-divisors function. Similarly $n$ is called deficient if $\sigma(n)/n<2$ (abundant if $>2$).

Since $\sigma(n)/n$ is multiplicative and $>1$, we see that perfect numbers form a primitive set, along with the subset of non-deficient numbers $n$ whose divisors $d\mid n$ are all deficient.

It is a classical theorem that non-deficient numbers have a well-defined, positive asymptotic density. This was originally proven with heavy analytic machinery, but Erdős found an **elementary proof **by using primitive non-deficient numbers (this density is now known $\approx 24.76\%$). His proof led him to introduce the notion of primitive sets and study them for their own sake.

This typified Erdős's penchant for proving major theorems by elementary methods.

**A related conjecture of Banks & Martin**

Recall $\mathbb{N}_k$ denotes the set of numbers with $k$ prime factors. In 1993, Zhang proved $f (\mathbb{N}_k) < f (\mathbb{N}_{1})$, which inspired Banks and Martin to predict the following:

**Conjecture 2**. $f (\mathbb{N}_k) < f (\mathbb{N}_{k-1})$ for each $k > 1$.

They further predicted that, for a set of primes $\mathcal Q$, \begin{align*} f\big(\mathbb{N}_k(\mathcal Q)\big) < f\big(\mathbb{N}_{k-1}(\mathcal Q)\big)\qquad\textrm{for each } k>1 \end{align*} where $A(\mathcal Q)$ denotes the numbers in $A$ composed of primes in $\mathcal Q$. Banks and Martin managed to prove this conjecture in the special case of sufficiently "sparse'' subsets $\mathcal Q$ of primes.

This result, along with Conjectures 1 & 2, illustrates the general view that $f(A)$ reflects the prime factorizations of $n\in A$ in a quite rigid way.

Beautiful though this vision of $f$ may be, it appears reality is more complicated. Recently I precisely computed the sums $f(\mathbb{N}_k)$ (see Figure 1 below) and obtained a surprising **disproof of Conjecture 2**!

**Theorem 2. **$ f( \mathbb{N}_k) > f(\mathbb{N}_6) $ for each $k\neq 6$.

* Figure 1. Plot of *$f(\mathbb{N}_k)$

*for*$k=1,2,..,10$.

I also proved $\lim_{k\to\infty} f(\mathbb{N}_k) = 1$, confirming a trend observed in the data. However, much about this data remains conjectural. For instance, the sequence $\{f(\mathbb{N}_k)\}_{k\ge6}$ appears to increase monotonically (to 1), and the rate of convergence appears to be exponential $O(2^{-k})$, while only $O(k^{\varepsilon-1/2})$ is known. Similar phenomena seem to occur when experimenting with subsets $A\subset \mathbb{N}_k$ of e.g. even, odd, and squarefree numbers.

I hope this note illustrates Erdős' conjecture spawning new lines of inquiry. For example, researchers are now studying variants of the problem in function fields $\mathbb{F}_q[x]$. Also, in forthcoming work with Chan and Pomerance, we manage to prove Conjecture 1 for **2-primitive sets** $A$, i.e., no number in $A$ divides the product of 2 others.

The full Erdős conjecture has remained elusive, but working towards it has led to interesting developments. In the words of Piet Hein:

*Problems worthy of attack **prove their worth by fighting back.*