ERDŐS/DAILY ▸

← back to the ledger

ERDőS #691 · PARTIAL

Erdős problem 691 — wave 7g

Date: 2026-07-27 (UTC)

Claim labels used throughout:

0. Mandatory live-page check

I fetched both the live problem page and its discussion thread on 2026-07-27 through a Bright Data browser session, not a datacenter curl.

Live status:

Thus none of the mandatory stop conditions is present.

Verbatim current statement

> Given $A\subseteq \mathbb{N}$ let $M_A=\{ n \geq 1 : a\mid n\textrm{ for some }a\in A\}$ be the set of multiples of $A$. Find a necessary and sufficient condition on $A$ for $M_A$ to have density $1$.

Results and qualifications listed on the live page

\[ A=\bigcup_k (n_k,(1+\eta_k)n_k)\cap\mathbb Z, \]

the page says that \(\sum_k\eta_k<\infty\) implies density \(<1\), and that \(\eta_k=1/k\) also gives density \(<1\).

\(1\log 2\). The equality case is not asserted on the page.

All visible discussion content

The page header says “4 comments”; the rendered thread contains three substantive 2026 entries, one deleted entry, and a 2025 reply:

1. YutaOriike (17 Apr 2026) shared a note and Lean file proving the finite-approximation equivalence

\[ d(M_A)=1\quad\Longleftrightarrow\quad \sup_{\substack{F\subseteq A\\F\ {\rm finite}}}d(M_F)=1. \]

2. Nat Sothanaphan replied that this is well known and pointed to Hall–Tenenbaum, equation (1.3).

3. YutaOriike replied that the note would be revised to credit Davenport–Erdős via Hall–Tenenbaum and presented as exposition/formalisation.

4. One older post is displayed as [Post deleted].

5. Thomas Bloom's visible reply to that deleted post says: “I think you might have misread the \(n_k\) as \(\eta_k\)?”

The live thread separately says there are no partial or complete solutions claimed in the comments.

1. Primary-source literature audit

I found and checked the following actual sources.

1. Erdős, Some unconventional problems in number theory, Astérisque 61 (1979), 73–82. Page 77 contains the problem and the block example. This verifies the live page's original citation.

2. Davenport–Erdős, On sequences of positive integers, J. Indian Math. Soc. 15 (1951), 19–24. [b] On pp. 19–21 they define the increasing finite densities and prove that their limit is both the lower natural density and the logarithmic density of the infinite set of multiples.

3. Hall–Tenenbaum, On Behrend sequences, Math. Proc. Camb. Phil. Soc. 112 (1992), 467–482. [b] Equation (1.3) is precisely the finite-approximation theorem cited in the live discussion. The introduction also quotes Erdős's request for a necessary and sufficient condition and treats special structured families.

4. Erdős–Hall–Tenenbaum, On the densities of sets of multiples, J. reine angew. Math. 454 (1994), 119–141. [b] This verifies that sets supported on integers with a bounded number of prime factors have natural density, while deciding whether that density is \(1\) remains a separate structural issue.

5. Ruzsa–Tenenbaum, A note on Behrend sequences, Acta Math. Hung. 72 (1996), 327–337. [b] Their Theorem 1 gives a genuine necessary-and-sufficient criterion for every \(A\subseteq\{pq:p,q\text{ prime}\}\). Thus the two-prime-factor case is already solved in the literature and is not claimed here as new.

6. Tenenbaum, On block Behrend sequences, Math. Proc. Camb. Phil. Soc. 120 (1996), 355–367. [b] This verifies the block theorem and the warning about the missing upper condition on \(n_{k+1}/n_k\).

7. Tenenbaum, Some of Erdős' unconventional problems in number theory, thirty-four years later (2013). This survey explicitly says that the two-prime-factor criterion is Ruzsa–Tenenbaum's and that boundedly many prime factors give existence of density, while emphasizing how intricate a general Behrend criterion is.

I searched by the problem statement, “Behrend sequence”, “sets of multiples”, the cited authors, and later citations. I found recent papers using Behrend sequences, but no primary source claiming a general structural characterization of arbitrary \(A\), and no source contradicting the live OPEN status. This is a search report, not a proof of absence.

2. The exact known reduction

