Dots that never repeat a step

In the 1960s John Costas, an engineer working on sonar at General Electric, had a problem of pattern design. A sonar pulse hops between frequencies over time — one frequency in each time slot — and its echo returns shifted in time, because the target is far away, and shifted in frequency, because the target is moving. To read both shifts off the echo unambiguously, the hopping pattern must have a property: if it is slid against itself by any amount in time and any amount in frequency, the slid copy should coincide with the original in at most one place. Then there is exactly one shift that makes the echo line up with the pulse, and that shift is the answer.

Drawn on a grid, with time across and frequency up, the pattern is a set of $n$ dots, one in each column and, if every frequency is used once, one in each row. The condition says that no two pairs of dots are joined by the same step — the same displacement across and up. Such patterns are now called Costas arrays. They are permutations with a geometric condition attached, and finite fields, which every element is a power of one of them showed are generated by a single element, turn out to be the natural way to build them. The surprise is how little of the subject the constructions reach.

Ten dots that never repeat a step #

Here is a Costas array of order ten. Its dots are at $(i, 2^i \bmod 11)$ for $i$ from 0 to 9, written with the values shifted down by one so that they run from 0 to 9.

The condition can be checked mechanically with the difference triangle. Its first row lists the rise from each dot to the next, its second row the rise from each dot to the one two columns along, and so on. Two pairs of dots joined by the same step means two pairs the same distance apart horizontally with the same rise, which is a repeated number within one row of the triangle. So the array is Costas exactly when no row of its triangle repeats a value, and this one passes: the nine rises in the first row are all different, the eight in the second, and so on down to the single entry in the ninth. The 45 segments joining pairs of dots are 45 different vectors.

The condition is much stronger than it looks. A random arrangement of ten dots in ten rows and columns almost always repeats a step: there are $10! = 3{,}628{,}800$ such arrangements and, as the search below finds, 2,160 Costas arrays among them, about one in seventeen hundred.

A primitive root builds them #

The array above is Welch’s construction, found by Lloyd Welch in 1982. Take a prime $p$ and a primitive root $g$ — a number whose powers modulo $p$ run through every nonzero remainder, as 2 does modulo 11. Put a dot at $(i, g^i \bmod p)$ for $i = 0, \ldots, p - 2$. The values $g^i$ run through $1, \ldots, p - 1$ exactly once each, so every row and column holds one dot; and the multiplicative structure of the remainders guarantees that the steps never repeat. A step $d$ columns to the right goes from $g^i$ to $g^{i+d}$. If two such steps, starting at columns $i$ and $j$, rose by the same amount, their rises would also agree modulo $p$, so $g^i(g^d - 1)$ and $g^j(g^d - 1)$ would leave the same remainder; since $g^d - 1$ is not a multiple of $p$ it can be cancelled, leaving $g^i$ and $g^j$ equal and $i = j$.

The construction gives more than one array. Since $g^{p-1} = 1$, the pattern repeats with period $p - 1$, and any window of $p - 1$ consecutive columns is again a Costas array.

All fifteen windows of the 24-column strip pass the test. A window starting at column $c$ is the original array with every value multiplied by $2^c$, and Welch’s argument applies to every such multiple. So one prime and one primitive root give $p - 1$ arrays, and there are $\varphi(p - 1)$ primitive roots for each prime: modulo 11 there are four, 2, 6, 7 and 8, giving forty Welch arrays of order ten. Removing the dot in a corner of a Welch array gives a Costas array one order smaller, and for primes with 2 as a primitive root a second corner can be removed as well. How often 2 is a primitive root is itself a famous question, which how often two generates every remainder measured against Artin’s conjecture.

Two primitive elements build more #

Solomon Golomb found a second construction in 1984, using the full structure of a finite field rather than just its multiplication. Take a field with $q$ elements — $q$ a prime or a power of a prime, like the field with four elements — and two primitive elements $\alpha$ and $\beta$, each of whose powers run through every nonzero element. Put a dot at $(i, j)$ whenever

$$\alpha^i + \beta^j = 1, \qquad 1 \le i, j \le q - 2.$$

For each $i$ the number $1 - \alpha^i$ is nonzero, so it is a single power of $\beta$, and each column gets exactly one dot; the same argument with the roles reversed puts one dot in each row. The Costas property follows from the field’s addition and multiplication together, in a proof a few lines long. Golomb’s construction reaches orders $q - 2$ for every prime power $q$, which includes orders Welch’s cannot reach: the field with sixteen elements, built from polynomials over the field of two elements, gives arrays of order fourteen. When $\alpha = \beta$ the condition is symmetric in $i$ and $j$, and the array is its own reflection in the diagonal; that special case was found by Abraham Lempel in 1975.

Costas arrays are rare, and the counts are known #

To see what the constructions miss, every Costas array must be listed, and for small orders that can be done by search. The search places dots one column at a time and keeps a table of the steps already used between pairs of placed dots; a new dot is rejected the moment it would repeat a step, which prunes most arrangements long before they are complete.

The counts agree with the published ones at every order: 40 of order five, 760 of order nine, 2,160 of order ten, 12,828 of order thirteen. They climb far more slowly than $n!$, and of the 6.2 billion arrangements of thirteen dots about one in half a million is a Costas array. Exhaustive searches by others, using the symmetries of the square to cut the work by eight and much sharper pruning, have carried the census to order 29, and the counts rise to a peak near order sixteen and then fall. Costas arrays become rarer in absolute numbers, not just as a share, as the order grows. That is unusual among combinatorial censuses. The Latin squares counted in nine thousand four hundred and eight grow faster than any exponential and are known exactly for only eleven orders because there are too many of them; Costas arrays are known for nearly thirty orders, and the obstacle is the opposite one. There are few of them, they are hard to find, and a search must examine an enormous number of near misses — arrangements that repeat a step only at the last column — for every array it keeps.

Almost every small Costas array has no formula #

With the full lists in hand, the arrays the constructions produce can be counted among them: Welch’s arrays from every prime and primitive root and every shift, the arrays left by removing one or two corner dots, Golomb’s arrays from every field of up to seventeen elements, and the turns and reflections of all of these.

Up to order four the constructions give everything, because there is so little room that every Costas array is forced. At orders five and six they give about half and a third. From order seven on they give less than one array in twenty: 8 of the 200 of order seven, 92 of the 2,160 of order ten, 96 of the 7,852 of order twelve, and only 4 of the 12,828 of order thirteen, where the only construction in reach is Golomb’s from the field of sixteen with a corner removed. The great majority of small Costas arrays are sporadic: they exist, the search finds them, and no known rule produces them. Other constructions exist beyond the ones counted here — variants that remove more corners or use special pairs of primitive elements — and they add arrays at some orders, but not enough to change the picture.

This is a situation that recurs whenever a combinatorial object has both an algebraic construction and a search. The algebra produces a few beautiful members with symmetry and structure, and the search reveals that most members have neither. Twenty cards with no set among them met a version of it: the largest collections of cards with no matching triple have structure, but the collections in general do not.

The search grows fivefold with every order #

The census stops where it does because the search grows exponentially.

From order nine on, each extra order multiplies the work by a factor between four and five and a half; from twelve to thirteen it was 4.85. Thirty-four million partial arrangements were examined for order thirteen. Carried on at that rate, a search of order 32 would examine about $4 \times 10^{20}$, far beyond any computer, and the searches that reached order 29 needed both better pruning and years of computing. Orders 32 and 33 are the smallest for which no Costas array is known — none from any construction, and none from any search, because no search can yet be completed there. Whether Costas arrays exist for every order is an open question, and those two orders are where the evidence runs out.

A ruler in two dimensions #

A Costas array is the two-dimensional relative of an older object, the Golomb ruler: a set of marks on a line whose pairwise distances are all different, so that every length the ruler can measure, it measures in only one way. The marks 0, 1, 4 and 6 form one; their six differences are 1, 2, 3, 4, 5 and 6. A Costas array asks the same of vectors in the plane, with the extra requirement of one dot in each row and column. Both are ways of spreading points so that no difference repeats, and both meet the same arithmetic.

The arithmetic has appeared in this collection in several guises. The densest graph without a square used Sidon sets, sets of numbers whose pairwise sums are all different, which is the same as their differences being different; the best of them are built from finite fields, by a construction of James Singer’s. A plane in a list of numbers found a whole projective plane encoded in four numbers whose differences hit every nonzero remainder exactly once, a perfect difference set, again from a finite field. And a labelling every tree seems to have asked for numbers on the points of a tree whose differences along the edges are all distinct, a question that has resisted proof for sixty years. In each case the field’s exponential map is what turns “no repeated difference” into “no repeated product”, and in each case the objects that do not come from a field are the hard part.

The sonar problem also has a clean statement in this language. The ambiguity of a hopping pattern at a given shift is the number of dots the shifted copy shares with the original. For a Costas array it is at most one at every shift except no shift at all, where it is $n$. No pattern can do better, since some shift always makes two dots coincide once there are two dots, and this “thumbtack” ambiguity — one spike, flat elsewhere — is why the arrays are still used in radar and sonar design.

Why fields and not something else #

The two constructions are not accidents of number theory. A Costas array is a permutation $\pi$ such that, for each horizontal distance $d$, the rises $\pi(i + d) - \pi(i)$ are all different. In a finite field, an exponential map $i \mapsto g^i$ turns horizontal distance into multiplication: the step $d$ to the right multiplies by $g^d$. Modulo $p$, a rise $g^{i+d} - g^i = g^i(g^d - 1)$ is the product of a fixed nonzero number and a power of $g$ that changes with $i$, and products of a fixed nonzero number with different powers are different remainders. The construction converts the condition about differences into the injectivity of multiplication, which a field supplies for free.

Golomb’s construction does the same with two exponential maps, one on each axis, joined by the field’s addition. That is why the constructions reach exactly the orders they do — one or two less than a prime or a prime power — and why the orders that are not near a prime power, such as 32 and 33, are the hard ones. The number 32 is itself a power of two, but Golomb’s construction would need a field of 34 or 35 elements, and neither number is a prime power; Welch’s would need a prime 33 or 34, and neither is prime. The algebra has nothing to offer at exactly the orders where the search has nothing to offer either.

What the pictures cannot show #

The counts up to order thirteen are exact and agree with the published census; the claim that the census continues to order 29 with a peak near sixteen is the published result, not something computed here. The share produced by the constructions depends on which constructions are counted, and the ones counted here are the principal ones, not all that are known, so the filled bars are lower bounds on what algebra reaches. The extrapolation to order 32 assumes the growth factor stays near 4.85, which is a guess about the search, not a theorem; a better search would be faster, and no extrapolation decides whether arrays of order 32 exist.

Nor do the pictures show the Costas property’s proof for Welch’s and Golomb’s arrays. The hero’s difference triangle verifies one array; the strip verifies fifteen windows; the proofs, that every array the constructions produce has the property, are a few lines of field arithmetic each, and they are what makes the constructions constructions rather than lucky finds.

Still open: an array of order 32 #

Is there a Costas array of order 32? None is known. The orders below 32 are all covered, by a construction or by a search; 32 and 33 are the first gaps, and above them the constructions leave gaps at more and more orders as primes and prime powers thin out. A single example at order 32 would settle that order, and the search for one has gone on for decades. It need not be exhaustive: a search that stops at the first array found can be far cheaper than a census, and randomised and constraint-solving searches have been run at these orders without success. A proof that none exists would be more surprising still, because nothing about 32 seems special except that the algebra misses it.

Behind that question stands a larger one: whether Costas arrays exist for every order at all. The counts fall after order sixteen, which suggests that arrays become scarce, and if the sporadic arrays thin out faster than the algebraic ones, the constructions would eventually be all there is — leaving the orders they miss empty. Nobody knows. The arrays were invented to make an echo unambiguous, and the question of which sizes of unambiguous echo are possible is still unanswered.