of a n-dimensional hypercube using at most K colors

The purpose of this document is to (make a program to) find a[n], defined as the title.

Two ways of coloring are regarded as the same
if they are conjugated by a permutation of the vertices caused by a rotation of the hypercube.

According to the Pólya enumeration theorem, a[n] = ∑K^{cy(g)} (g∈G')/#(G'),

where G' is the set of all permutation of the vertices caused by a rotation,

and cy(g) is the number of the cycles of the g, explained more precisely later.

Symbols: ∑: sum, ∏: product, R: real number. Assume n to be a positive integer.

We use ordinary n-dimensional cartesian coordinate system R^{n}: {(x_{1}, x_{2}, ..., x_{n}); x_{i}∈R}.

__Define__ **e**[i] as the i-th basis vector, with the direction of the axis x_{i}, and the size of 1.

Consider the 2^{n} points described as (±1, ±1, ..., ±1) are the vertices of the hypercube.

Let g be a linear mapping from R^{n} to R^{n}, and v be a subset of R^{n}.

g(v) means the image of v by g, and g^{k}(v) means the image of v by k-times g.

__Define__ G^{n} as a set of linear mapping g from R^{n} to R^{n} satisfying:

(1) For each basis vector **e**[i], there exist k and g(**e**[i]) = **e**[k] or g(**e**[i]) = -**e**[k]

(2) If i≠j, then g(**e**[i])≠g(**e**[k]), g(**e**[i])≠-g(**e**[k]).

Let g∈G^{n}, so for each e[i], there exist k and g(e[i]) = e[k] or g(e[i]) = -e[k].

__Define__ a n-number permutation σ_{g} and a n-term sequence {κ_{g}} as following:

If g(e[i]) = e[k] then κ_{g}[i] = 1, and otherwise κ_{g}[i] = -1,
and for the both case, σ_{g}(i) = k.

In other words, g(**e**[i]) = κ_{g}[i] **e**[σ_{g}(i)].

On the contrary, any pair of σ and {κ} gives different g satisfying (1),(2) above,

if σ is n-number permutation and {κ} is n-term sequence with each term 1 or -1.

**Claim 1**: All permutations of the vertices of hypercube by rotation are included in G^{n}.

Proof: Interpret such rotations as mapping each surface to another of the hypercube.
Each surface is described as the equation x_{i} = 1 or x_{i} = 1.
Take σ(i) and {κ}[i] as the surface x_{i} = 1 is mapped to the surface x_{σ(i)} = κ[i].
Then, they give g∈G^{n}.

However, the contrary is not true; G^{n} also contains mirroring mappings.

__Assumption__:
According to the theory of linear algebra, g∈G^{n} works as a rotation
if and only if the determinant of X_{g} equals 1,
where X_{g} is the n×n matrix representing g,
which means X_{g}(**v**) = g(**v**) for any column vector **v**∈R^n.

__Define__ d(g) as the determinant of X_{g} described above. Then we get:

**Claim 2**: d(g) = sign(σ_{g})∏κ_{g}[i],
and g works as a rotation if and only if d(g) = 1.

Proof: Substituting **e**[i] for **v** into X_{g}(**v**) = g(**v**),
it turns out that the i-th row vector of X_{g} equals g(**e**[i]).
In other words, X_{g}[i, σ_{g}(i)] = κ_{g}[i] for 1≤i≤n, and the other entries are all 0.
By the definition of the determinant of matrices, we get d(g) = sign(σ_{g})∏κ_{g}[i].

We can interpret g∈G^{n} as a permutation of the 2n surfaces,
and also as a permutation of the 2^{n} vertices of the hypercube.
They behave in different ways.

Example of n=3:

Let A:(surface x=1), B:(surface y=1), C:(surface z=1),
a:(surface x=-1), b:(surface y=-1), c:(surface z=-1),

P:(1,1,1), Q:(1,1,-1), R:(1,-1,1), S:(1,-1,-1),
T:(-1,1,1), U:(-1,1,-1), V:(-1,-1,1), W:(-1,-1,-1).

Let g∈G^{3} given by σ_{g}(1)=2, σ_{g}(2)=3, σ_{g}(3)=1, κ_{g}[1]=κ_{g}[2]=κ_{g}[3]=1.

The permutation of surfaces is as follows:
g(A)=B, g(B)=C, g(C)=A, g(a)=b, g(b)=c, g(c)=a.

The permutation of vertices is:
g(P)=P, g(Q)=T, g(R)=Q, g(S)=U, g(T)=R, g(U)=V, g(V)=S, g(W)=W.
(Precisely, g(Q)=g(1,0,0)+g(0,1,0)+g(0,0,-1)=(0,1,0)+(0,0,1)+(-1,0,0)=(-1,1,1)=T)

