# Hamming Distance

1. Mar 9, 2008

### 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.

Last edited: Mar 9, 2008
2. Mar 9, 2008

### 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?

3. Mar 9, 2008

### 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.

4. Mar 9, 2008

### 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

5. Mar 9, 2008

### asdf1234

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.

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

Last edited: Mar 10, 2008
6. Mar 11, 2008

### John Creighto

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?

7. Mar 11, 2008

### 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.

Last edited: Mar 11, 2008
8. Mar 11, 2008

### 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.

Last edited: Mar 11, 2008
9. Mar 12, 2008

### etaoin shrdlu

00000
00111
11100
?
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?

10. Mar 12, 2008