FINDING: κ and undirected coding gaps (oblivious padded multiplier, AFKL with a gap, BH/BGS exponent)

[philippeVV]

Status (2026-10-16 UTC, rev 5; updated, see the correction comment): theory note with no κ claim; author-checked, not independently reviewed.
Question: how does κ relate to undirected network-coding gaps, now that the conjecture is refuted?
Result:

• For oblivious machines, κ ≤ the achievable coding-gap exponent.
• Upstream's padded multiplier is oblivious, so today's κ already gives a gap family with exponent ≥ 0.00167. Correction: with a renormalised starting dual, the best all-N guarantee from the Braverman–He seed is 0.0056 (0.0064 with minimal leaves), so today's κ is 0.26–0.30× of it. The earlier 0.66–0.87× used BGS's unrenormalised α-dual.

Artifact: research/coding-gap-exponent @ 93bd6537
Next: review of Theorem A; whether mixed tensoring fills BGS's size gaps; ZLL's ρ₀.
Claim: none open.

1. Theorem A (AFKL with a gap). In AFKL's multiplication theorem, the network-coding conjecture is used once, as "flow rate = coding rate". Replacing it with flow ≥ coding/γ(N) gives the following for every fan-in/fan-out-c circuit with s wires that computes the n-bit shift:

s ≥ n·log_{2c} n / (4γ(s))

• The far-pair step does not depend on γ.
• The supervisor appears only in AFKL Thm 3, not in the multiplication theorem.

2. Corollary B. An oblivious multitape TM in time O(n lg^{1−κ} n) gives a size-O(T) circuit. So κ_obl ≤ η_* := liminf log γ(N)/log log N, which is ≤ 1 by the flow–cut bound. Consequences:

• κ → 1 requires coding gaps of (lg N)^{1−o(1)}. The converse does not follow.
• For general (non-oblivious) TMs the statement is vacuous, because Pippenger–Fischer costs exactly the log being saved.

3. Upstream's multiplier is oblivious after padding, at ×O(1) cost. The audit (HVDH-OBLIVIOUS-AUDIT.md) has a table of 23 rows with section and line citations. It finds three kinds of data dependence:

• variable-length integers;
• Harvey–van der Hoeven Lemma 2.2's scaling branch (fixed with clamp-and-select);
• sign handling, such as "complement if negative".

Everything else is driven by indices: the Gaussian and exponential weights, the Neumann counts, the label-and-sort, the FFT/Bluestein steps, §5's chunking and the base case. This closes the gap #634 left open ("HvdH internals not established"). So if upstream's Theorem 1 holds at κ, then γ(N) = Ω((lg N)^κ) at every N.

4. First explicit exponent for the Braverman–He seed (arXiv 2610.10108) amplified by BGS (arXiv 1608.06545). I rebuilt the 182-vertex graph from their Appendix A. All 157 sessions are at distance 5, which matches their 147/157.

quantity	value
c₁	67.94
BGS Thm 1.1 c₂	0.00298
all-N liminf (what Corollary B uses)	0.00198 (0.00260 with α optimised)

Today's κ ≈ 0.0017 is therefore 0.66–0.87× the best all-N guarantee from this seed. A gain of ×1.16–1.53 in κ would exceed it. This shows the scale of difficulty: a ×10 in κ would need a gap exponent well beyond anything published.

Credit and overlap.

• Research notes (no κ claim): #109 and lower bounds, the coding gap, a Lorentzian minrank obstruction, and a loss chain #634 (@ShikeChen01) has Lemma B′ (an oblivious machine at the same κ), the audit of HvdH Lemmas 2.1–2.5, and the "κ ≤ γ" question. This note supplies Theorem A with constants, the rest of the HvdH audit, the Lemma 2.2 clamp, and the BH⊗BGS exponent.
• I found no other thread on obliviousness or network coding.

Reproduce (standard library, each under 1 s): python3 exponents.py, python3 bh_c1.py, python3 bgs_dense.py.

Prepared with Claude Code (Claude Opus 5.5) assistance, using sub-agents; the main session re-ran the numerics. Not independently reviewed.

[philippeVV]

Correction and improvement: the BH⊗BGS guarantee is ≈ 0.0056 for all N (0.0064 with minimal leaves), not 0.0020. Artifact: bgs-renormalised @ 7c1b8657. Run python3 cert.py, which uses exact Fractions.

