This site is supported by donations to The OEIS Foundation.

User talk:Tilman Piesk/Subgroups of powers of Z2

From OeisWiki
Jump to: navigation, search

Hi Tilman, I tried to reproduce your results.

Z2_0, Z2_1, Z2_2 agree. With Z2_3 there are differences.

Can you help me to see what I have misunderstood?

The tables below have this format:

  • "Z2_n" list of elements of subgroups of Z2_n.
  • Next I map the names of the elements to [0..2^n-1].
  • Then the binary encoding.

Do you have a different table of subgroups of Z2_3?


Z2_0 := [
[ f0 ]
]:
f0:=0:
sort([seq(add(2^j,j=g),g = Z2_0)]);
[1]

Z2_1 := [
[ f0 ],
[ f0, f1 ]
]:
f0:=0: f1:=1:
sort([seq(add(2^j,j=g),g = Z2_1)]);
[1, 3]

Z2_2 := [                                
[ f0 ],                                  
[ f0, f1 ],                              
[ f0, f2 ],                              
[ f0, f1f2 ],                            
[ f0, f1, f2, f1f2 ]                     
]:                                       
f0:=0: f1:=1: f2:=2: f1f2:=3:            
sort([seq(add(2^j,j=g),g = Z2_2)]);      
[1, 3, 5, 9, 15]

Z2_3 := [
[f0 ],
[f0, f1 ],
[f0, f2 ],
[f0, f3 ],
[f0, f1f2 ],
[f0, f1f3 ],
[f0, f2f3 ],
[f0, f1f2f3 ],
[f0, f1, f2, f1f2 ],
[f0, f1, f3, f1f3 ],
[f0, f2, f3, f2f3 ],
[f0, f1, f2f3, f1f2f3 ],
[f0, f2, f1f3, f1f2f3 ],
[f0, f3, f1f2, f1f2f3 ],
[f0, f1f2, f1f3, f2f3 ],
[f0, f1, f2, f3, f1f2, f1f3, f2f3, f1f2f3 ]
]:
f0:=0: f1:=1: f2:=2: f3:=3: f1f2:=4:
f1f3:=5: f2f3:=6: f1f2f3:=7:
sort([seq(add(2^j,j=g),g = Z2_3)]);
[1, 3, 5, 9, 17, 23, 33, 43, 65, 77, 113, 129, 153, 165, 195, 255]

Peter Luschny 09:45, 26 May 2011 (UTC)


■ ■ ■


Well, I don't know what you did, but I see the results.

Your first item differing from "my" numbers is 23.
23 = 2^0 + 2^1 + 2^2 + 2^4 ; so the corresponding set is {0,1,2,4}. But that's not a subgroup - as e.g. 1*2=3, which is not in the set.
Your second differing item is 43.
43 = 2^0 + 2^1 + 2^3 + 2^5 ; so the corresponding set is {0,1,3,5}. But that's not a subgroup - as e.g. 1*3=2, which is not in the set.
You may check that in the Cayley table of (Z_2)^4.

So whatever you have calculated - it's not subgroups of a power of Z_2.
Here you see the subgroups of (Z_2)^3 in a Hasse diagram: File:Z2^3; Lattice of subgroups Hasse diagram.svg
Here with the numbers of the sequence: Zoom, File

By the way: Your subscript notation "Z2_n" instead of "(Z_2)^n" or "Z2^n" is strange to me.

Greetings, Tilman Piesk 08:49, 27 May 2011 (UTC)


■ ■ ■


  • Well, I don't know what you did, but I see the results.

Ok, I try to explain with more details.

Z2_2 := [
[ f0 ],
[ f0, f1 ],
[ f0, f2 ],
[ f0, f1f2 ],
[ f0, f1, f2, f1f2 ]
]:

This is the list of all subgroups of (Z_2)^2, the Klein 4-group. Each element in this list is again a list which represents the subgroup in terms of its elements. So for example [ f0 ] is the trivial subgroup and [ f0, f1, f2, f1f2 ] the group itself, [ f0, f1 ] and [ f0, f2 ] represent the remaining two subgroups.

