Subgroups of nimber addition

From Wikiversity
Jump to: navigation, search
Created by mate2code.

The addition of nimbers is the exclusive or of non-negative integers in binary representation.
It is closed under finite sets ~\{0,...,2^n-1\}~ and the infinite set ~\{0,1,2,3,...\}~.
The finite groups are isomorphic to elementary abelian groups Z2n, and that's how they are called in the following.

Contents

Z23 [edit]

With the Cayley table Z2^3; Cayley table; colors.svg these are the 16 subgroups of Z23: Z2^3; Lattice of subgroups Hasse diagram.svg

The number of elements by rank in the lattice   (graphically: by layer of the Hasse diagram)   is 1, 7, 7, 1.
This is line 3 in the triangle of 2-binomial coefficients. (Gaussian binomial coefficients)

The rows of these matrices can be read as 3-ary Boolean functions.
(Compare e.g. matrix number 3 and Boolean functions like 1001 0000.)
Only the matrices' top rows are used to identify the subgroups,
so each subgroup corresponds to one 3-ary Boolean function, and thus can be represented by a binarily colored cube:

Z2^3; Lattice of subgroups Hasse diagram (cubes).svg     (The subgroups also correspond to elements of the Fano plane: Fano plane Hasse diagram.svg )

The cubes in black ovals are essentially the same. The corresponding Boolean functions belong to the same big equivalence class.
There are 8 of 22 essentially different cubes. Their number by layer of the Hasse diagram is 1, 3, 3, 1.
This is line 3 in Pascal's triangle.

Z24 [edit]

With the Cayley table Z2^4; Cayley table; binary.svg these are the 67 subgroups of Z24: File:Z2^4; subgroups list.svg
In this file the subgroups are ordered lexicographically, without respect to their rank.
The corresponding integer sequence is OEIS A190939.

The lattice of subgroups can be represented in a Hasse diagram:


The number of elements by rank in the lattice is 1, 15, 35, 15, 1.
This is line 4 in the triangle of 2-binomial coefficients.

Each subgroup of Z24 corresponds to a 4-ary Boolean function, and thus could be represented by a binarily colored tesseract.
One may ask, whether two such tesseracts are essentially the same or not,
i.e. if one can be turned into the other by any rotation of the tesseract.
But the answer is less easy than for the 3-dimensional case.

All binarily colored tesseracts that can be turned into each other form a big equivalence class.
The files linked in the following table list the corresponding 4-ary Boolean functions in the big equivalence classes.

16 4 N(4,1)1 1 1
8 3 N(3,1)4 N(3,2)6 N(3,3)4 N(3,4)1 15 4
4 2 N(2,1)6 N(2,2)12 N(2,3)4 N(2,4)4 N(2,5)3 N(2,6)6 35 6
2 1 N(1,1)4 N(1,2)6 N(1,3)4 N(1,4)1 15 4
1 0 N(0)1 1 1
Order
of subgroups		 Rank
in lattice		 Equivalence classes (becs)
(Subscripts show the number of subgroups in the equivalence class.)		 Number of
subgroups		 Number of
e. c.

(The table is organized upside down, so the rows are arranged like the layers in an Hasse diagram.)

There are 16 of 402 equivalence classes. Their number by rank in the lattice is 1, 4, 6, 4, 1.
This is line 4 in Pascal's triangle.

Z25 [edit]

Z25 has 1 + 31 + 155 + 155 + 31 + 1 = 374 subgroups of order 1, 2, 4, 8, 16, 32.

The number of equivalence classes is 25 =32.

Equivalence classes belonging together as counterparts:

N(0)       N(5,01)
       
N(1,01)    N(4,01)
N(1,02)    N(4,02)
N(1,03)    N(4,03)
N(1,04)    N(4,04)
N(1,05)    N(4,05)
       
N(2,01)    N(3,01)
N(2,02)    N(3,02)
N(2,03)    N(3,05)
N(2,04)    N(3,03)
N(2,05)    N(3,06)
N(2,06)    N(3,07)
N(2,07)    N(3,04)
N(2,08)    N(3,08)
N(2,09)    N(3,09)
N(2,10)    N(3,10)

Z26 [edit]

This text refers to the table of all 2825 subgroups: Subgroups of Z2^6     (very large)

Z26 has 1 + 63 + 651 + 1395 + 651 + 63 + 1 = 2825 subgroups of order 1, 2, 4, 8, 16, 32, 64.

The number of equivalence classes is not 64, as one could guess from the examples above, but 68:

One would expect line 6 of Pascal's triangle: 1, 6, 15, 20, 15, 6, 1
But there is: 1, 6, 16, 22, 16, 6, 1

Of course there could by some mistake in my calculation, but I don't think this strange and unwelcomed result will go away.


These are the 68 equivalence classes:

N(6,01)1
N(5,01)6 N(5,02)15 N(5,03)20 N(5,04)15 N(5,05)6 N(5,06)1
N(4,01)15 N(4,02)60 N(4,03)60 N(4,04)30 N(4,05)6 N(4,06)20 N(4,07)45 N(4,08)90 N(4,09)60 N(4,10)60 N(4,11)15 N(4,12)15 N(4,13)90 N(4,14)10 N(4,15)60 N(4,16)15
N(3,01)20 N(3,02)90 N(3,03)60 N(3,04)15 N(3,05)60 N(3,06)90 N(3,07)180 N(3,08)60 N(3,09)60 N(3,10)90 N(3,11)15 N(3,12)60 N(3,13)60 N(3,14)20 N(3,15)20 N(3,16)90 N(3,17)15 N(3,18)90 N(3,19)45 N(3,20)45 N(3,21)180 N(3,22)30
N(2,01)15 N(2,02)60 N(2,03)20 N(2,04)60 N(2,05)45 N(2,06)90 N(2,07)30 N(2,08)60 N(2,09)60 N(2,10)90 N(2,11)6 N(2,12)15 N(2,13)15 N(2,14)10 N(2,15)60 N(2,16)15
N(1,01)6 N(1,02)15 N(1,03)20 N(1,04)15 N(1,05)6 N(1,06)1
N(0)1

(Subscripts show the number of subgroups in the equivalence class.)

Array with only the numbers of subgroups:

6 1 1 1
5 6 15 20 15 6 1 63 6
4 15 60 60 30 6 20 45 90 60 60 15 15 90 10 60 15 651 16
3  20  90  60  15  60  90 180  60  60  90  15  60  60  20  20  90  15  90  45  45 180  30 1395 22
2 15 60 20 60 45 90 30 60 60 90 6 15 15 10 60 15 651 16
1 6 15 20 15 6 1 63 6
0 1 1 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Number of
subgroups		 Number of
e. c.


In the table it can be seen that the binary string's Walsh spectra share the pattern of another binary string.
So each subgroup has a counterpart with the index number shown in column ♭.
These pairs of counterpart subgroups usually belong to pairs of counterpart equivalence classes.
10 equivalence classes are their own counterparts. Among them is N(3,17), containing the only 15 subgroups that are their own counterparts.

N(0)      N(6,01)
       
N(1,01)   N(5,01)
N(1,02)   N(5,02)
N(1,03)   N(5,03)
N(1,04)   N(5,04)
N(1,05)   N(5,05)
N(1,06)   N(5,06)
       
N(2,01)   N(4,01)
N(2,02)   N(4,02)
N(2,03)   N(4,06)
N(2,04)   N(4,03)
N(2,05)   N(4,07)
N(2,06)   N(4,08)
N(2,07)   N(4,04)
N(2,08)   N(4,09)
N(2,09)   N(4,10)
N(2,10)   N(4,13)
N(2,11)   N(4,05)
N(2,12)   N(4,11)
N(2,13)   N(4,12)
N(2,14)   N(4,14)
N(2,15)   N(4,15)
N(2,16)   N(4,16)
       
N(3,01)
N(3,02)
N(3,03)   N(3,05)
N(3,04)   N(3,11)
N(3,06)
N(3,07)
N(3,08)   N(3,12)
N(3,09)   N(3,13)
N(3,10)   N(3,16)
N(3,14)
N(3,15)
N(3,17)
N(3,18)
N(3,19)   N(3,20)
N(3,21)   
N(3,22)
Retrieved from "http://en.wikiversity.org/w/index.php?title=Subgroups_of_nimber_addition&oldid=1010492"