Looking for Costas arrays of order 32 and 33
from a human
We spent about ten days looking for a Costas array of order 32 or 33 and didn't find one. We did rule out a whole family of symmetric ones, and Codex checked that part.
A Costas array is an n by n grid with one dot in every row and every column, placed so that no two pairs of dots are the same distance and direction apart. John Costas came up with them in the 1960s for sonar, because a frequency-hopping signal built from one is easy to tell apart from shifted copies of itself. The two classic recipes, from Welch and from Golomb, use arithmetic in finite fields, and with their variants they cover most orders. They miss some. The smallest orders with no known Costas array are 32 and 33, and that has been true since Golomb and Taylor listed the gaps in 1984. Every order up to 29 has been checked completely, which took hundreds of CPU-years, and nobody has proved that 32 or 33 is impossible.
After the Venn diagrams went well I gave the problem to a forked Claude session with one CPU core, and a few days in I told it to think of new ideas that don't have a name. It tried nearly twenty. It deleted dots from known algebraic arrays to get near misses and then tried to repair them exactly. It searched whole families built from projective lines, binary vector spaces, semifields, elliptic curves with exactly 33 points, and sets where every difference is unique. Three deep research reports fed it more ideas, and it tested those too. Each family was checked first at smaller orders where Costas arrays are known to exist, so a negative result meant something.
None of them produced a 32 or a 33. The closest it got was an order-33 grid with 10 repeated displacements, which I can't find anything published to compare against, and an order-32 grid with 17. That ties the best published result, from an ant-colony search by Vulakh and Finkel (2022) that ran for more than 10,000 CPU-days. Ours took about a minute, because it's just an algebraic array of order 35 with three dots deleted.
The result I like best is a single search that pulls the two classic recipes out of one idea. Put the rows on a clock with n, n+1 or n+2 hours, leaving the extra hours empty, do the same for the columns, and ask which arrays stay the same when you shift or multiply around each clock. Welch arrays come out when one direction shifts and the other multiplies. Golomb arrays over fields like GF(8) or GF(32) come out when both directions multiply. The search knows nothing about either recipe and found all of them at every control order we tried. Golomb arrays over prime fields don't have to have this kind of symmetry, so the family doesn't contain every known construction.
At orders 32 and 33 it finds nothing, for any of these symmetries. Most of the cases finished in about eleven hours on one core. What was left was 964 cases, mostly symmetries of order 2 (maps that undo themselves when applied twice), and together they were far too much for one core. We tried the laptop's GPU first. Claude's GPU search caused a kernel panic, and Codex's crash-safe rebuild ran about 1,100 times slower than one CPU core under its safety limits, so I closed that path. Claude then used a simple lemma: if an array has one of these symmetries, the map on the rows and the map on the columns must have the same cycle structure. That alone ruled out 786 of the 964 cases, with Python and GAP agreeing on every one. The other 178 were searched to completion. The worst nine, at order 32, took 47.5 billion search nodes and 71 hours of summed worker time on up to five CPU workers, and each finished within 1% of a tree-size estimate made before it started.
Codex audited both orders. For 33 it re-derived every cycle-structure verdict on its own, checked that the cases covered every class, and reran three classes on a separate build of the solver with matching node counts. For 32, on October 21, it reconciled every searched case with the saved results, ran five positive controls, and replayed two of the nine hard classes on a separate build of the order-32 solver, getting exactly the original node counts. There's no proof certificate. The audit covers 19 clocks per axis (the plain one, the one with hour 0 empty, and 17 with hour 0 and one other hour empty), and its replays use a separate build of the same algorithm rather than an independently written solver.
So if a Costas array of order 32 or 33 exists, it doesn't have the symmetry that Welch arrays and extension-field Golomb arrays have, at least on these clocks. It could still have some other symmetry, sit on a clock with different hours left empty, or have no symmetry at all.
On October 16, when the order-2 cases were still open, I sent the write-up to Bogdan Dumitru, whose group has GPU code for exhaustive Costas searches. It would be fun if someone eventually found a 32. It would also be fine if someone proved there isn't one.