# The N=32 Wall

> Two numbers nobody can answer, and a search that shows you why.

A verified database of Costas arrays for orders 2–100, algebraic generators built over finite fields, and CP/SAT/LP experiments against the smallest orders where nobody has ever found one — or proved none exists.

- **Source:** https://github.com/butkeraites/costas-array
- **Licence:** MIT
- **Techniques:** Constraint programming, SAT solving, Exhaustive search, Finite fields
- **Stack:** Python, C++, OR-Tools, kissat

## Headline results

| Measure | Value |
| --- | --- |
| Arrays verified on every CI run | 9,217 |
| Orders with no known array | 18, smallest is 32 |
| Exhaustive search, order 15 | 2.2 s · 743k nodes |
| Exhaustive search, order 17 | does not finish |

## A permutation with an unreasonable property

A Costas array is a permutation of `1..N` where **every displacement vector
between two dots occurs exactly once**. Draw the dots on a grid, connect any
two, and no other pair anywhere in the array has that same offset.

The property is easy to state and brutal to satisfy. It is also useful: the
autocorrelation of such an arrangement is nearly ideal, which is why they show
up in radar and sonar waveform design.

## The wall

Costas arrays are known for most small orders. Two are missing.

**Nobody has ever found a Costas array of order 32 or 33, and nobody has proved
one does not exist.** Sixteen more orders up to 100 are in the same state. The
algebraic constructions — Welch, Golomb, Lempel, all of them built from
primitive elements of finite fields — produce arrays only for orders tied to
primes and prime powers. Every other order has to be searched. And search runs
into a wall you can feel:

| Order | Exhaustive search |
|---|---|
| 13 | 0.03 s |
| 14 | 0.4 s |
| 15 | 2.2 s, 743k nodes |
| 16 | ~19 s |
| 17 and up | does not finish |

Two orders past a two-second problem, the same program will outlive you.

## What is in the repository

**A verified database.** 9,217 arrays across 82 orders. Every one of them is
re-checked against the definition on every CI run — the difference property is
re-derived from scratch, not trusted. The eighteen orders with no known array
are checked too, against the published table, so the repository cannot quietly
disagree with the literature.

**Generators, not just data.** `costas_generate.py` builds arrays from the
published mathematics with no external input: exhaustive backtracking, the
Welch construction, and Golomb/Lempel over GF(p^k) — including its own
finite-field arithmetic, because the prime-power orders need a real field, not
modular arithmetic. It reproduces the database exactly for orders 2 through 7.
Above that it reproduces a subset, and the repository says so precisely rather
than implying otherwise.

**Search experiments.** Propagator ablations, symmetry breaking over the
dihedral group, LP relaxations sharded by column window, mined clique cuts and
forbidden patterns, and a SAT encoding whose size at order 32 is itself the
story: **1,016,863 variables and 3,048,590 clauses**.

## What the measurements taught me

The honest results are the interesting ones, and they were not what I expected.

Turning the matching propagator *off* cut node counts by only about 16% at
order 14 — while making order 13 roughly **four times faster in wall-clock**.
The dyadic filters changed node counts by **exactly zero** on satisfiable
instances.

The propagators are correct and carefully built. Measured against the thing
that actually matters, most of them do not pay for themselves here. That is
worth more to me than another green benchmark, because it is the kind of result
you only get if you instrument honestly and then publish what came back.

---

Renan Butkeraites · https://butkeraites.com/projects/costas-arrays/