Sage: Ticket #4115: [with patch, positive review] Double coset problems
https://trac.sagemath.org/ticket/4115
<p>
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).
</p>
<p>
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.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/4115
Trac 1.2Robert MillerMon, 15 Sep 2008 11:22:05 GMTsummary changed
https://trac.sagemath.org/ticket/4115#comment:1
https://trac.sagemath.org/ticket/4115#comment:1
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, not ready for review] Double coset problems</em> to <em>[with patch, needs review] Double coset problems</em>
</li>
</ul>
TicketDavid JoynerMon, 15 Sep 2008 12:37:27 GMT
https://trac.sagemath.org/ticket/4115#comment:2
https://trac.sagemath.org/ticket/4115#comment:2
<p>
I know I'm missing something but could you tell me why this fails?
</p>
<pre class="wiki">wdj@tinah:~/sagefiles/sage-3.1.2.rc1$ ./sage
----------------------------------------------------------------------
| SAGE Version 3.1.2.rc1, Release Date: 2008-09-09 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
Loading SAGE library. Current Mercurial branch is: dbl-coset
sage: hg_sage.apply("/home/wdj/sagefiles/trac_4115-double-cosets.patch")
cd "/home/wdj/sagefiles/sage-3.1.2.rc1/devel/sage" && hg status
cd "/home/wdj/sagefiles/sage-3.1.2.rc1/devel/sage" && hg status
cd "/home/wdj/sagefiles/sage-3.1.2.rc1/devel/sage" && hg import "/home/wdj/sagefiles/trac_4115-double-cosets.patch"
applying /home/wdj/sagefiles/trac_4115-double-cosets.patch
patching file sage/groups/perm_gps/partn_ref/refinement_binary.pyx
Hunk #1 FAILED at 21
1 out of 19 hunks FAILED -- saving rejects to file sage/groups/perm_gps/partn_ref/refinement_binary.pyx.rej
unable to find 'sage/groups/perm_gps/partn_ref/refinement_matrices.pxd' for patching
2 out of 2 hunks FAILED -- saving rejects to file sage/groups/perm_gps/partn_ref/refinement_matrices.pxd.rej
unable to find 'sage/groups/perm_gps/partn_ref/refinement_matrices.pyx' for patching
8 out of 8 hunks FAILED -- saving rejects to file sage/groups/perm_gps/partn_ref/refinement_matrices.pyx.rej
abort: patch failed to apply
</pre>
TicketMichael AbshoffMon, 15 Sep 2008 12:51:41 GMT
https://trac.sagemath.org/ticket/4115#comment:3
https://trac.sagemath.org/ticket/4115#comment:3
<p>
You need a more current release. rc4 will do fine, not sure about rc3 since some patches in that area went into rc4 IIRC:
</p>
<pre class="wiki">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
</pre><p>
Cheers,
</p>
<p>
Michael
</p>
TicketMichael AbshoffMon, 15 Sep 2008 12:55:22 GMT
https://trac.sagemath.org/ticket/4115#comment:4
https://trac.sagemath.org/ticket/4115#comment:4
<p>
My guess is that once you apply <a class="closed ticket" href="https://trac.sagemath.org/ticket/4097" title="#4097: enhancement: [with patch, positive review] matrix automorphism groups (closed: fixed)">#4097</a> to rc3 it will work with that release or even earlier ones.
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketDavid JoynerMon, 15 Sep 2008 21:51:45 GMT
https://trac.sagemath.org/ticket/4115#comment:5
https://trac.sagemath.org/ticket/4115#comment:5
<p>
With this patch applied to 3.1.2.rc3, I got several failures including this one:
</p>
<pre class="wiki">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
</pre><p>
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.
</p>
TicketRobert MillerTue, 16 Sep 2008 00:48:36 GMT
https://trac.sagemath.org/ticket/4115#comment:6
https://trac.sagemath.org/ticket/4115#comment:6
<p>
Sorry about that, <code>data_structures</code> was a module that I ended up not including, but since its ghost was still loitering around in build, tests passed for me...
</p>
TicketDavid JoynerTue, 16 Sep 2008 02:02:27 GMT
https://trac.sagemath.org/ticket/4115#comment:7
https://trac.sagemath.org/ticket/4115#comment:7
<p>
Okay. I applied <a class="closed ticket" href="https://trac.sagemath.org/ticket/4131" title="#4131: defect: [with patch, positive review] unbreak sage-clone (closed: fixed)">#4131</a> (using hg_scripts.apply) and <a class="closed ticket" href="https://trac.sagemath.org/ticket/4115" title="#4115: defect: [with patch, positive review] Double coset problems (closed: fixed)">#4115</a> to 3.1.2.rc4 and am running tests now. This looks like an extremely interesting patch so far!
</p>
TicketDavid JoynerTue, 16 Sep 2008 09:51:01 GMT
https://trac.sagemath.org/ticket/4115#comment:8
https://trac.sagemath.org/ticket/4115#comment:8
<p>
I still get this data_structures error after applying <a class="closed ticket" href="https://trac.sagemath.org/ticket/4131" title="#4131: defect: [with patch, positive review] unbreak sage-clone (closed: fixed)">#4131</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/4115" title="#4115: defect: [with patch, positive review] Double coset problems (closed: fixed)">#4115</a> and sage -b and sage -testall:
</p>
<pre class="wiki">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.
</pre><pre class="wiki">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
</pre><p>
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:
</p>
<pre class="wiki">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
</pre><p>
This suggests that a new patch is needed? Or am I doing something stupid again?
</p>
TicketRobert MillerWed, 17 Sep 2008 02:00:38 GMT
https://trac.sagemath.org/ticket/4115#comment:9
https://trac.sagemath.org/ticket/4115#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/4115#comment:8" title="Comment 8">wdj</a>:
</p>
<blockquote class="citation">
<p>
sage: from sage.groups.perm_gps.partn_ref.refinement_matrices import <a class="missing wiki">NonlinearBinaryCodeStruct?</a>
</p>
</blockquote>
<p>
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.
</p>
TicketRobert MillerWed, 17 Sep 2008 13:17:17 GMTattachment set
https://trac.sagemath.org/ticket/4115
https://trac.sagemath.org/ticket/4115
<ul>
<li><strong>attachment</strong>
set to <em>trac_4115-double-cosets.patch</em>
</li>
</ul>
TicketRobert MillerWed, 17 Sep 2008 15:43:20 GMTdescription changed
https://trac.sagemath.org/ticket/4115#comment:10
https://trac.sagemath.org/ticket/4115#comment:10
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/4115?action=diff&version=10">diff</a>)
</li>
</ul>
TicketDavid JoynerWed, 17 Sep 2008 23:13:11 GMT
https://trac.sagemath.org/ticket/4115#comment:11
https://trac.sagemath.org/ticket/4115#comment:11
<p>
A couple of cool examples:-)
</p>
<pre class="wiki">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]
</pre><pre class="wiki">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:
</pre><p>
This is a 24x4096 matrix!
</p>
<p>
So far so good. I'm going to try to find some more complicated examples:-)
</p>
TicketDavid JoynerThu, 18 Sep 2008 12:32:42 GMT
https://trac.sagemath.org/ticket/4115#comment:12
https://trac.sagemath.org/ticket/4115#comment:12
<p>
I'm confused by this output:
</p>
<p>
Put
</p>
<pre class="wiki">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
</pre><p>
called test.sage or something and attach it.
It seems to me it should always return True.
</p>
<pre class="wiki">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
</pre><p>
If you change the script to
</p>
<pre class="wiki">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
</pre><p>
you get
</p>
<pre class="wiki">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
</pre><p>
Again funny.
</p>
<p>
It should be g,h:C1->C2, so h<sup>(-1)*g in G1 should be true
and h*g</sup>(-1) in G1 should be false.
</p>
<p>
I'm probably misinterpreting something in the docstrings
(and probably and still too sleepy to think straight:-)
but something seems confusing to me here.
</p>
<p>
Can someone see the error here?
</p>
TicketRobert MillerThu, 18 Sep 2008 15:47:07 GMT
https://trac.sagemath.org/ticket/4115#comment:13
https://trac.sagemath.org/ticket/4115#comment:13
<p>
First of all, you should be using a <code>LinearBinaryCodeStruct</code> for this, since these are linear binary codes, and the code will run much faster. The <code>list</code> function of linear codes seemed pretty slow, so I posted something at <a class="closed ticket" href="https://trac.sagemath.org/ticket/4145" title="#4145: defect: [with patch, positive review] linear codes list function is slow (closed: fixed)">#4145</a>.
</p>
<p>
Second, after playing with this for a while, I realized that GAP permutations act on the right, which reverses the familiar multiplication:
</p>
<pre class="wiki">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)
</pre><p>
So I think the first version of your function was the correct one. With the patches here and at <a class="closed ticket" href="https://trac.sagemath.org/ticket/4145" title="#4145: defect: [with patch, positive review] linear codes list function is slow (closed: fixed)">#4145</a> applied, and with <code>test</code> defined as below, I get nothing but <code>True</code>s for 100 trials. Without <a class="closed ticket" href="https://trac.sagemath.org/ticket/4145" title="#4145: defect: [with patch, positive review] linear codes list function is slow (closed: fixed)">#4145</a>, I frequently get <code>False</code>'s. So perhaps <a class="closed ticket" href="https://trac.sagemath.org/ticket/4145" title="#4145: defect: [with patch, positive review] linear codes list function is slow (closed: fixed)">#4145</a> is actually a bug fix!
</p>
<pre class="wiki">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
</pre>
TicketDavid JoynerThu, 18 Sep 2008 17:11:07 GMTsummary changed
https://trac.sagemath.org/ticket/4115#comment:14
https://trac.sagemath.org/ticket/4115#comment:14
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] Double coset problems</em> to <em>[with patch, positive review] Double coset problems</em>
</li>
</ul>
<p>
I agree and also just gave <a class="closed ticket" href="https://trac.sagemath.org/ticket/4145" title="#4145: defect: [with patch, positive review] linear codes list function is slow (closed: fixed)">#4145</a> a positive review, so now I give this a positive review too.
</p>
<p>
Michael: If you apply this please also apply <a class="closed ticket" href="https://trac.sagemath.org/ticket/4145" title="#4145: defect: [with patch, positive review] linear codes list function is slow (closed: fixed)">#4145</a> at the same time. They need to go together.
</p>
<p>
Wow, this is a cool patch! There are a *ton* of improvements to the linear codes modules which will result from this....
</p>
TicketMichael AbshoffFri, 19 Sep 2008 00:48:18 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/4115#comment:15
https://trac.sagemath.org/ticket/4115#comment:15
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
Merged in Sage 3.1.3.alpha0
</p>
Ticket