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:  sage7.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: 
Description (last modified by )
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
 Branch set to u/dkrenn/omega
comment:2 Changed 5 years ago by
 Commit set to 004d61d40fa1ca52be7980ab59188b5da411ecf9
comment:3 Changed 5 years ago by
 Dependencies set to #21832, #21833, #21833, #21966, #21968, #21976, #21999, #22064
comment:4 Changed 5 years ago by
comment:5 Changed 5 years ago by
 Commit changed from 004d61d40fa1ca52be7980ab59188b5da411ecf9 to 4b1c37e34c2c5fa6264fd489e56e9e20cec3237d
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
41b1dcd  lazy import Omega

58943d6  rename Omega_higher > Omega_ge

49e75f4  fix imports in doctests

b122d0f  rename to homogenous_symmetric_function

0b6dba8  name Omega_numerator_P private

907d12e  docstring and tests for _Omega_numerator_P_

91ee1d0  add "helper function" comment to some docstrings

c97bac4  fix doc output

b085ca6  module description

4b1c37e  references

comment:6 Changed 5 years ago by
 Status changed from new to needs_review
comment:7 Changed 5 years ago by
 Cc cheuberg added
comment:8 followup: ↓ 10 Changed 5 years ago by
see also #10669
comment:9 Changed 5 years ago by
 Commit changed from 4b1c37e34c2c5fa6264fd489e56e9e20cec3237d to 79fe3b36ea31ccc8a836a88e9d09c280942172bf
Branch pushed to git repo; I updated commit sha1. New commits:
79fe3b3  extend docstring at top of file

comment:10 in reply to: ↑ 8 Changed 5 years ago by
comment:11 Changed 5 years ago by
 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 followup: ↓ 13 Changed 5 years ago by
 Commit changed from 79fe3b36ea31ccc8a836a88e9d09c280942172bf to 82327c883958a503e6291605e814ae36e7a35085
comment:13 in reply to: ↑ 12 Changed 5 years ago by
Merged in changed dependencies.
comment:14 Changed 5 years ago by
 Commit changed from 82327c883958a503e6291605e814ae36e7a35085 to fceb3e170e79f1390eee97d003d3f894954e901f
Branch pushed to git repo; I updated commit sha1. New commits:
f046132  Python3 iteritems

0db5399  MPolynomial: correct coefficient ring when dict as input

a20fb8a  revert 0f88065556 quickfix in normalize

397301a  doctest example of ticket 21999

fceb3e1  Merge branch 't/21999/laurentfloorhash' into t/22066/omega

comment:15 followup: ↓ 23 Changed 5 years ago by
 Description modified (diff)
 Status changed from needs_review to needs_work
This is a review of this ticket modulo its dependencies.
General:
 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 asMacMahonOmega
or something like that, perhaps with an alias in the docstring.
 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 think that "laurent" should be capitalized throughout, cf. the Wikipedia article.
 Nowadays, the developers guide wants us to store all bibliographical references in
SAGE_ROOT/src/doc/en/reference/references/index.rst
.
 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
:
expression
is allowed to be aFactorization
(as per the Tests), but this is not documented.
 Add examples demonstrating all allowed input variants (
expression
only, without denominator;denominator
as a nonfactorized Polynomial); perhaps use a simple example to demonstrate all useful variations.
 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
 Document and test
NotImplementedError
forop != operator.ge
.
 Test
ValueError
fornot denominator.is_integral()
.
 The line
numerator *= denominator.unit()
seems to be suspicious. Shouldn't it be/=
?
 Test
ValueError
"... is not a variable".
 Test
ZeroDivisionError
 Test
NotImplementedError
"... is not normalized"
 Test
NotImplementedError
"Cannot handle factor"
Function _Omega_
:
 Although main testing is done in
Omega
, it would be nice to have one nontrivial example to see how the input and output looks like.
Function Omega_ge
:
 State in docstring that
z_1
, ...,z_n
do not appear in the input, but do appear in the output.
 State the parent of the output in the docstring (The function
_Omega_
uses the fact that the parent does not depend ona
and uses a specific order of the variables)
 Is there a reason not to use
CyclotomicField
?
 Is there a reason to actually give the number of variables in
LaurentPolynomialRing
?
subs_power
: this is never called withvalue != None
but is only documented withvalue != None
. Thus remove the parametervalue
and adapt documentation.
subs_power
: The linep = tuple(var.dict().popitem()[0]).index(1)
is rather hard to understand, document that this actually just means thatvar
is thep
th generator of the parent.
subs_power
: also state that it is assumed thatvar
only occurs with exponents divisible byexponent
Function Omega_numerator
:
 Document that the numerator is normalized in such a way that the corresponding denominator has constant term 1.
 In
Omega_numerator
it is not clear why the input is not assumed to be flattened beforehand. Add a pointer toOmega_denumerator
.
Function _Omega_numerator_P
:
 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.
 Add a meaningful description; currently, one must find out that these are the polynomials