• BGS App. C/F start the amplification from the α-extension A* of the seed. For the Braverman–He seed (735 edges, 157 sessions, all at distance 5), A* is the 735 edges plus 314 unit-capacity pendant leaves.
• The dual D_α they use keeps the core weights 1/785 and gives the leaves weight 0.077× an edge weight. It has slack Σ dist = 1.031 and is never rescaled. The result is γ₀ = 1+ε/2 = 152/147 and c = l/w = 66.94, so all-N η = ln γ₀/(4 ln(c+1)) = 0.00198.
• On the same graph, the uniform dual w ≡ 1/1099 is feasible with Σ dist = 1 exactly. It gives z = 1049/1099, γ₀ = 1099/1049 and c = 7, so η = ln(1099/1049)/(4 ln 8) = 0.00560 for all N, and 0.0112 along BGS's sequence. With the printed Thm 1.1 constant ln γ₀/ln(16c₁²), the sequence value is 0.0067.
• Optimality on this graph. Any positive dual with l ≤ c·w has z ≥ a + 2(1−a)/c with a = 147/157, by weak duality against the core flow, and c ≥ 7. So uniform is the best dual for every rounding level. LP: HiGHS cutting planes, which agree to 10 digits.
• Why the honest optimal dual does not help. The core MCF is exactly 147/157 (rational flow certificate), and every optimal dual of the leaf graph puts weight 0 on all leaves. That is BGS's own "weight 0" obstruction, so a non-optimal dual is unavoidable.
• Hypotheses. Equal demands, distinct terminals, positive weights, feasibility and c_m ≥ c_k, c_n all hold. The coding rate stays ≥ 1 because each leaf carries one F₉ symbol per slot. App. F's proof uses D* only through standard form, NC/z(D*), l and w (Thm 3.6, Lemma 3.9, w_i = w_{i−1}²). The printed Thm 3.10/1.1 cannot be applied directly, since Lemma 2.2 would contract the leaves. Cite as "App. F's proof with D = uniform".*
• Further gain under the same standard form. Keep one terminal at each of the 133 terminal vertices and leaf only the other 181 terminals. This gives γ₀ = 483/458 at c = 7, so η = 0.00639 (all N) and 0.0128 (sequence).
• Consequence for the repo. Upstream's κ_sel = 0.00167 is about 0.26–0.30× of the guaranteed undirected coding-gap exponent. It is not comparable to it.
• Scripts: exact Fraction checker plus HiGHS LPs (expXI). Not independently reviewed.

So the upper body of this thread overstated how close κ is: today's κ is 0.26–0.30× of the guaranteed exponent, not 0.66–0.87×. I have updated the status block. Author-checked, not independently reviewed; the F₉ code itself is taken from BH and their verifier. Prepared with Claude Code (Claude Opus 5.5) assistance.

[philippeVV]

Artifact: bh-exact-schedule @ a5693d90. I ran the main reproduce commands myself from that directory, check_json.py and verify.py 3 cyc9.txt dense; both pass, and schedule9.json regenerates byte for byte.

First exact helper-free schedule of the Braverman–He code (q = 9 Hermitian Tanner code on PG(2,9))

This is a schedule of BH's 166-session code on the full PG(2,9), with no helper ports and no dropped sessions:

• Gates. There are 182 gates, each a [10,5] MDS code over F₉. Points use doubly-extended RS rows. Lines use the √q-twisted rows.
• Order. The order is Singer cyclic: points P_i at 2(16i mod 91), and lines L_l at 2((16l − 3) mod 91) + 1.
• Orientation. It is Eulerian, 5 in and 5 out at every gate. There are |R| = 166 back arcs, which equals dim C, and Γ − R is
  acyclic.
• Exactness. A gate-by-gate F₉ simulation finds every gate bijective and rank(Φ − I) = 0. So the session map is the identity:
  the schedule is exact and sound, with 166 = S sessions.
  • For comparison, BH's own order needs 9 C ports and 9 J ports.
• Negative controls. Rescaling one coordinate of the line codes gives rank(Φ − I) = 1. Rescaling all of them gives 61. These match
  the dense dim W of 165 and 105.

Reproduce. You need the file schedule9.json (the order, the 910 oriented arcs and R) plus the scripts:

python3 check_json.py schedule9.json          # stdlib: perfect difference set, incidences, Eulerian 5/5, Kahn acyclicity, |R| = S(9) = 166
python3 verify.py 3 cyc9.txt dense            # numpy: transportation 166/166, 182 gates bijective, rank(Phi - I) = 0, dense dim W = 166
PERTURB=one python3 verify.py 3 cyc9.txt      # control: rank(Phi - I) = 1

verify.py rewrites schedule9.json in the current directory when the check passes. Our rerun reproduced it byte for byte.

Scope and caveats.

• This is a circuit over F₉. It is not a candidate for finite_bit_contract.py.
  • The checker accepts the incidence: 166 roles, 182 gates, and 1076 physical edges (166 + 744 + 166).
  • It rejects the scalar map (Wrong input-to-output permutation), because F₉ gates have no XOR form.
  • No binary encoding can supply one: (F₉, +) has exponent 3.
• It is not routable. Girth 6 forces every head→tail path to have ≥ 5 arcs, and 5·166 = 830 > 744.
• No κ claim. On this exact, lane-free instance, every frame family we screened is certified at s ≥ Wm, so it gives no saving:
  • GRS-F₂, 23 phase-frame families, m = 4..8, 3 draws: 345 of 345 ranks full;
  • the two-class theorem, 41 partitions: all m ≤ 15;
  • the rational ray test, all scalings: 184 rays, every gcd trivial.
• The schedule is offered as a test bed. It does not open a route.

Prepared with Claude Code (Claude Opus 5.5) assistance; not independently reviewed.