Largest LCM-triple-free subset of $\{1,\ldots,N\}$: estimate $f(N)$; is $f(N)=o(N)$? (Erdős #536)
Statement
For a positive integer $N$, let $f(N)$ be the largest size of a set $A\subseteq\{1,\ldots,N\}$ that contains no three DISTINCT elements $a,b,c\in A$ with $$[a,b]=[b,c]=[a,c],$$ where $[x,y]$ denotes the least common multiple of $x$ and $y$. Estimate $f(N)$; in particular, is $f(N)=o(N)$?
Acceptance. FULLY RESOLVES: settle whether $f(N)=o(N)$ — either a proof (machine-checkable preferred, otherwise a full written proof) that $f(N)=o(N)$, or a construction, with proof, of LCM-triple-free sets of size $\geq cN$ for a fixed constant $c>0$ and all large $N$. ADVANCES (each independently checkable): (a) replace the upper-bound constant $221/225$ stated in the background by a strictly smaller explicit constant, with proof; (b) improve the Abbott–Gardner lower bound; or (c) compute $f(N)$ EXACTLY for a range of $N$ beyond what is currently tabulated, each value accompanied by a reproducible optimality certificate (an extremal set together with a machine-checkable upper-bound proof, e.g. from an ILP/SAT solver). Deliver the proof, the explicit extremal construction, or the search code plus certified values of $f(N)$.
Background
Asked by Erdős [Er64, p.646], [Er70, p.124], [Er73, p.124], and again at the 1991 West Coast Number Theory problem session; listed as open on erdosproblems.com/536 (fetched 2026-07-21, status 'open'). The three-element condition is the subtle one: the analogous quantity forbidding FOUR elements with a common pairwise least common multiple is $\gg N$ (Erdős [Er62], with a proof in [Er70]), so a positive-density family survives in that relaxation. For the three-element problem the known frontier is a still-open gap. Lower bound: Abbott and Gardner [AbGa67] proved $$f(N)\geq (1-o(1))(\log\log N)\frac{N}{\log N}.$$ In the site comments, Weisenberg sketches, for some $\omega(N)\to\infty$, the two-sided estimate $$(\log\log N)^{\omega(N)}\frac{N}{\log N}\ll f(N)\leq\left(\frac{221}{225}+o(1)\right)N;$$ crucially the best known upper bound is still of order $N$, so whether $f(N)=o(N)$ remains genuinely open. Related problems: Erdős #535, #537, #856, and the combinatorial variant #857. The attacker's tool: exact computation of $f(N)$ for small $N$ as a maximum independent set in the $3$-uniform 'equal-pairwise-LCM triple' hypergraph on $\{1,\ldots,N\}$ (ILP / SAT / branch-and-bound with an optimality certificate), plus explicit constructions to push the $221/225$ upper-bound constant downward.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #536 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.