Enumerate \(A=\{a_1,a_2,\ldots\}\), and put \(F_k=\{a_1,\ldots,a_k\}\). Davenport–Erdős gives

\[ \lim_{k\to\infty}d(M_{F_k}) =\underline d(M_A) =\delta(M_A), \tag{2.1} \]

where \(\underline d\) is lower natural density and \(\delta\) is logarithmic density. [b: Davenport–Erdős]

Consequently,

\[ d(M_A)=1 \quad\Longleftrightarrow\quad \sup_{\substack{F\subseteq A\\F\ {\rm finite}}}d(M_F)=1. \tag{2.2} \]

Indeed, if the supremum is \(1\), (2.1) gives lower density \(1\), hence natural density \(1\); the reverse implication is immediate from (2.1). [b: Davenport–Erdős]

For finite \(F\), inclusion–exclusion gives the completely explicit expression

\[ d(M_F)= \sum_{\varnothing\ne S\subseteq F} \frac{(-1)^{|S|+1}}{\operatorname{lcm}(S)}. \tag{2.3} \]

[a] Each simultaneous divisibility event has density

\(1/\operatorname{lcm}(S)\), proving (2.3).

Combining (2.2) and (2.3) gives a literal necessary-and-sufficient condition:

\[ \boxed{\quad \sup_{\substack{F\subseteq A\\F\ {\rm finite}}} \ \sum_{\varnothing\ne S\subseteq F} \frac{(-1)^{|S|+1}}{\operatorname{lcm}(S)} =1.\quad} \tag{2.4} \]

[b: Davenport–Erdős, with elementary finite inclusion–exclusion]

This is the exact clean reduction requested in output category (3), but it is not a new resolution: the live 2026 discussion already identified it as the classical finite-approximation theorem, and the site remains OPEN. The unresolved intent is a usable structural condition on \(A\), rather than the limiting restatement (2.4).

3. Exact finite squarefree-hypergraph form

This section records a useful from-scratch form of (2.3).

Let \(F\) be a finite set of squarefree integers and let \(P\) be the finite set of primes dividing them. Associate to each \(a\in F\) the hyperedge

\[ E_a=\{p\in P:p\mid a\}. \]

Call \(I\subseteq P\) independent when it contains no whole edge \(E_a\).

For a uniformly random residue modulo \(\prod_{p\in P}p\), the events \(p\mid n\) are independent and have probabilities \(1/p\), by the Chinese remainder theorem. The residue avoids \(M_F\) exactly when its selected prime set is independent. Therefore

\[ \boxed{ 1-d(M_F) =\sum_{\substack{I\subseteq P\\I\ {\rm independent}}} \prod_{p\in I}\frac1p \prod_{p\in P\setminus I}\left(1-\frac1p\right) =\prod_{p\in P}\left(1-\frac1p\right) \sum_{\substack{I\subseteq P\\I\ {\rm independent}}} \prod_{p\in I}\frac1{p-1}. } \tag{3.1} \]

[a]

For squarefree semiprimes, this is the weighted independence polynomial of an ordinary graph. For arbitrary squarefree \(A\), (2.1) says that \(A\) is Behrend exactly when the independent-set probability in (3.1) tends to \(0\) along finite exhaustions. [b: Davenport–Erdős]

For general, non-squarefree \(A\), replace the Bernoulli coordinate at \(p\) by an independent valuation \(V_p\) with

\[ \Pr(V_p\ge e)=p^{-e}. \]

Then \(a\mid n\) is the upward orthant

\(\{V_p\ge v_p(a)\ \forall p\}\). The exact remaining structural problem is therefore:

> Characterize when a countable union of these arithmetic upward orthants has full product measure.

[b: the equivalence to density uses Davenport–Erdős; the product-space encoding itself is elementary.]

Ruzsa–Tenenbaum supplies a nontrivial answer for the graph/two-prime-factor case. The located literature does not supply a comparable general criterion for unbounded hyperedge size and arbitrary valuation thresholds.

4. A density-preserving prime blow-up

The following construction makes the obstruction to coarse criteria explicit. I do not claim it is new.

Lemma

Let \(B=\{b_1,\ldots,b_t\}\) be a finite primitive set of integers \(>1\). For each \(i\), let \(P_i\) be an infinite set of primes such that:

1. the \(P_i\) are pairwise disjoint;

