--- title: The difference coarray lead: Put a few sensors on a line and list every distance between two of them. Those distances are what the array can measure, and a well-placed handful of sensors covers far more distances than it has sensors. prerequisites: --- An antenna, a microphone or a hydrophone listens at one point. Put several of them on a line and together they can tell where a wave is coming from, because the wave reaches each one at a slightly different moment. Place the sensors at whole-number positions and call the list of positions `A`. What the array really measures comes in pairs. Multiply the signal at one sensor by the signal at another and average over time. When the sources are unrelated to each other, the answer depends only on how far apart the two sensors are, not on where they stand. That distance is the lag. So what matters is not the positions but the lags they produce: the set of all differences `a - b` with `a` and `b` in `A`, written `A - A`. That set is the difference coarray. The running example is four sensors at `A = {0, 1, 4, 6}`. List the differences of its six pairs: `1 - 0 = 1`, `6 - 4 = 2`, `4 - 1 = 3`, `4 - 0 = 4`, `6 - 1 = 5`, `6 - 0 = 6`. Every lag from 1 to 6 appears, each exactly once. Read each pair backwards for the negative lags, add the lag 0 of a sensor with itself, and the coarray is all 13 whole numbers from -6 to 6. A ruler with marks only at 0, 1, 4 and 6 measures every whole length up to 6, which is why this set is called a sparse ruler. The figure draws exactly that. The diamond is the board of all 49 pairs of positions from 0 to 6, turned on its corner so that each vertical column holds the pairs of one lag: lag 0 down the middle, stepping out to -6 on one side and 6 on the other. The ruler runs along both upper edges, the four sensors in yellow and the three empty positions faint. A pair is lit blue when both of its positions hold a sensor, 16 lit pairs in all. The middle column has four and each of the other twelve has one. Beneath the diamond the lit pairs have fallen straight down their columns into stacks. Those stacks are the weight function. The weight `w(t)` is the number of ordered pairs of sensors whose difference is `t`. Three things hold for every array: `w(0)` is the number of sensors `N`, since each sensor pairs with itself; `w(t) = w(-t)`, since a pair read backwards gives the opposite lag; and the weights add up to `N^2`, since every ordered pair is counted once. For the ruler that is a stack of 4 in the middle and one block at each of the other twelve lags, `4 + 12 = 16`. A lag between the two ends with weight zero is a hole, and a coarray with no holes is hole-free. Hole-free is what makes the pairs useful. The averages at the lags `-L` to `L`, where `L` is the largest lag, behave like the readings of one long evenly spaced array of `2L + 1` sensors, a virtual array nobody had to build. Methods made for an evenly spaced array can run on the virtual one, and it can pick out more sources than there are real sensors. How far can this go? `N` sensors make `N(N - 1)` ordered pairs of two different sensors, so there are at most `N(N - 1) + 1` distinct lags, counting 0. Put the same `N` sensors one unit apart and they reach only `2N - 1` lags: lag 1 is measured `N - 1` times over and most pairs repeat each other. A sparse array spreads its sensors so that fewer pairs repeat, and the ceiling grows like `N^2`. The ruler meets it exactly, `4 x 3 + 1 = 13`. That is rare: rulers that measure every lag exactly once exist only up to four marks, and from five sensors on some lag is measured twice or not at all. [Moffet 1968](https://doi.org/10.1109/TAP.1968.1139138) asked for the next best thing: for a given number of sensors, the hole-free array with the fewest repeated lags. These minimum-redundancy arrays came from radio astronomy, where every antenna is expensive. They have no formula and are found by search, one size at a time; the ruler is the one with four sensors. Formulas came later. The nested array of [Pal and Vaidyanathan 2010](https://doi.org/10.1109/TSP.2010.2049264) puts two evenly spaced rows end to end: a dense row of `N1` sensors at `1, 2, ..., N1` and a sparse row of `N2` sensors at `N1 + 1, 2(N1 + 1), ..., N2(N1 + 1)`. The differences between the rows fill every gap, so the coarray is hole-free from `-(N2(N1 + 1) - 1)` to `N2(N1 + 1) - 1`. With two and two this is `{1, 2, 3, 6}`, 11 lags against the ruler's 13, but with half the sensors in each row it reaches about `N^2/2` lags for every `N`, no search needed. The coprime array of [Vaidyanathan and Pal 2011](https://doi.org/10.1109/TSP.2010.2089682) takes two evenly spaced rows whose spacings `p` and `q` share no factor: `q` sensors at `0, p, 2p, ...` and `p` sensors at `0, q, 2q, ...`, sharing the sensor at 0. The differences `p i - q j` across the rows are all different, because two of them agreeing would force `q` to divide a difference of two values of `i` smaller than `q`. So `p + q - 1` sensors produce `p q` distinct lags across the rows. Unlike the nested array, its coarray in general has holes. The price of all this is fragility. [Liu and Vaidyanathan 2019](https://doi.org/10.1109/TSP.2019.2912882) call a sensor essential when removing it changes the coarray, and the fragility of an array is the share of its sensors that are essential. The two end sensors are always essential, because only the pair of ends measures the longest lag. In an evenly spaced row of four or more they are the only ones, and the fragility is `2/N`, as low as it gets. In the ruler every sensor is essential: each lag other than 0 is measured by a single pair, so losing any sensor loses six lags. The [companion paper](https://doi.org/10.1109/TSP.2019.2912877) finds the same in minimum-redundancy arrays, nested arrays and Cantor arrays, where every sensor is essential. The fewer the repeats, the less there is to fall back on. The Cantor array builds a large array out of digits. Take the whole numbers whose base-3 digits are all 0 or 1: `0, 1, 3, 4, 9, 10, 12, 13`, and so on, the integer shadow of [the Cantor set](/wiki/cantor-set/). At level `k` there are `2^k` sensors below `3^k`. Subtract two of them digit by digit and every digit of the difference is -1, 0 or 1, with no carrying. Writing numbers in base 3 with the digits -1, 0 and 1 is balanced ternary, and every whole number from `-(3^k - 1)/2` to `(3^k - 1)/2` has exactly one such expansion of `k` digits. So the coarray is hole-free, `3^k` lags from `2^k` sensors. That is only `N^(log 3 / log 2)`, about `N^1.585` lags, short of `N^2`. [Cohen and Eldar 2020](https://doi.org/10.1109/TSP.2020.3016772) keep the digits and change what they are. Pick a small generator array with a hole-free coarray, let the base `M` be the number of lags in that coarray (they call it the translation factor), and take every number whose base-`M` digits all lie in the generator: that is a fractal array. A difference of two such numbers is a number whose digits all lie in the generator's coarray, a full block of `M` digits centred on 0, so the same balanced count fills every lag: `N^k` sensors from a generator of `N`, and a hole-free coarray of `M^k` lags. With the ruler as generator the base is 13, and level 2 puts 16 sensors at `a + 13 b` with `a` and `b` in `{0, 1, 4, 6}`, measuring every lag from -84 to 84, all 169 of them. They also show that a fractal array is at least as robust as its generator. ## In the tree [Sparse arrays](/research/arrays/) reads the fractal array as a digit design, numbers cut out by a rule on their digits, and follows its weights and its essential sensors digit by digit. A coarray is a sum of two sets, `A` and its mirror `-A`, and in one base that sum reads digit by digit; [two bases](/research/cobham/) adds a base-3 digit set to a base-4 one, where that reading breaks down, and [the three plus four demo](/demos/sumset/) lights those sums. The Cantor array is the base-3 set of [the Cantor set](/wiki/cantor-set/), a fractal array is a set of [missing-digit numbers](/wiki/missing-digit-numbers/) with its own digit rule, and its row of sensors, read as zeros and ones, is a [Kronecker power](/wiki/kronecker-product/) of the generator's row of `M` places.