Wikipedia uses 1 instead of f0, a instead of f1, b instead of f2 and ab instead of f1f2. [1] However, "Namen sind Schall und Rauch".

  • By the way: Your subscript notation "Z2_n" instead of "(Z_2)^n" or "Z2^n" is strange to me.

The reason is that what you see is in fact a Maple worksheet. There you have sometimes to use a slightly different notation in order to not confuse Maple. However, this is irrelevant as long as the intended meaning is clear from the context.

  • Your first item differing from "my" numbers is 23. 23 = 2^0 + 2^1 + 2^2 + 2^4 ; so the corresponding set is {0,1,2,4}.

OK. Here is what Maple does:

add(2^j,j=[f0, f1, f2, f1f2]);
2^f0 + 2^f1 + 2^f2 + 2^f1f2.
2^0  + 2^1  + 2^2   + 2^4.

So yes, this agrees with your computation with the given numerical substitution f0:=0: f1:=1: f2:=2: f3:=3: f1f2:=4:.

  • Here you see the subgroups of (Z_2)^3 in a Hasse diagram: File:Z2^3; Lattice of subgroups Hasse diagram.svg Here with the numbers of the sequence: Zoom, File

They are really delightful, your diagrams. Sometimes they incorporate even more information than I can cope with. My problem is that Maple does not understand these diagrams. So I have to use a more profane form of representation.

  • But that's not a subgroup - as e.g. 1*2=3, which is not in the set. So whatever you have calculated - it's not subgroups of a power of Z_2.

So what the heck is going on? I will pursue this later. Or do you have the list of the subgroups which you used in your calculations in the form

Z2_2 := [
[ 1 ],
[ 1, a ],
[ 1, b ],
[ 1, ab ],
[ 1, a, b, ab ]
]:

Peter Luschny 17:14, 27 May 2011 (UTC)


■ ■ ■


It's difficult to describe, how I computed these matrices, because when I did, I didn't even know, that they correspond to subgroups.
In the beginning I was interested in 3-ary Boolean functions. I realized, that some of the negator variation matrices, which I've put in my files, described equivalence relations (while most of them didn't).

Than I wanted to know all 16x16 matrices of this kind:
The matrices of order 1 and 2 are trivial.
My essential step, how to get all order 4 matrices from the order 2 matrices, is shown in this graphic: File:Z2^4; Lattice of subgroups; join of 2-element subgroups.svg (It's the original file I've used to do it.)
From the 8x8 case I concluded by analogy, that the "half full" matrices and the "full" matrix correspond to negated XORs.

You see that I've done this completely by hand. Handbetrieb bleibt Handbetrieb. I have no idea, how to do it in a digital way. But also a computer should be able to do, what I did: Combine the matrices of order 2 by logical or, and complete them (by adding 1s) to the smallest possible (i.e. order 4) matrix, that describes an equivalence relation. But of course it's much easier to go backwards from the "half full" matrices (computed with negated XORs), and combine them by logical and.

To prove that this (the backwards way) really gives subgroups of Z2^n, it's just necessary to prove, that the negated XORs describe subgroups. That the intersection of subgroups are subgroups themselves is known. Tilman Piesk 22:06, 27 May 2011 (UTC)


■ ■ ■


Hi Tilman! I cannot trace all the ideas you described here. My subject is only:

 A190939 Subgroups of (Z_2)^n interpreted as binary numbers.

 Let Z_2 be the cyclic group of order 2, and (Z_2)^n the n-times 
 product Z_2 × ... × Z_2.

 The elements of (Z_2)^n can be numbered from 0 to 2^n-1, with 0 
 representing the neutral element.

 (This is unambiguous, because all non-neutral elements of the 
 elementary abelian group (Z_2)^n have order 2.)

 Than every subgroup {0,a,b,c...} of (Z_2)^n can be assigned an 
 integer 1 + 2^a + 2^b + 2^c + ...

 For each (Z_2)^n there is a finite sequence of these numbers 
 ordered by size, and it is the beginning of the finite sequence 
 for (Z_2)^(n+1).

 This leads to the infinite sequence:

