Erdős–Surányi product divisibility: is $g(n)\leq(2+o(1))n$? (Erdős #708)
Statement
Let $g(n)$ be minimal such that for any $A\subseteq[2,\infty)\cap\mathbb{N}$ with $\lvert A\rvert=n$ and any set $I$ of $\max(A)$ consecutive integers there exists $B\subseteq I$ with $\lvert B\rvert=g(n)$ such that $$\prod_{a\in A} a \;\Big|\; \prod_{b\in B} b.$$ Is it true that $g(n)\leq(2+o(1))n$? Or perhaps even $g(n)\leq 2n$?
Acceptance. FULLY RESOLVES (proof-shaped): a complete rigorous proof — a Lean/Coq formalisation preferred, otherwise a full written proof — that $g(n)\leq(2+o(1))n$ (or the sharper $g(n)\leq 2n$), or a disproof exhibiting sequences $A$ that force $g(n)$ larger; equivalently, an asymptotic formula for $g(n)$ with proof. ADVANCES: (a) determine $g(n)$ exactly for some $n$ beyond the current record (only $g(2)=2$ and $g(3)=4$ are known), with a machine-checkable certificate of both the extremal $A$ and the matching upper bound; (b) improve the lower bound $g(n)\geq(2-o(1))n$ stated in the background via a better construction, with proof; or (c) prove any upper bound of the form $g(n)\leq Cn$ for an explicit constant $C$, with proof (no linear upper bound is currently stated). Deliver the proof, the certified exact values plus search code, or the improved construction.
Background
A problem of Erdős and Surányi [ErSu59], listed as open on erdosproblems.com/708 (fetched 2026-07-21, status 'open'). They proved $g(n)\geq(2-o(1))n$ and $g(3)=4$. Their lower-bound construction takes $A=\{p_ip_j:i\neq j\}$ for a set of primes $p_1<\cdots<p_\ell$ with $2p_1^2>p_\ell^2$. Gallai was the first to consider problems of this type, observing $g(2)=2$ and $g(3)\geq 4$. In [Er92c] Erdős offered '$100 or 1000 rupees', whichever is greater (about $38.60 in 1992), for a proof or disproof; see also [Er92e]. No OEIS sequence is yet recorded for $g(n)$. Attacker's tool: exhaustive / heuristic search over prime-product sets $A$ to sharpen the lower-bound construction and to compute exact values $g(4),g(5),\ldots$ (seeding a new integer sequence), combined with an extremal or greedy argument for matching upper bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #708 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.