Using the cycle notation, they are written as (ABC)(abc) or (P)(QTR)(SUV)(W)

__Define__ cy(g) as the number of cycles of g as a permutation of the vertices of the hypercube
(not the permutation of the surfaces).
For example, if g is the one given above, cy(g) = 4 because g has 4 cycles: (P), (QTR), (SUV), and (W).

We can also define cy(g) in other words.
__Define__ ord(v,g) as the least positive integer k such that g^{k}(v)=v.
__Define__ #(g,q) as the number of vertices of the hypercube
whose position vector **v** satisfies ord(**v**,g)=q.
Then the number of cycles in g with the length q equals #(g,q)/q, so their sum ∑#(g,q)/q is equivalent to cy(g).

However, it is not an efficient way to examining 2^{n} vertices for every g.

Let σ be a permutation. __Define__ S(σ, w) as the smallest set including w and closed by σ,
which means if y∈S(σ, w) then σ(y)∈S(σ, w).

Let g∈G^{n} and w goes 1 from n giving S(σ_{g}, w). Some may give the same set.
Assume that there given m different sets. Call them S[1], S[2], ..., S[m].
(In other words, they are the "cycles" of the σ_{g}.)
Using them, __Define__ M_{g} as the following steps:

(1) Let s[i] be the size of the set S[i] for each 1≤i≤m.

(2) Multiply s[i] by ∏κ_{g}[k] (k∈S[i])

(3) For the uniqueness, sort them in some order, for example the descending order.

Then, that is the sequence M_{g}.

**Proposition 1**:

Let g, g'∈G^{n}. Suppose that M_{g} and M_{g'} are the same sequences.
Then, #(g, q) = #(g', q) for any q, (it means cy(g) = cy(g')), and also d(g) = d(g').

Proof: We show that there exist f∈G^{n}
such that f(g(**v**)) = g'(f(**v**)) for any vector **v**∈R^{n}.

Let m and S[1], S[2], ..., S[m] described above.
Since M_{g} and M_{g'} are the same,
we can take S'[1], S'[2], ..., S'[m] which are m different set given by the form S(σ_{g'}, w),
such that S[i] and S'[i] have the same size and
∏κ_{g}[k] (k∈S[i]) = ∏κ_{g'}[k'] (k'∈S'[i])

Discuss with a specific i. Let the size of S[i] be s, which is also the size of S'[i].
Take w∈S[i] and w'∈S'[i].
Assume g^{t}(**e**[w]) = c**e**[k] and g'^{t}(**e**[w']) = c'**e**[k'].
Then take σ_{f}(k) = k' and κ_{f}[k] = c'/c.
By the definition of S(σ, w), When t goes from 1 to s, each t gives different k.
So σ_{f}(y) and κ_{f}[y] are determined for each y∈S[i].
Similarly, each t gives different k' so σ_{f}(y) takes all value in S'[i].
Each number of {1, 2, ..., n} appears in S[i] for some i and also in S'[i'] for some i',
so σ_{f} and {κ_{f}} are completely determined to give f∈G^{n}.

Then, confirm f(g(**v**)) = g'(f(**v**)).
Again discuss with a specific S[i] and using the description above,
we have f(g^{t}(**e**[w])) = g'^{t}(**e**[w']) for 1≤t≤s.
It means f(g(g^{t-1}(**e**[w]))) = g'(g'^{t-1}(**e**[w'])),
so if we also have f(g^{t-1}(**e**[w])) = g'^{t-1}(**e**[w']),
then it follows f(g(**v**)) = g'(f(**v**)) where **v**=g^{t-1}(**e**[w]).
The only case to check is when t-1=0.
Consider that while g works s times successively upon w,
all κ_{g}[y] (y∈S[i]) are multiplied one by one.
Then g^{s}(**e**[w]) = **e**[w] ∏κ_{g}[k] (k∈S[i]).
Similarly, g'^{s}(**e**[w']) = **e**[w'] ∏κ_{g'}[k'] (k'∈S'[i]).
We already have f(g^{s}(**e**[w])) = g'^{s}(**e**[w']) and
∏κ_{g}[k] (k∈S[i]) = ∏κ_{g'}[k'] (k'∈S'[i]).
Those lead to f(**e**[w])=w', which was the case to check.