2. no prime in any \(P_i\) divides any \(b_j\);

3. \(\sum_{p\in P_i}1/p=\infty\) for every \(i\).

Define

\[ A(B;P_1,\ldots,P_t)= \bigcup_{i=1}^t\{b_ip:p\in P_i\}. \tag{4.1} \]

Then:

\[ d(M_A)=d(M_B),\qquad \sum_{a\in A}\frac1a=\infty. \tag{4.2} \]

Moreover, \(A\) is primitive, and if every \(P_i\) has at least two primes then

\(\gcd(A)=\gcd(B)\). [a, conditional on the displayed hypotheses]

Proof

Certainly \(M_A\subseteq M_B\). Fix \(i\) and a finite \(E\subset P_i\). By CRT, the density of integers divisible by \(b_i\) but by none of the primes in \(E\) is

\[ \frac1{b_i}\prod_{p\in E}\left(1-\frac1p\right). \]

Since \(\sum_{p\in P_i}1/p=\infty\), these products tend to \(0\). Hence the set of multiples of \(b_i\) missed by every \(b_ip\), \(p\in P_i\), has upper density \(0\). There are only \(t\) arms, so \(M_B\setminus M_A\) has density \(0\), proving the first part of (4.2). The reciprocal sum is

\[ \sum_{i=1}^t\frac1{b_i}\sum_{p\in P_i}\frac1p=\infty. \]

If \(b_ip\mid b_jq\), then \(p\mid b_jq\). The avoidance hypothesis gives \(p=q\); disjointness then forces \(i=j\), and primitivity of \(B\) rules out any remaining proper divisibility. Thus \(A\) is primitive. Finally, the gcd inside the \(i\)-th arm is \(b_i\), because \(P_i\) contains two distinct primes, so the gcd of all arms is \(\gcd(B)\). \(\square\)

Disjoint \(P_i\) satisfying the hypotheses exist explicitly: discard the finitely many forbidden primes and distribute the remaining primes cyclically by index. Euler's divergence of the prime reciprocal series, together with Bertrand's postulate to compare the finitely many positions in each block, shows that every class has divergent reciprocal sum. [b: Euler's theorem and Bertrand's postulate]

Thus every density arising from a finite primitive base \(B\) also arises from an infinite primitive sequence with the same gcd and divergent reciprocal sum. [b: the lemma plus Euler/Bertrand for existence]

5. Two contrasting explicit sequences

5.1 A primitive Behrend sequence

Let

