Add domains for permutation groups

mwhansen commented 13 years ago

Often, one wants to define a permutation group on a set other than {1,2,...,n} such as say {'a', 'b', 'c', 'd'}.

For example,

sage: G = PermutationGroup([ [('c','d')], [('a','c')] ])
sage: G.orbit('a')
['a', 'c', 'd']

Apply:

attachment: trac_10335-permgroup_domain-rebase.patch

Depends on #10334

CC: @sagetrac-sage-combinat @sagetrac-jasonbhill @rbeezer @jdemeyer

Component: group theory

Keywords: sd31

Author: Mike Hansen, Jason Hill, David Loeffler

Reviewer: Robert Miller, Rob Beezer, Nicolas Borie, Nicolas M. Thiéry

Merged: sage-4.7.2.alpha3

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

mwhansen commented 13 years ago

comment:1

This depends

mwhansen commented 13 years ago

Description changed:

--- 
+++ 
@@ -8,3 +8,4 @@
 ['a', 'c', 'd']

+Depends on #10334.

89c6e537-b2e3-45e6-882d-d4957b74ffe5 commented 13 years ago

Reviewer: Robert Miller

89c6e537-b2e3-45e6-882d-d4957b74ffe5 commented 13 years ago

Work Issues: needs rebase

89c6e537-b2e3-45e6-882d-d4957b74ffe5 commented 13 years ago

comment:3

Applying to sage-4.6.2.alpha0 on top of #10334, I get:

applying trac_10335-permgroup_domain-mh.patch
patching file sage/groups/perm_gps/permgroup.py
Hunk #5 FAILED at 321
1 out of 59 hunks FAILED -- saving rejects to file sage/groups/perm_gps/permgroup.py.rej
patching file sage/groups/perm_gps/permgroup_named.py
Hunk #10 succeeded at 313 with fuzz 2 (offset 0 lines).
Hunk #11 succeeded at 315 with fuzz 1 (offset -49 lines).
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_10335-permgroup_domain-mh.patch

The failure:

$ cat sage/groups/perm_gps/permgroup.py.rej
--- permgroup.py
+++ permgroup.py
@@ -320,7 +322,7 @@
         sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
         sage: TestSuite(G).run()
     """
-    def __init__(self, gens=None, gap_group=None, canonicalize=True, category = None):
+    def __init__(self, gens=None, gap_group=None, canonicalize=True, category=None, domain=None):
         r"""
         INPUT:

Looks trivial to fix, and I'm excited to see this feature in Sage. Thank you, Mike!

89c6e537-b2e3-45e6-882d-d4957b74ffe5 commented 13 years ago

Description changed:

--- 
+++ 
@@ -8,4 +8,4 @@
 ['a', 'c', 'd']

-Depends on #10334. +Depends on #8359 and #10334.

nthiery commented 13 years ago

comment:5

This was most likely a minor conflict with Rob's permgroup patches which were merged late in the 4.6.2 release cycle.

Only apply: trac_10335-permgroup_domain-mh.2.patch

nthiery commented 13 years ago

Changed work issues from needs rebase to none

nthiery commented 13 years ago

comment:6

Ah, the test fail, and that's because the patch still did not commute perfectly with trac_8359-coxeter-groups-permutation-nt.patch. we need to have this patch add the category argument to __init__ of permutation groups, and remove that part from 8359.

Mike: let me know if you can do it shortly, and then #8359 is fair game. Otherwise I'll handle it.

mwhansen commented 13 years ago

Description changed:

--- 
+++ 
@@ -8,4 +8,4 @@
 ['a', 'c', 'd']

-Depends on #8359 and #10334. +Depends on #10334.

mwhansen commented 13 years ago

comment:8

I've fixed the issue along with updating the patch at #8359.

Only apply: trac_10335-permgroup_domain-mh.patch

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

comment:9

This looks real good, Mike. I spent some time with this today. I know its not done yet, but hopefully the following will be helpful.

I applied the patch from sage-combinat for #8359 to 4.7.alpha1, as best I could tell (used patch from http://combinat.sagemath.org/hgwebdir.cgi/patches/rev/508d4942a6d2). One hunk failure at sage/combinat/root_system/all.py. Then #10334 had a hunk failure in sage/groups/perm_gps/permgroup.py and #10335 had a had failure in sage/categories/pushout.py. All easy to fix by hand, and maybe a result of not getting the right thing from the sage-combinat server.

