Characterise the Behrend sequences: which $A$ make the set of multiples $M_A$ have density 1? (Erdős #691)
Statement
Given $A\subseteq\mathbb{N}$, let $M_A=\{\,n\geq 1 : a\mid n\text{ for some }a\in A\,\}$ be its set of multiples. Find a necessary and sufficient condition on $A$ for $M_A$ to have (natural) density $1$. A sequence $A$ with this property is called a Behrend sequence.
Acceptance. FULLY RESOLVES (proof-shaped): a complete rigorous proof — a Lean/Coq formalisation preferred, otherwise a full written proof — exhibiting an explicit necessary-and-sufficient condition on an arbitrary $A\subseteq\mathbb{N}$ for $M_A$ to have density $1$, with the equivalence established in both directions. ADVANCES: prove a new sufficient condition or a new necessary condition strictly generalising the known cases stated in the background (the pairwise-coprime divergence criterion; Tenenbaum's $\beta=\log 2$ threshold for two-sided lacunary block sequences), with proof; or settle the Behrend / non-Behrend dichotomy for a natural family of sequences not covered by Tenenbaum's theorem, with proof. Deliver the proof or the new criterion together with its demonstration.
Background
Posed by Erdős [Er79e] and listed as open on erdosproblems.com/691 (fetched 2026-07-21, status 'open'). When $A$ is pairwise coprime with $1\notin A$ (in particular a set of primes), the density of $M_A$ is $1$ if and only if $\sum_{a\in A}1/a=\infty$; the general case is far subtler. For block sequences — $A$ a union of intervals $(n_k,(1+\eta_k)n_k)\cap\mathbb{Z}$ over a lacunary sequence $n_1<n_2<\cdots$ — Erdős believed there is a threshold $\alpha\in(0,1)$ so that with $\eta_k=k^{-\beta}$ one gets density $1$ for $\beta<\alpha$ and density $<1$ for $\beta>\alpha$. Tenenbaum [Te96] observed this fails as stated (if the $n_j$ grow fast enough $A$ is never Behrend, whatever the $\eta_k$), and, imposing the two-sided condition $1<C_1<n_{i+1}/n_i<C_2$ that Erdős confirmed he had intended, proved the threshold is $\beta=\log 2$: Behrend iff $\beta<\log 2$, not Behrend iff $\beta>\log 2$. A full characterisation for arbitrary $A$ remains open. This sits in the classical Davenport–Erdős–Hall theory of densities of sets of multiples; compare the finite-set density question Erdős #488 (erdosproblems.com/488), which is distinct. Attacker's tool: the analytic machinery of logarithmic densities of sets of multiples (Hall–Tenenbaum), together with numerical estimation of the density of $M_A$ for explicit block families to probe candidate thresholds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #691 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.