P
in [APR2001].
 The last component of the input
x
is never used;t
is used instead. Consider removing the last component ofx
. Explain the situation.
Function Omega_factors_denominator
:
 Document that the denominator is normalized such that it has constant term 1 (cf. 24)
 The implicit assumption is that the
x
andy
are collected in such a way that one entry ofx
corresponds to the orbit of somex_j
under multiplication byd
th roots of unity and that the output is collected in a corresponding way.
Function partition
:
 Perhaps use an "ALGORITHM" block for the link to the source code.
Function homogeneous_symmetric_function
:
 Give definition (or a link to a definition) of homogeneous symmetric polynomials
 "whose type is determined by the input
x
": what does this mean?
comment:16 Changed 5 years ago by
 Reviewers set to Clemens Heuberger
comment:17 Changed 5 years ago by
 Commit changed from fceb3e170e79f1390eee97d003d3f894954e901f to 8ede01a667f9da18e43669e5e368323eaeeb0ff4
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
d9514a4  Trac #22066.14: test nonnormalized input

10900a9  Trac #22066.15: test nonbinom input

c0bf0b5  Trac #22066.16: add nontrivial doctest in _Omega_

e60311a  Trac #22066.17: document z_i in Omega_ge

80125f8  Trac #22066.18: state parent of output in Omega_ge

2a0f48e  Trac #22066.19: use CyclotomicField instead of QQ.extension(...)

8f6ec42  Trac #22066.21: remove parameter value of subs_power as not needed

d874fd3  Trac #22066.22: comment hard to read line

001dccf  Trac #22066.23: make a note in docstring on assumptions in subs_power

8ede01a  Trac #22066.24: note in Omega_numerator on normalization

comment:18 Changed 5 years ago by
 Commit changed from 8ede01a667f9da18e43669e5e368323eaeeb0ff4 to 0408bce6c72df493b369548e2f478698107db8d8
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
7034154  Trac #22066.28: remove last component of x in _Omega_Numerator_P_

7f41896  Trac #22066.27: reference P of [APR2001]

0331867  Trac #22066.29: document normalized output of denominator

da4c210  Trac #22066.30: write down implicit assumptions on x and y in _Omega_Numerator_P_

61a7ad8  Trac #22066.31: use ALGORITHMblock

09fe59f  Trac #22066.32: provide link to definition of c.h.s. polynomials

278014d  Trac #22066.33: specify outputtype more clearly

6da446e  Trac #22066.6: document Factorizationinput

f55b39f  Trac #22066.7: test all input variants

0408bce  Trac #22066.11: correct handling of unit of denominator

comment:19 Changed 5 years ago by
 Commit changed from 0408bce6c72df493b369548e2f478698107db8d8 to 776800f36ee2ceb248b5df86b6053d08f0ed8de8
Branch pushed to git repo; I updated commit sha1. New commits:
776800f  Merge tag '7.5.rc1' into t/22066/omega7.5.rc1

comment:20 Changed 5 years ago by
 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
 Branch changed from u/dkrenn/omega to u/dkrenn/omega7.5.rc1
 Commit changed from 0408bce6c72df493b369548e2f478698107db8d8 to 776800f36ee2ceb248b5df86b6053d08f0ed8de8
Last 10 new commits:
7f41896  Trac #22066.27: reference P of [APR2001]

0331867  Trac #22066.29: document normalized output of denominator

da4c210  Trac #22066.30: write down implicit assumptions on x and y in _Omega_Numerator_P_

61a7ad8  Trac #22066.31: use ALGORITHMblock

09fe59f  Trac #22066.32: provide link to definition of c.h.s. polynomials

278014d  Trac #22066.33: specify outputtype more clearly

6da446e  Trac #22066.6: document Factorizationinput

f55b39f  Trac #22066.7: test all input variants

0408bce  Trac #22066.11: correct handling of unit of denominator

776800f  Merge tag '7.5.rc1' into t/22066/omega7.5.rc1

comment:22 Changed 5 years ago by
 Commit changed from 776800f36ee2ceb248b5df86b6053d08f0ed8de8 to 13f2fdd726fe6e9719edcb6628e9485f62c0a2a5
comment:23 in reply to: ↑ 15 ; followup: ↓ 25 Changed 5 years ago by
I've addressed all issues mentioned earlier; comments below.
Replying to cheuberg:
 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 asMacMahonOmega
or something like that, perhaps with an alias in the docstring.
Changed to MacMahonOmega? everywhere.
 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?
 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 docclean
as the references were not recognized...). I comment when I have a pass.
 Is there a reason to actually give the number of variables in
LaurentPolynomialRing
?
Yes, so that the univariate polynomial ring is represented as multivariate ring as well.
comment:24 Changed 5 years ago by
 Commit changed from 13f2fdd726fe6e9719edcb6628e9485f62c0a2a5 to 6cff79afc7776388567ba8982f99e238ba6c2054
