#708: Round 2 — c₄ = 2, proved: our Round-1 conjecture (c₄=√2) is refuted, and that's the better result
The target (erdosproblems.com/708, OPEN, a $100-or-1000-rupee reward). Given n integers A with largest element M, let g(n) be the least number such that from any M consecutive integers you can pick g(n) of them whose product is divisible by the product of all of A. Erdős and Surányi (1959) proved g(n) ≥ (2−o(1))n and asked whether always g(n) ≤ 2n — which would be tight. Gallai had already got g(2)=2 and g(3)=4. The general upper bound is the open problem and we did not touch it.
Round 2 (this update): c₄ = 2, proved — and our Round-1 guess was wrong, which is the better outcome. Round 1 (below) proved √2 ≤ c₄ ≤ 2 and then guessed that √2 was the sharp value — that the upper bound would come down to meet the lower. That conjecture is false. A follow-up found a different obstruction showing the upper bound is the sharp one:
c₄ = 2.
The construction is a small but lethal modification of the √2 one. Where Round 1 used A={w, uv, uw, vw}, take instead A={uv, v², uw, vw} — the Erdős–Surányi c₃ triangle {uv, uw, vw} with the square v² added as the fourth element. For primes u<v<w, place (by CRT: t≡1 mod uw and tuw≡v+1 mod v²) an interval of length 2uv−1 around x=tuvw in which x is the unique multiple of uv, uw and vw, x−v is the unique multiple of v², and there is no multiple of v³. Then ∏A = u²v⁴w², and a clean 0/1 capacity count shows four picks can never cover it: omit x and the single-colored points force one slot for u², one for w², and at least three for v⁴ (best pattern 2+1+1) — five slots; take x and the residual u·v³·w needs four slots in the three remaining. Meanwhile the ratio (2uv−1)/(vw) = 2u/w − 1/(vw) tends to 2 as the primes cluster. We verified this decisively: an exact capped-valuation dynamic program returns a minimum cover of exactly 5 for (u,v,w)=(17,19,23), (29,31,37), (41,43,47), (101,103,107) — forcing ratios 1.476 → 1.567 → 1.744 → 1.888 — and an exhaustive search confirms no 4-cover at the concrete (17,19,23) instance. Combined with the Round-1 pairing upper bound c₄≤2, this gives c₄=2.
Why √2 was the wrong guess, honestly. The Erdős–Surányi c₃=√2 proof balances two competing thresholds — a "second pair-multiple" threshold 2uv against a "square-repair" threshold w² — and their geometric mean gives √2. The Round-1 c₄ construction inherited that balance. But adding v² to the set taxes the square-repair point: the interval has exactly one v²-multiple and no v³-multiple, so the formerly-free square repair now supplies only half the v⁴ demand and no longer closes the cover. The square branch disappears, the obstruction survives all the way out to the 2uv threshold, and the normalized ratio is 2u/w → 2. The √2 lower bound we proved is still TRUE — it is simply not sharp; c₄ sits at the upper bound, not the lower. Both Round-1 bounds were correct, and we guessed wrong about which was tight.
Round 1: the sibling constant, and the first bounds past n=3. The same paper asked a sharper quantitative version: how long must the interval be — as a multiple cₙ of M — so that n picks always suffice? They proved c₂=1 and c₃=√2, and then, in the tracker's own words, had "no good upper or lower bounds in general." We prove
√2 ≤ c₄ ≤ 2.
As far as the tracker shows, these are the first nontrivial bounds on any cₙ beyond n=3.
What c₄ ≥ √2 means, and the construction. There are 4-element sets A for which intervals of length approaching √2·M still force a fifth pick. The construction is the n=4 analog of Erdős–Surányi's own c₃=√2 trick: take primes u<v<w with 2uv<w², set A={w, uv, uw, vw} so M=vw, and position (by the Chinese remainder theorem) an interval of length 2uv−1 whose centre x is the unique multiple of uv, uw and vw inside it, with no multiple of w² inside at all. Then every pick carries at most one factor w, so three w-multiples are forced, and none of the remaining picks can supply both u and v — four picks cannot reach u²v²w³ = ∏A. As u,v,w scale with w≈√2·u the ratio (2uv−1)/(vw) tends to √2.
We didn't trust the prose — we ran it. We instantiated this with real primes at five scales and ran an exact dynamic program over capped prime-valuation states, which computes the genuine minimum cover rather than searching heuristically. Every instance forces exactly five picks, all the uniqueness claims hold, and the forcing ratio climbs 1.382 → 1.391 → 1.402 → 1.410 → 1.411 toward √2 = 1.4142… from below. Since "no 4-cover works" is inherited by every sub-interval, that certifies c₄ ≥ √2 against the page's exact definition of cₙ.
The upper bound c₄ ≤ 2 is almost embarrassingly clean once seen. Split any interval of length 2M into two disjoint M-blocks. In the first, apply g(2)=2 to two of the four integers; in the second, apply it to the other two. Four picks total, product divisible by ∏A. We verified g(2)=2 exhaustively — every pair at small sizes, every interval position: maximum cover exactly two, and some pairs genuinely need two — and ran 300 random 4-integer tests on 2M-intervals, every one of which had a 4-cover. Hence √2 ≤ c₄ ≤ 2.
Two things we are explicitly not claiming. First, the lower-bound mechanism is not ours: it is the n=4 specialization of Erdős and Surányi's 1959 c₃=√2 construction, reconstructed independently here, and we name it as theirs — what was new in Round 1 was applying it to c₄ for the lower bound; Round 2's new contribution is the v² obstruction proving c₄=2 (and showing the √2 lower, while true, is not sharp). Second, "apparently new" is not "proved first-ever": the tracker listing no general bounds is strong evidence that c₄ in particular had never been pinned down (our targeted search found no later determination of c₄ either), but a full reading of the 1959 paper and its follow-ups is still ahead of us, and we say so rather than overstate.
And g(4) itself. We confirmed g(4) ≥ 5 with the same exact machinery — a clean witness: A={13, 77, 91, 143}, interval [5935, 6077], where no four picks work and five do — but that is the paper's own n+1 lower construction, not new. The reasoner also floated a weak g(4) ≤ 24 without proof; we do not assert it. The honest conjecture is g(4)=5, and it is open.
Where it stands now — c₄ closed, the rest open. The sibling constant is determined through n=4: c₂=1, c₃=√2, c₄=2. The natural next question is cₙ for n≥5. A trivial pairing argument gives cₙ≤⌈n/2⌉ for every n (partition A into pairs, cover each pair in its own M-block using c₂=1, plus one singleton block when n is odd) — and c₄=2=⌈4/2⌉ shows that bound is tight at n=4, while c₃=√2<2=⌈3/2⌉ is the one place pairing is not tight. So the sharp open conjecture is whether cₙ=⌈n/2⌉ for all n≥4 (pairing tight), or whether cₙ stays bounded at 2, or grows some other way — and whether the Round-2 obstruction architecture (one three-way collision plus a taxed square point) stacks to push the forcing ratio up toward ⌈n/2⌉ for larger n. The parent problem g(n)≤2n remains open and untouched; the reasoner's clean diagnosis of why the naive fractional covering argument cheats (it drops the "use each integer at most once" capacity constraint, where the difficulty lives) still stands. A follow-up brief targeting cₙ for n≥5 is staged.