--- id: "2026-10-14-external-memory-integer-sorting-beats-comparison-bound-network-coding" url: "https://postcutoff.com/e/2026-10-14-external-memory-integer-sorting-beats-comparison-bound-network-coding/" as_of: "2026-10-15T10:09:00+02:00" date: "2026-10-14" date_precision: day category: science importance: 4 confidence: medium status: [Awaiting review] verification: Lean-verified sources: 2 editor: human editor human_review: null version: "2026-10-15" --- As of: 2026-10-15 10:09 CEST. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-10-14-external-memory-integer-sorting-beats-comparison-bound-network-coding/ # Li, Li & Liu: external-memory integer sorting beats the comparison bound, answering Aggarwal–Vitter (1988) by way of network coding, with ChatGPT/Codex and Lean On 14 Oct 2026 Baochun Li (Toronto), Zongpeng Li and Sirui Liu (Tsinghua) posted arXiv 2610.20079. It gives a new counterexample to the 2004 Li–Li conjecture and uses it to sort N integers of Θ(log N) bits in external memory with O((N/B)(1 + log N/((log(M/B))^{1−ε}(log M)^ε))) block transfers. In some parameter ranges this is asymptotically below the comparison-sorting bound of Aggarwal and Vitter. Whether integer keys can beat that bound has been open since they asked it in 1988. The sorting algorithm's correctness and complexity bounds are checked in Lean 4. The method adapts OpenAI's 2026 integer-multiplication circuits, and ChatGPT and Codex were used throughout. ## Key facts - Paper: 'Undirected Network Coding and Faster External-Memory Integer Sorting', arXiv 2610.20079 (cs.DS, 14 Oct 2026) - Bound: for N integers of Θ(log N) bits, memory M words, block size B with 2B ≤ M ≤ N: O((N/B)·(1 + log N / ((log(M/B))^{1−ε}(log M)^ε))) transfers, ε > 0 an absolute constant; the comparison bound is Θ((N/B)(1 + log(N/M)/log(M/B))) [Aggarwal–Vitter 1988] - Context: Farhadi, Hajiaghayi, Larsen and Shi (2019) showed that if the Li–Li conjecture held, no algorithm could beat comparison sorting in ranges including B ≥ log N. The conjecture was refuted on 7 Oct by Braverman–He and by Zhang–Li–Li; this paper notes that 'invalidating the assumption behind a conditional lower bound does not itself produce a faster algorithm' and supplies one - Builds on OpenAI's integer-multiplication work ('[Ope26]'), whose recursive linear-circuit construction is adapted to block transfers - Lean: 'We also use Lean 4 to verify the sorting algorithm's correctness and complexity bounds, and the strict advantage of coding over routing' (github.com/rtyu-1/coded-sorting-lean) - AI methodology (verbatim): 'We used OpenAI's ChatGPT, including Codex, to assist with exploring network-coding constructions and sorting algorithms, developing and examining mathematical arguments, implementing and debugging Lean proofs … The tools materially affected the constructions and algorithmic analyses in Sections 4–7' ## What happened In 2004 Zongpeng Li and Baochun Li conjectured that in undirected multiple-unicast networks network coding does no better than fractional routing. The conjecture mattered beyond networking: Farhadi, Hajiaghayi, Larsen and Shi showed in 2019 that it would rule out integer sorting faster than comparison sorting in external memory, which would close a question Aggarwal and Vitter asked in 1988. On 7 Oct 2026 the conjecture was refuted twice, both times with GPT-6 help ([entry](/e/2026-10-07-multiple-unicast-conjecture-false-gpt-6/)). A week later Baochun Li, Zongpeng Li and Sirui Liu turned the refutation into an algorithm ([arXiv 2610.20079](https://arxiv.org/abs/2610.20079)). They build a coding counterexample suited to "address-field interchange", rearrange data with recursive XOR circuits adapted from OpenAI's integer-multiplication construction, and combine this with Columnsort and most-significant-digit radix partitioning. The result is a deterministic sort whose I/O count is asymptotically below the comparison bound in a range of parameters. The algorithm's correctness and complexity bounds, and the advantage of coding over routing, are checked in Lean 4. AI methodology section (verbatim): "We used OpenAI's ChatGPT, including Codex, to assist with exploring network-coding constructions and sorting algorithms, developing and examining mathematical arguments, implementing and debugging Lean proofs, and preparing the manuscript and literature discussion. The tools materially affected the constructions and algorithmic analyses in Sections 4–7, the supporting arguments and formalization in Appendices A–D, and their exposition in Sections 1–3." No Hacker News thread was found on 15 Oct (Algolia). X was not searched directly. ## Why it matters It is a clear chain in which one AI-assisted refutation led to an AI-assisted algorithm: a disproved conjecture removed a conditional lower bound, and within a week the conjecture's own authors used it to answer a 38-year-old question. External-memory integer sorting is a central problem of I/O-efficient algorithms. The gain is asymptotic and holds only in some parameter ranges, so its practical impact is not claimed. ## What is disputed or not yet verified - Verification: Lean 4 formalization of the algorithm's correctness and complexity bounds (scope in Appendix D); unrefereed preprint ## Your AI and this story - GPT-6 Astra (training cutoff April 2026): 167 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 106 days after its cutoff - Gemini 4 Argon (training cutoff March 2026): 197 days after its cutoff - Grok 4.7 (training cutoff May 2026): 136 days after its cutoff ## Sources 1. [arXiv 2610.20079: Undirected Network Coding and Faster External-Memory Integer Sorting](https://arxiv.org/abs/2610.20079) (arxiv.org, paper) 2. [GitHub: rtyu-1/coded-sorting-lean](https://github.com/rtyu-1/coded-sorting-lean) (github.com, code) ## Changes - 2026-10-15 (filed): Created from the arXiv PDF ## Related - 2026-10-07: [Braverman & He refute the 2004 undirected multiple-unicast (network coding) conjecture with a GPT-6-found counterexample on PG(2, 9)](https://postcutoff.com/e/2026-10-07-multiple-unicast-conjecture-false-gpt-6/index.md) - 2026-10-07: [Outside researchers using AI crowdsource a tighter exponent in OpenAI's integer-multiplication result #109, from 2^-182 to about 2^-9.4 (conditional)](https://postcutoff.com/e/2026-10-07-colkitt-codex-integer-multiplication-exponent/index.md) - 2026-10-06: [OpenAI releases 722 AI-written math manuscripts claiming hundreds of open problems](https://postcutoff.com/e/2026-10-06-openai-math-release-722-manuscripts/index.md)