Erdős #708 — linear bound for divisor-product covering constant g(n)

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 \mid \prod_{b\in B}b.\] Is it true that $g(n)\leq(2+o(1))n$? Or perhaps even $g(n)\leq 2n$? (erdosproblems.com/708, direct fetch.)

Facts

- Prize \$100 ("100 dollars or 1000 rupees, whichever is more" — Erdős [Er92c]; in 1992, 1000 rupees ≈ \$38.60); status open, falsifiability not-finite — the site states explicitly "This is open, and cannot be resolved with a finite computation" (erdosproblems.com/708). - Falsifiable: no — this is an asymptotic-for-all-$n$ claim; no finite computation settles it. - Origin: Erdős and Surányi, "Bemerkungen zu einer Aufgabe eines mathematischen Wettbewerbs", Mat. Lapok 10 (1959), 39-48 [ErSu59] (bib fetched from erdosproblems.com/bibs/ErSu59); re-posed with the prize in Erdős, "Some of my forgotten problems in number theory", Hardy-Ramanujan J. (1992), 34-50 [Er92c]; also in Erdős, "Some Unsolved problems in Geometry, Number Theory and Combinatorics", Eureka (1992), 44-48 [Er92e] (both bibs fetched). - Known results / best bounds (erdosproblems.com/708, direct fetch — this is the entirety of what's recorded): Erdős–Surányi proved $g(n)\geq(2-o(1))n$ and the exact small case $g(3)=4$. Their lower-bound construction: $A=\{p_ip_j : i\neq j\}$ for primes $p_1<\cdots<p_\ell$ with $2p_1^2>p_\ell^2$ (so $n=\binom{\ell}{2}$) — each prime then needs high-enough valuation in $B$ that close to two elements of $I$ per element of $A$ are forced. No nontrivial upper bound of any kind for general $n$ is recorded on the page or found anywhere in my search — not even a weak $O(n\log n)$-type bound. This makes #708 colder than its solved sibling #650 (below), where a factor-of-2 gap (not "no bound at all") was the starting point. - Historical note: Gallai was first to consider this type of problem, observing $g(2)=2$, $g(3)\geq4$ (erdosproblems.com/708). - Companion question in the same 1959 paper: smallest $c_n\geq1$ such that any interval of length $c_n\max(A)$ contains $B$, $\lvert B\rvert=n$, with $\prod_A a\mid\prod_B b$; Erdős–Surányi got only $c_2=1$, $c_3=\sqrt2$, with no general bounds (erdosproblems.com/708). - Related problems: erdos/709, erdos/711, erdos/650 — confirmed (erdosproblems.com/search_bib/ErSu59, direct fetch) to be the *only* four problems on the site citing [ErSu59]; they form a tight "divisor/multiple covering-interval" family from the same 1959 Erdős–Surányi paper, and #708's own page cross-links "See also [709]".

Literature state

Not resolved, and essentially untouched. erdosproblems.com/forum/discuss/708 (direct fetch) shows zero comments and the status widget records "There are no solutions, partial or complete, claimed in the comments." My independent search (arXiv, Google Scholar via WebSearch, OpenAlex-style queries, GitHub) found no paper citing Erdős–Surányi [ErSu59] in connection with $g(n)$ itself, and no DeepMind formal-conjectures Lean stub exists (FormalConjectures/ErdosProblems/708.lean → HTTP 404 on raw.githubusercontent.com, checked directly), i.e. #708 has not even been formalized as a statement.

The picture is very different for its three siblings, all sharing the same [ErSu59] origin, all touched in 2026: - **erdos/650 is FULLY SOLVED. $f(m)$ (largest guaranteed number of disjoint divisor-pairs $(a,b)$, $a\in A$, $b$ in an interval of length $2\max(A)$) is now known exactly: $f(m)=\min(m,\lceil2\sqrt m\rceil)$ — van Doorn, Li, Tang, "Optimal bounds for an Erdős problem on matching integers to distinct multiples", arXiv:2603.28636 (2026). Erdős–Surányi [ErSu59] had $f(m)\geq\sqrt m$; Erdős–Selfridge [Er78],[Er86c] had $f(m^2)\leq2m$ i.e. $f(m)\leq2\lceil\sqrt m\rceil$ — a factor-2 gap that stood ~65 years until this 2026 paper closed it exactly. The proof was AI-assisted: "the proof strategy was first proposed by ChatGPT [GPT-5.4 Pro], and the detailed argument was subsequently made fully rigorous and formally verified in Lean by Aristotle" (arXiv:2603.28636 abstract, PDF read directly); the public discussion trail is logged on erdosproblems.com/forum/thread/650. - erdos/709 is open but improved.** Erdős–Surányi proved $(\log n)^c\ll f(n)\ll n^{1/2}$ for the "distinct-representatives" version (interval of length $f(n)\max(A)$ must contain *distinct* $x_1,\ldots,x_n$ with $a_i\mid x_i$); the lower bound was improved to $\frac{\log n}{\log\log n}\ll f(n)$ using van Doorn's result on #711 [vD26] (erdosproblems.com/709, direct fetch). - **erdos/711 is partially resolved.** Erdős–Pomerance [ErPo80] (1980) conjectured $\max_m f(n,m)\leq n^{1+o(1)}$ and $\max_m(f(n,m)-f(n,n))\to\infty$; van Doorn, "On the length of an interval that contains distinct multiples of the first $n$ positive integers", arXiv:2601.16972 / Integers (2026) #A7 (metadata fetched directly from arxiv.org/abs/2601.16972) proved the second conjecture, showing $\max_m(f(n,m)-f(n,n))\gg\frac{\log n}{\log\log n}\,n$. The first conjecture ($n^{1+o(1)}$ bound) remains open.

So the family has real 2026 momentum (van Doorn, Li, Tang; GPT-5.4 Pro; Aristotle) on the *matching/SDR* variants (#650, #709, #711), but #708's aggregate "$\prod A\mid\prod B$" variant has received none of it — it is not a bipartite-matching statement in the same direct sense (see Attack surface).

Attack surface

- Mode: derivation+formalization primary (the literature search above is itself the literature-resolution pass, and it came up empty — genuinely open with no known partial results to recombine). - Concrete first experiment: reformulate $\prod_{a\in A}a\mid\prod_{b\in B}b$ prime-by-prime: for every prime $p$, $\sum_{a\in A}v_p(a)\leq\sum_{b\in B}v_p(b)$, where $v_p$ is $p$-adic valuation. This turns #708 into a transportation/flow-feasibility problem (supply = valuation profile of $A$, capacity = valuation profile of each candidate $b\in I$) rather than a 1-1 bipartite matching — i.e. Hoffman's circulation theorem (the natural flow-generalization of Hall's/König–Ore's theorem, the exact tool that gave the #650 lower bound per arXiv:2603.28636 §4, Lemma 2.3) is the structurally-correct next tool to try, but this reformulation is not present in any source I found — it is a derivation hypothesis, not a verified result. A concrete runnable step: implement the flow LP for small $n$ (say $n\leq 8$) over the Erdős–Surányi $p_ip_j$ extremal family and numerically test whether the flow-feasibility bound matches $2n$ or exceeds it, to sanity-check whether "$g(n)\leq2n$" (the strong form) is even numerically plausible before attempting a proof. - Oracle: for any fixed finite $n$ and finite search bound on $\max(A)$, $g(n)$-candidates and counterexamples to a proposed closed-form bound are mechanically checkable (prime-factorize $A$ and every candidate $B\subseteq I$, compare valuation sums) — but this only calibrates small cases, since the actual \$100 question is an asymptotic-for-all-$n$ statement flagged explicitly by the site as not finite-computation-resolvable. - Feasibility: honestly low-to-medium in the near term. Unlike its sibling #650 (which had a standing factor-2 gap and a clean bipartite-matching structure that Hall's theorem attacks directly), #708 currently has zero recorded nontrivial upper-bound progress since 1959, and its aggregate-divisibility condition is not literally the matching condition that the 2026 machinery (König–Ore defect formula, Erdős–Selfridge greedy argument) was built for — a genuine reformulation step (the flow/transportation recast above) is needed before that machinery even applies. Given the 2026 momentum on the rest of the [ErSu59] family (van Doorn/Li/Tang + GPT-5.4 Pro + Aristotle), #708 is a plausible next target for the same team/workflow, but it is not a drop-in recombination — real derivation work is required first.

Related

- erdos/709 — sibling from the SAME 1959 paper: $f(n)$, the "distinct-representatives" (SDR) version requiring distinct $x_1,\ldots,x_n$ with $a_i\mid x_i$ rather than an aggregate product-divisibility; $(\log n)^c\ll f(n)\ll n^{1/2}$, lower bound improved via erdos/711's partial resolution (erdosproblems.com/709). Still open. Explicitly cross-linked ("See also [708]"/"See also [709]") on both pages. - erdos/711 — Erdős–Pomerance's $f(n,m)$: interval $(m,m+f(n,m))$ containing distinct $a_1,\ldots,a_n$ with $k\mid a_k$; one of the two ErPo80 conjectures (on $\max_m(f(n,m)-f(n,n))\to\infty$) proved by van Doorn (arXiv:2601.16972 / Integers 2026 #A7); the other ($n^{1+o(1)}$ bound) still open. - erdos/650 — SOLVED sibling (2026): $f(m)=\min(m,\lceil2\sqrt m\rceil)$ exactly, via König–Ore/Hall-defect matching lower bound + explicit $s\times t$-grid divisor construction upper bound; proof strategy by GPT-5.4 Pro, full Lean formalization by Aristotle (van Doorn–Li–Tang, arXiv:2603.28636). Direct template for how the 1959 [ErSu59] gap-closing pattern plays out, though #708's aggregate-product condition is structurally different from the bipartite matching solved there. - concept/hall-defect-matching — König–Ore/Hall deficiency-version maximum-matching-size formula; the exact tool behind the #650 lower bound (arXiv:2603.28636, Lemma 2.3, citing Bondy–Murty Ex. 16.2.8(b)); would need to be replaced by a flow/transportation analogue (Hoffman's circulation theorem) to attack #708's aggregate condition. - concept/prime-valuation-transportation — the reformulation of "$\prod A\mid\prod B$" as a per-prime supply/capacity flow-feasibility problem; the proposed (unverified, not found in any source) structural attack on #708. - concept/multiplicative-lower-bound-construction — Erdős–Surányi's own $A=\{p_ip_j\}$ prime-product construction technique giving the $(2-o(1))n$ lower bound (erdosproblems.com/708) and, in spirit, the extremal constructions used across the whole [ErSu59] family. - concept/ai-assisted-lean-formalization — the GPT-5.4-Pro-proposes/Aristotle-formalizes workflow (arXiv:2603.28636) that fully closed sibling #650 in 2026; the most directly transferable machinery from this solved-analog family, contingent on first finding the right combinatorial reformulation for #708.