* 1,         (1 until here for (Z_2)^0)
* 3,         (2 until here for (Z_2)^1)
* 5, 9, 15,  (5 until here for (Z_2)^2)
* 17, 33, 51, 65, 85, 105, 129, 153, 165, 195, 255, (16 until here for (Z_2)^3)

I cannot reproduce your last line.

You define this part of the sequence by "Subgroups of (Z_2)^3 interpreted as binary numbers"

Well, so you must be able to give a description of these "subgroups of (Z_2)^3".

Otherwise we cannot even start our computation. I have given this list subgroups in terms of their elements.

[f0 ],
[f0, f1 ],
[f0, f2 ],
[f0, f3 ],
[f0, f1f2 ],
[f0, f1f3 ],
[f0, f2f3 ],
[f0, f1f2f3 ],
[f0, f1, f2, f1f2 ],
[f0, f1, f3, f1f3 ],
[f0, f2, f3, f2f3 ],
[f0, f1, f2f3, f1f2f3 ],
[f0, f2, f1f3, f1f2f3 ],
[f0, f3, f1f2, f1f2f3 ],
[f0, f1f2, f1f3, f2f3 ],
[f0, f1, f2, f3, f1f2, f1f3, f2f3, f1f2f3 ].

It is not difficult to verify this list using free computer algebra software.

In this case I recommend the excellent GAP. (Google shows you where you can download it.)

Ok. Let us look at a GAP-session.

gap> SmallGroupsInformation( 8 );

 There are 5 groups of order 8.
   1 is of type c8.
   2 is of type 2x4.
   3 is of type D8.
   4 is of type Q8.
   5 is of type 2^3.

Nice. Clearly we want group number 5.

gap> G:= SmallGroup(8,5);

<pc group of size 8 with 3 generators>

We know:

Fact 1: G is Abelian.

Fact 2: All subgroups of Abelian groups are normal.

Thus we only need a single further command:

gap> for n in NormalSubgroups(G) do Print(Elements(n),"\n"); od;

Then GAP gives a list equivalent to my list above.

Now I cannot reach from this list of subgroups your list of integers.

So please provide some further information how this can be done; after all sequences in OEIS have to be described in a reproducible way. Peter Luschny 22:58, 27 May 2011 (UTC)


■ ■ ■


Well, I've just described an easy way to compute this sequence, just with the multigrade operator negated exclusive or and the logical and. I don't use the fact that these are subgroups - I just compute the sequence, and than I check that indeed the items correspond to subgroups of Z2^n. You tried to calculate subgroups by means of group theory, but for some reason it didn't work - some of your items didn't correspond to subgroups, like 23 = 2^0 + 2^1 + 2^2 + 2^4, which corresponds to {0,1,2,4}.

So here is my way, without any group theory

Let 8-bit strings define subgroups of {0,1,2,3,4,5,6,7}:

Take the 3 strings

A: 0101 0101
B: 0011 0011
C: 0000 1111

and combine them by negated exclusive or (my abbrevation is NXOR, not to be confused with XNOR). The result is the following:

NXOR(   ): 1111 1111    -->    {0,1,2,3,4,5,6,7}
NXOR(A  ): 1010 1010    -->    {0,  2,  4,  6  }
NXOR( B ): 1100 1100    -->    {0,1,    4,5    }
NXOR(AB ): 1001 1001    -->    {0,    3,4,    7}
 
NXOR(  C): 1111 0000    -->    {0,1,2,3        }
NXOR(A C): 1010 0101    -->    {0,  2,    5,  7}
NXOR( BC): 1100 0011    -->    {0,1,        6,7}
NXOR(ABC): 1001 0110    -->    {0,    3,  5,6  }

(Compare this matrix.)

These are subgroups of Z2^3, and they correspond to the upper half of my Hasse diagram.

Now we have the seven half full strings. To compute the quater full strings we use logical and. We make a 7x7 matrix, and compute all possible conjunctions:

AND                 1010 1010     1100 1100     1001 1001     1111 0000     ...
   
