Sudoku Symmetry Group (minimal spec)

Everything about Sudoku that doesn't fit in one of the other sections

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Wed Dec 19, 2018 8:17 pm

Hi Mathimagics,

Thanks for the explanation about N=5 and SmallGeneratingSet.
I understand the name now ... i.e. why it isn't called MinimalGeneratingSet.

Ok, but the real upshot is that this demonstrates what I said earlier about rotate being more "powerful" than flip - the rotate permutation still completed the group, without having a complete subgroup of row/band permutations.

This explains why my x and y operations using (N-1) + (N-2) shifts still work, even though the pair {x, y} does not generate the full band/row subgroup! It doesn't actually have to, because of the power of rotate to fill in the gaps (pun intended)! 8-)

Yes, I witnessed the "power of rotate", in my earlier scheme.

PS: Yes, my shifts are done left to right (+ means "followed by"). I haven't tested whether this order is critical or not, but will do this.

[EDIT] The order of the shifts is apparently not critical at all, the "+" actually commutes in this particular case!

The order of the operations will make a difference in the actual generators, though, since row operations in band 1, don't commute with band operations involving band 1.
I don't know how detailed your testing was, but unless I have a bug, for N=3, the ordering did matter, as to whether {x,y} generates the "bands & rows" group. It's possible that even though switching the order (apparently) doesn't work for that part, adding "z = rotate" to the set, still works for generating the full group.

You will have gathered that all my verifications simply involve examining the group size when I plug a set of permutations into GAP ... very fast.

Nothing wrong with that. I should really learn GAP :(

We have done well, I think! We have produced truly elegant, generally applicable minimal generators ... good job all round!

I would be much happier if we could come up with an actual proof (or a clear vision that one exists), for general N, and some particular specification of generators.

I think I could do that for my earlier setup for the full group, but I'ld be much happier if we could do it for a pair of generators for the "bands & rows" subgroup. I'm close to having something, I think. (Edit: ... not as close as I hoped :() If it works, it would involve an "odd/even" difference, again, in the way the generators are specified.
blue
 
Posts: 853
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Thu Dec 20, 2018 2:28 am

blue wrote:I should really learn GAP :(

The interface is a little primitive and unforgiving, but installation is painless (on Win64 at least, but that says much for an open-source package). I can give you my scripts for getting the group sizes, (and I have one for extracting individual conjugacy class permutations). That will save you much pain ...

blue wrote:I'd be much happier if we could do it for a pair of generators for the "bands & rows" subgroup.

I agree this seems the more likely route. We need to show that HG1 {x, y} generates this subgroup for any N, and then that adding the flip element generates the full group.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1283
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Thu Dec 20, 2018 8:15 am

Mathimagics wrote:
blue wrote:I should really learn GAP :(

The interface is a little primitive and unforgiving, but installation is painless (on Win64 at least, but that says much for an open-source package). I can give you my scripts for getting the group sizes, (and I have one for extracting individual conjugacy class permutations). That will save you much pain ...

I have it downloaded and installed, and some of it learned, thanks.

Below is some "LogTo" file output, showing some results.

For anyone else who's interested, at the top, are short functions for producing the groups for (N*N)x(N*N) and (N1*N2)x(N2*N1) Sudoku.
(I'm not sure if I have the orderering right, for the N1,N2 case).

Hidden Text: Show
Code: Select all
gap> sgrp  := function(N)
>   local g;
>   g := WreathProduct(SymmetricGroup(N),SymmetricGroup(N));
>   return WreathProduct(g,SymmetricGroup(2));
> end;;
gap>
gap> sgrp2 := function(N1,N2)
>   local g1, g2;
>   g1 := WreathProduct(SymmetricGroup(N1),SymmetricGroup(N2));
>   g2 := WreathProduct(SymmetricGroup(N2),SymmetricGroup(N1));
>   return DirectProduct(g1,g2);
> end;;
gap>
gap> Size(sgrp(3));
3359232
gap> NrConjugacyClasses(sgrp(3));
275
gap>
gap> Size(sgrp2(3,3));
1679616
gap> NrConjugacyClasses(sgrp2(3,3));
484
gap>
gap> Size(sgrp(4));
126806761930752
gap> NrConjugacyClasses(sgrp(4));
18335
gap>
gap> Size(sgrp(5));
17832200896512000000000000
gap>
gap> Size(sgrp2(2,3));
3456
gap> NrConjugacyClasses(sgrp2(2,3));
90
gap> quit;
blue
 
Posts: 853
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby StrmCkr » Thu Dec 20, 2018 9:06 pm

deleted
Last edited by StrmCkr on Sun Dec 23, 2018 9:10 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 980
Joined: 05 September 2006

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Fri Dec 21, 2018 3:49 am

deleted
Last edited by blue on Sun Dec 23, 2018 10:29 am, edited 1 time in total.
blue
 
Posts: 853
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby StrmCkr » Fri Dec 21, 2018 11:20 am

deleted.
Last edited by StrmCkr on Sun Dec 23, 2018 9:11 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 980
Joined: 05 September 2006

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Fri Dec 21, 2018 11:46 am

.
Transpose (aka flip) IS a diagonal reflection (main diagonal).

Rotate quarter turn is different.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1283
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Fri Dec 21, 2018 12:15 pm

deleted
Last edited by blue on Sun Dec 23, 2018 10:30 am, edited 1 time in total.
blue
 
Posts: 853
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby StrmCkr » Fri Dec 21, 2018 12:18 pm

deleted.
Last edited by StrmCkr on Sun Dec 23, 2018 9:07 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 980
Joined: 05 September 2006

Re: Sudoku Symmetry Group (minimal spec)

Postby StrmCkr » Fri Dec 21, 2018 12:33 pm

blue wrote:
Code: Select all
+-------+    +-------+    +-------+    +-------+
| a b c |    | e . . |    | e d a |    | . . c |
| d . . | -> | d . . | -> | . . b | -> | . . b |
| e . . |    | a b c |    | . . c |    | e d a |
+-------+    +-------+    +-------+    +-------+

1,2,3,4

1 and 4 ( I have)
2 and 3 ( I have)
.
3 - 4 and
1-2 I don't.
(so yes you are using a fixed rotational direction 1/4 turn after transposing...
Last edited by StrmCkr on Fri Dec 21, 2018 1:03 pm, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 980
Joined: 05 September 2006

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Fri Dec 21, 2018 12:45 pm

deleted
Last edited by blue on Sun Dec 23, 2018 10:30 am, edited 1 time in total.
blue
 
Posts: 853
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby StrmCkr » Fri Dec 21, 2018 12:59 pm

deleted
Last edited by StrmCkr on Sun Dec 23, 2018 9:09 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 980
Joined: 05 September 2006

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Fri Dec 21, 2018 2:34 pm

deleted
Last edited by blue on Sun Dec 23, 2018 10:31 am, edited 1 time in total.
blue
 
Posts: 853
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby StrmCkr » Fri Dec 21, 2018 3:17 pm

deleted
Last edited by StrmCkr on Sun Dec 23, 2018 9:04 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 980
Joined: 05 September 2006

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Fri Dec 21, 2018 4:36 pm

deleted
Last edited by blue on Sun Dec 23, 2018 10:32 am, edited 1 time in total.
blue
 
Posts: 853
Joined: 11 March 2013

PreviousNext

Return to General