Codes for n-dimensional hypercube

Versione italiana

Let's consider two nodes of a cube linked by a diagonal, as in the following picture, the others 6 nodes are connected by a single step to one of the two nodes. Each couple of nodes connected by a diagonal is a code C. C is also called a minimum dominating set with cover radius 1.

Following picture shows the cube (3-hypercube) and the code.

Left image is the cube, right is code C = {0,7}. Note that the green nodes (code) are able to touch with a single step other nodes (white nodes).

The problem of finding a C code is simple to solve for the cube (3-dim hypercube), but what happens if it increases the space dimension?

You can show 4-dimensional hypercube (n-dimensional speaking in general) 

and in this way we are preparing to increasing the space dimension, as shown in the following picture: there are 16 nodes on 5 levels.

Hypercube 4 dimensional with 16 nodes.

This hypercube has 16 nodes because 2^4=16.

We can see it in the follow picture.

Code C =  {0,1,14,15}. 
Codewords are green, ipercube words not in code are white. 
Segments are green and connect a node of code with his parents (the node with only a bit different in binary notation).

If C is a code then all nodes are "touched" at least one time by a green segment: there is no isolated node. 

Cover map in decimal notation      Cover map in binary notation: 
  0 -->   0, 1, 2, 4, 8.                    0000 --> 0000, 0001,0100,0010,1000
  1 -->   1, 0, 3,  5, 9.                   0001 --> 0001, 0000,0011,0101,1001
14 --> 14, 6,10,12 ,15                  1110 --> 1110, 0110,1010,1100,1111
15 --> 15, 7,11,13,14.                  1111 --> 1111,0111,1011,1101,1110

--> means: a node's parents (father or child)

Note 1: a node always cover itself.
Note 2: a node father has always a digit 1 less in binary notation (0000 is father of 0001)
Note 3. a node child has always a digit 1 more in binary notation (0001 is chilld of 0000)

Why use 5 different levels?
Because the number of 1 digits is from 0 to 4:

Level 0
0 = 0000 

Level 1
1 = 0001 2 = 0010 4 = 0100 8 = 1000

Level 2
 3 = 0011  5 = 0101  9 = 1001  6 = 0110 10 =1010 12 =,1100 

Level 3
7 = 0111 11=1011, 13=1101,14=1110

Level 4
15 = 1111

Now, as said 0,1,14,15 green nodes is a code C for the 4-dimensional hypercube.

It is possible to understand in another way: try to union C = {0,1,14,15} and the set of all the childs and the fathers: CP = {1,2,4,8,0,3,5,9, 6,10,12,15, 7,11,13,14}:

C union CP = {0,1,14,15,1,2,4,8,0,3,5,9, 6,10,12,15, 7,11,13,14}
Each ipercube node is in C union CP at least one time.
If only one time then cover coefficient = 1
If two times then cover coefficient crc = 2, and so on.
Here only 0,1,14,15 has crc = 2 (the nodes of code)

What about the sum S of code words?
Here the number of words code is even so there will be a single value for S.
Formula: S = (2 ^ n-1) * (b / 2) =  (2 ^ 4-1) * (4 / 2)  = 15 * 2 ​​= 30.
So all codes has sum S = 30.
Code in the picture has S = 0 +1 +14 +15 = 30.

Hypercube 5 dimensional with 32 nodes.

A more complex code C is found in the following image for the 5-dimensional hypercube: 32 nodes and codes of 7 words (because 7? See reference:  
http://www.sztaki.hu/ ~ / codes /  or 
http:/ / ~ www.eng.tau.ac.il/ litsyn / tablecr / )

C = {2,5,14,22,24,25,27}

What about sum S of code words?

Here the number of words code is odd so there will be a range values for S.

Formula (2 ^ n-1) * (b / 2) computes a closed interval [a, b] where

a =  (2 ^ 5-1) * sub (7/2)  = 31 * 3 = 93, where 7/2 is the first natural number n <7/2  

b =  (2 ^ 5-1) * sup (7/2)  = 31 * 4 = 124, where 7/2 is the first natural number n> 7/2.

So all the codes has sum S between 93 and 124.

About this code S = 2 +5 +14 +22 +24 +25 +27 = 119 .

Note: hyper with 5 dimension is the only one with sum S within a range.

Hypercube 6 dimensional with 64 nodes.

If n = 6 then hyper is 6-dimensional with 64 nodes. Each code has 12 words with sum S=378.

This appears to be a general rule (although there is no evidence I suppose). 

Formula is respected (2 ^ n-1) * (b / 2) with n = dim hyper b = number of code words. 

Therefore: (2 ^ 6-1) * (12/2) = 63 * 6 = 378 (the magic number).

But this has never been proven (I think so) with a theorem. As soon as it happened that all 12 words codes calculated by my algorithm (lots of dozens of them) has 378 as the sum of their words. But this does not mean that there is a code with a different sum.

The number of binomial combination is (64 12) and is the total number of subsets: it is a very great number: 3.284.214.703.056 (over 3 trillion), and among them a lot of sets (although a little% of total sets) are codes covering radius 1. Could it be that a small portion of them may have different sum from 378.

The following is an example of code: C = {3,8,19,20,29,30,37,38, 40, 47,51,56} 

What about the sum S of code words? 

Here the number of words code is even so there only one value for S. 

formula: S = (2 ^ n-1) * (b / 2) =  (2 ^ 6-1) * (12 / 2)  = 63 * 6 = 378.

So all codes has sum S = 378. The image code S = 3 +8 +19 +20 +29 +30 +37 +38 +40 +47 +51 +56 = 378.

Hypercube 7 dimensional with 128 nodes.

If n = 7 then hyper is 7-dimensional with 128 nodes

Formula is again true: S =  (2 ^ 7-1) * (16/2) = 127 * 8 = 1016.

It also happens that each node does not belong to the code is "touched" only once: we have a code perferct (CDC = 1 where CDC is the coefficient of the cover)

Red nodes are even numbers and odd numbers green nodes.

What about the sum S of code words?

Here the number of words code is even so there only one value for S. 

Formula: S = (2 ^ n-1) * (b / 2) =  (2 ^ 7-1) * (16/2)  = 127 * 8 = 1016.

So all the codes has sum S = 1016.

The image code S = 2 +5 +25 +30 +40 +47 +51 +52 +75 +76 +80 +87 +97 +102 +122 +125  = 1016.

Hypercube 8 dimensionalal with 256 nodes.

If n = 8 hypercube has 256 nodes and codes with 32 words. 

The following code has been calculated starting from the previous code for 7-dim hypercube with the addition of another 16 words (126 127, ...140,141) as input for the calculation algorithm. After two seconds of computing time the code has been calculated: the first 16 words code (code exactly half) are the same of the previous code of 7-dim hyper.

C = {2, 5, 25, 30, 40, 47, 51, 52, 75, 76, 80, 87, 97, 102, 122, 125, 134, 139,  144, 157, 161, 172, 183, 186 , 197, 200, 211, 222, 226, 239, 244, 249}

Four important things to note:

1) Sum of words is again  according to the sum formula.

S = (2 ^ 8-1) * (32/2) = 255 * 16 = 4080.

S =  2 + 5 + 25 + 30 + 40 + 47 + 51 + 52 + 75 + 76 + 80 + 87 + 97 + 102 + 122 + 125 + 134 + 139 +  144 + 157 + 161 + 172 + 183 + 186 + 197 + 200 + 211 + 222 + 226 + 239 + 244 + 249 = 4080.

2) There  are 32 nodes with a coverage factor of 2, the same number of code words. About the others 224 nodes of hypercube, value of  this coefficient (CDC) is 1. 
3) None of the nodes with CDC 2 (purple in the following pitcure) is a node of code C too (green nodes).  
4) Sum S 'nodes with cdc 2 (Purple nodes) nodes is 4080. That is S = S'.

What about the sum S of code words?

Here the number of words code is even so there only one value for S. 

Formula: S = (2 ^ n-1) * (b / 2) =  (2 ^ 8-1) * (32/2)  = 255 * 16 = 4080.

So all the codes has sum S = 4080.

Code within the image has 

S =  2 +5 +25 +30 +40 +47 +51 +52 +75 +76 +80 +87 +97 +102 +122 +125 +134 +139 +144 +157 +161 +172 +

183 +186 +197 +200 +211 +222 +226 +239 +244 +249 = 4080.

Hypercube 9 dimensionalal with 512 nodes.

