Opened 12 years ago
Closed 12 years ago
#4115 closed defect (fixed)
[with patch, positive review] Double coset problems
Reported by: | rlm | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-3.1.3 |
Component: | group theory | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Implements computations of properties which form double cosets. For example, if G is isomorphic to H, and m : G -> H is an isomorphism, then the set of all isomorphisms is the double coset Aut(H) m Aut(G).
This algorithm is pretty close to the canonical label algorithm, but it is a more efficient way to implement the isomorphism question. If the objects are not isomorphic, it will tend to discover this pretty quickly, via refinement invariants and examining the partition structure. If they are isomorphic, chances are this isomorphism will be discovered quickly and the algorithm will terminate at that moment.
Attachments (1)
Change History (16)
comment:1 Changed 12 years ago by
- Summary changed from [with patch, not ready for review] Double coset problems to [with patch, needs review] Double coset problems
comment:2 Changed 12 years ago by
comment:3 Changed 12 years ago by
You need a more current release. rc4 will do fine, not sure about rc3 since some patches in that area went into rc4 IIRC:
mabshoff@sage:/scratch/mabshoff/release-cycle/sage-3.1.2.rc4/devel/sage$ patch -p1 --dry-run < ~/trac_4115-double-cosets.patch\?format\=raw patching file sage/groups/perm_gps/partn_ref/automorphism_group_canonical_label.pxd patching file sage/groups/perm_gps/partn_ref/automorphism_group_canonical_label.pyx patching file sage/groups/perm_gps/partn_ref/data_structures_pxd.pxi patching file sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi patching file sage/groups/perm_gps/partn_ref/double_coset.pxd patching file sage/groups/perm_gps/partn_ref/double_coset.pyx patching file sage/groups/perm_gps/partn_ref/refinement_binary.pxd patching file sage/groups/perm_gps/partn_ref/refinement_binary.pyx patching file sage/groups/perm_gps/partn_ref/refinement_graphs.pxd patching file sage/groups/perm_gps/partn_ref/refinement_graphs.pyx patching file sage/groups/perm_gps/partn_ref/refinement_matrices.pxd patching file sage/groups/perm_gps/partn_ref/refinement_matrices.pyx patching file setup.py
Cheers,
Michael
comment:4 Changed 12 years ago by
My guess is that once you apply #4097 to rc3 it will work with that release or even earlier ones.
Cheers,
Michael
comment:5 Changed 12 years ago by
With this patch applied to 3.1.2.rc3, I got several failures including this one:
wdj@hera:~/sagefiles/sage-3.1.2.rc3$ ./sage -t devel/sage/sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi sage -t devel/sage/sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi********************************************************************** File "/home/wdj/sagefiles/sage-3.1.2.rc3/tmp/data_structures_pyx.py", line 7: sage: import sage.groups.perm_gps.partn_ref.data_structures Exception raised: Traceback (most recent call last): File "/home/wdj/sagefiles/sage-3.1.2.rc3/local/lib/python2.5/doctest.py", line 1228, in __run compileflags, 1) in test.globs File "<doctest __main__.example_0[2]>", line 1, in <module> import sage.groups.perm_gps.partn_ref.data_structures###line 7: sage: import sage.groups.perm_gps.partn_ref.data_structures ImportError: No module named data_structures
This seems fairly serious so I'm guessing I should move one to rc4 instead. Sorry for the delay. I tried soing something witth this at work but my machine there is relatively slow.
comment:6 Changed 12 years ago by
Sorry about that, data_structures
was a module that I ended up not including, but since its ghost was still loitering around in build, tests passed for me...
comment:7 Changed 12 years ago by
comment:8 follow-up: ↓ 9 Changed 12 years ago by
I still get this data_structures error after applying #4131, #4115 and sage -b and sage -testall:
The following tests failed: sage -t devel/sage/sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi sage -t devel/sage/sage/groups/perm_gps/partn_ref/refinement_binary.pyx Total time for all tests: 5376.0 seconds Please see /home/wdj/sagefiles/sage-3.1.2.rc4/tmp/test.log for the complete log from this test.
wdj@hera:~/sagefiles/sage-3.1.2.rc4$ ./sage -t devel/sage/sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi sage -t devel/sage/sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi********************************************************************** File "/home/wdj/sagefiles/sage-3.1.2.rc4/tmp/data_structures_pyx.py", line 7: sage: import sage.groups.perm_gps.partn_ref.data_structures Exception raised: Traceback (most recent call last): File "/home/wdj/sagefiles/sage-3.1.2.rc4/local/lib/python2.5/doctest.py", line 1228, in __run compileflags, 1) in test.globs File "<doctest __main__.example_0[2]>", line 1, in <module> import sage.groups.perm_gps.partn_ref.data_structures###line 7: sage: import sage.groups.perm_gps.partn_ref.data_structures ImportError: No module named data_structures ********************************************************************** 1 items had failures: 1 of 3 in __main__.example_0 ***Test Failed*** 1 failures. For whitespace errors, see the file /home/wdj/sagefiles/sage-3.1.2.rc4/tmp/.doctest_data_structures_pyx.py [2.4 s] exit code: 1024 ---------------------------------------------------------------------- The following tests failed: sage -t devel/sage/sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi Total time for all tests: 2.4 seconds
I guess one could argue that somehow the patch includes an "add" which was not needed and so this error is more-or-less spurious. However, this is more serious:
sage: from sage.groups.perm_gps.partn_ref.refinement_matrices import NonlinearBinaryCodeStruct --------------------------------------------------------------------------- ImportError Traceback (most recent call last) /home/wdj/sagefiles/sage-3.1.2.rc4/<ipython console> in <module>() ImportError: cannot import name NonlinearBinaryCodeStruct
This suggests that a new patch is needed? Or am I doing something stupid again?
comment:9 in reply to: ↑ 8 Changed 12 years ago by
Replying to wdj:
sage: from sage.groups.perm_gps.partn_ref.refinement_matrices import NonlinearBinaryCodeStruct?
This line does not show up at all in the patch, as-is right now. You should get the latest version of the patch and try again.
Changed 12 years ago by
comment:10 Changed 12 years ago by
- Description modified (diff)
comment:11 Changed 12 years ago by
A couple of cool examples:-)
sage: P.<x> = PolynomialRing(GF(2),"x") sage: g = x^3+x+1 sage: C1 = CyclicCodeFromGeneratingPolynomial(7,g); C1 Linear code of length 7, dimension 4 over Finite Field of size 2 sage: CW1 = matrix(GF(2),C1.list()) sage: C2 = HammingCode(3,GF(2)); C2 Linear code of length 7, dimension 4 over Finite Field of size 2 sage: CW2 = matrix(GF(2),C2.list()) sage: B = NonlinearBinaryCodeStruct(CW1) sage: C = NonlinearBinaryCodeStruct(CW2) sage: B.is_isomorphic(C) [0, 1, 2, 6, 5, 3, 4]
sage: C1 = ExtendedQuadraticResidueCode(23,GF(2)); C1 Linear code of length 24, dimension 12 over Finite Field of size 2 sage: C2 = ExtendedBinaryGolayCode(); C2 Linear code of length 24, dimension 12 over Finite Field of size 2 sage: C1 == C2 False sage: time CW1 = matrix(GF(2),C1.list()) CPU times: user 32.98 s, sys: 0.03 s, total: 33.01 s Wall time: 33.12 s sage: time CW2 = matrix(GF(2),C2.list()) CPU times: user 31.93 s, sys: 0.03 s, total: 31.95 s Wall time: 32.05 s sage: time B = NonlinearBinaryCodeStruct(CW1) CPU times: user 0.19 s, sys: 0.00 s, total: 0.19 s Wall time: 0.19 s sage: time C = NonlinearBinaryCodeStruct(CW2) CPU times: user 0.21 s, sys: 0.00 s, total: 0.21 s Wall time: 0.21 s sage: time B.is_isomorphic(C) CPU times: user 0.22 s, sys: 0.00 s, total: 0.22 s Wall time: 0.22 s [0, 1, 2, 3, 4, 5, 14, 19, 23, 21, 16, 15, 18, 17, 22, 7, 11, 12, 8, 6, 10, 13, 9, 20] sage:
This is a 24x4096 matrix!
So far so good. I'm going to try to find some more complicated examples:-)
comment:12 Changed 12 years ago by
I'm confused by this output:
Put
def test(): G = SymmetricGroup(20) g = G("(11,12,13,14,15,16,17)") for i in range(10): C1 = RandomLinearCode(20,10,GF(2)) C2 = C1.permuted_code(g) CW1 = matrix(GF(2),C1.list()) CW2 = matrix(GF(2),C2.list()) B = NonlinearBinaryCodeStruct(CW1) C = NonlinearBinaryCodeStruct(CW2) ans = B.is_isomorphic(C) L = [j+1 for j in ans] h = G(L) G1 = C1.automorphism_group_binary_code() print i, g, h, h*g^(-1) in G1
called test.sage or something and attach it. It seems to me it should always return True.
sage: time test() 0 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 1 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 2 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 3 (11,12,13,14,15,16,17) (11,12,13,14,15,16) True 4 (11,12,13,14,15,16,17) (9,12,13,14,15,16,17) False 5 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 6 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 7 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 8 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 9 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True CPU times: user 88.99 s, sys: 0.10 s, total: 89.09 s Wall time: 90.93 s
If you change the script to
def test(): G = SymmetricGroup(20) g = G("(11,12,13,14,15,16,17)") for i in range(10): C1 = RandomLinearCode(20,10,GF(2)) C2 = C1.permuted_code(g) CW1 = matrix(GF(2),C1.list()) CW2 = matrix(GF(2),C2.list()) B = NonlinearBinaryCodeStruct(CW1) C = NonlinearBinaryCodeStruct(CW2) ans = B.is_isomorphic(C) L = [j+1 for j in ans] h = G(L) G1 = C1.automorphism_group_binary_code() print i, g, h, h^(-1)*g in G1
you get
sage: time test() 0 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 1 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 2 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 3 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 4 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 5 (11,12,13,14,15,16,17) (8,15,16,17,11)(12,13,14) False 6 (11,12,13,14,15,16,17) (10,12,13,14,15,16,17) False 7 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True 8 (11,12,13,14,15,16,17) (9,12,13,14,15,16,17) False 9 (11,12,13,14,15,16,17) (11,12,13,14,15,16,17) True CPU times: user 92.33 s, sys: 0.11 s, total: 92.45 s Wall time: 92.92 s
Again funny.
It should be g,h:C1->C2, so h^{(-1)*g in G1 should be true and h*g}(-1) in G1 should be false.
I'm probably misinterpreting something in the docstrings (and probably and still too sleepy to think straight:-) but something seems confusing to me here.
Can someone see the error here?
comment:13 Changed 12 years ago by
First of all, you should be using a LinearBinaryCodeStruct
for this, since these are linear binary codes, and the code will run much faster. The list
function of linear codes seemed pretty slow, so I posted something at #4145.
Second, after playing with this for a while, I realized that GAP permutations act on the right, which reverses the familiar multiplication:
sage: G = SymmetricGroup(20) sage: g = G("(11,12,13,14,15,16,17)") sage: h = G("(11,12)(13,14,15,16,17)") sage: h^(-1) (11,12)(13,17,16,15,14) sage: (h^(-1))*g (11,13) sage: g*(h^(-1)) (12,17)
So I think the first version of your function was the correct one. With the patches here and at #4145 applied, and with test
defined as below, I get nothing but True
s for 100 trials. Without #4145, I frequently get False
's. So perhaps #4145 is actually a bug fix!
def test(n): G = SymmetricGroup(20) g = G("(11,12,13,14,15,16,17)") for i in range(n): C1 = RandomLinearCode(20,10,GF(2)) C2 = C1.permuted_code(g) CW1 = matrix(GF(2),C1.list()) CW2 = matrix(GF(2),C2.list()) B = NonlinearBinaryCodeStruct(CW1) C = NonlinearBinaryCodeStruct(CW2) ans = B.is_isomorphic(C) L = [j+1 for j in ans] h = G(L) G1 = C1.automorphism_group_binary_code() print i, g, h, g*(h^(-1)), g*(h^(-1)) in G1 print G1
comment:14 Changed 12 years ago by
- Summary changed from [with patch, needs review] Double coset problems to [with patch, positive review] Double coset problems
I agree and also just gave #4145 a positive review, so now I give this a positive review too.
Michael: If you apply this please also apply #4145 at the same time. They need to go together.
Wow, this is a cool patch! There are a *ton* of improvements to the linear codes modules which will result from this....
comment:15 Changed 12 years ago by
- Resolution set to fixed
- Status changed from new to closed
Merged in Sage 3.1.3.alpha0
I know I'm missing something but could you tell me why this fails?