Passed all tests in sage/groups/perm_gps, except two, so not too far off. Both doctest failures look very minor, and a result of routines I wrote that have been added recently.

**********************************************************************
File "/sage/dev/devel/sage-main/sage/groups/perm_gps/permgroup.py", line 1920:
    sage: G.subgroups()
Expected:
    [Permutation Group with generators [()],
     Permutation Group with generators [(2,3)],
     Permutation Group with generators [(1,2)],
     Permutation Group with generators [(1,3)],
     Permutation Group with generators [(1,2,3)],
     Permutation Group with generators [(1,3,2), (1,2)]]
Got:
    [Permutation Group with generators [()],
     Permutation Group with generators [(2,3)],
     Permutation Group with generators [(1,2)],
     Permutation Group with generators [(1,3)],
     Permutation Group with generators [(1,2,3)],
     Permutation Group with generators [(1,2), (1,3,2)]]
**********************************************************************
File "/sage/dev/devel/sage-main/sage/groups/perm_gps/permgroup.py", line 2082:
    sage: A.cosets(S)
Expected:
    Traceback (most recent call last):
    ...
    ValueError: Subgroup of SymmetricGroup(3) generated by [(1,2)] is not a subgroup of AlternatingGroup(3)
Got:
    Traceback (most recent call last):
      File "/sage/dev/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/sage/dev/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/sage/dev/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_61[29]>", line 1, in <module>
        A.cosets(S)###line 2082:
    sage: A.cosets(S)
      File "/sage/dev/local/lib/python/site-packages/sage/groups/perm_gps/permgroup.py", line 2099, in cosets
        raise ValueError("%s is not a subgroup of %s" % (S, self))
    ValueError: Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(1,2)] is not a subgroup of Alternating group of order 3!/2 as a permutation group
**********************************************************************

I think the stabilizer() routine needs some work.

try:
    postition = self._domain_to_gap[point]
except KeyError:
    return self.subgroup(gens=self.gens())
return self.subgroup(gap_group=gap.Stabilizer(self, point))

"position" is mis-spelled as first defined, and in the return, I think "point" should be replaced with "position". With these changes, this seems to work properly with a non-trivial domain in play.

Not a comprehensive look, but hopefully of use. Let me know what I can do to help (including assisting with documentation). It'd be nice if there was a patch, or something, at #8359 explaining how best to apply that work.

Rob

nthiery commented 13 years ago

comment:10

Hi Mike,

For the record: I rebased trac_10335-permgroup_domain-mh.patch on the sage-combinat server on top of #9949

nthiery commented 13 years ago

comment:11

Hi Mike!

Replying to @nthiery:

For the record: I rebased trac_10335-permgroup_domain-mh.patch on the sage-combinat server on top of #9949

With Rob we are both at Sage days 30, and would love to push permutation groups in. Rob is going to rebase #10334, and I'll finalize the review. #10335 itself needs rebase on 3.4.7, and has quite a few failing doctests, though most look harmless (it's just that the output of permutation groups have changed). Would there be any chance for you to work on this early this week?

Thanks!

Cheers, Nicolas

mwhansen commented 13 years ago

comment:12

Sure -- I'll try to get this taken care of tonight.

mwhansen commented 13 years ago

comment:13

I've fixed the doctest failures and updated the patch.

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

comment:14

I ran make ptestlong and got quite a few failures. I even tried it twice - not sure what is up.

Many were in sage/doc
Many were simply the new version of _repr_ for the symmetric group, and its subgroups
The latex() method is putting a comma between the cycles within each generator. Is this desired?

return ",".join(["(" + ",".join([latex(x) for x in cycle])+")" for cycle in self.cycle_tuples()])

At a minimum it is causing doctest failures.

73 failures in sage/rings/number_field/galois_group.py, likely all the same root cause

Saw these in the patch itself:

a stray "deprecated_function_alias" in a docstring
``selfs`` in a docstring

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 13 years ago

Dependencies: #10334

mwhansen commented 13 years ago

comment:16

I'm pretty sure that this patches addresses all of the above problems.

Apply trac_10335-permgroup_domain-mh.patch

mwhansen commented 13 years ago

comment:17

Fixed commit message.

Apply trac_10335-permgroup_domain-mh.patch

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 13 years ago

comment:18

I was very close to set a positive review for this patch but I got this faillure :