1010 1010           
1100 1100           1000 1000     
1001 1001           1000 1000     1000 1000 
1111 0000           1010 0000     1100 0000     1001 0000
...

We are not interested in the diagonal, and of the rest we are only interested in one of the two triangles. So among (72-7)/2 = 21 strings we find the quarter full strings we are looking for.

Of course these are the seven strings 1100 0000 , 1010 0000 , ... , 1000 0001.

To "find" the string 1000 0000 we combine the seven strings above by logical and. The result is always 1000 0000. End of algorithm.

For other Z2^n it works the same way: Find the 2n-1 half full strings with negated exclusive or. Combine them by logical and to find the quarter full strings. Combine these by logical and to find the 1/8 full strings. And so on, until you have the 1/2n full string, with only one 1 at the beginning.

To make it perfect, we just need to prove, that the negated XORs are subgroups for every Z2^n. Tilman Piesk 11:29, 28 May 2011 (UTC)

■ ■ ■

OK. I give up.

There is no reference to "negated exclusive or" and the "logical and" in the published description of your sequence, so I don't care about that. A user which reads the database entry wants to be able to reproduce the sequence from the description given there.

Sure you handcrafted your sequence somehow; however this is not the point here. You did not show how to accomplish this starting from your own written words and nothing else; 'full strings', 'quater full strings', 'take this', 'take that' etc. are not part of your description of A190939.

"You tried to calculate subgroups by means of group theory, but for some reason it didn't work"

I think it worked well. It just did not gave the results that you listed.

Please observe that my results agree with the informations given by GAP. If you can show them wrong you have found a bug comparable to Mathematica calculating 2*3=5.

Peter Luschny 13:06, 28 May 2011 (UTC)

■ ■ ■

Do we both agree, that this is the correct Cayley table of Z2^4 ?
And that the 8x8 matrix in the top left corner is the correct Cayley table of Z2^3 ?
Than we should both agree, that 2*3 = 3*2 = 1.

"I think it worked well. It just did not gave the results that you listed."

You think it worked well? So do you think, that {0,1,2,4} is a subgroup of Z2^3, with the elements numbered {0, 1, 2, 3, 4, 5, 6, 7} ?
Note, that the elements are numbered in this way, and not { {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3} }, or whatever.
My description clearly reads:

"The elements of (Z_2)^n can be numbered from 0 to 2^n-1, with 0 representing the neutral element."
Again: {0,1,2,4} is not a subgroup of Z2^3, with the elements numbered {0,1,2,3,4,5,6,7}:
 
0 1 2 3   4 5 6 7
1 0 3 2   5 4 7 6
2 3 0 1   6 7 4 5
3 2 1 0   7 6 5 4
 
4 5 6 7   0 1 2 3
5 4 7 6   1 0 3 2
6 7 4 5   2 3 0 1
7 6 5 4   3 2 1 0
 
So 2^0 + 2^1 + 2^2 + 2^4 = 23 is not part of the sequence.
For comparison: {0,3,5,6} is a subgroup of Z2^3, with the elements numbered {0,1,2,3,4,5,6,7}:
 
0 1 2 3   4 5 6 7
1 0 3 2   5 4 7 6
2 3 0 1   6 7 4 5
3 2 1 0   7 6 5 4

4 5 6 7   0 1 2 3
5 4 7 6   1 0 3 2
6 7 4 5   2 3 0 1
7 6 5 4   3 2 1 0
 
So 2^0 + 2^3 + 2^5 + 2^6 = 105 is part of the sequence.

There's no reference to negated XOR and AND in my description of the sequence, because thats just a definition. The algorithm that I recommend to compute the items could be added in the section PROG. Tilman Piesk 15:13, 28 May 2011 (UTC)


■ ■ ■


Dear Tilman, although I have given up all hope to convince you I add another comment

to explain my view even more explicit and complete.

First let us look again at the list of subgroups.


                                           #       [f0,f1,f2,f3,f1f2,f1f3,f2f3,f1f2f3]
