{"id":"openai-math/Integer-multiplication-below-n-log-n","pdf":"https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026","tags":["algorithms","complexity-theory","integer-multiplication"],"score":0,"title":"Integer multiplication below n log n","domain":"Theoretical computer science","family":"109","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We give a deterministic algorithm that multiplies two n -bit integers in $`O(n(\\lg n)^{1-\\kappa})`$ worst-case time, with $`\\kappa=2^{-182}`$, on one fixed finite-alphabet Turing machine with a fixed finite number of one-dimensional tapes. The algorithm is exact for every input length and disproves the $`n\\log n`$ optimality conjecture of Schönhage and Strassen in this model.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":3,"published":"2026-09-23","reactions":{},"discussion":[{"url":"https://beyond-n-log-n.netlify.app","kind":"web","site":"beyond-n-log-n.netlify.app","text":"Conditional integer multiplication bounds, pull requests, mathematical approaches, and forks.","added":"2026-10-24","title":"Beyond n log n · Integer multiplication"},{"url":"https://mathoverflow.net/a/515855","date":"2026-10-08","kind":"web","site":"mathoverflow.net","text":"One of OpenAI's results is a deterministic algorithm for multiplying two $n$ -bit integers in time $$O(n (\\log n)^{1-\\varepsilon})$$ for a fixed $\\varepsilon>0$ . This is especially startling because multiplication is one of the most fundamental operations in mathematics, and $n\\log n$ was not…","added":"2026-10-24","title":"Answer to: Which of the results released by OpenAI went against the conventional mathematical wisdom?","author":"Philip Weiss"},{"url":"https://arxiv.org/abs/2610.14263","date":"2026-10-09","kind":"web","site":"arXiv.org","text":"Under the conditional framework breaking the longstanding O(n log n) integer multiplication barrier (originating from OpenAI Preprint #109), the asymptotic time complexity exponent T(n) = O(n (log n)^{1-κ}) is governed by bounding the second moment E[X^2] < 1 of recursive branching processes over…","added":"2026-10-24","title":"Bipartite Carrier Compression and Machine-Certified Bounds in Sch\\\"onhage Trilinear Multiplication Tensors","author":"Volkan Dağlı, Zerrin Dağlı, Dağhan Dağlı","record":"arxiv/2610.14263"}],"formalized":false,"family_title":"Integer multiplication below $`n\\log n`$"}