This Hyper C code has 62 words and has been calculated in few seconds.  My research (Alessio Raspanti first code with 62 words was calculated in autumn 1996 after my thesis in which  it was believed that minimum words code number was 64 instead of 62., but after some days my algorithm computes a code of 62 words only. It was a heuristic written in C language and running on a 486 DX2).

There is a little difficut for examininig the picture of code for hyper 9-dim.
Yes, because for every n increase in the number of hyper node is double: so we have so far  hyper examinated with size 3-9: node number are always double: 8,16,32,64,128,256,512.

What about the sum S of code words?

Again  the number of words code is even so there only one value for S. 

Formula: S = (2 ^ n-1) * (b / 2) =  (2 ^ 9-1) * (62/2)  = 511 * 31 = 15841.

So all the codes has sum S = 15841? No.

Code within the image has in fact S = 15830:
S = 4 +6 +7 +13 +14 +15 +50 +53 +57 +60 +83 +88 +96 +97 +106 +127 +144 +145 +154 +163 +168 +191 + 197 203 + 204 +214 +221 +230 +237 +244 +246 +257 +264 +283 +299 +304 +306 +310 +317 +322 +329 + 340 +341 +350 +359 +364 +386 +393 +407 +412 +420 +421 +430 +448 +450 +463 +497 +499 +504 +505 + 506 +507 = 15830.

Now, 62 codes has sum S = 15830, there is a difference of 11 calculated from the formula of the sum S.

So, sum S formula about words code C with cover radius 1 is no longer valid if hyper is 9 dimensional.

The unexpected is that in 1996 the minimum number of words was believed in [54,64], so it was usual to start with the search of  64-words code. 
All such code has S = (2 ^ n-1) * (b / 2) =  (2 ^ 9-1) * (64/2)  = 511 * 32 = 16352, so I thought that 64 was the minimum value.
A day with great surprice my algorithm calculated a 63 words code. But a word was redundant because without it the 62-set was a code too.
So: there isn't a code with 63 words: all the code calculated with 63 words has a redundant words, so code is 62-words.
There has been calculated a lot of 62-words and usually sum is different from  
S = (2 ^ n-1) * (b / 2) =  (2 ^ 9-1) * (62/2)  = 511 * 31 = 15841.
What is minimum?
I tried with 61 words: it is computationally relevant that in a few seconds algorithm is able to calculate sets which cover only 506 (98.82%) nodes of hyper and no more after hours of computational time.

Hypercube 10 dimensionalal with 1024 nodes.

Now a great battle: in this hyper minimum is not known again, it is supposed to be near 120 words.

Lower-upper bound interval suggested is [107-120]. 

I calculated a lot of codes with 120 words and the formula is no valid.

In this case S = (2 ^ n-1) * (b / 2) =  (2 ^ 10-1) * (120/2)  = 1023 * 60 = 61380. Code with 120 words have usually a different sum, so formula is false.

But the question is: is really 120 the minimum number words code of a code able to cover all the 1024 nodes? 

I tried input of 119 words and it has been like to climb a very high mountain.

Why? Because algorithm is able to calculate sets covering 1022 on 1024 nodes in a computational time of minutes. Then no more improvments in hundreads and hundreads of attempts. 
But in 23 may 2013, 03:24 a.m., it has been calculated a set (which I call the almost code) with 119 words able to cover 1023 nodes!!  

It is the best result found so far and despite a lot of running program, no such result has been happened again... to boldly go where no man has gone before! 

Recently (october 2014), program is running since 21 september (three weeks) and has examinated 4,500,000,000,000 sets with 119 nodes... the best result is a great number of sets covering only 1022/1024 hyper nodes. 
Really, I expexted that program was able to find another set covering 1023/1024, but it was a only hope I see.
So, how many could be the sets able to cover 1023/1024 hypercube nodes? I'd like to remeber that the number of possible sets is (1024 119) ~= 2.3975 *10 ^ 158. So, if we suppose that there is only a set (able to cover 1023 nodes) inside an imprecisated number of thousand billions, it is possible to argument that could be a set (able to cover 1023 nodes)  among 5 (or 6) thousand billions sets.
So, if there are (1024 119) ~= 2.3975 *10 ^ 158 set, it is possible to have around a number of 10^147 sets covering 1023 nodes: a great number of them even if only one has been calculated so far.
But it is not the only one because of his derived set (no time now, discussion in next days). Good by everyone following hypercubes.