Subgroups of nimber addition

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

The addition of nimbers is the bitwise XOR of non-negative integers. It is closed under finite sets .
These groups are isomorphic to elementary abelian groups Z2n, and that's how they are called in the following.
Subgroups of Z2n may also be called sonas of size 2n or n-ary sonas.
Their order is always a power of two. Sonas of order 2k may also be called sonas of weight 2k or sonas of rank k.


Sequences and triangles[edit]

Each sona can be seen as a set of binary numbers. (Compare the list.)
Among them is a unique odd number. The Wolka sequence[1] Sloane'sA190939 shows these numbers ordered by size:

  • 1, (1 until here for Z20)
  • 3, (2 until here for Z21)
  • 5, 9, 15, (5 until here for Z22)
  • 17, 33, 51, 65, 85, 105, 129, 153, 165, 195, 255, (16 until here for Z23)
  • 257, 513, 771, 1025, 1285, 1545, 2049, 2313, 2565, 3075, 3855, 4097, 4369, 4641, 5185, 6273, 8193, 8481, 8721, 9345, 10305, 12291, 13107, 15555, 16385, 16705, 17025, 17425, 18465, 20485, 21845, 23205, 24585, 26265, 26985, 32769, 33153, 33345, 33825, 34833, 36873, 38505, 39321, 40965, 42405, 43605, 49155, 50115, 52275, 61455, 65535, (67 until here for Z24)
  • 65537, ... (continues 374, 2825, 29212...)

The index numbers of this sequence are used to denote the sonas - e.g. in the Hasse diagrams shown below.




The following triangles show the number of sonas and sona-becs by arity (vertical) and rank in the lattice (horizontal). (The sonas of rank k have weight 2k.)

      |                subgroups (or sonas or sona-secs)                |        equivalence classes (or sona-becs)
      |     A022166                                         A006116     |     A076831                              A076766
      |     0    1     2      3      4     5    6    7         sums     |     0   1   2   3    4    5    6    7       sums
      |                                                                 | 
0     |     1                                                     1     |     1                                          1
1     |     1    1                                                2     |     1   1                                      2
2     |     1    3     1                                          5     |     1   2   1                                  4
3     |     1    7     7      1                                  16     |     1   3   3   1                              8
4     |     1   15    35     15      1                           67     |     1   4   6   4    1                        16
5     |     1   31   155    155     31     1                    374     |     1   5  10  10    5    1                   32
6     |     1   63   651   1395    651    63    1              2825     |     1   6  16  22   16    6    1              68
7     |     1  127  2667  11811  11811  2667  127    1        29212     |     1   7  23  43   43   23    7    1        148

E.g. there are Sloane'sA022166(4, 2) = 35 4-ary sonas of rank 2, and they fall into Sloane'sA076831(4, 2) = 6 different equivalence classes.

The Boolean functions in the sona-secs may be called sona-functions, and the number of n-ary sona-functions is Sloane'sA182176(n). (Currently there is no corresponding triangle in the OEIS.)




Each equivalence class has a weight partition, denoted by an index number of Sloane'sA194602. (Compare this triangle.)




Usually sonas (or sona-secs) are denoted by the unique odd number in the sec (their entry in the Wolka sequence),
but they could just as well be denoted by the smallest number in the sec (i.e. as a value of Sloane'sA227722).
In Sloane'sA227963 these smallest numbers are shown - not ordered by size, but in the order of the Wolka sequence.

Similarly Sloane'sA227960 denotes each sona-bec by the smallest number in the bec (i.e. as a value of Sloane'sA227723). This sequence is ordered by size:

  • 1, (1 until here for Z20)
  • 3, (2 until here for Z21)
  • 6, 15, (4 until here for Z22)
  • 24, 60, 105, 255, (8 until here for Z23)
  • 384, 960, 1632, 1680, 4080, 15555, 27030, 65535, (16 until here for Z24)
  • 98304, ... (continues 32, 68, 148...)


The rows of the triangle Sloane'sA227962 are permutations that assign complementary sona-becs to each other - using their index numbers in Sloane'sA227960.
The complements are also shown here for arities up to 7.

Sloane'sA198260 shows the number of runs of ones in the binary string of each entry of the Wolka sequence.
The triangle Sloane'sA227961 shows that all numbers in appear as numbers of runs of ones of n-ary sonas, and that the numbers greater than appear exactly twice.
E.g. the numbers of runs of ones of 4-ary sonas range from 1 to 8, and those greater 4 appear exactly twice. (The two 4-ary sonas with 8 runs of ones are 46 and 61 - compare the list.)

Z22[edit]

w:Klein four-group
Z2^2; Lattice of subgroups Hasse diagram.svg
Subgroups of Z2^2; digit weights in equivalence classes.svg


Z23[edit]

Z2^3; Lattice of subgroups Hasse diagram.svg
Subgroups of Z2^3; digit weights in equivalence classes.svg



Z24[edit]

Z2^4; Lattice of subgroups Hasse diagram.svg
Subgroups of Z2^4; digit weights in equivalence classes.svg




The number of elements by rank in the lattice is 1, 15, 35, 15, 1.
This is row 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 row 4 in Sloane'sA076831.


All Sloane'sA182176(4) = 307 functions in these equivalence classes (in a matrix like this one)
The respective matrices for smaller sona are the 16x16, 4x4, 2x2 and 1x2 submatrices.
All Sloane'sA006116(4) = 67 functions that correspond to entries of Sloane'sA190939
These are the entries in the odd columns of the matrix on the left.


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 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.

These are the Sloane'sA076766(6) = 68 equivalence classes:

(m,n) with 0≤m≤6 and 1≤nSloane'sA076831(6,m)
The table entries show the number of subgroups in the equivalence class (m,n).

64 6 1 1 1
32 5 6 15 20 15 6 1 63 6
16 4 15 60 60 30 6 20 45 90 60 60 15 15 90 10 60 15 651 16
8 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
4 2 15 60 20 60 45 90 30 60 60 90 6 15 15 10 60 15 651 16
2 1 6 15 20 15 6 1 63 6
1 0 1 1 1
Order
of subgroups
Rank
in lattice
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.
The elements of four equivalence classes:
N(2,11) and N(4,5) with 6 sonas each are counterparts.
N(1,6) and N(5,6) with one sona each are counterparts.

In the big table it can be seen that the binary string's Walsh spectra share the pattern of another binary string.
So each sona has a counterpart with the index number shown in column .
These pairs of counterpart sonas belong to pairs of counterpart equivalence classes.
10 equivalence classes N(3,k) are their own counterparts. In one of them - N(3,17) - even the sonas themselves are their own counterparts.

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


Each equivalence class has a weight partition, but some have the same. Weight partition 6506 is the first one that does not identify an equivalence class. It belongs both to N(3,15) and N(3,17).


The 20 elements of N(3,15)
The 15 elements of N(3,17)
N(3,15) and N(3,17) have the same weight partition 6506.


References[edit]

  1. Because of its A-number I chose to name this sequence after the battle of Wólka Węglowa, which took place on 1939-09-19.