Calculating Hamming Distances in 5-Bit Binary Sets

[asdf1234]

Hello,

I'm working on a proof and I would like some help. I need to show that any set of 6 distinct 5-bit binary numbers must have at least 5 distinct pairs of elements with Hamming distance less than or equal to 2.

Hamming distance is the sum of the absolute value of each pair of coordinates: the distance between 000 and 111 is

|0-1|+|0-1|+|0-1|=3

Any help would be appreciated.

 

[rodigee]

Could you define what you mean by "pairs of elements" and 5-bit binary? I don't know what either of those are.

But without even really understanding the problem my first thought is the infamous pigeion-hole principal. Have you had any luck trying it?

 

[CRGreathouse]

Take an element A. (If it helps, you can assume without loss of generality that it's 00000.) If all other elements are within Hamming distance 1 or 2 ("close"), you're essentially done. (You'd have to show this, of course.) Otherwise, there is an element B with Hamming distance 3 or more ("far") from A to B. (If it helps, you can split this into 3 cases WLOG, where B is 00111, 01111, or 11111.) Now you can group the remaining elements into three groups: those close to both A and B, those close to A but far from B, and those close to B but far from A. If you can limit the size of one of the latter two, you're done.

On the other hand, you could try a pigeonhole approach.

 

[John Creighto]

My attempt at a counter example failed. Why not just use a computer to test all possibilities.

A: 01010
B: 11001
C: 01100
D: 00011
E: 11101
F: 00011

|A,B|=3
|A,C|=1
|A,D|=2
|A,E|=3
|A,F|=2
|B,C|=3
|B,D|=3
|B,E|=2
|B,F|=3
|C,D|=2
|C,E|=2
|C,F|=3

 

[asdf1234]

Take an element A. (If it helps, you can assume without loss of generality that it's 00000.) If all other elements are within Hamming distance 1 or 2 ("close"), you're essentially done. (You'd have to show this, of course.) Otherwise, there is an element B with Hamming distance 3 or more ("far") from A to B. (If it helps, you can split this into 3 cases WLOG, where B is 00111, 01111, or 11111.) Now you can group the remaining elements into three groups: those close to both A and B, those close to A but far from B, and those close to B but far from A. If you can limit the size of one of the latter two, you're done.

On the other hand, you could try a pigeonhole approach.

This seems like an interesting approach. The only problem I can see running into is how to determine how many pairs have been discovered with each element 'close' to A or B. I guess it would be the number 'close' plus 1 (A or B) choose 2, but how would I know the total amount? Would I have to do cases for the amount 'close' to A, B, etc.? I'm not totally sure I understand.

Any idea how the pigeonhole argument would work in this scenario?

Thanks for the input guys.

My attempt at a counter example failed. Why not just use a computer to test all possibilities.

A: 01010
B: 11001
C: 01100
D: 00011
E: 11101
F: 00011

|A,B|=3
|A,C|=1
|A,D|=2
|A,E|=3
|A,F|=2
|B,C|=3
|B,D|=3
|B,E|=2
|B,F|=3
|C,D|=2
|C,E|=2
|C,F|=3

You didn't test every pair. There should be 6 choose 2 = 15 pairs.

 

[John Creighto]

You didn't test every pair. There should be 6 choose 2 = 15 pairs.

Oh, I stopped because I was only looking for 5. I didn't read carefully enough. By chance does this problem have anything to do with noise immunity and error checking?

 

[dodo]

I have a sketch for a proof, but at this moment it is terribly informal. Here it goes.

For one given element A (without loss of generality, 00000), the count of 5-bit elements with distance 0,1,2,3,4,5 to A are resp. 1,5,10,10,5,1. Thus A partitions the 5-bit space in exactly half: 16 with distance > 2, and 16 (in this case, including A) with distance <= 2.

Now the informal part. How would you distribute 6 elements to minimize the number of close pairs? If you choose to place the first 4 elements A,B,C,D, two at one extreme (say, A,B) and two at the other (C,D) of the 5-bit range, with those 4 elements you can form 2 pairs (AB, CD), and when placing the 5th element, it will get close to either AB or CD, thus forming other 2 pairs (f.i, AE, BE). The moment you place the 6th, you will have more than 4 pairs.

Alternatively, if you space equally the first 4 elements, you will have 3 pairs (AB, BC, CD); the moment you add a 5th, it will be close to other two. And you still have a 6th element to place.

Terribly informal, I warned you, just a sketch. I think we need a topology guy.

P.S.: I said "topology", because I think the Hamming distance is a metric on the 5-bit space, thus I suspect the triangle inequality d(A,C) <= d(A,B) + d(B,C) will play a major role in a proof, possibly on the lines sketched above.

 

[John Creighto]

I can show there is atleast 5 as follows:

It is easy to show that given any three 5 bit binary numbers there must be at least one pair with a hamming distance less then two.

Now with 6 binary numbers there are 6!/(3!(6-3)!=20 ways to choose 3 of the 6 binary numbers. Now for any 3 of the 5 digit binary numbers there can be at most 3 other choices of 3 from the 6 numbers which share the same pair that has a hamming distance less then or equal to 2. Consequently of the 20 choices of 3 numbers which contain a pair with hamming distance less then or equal to 2 the redundancy can be no greater then 4. Consequently there must be at least 20/4=5 pairs which have a hamming distance less then or equal to 2.

 

[etaoin shrdlu]

It is easy to show that given any three 5 bit binary numbers there must be at least one pair with a hamming distance less then two.

What about
00000
00111
11100
?

Why not just use a computer to test all possibilities.

I second this suggestion. The search space is tiny, and if you're still looking for a proof, what you find may surprise you.

What reasons do you have to believe that the statement is true?

 

[rodigee]

I:
It is easy to show that given any three 5 bit binary numbers there must be at least one pair with a hamming distance less then two.

Are you sure about that?

I tried creating a pigeonhole argument, but just wound up creating more problems. My idea was to do something like this:

Let S = {A,B,C,D,E,F} be our set of 6 5-bit binary numbers. There are 15 pairs of these 6 numbers. Suppose there are only 4 pairs with a Hamming Distance of 2 or 1 and find a contradiction.

Given any distinct pair, they can have a Hamming Distance of 1, 2, 3, 4, or 5. We assumed there are only 4 having a Hamming Distance of 1 or 2, leaving 11 pairs with a Hamming Distance of 3, 4, or 5. Therefore, at least one of those distances must have at least 4 pairs with that distance.

Clearly, there can't be 4 pairs of distance 5 since we only have 6 numbers and we'd need 8 numbers for that to happen. So can there be 4 pairs of distance 3? 4 pairs of distance 4? I have no idea... this is where I think going this route does more harm than good.

On a side note, something cool I noticed while pigeon-holing around is that if you select any two digits, say the 1st and 4th digit, there will be at least one pair of our numbers whose digits match there.