The New Sudoku Players' Forum

[Mathimagics]

Keeping two swaps, the third one could be
x = Swap(R12)
y = Swap(B12)
z = Shift(R12345) + Shift(B12345) + Flip


Also verified
x = Swap(R1234)
y = Swap(B1234)
z = Shift(R12345) + Shift(B12345) + Flip

Sorry, but these do not generate the full group (25x25).

Assuming "Swap" in the 2nd triplet should be "Shift", this is my 25x25 solution with flip instead of rotate, but only rotate does the complete job.

[qiuyanzhe]

Sorry, but these do not generate the full group (25x25).

Oops, I made a mistake there. The bands cannot be swapped so easily, their rows may be in different phases. So sorry

[Mathimagics]

Oops, I made a mistake there. The bands cannot be swapped so easily, their rows may be in different phases. So sorry

No problem, I make mistakes all the time!

In fact I just made a rather bad mistake on the 25x25 case also ...

In copying the code (my usual hacking technique) for doing 16x16 ops into a 25x25 op set, I forgot to change the number of rows that make up a band-swap from 4 to 5.

This had no effect on my "full group" size (this is the set of all possible swap ops + rotate + flip, which I use to establish the symmetry group size for comparison purposes). This op set had enough redundancy to obscure my blunder ...

But it does mean that my own 25x25 triplet is now shown to be an impostor. A loss of elegance owing to invalidity!

PS: qiuyanzhe might not be aware of my track record for public humiliation on this forum. Everybody else does, though!

[Mathimagics]

.
blue, I take it you are using GAP to test your triplets?

If so, can you confirm the correct group size for 25 x 25 is:

• 17832200896512000000000000

[blue]

This seems to be a general solution (verified for N=1,2,...,10):

Code: Select all

For (N * N) x (N * N), N = 1:

    No generators ... trivial group

For (N * N) x (N * N), N = 2:

    A : quarter turn clockwise
    B : swap rows 1 & 2
    C : swap bands 1 & 2

For (N * N) x (N * N), N = 3:

    A : quarter turn clockwise
    B : swap rows 1 & 2
    C : swap bands 2 & 3

For (N * N) x (N * N), even N > 2:

    A : quarter turn clockwise

    B : swap rows 1 & 2
        cycle bands 2 through N ... (2->3->4->...N->2)
           B^N does only the band cycling
           B^(N-1) does only the row swap

    C : cycle rows 2 through N ... (2->3->4->...N->2)
        swap bands 2 & 3
           C^N does only the row cycling
           C^(N-1) does only the band swap

For (N * N) x (N * N), odd N > 3:

    A : quarter turn clockwise

    B : swap rows 1 & 2
        cycle bands 3 through N ... (3->4->...N->3)
           B^(N-1) does only the band cycling
           B^(N-2) does only the row swap

    C : cycle rows 3 through N ... (3->4->...N->3)
        swap bands 2 & 3
           C^(N-1) does only the row cycling
           C^(N-2) does only the band swap


N=2 is a special case of the N>2 setup, where C is omitted, and the cycle length is 1.
N=3 is a special case of the N>3 setup, where the cycle lengths are 1.

Edit: Added a C transformation for N=2, that doesn't conform to the general "N even, N > 2" case.
(I thought I had verified it "by hand" for just {A,B}. I made a mistake somewhere.)

[blue]

blue, I take it you are using GAP to test your triplets?

If so, can you confirm the correct group size for 25 x 25 is:

• 17832200896512000000000000

The group size is correct ... 2*(5!)^(2*(5+1)).

I'm not using GAP ... custom code instead.
For a hint at what I'm doing, these are my notes from the 16x16 case:

Hidden Text: Show

Code: Select all

A : swap (band 1) rows 1 & 2
    cycle bands 2,3,4 "down" (2 -> 3 -> 4 -> 2)
        -- then
            A^3 swaps rows 1&2
            A^2 cycles bands 2,3,4 "up" (4 -> 3 -> 2 -> 4)
B : cycle (band 1) rows 2,3,4 "down" (2 -> 3 -> 4 -> 2)
    swap bands 2 & 3
        -- then
            B^2 cycles rows 2,3,4 "up" (4 -> 3 -> 2 -> 4)
            B^3 swaps bands 2&3