Branch pushed to git repo; I updated commit sha1. New commits:
4a20e21  Trac #22066: remove periods when not full sentence (INPUT/OUTPUT blocks)

5250cd0  Trac #22066: extend title (insert "partition analysis")

9354988  Trac 22066: repair broken links

2124040  Trac #22066: insert example at top

6cff79a  Merge remotetracking branch 'trac/u/dkrenn/omega' into t/22066/omega7.5.rc1

comment:25 in reply to: ↑ 23 Changed 5 years ago by
 Status changed from needs_work to needs_review
Replying to dkrenn:
 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.
 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 docclean
as the references were not recognized...). I comment when I have a pass.
Passed.
comment:26 followup: ↓ 32 Changed 5 years ago by
 Branch changed from u/dkrenn/omega7.5.rc1 to u/cheuberg/omega7.5.rc1
comment:27 Changed 5 years ago by
 Commit changed from 6cff79afc7776388567ba8982f99e238ba6c2054 to 2ce3ab16ce8f41a9961d95a440dd832a138202eb
comment:28 followup: ↓ 33 Changed 5 years ago by
Replying to cheuberg:
 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
:
 Add examples demonstrating all allowed input variants (
expression
only, without denominator;denominator
as a nonfactorized 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"?)
 Test
NotImplementedError
"... is not normalized"
I think that the documentation should clearly state how the denominator must be factored.
 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.
 What happens if the input is formulated in terms of polynomial rings instead of Laurent polynomial rings?
comment:29 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:30 Changed 5 years ago by
 Branch changed from u/cheuberg/omega7.5.rc1 to u/dkrenn/omega7.5.rc1
comment:31 Changed 5 years ago by
 Commit changed from 2ce3ab16ce8f41a9961d95a440dd832a138202eb to 4b1bb1d008fc6baf0b0c042cb5e54f228ed36364
comment:32 in reply to: ↑ 26 Changed 5 years ago by
Replying to cheuberg:
Branch changed from u/dkrenn/omega7.5.rc1 to u/cheuberg/omega7.5.rc1
Crossreviewed (LGTM)
comment:33 in reply to: ↑ 28 Changed 5 years ago by
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 nseems to be a strange error message (What is "n"?)
This is hardcoded in factor
and appears as Laurent polynomials have not method factor
.
 Test
NotImplementedError
"... is not normalized"I think that the documentation should clearly state how the denominator must be factored.
 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.
 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 followup ticket.)
comment:34 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:35 Changed 5 years ago by
 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
 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:
fded046  Merge branch 'u/dkrenn/laurentuniconvert' in 7.5.1

c75d370  trac 21855 some details

11707ed  trac 21855 more details

65e2fc5  Merge tag '7.6.beta2' into t/21855/public/21855

80eea43  Merge branch 'public/21855' of git://trac.sagemath.org/sage into t/21976/laurentefficientconstruction

f1e2fcd  Merge branch 'u/dkrenn/laurentefficientconstruction' of git://trac.sagemath.org/sage into t/22066/omega7.5.rc1

comment:37 Changed 5 years ago by
Merged in #21976 (and thus 7.6.beta2) to make this patch work again.
comment:38 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:39 followup: ↓ 41 Changed 5 years ago by
 Milestone changed from sage7.5 to sage7.6
 Status changed from positive_review to needs_work
Needs another rebasing.
comment:40 Changed 5 years ago by
 Commit changed from f1e2fcd1060fc380f31f6e4ae14087c50a27f187 to 482ab70907bb11a8f55cff4860870b3af4ac3b31
Branch pushed to git repo; I updated commit sha1. New commits:
cf22ee8  Merge branch 'u/dkrenn/laurentefficientconstruction' of git://trac.sagemath.org/sage into public/polynomials/multivariable_laurent_poly_constructor21976

c58559d  Some reviewer changes.

1b7377c  Merge branch 'develop' into public/polynomials/laurent_mpoly_constructor21976

482ab70  Merge branch 'public/polynomials/laurent_mpoly_constructor21976' of git://trac.sagemath.org/sage into t/22066/omega7.5.rc1

comment:41 in reply to: ↑ 39 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:42 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:43 Changed 5 years ago by
 Branch changed from u/dkrenn/omega7.5.rc1 to 482ab70907bb11a8f55cff4860870b3af4ac3b31
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
minor rewrite to increase readability
allow passing mon in _element_constructor_
fix pickling bug
determine parent at top of _element_constructor_
rewrite to detect more specialized situations
Merge branch 'u/dkrenn/laurentefficientconstruction' of trac.sagemath.org:sage into u/dakrenn/omega
quickfix in normalize
Merge branch 'u/dkrenn/laurentfloorhash' of trac.sagemath.org:sage into u/dakrenn/omega
use __call__ in subs to be more efficient
Merge branch 'u/dkrenn/laurentsubs' of trac.sagemath.org:sage into u/dakrenn/omega