Braverman & He refute the 2004 undirected multiple-unicast (network coding) conjecture with a GPT-6-found counterexample on PG(2, 9)

In directed networks, coding at intermediate nodes is known to beat routing (the classic butterfly example). For undirected networks with many source–sink pairs, Li and Li and, independently, Harvey, Kleinberg and Lehman conjectured in 2004 that coding gives no advantage over fractional multicommodity flow. The conjecture mattered beyond networking. A proof would have given unconditional lower bounds for external-memory algorithms and an Ω(n log n) circuit lower bound for multiplying integers.

Mark Braverman and Zhongtian He had refuted stronger variants of the conjecture in 2025. This time they posed an even stronger “nondeterministic” version to GPT-6, in which bits simply appear on edges and each vertex accepts or rejects by local checks. GPT-6 found a counterexample using Reed–Solomon codes on the projective plane over 𝔽₉. The authors then oriented the edges and ran a local search, and the example became a genuine causal code, which disproves the conjecture itself. The paper ships a standalone verifier and simulator.

The authors also note that OpenAI’s catalogue, released the day before, implies the same refutation indirectly: its claimed sub-n log n Fourier circuits, combined with the Afshani et al. argument, would yield a coding advantage.

This is a clean, checkable AI-found counterexample to a 22-year-old conjecture in information theory, by a leading theoretical computer scientist who describes exactly how the model was steered. Together with OpenAI’s claimed sub-n log n multiplication, it shifts a whole cluster of beliefs about lower bounds in the same week.