Since each basis vector appears somewhere and the mapping is linear mapping,
now we have f(g(**v**)) = g'(f(**v**)) for any vector **v**∈R^{n}.
Substituting g(**v**) for **v**,
we have f(g(g(**v**))) = g'(f(g(**v**)) = g'(g'(f(**v**))
Repeating similarly, we have f(g^{k}(**v**)) = g'^{k}(f(**v**)).
It means if g^{k}(**v**) = **v** than g'^{k}(f(**v**)) = f(**v**)
and if g^{k}(**v**) ≠ **v** than g'^{k}(f(**v**)) ≠ f(**v**).
Then, each vertex **v** of the hypercube corresponds to another vertex F(**v**)
such that org(g,**v**) = ord(g',f(**v**)). It means cy(g) = cy(g').

d(g) = d(g') is easily confirmed by Claim 2: d(g) = sign(σ_{g})∏κ_{g}[i] far above.

Now, we can __define__ #(M,q) = #(g,q), Cy(M) = cy(g), D(M) = d(m) by taking g such as M_{g}=M.

**Proposition 2:**

Let M={M[1], M[2], ..., M[m]} be a m-length sequence with non-zero integer and ∑|M[i]|=n.
__Define__ H(M) as the number of g∈G^{n} such that M_{g} = M.
Then, H(M) is given by:

H(M) = 2^(n-m) n! / ∏|M[k]| (1≤k≤m) / ∏(the number of i such that |M_{i}|=y)! (1≤y≤n).

Proof: There are 2^{m} patterns to give signs to every M[i],
and there are 2^{n} patterns to give signs to κ_{g}[i].
2^{n} patterns are equally divided into 2^{m} patterns.
So 2^{n-m} is the number of patterns of κ_{g} satisfying M_{g}=M.
So the number of patterns of σ_{g} is the rest part.
The way to divide n numbers into M[1], M[2], ..., M[k] subgroups is
n!/∏|M[k]|! (1≤k≤m).
And consider that each subgroups makes (|M[k]|-1)! circular permutation.
Finally, remove distinctions between subgroups with the same size.
These are realized by the expression of H(M) above.

**Claim 3**:
a[n] = ∑H(M)K^{Cy(M)}/∑H(M), where M takes all sequence by non-zero integer,
satisfying ∑|M[i]| = n and D(M) = 1.

Proof: According to the Pólya enumeration theorem, a[n] = ∑K^{cy(g)} (g∈G')/#(G'),
where G' is the set of all permutation of the vertices caused by a rotation.
By Claim 1 and 2, G' = {g∈G^{n} and d(g) = 1}.
Using Proposition 1 and 2, we can gather g with the same M_{g} which result the claim above.

**Proposition 3**:

Suppose M = [n]. If q|n then #(M,q) = ∑μ(q/d)×2^{d} (d|q), otherwise #(M,q) = 0.

Also, if n is odd then D(M) = 1 and otherwise D(M) = -1.

Here μ(x) is the Möbius function and x|y means y is divisible by x.

Proof: Take g with σ_{g}(i) = i+1 (i≠n), σ_{g}(n) = 1,
and κ_{g}[i] = 1 for each i, then M_{g} = M.

Let **v** be a position vector of a vertex of the hypercube, expressed as **v** = ∑a[w]**e**[w] (1≤w≤n),
where a[w] is 1 or -1 for each w.
Considering g(**v**) = ∑a[w]**e**[σ_{g}(w)] (1≤w≤n) and the feature of σ_{g},
we get g^{k}(**v**) = ∑a[w]**e**[w+k] (1≤w≤n)
(if w+k>n, **e**[w+k] means **e**[w+k-n]).

Regardless of a[w] we have g^{n}(**v**) = **v**.
It means ord(**v**,g)|n, and the last part of the proposition follows from here.

Then let q be a divisor of n.
g^{q}(**v**) = **v** means a[w] = a[w+q] for each w (if w+q>n, a[w+q] means a[w+k-n]).
To satisfy this, we can set arbitrary a[1],a[2], ..., a[q], but a[w] (w>q) are determined automatically.
There are 2^{q} kinds of such combination of {a[i]},
so there are 2^{q} vertices satisfying g^{q}(**v**) = **v**.
So, ∑#(g,d) (d|q) = 2^{q}. In programming this form is rather useful,
but by the Möbius transform, we have #(g,q) = ∑μ(q/d)×2^{d} (d|q).

d(g) is easily confirmed by Claim 2.

**Proposition 4**:

Suppose M = [-n]. If q is odd then #(M,q) = 0.

If n is odd, D(M) = 1 and let M' = {n}, then #(M,2q) = #(M',q).

If n is even, D(M) = -1 and let M' = {-n/2,-n/2}, then #(M,2q) = #(M',q).

Proof: Take g with σ_{g}(i) = i+1,
κ_{i} = 1 (i≠n), and σ_{g}(n) = 1,κ_{g}[n] = -1,
then M_{g} = M.