nicolas@lancelot:/opt/sage/devel/sage-combinat$ sage -t sage/groups/perm_gps/permgroup.py 
sage -t  "devel/sage-combinat/sage/groups/perm_gps/permgroup.py"
**********************************************************************
File "/opt/sage/devel/sage-combinat/sage/groups/perm_gps/permgroup.py", line 2550:
    sage: G.isomorphism_to(H)
Expected:
    Permutation group morphism:
      From: Permutation Group with generators [(2,3), (1,2,3)]
      To:   Permutation Group with generators [(1,2,4), (1,4)]
      Defn: [(2,3), (1,2,3)] -> [(2,4), (1,2,4)]
Got:
    Permutation group morphism:
      From: Permutation Group with generators [(2,3), (1,2,3)]
      To:   Permutation Group with generators [(1,2,4), (1,4)]
      Defn: [(2,3), (1,2,3)] -> [(2,4), (1,4,2)]
**********************************************************************
1 items had failures:
   1 of   9 in __main__.example_73

Is this a random test ? Is this test really unrandonized (sorry for such a word) ? I am running a 11.4 Ubuntu up to date on a macbook santa rosa 4,1. I got this faillure both using the sage combinat queue and a separate branch with only 10334 and 10335.

Also, in sage/groups/perm-gps/permgroup.py line 1119, there is still the micro typo : postition --> position

Anyway, It is a very very nice work and improvement of permutation groups.

mwhansen commented 13 years ago

comment:19

The failure you see is at #11427 . I'll put up a new patch fixing the typo.

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 13 years ago

comment:20

Attachment: trac_10335-permgroup_domain-mh.patch.gz

Nice shoot! I confirm that I use a lot the Gap database especially for Transitive Groups. The optional package was installed on my machine.

Thanks for your work and your rapidity for fixing this last typo.

I give this patch a positive review.

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 13 years ago

Changed reviewer from Robert Miller to Robert Miller, Rob Beezer, Nicolas Borie

jdemeyer commented 13 years ago

Description changed:

--- 
+++ 
@@ -7,5 +7,3 @@
 sage: G.orbit('a')
 ['a', 'c', 'd']

- -Depends on #10334.

nthiery commented 13 years ago

comment:22

For the record: when applying this patch with the sage-combinat queue on sage-4.7.2, I got an import loop, and used the extra patch to fix it.

nthiery commented 13 years ago

Description changed:

--- 
+++ 
@@ -7,3 +7,5 @@
 sage: G.orbit('a')
 ['a', 'c', 'd']

+ +

mwhansen commented 13 years ago

comment:23

Replying to @nthiery:

For the record: when applying this patch with the sage-combinat queue on sage-4.7.2, I got an import loop, and used the extra patch to fix it.

On 4.7.2?

nthiery commented 13 years ago

comment:24

Replying to @mwhansen:

Replying to @nthiery:

For the record: when applying this patch with the sage-combinat queue on sage-4.7.2, I got an import loop, and used the extra patch to fix it.

On 4.7.2?

Oops, 4.7.1 alpha2!

Sage-Combinat is not that much in advance :-)

jdemeyer commented 13 years ago

comment:26

New patch needs review.

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Changed keywords from none to sd31

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

comment:27

Replying to @jdemeyer:

New patch needs review.

Almost passes all tests on 4.7.1.alpha2 and I get no import problems.

But the German documentation has old _repr_ behavior. Aargh.

sage -t  -long -force_lib ooks/devel/sage/doc/de/tutorial/tour_groups.rst # 1 doctests failed
sage -t  -long -force_lib ooks/devel/sage/doc/de/tutorial/interfaces.rst # 1 doctests failed

Patch coming up, maybe.

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Attachment: trac_10335_german_tutorial_doc.patch.gz

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

comment:28

German doc patch should solve above problems. Gotta run - ticket needs "apply" block....

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Description changed:

--- 
+++ 
@@ -8,4 +8,7 @@
 ['a', 'c', 'd']

- +Apply: +1. attachment: trac_10335-permgroup_domain-mh.patch +2. attachment: trac_10335-permgroup_domain-import_loop_fix-nt.patch +3. attachment: trac_10335_german_tutorial_doc.patch

jdemeyer commented 13 years ago

comment:30

Note that attachment: trac_10335-permgroup_domain-import_loop_fix-nt.patch should have its commit message changed.

nthiery commented 13 years ago

Merge only if needed

nthiery commented 13 years ago

comment:32

Attachment: trac_10335-permgroup_domain-import_loop_fix-nt.patch.gz

