Finding twelve 32-bit numbers with at least 17 bit differences between pairs

Question

Find twelve 32-bit numbers such that each pair of them differs by bits in at least 17 positions.

I'm struggling to find and optimal algorithm for this problem. More general question is: Find 'n' 32-bit numbers such that each pair of them differs by bits in at least 'm' positions.

My first approach was to randomly pick a number or start from any let's say 6 (00000110) and then once again pick other random number. Then make a XOR operation and count how many 1 we have in binary representation of the XOR result which will indicate on how many places the numbers differentiate. If the condition is accepted we can store those two numbers and do the same process until we reach wanted amount of numbers. However such algorithm seems not to be optimal because we are picking random numbers so it could last 'forever'.

*UPDATE I prepared such code and for m = 16 it actually returns 12 results, however for 17 (which I need) it stops at 9 results and code never finishes. I am wondering if it is possible that in [0, 2^32] range there are not such twelve numbers, but how to prove it?

import random

def hamming_distance(x, y):
    dist = 0

    # The ^ operator sets to 1 only the bits that are different
    val = x ^ y
    while val > 0:
        # We then count the bit set to 1 using the Peter Wegner way
        val = val & (val - 1)  # Set to zero val's lowest-order 1
        dist += 1

    # Return the number of differing bits
    return dist


def solution(n = 12, m = 17):
    result = [0]

    while len(result) < n:
        r = random.randint(0,2**32)

        if all(hamming_distance(r,el) >= m for el in result):
            result.append(r)
            print(result)
    
    return result


print(solution())

Yorke

Search for Codes with Hamming-distance m. – Cormac

random picking is actually not that bad of a strategy, you are quite likely to reach something near optimal – Wrapped

For m=16 you have the Reed Muller code RM(1, 5), which gives you 64 32-bit values that all differ from each other by at least 16 bits. I'm wondering whether there's some way to tweak that to get what you want. – Lapland

Answer 1

We construct a set of 12 code words each having 32 bits such that the minimum distance is 17. The outline is

• Using number theory (specifically quadratic residues mod 11), construct a set of 12 code words each having 11 bits such that the minimum distance is 6.
• Make three copies total of each bit, thereby obtaining a set of 12 code words each having 33 bits such that the minimum distance is 18.
• Drop the low-order bit from each code word.

I implement the construction in Python below.

import itertools


def min_distance(code):
    return min((x ^ y).bit_count() for (x, y) in itertools.combinations(code, 2))


quadratic_residues = {pow(x, 2, 11) for x in range(11)}
code11 = {sum(1 << ((y + z) % 11) for y in quadratic_residues) for z in range(11)}
code11.add(0)
assert len(code11) == 12
assert min_distance(code11) == 6

c = 1 + (1 << 11) + (1 << 22)
code33 = {c * x for x in code11}
assert len(code33) == 12
assert min_distance(code33) == 18

code32 = {x >> 1 for x in code33}
assert len(code32) == 12
assert min_distance(code32) == 17
for x in sorted(code32):
    print(hex(x))

Output:

0x0
0x1da3b476
0x3b4768ed
0x4768ed1d
0x68ed1da3
0x768ed1da
0x8ed1da3b
0xa3b4768e
0xb4768ed1
0xd1da3b47
0xda3b4768
0xed1da3b4

Laaland

Could you explain or link to a more detailed explanation of your first bullet? – Cryometer

@Cryometer mathworld.wolfram.com/PaleyConstruction.html is related. I couldn't find the exact construction I describe without more digging. – Laaland

I also couldn't find anything online about this construction, which surprised me a bit. In particular, Quadratic residue codes aren't quite the same thing, since they're linear codes (the sum of two codewords is again a codeword). But I believe the 1st step of David's construction works for any prime p congruent to 3 modulo 4. A key step in the proof is to note that for fixed and distinct i and j in GF(p), the count of values such that x - i is a square and x - j is not a square (or vice versa) is exactly (p + 1) / 2 ... – Lapland

... and to see that, it's enough to look at when (x - i) / (x - j) is a quadratic nonresidue (with x necessarily not equal to j) - it's straightforward to check that there are (p - 1) / 2 solutions x, and that there's then one more x such that either x - i or x - j is zero and the other is a non-residue. That last part is where we require that p is 3 modulo 4, since that guarantees that exactly one of i - j and j - i is a nonresidue. (If p were 1 modulo 4 then either both i - j and j - i would be residues, or both would be nonresidues.) – Lapland

Ah, there we go: exercise 5.7.13, entitled "The Paley 2-design", in "Communication Theory", Goldie & Pinch, CUP, 1991, (ISBN 9780521406062) describes exactly this construction. – Lapland

