December 19 Information

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 ${\displaystyle {\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 ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle n=7}$, and based on the complexity described in the article this isn't surprising. For ${\displaystyle n=8}$ it would take an order of ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle {\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