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] = ∑Kcy(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 Rn: {(x1, x2, ..., xn); xi∈R}.
Define e[i] as the i-th basis vector, with the direction of the axis xi, and the size of 1.
Consider the 2n points described as (±1, ±1, ..., ±1) are the vertices of the hypercube.
Let g be a linear mapping from Rn to Rn, and v be a subset of Rn.
g(v) means the image of v by g, and gk(v) means the image of v by k-times g.
Define Gn as a set of linear mapping g from Rn to Rn 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∈Gn, 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 Gn.
Proof: Interpret such rotations as mapping each surface to another of the hypercube. Each surface is described as the equation xi = 1 or xi = 1. Take σ(i) and {κ}[i] as the surface xi = 1 is mapped to the surface xσ(i) = κ[i]. Then, they give g∈Gn.
However, the contrary is not true; Gn also contains mirroring mappings.
Assumption: According to the theory of linear algebra, g∈Gn works as a rotation if and only if the determinant of Xg equals 1, where Xg is the n×n matrix representing g, which means Xg(v) = g(v) for any column vector v∈R^n.
Define d(g) as the determinant of Xg 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 Xg(v) = g(v), it turns out that the i-th row vector of Xg equals g(e[i]). In other words, Xg[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∈Gn as a permutation of the 2n surfaces, and also as a permutation of the 2n 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∈G3 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 gk(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 2n 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∈Gn 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 Mg 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 Mg.
Proposition 1:
Let g, g'∈Gn. Suppose that Mg and Mg' 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∈Gn
such that f(g(v)) = g'(f(v)) for any vector v∈Rn.
Let m and S[1], S[2], ..., S[m] described above.
Since Mg and Mg' 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 gt(e[w]) = ce[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∈Gn.
Then, confirm f(g(v)) = g'(f(v)).
Again discuss with a specific S[i] and using the description above,
we have f(gt(e[w])) = g't(e[w']) for 1≤t≤s.
It means f(g(gt-1(e[w]))) = g'(g't-1(e[w'])),
so if we also have f(gt-1(e[w])) = g't-1(e[w']),
then it follows f(g(v)) = g'(f(v)) where v=gt-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 gs(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(gs(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∈Rn.
Substituting g(v) for v,
we have f(g(g(v))) = g'(f(g(v)) = g'(g'(f(v))
Repeating similarly, we have f(gk(v)) = g'k(f(v)).
It means if gk(v) = v than g'k(f(v)) = f(v)
and if gk(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 Mg=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∈Gn such that Mg = M.
Then, H(M) is given by:
H(M) = 2^(n-m) n! / ∏|M[k]| (1≤k≤m) / ∏(the number of i such that |Mi|=y)! (1≤y≤n).
Proof: There are 2m patterns to give signs to every M[i], and there are 2n patterns to give signs to κg[i]. 2n patterns are equally divided into 2m patterns. So 2n-m is the number of patterns of κg satisfying Mg=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)KCy(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] = ∑Kcy(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∈Gn and d(g) = 1}. Using Proposition 1 and 2, we can gather g with the same Mg which result the claim above.
Proposition 3:
Suppose M = [n]. If q|n then #(M,q) = ∑μ(q/d)×2d (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 Mg = 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 gk(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 gn(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.
gq(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 2q kinds of such combination of {a[i]},
so there are 2q vertices satisfying gq(v) = v.
So, ∑#(g,d) (d|q) = 2q. In programming this form is rather useful,
but by the Möbius transform, we have #(g,q) = ∑μ(q/d)×2d (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 Mg = M.
Let v = ∑a[w]e[w] similarly as the proof above.
Regardless of a[w] we have gn(v) = -v (≠v) this time.
Since g2n(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 Mg' = {n}.
If n is even, σg' divides into two cycles and each cycle has one negative κg'[i].
Thus, Mg' = {-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 Mg = M, Mg' = M', and Mg" = 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 gk(v'+v") = v'+v".
Since there are no common terms between S' and S", it requires
both gk(v') = v' and gk(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