# Binary labelling

I learned of this question from a man in England and I find it fascinating.

You have a number of portraits which are distinguished from each other by binary labels. For example, in each portrait the person has either brown eyes or blue eyes and in each of the portraits the person is wearing a hat or not wearing a hat.

Now you want to consider a collection of portraits so that each portrait differs from each other portrait by at least four traits.
The question is if there are $$n$$ binary traits what is the largest number of portraits you can have so that any two portraits in the collection differ by at least four traits.

I approached this problem as follows. We work with binary numbers and we write the digits in reverse order.
So zero is 00000000000000, where here we are working with fourteen binary digits.
Now 1 = 10000000000000 and 2 = 01000000000000 and 7 = 11100000000000000 and so on.

Now let us start with 0 = 00000000000000. I wrote a computer program that looked a the numbers 1,2,3,4,.... until it found a number that differed from zero in four places. That number was 15 = 111100000000000000. Then the program went on look at 16,17,..... until it found a number that differed from 0 and 15 in at least four places. That number was 51 = 11001100000000. Continuing in this way the program found the next number is 60 = 00111100000000. Below I will write out the first few numbers.

    1    00000000000000
2    11110000000000
3    11001100000000
4    00111100000000
5    10101010000000
6    01011010000000
7    01100110000000
8    10010110000000
9    01101001000000
10    10011001000000
11    10100101000000
12    01010101000000
13    11000011000000
14    00110011000000
15    00001111000000
16    11111111000000
17    11000000110000


Here is what I found.

number of digits number of portraits that all differ by four or more digits
4 2
5 2
6 4
7 8
8 16
9 16
10 32
11 64

From here on every time you add another digit you double the number of portraits. I have check this up to 512.

What I believe but can not prove is that this method is optimal so, for example, if you have 12 binary traits the largest number of portraits that all differ by at least 4 binary traits is 128. The other thing is that each of the binary numbers has an even number of ones.
Also, I believe but can not prove is that if there are n binary traits where n > 9 then the maximum number of portraits you can have that differ by at least 4 binary traits is 2^(n-5).

• The question may be restated (in a more graph-theoretic way) as: find a maximal subset of vertices in the hypercube graph $Q_n$ such that the distance of every pair of vertices in this subset is at least 4. Commented Nov 23, 2022 at 15:11
• If we change the distance condition to "at least 3" there's a quick solution by observing that every vertex in $Q_n$ has $n$ neighbours, and the neighbourhood of any two vertices in the subset should not intersect. This method gives a upper bound for all "odd distance conditions" and is sharp in the 3 case, but I believe it fails in the even case. Commented Nov 23, 2022 at 15:17
• For what it's worth, this can be seen as a coding theory problem. For a given value $n$, what is the largest possible (i.e., most codewords) length $n$ binary code you can have so that the minimum (Hamming) distance is $4$. I suspect this is a hard problem to get a fully general answer for. Commented Nov 23, 2022 at 17:53

What you are constructing is known as a lexicographic code, or a lexcode for short. Lexcodes are pretty good, but usually not optimal. For example, it is possible to find $$20$$ binary vectors of length $$9$$ such that any two differ in at least four places, whereas you only found $$16$$. This following example was taken from the Sloane and MacWilliams book cited at the end, p. 57.

000 000 000
111 001 010
111 100 001
111 010 100
010 111 001
001 111 100
100 111 010
001 010 111
100 001 111
010 100 111
100 110 101
010 011 110
001 101 011
101 100 110
110 010 011
011 001 101
110 101 100
011 110 010
101 011 001
111 111 111


In general, finding the largest code of a given length and distance is an open problem. This website by Andries E. Brouwer gives a table of the best known bounds on binary codes. The $$d=4$$ column is what is relevant to your question.

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978.