How few distances fix a word

The theory of error-correcting codes is about spreading words apart in the cube of all binary strings, so that a corrupted word stays closest to the one that was sent. All of that is about moving words so that distances tell them apart. There is a converse question, older than it looks and with a different kind of answer. Suppose the unknown is the word itself, and the only thing that can be measured is its distance from words of one’s choosing. How many of these measurements are needed to know the word exactly?

The trivial answer is $n$, or less. The word of all noughts gives the number of ones, and comparing with a word with a single 1 in position $i$ then reveals bit $i$. That is $n$ questions asked about $n$ bits, and each answer seems to be used as a yes or no. But a distance can be any number from nought to $n$, so one answer holds more than one bit of information, potentially up to $\log_2(n + 1)$ bits. Much less than $n$ might be enough. And there is the second question of whether the list of queries must be adapted as the answers arrive or can be written down in advance.

A set of words that fixes everything by its distances is called resolving, and the size of the smallest such set is the metric dimension of the cube. For small cube sizes it is a straightforward computation, and the numbers run almost on the diagonal: 1, 2, 3, 4, 4, 5. Further out they fall away from it, and the way they do so turns out to be the same in coin weighing, in Mastermind and in many other things that do not look like questions about distance at all.

Counting the landmarks #

In a resolving set the landmark words are fixed in advance and the unknown is one of the $2^n$ words. For it to be determined, the $2^n$ lists of distances must all be different. So finding a smallest one is a search over choices of landmarks, with the test being whether all the lists differ.

The search has a useful symmetry. The cube can be flipped: replacing every word $x$ by $x \oplus w$ keeps all distances unchanged and carries $w$ to the word of noughts. So some landmark may as well be all noughts. That reduces the search by a large factor, and a complete search is possible up to six bits, where it tries 48,865 sets of landmarks and proves that four are not enough and five are.

From six bits up the exhaustive search becomes impractical in the time available, and a random search with local repair is used. It finds resolving sets of size 6, 6, 7 and 7 at seven, eight, nine and ten bits. Those values match the published minima, which were established with more elaborate methods. The search gives upper bounds on its own, and it has not been used to prove anything is impossible. In the published table the same slow growth continues, and at length 10 it takes seven landmarks to fix a word in which there are three more bits than landmarks. That is hardly a triumph. Still, the trend is real, and the shape of the true answer is much more interesting than these small values suggest.

The counting bound under the curve is easy to state. With $k$ landmarks there are at most $(n + 1)^k$ lists of answers, and these must separate $2^n$ words, so $k \ge n/\log_2(n + 1)$. That bound is out by a factor of two, for a reason worth seeing, because it is about what a distance really measures.

A balance and a signed sum #

Distance to a landmark $w$ is a sum of contributions from each bit. If $w_i = 0$, bit $x_i$ contributes $x_i$ to the distance. If $w_i = 1$, it contributes $1 - x_i$. Therefore

$$d(x, w) = |w| + \sum_{i} (1 - 2w_i)\, x_i.$$

The first term is known. So the measurement reveals a signed sum of the unknown bits, where the sign pattern is chosen by the landmark. In other words it is a balance scale with two pans. Each coin is good or one gram heavy, $x_i = 1$ meaning heavy, and a landmark is a placement of each coin in one pan or the other. The balance reports the difference in grams between the pans.

That problem had already been asked, on its own account. Hermann Shapiro posed it in 1960 for a spring balance, weighing subsets of coins with known good and bad weights. Paul Erdős and Alfréd Rényi proved the leading term soon after, and the same mathematics was found several more times.

The balance question lets a coin stay out of both pans, which the distance formula does not, but the two differ in a small way: a coin in neither pan would be a coin ignored by the landmark, which is exactly what a distance cannot do. It changes the numbers slightly and not the rate.

So here is a remarkable thing to look at. The table fixes seven weighings before any coin is touched, and they determine which of twelve coins are heavy, for every one of the 4,096 possible answers. No answer is used to choose a later weighing. The check was exhaustive: every set of coins was put through the table and the lists compared. Twelve bits have been read with seven measurements, none of them looking at any bit alone, and nothing about the pattern of pans hints that it would work.

Why half a logarithm #

The table comes from a recursion. If $A$ is a table of $k$ weighings for $n$ coins with this property, a larger one has $2k + 1$ weighings for $2n + k + 1$ coins:

$$\begin{pmatrix} A & A & I & 0 \\ A & -A & 0 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix}.$$

It can be read off directly why this works. Adding the first two blocks of readings cancels the second copy of the unknowns and doubles the first; the block with the identity adds each of its bits unmixed, and the parity of each sum therefore reveals those bits, since everything else is doubled and even. With the identity-block bits known, the two copies follow from $A$’s property, by induction. The one-coin table $[1]$ then gives 3 weighings for 4 coins, 7 for 12, 15 for 32, and $2^m - 1$ for $m \cdot 2^{m-1}$. Those are the constructions of Bernt Lindström in 1964 and David Cantor and W. H. Mills in 1966.

So $k$ weighings read about $\tfrac12 k\log_2 k$ coins, and at 255 weighings the table reads 1,024 coins, at four coins per weighing. And this matches a lower bound. A reading is not spread evenly over its $n + 1$ possible values: by the same fluctuation that makes an average settle, a reading of $n$ independent coins is concentrated in a range of width about $\sqrt n$. It holds about $\log_2 \sqrt n$ bits of information, which is half of $\log_2 n$. So each measurement delivers half as much as the naive count supposes, and the true number of questions is about

$$\frac{2n}{\log_2 n}.$$

The factor of two that the naive count missed is entropy, in the sense of the measure Shannon built channel capacity from. The answers are bunched near the middle, and an answer that is usually near the middle tells less than one that could be anywhere. So to find a word of a thousand bits by distances, about two hundred are needed. There is a further surprise in what these constructions do not need, which the best a code can be would have no occasion to ask: adaptivity. The questions were fixed in advance, and adaptive questioning can at best shave lower-order terms. The information in each answer is limited, whichever word is asked about next, and a fixed table of the right shape attains it.

Mastermind #

There is a well-known game with exactly this form. Four pegs, six colours, so 1,296 possible codes. A guess is answered by the number of pegs of the right colour in the right place, and the number of the right colour in the wrong place. Mordecai Meirowitz invented it around 1970. It is a resolving problem with a larger alphabet and a second number in each answer, and the first number by itself is a Hamming distance on four symbols.

So the question is what to guess. Donald Knuth analysed this in 1977, with a simple rule. After each answer, the remaining codes form a set; a guess splits that set according to the answer it would receive; choose the guess whose largest class is smallest. In other words, plan for the worst answer. Note that the best such guess need not be a code that could still be the secret.

Run exactly over every code, starting from the guess 1122 that Knuth’s rule selects, the rule finishes one code at the first guess, six at the second, 62 at the third, 533 at the fourth and 694 at the fifth, and it never needs a sixth. The mean is 4.476 guesses, which is 5,801 over 1,296, in agreement with Knuth’s paper. The minimax is not the best average. Kenji Koyama and Tony Lai found by exhaustive search in 1993 that the optimal mean is 4.340 guesses, but it needs a rule that takes six guesses on one code. No rule both minimises the mean and keeps every code within five, and the first guess shows the same disagreement in miniature.

There are only five essentially different openings, since colours and positions can be renamed. The guess 1111 is the weakest, leaving a class of 625 codes among the five possible answers, and giving 1.498 bits of information. The guess 1122 has the smallest worst class, at 256, with 2.885 bits. The guess 1123 has a larger worst class of 276 and 3.044 bits; and 1234 has the largest worst class of the three, 312, and the most information of all, 3.057 bits. These are two different objectives and each opening wins by one. With $\log_2 1296 = 10.34$ bits to find and about 3 bits available per guess at most, the theoretical minimum is between three and four guesses, and the actual 4.340 shows how much the answers overlap once several guesses have been made. A later guess is limited by what earlier answers have already revealed.

Where the two versions meet #

Vašek Chvátal made the link explicit in 1983. The static version of Mastermind, where all guesses are written down before any answer, is exactly the metric dimension of a graph of words with $k$ symbols, ignoring the white pegs. For long words his result is the same shape as the coin problem: about $2n\log_2 k/\log_2 n$ guesses are needed, for $k$ colours and $n$ positions when $n$ is large against $k$. So the number of questions grows almost linearly with the information to be found, with the logarithm in the denominator measuring the concentration of one reading.

