Opened 5 years ago

Closed 5 years ago

#22066 closed enhancement (fixed)

implement MacMahon's Omega operator

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-7.6
Component: algebra Keywords:
Cc: cheuberg Merged in:
Authors: Daniel Krenn Reviewers: Clemens Heuberger
Report Upstream: N/A Work issues:
Branch: 482ab70 (Commits, GitHub, GitLab) Commit: 482ab70907bb11a8f55cff4860870b3af4ac3b31
Dependencies: #21832, #21833, #21966, #21968, #21976, #21999, #22064 Stopgaps:

Status badges

Description (last modified by cheuberg)

MacMahon's Omega operator takes a quotient of laurent polynomials and removes all negative exponents in the corresponding power series.

The aim of this ticket is to implement it.

Change History (43)

comment:1 Changed 5 years ago by dkrenn

  • Branch set to u/dkrenn/omega

comment:2 Changed 5 years ago by git

  • Commit set to 004d61d40fa1ca52be7980ab59188b5da411ecf9

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

d33a595minor rewrite to increase readability
5a5db0ballow passing mon in _element_constructor_
3a809a4fix pickling bug
be67f37determine parent at top of _element_constructor_
6137662rewrite to detect more specialized situations
0570355Merge branch 'u/dkrenn/laurent-efficient-construction' of trac.sagemath.org:sage into u/dakrenn/omega
0f88065quick-fix in normalize
c0fea6eMerge branch 'u/dkrenn/laurent-floor-hash' of trac.sagemath.org:sage into u/dakrenn/omega
9389e62use __call__ in subs to be more efficient
004d61dMerge branch 'u/dkrenn/laurent-subs' of trac.sagemath.org:sage into u/dakrenn/omega

comment:3 Changed 5 years ago by dkrenn

  • Dependencies set to #21832, #21833, #21833, #21966, #21968, #21976, #21999, #22064

comment:4 Changed 5 years ago by dkrenn

  • Authors set to Daniel Krenn

comment:5 Changed 5 years ago by git

  • Commit changed from 004d61d40fa1ca52be7980ab59188b5da411ecf9 to 4b1c37e34c2c5fa6264fd489e56e9e20cec3237d

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

41b1dcdlazy import Omega
58943d6rename Omega_higher --> Omega_ge
49e75f4fix imports in doctests
b122d0frename to homogenous_symmetric_function
0b6dba8name Omega_numerator_P private
907d12edocstring and tests for _Omega_numerator_P_
91ee1d0add "helper function" comment to some docstrings
c97bac4fix doc output
b085ca6module description
4b1c37ereferences

comment:6 Changed 5 years ago by dkrenn

  • Status changed from new to needs_review

comment:7 Changed 5 years ago by dkrenn

  • Cc cheuberg added

comment:8 follow-up: Changed 5 years ago by chapoton

see also #10669

comment:9 Changed 5 years ago by git

  • Commit changed from 4b1c37e34c2c5fa6264fd489e56e9e20cec3237d to 79fe3b36ea31ccc8a836a88e9d09c280942172bf

Branch pushed to git repo; I updated commit sha1. New commits:

79fe3b3extend docstring at top of file

comment:10 in reply to: ↑ 8 Changed 5 years ago by dkrenn

Replying to chapoton:

see also #10669

Thank you for mentioning this. (I have never thought anyone already created a ticket for this.) ;)

Last edited 5 years ago by dkrenn (previous) (diff)

comment:11 Changed 5 years ago by cheuberg

  • Dependencies changed from #21832, #21833, #21833, #21966, #21968, #21976, #21999, #22064 to #21832, #21833, #21966, #21968, #21976, #21999, #22064

Removed duplicate dependency #21833

comment:12 follow-up: Changed 5 years ago by git

  • Commit changed from 79fe3b36ea31ccc8a836a88e9d09c280942172bf to 82327c883958a503e6291605e814ae36e7a35085

Branch pushed to git repo; I updated commit sha1. New commits:

f7e9540fix doctest (conversion to symbolic)
82327c8Merge branch 'u/dakrenn/laurent-subs' into t/22066/omega

comment:13 in reply to: ↑ 12 Changed 5 years ago by dkrenn

Merged in changed dependencies.

comment:14 Changed 5 years ago by git

  • Commit changed from 82327c883958a503e6291605e814ae36e7a35085 to fceb3e170e79f1390eee97d003d3f894954e901f

Branch pushed to git repo; I updated commit sha1. New commits:

