Largest $A\subseteq[n]$ with no element dividing two others: is $\lim f(n)/n$ irrational? (Erdős #1062)
Statement
For a positive integer $n$, let $f(n)$ be the largest size of a subset $A\subseteq\{1,\ldots,n\}$ that contains no three distinct elements $a,b,c$ with $a\mid b$ and $a\mid c$ (equivalently, no element of $A$ divides two other elements of $A$). Determine the growth of $f(n)$: how large can $f(n)$ be, does $\lim_{n\to\infty}f(n)/n$ exist, and if so is this limit irrational?
Acceptance. FULLY RESOLVES: a proof of the irrationality (or rationality) of the limiting density $c_2=\lim_{n\to\infty}f(n)/n$, or an exact determination of $c_2$ — its existence $f(n)=c_2n+o(n)$ is already established (see background), so the live content is the arithmetic nature/value of $c_2$; proof-shaped, machine-checkable proof preferred, else a full written proof. ADVANCES, each independently checkable: (a) a proven improvement to either side of Lebensold's window — a lower bound strictly above $0.6725$ or an upper bound strictly below $0.6736$, narrowing the rigorous enclosure of $c_2$ (state Lebensold's $0.6725\,n\le f(n)\le 0.6736\,n$ as the bar) — with a proof or a reproducible optimisation certificate (an LP/ILP dual bound, a transfer-matrix computation, or an exhaustively verified extremal family); or (b) a proven partial result toward the irrationality of $c_2$. Deliver the proof or the certified bound together with the program that produces it.
Background
Erdős's problem B24 in Guy's Unsolved Problems in Number Theory [Gu04]; listed as open on erdosproblems.com/1062 (fetched 2026-07-21, status 'open'). The block $A=[m+1,3m+2]$ contains no element dividing two others (if $a\mid b,a\mid c$ with $a<b<c$ then $c\ge 3a>3m+2$), giving $f(n)\ge\lceil\tfrac{2}{3}n\rceil$. Lebensold [Le76] proved that for large $n$ $$0.6725\,n\le f(n)\le 0.6736\,n,$$ so any limiting density $f(n)/n$ lies in $[0.6725,0.6736]$. Davis [Da26] recast the condition as forbidding a subgraph in the directed divisor graph and proved $f(n)=c_2n+o(n)$ for an effectively computable constant $c_2$, so the limit $\lim f(n)/n=c_2$ exists; whether $c_2$ is irrational (the heart of Erdős's question) and its exact value remain open. Related counts are in OEIS A038372, and a Lean-formalised statement is available in the formal-conjectures project. This condition is strictly weaker than being primitive (no element divides another), so $f(n)$ exceeds the maximal-primitive/non-dividing density studied in the neighbouring Erdős #131 (erdosproblems.com/131). Attacker's tool: integer/linear programming and exhaustive search over interval and residue structures to tighten Lebensold's numeric window, plus a renewal/self-similarity analysis of the extremal configurations to sharpen the rigorous enclosure of $c_2$ and probe its irrationality.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1062 (T. F. Bloom) | website |
| REF-02 | D. Davis, Forbidden subgraphs in divisor graphs and an Erdős divisibility problem (2026) | website |
| REF-03 | OEIS A038372 — related divisor-restricted subset sizes | website |
| REF-04 | Lean formalisation of Erdős #1062 (formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.