C : quarter turn clockwise
        -- then
            C^2 reverses the band order
                reverses the row order in each band
                reverses the stack order
                reverses the column order in each stack
        -- then if T is a "bands & rows" permutation,
            CCC(T)C does to stacks & columns, what T does to bands & rows
        -- and if T is the transformations that reverses the overall row order,
            CT is the "transpose"/"diagonal reflection" operation
            note: T = AACCAACCAA   ***NO** : this only reverses the band order

band order:
    * -- means:
            row order is reversed in each band
            stack order is reversed
            column order is reversed in each stack

.1234        e - identity transformation
.4321*       CC
.1342        AA
.2431*       CCAA        CCAA(X) = C(C(A(A(X))))
.1423        AAAA
.3241*       CCAAAA

.4213*       AACC
.3124        CCAACC
.4132*       AAAACC
.2314        CCAAAACC

.2314*       AACCAA
.4132        CCAACCAA
.2143*       AAAACCAA
.3412        CCAAAACCAA

.3412*       AACCAAAA
.2143        CCAACCAAAA
.3124*       AAAACCAAAA
.4213        CCAAAACCAAAA

.3241        AACCAACC
.1423*       CCAACCAACC

.2431        AACCAACCAAAA
.1342*       CCAACCAACCAAAA

.4321        AACCAACCAA
.1234*       CCAACCAACCAA

.1324        BBB
.4231*       BBBCC
.1432        BBBAA
.2341*       BBBCCAA
.1243        BBBAAAA
.3421*       BBBCCAAAA

.4123*       BBBAACC
.3214        BBBCCAACC
.4312*       BBBAAAACC
.2134        BBBCCAAAACC

.2134*       BBBAACCAA
.4312        BBBCCAACCAA
.2413*       BBBAAAACCAA
.3142        BBBCCAAAACCAA

.3142*       BBBAACCAAAA
.2413        BBBCCAACCAAAA
.3214*       BBBAAAACCAAAA
.4123        BBBCCAAAACCAAAA

.3421        BBBAACCAACC
.1243*       BBBCCAACCAACC

.2341        BBBAACCAACCAAAA
.1432*       BBBCCAACCAACCAAAA

.4231        BBBAACCAACCAA
.1324*       BBBCCAACCAACCAA

then define:
    D := CCAACCAACCAA
        -- reverses the row order in each band

band 1 row order:
    * -- means:
            row order is reversed in bands 2,3 & 4
            stack order is reversed
            column order is reversed in each stack

.1234        e - identity transformation
.4321*       D
.1342        BB
.2431*       DBB
.1423        BBBB
.3241*       DBBBB

.4213*       BBD
.3124        DBBD
.4132*       BBBBD
.2314        DBBBBD

.2314*       BBDBB
.4132        DBBDBB
.2143*       BBBBDBB

.3412*       BBDBBBB
.2143        DBBDBBBB
.3124*       BBBBDBBBB
.4213        DBBBBDBBBB

.3241        BBDBBD
.1423*       DBBDBBD
.3412        BBBBDBBD

.2431        BBDBBDBBBB
.1342*       DBBDBBDBBBB

.4321        BBDBBDBB
.1234*       DBBDBBDBB

.2134        AAA
.3421*       AAAD
.3142        AAABB
.4231*       AAADBB
.4123        AAABBBB
.2341*       AAADBBBB

.2413*       AAABBD
.1324        AAADBBD
.1432*       AAABBBBD
.3214        AAADBBBBD

.3214*       AAABBDBB
.1432        AAADBBDBB
.1243*       AAABBBBDBB

.4312*       AAABBDBBBB
.1243        AAADBBDBBBB
.1324*       AAABBBBDBBBB
.2413        AAADBBBBDBBBB

.2341        AAABBDBBD
.4123*       AAADBBDBBD
.4312        AAABBBBDBBD

.4231        AAABBDBBDBBBB
.3142*       AAADBBDBBDBBBB

.3421        AAABBDBBDBB
.2134*       AAADBBDBBDBB


Edit: Added a note about something being incorrect in the "notes".

[blue]

Hi Mathimagics,

A question for you: what does GAP give, for the minimum generator count for the subgroup containing only the "bands & rows" permutations ... for 9x9 and 16x16, say ?

[Mathimagics]

what does GAP give, for the minimum generator count for the subgroup containing only the "bands & rows" permutations ... for 9x9 and 16x16, say ?

The answer is 2 for any size (9, 16, 25, 36)

[blue]

Interesting.
So two like that, with either a flip or quarter turn, would generate the full group.

[Mathimagics]

.
I think that we do not have to distinguish between even and odd N ...

