Hamming Distance

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

[latex]|0-1|+|0-1|+|0-1|=3[/latex]

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

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.

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?

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

What about
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?

rodigee

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.