A sequence is a vector
Leave the radar background aside for a moment. A four-phase sequence of length N is simply an N-dimensional complex vector: each entry takes one of the values 1, i, -1, -i, written as powers of i as i⁰, i¹, i², i³ and encoded as 0, 1, 2, 3 in submissions. These four symbols represent four equally spaced angles on the unit circle, so they can be subtracted and multiplied, which underpins everything that follows.
A codebook consists of five such vectors. The goal is to make these five vectors point in directions that are as distinct as possible, and to maintain that property across all of their shifted copies.
Inner products measure how close two directions are
The inner product of two complex vectors is ⟨y, x⟩ = Σ yₜ · conj(xₜ). Each term yₜ · conj(xₜ) is the quotient of two unit complex numbers, representing the phase difference at that position.
If two vectors point in the same direction, the phase difference is identical at every position, the terms add in phase, and the modulus reaches up to N. If they point in different directions, the phase differences scatter around the unit circle, cancel out in the sum, and leave a modulus near zero.
At the receiver, the inner product tests whether two signals match: a large modulus means yes, and a modulus near zero means no. That is how the receiver identifies an echo.
The challenge lies in the number of pairings tested: the receiver evaluates over a thousand pairings, and only the single true match should produce a strong response. Any wrong pairing with a large inner product risks a false detection. Keeping all wrong pairings small is what makes the true echo stand out clearly.
Only the modulus of the inner product matters, because reflection off a target introduces an unknown overall phase shift. Rotating the whole signal rotates the inner product without changing its modulus.
Every shift tests a candidate distance
Because an echo takes an unknown amount of time to return, the receiver slides each candidate sequence by 0, 1, 2, and so on, computing an inner product at every shift. Each shift k directly tests a candidate distance: is there a target at this range?
The receiver is therefore evaluating an entire two-dimensional table: five channels across every possible range. Each cell in the table records the inner-product modulus for that channel and shift.
Ideally, only the single cell corresponding to the true channel and true range gives a strong response, while every other cell stays near zero. That is the core requirement of the 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 (positive and negative shifts have equal modulus, so only half are counted), and each of the 10 pairs of distinct sequences has 2N−1 shifts. In total there are 5(N−1) + 10(2N−1) = 25N − 15 cells: 910 at N = 37, and 1810 at N = 73.
Goal: make all non-matching pairings near-orthogonal
Putting the two pieces together, the problem can be stated in one sentence:
Design five four-phase complex sequences so that they and all their shifted copies have inner products as close to zero as possible across every non-matching pairing.
The only excluded pairing is a = b with k = 0, where a sequence aligns with itself at zero shift. That inner product is always N, representing the true detection peak, and is not scored. Every other inner product should be as small as possible.
A concrete example: orthogonality and sidelobes
Take two sequences of length 4: A has constant phase 0° at all four positions, while B advances by 90° each step: 0°, 90°, 180°, 270°. As complex vectors, A = (1, 1, 1, 1) and B = (1, i, -1, -i).
At zero shift, ⟨A, B⟩ = 1 − i − 1 + i = 0, so the two vectors are orthogonal: testing echo B against template A gives zero output, while ⟨B, B⟩ = 4 gives the full response.
Yet zero shift is only one cell in the table. Against its own shifts, A performs poorly: modulus 3 at shift 1, 2 at shift 2, and 1 at shift 3. A single target would therefore trigger false detections across neighbouring ranges. A constant sequence fails because it correlates strongly with its own shifted copies.
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 an inner product by hand
The symbols 0, 1, 2, 3 are exponents of i: symbol p stands for iᵖ. Dividing one phase by another gives i^(p−q), turning complex multiplication into subtraction modulo 4. The entire inner product reduces to integer counting.
It takes three steps: first, align the two sequences at the given shift and subtract the lower symbol from the upper modulo 4 across the overlap; second, count how often 0, 1, 2, and 3 appear, calling the counts n₀, n₁, n₂, n₃; third, the real part is n₀ − n₂, the imaginary part is n₁ − n₃, and the squared modulus is (n₀ − n₂)² + (n₁ − n₃)².
Why this works: differences of 0 and 2 contribute +1 and −1 along the real axis, while differences of 1 and 3 contribute +i and −i along the imaginary axis. The inner product is determined entirely by the two pairs of count differences.
A = 0 0 1 3 B = 0 2 3 1
differences n0/n1/n2/n3 re = n0-n2 im = n1-n3 |R|²
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 4This is the exact calculation the verifier performs. It also makes the design goal clear: the more evenly the four counts are balanced, the closer both differences stay to zero; whenever one phase difference dominates, the inner-product modulus spikes.
Two types of false response and dynamic range
Non-matching inner products fall into two categories: a large non-zero-shift autocorrelation creates ghost echoes of a real target at wrong ranges, while a large cross-correlation between different sequences causes crosstalk between channels.
The primary score tracks the worst peak across all non-matching pairings. Because the receiver cannot distinguish a strong target's sidelobe from a weak target's true echo, the ratio of the main peak to the worst sidelobe sets the dynamic range between strong and weak targets.
The table below compares two length-73 codebooks on the site, both with a main detection peak 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 has a ratio of 1.00, with its worst false peak equal to the main peak, serving only as a trivial starting baseline.
Scoring: a three-part integer tuple
Because every entry is 1, i, -1, or -i, each inner product is a Gaussian integer. Scoring uses the squared modulus re² + im², computed entirely in exact integer arithmetic.
The score is a three-integer tuple compared lexicographically: first, the maximum squared modulus across all non-matching pairings (peak²); second, the number of pairings that hit that maximum (ties); third, the sum of squared moduli across all non-matching pairings (total energy), displayed as peak² · ties · total energy.
The secondary tie-breakers matter because the peak squared modulus is a small integer where ties are frequent. Counting ties and total energy distinguishes codebooks that share the same peak. At first, you can focus simply on pushing the peak squared modulus as low as possible.
For the theoretical lower bound at N = 73, a Welch-type inequality gives a continuous bound of about 22.21. Because the squared modulus of a Gaussian integer must be a sum of two integer squares, and neither 23 nor 24 qualifies while 25 = 3² + 4² does, the strict integer lower bound is 25. No published codebook with full explicit sequences was found for these exact parameters, so no external record is listed.
Search space and coupling
If phases could vary continuously, finding low-correlation waveforms would be much easier; however, practical transmitters require constant-amplitude pulses with phases drawn from a small discrete alphabet, making four-phase modulation (QPSK) a standard choice.
After fixing the initial phase of each sequence, there are 4^(5(N−1)) candidate codebooks—roughly 10¹⁰⁸ at N = 37—making exhaustive search impossible. Worse, the problem is tightly coupled: flipping a single symbol alters many autocorrelation and cross-correlation values at once, so pushing down the current worst peak often raises another shift in its place.
Engineering context
In multiple-input multiple-output (MIMO) radar and sonar, multiple antennas transmit simultaneously and the receiver observes the superposition of all echoes. Matched filtering—computing the inner-product table above—separates the channels and estimates target ranges. High peaks at wrong pairings cause ghost targets, range ambiguities, or channel crosstalk.
Designing discrete-phase codebooks with low autocorrelation sidelobes and low cross-correlation is a classic waveform design problem. P70 distils it into a clean, exactly verifiable combinatorial minimax problem: five channels, four phases, and the worst non-matching correlation peak made as small as possible.