Let **v** = ∑a[w]**e**[w] similarly as the proof above.
Regardless of a[w] we have g^{n}(**v**) = -**v** (≠**v**) this time.
Since g^{2n}(**v**) = **v**, ord(g,**v**) is a divisor of 2n but is not a divisor of n.
That means that ord(g,**v**) is even.

Let g'∈G satisfy g'(v) = g(g(v)) for any v.
Then, ord(g,**v**) = 2q means ord(g',**v**) = q.
If n is odd, σ_{g'} is also one cycle permutation (consider the equation 2x≡0 (mod n)),
and ∏κ_{g'}[i] = 1 (because there appear two negative terms in {κ_{g'}}).
Thus M_{g'} = {n}.
If n is even, σ_{g'} divides into two cycles and each cycle has one negative κ_{g'}[i].
Thus, M_{g'} = {-n/2,-n/2}.

d(g) is easily confirmed by Claim 2.

**Proposition 5**:

Suppose M has more than one term.
Let M', M" be its two subsequences and those fusion equals M.
Then #(M,q) = ∑#(M',x)#(M",y) (LCM(x,y) = q),
where LCM(x,y) is the least common multiple of x, y. Also D(M) = D(M')D(M").

Proof: Take g, g', and g" such as M_{g} = M, M_{g'} = M', and M_{g"} = M".
σ_{g} has several cycles. Some correspond with M' and the other correspond with M".
Let S', S" be subsets of {1, 2, ..., n} such that: For each 1≤w≤n,
if the cycle S(σ_{g}, w) correspond with M' then w∈S', and otherwise w∈S".

Let **v'** = ∑a[w]**e**[w] (w∈S'),
**v"** = ∑a[w]**e**[w] (w∈S"), where a[w] is 1 or -1 for each w.
Then, g(**v'**) is also a linear combination of **e**[w] (w∈S')
and g(**v"**) is a linear combination of **e**[w] (w∈S").

Suppose g^{k}(**v'**+**v"**) = **v'**+**v"**.
Since there are no common terms between S' and S", it requires
both g^{k}(**v'**) = **v'** and g^{k}(**v"**) = **v"**.
Therefore, ord(**v'**+**v"**,g) = LCM(ord(**v'**,g),ord(**v"**,g)).
Here, the number of patterns of a[w] satisfying ord(**v'**,g) = x, is equivalent to #(g',x)
because **v'** is restricted into a subspace, whose dimension equas the size of S',
which equals the dimension of g'. #(g",y) is similar.
#(g',x)= X means there are X patterns of a[w] (w∈S')
and #(g",y) = Y means Y patterns of a[w] (w∈S").
Then, there are XY patterns of a[w] satisfying both.
D(M) = D(M')D(M") is obtained by sign(σ')sign(σ") = sign(σ'σ") and else.

I sorted the sequence M[i] by the descending order with the absolute value,
and if absolute value the same, positive integers higher priority.

Let i start from 1.

Assume that: About M such as ∑|M[i]| < i are already calculated.

Calculate #(M,q),D(M) for M = [n] using Proposition 3.

For each 1≤j<i, and for each M'=[±j],

For each M" such that ∑|M"[i]|=n-j and M'[1] has higher priority than M"[1],

(Every fused M is obtained only once under this restriction)

Calculate #(M,q),D(M) for M =(fusion of M', M"), using Proposition 5.

Calculate #(g,q),D(M) for M = [-n] using Proposition 4.

Next i (until somewhere).

Let i start from 1 again.

For each M satisfying ∑|M[i]|=i,

if D(M) = 1, calculate H(M) by Proposition 2 and Cy(M)=∑#(g,q)/q

Then, output.

Here is my source code written by C language: hypercube.c

And the output for 1≤n≤10: hypercube_output.txt

And the result with K=2 calcurated by Maxima: hypercube_an.txt

Limitation:

Generally, integer overflow, run time, and memory may limit programs.
This time, the integer overflow was the limitation.
I attemped to check integer overflow using such function:

int safe(int x,int y){ //safe means x*y will not overflow assuming x,y>0

int i; while(x){x/=2;i++;} while(y){y/=2;i++;}

if(i>31){printf("Alert from safe(x,y)\n");return 0;}

return 1;}

Then I had one alert when n=10. So, a[10] might be wrong.

Acknowledgement

I would like to thank mleparadonan for providing this interesting topic in yahoo questionnaire. I made much reference to several Wikipedia pages referring to rotation matrix, the Pólya enumeration theorem, and etc. And I looked up the Weblio online English dictionary many times. Of course this work also owes to developers of the Borland (compiler) and the Maxima (mathematical software), and etc.

2014/2/13 Azuma Seiichi