The relation with coding theory is close, and it goes the other way round from the usual uses of distance. A code chooses a set of words whose distances from one another are all large, in order that a received word has one nearest neighbour. A resolving set chooses landmarks whose distances to every word are jointly unique, in order that a word is known by what it is measured against. The Hamming decoder of finding the error without reading the message is a resolving procedure of another kind: it computes linear checks whose answers uniquely identify an error position. If the unknown is an error pattern with a single 1 among 15 bits, four parity checks find it, because the checks form a table that distinguishes all its columns. Syndrome decoding is therefore a detection table over the two-element field, and the coin-weighing table is one over the integers. The integers allow carries, and those carries are the source of the extra factor of a half of a logarithm.

Other things this measures #

Weighing with a noisy balance is an information question of the same kind, and there the answer returns to the capacity of a channel. Group testing, where a blood test reports only whether any of a pooled set is positive, uses a very weak form of answer, a single bit, and there the number of tests goes as the number of positives times a logarithm rather than as $n/\log n$. A linear sensing problem is the same question over the real numbers, with sparsity as the assumption that makes it solvable, and it links directly to the uncertainty results about a few frequencies.

A striking relative is the question of how hard the logical puzzle is rather than how few questions it needs. Given a list of Mastermind answers, deciding whether any code is consistent with them is NP-complete, as Jeff Stuckman and Guo-Qiang Zhang proved in 2006. So a player has an awkward thing to do at each step. Knuth’s analysis worked by holding the list of remaining codes, and for four pegs the list is short. At twenty pegs, working out even one consistent code to guess next is a problem with no known efficient method. The information bound says that few questions suffice; it says nothing about how to process the answers. Bernt Lindström’s table, by contrast, comes with an efficient decoder as part of its structure, and that is a further reason to be interested in explicit constructions.

Which of these numbers are proved #

The figures rest on checks of different strengths. The least sizes through six bits are proved by exhaustion over landmarks including the all-nought word. Those from seven to ten are upper bounds found by a random search starting from the published value, and the values below them are taken from the literature. The seven-by-twelve table was tested on all 4,096 sets of coins, and the three-by-four on all sixteen. The fifteen-by-thirty-two table has more cases than can be tried in reasonable time, and it was tested on 400,000 random pairs with no repeated reading, which supports but does not by itself establish the recursion; the argument above does that.

Knuth’s rule is run in full on all 1,296 codes, with ties broken in favour of a guess that could still be the secret and then by the earliest guess in order, and it yields Knuth’s published distribution. The optimal mean 4.340 is cited and was not recomputed. The figure of about $2n/\log_2 n$ is an asymptotic statement, and on the small sizes drawn it is not yet accurate. The rule that the first few values sit near the diagonal is what small cases should be expected to do, not a contradiction.

Still open: the metric dimension at each length #

What is the metric dimension of the cube at every length? The leading term is known. The exact values are not, beyond a small range. Computations reach somewhat further than the table here, using integer programming and heuristic search, and beyond a modest length only upper bounds are available. The exact sequence has no known closed form, and it has irregular plateaus such as the repeated 4 and the repeated 6 that the leading-term analysis is too coarse to explain. The lower-order behaviour, whether the true value is $2n/\log_2 n$ plus a smaller term of a regular form, is not settled. Even with adaptive questions, the exact count is unknown beyond small cases.

Mastermind has its own version. With $n$ positions and $k = n$ colours the number of guesses needed has been narrowed to between about $n$ and $n\log\log n$ by Doerr, Doerr, Spöhel and Thomas and others, a very fine gap for a problem of this flavour, and closing it would need a new way of arguing about adaptive guessing.

Half of a logarithm per question #

To fix a word by its distances from chosen words takes about $2n/\log_2 n$ measurements, because each distance is a signed sum of the bits and a sum of $n$ bits carries only half of $\log_2 n$ bits of information. A balance reading twelve coins with seven weighings fixed in advance attains it at small scale, and a doubling construction attains it for ever. Mastermind plays the same game with six colours, and Knuth’s rule solves all 1,296 codes in five guesses at most.

A code separates its words so that distance points back to the sender. A resolving set does the reverse, using distance as the only instrument. What it shows about that instrument is exact. A distance is a much better measurement than a single bit, and a much worse one than the number of values it can take would suggest. The difference between those two statements is a spread of $\sqrt n$.