The upper half of the weighted data-selection gap: F_(w)(d,n)=1+(2d-n)/d for 2n ≥ 3d

The lower-bound witness D_(d,2) = (eⱼ, 3), (-eⱼ, -1)_(j=1..d) for weighted data selection with the min-norm ERM: over every selection pattern of the d coordinates using at most n of the 2d points, the separated cost (0 if both points of a coordinate are selected, 1 if exactly one, c² = 4 if neither, the last by the min-norm tie rule) has minimum exactly 2d - n for every d <= n <= 2d, and the minimum is attained; hence L*_D(n;A*) = 1 + (2d-n)/d and F_w(d,n) >= 1 + (2d-n)/d, in particular F_w(4,6) >= 3/2. General in d, n and in the squared shift m = c² >= 2; kernel-clean, no native axiom

The branch recursion of Theorem A closes on the upper half, in general dimension: if P: N -> N -> Q satisfies P m 0 = 0 (exact recovery at budget 2m) and, for 1 <= j <= d-1, P d j <= max j/d (rigidity), P (d-1) (j-1) (anchor), P (d-c+1) (j+2-c) for 3 <= c <= d (circuit), then P d j <= j/d whenever 2j <= d. In the original coordinates (j = 2d - n): Psi_d(n) <= (2d-n)/d for every n >= ceil(3d/2), which is the upper-bound half of Theorem A – F_w(d,n) = 1 + (2d-n)/d on 2n >= 3d – modulo the geometric branch lemmas. Kernel-clean, no native_decide, no bound on d. With the circuit inequality (j+2-c)d <= j(d-c+1) proved in general from 2j <= d, and its failure at (d,j,c) = (3,2,3) and (4,3,3), i.e. at F_w(3,4) and F_w(4,5); and with the rigidity branch's own numerical core proved rather than assumed – among d line energies some k of them carry at most the fraction k/d of the total (no nonnegativity needed), in the form k = 2d-n with total energy at most 1, together with its tightness on the cross-polytope's uniform energies

The branch recursion U_d(n) – U = 0 for n >= 2d, U_d(n) = max(2d-n)/d, U_(d-1)(n-1), U_(d-c+1)(n-c) for 3 <= c <= d on d < n < 2d – settles exactly the upper half for every d <= 30: U_d(n) = (2d-n)/d when 2n >= 3d (225 cells) and U_d(n) is strictly larger, or unusable, when 2n < 3d (210 cells). The same holds with the volume-sampling base case Uₘ(m) = m deleted, so Theorem A uses no volume sampling and no determinantal point processes. Spot values: U₄(6) = 1/2, U_d(2d-1) = 1/d at d = 3,4,5,8, U₃(4) = 1 > 2/3, U₄(5) = 2 > 1, U₅(7) = 1 > 3/5

Gamma_(d,k) = (d-k)/d whenever 2k >= d, for every d: with d = qₛ s + aₛ, C_(d,s) = ((s-aₛ)/qₛ + aₛ/(qₛ+1))⁻¹ and Gamma_(d,k) = max_(k+1<=s<=d) (s-k) C_(d,s) (the source's eq. (gamma)), every s-term is at most (d-k)/d and s = d attains it. Proved in general (no bound on d, no native_decide) from the exact AM-HM identity d(s(q+1)-a) = s² q(q+1) + a(s-a) and d²(s-k) <= (d-k)s². Consequently the source's conjectured value 1 + Gamma_(d,n-d) equals 1 + (2d-n)/d exactly on the upper half 2n >= 3d, so Theorem A confirms the conjecture there

Theorem A: F_w(d,n) = 1 + (2d-n)/d for every d >= 1 and every ceil(3d/2) <= n <= 2d – the upper half of Question 2 of the COLT 2025 open-problem note of Hanneke, Moran, Shlimovich and Yehudayoff (PMLR 291:6225-6229). Proof: the lower bound is the cross-polytope dataset D_(d,2) (row DF1); the upper bound is a case split on a minimum-cardinality positively spanning subset B of the nonzero whitened gradients – exact recovery when |B| <= n, a circuit interface Psi_d(n) <= E(P) Psi_(d-c+1)(n-c) when a positive circuit of size 3 <= c <= d exists, a penalty-limit anchor Psi_d(n) <= Psi_(d-1)(n-1) when some point has zero gradient and nonzero feature, and rigidity Psi_d(n) <= (2d-n)/d when |B| = 2d – closed by the induction of row DF2. Uses neither Steinitz's interior theorem nor volume sampling / determinantal point processes

F_w(4,6) = 3/2 – the exact value at the cell arXiv:2608.28007 names in print as 'the smallest open cell'. The lower bound is row DF1 (kernel-checked); the upper bound is the instance j = 2, d = 4 of Theorem A (row DF5), where the rectangle branch that makes F_w(4,5) hard evaporates because a positively spanning set of six gradients in R⁴ carries a strictly positive vanishing relation and its features span, so budget 6 recovers the optimum exactly

The numerical audit of the branch structure at (d,n) = (4,6), in exact rational arithmetic: an independently validated exact solver for the infimum over strictly convex selections reproduces the source's block-model minimax value Phi(r,k) on 49 (r,k) cells with 0 mismatches; the cross-polytope gives 1 + (2d-n)/d in every computable cell for d <= 4; all three of the source's published obstruction instances have achievable excess 0 at budget 6; branch (C) holds with equality on 48 circuit/block cells and branch (E2) holds on 63 axis cells with its own selection exactly optimal in all 63; and a targeted hard-branch refutation sweep over 2126 systems with |B| in 6,7,8 (plus 59 random controls) finds none exceeding excess 1/2 (worst: 0 at |B| = 6, 5/14 at |B| = 7, 5/11 at |B| = 8)