How many multiplications does it take to multiply two polynomials over F2? For the truncated and cyclic products the best known answers are still hand constructions from the 1980s and 2009, and in March 2026 every lower bound underneath them moved. Modern search has been pointed at exactly one of them, once, in a footnote — and it won. The free search did not beat a single published upper bound. It reproduced 3 of them from scratch at no cost, which is the honest result and is why the calibration below is worth more than the headline would have been.
| target | what it is | naive | published | ours | standing | upper bound is due to |
|---|---|---|---|---|---|---|
| C7 | cyclic product, 7 coefficients each | 49 | 13..13 | 13 | held | M. D. Wagh and S. D. Morgera, 'A new structured design method for convolutions over finite fields 1983 |
| C8 | cyclic product, 8 coefficients each | 64 | 19..22 | 25 | open | S. D. Morgera, 'Multiplicative complexity of bilinear algorithms for cyclic convolution over finite fields' 1990; M. Cenk and F. Ozbudak, 'Multiplication of polynomials modulo x^n' 2011 |
| P2 | full product, 2 coefficients each | 4 | — | 3 | dep | — |
| P3 | full product, 3 coefficients each | 9 | — | 6 | dep | — |
| P4 | full product, 4 coefficients each | 16 | — | 9 | dep | — |
| T6 | truncated product, 6 coefficients each | 21 | 13..14 | 14 | held | M. Cenk and F. Ozbudak, 'Multiplication of polynomials modulo x^n' 2011 |
| T7 | truncated product, 7 coefficients each | 28 | 16..18 | 18 | held | M. Cenk and F. Ozbudak, 'Multiplication of polynomials modulo x^n' 2011 |
| T8 | truncated product, 8 coefficients each | 36 | 19..22 | 23 | open | M. Cenk and F. Ozbudak, 'Multiplication of polynomials modulo x^n' 2011 |
| T9 | truncated product, 9 coefficients each | 45 | 21..26 | 27 | open | Wang, arXiv:2603.07280, footnote to Table 1: a new upper bound of 26 for multiplication over Z[x]/x^9, obtained by flip-graph search over F2 and lifted to Z |
The naive column is the definition itself run as an algorithm — one multiplication per non-zero of the target tensor. That is where every walk starts, and it is told nothing else: no construction, no published scheme, no hint. Published is the interval the literature leaves open, lower bound from Wang's 2026 preprint, upper bound from the hand constructions named in the last column.
A search that reports a number on an open problem is worth exactly as much as its behaviour on the problems whose answers are already known. So the instrument's battery carries a ladder of PUBLISHED ranks the free walk has to keep reaching, at a fixed seed and a fixed budget — a deterministic gate, not a coin flip.
The sharpest rung is C7. Wagh and Morgera gave a rank-13 cyclic convolution over F2 in 1983; Wang proved in 2026 that 13 is also a lower bound. The two walls meet, so 13 is the exact rank — and the walk finds it from the naive rank-49 algorithm, in seconds, having been told nothing.
The ladder is also what caught this search being broken. Without a rank-INCREASING move the walk matched the literature on the small full products and then quietly sat above it from P5 on — which looks exactly like success if nobody checks the top of the ladder. Adding the plus transition moved P6 from 21 to 18. That is the whole argument for calibrating against published numbers rather than against nothing.
| who | what they searched | what it means for this page |
|---|---|---|
| Barbulescu, Detrey, Estibals & Zimmermann 2012; Covanov 2017 | exhaustive search for OPTIMAL bilinear formulae | reaches degree 5 — the short product modulo X⁵ and the circulant modulo X⁵−1. Every target on this page is beyond it. |
| Chen & Kauers, arXiv:2502.06264, Feb 2025 | flip graphs for the FULL product over Z₂, a 10×10 table | the full product is theirs, and their squares land exactly ON the Montgomery bounds, never below. Their table is used here as the calibration ladder, not as a target. The words cyclic, truncated and negacyclic do not appear in their paper. |
| Wang, arXiv:2603.07280, Mar 2026 | 18 new LOWER bounds; and, in one footnote, a flip-graph search over F2 for T₉ | the lower walls on this page are his. His footnote also improves T₉ from 27 to 26 by exactly this method — so the one truncated case modern search has touched, it beat. That is the reason to expect the others to move. |
This table is the correction. The task that produced this page was written around the claim that flip-graph search had never been pointed at polynomial multiplication. That is false, and finding out cost half an hour: Chen and Kauers had already done the full product, so attacking it would have been redoing their run. What survived the check is smaller and real — the cyclic and truncated families, which nobody has swept. An item whose appeal rests on "nobody has tried this" is resting on a negative that was never checked.
The failure mode for this kind of search is not an arithmetic slip, it is certifying the wrong tensor. Any set of rank-one terms decomposes SOME tensor; a certifier that accepts the target alongside the scheme is checking a tautology. So instruments/bilinear takes only the target's NAME and rebuilds the tensor itself, by literal polynomial arithmetic — an actual convolution, an actual reduction modulo Xⁿ−1 — never by the index formula the search uses. The two derivations are asserted equal in the battery, entry by entry, for every family and size.
The red controls are what make that more than a claim. A correct C7 scheme audited as T7 is REFUTED. Strassen's rank 7, handed over in the other C-index layout, is REFUTED — the target name pins the tensor and the instrument will not shop for a convention that makes a claim pass. And the one case this instrument shares with the older instruments/strassen is put through both, which is worth more than either alone.
One more refusal is wired in and has never fired: a scheme that certifies BELOW a published lower bound refuses this build outright. It would mean a 2026 theorem is false, and it is far likelier that this repository is wrong — so it is treated as a bug report against us until an independent check says otherwise, rather than as the headline it would be.
Nothing here is new mathematics. The search matched the literature and did not get under it, on the budget it was given, and that is reported as the result rather than buried. These are F2 statements; a scheme over F2 need not lift to Z or to any other field, and no lifting was attempted. The 3 rows are still above the literature, listed rather than dropped. And this is not a complete sweep: P6, P7, P8, C10, T10, T11 carry published bounds and were never attempted here — the campaign was stopped, not exhausted. Published, not peer-reviewed, not independently rerun — which is exactly the status this machine exists to stop being true of other people's work, and it applies to ours the same way.