Opened 12 years ago

Closed 12 years ago

Last modified 12 years ago

#8549 closed enhancement (fixed)

Implements cycle index for permutation groups, toward Polya enumeration

Reported by: nborie Owned by: nborie
Priority: major Milestone: sage-4.4.4
Component: combinatorics Keywords: permutation groups, cycle index, Polya enumeration
Cc: sage-combinat Merged in: sage-4.4.4.alpha0
Authors: Nicolas Borie, Nicolas M. Thiéry Reviewers: Nicolas M. Thiéry, Nicolas Borie, Rob Beezer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by nborie)

Let G a permutation group. Each permutation of G has a cycle type. The goal of this ticket is to add a method for permutation group which returns a symmetric function in the monomial symmetric functions whose terms are the numbers of permutation in G having the cycle type (Partition) indexing the corresponding monomial.

Attachments (1)

trac_8549_cycle_enumerator-nb.patch (7.2 KB) - added by nborie 12 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 12 years ago by nborie

  • Description modified (diff)
  • Summary changed from Add a cycle enumerator for Permutation Group to Add a cycle enumerator polynomial for Permutation Group

comment:2 Changed 12 years ago by nborie

  • Status changed from new to needs_review

This should allow to do some plethysm very easily.

Suggestion welcome to improve the latex math line and make it more nice and understandable.

comment:3 Changed 12 years ago by nthiery

  • Summary changed from Add a cycle enumerator polynomial for Permutation Group to Implements cycle index for permutation groups, toward Polya enumeration

comment:4 Changed 12 years ago by nborie

After face to face discussion, this patch is ready for review!

comment:5 Changed 12 years ago by nthiery

  • Authors set to Nicolas Borie, Nicolas M. Thiéry
  • Cc nthiery removed
  • Keywords groups index Polya added
  • Reviewers set to Nicolas M. Thiéry, Nicolas Borie
  • Status changed from needs_review to positive_review

comment:6 Changed 12 years ago by jhpalmieri

  • Status changed from positive_review to needs_work

If I apply "trac_8549_cycle_enumerator-nb.patch" on top of 4.4.alpha1, all tests pass. If I instead apply the patch from #8500, all tests pass. If I apply both patches, though, then I get a doctest failure:

sage -t -long "devel/sage/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py"
**********************************************************************
File "/Applications/sage_builds/sage-4.4.alpha1/devel/sage/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py", line 315:
    sage: len(C.points())
Exception raised:
    Traceback (most recent call last):
      File "/Applications/sage_builds/sage-4.4.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Applications/sage_builds/sage-4.4.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Applications/sage_builds/sage-4.4.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_6[7]>", line 1, in <module>
        len(C.points())###line 315:
    sage: len(C.points())
      File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py", line 327, in points
        self.__points = self._points_fast_sqrt() # this is fast using Zech logarithms
      File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py", line 239, in _points_fast_sqrt
        points.append(self.point([x, v+sqrtD, one], check=True))
      File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/generic/scheme.py", line 256, in point
        return self._point_class(self, v, check=check)
      File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/generic/algebraic_scheme.py", line 196, in _point_class
        return self.__A._point_class(*args, **kwds)
      File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/generic/projective_space.py", line 535, in _point_class
        return morphism.SchemeMorphism_projective_coordinates_field(*args, **kwds)
      File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/generic/morphism.py", line 608, in __init__
        X.codomain()._check_satisfies_equations(v)
      File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/generic/algebraic_scheme.py", line 465, in _check_satisfies_equations
        raise TypeError, "Coordinates %s do not define a point on %s"%(list(v),self)
    TypeError: Coordinates [7*a + 9, 2*a + 2, 1] do not define a point on Hyperelliptic Curve over Finite Field in a of size 11^2 defined by y^2 + (x^2 + 2)*y = x^5 + x + 10
**********************************************************************
1 items had failures:
   1 of   8 in __main__.example_6
***Test Failed*** 1 failures.
For whitespace errors, see the file /Users/palmieri/.sage//tmp/.doctest_hyperelliptic_finite_field.py
	 [8.2 s]

comment:7 follow-up: Changed 12 years ago by jhpalmieri

I'm sorry, I forgot to say that I've only seen this on a Mac (OS X 10.6.3). On sage.math, all tests pass.

comment:8 in reply to: ↑ 7 Changed 12 years ago by rbeezer

Replying to jhpalmieri:

I'm sorry, I forgot to say that I've only seen this on a Mac (OS X 10.6.3). On sage.math, all tests pass.

#8500 and #8549 together pass all long tests on 64-bit Ubuntu 9.04. I also saw Mike Hansen at Sage Days 21 test just the file sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py with both patches and it passed all tests as well. I'll be working on a review at some point today.

comment:9 Changed 12 years ago by rbeezer

Nicolas(s),

This is a nice addition, and I can already think of a use for it in a classroom example.

Some small comments/suggestions:

  1. One small bit of language, in
Here are the cycle index of some permutation groups

I would write the plural as "cycle indices." Nicely written otherwise.

  1. Would there be some way to qualify a value for the parent keyword as being legitimate? For example, with D=DihedralGroup(7), 14*D.cycle_index(parent=QQ) goes boom. It doesn't seem that there is a simple type to test on (but maybe I'm wrong on this), but it does look like parent need only implement term() and sum(). Would it work to put something like parent.term(Partition([1]), 1) in a try/except block?
  1. Documentation.

(a) Do you want to add this into the reference manual?
(b) Last doctest block needs a preceding "::" to make it render as verbatim.
(c) Two instances of "cycle_type" near the top print weird due to the underscore.

Important stuff: builds and passes long tests, works as advertised. So I'm ready to give this a positive review subject to the above minor items.

Rob

comment:10 Changed 12 years ago by rbeezer

See #8500 for the results of further OSX testing on this combination.

comment:11 Changed 12 years ago by nthiery

  • Reviewers changed from Nicolas M. Thiéry, Nicolas Borie to Nicolas M. Thiéry, Nicolas Borie, Robert Beezer

Hi,

I just wrote a quick patch in the queue implementing the requested changes, and adding FinitePermutationGroups? to the ref manual where it was missing. Nicolas, please double check, fold, and reupload.

Changed 12 years ago by nborie

comment:12 Changed 12 years ago by nborie

  • Status changed from needs_work to needs_review

Thanks very much for these fix.

All tests pass for sage, all tests long and optionnal pass for the finite_permutation_groups, the doc is well built... New comments for parent argument make also more clear the doc.

Positive Review from me. Thanks you Rob for pointing improvements and fix.

comment:13 Changed 12 years ago by nborie

  • Status changed from needs_review to positive_review

comment:14 Changed 12 years ago by nborie

I change two times the status of this patch but I precise the last change come from Nicolas Thiéry.

This positive review is also modulo the comment

If I apply "trac_8549_cycle_enumerator-nb.patch" on top of 4.4.alpha1, all tests pass. If I instead apply the patch from #8500, all tests pass. If I apply both patches, though, then I get a doctest failure

I currently have no possible access to any OS X machine. All my tests was computing from Ubuntu machines.

comment:15 Changed 12 years ago by mhansen

  • Merged in set to sage-4.4.4.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:16 Changed 12 years ago by mhansen

  • Reviewers changed from Nicolas M. Thiéry, Nicolas Borie, Robert Beezer to Nicolas M. Thiéry, Nicolas Borie, Rob Beezer
Note: See TracTickets for help on using tickets.