Testwiki:Reference desk/Archives/Mathematics/2012 December 19

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < December 18 ! width="25%" align="center"|<< Nov | December | Jan >> ! width="20%" align="right" |Current desk > |}

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)

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)

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)

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)

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)

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)

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)

I suppose you mean number of edges per node. The actual number of edges is $\mathrm{\Theta }(2^n{n}^2)$. -- Meni Rosenfeld (talk) 10:41, 21 December 2012 (UTC)

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)

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

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)

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)

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)

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)

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)

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)