Mathematicians' PatternBoost Churns Out 5,000 Rare Math Matrices per Hour
A transformer plus local-search loop pumps out thousands of inequivalent Hadamard matrices per hour and cracks orders where random search fails.
ProTakeaways
- Transformer plus local search (PatternBoost) generates thousands of inequivalent Hadamard matrices per hour on a single H100.
- Restricts to Goethals-Seidel type matrices where FFT-based scoring makes local search tractable.
- Largest example produced has order 252, succeeding where random-init search fails entirely.
- Transformer dynamically discovered a hidden dihedral symmetry in an alternate ansatz, boosting solution rate.
- Uses symmetry group action for canonicalization plus on-the-fly data augmentation, eliminating overfitting.
- Full code and training runs available on GitHub and Weights and Biases.
A trio of mathematicians has built a system that generates Hadamard matrices at industrial scale by pairing a small transformer with classical local search. On a single H100, it can produce thousands of inequivalent order-148 examples per hour, and in harder regimes where random-init local search gives up entirely, it still finds needles in the haystack, all the way up to order 252.
The paper from Geordie Williamson, Oded Yacobi, and Paul Zinn-Justin lands squarely in the growing 'AI for Math' bucket. During training, the transformer figures out and starts exploiting hidden symmetries of the search space on its own, rediscovering structural shortcuts that mathematicians had previously imposed by hand.
Needles in an exponential haystack
A Hadamard matrix is an n by n array of plus-ones and minus-ones whose rows are all mutually orthogonal. Apart from the trivial orders 1 and 2, the order n must be a multiple of 4, and Hadamard's conjecture, unproven since 1893, claims that every such multiple works. The only orders less than 1000 for which no example is known are 668, 716, and 892; the last breakthrough was a construction of order 428 in 2005.
Even in ranges where existence is settled, examples are painfully sparse. Sloane's database contains a single matrix in each possible order up to 256, and for the higher orders those are essentially the only known instances. The reason is combinatorial: the fraction of plus/minus-one matrices that happen to be Hadamard shrinks roughly like a constant to the n squared, so brute force is hopeless past very small n.
The Goethals-Seidel shortcut
The authors restrict to matrices of Goethals-Seidel (GS) type, a highly structured 4-by-4 block form where the whole matrix is determined by four circulant blocks A, B, C, D of size n/4. That shrinks the search space from 2^(n^2) candidates down to 2^n. Crucially, the determinant of M is easily computed in terms of the eigenvalues of A, B, C, D, i.e., the discrete Fourier modes of one of their rows. Scoring a candidate becomes an FFT, and incremental updates during local search are cheap.
The score function itself is elegant. Define S as minus the log determinant of M divided by root n. It is nonnegative for any plus/minus-one matrix and hits zero exactly when M is Hadamard. In Fourier coordinates it decomposes into a sum over frequencies, so a greedy bit-flip search can identify which frequency is furthest from the Hadamard target and fix it locally.