\[ C=\{pq:pIt is primitive and has gcd \(1\). [a]

For the first \(m\) primes \(p_1,\ldots,p_m\), let \(C_m\) contain all

\(p_ip_j\), \(i \[ 1-d(M_{C_m}) =Q_m(1+T_m),\quad Q_m=\prod_{i\le m}\left(1-\frac1{p_i}\right),\quad T_m=\sum_{i\le m}\frac1{p_i-1}. \tag{5.2} \]

[a]

Writing \(S_m=\sum_{i\le m}1/p_i\),

\[ Q_m\le e^{-S_m},\qquad T_m =S_m+\sum_{i\le m}\frac1{p_i(p_i-1)} \le S_m+1. \]

Euler's theorem \(S_m\to\infty\) implies

\[ 1-d(M_{C_m})\le e^{-S_m}(S_m+2)\to0. \]

Since \(M_{C_m}\subseteq M_C\), this proves \(d(M_C)=1\). [b: Euler's divergence of \(\sum_p1/p\); all other steps elementary]

Also

\[ \sum_{a\in C}\frac1a =\sum_{p[b: Euler's theorem]

5.2 Same coarse invariants, density \(2/3\)

List the primes \(>3\) as \(r_1=5,r_2=7,\ldots\), and put

\[ P=\{r_1,r_3,r_5,\ldots\},\qquad Q=\{r_2,r_4,r_6,\ldots\}. \]

Euler's theorem and Bertrand's postulate imply

\(\sum_{p\in P}1/p=\sum_{q\in Q}1/q=\infty\). [b]

Now define

\[ D=\{2p:p\in P\}\cup\{3q:q\in Q\}. \tag{5.3} \]

This is the blow-up of \(B=\{2,3\}\). Hence \(D\) is primitive, \(\gcd(D)=1\),

\[ \sum_{d\in D}\frac1d=\infty, \qquad d(M_D)=d(M_{\{2,3\}})=\frac23. \tag{5.4} \]

[b: the elementary blow-up lemma plus Euler/Bertrand]

Therefore the conjunction

\[ \text{“primitive”}+\text{“gcd \(1\)”}+\text{“}\sum_{a\in A}1/a=\infty\text{”} \]

is not sufficient for \(A\) to be Behrend. This is not a counterexample to Erdős's problem; it is a counterexample to a natural coarse candidate criterion. [b]

For \(k\) primes in each arm, put

\[ u_k=\prod_{j=1}^k\left(1-\frac1{r_{2j-1}}\right),\qquad v_k=\prod_{j=1}^k\left(1-\frac1{r_{2j}}\right). \]

Direct CRT gives the exact finite-truncation density

\[ d_k= \frac12(1-u_k)+\frac13(1-v_k) -\frac16(1-u_k)(1-v_k)\longrightarrow\frac23. \tag{5.5} \]

[a]

6. Exact finite computation

The standalone checker is erdos691_wave7g_reverify.py. It uses only the standard library.

For every graph \(G\) on the five prime vertices \(\{2,3,5,7,11\}\), it forms

\[ F_G=\{pq:\{p,q\}\in E(G)\}. \]

Every such \(F_G\) is primitive. The checker independently recomputes \(d(M_{F_G})\) by:

1. generic lcm-aggregated inclusion–exclusion;

2. direct Bernoulli prime-divisibility probability;

3. the weighted independence polynomial (3.1);

4. brute enumeration of one full lcm-period (a divisor of \(2310\), and

\(2310\) when all five primes occur).

All four exact rational answers agree for all \(2^{10}=1024\) graphs. [d]

The exhaustive sharp extrema for a fixed number \(e\) of semiprimes are:

| \(e\) | minimum density | one minimizing family | maximum density | one maximizing family |

|---:|---:|:---|---:|:---|

| 0 | \(0\) | – | \(0\) | – |

| 1 | \(1/77\) | \(7\!\cdot\!11\) | \(1/6\) | \(2\!\cdot\!3\) |

| 2 | \(1/35\) | \(5\!\cdot\!11,7\!\cdot\!11\) | \(7/30\) | \(2\!\cdot\!3,2\!\cdot\!5\) |

| 3 | \(19/385\) | \(3\!\cdot\!11,5\!\cdot\!11,7\!\cdot\!11\) | \(19/70\) | \(2\!\cdot\!3,2\!\cdot\!5,2\!\cdot\!7\) |

| 4 | \(27/385\) | \(2\!\cdot\!11,3\!\cdot\!11,5\!\cdot\!11,7\!\cdot\!11\) | \(32/105\) | \(2\!\cdot\!3,2\!\cdot\!5,2\!\cdot\!7,3\!\cdot\!5\) |

| 5 | \(37/385\) | \(2\!\cdot\!11,3\!\cdot\!11,5\!\cdot\!7,5\!\cdot\!11,7\!\cdot\!11\) | \(376/1155\) | \(2\!\cdot\!3,2\!\cdot\!5,2\!\cdot\!7,2\!\cdot\!11,3\!\cdot\!5\) |

| 6 | \(151/1155\) | \(2\!\cdot\!11,3\!\cdot\!7,3\!\cdot\!11,5\!\cdot\!7,5\!\cdot\!11,7\!\cdot\!11\) | \(398/1155\) | \(2\!\cdot\!3,2\!\cdot\!5,2\!\cdot\!7,2\!\cdot\!11,3\!\cdot\!5,3\!\cdot\!7\) |

| 7 | \(191/1155\) | \(2\!\cdot\!7,2\!\cdot\!11,3\!\cdot\!7,3\!\cdot\!11,5\!\cdot\!7,5\!\cdot\!11,7\!\cdot\!11\) | \(82/231\) | \(2\!\cdot\!3,2\!\cdot\!5,2\!\cdot\!7,2\!\cdot\!11,3\!\cdot\!5,3\!\cdot\!7,3\!\cdot\!11\) |

| 8 | \(251/1155\) | \(2\!\cdot\!7,2\!\cdot\!11,3\!\cdot\!5,3\!\cdot\!7,3\!\cdot\!11,5\!\cdot\!7,5\!\cdot\!11,7\!\cdot\!11\) | \(421/1155\) | \(2\!\cdot\!3,2\!\cdot\!5,2\!\cdot\!7,2\!\cdot\!11,3\!\cdot\!5,3\!\cdot\!7,3\!\cdot\!11,5\!\cdot\!7\) |

| 9 | \(311/1155\) | all except \(2\!\cdot\!3\) | \(61/165\) | all except \(7\!\cdot\!11\) |

| 10 | \(431/1155\) | all ten | \(431/1155\) | all ten |

This table is [d], not an asymptotic theorem.

Additional exact/rational cross-checks from the same run:

| family | truncation | exact/decimal density |

|:---|---:|---:|

| complete semiprimes \(C_m\) | \(m=2\) primes | \(1/6\) |

| | \(m=3\) | \(4/15\) |

| | \(m=5\) | \(431/1155\) |

| | \(m=20\) | \(0.550987936765\) |

| | \(m=100\) | \(0.655717556492\) |

| | \(m=200\) | \(0.685384651038\) |

| two-star \(D_k\) | \(k=1\) per arm | \(1/7\) |

| | \(k=2\) | \(590/3003\) |

| | \(k=20\) | \(0.336534468038\) |

| | \(k=100\) | \(0.389035410278\) |

These decimal entries were computed internally as exact fractions.Fraction values before formatting. [d]

Run:

python3 runs/erdos691_wave7g_reverify.py

Observed on this VM: exit code \(0\), wall time \(1.5\)–\(1.6\) seconds, final line

VERIFIED: 1024/1024 graph cases agree under four exact methods; all finite family cross-checks passed.

7. Precise wall

Why finite computation cannot decide arbitrary input

Let \(F\) be any finite set not containing \(1\).

  • A Behrend extension is obtained by adjoining all sufficiently large primes. [b: divergence of prime reciprocals plus the pairwise-coprime criterion]
  • A non-Behrend extension is obtained by adjoining infinitely many numbers already divisible by a fixed element of \(F\); this does not change \(M_F\). If \(F=\varnothing\), use all even integers. [a]
  • A finite \(F\) itself has \(d(M_F)<1\), because the residue \(1\bmod\operatorname{lcm}(F)\) misses every member. [a]

Thus every nontrivial finite prefix is compatible with both answers. No amount of exact finite-prefix enumeration supplies the missing uniform tail statement. [a]

Exact missing lemma for this route

After the reduction in §3, what is needed is a structural zero-probability criterion for the weighted independent sets of a countable arithmetic hypergraph (and, with prime powers, for upward orthants in independent geometric valuation coordinates). Ruzsa–Tenenbaum proves such a criterion for two-prime-factor edges. A general version handling edge size \(3\), unbounded edge size, and valuation thresholds is the missing lemma for this approach. This literature search did not locate such a theorem.

The exact lcm dynamic program can have \(2^m\) distinct states for \(m\) input divisors, and exhaustive graph enumeration on \(r\) prime vertices has \(2^{\binom r2}\) cases. [a: worst-case state/case counts] Moving the present graph census from \(r=5\) (1024 graphs) to \(r=8\) (268,435,456 graphs) would require roughly \(10^2\)–\(10^3\) core-hours even with a compact optimized graph engine, and much more if the independent period check were retained. [d: engineering estimate] Such a census would still not provide uniform tail control and therefore would not resolve the problem.

8. Bottom line

  • [b] The classical Davenport–Erdős theorem plus (2.3) gives an exact but non-structural necessary-and-sufficient condition.
  • [a/b] The prime-hypergraph/product-measure formulation isolates the structural issue exactly.
  • [a/b] The density-preserving blow-up produces explicit infinite primitive, gcd-\(1\), reciprocal-divergent non-Behrend sequences; the displayed example has density exactly \(2/3\).
  • [d] The standalone checker verifies a sharp complete five-prime semiprime table by four independent exact methods.
  • No general structural characterization is proved here, so the live problem is not claimed solved.

PARTIAL: Classical finite-lcm reduction verified; a density-preserving blow-up gives a primitive gcd-1 reciprocal-divergent example of exact density 2/3, and all 1024 five-prime semiprime families were exhaustively checked, but the general weighted-hypergraph tail criterion remains missing.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger