A sequence is a vector
Set the radar aside for now. A four-phase sequence of length N is an N-dimensional complex vector: each position is one of 1, i, -1, -i, which written as powers of i are i⁰, i¹, i², i³ and are submitted as 0, 1, 2, 3. The four symbols are not four unrelated labels but four angles on one unit circle: they can be subtracted from one another and multiplied together, and everything below rests on that.
A codebook is five such vectors. The problem does not ask for any five. It asks for five that point in different directions, and it asks that of every shifted copy of them as well.
An inner product is how alike two directions are
The inner product of two complex vectors is ⟨y, x⟩ = Σ yₜ · conj(xₜ). Each term yₜ · conj(xₜ) is one unit complex number divided by another, which is the phase difference at that position.
If the two vectors already point the same way, the phase difference is the same at every position, the terms all add in phase, and the modulus is large: at most N. If they point differently, the differences scatter around the circle, the sum cancels, and the modulus lands near zero.
So an inner product is not a similarity score. It answers a yes-or-no question: are these two the same signal? Large is yes and near zero is no. The test is a good one, and it is exactly how the receiver recognises an echo at all.
The difficulty is not in the test but in how many times it is applied: the receiver asks it of a thousand-odd pairings and exactly one should come back yes. Any wrong pairing that also returns a large inner product has the receiver calling two different things the same. Pushing those down is not the goal in itself. It is what leaves the one yes standing alone.
It is the modulus that matters and not the direction, because a reflection puts an unknown overall phase on the whole signal. Rotating everything rotates the inner product without changing its modulus.
Every shift is a range
This is the step that makes the problem make sense. An echo takes time to come back and the receiver does not know how much, so it slides the candidate sequence over by 0, 1, 2 and so on, taking an inner product at each. The shift k is not an abstract parameter. It is a range hypothesis: is there a target at this distance?
So the receiver is not asking one question but a whole table of them: five channels crossed with every possible range. Its answer to each is how large that inner product's modulus comes out.
Across that whole table exactly one cell should answer loudly: the right channel at the right range. Every other cell has to come out near zero. That is the entire problem.
shift |k| overlap what this inner product asks
0 N are the two whole vectors alike
1 N-1 are they still alike one step apart
2 N-2 still alike two steps apart
... ...
N-1 1 one position of overlap leftEach sequence has N−1 non-zero shifts against itself (a shift and its negative have the same modulus, so only half are counted), each pair of distinct sequences has 2N−1 shifts, and five sequences make ten pairs. That is 5(N−1) + 10(2N−1) = 25N − 15 cells: 910 of them at N = 37, and 1810 at N = 73.
So the ask is: every wrong pairing near-orthogonal
Putting the two sections together, the problem states itself in one line:
Design five complex vectors over four phases so that the set made of them and all their shifted copies is as close to orthogonal as possible at every pairing that is not supposed to match.
The one pairing that is not pushed down is a = b with k = 0, a sequence correctly aligned with itself. That one is necessarily N. It is the true detection and it is not scored. Every other inner product has to be small.
What orthogonal and not-orthogonal look like
Take two sequences of length 4. A is constant, 0° at all four positions; B turns a quarter each step: 0°, 90°, 180°, 270°. As vectors, A = (1, 1, 1, 1) and B = (1, i, -1, -i).
Unshifted, ⟨A, B⟩ = 1 − i − 1 + i = 0. They are orthogonal: hand the receiver B and let it test with A, and in the ideal case it responds with nothing. Meanwhile ⟨B, B⟩ = 4, the full response for the right candidate.
That is one cell. A against its own shifts is bad: modulus 3 at one step, 2 at two, 1 at three. A would report a target at nearly every range. A constant sequence is the worst answer here, not because it fails against the others but because it is too alike every shift of itself.
A = (1, 1, 1, 1) B = (1, i, -1, -i) <A, B> shift 0 = 0 orthogonal, good <B, B> shift 0 = 4 the true detection, not scored <A, A> shift 1 mod 3 A reports a target at this range <A, A> shift 2 mod 2 <A, A> shift 3 mod 1
Computing one by hand
0, 1, 2 and 3 are not four labels. They are exponents: the symbol p stands for i^p. So each term i^p · conj(i^q) is i^(p−q), and one complex multiplication collapses into one subtraction modulo 4. The whole inner product needs no complex arithmetic at all.
Three steps. Line the two rows up at the shift, and at each overlapping position subtract the lower symbol from the upper one, modulo 4. Count how many of the results are 0, 1, 2 and 3; call those n₀, n₁, n₂, n₃. The real part is n₀ − n₂, the imaginary part is n₁ − n₃, and the squared modulus is the sum of their squares.
Why that works: a result of 0 contributes +1 and a result of 2 contributes −1, and those cancel along the real axis; a result of 1 contributes +i and a result of 3 contributes −i, cancelling along the imaginary one. The inner product is just two differences of four counts.
A = 0 0 1 3 B = 0 2 3 1
differences n0/n1/n2/n3 re = n0-n2 im = n1-n3 |R|^2
shift 0 0 2 2 2 1/0/3/0 -2 0 4
shift 1 0 3 0 2/0/0/1 2 -1 5
shift 2 1 1 0/2/0/0 0 2 4That is exactly what the verifier computes. It also says what to aim for: the more evenly the four counts are spread, the closer both differences come to zero. An inner product is large precisely when one phase difference dominates the tally, which is what it means for two rows to be alike at that shift.
The two ways to be wrong
A large inner product between a sequence and a non-zero shift of itself means one real target appears a second time at the wrong range. A large one between different sequences means one channel's echo lands in another channel's detection, putting a target on a direction that never illuminated it.
The score looks only at the worst of them, because the receiver cannot tell one strong target's false response from a genuinely weaker target's true one. The ratio between the true detection and the largest false response is exactly how much fainter one target may be than another and still be seen.
Two length-73 codebooks shipped on this site show that ratio. Both have a true detection of 73.
true peak worst false ratio constant (baseline) 73 73 1.00x = 0.0 dB the audited one 73 11.18 6.53x = 16.3 dB
The constant codebook comes in at 1.00: the false peak stands as tall as the true one and nothing can be told apart. It ships as the baseline because it is the worst answer anybody could write down in one sentence, and this site does not solve its own problems.
The score: three integers
Every position is 1, i, -1 or -i, so every inner product is a Gaussian integer with whole real and imaginary parts. The score uses the squared modulus re² + im², which needs no square root and which the verifier computes exactly in integers. No float and no tolerance anywhere.
The score is three integers compared in order: the largest squared modulus among the wrong pairings, how many pairings reach it, and the sum of squared moduli over all of them. The page shows it as peak² · ties · total energy, and the separators are not multiplication.
Three keys are needed because the main score is a small integer and ties across a thousand-odd pairings are constant; ranking on it alone would hand each record to whoever submitted first rather than to whoever built the better codebook. On a first reading the last two can be set aside: make the worst wrong match as low as it will go.
As for how low it could go: at length 73 a Welch-type inequality gives 22.21. But a squared modulus is a sum of two integer squares, and neither 23 nor 24 is one while 25 = 3² + 4² is, so the strict bound is 25. No downloadable, individually verifiable published codebook was found for these parameters, so no known best is set and the interval is wide open.
Why only four phases, and how big that is
With continuous phase, finding low-correlation waveforms is much easier and the literature has near-ideal continuous solutions. But a real transmitter needs every pulse at the same amplitude, the phase drawn from a finite set, and the waveform producible by a digital modulator. Four-phase modulation meets all three, and those continuous solutions cannot be transmitted.
With each row's first phase fixed there are 4^(5(N−1)) candidates, about 10^108 at N = 37, so enumeration is not a plan. Worse is the coupling: changing one position moves many of that sequence's own correlations and many of its correlations against the other four, and pushing the current worst peak down routinely promotes some other shift to be the new worst. It is a tightly coupled discrete minimax problem.
What this is, out in the world
A multiple-input multiple-output radar or sonar transmits on several channels at once and receives the sum of all the echoes. It pulls them apart with exactly the table above: which channel an echo came from, how long it was delayed, and therefore how far away the target is. A high peak on a wrong pairing shows up on the screen as a false target, a wrong range, or crosstalk between channels.
Finite-phase codebooks with low autocorrelation sidelobes and low cross-correlation are therefore a real waveform design problem with an established literature. P70 takes a simplified version of it, cut down until it can be verified exactly: five fixed channels, four phases, and the worst peak among all the wrong matches pushed as low as it will go.