f046132Python3 iteritems
0db5399MPolynomial: correct coefficient ring when dict as input
a20fb8arevert 0f88065556 quick-fix in normalize
397301adoctest example of ticket 21999
fceb3e1Merge branch 't/21999/laurent-floor-hash' into t/22066/omega

comment:15 follow-up: Changed 5 years ago by cheuberg

  • Description modified (diff)
  • Status changed from needs_review to needs_work

This is a review of this ticket modulo its dependencies.

General:

  1. I am not happy to have Omega in the global name space. There might be other uses of the upper case greek letter Omega which might as well live in the global name space, e.g., in context with asymptotics. Thus I suggest to have it as MacMahonOmega or something like that, perhaps with an alias in the docstring.
  1. Is there a reason why some of the auxiliary functions are visible and some others are hidden (e.g., for #22067?). In that case, I suggest to have one example in the module documentation which demonstrates how to use Omega and perhaps one other example there which demonstrates how to use the other functions efficiently.
  1. I think that "laurent" should be capitalized throughout, cf. the Wikipedia article.
  1. Nowadays, the developers guide wants us to store all bibliographical references in SAGE_ROOT/src/doc/en/reference/references/index.rst.
  1. Long descriptions in docstrings: The developer guide does not give clear indications; nevertheless, I suggest to use the same command form as in the short description block above. Otherwise, it seems to be strange to have "Return ..." ... "this calculates".

Function Omega:

  1. expression is allowed to be a Factorization (as per the Tests), but this is not documented.
  1. Add examples demonstrating all allowed input variants (expression only, without denominator; denominator as a non-factorized Polynomial); perhaps use a simple example to demonstrate all useful variations.
  1. There are two consecutive lines of imports from sage.rings.polynomial.laurent_polynomial_ring which could be done in one import; the second line is too long anyway
  1. Document and test NotImplementedError for op != operator.ge.
  1. Test ValueError for not denominator.is_integral().
  1. The line numerator *= denominator.unit() seems to be suspicious. Shouldn't it be /=?
  1. Test ValueError "... is not a variable".
  1. Test ZeroDivisionError
  1. Test NotImplementedError "... is not normalized"
  1. Test NotImplementedError "Cannot handle factor"

Function _Omega_:

  1. Although main testing is done in Omega, it would be nice to have one non-trivial example to see how the input and output looks like.

Function Omega_ge:

  1. State in docstring that z_1, ..., z_n do not appear in the input, but do appear in the output.
  1. State the parent of the output in the docstring (The function _Omega_ uses the fact that the parent does not depend on a and uses a specific order of the variables)
  1. Is there a reason not to use CyclotomicField?
  1. Is there a reason to actually give the number of variables in LaurentPolynomialRing?
  1. subs_power: this is never called with value != None but is only documented with value != None. Thus remove the parameter value and adapt documentation.
  1. subs_power: The line p = tuple(var.dict().popitem()[0]).index(1) is rather hard to understand, document that this actually just means that var is the pth generator of the parent.
  1. subs_power: also state that it is assumed that var only occurs with exponents divisible by exponent

Function Omega_numerator:

  1. Document that the numerator is normalized in such a way that the corresponding denominator has constant term 1.
  1. In Omega_numerator it is not clear why the input is not assumed to be flattened beforehand. Add a pointer to Omega_denumerator.

Function _Omega_numerator_P:

  1. When reading [APR2001] one would assume that _Omega_numerator_P_ should be a cached function. I assume that performance tuning showed that this does not help. Document this.
  1. Add a meaningful description; currently, one must find out that these are the polynomials P in [APR2001].
  1. The last component of the input x is never used; t is used instead. Consider removing the last component of x. Explain the situation.

Function Omega_factors_denominator:

  1. Document that the denominator is normalized such that it has constant term 1 (cf. 24)
  1. The implicit assumption is that the x and y are collected in such a way that one entry of x corresponds to the orbit of some x_j under multiplication by dth roots of unity and that the output is collected in a corresponding way.

Function partition:

  1. Perhaps use an "ALGORITHM" block for the link to the source code.

Function homogeneous_symmetric_function:

  1. Give definition (or a link to a definition) of homogeneous symmetric polynomials
  1. "whose type is determined by the input x": what does this mean?

comment:16 Changed 5 years ago by cheuberg

  • Reviewers set to Clemens Heuberger

comment:17 Changed 5 years ago by git

  • Commit changed from fceb3e170e79f1390eee97d003d3f894954e901f to 8ede01a667f9da18e43669e5e368323eaeeb0ff4

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

d9514a4Trac #22066.14: test non-normalized input
10900a9Trac #22066.15: test non-binom input
c0bf0b5Trac #22066.16: add non-trivial doctest in _Omega_
e60311aTrac #22066.17: document z_i in Omega_ge
80125f8Trac #22066.18: state parent of output in Omega_ge
2a0f48eTrac #22066.19: use CyclotomicField instead of QQ.extension(...)
8f6ec42Trac #22066.21: remove parameter value of subs_power as not needed
d874fd3Trac #22066.22: comment hard to read line
001dccfTrac #22066.23: make a note in docstring on assumptions in subs_power
8ede01aTrac #22066.24: note in Omega_numerator on normalization

comment:18 Changed 5 years ago by git

  • Commit changed from 8ede01a667f9da18e43669e5e368323eaeeb0ff4 to 0408bce6c72df493b369548e2f478698107db8d8

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

7034154Trac #22066.28: remove last component of x in _Omega_Numerator_P_
7f41896Trac #22066.27: reference P of [APR2001]
0331867Trac #22066.29: document normalized output of denominator
da4c210Trac #22066.30: write down implicit assumptions on x and y in _Omega_Numerator_P_
61a7ad8Trac #22066.31: use ALGORITHM-block
09fe59fTrac #22066.32: provide link to definition of c.h.s. polynomials
278014dTrac #22066.33: specify output-type more clearly
6da446eTrac #22066.6: document Factorization-input
f55b39fTrac #22066.7: test all input variants
0408bceTrac #22066.11: correct handling of unit of denominator

comment:19 Changed 5 years ago by git

  • Commit changed from 0408bce6c72df493b369548e2f478698107db8d8 to 776800f36ee2ceb248b5df86b6053d08f0ed8de8

Branch pushed to git repo; I updated commit sha1. New commits:

776800fMerge tag '7.5.rc1' into t/22066/omega-7.5.rc1

comment:20 Changed 5 years ago by git

  • Commit changed from 776800f36ee2ceb248b5df86b6053d08f0ed8de8 to 0408bce6c72df493b369548e2f478698107db8d8

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

comment:21 Changed 5 years ago by dkrenn

  • Branch changed from u/dkrenn/omega to u/dkrenn/omega-7.5.rc1
  • Commit changed from 0408bce6c72df493b369548e2f478698107db8d8 to 776800f36ee2ceb248b5df86b6053d08f0ed8de8

Last 10 new commits:

7f41896Trac #22066.27: reference P of [APR2001]
0331867Trac #22066.29: document normalized output of denominator
da4c210Trac #22066.30: write down implicit assumptions on x and y in _Omega_Numerator_P_
61a7ad8Trac #22066.31: use ALGORITHM-block
09fe59fTrac #22066.32: provide link to definition of c.h.s. polynomials
278014dTrac #22066.33: specify output-type more clearly
6da446eTrac #22066.6: document Factorization-input
f55b39fTrac #22066.7: test all input variants
0408bceTrac #22066.11: correct handling of unit of denominator
776800fMerge tag '7.5.rc1' into t/22066/omega-7.5.rc1

comment:22 Changed 5 years ago by git

  • Commit changed from 776800f36ee2ceb248b5df86b6053d08f0ed8de8 to 13f2fdd726fe6e9719edcb6628e9485f62c0a2a5

Branch pushed to git repo; I updated commit sha1. New commits:

97f51f7Trac 22066.30: ReST-fixup
2ec3856Merge remote-tracking branch 'trac/u/dkrenn/omega' into t/22066/omega-7.5.rc1
13f2fddTrac #22066.4: put biblography in references file

comment:23 in reply to: ↑ 15 ; follow-up: Changed 5 years ago by dkrenn

I've addressed all issues mentioned earlier; comments below.

Replying to cheuberg:

  1. I am not happy to have Omega in the global name space. There might be other uses of the upper case greek letter Omega which might as well live in the global name space, e.g., in context with asymptotics. Thus I suggest to have it as MacMahonOmega or something like that, perhaps with an alias in the docstring.

Changed to MacMahonOmega? everywhere.

  1. Is there a reason why some of the auxiliary functions are visible and some others are hidden (e.g., for #22067?). In that case, I suggest to have one example in the module documentation which demonstrates how to use Omega and perhaps one other example there which demonstrates how to use the other functions efficiently.

I am not sure here, what should be hidden and what not. The idea was, hide everything that for sure is a helper function. But I guess in some sense everything except for the main function is a helper somehow. Any suggestions how to proceed?

  1. Nowadays, the developers guide wants us to store all bibliographical references in SAGE_ROOT/src/doc/en/reference/references/index.rst.

Done, but my docs are still compiling (had to do make doc-clean as the references were not recognized...). I comment when I have a pass.

  1. Is there a reason to actually give the number of variables in LaurentPolynomialRing?

Yes, so that the univariate polynomial ring is represented as multi-variate ring as well.

comment:24 Changed 5 years ago by git

  • Commit changed from 13f2fdd726fe6e9719edcb6628e9485f62c0a2a5 to 6cff79afc7776388567ba8982f99e238ba6c2054

Branch pushed to git repo; I updated commit sha1. New commits:

4a20e21Trac #22066: remove periods when not full sentence (INPUT/OUTPUT blocks)
5250cd0Trac #22066: extend title (insert "partition analysis")
9354988Trac 22066: repair broken links
2124040Trac #22066: insert example at top
6cff79aMerge remote-tracking branch 'trac/u/dkrenn/omega' into t/22066/omega-7.5.rc1

comment:25 in reply to: ↑ 23 Changed 5 years ago by dkrenn

  • Status changed from needs_work to needs_review

Replying to dkrenn:

  1. Is there a reason why some of the auxiliary functions are visible and some others are hidden (e.g., for #22067?). In that case, I suggest to have one example in the module documentation which demonstrates how to use Omega and perhaps one other example there which demonstrates how to use the other functions efficiently.

I am not sure here, what should be hidden and what not. The idea was, hide everything that for sure is a helper function. But I guess in some sense everything except for the main function is a helper somehow. Any suggestions how to proceed?

Now I've added an example at the top to show what MacMahon?'s Omega does and how it is applied.

  1. Nowadays, the developers guide wants us to store all bibliographical references in SAGE_ROOT/src/doc/en/reference/references/index.rst.

Done, but my docs are still compiling (had to do make doc-clean as the references were not recognized...). I comment when I have a pass.

Passed.

comment:26 follow-up: Changed 5 years ago by cheuberg

  • Branch changed from u/dkrenn/omega-7.5.rc1 to u/cheuberg/omega-7.5.rc1

comment:27 Changed 5 years ago by git

  • Commit changed from 6cff79afc7776388567ba8982f99e238ba6c2054 to 2ce3ab16ce8f41a9961d95a440dd832a138202eb

Branch pushed to git repo; I updated commit sha1. New commits:

b8314a3Trac #22066: Format Mac1915
2ce3ab1Trac #22066: minor rewording

comment:28 follow-up: Changed 5 years ago by cheuberg

Replying to cheuberg:

  1. Is there a reason why some of the auxiliary functions are visible and some others are hidden (e.g., for #22067?). In that case, I suggest to have one example in the module documentation which demonstrates how to use Omega and perhaps one other example there which demonstrates how to use the other functions efficiently.

are we sure that the interface for the low level functions will remain stable?

Function Omega:

  1. Add examples demonstrating all allowed input variants (expression only, without denominator; denominator as a non-factorized Polynomial); perhaps use a simple example to demonstrate all useful variations.
sage: MacMahonOmega(mu, mu^2, (1 - x*mu)*(1 - y/mu))
Traceback (most recent call last):
...
TypeError: unable to factor n

seems to be a strange error message (What is "n"?)

  1. Test NotImplementedError "... is not normalized"

I think that the documentation should clearly state how the denominator must be factored.

  1. I am not happy that MacMahonOmega(mu, mu^2 / ((1 - x*mu)*(1 - y/mu))) does not work. This implies that the input method "expression – an element of the quotient field of some Laurent polynomials" only works in trivial cases. After all, just entering a rational function would be the most natural input format.
  1. What happens if the input is formulated in terms of polynomial rings instead of Laurent polynomial rings?

comment:29 Changed 5 years ago by cheuberg

  • Status changed from needs_review to needs_work

comment:30 Changed 5 years ago by dkrenn

  • Branch changed from u/cheuberg/omega-7.5.rc1 to u/dkrenn/omega-7.5.rc1

comment:31 Changed 5 years ago by git

  • Commit changed from 2ce3ab16ce8f41a9961d95a440dd832a138202eb to 4b1bb1d008fc6baf0b0c042cb5e54f228ed36364

Branch pushed to git repo; I updated commit sha1. New commits:

b8314a3Trac #22066: Format Mac1915
2ce3ab1Trac #22066: minor rewording
4b1bb1dMerge remote-tracking branch 'trac/u/cheuberg/omega-7.5.rc1' into t/22066/omega-7.5.rc1

comment:32 in reply to: ↑ 26 Changed 5 years ago by dkrenn

Replying to cheuberg:

Branch changed from u/dkrenn/omega-7.5.rc1 to u/cheuberg/omega-7.5.rc1

Cross-reviewed (LGTM)

comment:33 in reply to: ↑ 28 Changed 5 years ago by dkrenn

Replying to cheuberg:

Replying to cheuberg: are we sure that the interface for the low level functions will remain stable?

Omega_numerator and Omega_factors_denominator are now private.

sage: MacMahonOmega(mu, mu^2, (1 - x*mu)*(1 - y/mu))
Traceback (most recent call last):
...
TypeError: unable to factor n

seems to be a strange error message (What is "n"?)

This is hardcoded in factor and appears as Laurent polynomials have not method factor.

  1. Test NotImplementedError "... is not normalized"

I think that the documentation should clearly state how the denominator must be factored.

  1. I am not happy that MacMahonOmega(mu, mu^2 / ((1 - x*mu)*(1 - y/mu))) does not work. This implies that the input method "expression – an element of the quotient field of some Laurent polynomials" only works in trivial cases. After all, just entering a rational function would be the most natural input format.
  1. What happens if the input is formulated in terms of polynomial rings instead of Laurent polynomial rings?

I've removed inputing a quotient from the docs as it is not functioning correctly in some cases. (Refactoring one of the factors in the denominator is not trivial and may change the result. To come around this, one has to know something on the coefficients of a factor; this should all go to a follow-up ticket.)

comment:34 Changed 5 years ago by dkrenn

  • Status changed from needs_work to needs_review

comment:35 Changed 5 years ago by cheuberg

  • Status changed from needs_review to positive_review

ok. Dependencies are rather orthogonal to this ticket, so I set this one to positive. At some stage, it might be good to implement other algorithms (cf. #10669) and to compare speed.

comment:36 Changed 5 years ago by git

  • Commit changed from 4b1bb1d008fc6baf0b0c042cb5e54f228ed36364 to f1e2fcd1060fc380f31f6e4ae14087c50a27f187
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

fded046Merge branch 'u/dkrenn/laurent-uni-convert' in 7.5.1
c75d370trac 21855 some details
11707edtrac 21855 more details
65e2fc5Merge tag '7.6.beta2' into t/21855/public/21855
80eea43Merge branch 'public/21855' of git://trac.sagemath.org/sage into t/21976/laurent-efficient-construction
f1e2fcdMerge branch 'u/dkrenn/laurent-efficient-construction' of git://trac.sagemath.org/sage into t/22066/omega-7.5.rc1

comment:37 Changed 5 years ago by dkrenn

Merged in #21976 (and thus 7.6.beta2) to make this patch work again.

comment:38 Changed 5 years ago by dkrenn

  • Status changed from needs_review to positive_review

comment:39 follow-up: Changed 5 years ago by tscrim

  • Milestone changed from sage-7.5 to sage-7.6
  • Status changed from positive_review to needs_work

Needs another rebasing.

comment:40 Changed 5 years ago by git

  • Commit changed from f1e2fcd1060fc380f31f6e4ae14087c50a27f187 to 482ab70907bb11a8f55cff4860870b3af4ac3b31

Branch pushed to git repo; I updated commit sha1. New commits:

cf22ee8Merge branch 'u/dkrenn/laurent-efficient-construction' of git://trac.sagemath.org/sage into public/polynomials/multivariable_laurent_poly_constructor-21976
c58559dSome reviewer changes.
1b7377cMerge branch 'develop' into public/polynomials/laurent_mpoly_constructor-21976
482ab70Merge branch 'public/polynomials/laurent_mpoly_constructor-21976' of git://trac.sagemath.org/sage into t/22066/omega-7.5.rc1

comment:41 in reply to: ↑ 39 Changed 5 years ago by dkrenn

  • Status changed from needs_work to needs_review

Replying to tscrim:

Needs another rebasing.

Merged in dependency #21976. Once the patchbot is happy, this can be positive again.

comment:42 Changed 5 years ago by dkrenn

  • Status changed from needs_review to positive_review

comment:43 Changed 5 years ago by vbraun

  • Branch changed from u/dkrenn/omega-7.5.rc1 to 482ab70907bb11a8f55cff4860870b3af4ac3b31
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.