@Mark I think I learned about it in the context of combinatorial designs. – Laaland

Answer 2

Choosing a code randomly is good for asymptotic channel capacity, but as the argument below shows, you’re right on the edge of what’s possible. Almost surely, if there is a set of code words, it will have some abstract algebraic logic to it.

(Leaving the write-up below for posterity, but basically I re-derived the Plotkin bound.)

Suppose to the contrary that there exists a set of code words W ⊆ {0, 1}³² such that |W| = 12 and, for all {w, x} ⊆ W, we have d(w, x) ≥ 17, where d denotes the number of positions where its arguments differ (Hamming distance). I claim that

∑_w,x∈W d(w, x) ≥ 12·11·17 + 2·6·5 = 2304.

The first term of the right-hand side comes directly from the assumption. The second term arises from a parity argument. Decompose W = E ∪ O where E is the set of code words with even parity and O is the set of code words with odd parity. For all {w, x} ⊆ E, we have d(w, x) ≥ 18, since the distance between two code words of even parity is even. Likewise, for all {w, x} ⊆ O, we have d(w, x) ≥ 18. Hence we have |E| (|E| − 1) + |O| (|O| − 1) ≥ 2·6·5 pairs of minimum distance 18.

Now we apply linear algebra. Let V ⊆ {1, −1}³² be the set of code vectors where we derive a code vector from a code word by replacing each 0 with 1 and each 1 with −1. (The formal element-wise transformation is v[i] = (−1)^w[i].) We have

∑_w,x∈W (32 − 2 d(w, x)) = ∑_u,v∈V (u·v) = ‖∑_v∈V v‖² ≥ 0,

where the first equality comes from relating Hamming distance and dot product, and the rest comes from standard linear algebraic arguments. Double the first inequality and add it to the second:

∑_w,x∈W 32 ≥ 2·2304.

Hilariously enough, both sides are 12·12·32 = 4608. An argument shaped like this rules out 13 code words.

Laaland

Can you please provide some keywords or pointers for the “standard linear algebraic arguments” behind the inequality “∑_u,v∈V (u·v) ≥ 0”? – Dogeared

@Dogeared I added a step. It's the distributive law plus the nonnegativity of the 2-norm. – Laaland

Answer 3

This answer is also a work in progress partial result.

for 17 (which I need) it stops at 9 results

I can do better than that: here are 10 words at distance ≥17:

00000000000000000000000000000000
00000000000000011111111111111111
00000011111111100000000011111111
00111100001111100001111100000111
01011101110001101110001100011011
01111110010010110010110001111000
11011110101100011100000110100101
10101101111100101111110011100010
11100010011111010111001100011100
11110011100011011000111011000011

I am wondering if it is possible that in [0, 2^32] range there are not such twelve numbers, but how to prove it?

I agree with the gut feeling that this might be impossible. Of course any randomized approach can't really provide much value if your goal is to prove the impossibility of something. Particularly in light of David's answer stating that 12 is really at the limit of what you can even hope for.

So I am looking into a systematic search. And I am realizing that this appears to be a huge undertaking, and it may be years before what I describe here can be executed to completion.

Here are some of the tricks that I would consider for a systematic search.

1. You can always XOR all the words with a common pattern without affecting the distances. For this reason, you can pick all zeros as one of the patterns, without loss of generality.

2. The order of the bits doesn't really matter. For this reason, my main modeling approach is essentially a map from subsets of indices to number of bits set. In code this is essentially a map from int to int. Suppose you have an entry 5: 7 in that map. Since 5 = 0b101 = 2⁰ + 2² that means that there are 7 bits which are set in words 0 and 2 but not in word 1 (nor any words >2 if there are any such words being considered). All of this is not counting the all-zero word which in my counting would be at index -1. So the general mode of operation for me is a recursive call, where the arguments are the current depth and this map from index bit pattern to count. The outermost call would be with arguments (0, {0: 32}) meaning that at depth 0 (with only the all-zero word already decided) we have all 32 bits assigned to be set in none of the words.

3. When going from one recursive call to the one one level deeper, you need to essentially split each of the numbers in your map in all possible ways between having them set or not set in the next word. So going with the example above of a map entry 5: 7, if you are now looking at word 3 (bit value 8), that means you want to replace that one entry with all 8 possible splits from 5: 7, 13: 0 to and including 5: 0, 13: 7. You want to do that for every entry of the map, which can be implemented as a second recursive call. As you do so, you can keep track of how much of the budget of common bits you have used up with each of the already defined words. You start out with 15 allowed common bits for every existing word (including the all-zero word), and for every split you update these counts but the moment a budget becomes negative you can return early. This ensures that all the generated splits are actually acceptable based on the permissible minimum distance.

