Mathematics desk
< December 18	<< Nov \| December \| Jan >>	December 20 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 19

# of points where hamming distance >= 3 in {0,1}^n?

Is there an easy way to calculate the maximum number of points in {0,1}^n where the Hamming distance from any point in the set to any other point in the set is 3 or greater? For {0,1}^3, the answer is 2 ((0,0,0),(1,1,1)). For {0,1}^4, the answer is also 2, however for {0,1}^5, the answer is at least 4 ((0,0,0,0,0),(0,0,1,1,1),(1,1,0,1,1),(1,1,1,0,0)). Does anyone have a way to calculate this or a pointer to an OEIS sequence for this?Naraht (talk) 22:01, 19 December 2012 (UTC)[reply]

I think the first terms are 1, 1, 2, 2, 4, 8, 16. I could find no relevant match on OEIS.

You have the upper bound

{\frac {2^{n}}{n+1}}

in case that helps. -- Meni Rosenfeld (talk) 19:14, 20 December 2012 (UTC)[reply]

I went looking for anything in OEIS with 2,2,4 in it and didn't find anything useful. I had found it as an upper bound, but given that it doesn't work for n=4, I'm not sure how close it stays.Naraht (talk) 20:19, 20 December 2012 (UTC)[reply]

I think the upper bound should actually be quite good even for large n.

I don't know what is the procedure for adding sequences to OEIS but this seems like a good fit. -- Meni Rosenfeld (talk) 10:41, 21 December 2012 (UTC)[reply]

I'd want to be fairly sure of the values through n=9 before I put to OEIS.Naraht (talk) 11:34, 21 December 2012 (UTC)[reply]

Also, this is a special case of Independent set (graph theory), where there are

2^{n}

nodes and they are connected by an edge if their hamming distance is 1 or 2. So the algorithms for that apply. -- Meni Rosenfeld (talk) 19:18, 20 December 2012 (UTC)[reply]

I'm pretty sure that the graph would be sparse since the number of edges is O(n^2) while the nodes are 2^n. So at least calculating it wouldn't be insane.Naraht (talk) 20:19, 20 December 2012 (UTC)[reply]

I suppose you mean number of edges per node. The actual number of edges is

\Theta (2^{n}n^{2})

. -- Meni Rosenfeld (talk) 10:41, 21 December 2012 (UTC)[reply]

Mathematica has built-in independent set algorithms. It's currently choking on

n=7

, and based on the complexity described in the article this isn't surprising. For

n=8

it would take an order of

10^{21}

operations so it's pretty much impossible with my current setup. The only hope would be to find a better algorithm that makes use of the special case. -- Meni Rosenfeld (talk) 10:56, 21 December 2012 (UTC)[reply]

Well, what did you get for n=1 through 6?Naraht (talk) 19:17, 21 December 2012 (UTC)[reply]

The same results that I wrote earlier (most of them are obvious). Also, while I couldn't solve for

n=7

with the generic method, the answer is obviously 16 (Hamming(7,4)). Lower bounds are also easy to come up with using Monte carlo methods, for

n=8

the answer is at least 20 (and at most 28). This is the highest I found after 100,000 iterations so it might be the right answer or close to it.

Apparently this sequence start is unique, so I see no reason not to add to OEIS with the 7 known terms. -- Meni Rosenfeld (talk) 16:05, 22 December 2012 (UTC)[reply]

In other words, you are asking for the maximal size of an error-correcting code of distance 3, length n. This may help you searching for more information, though most of the literature on the theory of error-correcting codes concentrates on linear codes. (Strangely enough, we have about a million of articles on particular ECC, and a software engineer’s introduction to the subject here, but I couldn’t find any article discussing the theory.)—Emil J. 19:55, 20 December 2012 (UTC)[reply]

Yeah, I looked through the Error Correcting codes and didn't find anything on building ones, just on ones that had been created. The problem that I read was originally stated as how many possible distinct messages can be sent using n bits if a malicious opponent *may* change exactly one bit. I'm pretty sure that this is an equivalent problem. This leads to the question of whether more distinct messages can be sent if the malicious opponent *must* change exactly one bit.Naraht (talk) 20:19, 20 December 2012 (UTC)[reply]

Well, there's Coding theory, but not knowing much about it myself I don't know what is missing. -- Meni Rosenfeld (talk) 11:27, 21 December 2012 (UTC)[reply]

Well, Hamming bound applies with q=2 and t=3/d=1. which does simplify in that case to the ${\frac {2^{n}}{n+1}}$ mentioned earlier.Naraht (talk) 11:44, 21 December 2012 (UTC)[reply]

The first terms are given by 1, 1, 2, 2, 4, 8, 16,20,40,72,144,256,512, 1024,2048. This follows from this online table [1]. You will find many other (recent) results there. It is quite well known that if n is a power of 2 minus 1, then you can attain the bound \frac{2^n}{n+1} by constructing a Hamming code (this can be generalized to non-binary codes). In fact, there is a strong link between caps in projecive geometry and linear codes with certain minimum distance, using a [[parity-check matrix]. See for instance [2].

Evilbu (talk) 18:04, 22 December 2012 (UTC)[reply]