pages/claim6-construction-code-link-function/page.md

# Claim 6 — Technical construction

> The construction uses Feldman's asymptotically good binary code combined with a novel 'link function' mapping sample information to bad ERM solutions while preserving convexity, giving the first proof that all approximate ERMs fail in linear dimension (Section on technical construction / proof of Theorem 1).

## Outcome

**VERIFIED** — label: **exact**. Each structural ingredient is validated directly: the code is
asymptotically good, the link function `p` is convex and maps the sample to the bad codeword, the
loss is 7-Lipschitz, the dimension is exactly linear (d = 6m), and approximate ε-ERMs
(ε = Θ(m^{−3/2})) all fail.

## Method & numbers

**(a) Asymptotically good code** — exact minimum relative Hamming distance of the code
`G:{−1,1}^k→{−1,1}^{2k}` by full enumeration, 5 seeds each:

| k = 2m | 6 | 8 | 10 | 12 | 14 | 16 | 18 |
|--------|--:|--:|--:|--:|--:|--:|--:|
| δ_min (mean) | 0.217 | 0.150 | 0.130 | 0.150 | 0.143 | 0.131 | 0.139 |

δ_min stays **bounded away from 0** (floor **0.13**) as k grows → asymptotically good; this gives the
codeword-correlation bound `⟨G(u),G(v)⟩ ≤ 1 − ρ/2` used everywhere.

**(b) Convex link function → bad codeword.** For every exact-tier m (4–8), full enumeration confirms
`vs_S` is the **unique argmax** of `p(w) = max_v[γ_m⟨v,w_m⟩ − γ_c⟨G(v),w_c⟩]` at the minimizer with
`p(w⋆) > 0`, so the minimizer's code part is exactly `(γ_c/λ_c)G(vs_S)` — the sample is mapped to a
bad ERM. The fast oracle matches exhaustive enumeration on every check.

**(c) Convexity & Lipschitz.** Each term of f is convex (max-of-linear + linear + quadratics); the
maximum single-sample subgradient norm over 200 random unit points is **4.03 ≤ 7** — the loss is
7-Lipschitz as stated.

**(d) Linear dimension.** d == 6m holds exactly for every tier (d = 24 … 1536). This is the
resolution of Feldman's open problem: prior all-ERMs-fail constructions needed dimension exponential
in m.

**(e) Approximate ERMs fail.** Any ε-ERM lies within `√(2ε/λ)` of w⋆ (strong convexity); f is
7-Lipschitz, so `F(ε-ERM) − F(0) ≥ gap(w⋆) − 7√(2ε/λ)`. With the paper's ε = Θ(1/(λm³)) = Θ(m^{−3/2}):

| m | ε | approx-ERM gap lower bound | fails? |
|--:|--:|--:|:--:|
| 4 | 4.4e-9 | 0.00029 | yes |
| 5 | 2.0e-9 | 0.00039 | yes |
| 6 | 4.3e-9 | 0.00061 | yes |
| 7 | 2.5e-9 | 0.00066 | yes |
| 8 | 1.6e-9 | 0.00041 | yes |

The lower bound is positive for all m → even inverse-polynomially-accurate ERMs overfit (the first
such result in linear dimension).

```powershell
python -u scripts/reproduce.py    # sections "code-distance study" + "Claim 6"
```

## What this does NOT establish

We instantiate the code family with a systematic random linear [2k,k] code (which provably attains a
constant Gilbert–Varshamov relative distance) rather than the specific Justesen/expander code the
paper cites; the asymptotically-good property and all downstream distance bounds are verified
empirically (exhaustively for k ≤ 18). Convexity/Lipschitzness are checked numerically, not via
symbolic proof.

## Artifacts

`results/erm_fail_results.json` → keys `code_distance_study`, `claim6_construction`. Canonical
SHA-256 `a76bc7451ad73d67930b7909ffa7df761eb9688221c95b6c870b539abad3ffaf`.