4. The problem is very symmetric: the order of words doesn't really matter. Which means that if implemented you would revisit situations that are essentially the same except for the order of words. To avoid this, I try all possible ways of inserting the latest bit into the index, not just at the highest position. If the one where I insert at the highest position is the lexicographically minimal representation of this map, then I continue to recurse into that extended pattern. If not, I just discard the extended pattern since I will also encounter an essentially equivalent situation for some other order of words.

5. Launching the above as a single binary, it is very hard to get any feeling of progress (or lack thereof). I had it running for a few days and never got past a 9 word example. So I decided to split my program. In the first step I only run the recursion to a depth of 6 words, then I record the map to a file. In the second step I want to process each of these entries to completion. If I do so in a random order, the time needed for each of them should even out over larger numbers, allowing me to predict the total running time.

   The first step is done, and has left me with 450,353,627 different 6-word combinations to proceed with, stored in a 15G file. The next step however shows that each of these cases still takes a really long time to process. I still have to include some time measurement into my codebase, but after 1300h of CPU time I have only got around 60 of the 450M cases completed. By lucky coincidence, one of them led to the 10 word example cited above. This suggests we'd wait for a million years of CPU time for a negative result. If there is a positive result to be had, we might encounter it anywhere along the way, so perhaps that would “only” take half a million years.

6. Taking a closer look at David's answer, observe that he essentially demonstrated that his inequalities need to be satisfied with equality. This means that not only every distance has to be ≥17, but also every distance has to be ≤18. Furthermore, there must be 6 even and 6 odd parity words. Taking these constraints into account should reduce the search space somewhat, at the cost of potentially missing some 11-word combinations. I haven't written code to do this yet.

I haven't uploaded my code yet. Part of the reason is that it is terribly ugly code: there are a dozen slightly different occurrences of the term “index” and “count”, and I need to come up with better names to make that code accessible. Give me a bit more time, and I'll try to write it up in an understandable form.

One other alternative to consider: the map I described has indices from 0 (set in none of the words) through 2¹¹ − 1 (set in all words except the all-zero word). You could treat these 2048 different map values as variables of a mixed integer program, and the condition for the minimal distance as inequalities. Then you could use tools from mixed integer programming to try and find a feasible solution to this. I have some Sage code for modeling the problem in this way, but haven't found a good solution with that in a timely fashion either. Perhaps some super fancy commercial MIP solver can do better than my off the shelve FOSS tools, though.

Dogeared

Answer 4

Work-in-progress: just some thoughts on this problem, not yet a solution.

Let's say a set of 12 such numbers exists. If we flip the i'th bit of all members of this set, we still have a valid solution. Therefore if there's a valid solution, there's one which has all bits set to 0. Let's assume S is such a solution, and find the other elements.

Every other element of S has at least 17 1's. Assume exactly 17 1's until forced to assume more.

WLOG we can let the next element of S have the first 17 bits set to 1, the rest to 0.

I'll define a cohort to be a set of bit indices s.t. all elements currently in S are identical in every index. E.g., at present we have cohorts 00 of size 15, and 01 of size 17, representing the counts of indices where both elements have 0 bits, vs the count of indices where the first elt has a 0 and the 2nd a 1.

In general, we don't care where the indices contributing to cohorts are, just what the cohorts are and their counts. I.e., while 11111111111111111000000000000000 is just one of the choose(32,17) 32-bit ints with 17 1s, these are all equivalent for our purposes, so we only need to track the cohort counts. Let's say f() counts cohorts, so f(00) = 15, f(01) = 17.

For our 3rd elt, we need:

f(000) + f(001) = f(00) = 15, 
f(010) + f(011) = f(01) = 17, 
f(001) + f(011) = 17
f(001) + min(f(010), f(011)) = 17

Here, there are valid solutions for 0 <= f(000) <= 6, with all other counts determined by this choice. My intuition is that as we go along, where we have a choice, we want to maximize the count of cohorts that are unbalanced (mostly 0's or mostly 1's) since in the future a bit set in the opposite direction will buy us more differences, but this may be wrong.

This can only help us with at most a few elements before all cohorts have size 1. And at the 3rd elt we already have 7 possible sets of valid cohorts.

Okay, so what next? There are choose(32,17) ~ 566 million 32-bit integers with 17 set bits. For each set of valid cohorts, we parse this list retaining just those that differ in at least 17 places from each of the elts in the set of valid cohorts we're considering. We can then treat these as nodes in a graph, with an edge between pairs that differ by 17+ bits, and look for cliques of size 12 - (elts in set of valid cohort under consideration). While there's no fast deterministic algorithm for this, there are good randomized algorithms.

Cryometer