• x = ShiftR(1...N-2) + ShiftB(1...N-1)

• y = ShiftR(1...N-1) + ShiftB(1...N-2)

• z = Rotate

Seems to work for all N > 2.

For N = 3, the (1...N-2) shifts disappear, and the (1...N-1) shifts become single swaps. This is the minimal form we started with in my OP, and this form also applies to the special N = 2 case, as blue indicated.

GAP verified for N = 3, 4, 5, 6, 7, 8, 9. Looks kosher!

[Mathimagics]

Interesting.
So two like that, with either a flip or quarter turn, would generate the full group.

Tested this with GAP on 25x25 case, and this is true, but ONLY with a quarter turn! Flip comes up short ...

[blue]

I think that we do not have to distinguish between even and odd N ...

(...)

GAP verified for N = 3, 4, 5, 6, 7, 8, 9. Looks kosher!

Nice

Interesting.
So two like that, with either a flip or quarter turn, would generate the full group.

Tested this with GAP on 25x25 case, and this is true, but ONLY with a quarter turn! Flip comes up short ...

Either one should work.

Added: I think I see the problem ...

• x = ShiftR(1...N-2) + ShiftB(1...N-1)

• y = ShiftR(1...N-1) + ShiftB(1...N-2)

• z = Rotate

{x,y} doesn't generate the full "bands & rows" group ... band N never changes.

Try these:

• x = ShiftR(1...N) + ShiftB(1...N-1)
• y = ShiftR(1...N-1) + ShiftB(1...N)
• z = Rotate

• x = ShiftR(1...N) + ShiftB(1...N-1)
• y = ShiftR(1...N-1) + ShiftB(1...N)
• z = Flip

{x,y} generates the full "bands & rows" group, for N=2,3,4
I can't test anything over N=4, without learning GAP.

Note: Where you wrote "ShiftR(1...N-2) + ShiftB(1...N-1)", I assumed that ShiftR was applied first, followed by ShiftB.
[ I don't think your earlier posts specified any particular interpretation for the order of the operations. ]

[Mathimagics]

.
Hi blue!

Ok, firstly I need to clarify a mistake I made on the "rows and bands" tests. You suggested that as long as we had a complete generator for rows/bands, then either rotate or flip should produce the full group when added to this generator.

This is, of course, true!

But, when I tested this on N=5 (25x25), however, it failed for flip, but worked for rotate.

I failed to appreciate the reason for the flip failure, however, until I redid the test, paying more attention this time!

I assumed that the SmallGeneratingSet GAP function that I used to get the rows/bands generating set would have 2 elements, which was suggested by my tests on N=3 and 4. But in this case it actually had 3. I only extracted the first 2 permutations, and so, as a result, my minimal generator did NOT generate the full set of row/band permutations.

(It turns out that the rows/bands group for N=5 is "not solvable" (whatever that means). This means that that GAP can not guarantee that the SmallGeneratingSet returned is in fact the minimum size. Solvable groups apparently allow easy calculation of a minimal generator. One suspects that a 2-element generator for N=5 DOES in fact exist, and that would of course work with both rotate and flip to produce the full group.)

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)!

Thus I am able to eliminate two swaps in each of x and y.

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!

[Mathimagics]

Try these:

• x = ShiftR(1...N) + ShiftB(1...N-1)
• y = ShiftR(1...N-1) + ShiftB(1...N)
• z = Rotate or Flip

Yes indeed, extending each shift by 1 row/band means that {x, y} generates full row/band subgroup, and so this works with either rotate or flip.

Confirmed for N=5 and N=6.

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.

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

[Mathimagics]

.
We can simplify the notation a little, writing rs(k), bs(k) for ShiftR(1...k), ShiftB(1...k), q for quarter-turn, f for flip.

So, to recap briefly, we can write our two universal (ie any box size N > 2) generators as triples {x,y,z}:

• SG1 = { rs(N-1) + bs(N), rs(N) + bs(N-1), z} (z = q or f)

• SG2 = { rs(N-2) + bs(N-1), rs(N-1) + bs(N-2), q}

Let HG = {x,y}. So HG1 generates the complete set of row/band permutations, ie |HG1| = N! ^ (N+1).

But HG2 generates only a subset, |HG2| = (N-1)! ^ (N-1). (HG2[N] is basically the same as HG1[N-1]). Nevertheless, with q added it suffices to generate he complete SG.

[EDIT] Fixed the exponent in |HG1| formula