Replying to @jdemeyer:

Note that attachment: trac_10335-permgroup_domain-import_loop_fix-nt.patch should have its commit message changed.

Oops, done.

nthiery commented 13 years ago

comment:33

Replying to @rbeezer:

German doc patch should solve above problems. Gotta run - ticket needs "apply" block....

Sounds good to me assuming the patch bot is happy.

jdemeyer commented 13 years ago

comment:34

The Russian tutorial (#9378) also needs to be fixed:

sage -t  -force_lib devel/sage/doc/ru/tutorial/interfaces.rst
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.2.alpha0/devel/sage-main/doc/ru/tutorial/interfaces.rst", line 167:
    sage: G.center()
Expected:
    Permutation Group with generators [()]
Got:
    Subgroup of (Permutation Group with generators [(3,4), (1,2,3)(4,5)]) generated by [()]
**********************************************************************

sage -t  -force_lib devel/sage/doc/ru/tutorial/tour_groups.rst
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.2.alpha0/devel/sage-main/doc/ru/tutorial/tour_groups.rst", line 24:
    sage: G.center()
Expected:
    Permutation Group with generators [()]
Got:
    Subgroup of (Permutation Group with generators [(3,4), (1,2,3)(4,5)]) generated by [()]
**********************************************************************

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

German and Russian language fixes combined

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Description changed:

--- 
+++ 
@@ -11,4 +11,4 @@
 **Apply:**
 1.  [attachment: trac_10335-permgroup_domain-mh.patch](https://github.com/sagemath/sage-prod/files/10651495/trac_10335-permgroup_domain-mh.patch.gz)
 2.  [attachment: trac_10335-permgroup_domain-import_loop_fix-nt.patch](https://github.com/sagemath/sage-prod/files/10651497/trac_10335-permgroup_domain-import_loop_fix-nt.patch.gz)
-3.  [attachment: trac_10335_german_tutorial_doc.patch](https://github.com/sagemath/sage-prod/files/10651496/trac_10335_german_tutorial_doc.patch.gz)
+3.  [attachment: trac_10335-tutorial-languages-fixes.patch](https://github.com/sagemath/sage-prod/files/10651498/trac_10335-tutorial-languages-fixes.patch.gz)

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

comment:35

Attachment: trac_10335-tutorial-languages-fixes.patch.gz

Replying to @jdemeyer:

The Russian tutorial (#9378) also needs to be fixed:

Applied #9378 and the two main patches here. (I do not understand what "merge if needed" is suppose to mean - so I included that). Rolled the Russian fixes up with the German fixes into one patch.

Passes all tests in doc directory.

Could we please review and merge this before anymore new languages surface? ;-) ;-)

Rob

nthiery commented 13 years ago

comment:36

Replying to @rbeezer:

Applied #9378 and the two main patches here. (I do not understand what "merge if needed" is suppose to mean - so I included that).

See comment 23 above.

Rolled the Russian fixes up with the German fixes into one patch.

Passes all tests in doc directory.

Could we please review and merge this before anymore new languages surface? ;-) ;-)

I checked your new patch, and am happy with it. Back to positive review. Thanks!

nthiery commented 13 years ago

Changed reviewer from Robert Miller, Rob Beezer, Nicolas Borie to Robert Miller, Rob Beezer, Nicolas Borie, Nicolas M. Thiéry

jdemeyer commented 13 years ago

Merged: sage-4.7.2.alpha0

jdemeyer commented 13 years ago

Changed merged from sage-4.7.2.alpha0 to none

jdemeyer commented 13 years ago

comment:38

Unfortunately, there is a doctest error on Solaris (to be more precise, the buildbot machine mark2):

sage -t -long  -force_lib devel/sage/sage/groups/perm_gps/permgroup.py
**********************************************************************
File "/home/buildbot/build/sage/mark-1/mark_full/build/sage-4.7.2.alpha0/devel/sage-main/sage/groups/perm_gps/permgroup.py", line 811:
    sage: G.gens_small()
Expected:
    [('a','b'), ('a','b','c')]
Got:
    [('b','c'), ('a','b','c')]
**********************************************************************

jdemeyer commented 13 years ago

Work Issues: Solaris doctest error

mwhansen commented 13 years ago

comment:39

What's the best way to test a fix on that machine? Do I have to log into mark2 and do a full build or is there a way to access that build?

sagemath / sage

Add domains for permutation groups #10335