Optimisations + corrections to latin.py

[b6699e46-0a76-473a-9c8a-88795bfcd32d]

• Removed code that used gap.Representative in an unsafe manner (assumed that the ordering would be the same on each execution but the GAP manual says that this may not be the case). Previous code did work but was not safe.
• Replacement tau_to_bitrade uses correct and straightforward combinatorial approach.
• Replacement of p3_group_bitrade_generators is orders of magnitude faster; uses GAP's IsomorphismPermGroup instead of explicitly constructing a natural homomorphism.

CC: @sagetrac-sage-combinat

Component: combinatorics

Issue created by migration from https://trac.sagemath.org/ticket/4341

[wdjoyner]

comment:1

This applies cleanly to 3.2 and passes sage -testall. However, I have several (possibly very stupid) questions about the docstrings, which I've passed on to the author off-list (to save myself the embarrassment of asking dumb questions:-). I prefer to wait until I hear back to give an appraisal.

[wdjoyner]

comment:2

Attachment: ch-latin.patch.gz

Regarding the "to do" using nauty: please don't. Robert Miller's code NICE does this fine:

sage: from sage.combinat.matrices.latin import *
sage: M = matrix([(0, 1, 2, 3), (2, 3, 0, 1), (3, 2, 1, 0), (1, 0, 3, 2)])
sage: L = LatinSquare(M)
sage: L.is_latin_square()
True
sage: from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct
sage: A = MatrixStruct(M)
sage: autgp = A.automorphism_group()
sage: gens = [[j+1 for j in autgp[0][i]] for i in range(len(autgp[0]))]
sage: S4 = SymmetricGroup(4)
sage: G = PermutationGroup([S4(x) for x in gens]); G
Permutation Group with generators [(1,2)(3,4)]

An easy "to do": take the very short MOLS codes in Guava (included in Sage), at http://sage.math.washington.edu/home/wdj/guava/lib/matrices.gi, and translate it into Python/Sage/latin.py code. (MOLS are used to construct optimal non-linear codes, but non-linear codes have not yet been implemented in Sage.)

I'm currently running tests on this (second) patch and will post again soon.

[wdjoyner]

comment:3

This looks good to me. Applies cleanly to 3.2.alpha0 and passes sage -testall.

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

Description changed:

--- 
+++ 
@@ -1,5 +1,3 @@
 * Removed code that used gap.Representative in an unsafe manner (assumed that the ordering would be the same on each execution but the GAP manual says that this may not be the case). Previous code did work but was not safe.
-
 * Replacement tau_to_bitrade uses correct and straightforward combinatorial approach.
-
 * Replacement of p3_group_bitrade_generators is orders of magnitude faster; uses GAP's IsomorphismPermGroup instead of explicitly constructing a natural homomorphism.

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:5

Merged in Sage 3.2.1.alpha1