[f0 ],                                     #   1 ~ [1]
[f0, f1 ],                                 #   3 ~ [1, 1]
[f0, f2 ],                                 #   5 ~ [1, 0, 1]
[f0, f3 ],                                 #   9 ~ [1, 0, 0, 1]
[f0, f1f2 ],                               #  17 ~ [1, 0, 0, 0, 1]
[f0, f1f3 ],                               #  33 ~ [1, 0, 0, 0, 0, 1]
[f0, f2f3 ],                               #  65 ~ [1, 0, 0, 0, 0, 0, 1]
[f0, f1f2f3 ],                             # 129 ~ [1, 0, 0, 0, 0, 0, 0, 1]
[f0, f1, f2, f1f2 ],                       #  23 ~ [1, 1, 1, 0, 1]
[f0, f1, f3, f1f3 ],                       #  43 ~ [1, 1, 0, 1, 0, 1]
[f0, f2, f3, f2f3 ],                       #  77 ~ [1, 0, 1, 1, 0, 0, 1]
[f0, f1f2, f1f3, f2f3 ],                   # 113 ~ [1, 0, 0, 0, 1, 1, 1]
[f0, f1, f2f3, f1f2f3 ],                   # 195 ~ [1, 1, 0, 0, 0, 0, 1, 1]
[f0, f2, f1f3, f1f2f3 ],                   # 165 ~ [1, 0, 1, 0, 0, 1, 0, 1]
[f0, f3, f1f2, f1f2f3 ],                   # 153 ~ [1, 0, 0, 1, 1, 0, 0, 1]
[f0, f1, f2, f3, f1f2, f1f3, f2f3, f1f2f3] # 255 ~ [1, 1, 1, 1, 1, 1, 1, 1]


Here I fully display the mapping of the subgroups of (Z_2)^3 onto its binary encoding.

(It would really be helpful if you would post your version of this list and mapping for comparison.)

It seems to me that you are not familiar with this notation although you referred to Wikipedia's Klein four-group [2]

which also makes use of this notation. The Cayley table there is written as {1,a,b,ab}. With the choice of names

which I use here this would be {f0, f1, f2, f1f2}.

Cite Tilman:
Your first item differing from "my" numbers is 23.
23 = 2^0 + 2^1 + 2^2 + 2^4 ; so the corresponding set is {0,1,2,4}. 
But that's not a subgroup - as e.g. 1*2=3, which is not in the set.
Your second differing item is 43.
43 = 2^0 + 2^1 + 2^3 + 2^5 ; so the corresponding set is {0,1,3,5}. 
But that's not a subgroup - as e.g. 1*3=2, which is not in the set.

This is a complete misunderstanding. As you can see from the table above the 'binary value' 23

corresponds to the subgroup [f0, f1, f2, f1f2]. Thus this is a isomorphic copy of the Klein four-group.

Just remember that f1f2 = f1*f2 = f3 from the Cayley table.

The second case is analogically: [f0, f1, f3, f1f3 ] -> 43 ~ [1, 1, 0, 1, 0, 1].

This is another isomorphic copy of the Klein four-group as f1f3 = f2. Peter Luschny 10:15, 29 May 2011 (UTC)


■ ■ ■


OK, now I see, why we get different results. You refer to a different Cayley table of Z2^3, while I refer to Cayley tables of Z2^n with the most regular pattern (which are also the addition tables of nimbers).

You numbered the following elements in this order from right to left, while I numbered them lexicographically.

 "f0"   f1     f2     f3     f1*f2   f1*f3    f2*f3   f1*f2*f3
 {}     {1}    {2}    {3}    {1,2}   {1,3}    {2,3}   {1,2,3} 
 000    100    010    001    110     101      011     111
    

The Cayley table you used:

 
000  100  010  001    110  101  011  111
100  000  110  101    010  001  111  011
010  110  000  011    100  111  001  101
001  101  011  000    111  100  010  110
 
110  010  100  111    000  011  101  001
101  001  111  100    011  000  110  010
011  111  001  010    101  110  000  100
111  011  101  110    001  010  100  000

I thought the Cayley table of Z2^n is always unique (as for Z2^2), but indeed it's not. So the following statement in my description of A190939 is wrong:

"This is unambiguous, because all non-neutral elements of the elementary abelian group (Z_2)^n have order 2."

I propose the following new title and modified description:

TITLE: Subgroups of nimber addition interpreted as binary numbers

COMMENTS:

Each subgroup {0,a,b,...} of nimber addition can be assigned an integer 1+2^a+2^b+...
These integers ordered by size give this sequence.
Without nimbers the sequence may be defined as follows:
The powerset af a set {0,...,n-1} with the symmetric difference as group operation forms the elementary abelian group (Z_2)^n.
The elements of the group can be numbered lexicographically from 0 to 2^n-1, with 0 representing the neutral element:
{}-->0 , {0}-->2^0=1 , {1}-->2^1=2 , {0,1}-->2^0+2^1=3 , ... , {0,...,n-1}-->2^n-1
So the subroups of (Z_2)^n can be represented by subsets of {0,...,2^n-1}.
So each subgroup {0,a,b,...} of (Z_2)^n can be assigned an integer 1+2^a+2^b+...
For each (Z_2)^n there is a finite sequence of these numbers ordered by size, and it is the beginning of the finite sequence for (Z_2)^(n+1).
This leads to the infinite sequence:
...

Greetings, Tilman Piesk 15:36, 29 May 2011 (UTC)


■ ■ ■


  • OK, now I see, why we get different results.

That's fine.

Well, not realy, as I have written in plain English and not with color squares.

But I take your word that this reflects what I did.

However, you say that this is 'untypical'. Why?

  • The Cayley table you used:

I show you with three lines of Maple why I do not think that this is an untypical table:

G := [[0,0,0],[1,0,0],[0,1,0],[0,0,1],[1,1,0],[1,0,1],[0,1,1],[1,1,1]]:
Xor := (frog,toad) -> zip((x,y)->`if`(x=y,0,1),frog,toad):
for g in G do print(seq(Xor(g,h),h = G)) od;

Result:

[0,0,0],[1,0,0],[0,1,0],[0,0,1],[1,1,0],[1,0,1],[0,1,1],[1,1,1]
[1,0,0],[0,0,0],[1,1,0],[1,0,1],[0,1,0],[0,0,1],[1,1,1],[0,1,1]
[0,1,0],[1,1,0],[0,0,0],[0,1,1],[1,0,0],[1,1,1],[0,0,1],[1,0,1]
[0,0,1],[1,0,1],[0,1,1],[0,0,0],[1,1,1],[1,0,0],[0,1,0],[1,1,0]
[1,1,0],[0,1,0],[1,0,0],[1,1,1],[0,0,0],[0,1,1],[1,0,1],[0,0,1]
[1,0,1],[0,0,1],[1,1,1],[1,0,0],[0,1,1],[0,0,0],[1,1,0],[0,1,0]
[0,1,1],[1,1,1],[0,0,1],[0,1,0],[1,0,1],[1,1,0],[0,0,0],[1,0,0]
[1,1,1],[0,1,1],[1,0,1],[1,1,0],[0,0,1],[0,1,0],[1,0,0],[0,0,0]

Peter Luschny 19:18, 30 May 2011 (UTC)

As it is not everyone's cup of tea to read binary numbers here the conventional version.

nimsum := proc(a,b) local i;
zip((x,y)->`if`(x<>y,1,0),convert(a,base,2),convert(b,base,2),0);
add(`if`(%[i]=1,2^(i-1),0),i=1..nops(%)) end:

G := [0,1,2,3,4,5,6,7]:
for g in G do print(seq(nimsum(g,h),h = G)) od;

Result:

         0, 1, 2, 3, 4, 5, 6, 7
         1, 0, 3, 2, 5, 4, 7, 6
         2, 3, 0, 1, 6, 7, 4, 5
         3, 2, 1, 0, 7, 6, 5, 4
         4, 5, 6, 7, 0, 1, 2, 3
         5, 4, 7, 6, 1, 0, 3, 2
         6, 7, 4, 5, 2, 3, 0, 1
         7, 6, 5, 4, 3, 2, 1, 0

Peter Luschny 22:59, 30 May 2011 (UTC)