Erdős Problem #168
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: additive combinatorics.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Let \(F(N)\) be the greatest cardinality of a subset \(A\subseteq\{1,\ldots,N\}\) containing no full triple of the form
for any positive integer \(n\). Erdős and Graham asked for the limiting maximum density
and, in particular, whether \(\delta\) is irrational. The existence of the limit, its numerical value and its irrationality are three distinct questions.
A small example
For \(N=3\), the only forbidden triple is \(\{1,2,3\}\), so a maximal admissible set has two elements: \(F(3)=2\). For \(N=6\), both \(\{1,2,3\}\) and \(\{2,4,6\}\) are forbidden, and one can choose four or more positions without creating a complete triple; the exact maximum should be computed rather than inferred from density.
A useful structural observation is that each positive integer has a unique factorization \(m\,2^a3^b\) with \(\gcd(m,6)=1\). A forbidden triple \(\{n,2n,3n\}\) remains in the same \(m\) component, so the problem decomposes into independent finite optimization problems on lattices of powers of two and three.
What is known
The existence of \(\delta\) was proved by Graham, Spencer and Witsenhausen (1977). They express it as a convergent series involving the 3-smooth numbers \(d_1<d_2<\cdots\) (numbers with prime factors only two and three) and finite extremal counts \(f(k)\):
This formula makes the constant computable. In the maintained #168 discussion, Sean Eberhard gives a corrected high-precision numerical estimate
which agrees with the site's summary \(0.800965\ldots\). Irrationality remains OPEN. A long nonrepeating-looking decimal expansion is no proof of irrationality. The maintained catalogue calls the umbrella problem open because that arithmetic characterization is not known.
There is a further source-fidelity warning: the discussion reports that an older proposed finite smooth-number equality fails at \(k=45\). An implementer must recompute the true finite optimum rather than reuse an unverified shortcut.
GCL's current state
The pinned and maintained catalogue classify #168 OPEN; issue #1437. The statement separates the already proved limit and numerical estimate from the unproved irrationality. The original 1977 proof and the full precision computation have not been independently reproduced.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded successor decomposes all integers up to \(N=100\) by their unique \(m\) coprime to six, enumerates the 3-smooth subproblem, and computes exact \(F(N)\) with a second whole-interval integer-programming formulation. Acceptance: both formulations agree for every tested cutoff, the \(N=3\) fixture yields two, and contributions are explicitly linked to each smooth-number index. Stop after exact finite checks and rigorous series-tail bounds; do not claim an irrationality proof.
Sources and claim boundaries
- Erdős #168, Graham–Spencer–Witsenhausen (1977) series.
- Eberhard's corrected precision discussion, computational provenance and reported old shortcut error.
- GCL source issue #1437.
No irrationality theorem, independently certified decimal precision or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1437 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.