implement MacMahon's Omega operator

[dkrenn]

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.

[git]

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

​d33a595	minor rewrite to increase readability
​5a5db0b	allow passing mon in _element_constructor_
​3a809a4	fix pickling bug
​be67f37	determine parent at top of _element_constructor_
​6137662	rewrite to detect more specialized situations
​0570355	Merge branch 'u/dkrenn/laurent-efficient-construction' of trac.sagemath.org:sage into u/dakrenn/omega
​0f88065	quick-fix in normalize
​c0fea6e	Merge branch 'u/dkrenn/laurent-floor-hash' of trac.sagemath.org:sage into u/dakrenn/omega
​9389e62	use __call__ in subs to be more efficient
​004d61d	Merge branch 'u/dkrenn/laurent-subs' of trac.sagemath.org:sage into u/dakrenn/omega

[git]

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

[chapoton]

see also #10669

[git]

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

​79fe3b3

extend docstring at top of file

[dkrenn]

Replying to chapoton:

see also #10669

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

[cheuberg]

Removed duplicate dependency #21833

[git]

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

​f7e9540	fix doctest (conversion to symbolic)
​82327c8	Merge branch 'u/dakrenn/laurent-subs' into t/22066/omega

[dkrenn]

Merged in changed dependencies.

[git]

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 quick-fix in normalize
​397301a	doctest example of ticket 21999
​fceb3e1	Merge branch 't/21999/laurent-floor-hash' into t/22066/omega

[cheuberg]

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.

2. 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.

3. I think that "laurent" should be capitalized throughout, cf. ​the Wikipedia article.

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

5. 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:

6. expression is allowed to be a Factorization (as per the Tests), but this is not documented.

7. 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.

8. 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

9. Document and test NotImplementedError for op != operator.ge.

10. Test ValueError for not denominator.is_integral().

11. The line numerator *= denominator.unit() seems to be suspicious. Shouldn't it be /=?

12. Test ValueError "... is not a variable".

13. Test ZeroDivisionError

14. Test NotImplementedError "... is not normalized"

15. Test NotImplementedError "Cannot handle factor"

Function _Omega_:

16. 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:

17. State in docstring that z_1, ..., z_n do not appear in the input, but do appear in the output.

18. 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)

19. Is there a reason not to use CyclotomicField?

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

21. subs_power: this is never called with value != None but is only documented with value != None. Thus remove the parameter value and adapt documentation.

22. 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.

23. subs_power: also state that it is assumed that var only occurs with exponents divisible by exponent

Function Omega_numerator:

24. Document that the numerator is normalized in such a way that the corresponding denominator has constant term 1.

25. 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:

26. 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.

27. Add a meaningful description; currently, one must find out that these are the polynomials P in [APR2001].

28. 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:

29. Document that the denominator is normalized such that it has constant term 1 (cf. 24)

30. 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:

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

Function homogeneous_symmetric_function:

32. Give definition (or a link to a definition) of homogeneous symmetric polynomials

33. "whose type is determined by the input x": what does this mean?

[git]

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

​d9514a4	Trac #22066.14: test non-normalized input
​10900a9	Trac #22066.15: test non-binom input
​c0bf0b5	Trac #22066.16: add non-trivial 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

[git]

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 ALGORITHM-block
​09fe59f	Trac #22066.32: provide link to definition of c.h.s. polynomials
​278014d	Trac #22066.33: specify output-type more clearly
​6da446e	Trac #22066.6: document Factorization-input
​f55b39f	Trac #22066.7: test all input variants
​0408bce	Trac #22066.11: correct handling of unit of denominator

[git]

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

​776800f

Merge tag '7.5.rc1' into t/22066/omega-7.5.rc1

[git]

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

[dkrenn]

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 ALGORITHM-block
​09fe59f	Trac #22066.32: provide link to definition of c.h.s. polynomials
​278014d	Trac #22066.33: specify output-type more clearly
​6da446e	Trac #22066.6: document Factorization-input
​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/omega-7.5.rc1

[git]

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

​97f51f7	Trac 22066.30: ReST-fixup
​2ec3856	Merge remote-tracking branch 'trac/u/dkrenn/omega' into t/22066/omega-7.5.rc1
​13f2fdd	Trac #22066.4: put biblography in references file

[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.

2. 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?

4. 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.

20. 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.

[git]

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 remote-tracking branch 'trac/u/dkrenn/omega' into t/22066/omega-7.5.rc1

[dkrenn]

Replying to dkrenn:

2. 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.

4. 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.

[git]

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

​b8314a3	Trac #22066: Format Mac1915
​2ce3ab1	Trac #22066: minor rewording

[cheuberg]

Replying to cheuberg:

2. 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:

7. 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"?)

14. Test NotImplementedError "... is not normalized"

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

34. 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.

35. What happens if the input is formulated in terms of polynomial rings instead of Laurent polynomial rings?

[git]

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

​b8314a3	Trac #22066: Format Mac1915
​2ce3ab1	Trac #22066: minor rewording
​4b1bb1d	Merge remote-tracking branch 'trac/u/cheuberg/omega-7.5.rc1' into t/22066/omega-7.5.rc1

[dkrenn]

Replying to cheuberg:

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

Cross-reviewed (LGTM)

[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.

14. Test NotImplementedError "... is not normalized"

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

34. 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.

35. 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.)

[cheuberg]

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.

[git]

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

​fded046	Merge branch 'u/dkrenn/laurent-uni-convert' 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/laurent-efficient-construction
​f1e2fcd	Merge branch 'u/dkrenn/laurent-efficient-construction' of git://trac.sagemath.org/sage into t/22066/omega-7.5.rc1

[dkrenn]

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

[tscrim]

Needs another rebasing.

[git]

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

​cf22ee8	Merge branch 'u/dkrenn/laurent-efficient-construction' of git://trac.sagemath.org/sage into public/polynomials/multivariable_laurent_poly_constructor-21976
​c58559d	Some reviewer changes.
​1b7377c	Merge branch 'develop' into public/polynomials/laurent_mpoly_constructor-21976
​482ab70	Merge branch 'public/polynomials/laurent_mpoly_constructor-21976' of git://trac.sagemath.org/sage into t/22066/omega-7.5.rc1

[dkrenn]

Replying to tscrim:

Needs another rebasing.

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