The maximal density of sets avoiding {n,2n,3n}: evaluate the limit and decide irrationality (Erdős #168)
Statement
Let $F(N)$ be the size of the largest subset $A\subseteq\{1,\ldots,N\}$ which does not contain any set of the form $\{n,2n,3n\}$ — that is, there is no integer $n$ with $n$, $2n$, and $3n$ all in $A$. What is $$\lim_{N\to\infty}\frac{F(N)}{N}?$$ Is this limit irrational?
Acceptance. FULLY RESOLVES: a proof that the constant $\lim_{N\to\infty}F(N)/N$ (equal to the GSW series described in the background) is irrational, or a proof that it is rational together with its exact value; a proven closed-form evaluation of the limit also fully resolves the 'what is the limit' half. Machine-checkable proof (Lean 4, building on the formalised statement) preferred, else a complete written proof. ADVANCES: (a) a certified high-precision computation of the constant strictly extending the digits recorded in the background/OEIS A386439, with reproducible code and a rigorous error bound derived from the tail of the GSW series; (b) a substantial certified extension of the auxiliary sequences A057561 and A004059 (equivalently, of the index set $K$), with exhaustive-search code; (c) a proven arithmetic constraint on the constant — e.g. an irrationality measure statement, or a certified continued-fraction computation proving that if the constant is rational its denominator exceeds an explicit large bound; (d) a proven structural theorem about the index set $K$ (its density, or a characterisation of when $f(k)>f(k-1)$). Deliver the proof file, or the code plus certified digits/sequence terms.
Background
Asked by Erdős and Graham [ErGr79, ErGr80]; listed as open on erdosproblems.com/168 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). The limit is known to exist: Graham, Spencer, and Witsenhausen [GSW77] proved existence and gave the formula $$\frac{1}{3}\sum_{k\in K}\frac{1}{d_k},$$ where $d_1<d_2<\cdots$ are the 3-smooth numbers (OEIS A003586) and $K$ is the set of indices $k$ with $f(k)>f(k-1)$, $f(k)$ being the size of the largest $\{n,2n,3n\}$-free subset of $\{d_1,\ldots,d_k\}$. Using this formula, Eberhard computed the value as $0.800965\cdots$ (decimal expansion: OEIS A386439); Bloom's page notes the limit can also be estimated by elementary arguments. So the 'what is the limit' half asks for a closed form or structural description beyond the GSW series, and the sharp open question is arithmetic: is the constant irrational? The auxiliary objects are computable: $f$ is OEIS A057561, with companion hitting-set sequence A094708 and index sequence A004059. Analogous questions for the density and upper density of infinite $\{n,2n,3n\}$-free sets are also open. The statement is formalised in Lean in google-deepmind/formal-conjectures. The attacker's tool: dynamic programming over the lattice of 3-smooth numbers to certify many more digits of the constant (with rigorous tail bounds from the GSW series), extension of A057561/A004059, and — for irrationality — the explicit series structure, the natural handle for irrationality arguments.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #168 (T. F. Bloom) | website |
| REF-02 | OEIS A386439 — decimal expansion of the maximal density of a set of positive integers free of subsets {n, 2n, 3n} | website |
| REF-03 | OEIS A057561 — size of the largest {x,2x,3x}-free subset of the first n 3-smooth numbers | website |
| REF-04 | OEIS A004059 — position of first n in A057561 | website |
| REF-05 | Lean formalisation of Erdős #168 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.