generating function of integral points of polyhedra

[dkrenn]

Implement this using MacMahon's Omega operator (#22066).

[dkrenn]

Last 10 new commits:

​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
​5d49102	Merge branch 'u/dakrenn/omega' into u/dakrenn/gf-polyhedron

[git]

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

​4b1c37e	references
​79fe3b3	extend docstring at top of file
​f1ec72e	Merge branch 'u/dkrenn/omega' of git://trac.sagemath.org/sage into t/22067/gf-polyhedron
​ddbf737	repr_pretty and _latex_ of Hrepresentation
​54fc5b8	repr_pretty_Hrepresentation for polyhedra
​968a998	Merge branch 'u/dkrenn/inequality-pretty' of git://trac.sagemath.org/sage into t/22067/gf-polyhedron
​1e327c5	add generating_function module to index
​662195b	module description
​4a98951	fix imports in doctests
​32c6eeb	fix omega imports

[git]

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

​9ca1aeb	move repr_pretty code outside class, so that it can be used elsewhere as well
​73649f9	Merge branch 'u/dkrenn/inequality-pretty' into t/22067/gf-polyhedron
​6f59894	use repr_pretty (and remove old pretty_inequality)
​ae030fa	more logging cleanup
​a2334a3	make helper functions private
​c4d01ec	make helper function private (part 2)
​86f40ca	write missing docstrings/comments
​24abfd4	todo-cleanup
​76801db	fix a doctest
​7fcfe5e	fix code typo

[git]

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

​adf4dad

remove Summandization

[git]

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

​dd0679e	use relative imports
​50a2a7a	method generating_function for a polyhedron
​9932d28	fix docstrings
​999140f	rephare OUTPUT-block

[mkoeppe]

Return the generating function of the integer points of
+    the polyhedron's orthant with only nonnegative coordinates.

Why only the integer points with nonnegative coordinates?

[git]

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

​f85e038

add doctest to _generate_mod_

[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
​16e515e	Merge branch 't/22066/omega' into t/22067/gf-polyhedron
​0049218	remove periods at end of non-sentence in INPUT-block
​91cab4a	Python3 print syntax
​fce0c71	Merge branch 'u/dkrenn/inequality-pretty' into t/22067/gf-polyhedron

[dkrenn]

Merged in changed dependencies.

[vdelecroix]

Hello,

This would be really useful.

1) The name is too generic: generating_function could be anything (e.g. the number of lattice points in dilates). It should be something like non_negative_lattice_points_generating_function.

2) What do you mean by "generating function"? Is it weighted by the sum of the vector?

3) You should at least check that the number of integer partitions is correctly computed by your function with the polyhedron

x1 >= x2 >= x3 >= x4 >= x5 >= 1

versus

sage: [Partitions(k, length=5).cardinality() for k in range(5,20)]
[1, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70]

[mkoeppe]

I agree with Vincent that the name is too generic. This seems to compute what, for example, LattE would call the multivariate generating function (which can be computed by count --multivariate-generating-function after installing package latte_int) -- but not of the integer points of the given polyhedron but of its intersection with the positive orthant. This "positive orthant" business, I think, is just a peculiarity of the Omega approach but I don't think it's makes sense to expose it to the user. Maybe raise a NotImplementedError instead if the given polytope is not contained in the positive orthant?

[vdelecroix]

Replying to mkoeppe:

This "positive orthant" business, I think, is just a peculiarity of the Omega approach but I don't think it's makes sense to expose it to the user. Maybe raise a NotImplementedError instead if the given polytope is not contained in the positive orthant?

+1. The API would be much better (and allows extension in the future to count all points (that can already be done intersecting with the 2^dim orthants and applying symmetries)).

[git]

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

​5c22d7f	rename methods (to make it more precise)
​68e3fc7	check if polyhedron is in nonnegative orthant
​d001a8e	doctests for polyhedra with negative coordinates
​4ee76c4	fix existing doctests
​7a96155	document nonnegative-orthant-changes
​0afac56	minor rewrite (integer points --> integral points)
​871aea4	write down formula to make resulting GF precise
​aa208ea	minor rewrite in SEEALSO blocks
​594d9e5	example integer partitions
​5d4018a	fix docs (ReST syntax)

[dkrenn]

Replying to vdelecroix:

This would be really useful.

Good :)

Thank you for your comments. Code updated.

1) The name is too generic: generating_function could be anything (e.g. the number of lattice points in dilates). It should be something like non_negative_lattice_points_generating_function.

It seems that "integral points" is used in sage.geometry.polyhedron` a couple of times, thus, changed to generating_function_of_integral_points.

2) What do you mean by "generating function"? Is it weighted by the sum of the vector?

Inserted a formula to make this precise.

3) You should at least check that the number of integer partitions is correctly computed by your function with the polyhedron

x1 >= x2 >= x3 >= x4 >= x5 >= 1

versus

sage: [Partitions(k, length=5).cardinality() for k in range(5,20)]
[1, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70]

Indeed; example added.

[dkrenn]

Replying to vdelecroix:

Replying to mkoeppe:

This "positive orthant" business, I think, is just a peculiarity of the Omega approach but I don't think it's makes sense to expose it to the user. Maybe raise a NotImplementedError instead if the given polytope is not contained in the positive orthant?

+1. The API would be much better (and allows extension in the future to count all points (that can already be done intersecting with the 2^dim orthants and applying symmetries)).

I agree. Changed the documentation and added a few lines to check if polyhedron is in the nonnegative orthant; otherwise raise NotImplementedError. (Created a follow up ticket #22099 for the extension to arbitary corrdinates.)

[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
​fe77eec	Merge branch 't/22066/omega' into t/22067/gf-polyhedron

[mkoeppe]

sage: P = Polyhedron(vertices=[[1], [5]])
sage: P.generating_function_of_integral_points()
TypeError: unsupported operand type(s) for -: 'tuple' and 'tuple'

[git]

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

​35cf3a2

fix 1-dimensial case (creation of univariate laurent polynomial ring)

[dkrenn]

Replying to mkoeppe:

sage: P = Polyhedron(vertices=[[1], [5]])
sage: P.generating_function_of_integral_points()
TypeError: unsupported operand type(s) for -: 'tuple' and 'tuple'

Fixed.

[mkoeppe]

I think the name of the variables used in the generating function should be a user option

[mkoeppe]

sage: P = Polyhedron(rays=[(1, sqrt(2)), (0, 1)])
sage: P.generating_function_of_integral_points()
1 * (-y0 + 1)^-1 * (-y1 + 1)^-1

I had hoped for an error

[mkoeppe]

Also I think the method generating_function_of_integral_points should have an algorithm keyword. For polytopes, could provide a naive algorithm that just collects the monomials corresponding to integral_points. And another algorithm would be to just call LattE.

Various algorithms options such as result_as_tuple are not sufficiently documented.

For the LattE algorithm, the best output format would be a sum of Factorizations. Is this what result_as_tuple can represent?

[git]

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

​98d46b6	new option: specify the prefix of the output variables
​fb2f8f6	test and document prefix_variable_name
​7bbae4b	extend documentation of parameter result_as_tuple
​3d9bb3f	extend documentation of parameter sort_factors
​401c498	check base ring of the polyhedron (if it is ZZ or QQ)

[dkrenn]

Replying to mkoeppe:

I think the name of the variables used in the generating function should be a user option

True; option is now available :)

[dkrenn]

Replying to mkoeppe:

sage: P = Polyhedron(rays=[(1, sqrt(2)), (0, 1)])
sage: P.generating_function_of_integral_points()
1 * (-y0 + 1)^-1 * (-y1 + 1)^-1

I had hoped for an error

Now the base ring of the polyhedron is inspected.

[dkrenn]

Replying to mkoeppe:

Various algorithms options such as result_as_tuple are not sufficiently documented.

Docs extended.

[dkrenn]

Replying to mkoeppe:

Also I think the method generating_function_of_integral_points should have an algorithm keyword. For polytopes, could provide a naive algorithm that just collects the monomials corresponding to integral_points. And another algorithm would be to just call LattE.

As this does not change the interface, only extends it, I have put this on the follow--up enhancement ticket #22111.

[dkrenn]

Replying to mkoeppe:

For the LattE algorithm, the best output format would be a sum of Factorizations. Is this what result_as_tuple can represent?

Yes, correct. (As mentioned, I've extended the docstring of this option.)

[mkoeppe]

Replying to dkrenn:

Replying to mkoeppe:

Various algorithms options such as result_as_tuple are not sufficiently documented.

Docs extended.

Wouldn't it be nicer to have a class to represent such sums, much like Factorization represents products?

[dkrenn]

Replying to mkoeppe:

Replying to dkrenn:

Replying to mkoeppe:

Various algorithms options such as result_as_tuple are not sufficiently documented.

Docs extended.

Wouldn't it be nicer to have a class to represent such sums, much like Factorization represents products?

Yes, indeed. I had this (a class Summandization in some draft, but as it is nowhere else in SageMath (e.g. partial_fraction_decomposition), I decided to keep it simple and consistent and use a tuple.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 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
​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
​22bd0c4	Merge branch 'u/dkrenn/omega-7.5.rc1' of git://trac.sagemath.org/sage into t/22067/gf-polyhedron

[git]

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

​78c8278	precise description of input/output of helper functions
​3550782	unify error messages

[dkrenn]

Replying to git:

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

​78c8278

precise description of input/output of helper functions

I've written a better description of the helper functions to make reviewing easier.

[git]

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

​4d2ccb6

unify INPUT/OUTPUT blocks

[mkoeppe]

needs 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
​3a3aec5	Merge branch 'public/polynomials/laurent_mpoly_constructor-21976' of git://trac.sagemath.org/sage into t/22067/gf-polyhedron

[dkrenn]

Replying to mkoeppe:

needs rebasing

This was because of a change in one of its dependencies. Merged in; should now work again.

[git]

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

​b09d162

Trac #22067: minor modification of logging output

[git]

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

​24a861f	rename _generate_mods_ to generate_mods
​7bb6fef	adapt to previous code movement
​fd117ff	factor out calling-Omega-code
​f137fba	small cleanup
​aaf0fa0	restrict splitting off inequality to constants <= 0
​802c523	use _simplify_ to cancel terms
​2d94245	update doctests
​b4082d2	function _simplify_ for cancelling factors in intermediate result (quotient)
​b02b7f1	use and test new feature in _Omega_-function
​423096c	Merge branch 'u/dakrenn/omega-simplify' into t/22067/gf-polyhedron

[dkrenn]

• Merged in 7.6, as some error messages concerning polynomial rings have changed and thus doctests failed.
• Merged in #22803, which simplifies the some generating functions due to cancellations
• Fixed a small bug.
• Restructured/refactored some code to make testing the overall result easier.
• Extended the existing doctests to see the correctness of the results.

(Set it to needs work as some docstrings are not yet written.)

[git]

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

​53b5fb0	correct link
​3cfd809	complete docstrings and doctests

[chapoton]

2 failing doctests, see patchbot report (wrong import)

[chapoton]

ping ? just 2 imports need to be changed..

[git]

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

​c91baa5

Trac #22067: correct import of lcm

[dkrenn]

Replying to chapoton:

ping ? just 2 imports need to be changed..

Sorry, I am currently some kind of busy. However, changed the import. Let's see what the patchbot says now ;)

[chapoton]

Trivial remark: some "laurent" are missing their capitals.

[chapoton]

and one failing doctest

[git]

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

​1bd336a	Merge tag '8.3' into t/22067/gf-polyhedron
​d5f551a	Merge commit 'b1ae583' into t/22067/gf-polyhedron
​acb0c64	fix error message (change due to new SageMath version)
​1b922e7	fix call to deprecated method

[git]

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

​0f2d193

doc: laurent --> Laurent

[dkrenn]

Replying to chapoton:

Trivial remark: some "laurent" are missing their capitals.

Fixed in ​0f2d193

[dkrenn]

Replying to chapoton:

and one failing doctest

Fixed.

[chapoton]

you can just remove the dependencies (empty this field), once closed

[git]

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

​372da68

cleanup pyflakes warnings

[git]

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

​1583e91

fixup: forgotten ** left of kwds

[git]

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

​0510896

uniquify sorting in SplitOffSimpleInequalities

[embray]

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

[chapoton]

one failing doctest.

[embray]

Ticket retargeted after milestone closed

[mkoeppe]

pushing these forward to 9.2

[mkoeppe]

Looks like some py3 issues need fixing

[mkoeppe]

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[git]

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

​50dd52b	Merge tag '9.3' into t/22067/gf-polyhedron
​d1987b9	Trac #22067: fix py3 issues related to zip
​c1792b7	Trac #22067: fix doctests due to changed error message
​066ba21	Trac #22067: remove old py2/3 compatible code

[dkrenn]

Actually, looked at this ticket just yesterday; now merged in 9.3, fixed the py3 issues and make it pass the tests again.

[dkrenn]

I've skim read all the comments here; AFAICS, 3 to 4 years ago, the review seems to have completed but it hasn't made the step to a positive review. Anything that I missed?

[dkrenn]

Replying to dkrenn:

I've skim read all the comments here; AFAICS, 3 to 4 years ago, the review seems to have been completed but it hasn't made the step to a positive review. Anything that I missed?

[mkoeppe]

I think prefix_variable_name should be replaced by handling name and names arguments, like for example the PolynomialRing constructor does.

[mkoeppe]

Also, codespell from ./sage -tox -- src/sage/geometry/polyhedron/generating_function.py indicates the correction

sage/geometry/polyhedron/generating_function.py:110: handeled ==> handled, handheld

In the same line where this typo appears, there is another one: polyhedon->polyhedron

[git]

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

​ab74b6e	Trac #22067 comment:81: replace prefix_variable_name by the usual name and names parameters
​8fcebd1	Trac #22067 comment:82: fix typos in docstring

[dkrenn]

Thank you for your fast replies. I've addressed both ticket:22067#comment:81 and ticket:22067#comment:82, need review.

[mkoeppe]

There is still a prefix_variable_name in a docstring

[git]

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

​f04075f

Trac #22067 comment:85: fix docstring (forgotten prefix_variable_name)

[dkrenn]

Replying to mkoeppe:

There is still a prefix_variable_name in a docstring

Indeed, thanks, fixed.

[mkoeppe]

Also this docstring needs work

+def compositions_mod(u, m, r=0, multidimensional=False):
+    r"""
+    Return an iterable of tuples `a` such that `a u^T \equiv r \mod m`.

It should make clear that the items of a are elements of Zmod(m). Is there are reason why you don't make the results vectors over Zmod(m)?

Also this:

+
+    return _compositions_mod_(u, r)

I think should be using yield from.

[mkoeppe]

+def _compositions_mod_(u, r):
+    r"""
+    Helper function to :func:`compositions_mod`.

should still describe what it does and explain input and output

[mkoeppe]

+        split = iter((ph, ph.Hrepresentation_str(**Hrepresentation_str_options))
+                     for ph in split)

this is a "useless use of iter" -- the generator expression is already iterable. (similarly in several other places in the file)

[mkoeppe]

+    v = u[0]
+    m = max(vv.order() for vv in v)
+    Z = Zmod(m)
+    for j in srange(m):

I don't think max is correct here, shouldn't this be lcm?

[mkoeppe]

Also

+    def _transform_(self):

... I think standard naming for internal functions would be _transform

[git]

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

​223517f	Trac #22067 comment:89: refactor recursively called code
​ad0444a	Trac #22067 comment:88(2): use "yield from"
​c75e86d	Trac #22067 comment:88(1): describe outout of composition_mod more detailed
​fbf3b4e	Trac #22067 comment:90: remove obsolete iter statements
​015883b	Trac #22067 comment:91: fix wrong modulus

[dkrenn]

Replying to mkoeppe:

+def _compositions_mod_(u, r):
+    r"""
+    Helper function to :func:`compositions_mod`.

should still describe what it does and explain input and output

Reading this again, I think, this is not a good style, as _composition_mod_ is basically needed/used as this function calles recursively itself. I've renamed it to recursively_build_compositions and moved it into the main function, so slightly refactored the code.

[dkrenn]

Replying to mkoeppe:

Also this docstring needs work

+def compositions_mod(u, m, r=0, multidimensional=False):
+    r"""
+    Return an iterable of tuples `a` such that `a u^T \equiv r \mod m`.

It should make clear that the items of a are elements of Zmod(m).

Docstrings extended to state precisely what the items are.

[dkrenn]

Replying to mkoeppe:

Is there are reason why you don't make the results vectors over Zmod(m)?

Yes. The elements do not have all neccessarily the same modulus; documented this now as well.

[dkrenn]

Replying to mkoeppe:

Also this:

+
+    return _compositions_mod_(u, r)

I think should be using yield from.

This does not change anything at all as _compositions_mod_ is already a generator expression (and FWIW no for-loop is used anyways). What is the reason for doing this? A semantic reason maybe? (I've done the change, but it can be reverted easily if there is no reason for using yield from.)

[dkrenn]

Replying to mkoeppe:

+        split = iter((ph, ph.Hrepresentation_str(**Hrepresentation_str_options))
+                     for ph in split)

this is a "useless use of iter" -- the generator expression is already iterable. (similarly in several other places in the file)

Indeed; removed (all).

[dkrenn]

Replying to mkoeppe:

+    v = u[0]
+    m = max(vv.order() for vv in v)
+    Z = Zmod(m)
+    for j in srange(m):

I don't think max is correct here, shouldn't this be lcm?

Ouch, yes, correct, it should definitely be lcm. How could I miss this? :) Changed.

[mkoeppe]

it would be good to add a doctest in which lcm is different from max.

[dkrenn]

Replying to mkoeppe:

Also

+    def _transform_(self):

... I think standard naming for internal functions would be _transform

I do think both conventions are used

dakrenn@nops:/opt/sage/9.3$ ./sage -grep "def _[a-zA-Z0-9][_a-zA-Z0-9]*[a-zA-Z0-9](" | wc -l
5899
dakrenn@nops:/opt/sage/9.3$ ./sage -grep "def _[a-zA-Z0-9][_a-zA-Z0-9]*[a-zA-Z0-9]_(" | wc -l
5908

Also, _..._ is used in methods like _repr_, therefore I'm in favor of keeping it.

[dkrenn]

Replying to mkoeppe:

it would be good to add a doctest in which lcm is different from max.

This is already the case in the existing

        sage: list(compositions_mod([(1, 2), (2, 2), (3, 2)], 6,
        ....:                       multidimensional=True))
        [(0, 0, 0), (1, 1, 1), (2, 2, 2), (3, 0, 3), (4, 1, 4), (5, 2, 5)]

(which changed after switching to lcm)

[mkoeppe]

Replying to dkrenn:

_..._ is used in methods like _repr_

Yes, but this specifically mimics the "dunder" method __repr__ to which it is connected.

[mkoeppe]

Replying to dkrenn:

Replying to mkoeppe:

it would be good to add a doctest in which lcm is different from max.

This is already the case in the existing

        sage: list(compositions_mod([(1, 2), (2, 2), (3, 2)], 6,
        ....:                       multidimensional=True))
        [(0, 0, 0), (1, 1, 1), (2, 2, 2), (3, 0, 3), (4, 1, 4), (5, 2, 5)]

(which changed after switching to lcm)

OK, thanks, I hadn't noticed that

[mkoeppe]

Replying to dkrenn:

Replying to mkoeppe:

Also this:

+
+    return _compositions_mod_(u, r)

I think should be using yield from.

This does not change anything at all as _compositions_mod_ is already a generator expression (and FWIW no for-loop is used anyways). What is the reason for doing this? A semantic reason maybe? (I've done the change, but it can be reverted easily if there is no reason for using yield from.)

It makes of course no practical difference in this example. But it is the syntactic presence of yield in the body of a function that changes a function to a generator. Consider:

sage: def test():
....:     if False: yield 1
....: 
sage: test()
<generator object test at 0x105434970>

So it is good practice to use yield from to pass on another generator, instead of just returning the generator object.

[dkrenn]

Replying to mkoeppe:

Replying to dkrenn:

_..._ is used in methods like _repr_

Yes, but this specifically mimics the "dunder" method __repr__ to which it is connected.

I see, thank you for this explanation. Anyways, the function discussed was renamed and refactored.

[dkrenn]

Replying to mkoeppe:

But it is the syntactic presence of yield in the body of a function that changes a function to a generator. Consider:

sage: def test():
....:     if False: yield 1
....: 
sage: test()
<generator object test at 0x105434970>

So it is good practice to use yield from to pass on another generator, instead of just returning the generator object.

Ok, thank you. Yes, we then should keep the yields from.

[mkoeppe]

+    if split is True:
+        split = (
+            (Polyhedron(
+                ieqs=[tuple(1 if i==b else (-1 if i==a or i==0 and a > b else 0)
+                            for i in range(d+1))
+                      for a, b in zip(pi[:-1], pi[1:])]),
+             'b{}'.format(pi[0]-1) +
+             ''.join((' <= ' if a < b else ' < ') +
+                     'b{}'.format(b-1)
+                     for a, b in zip(pi[:-1], pi[1:])))
+            for pi in Permutations(d))
+

This part looks a bit magical, could you illustrate this with doctests somewhere?

[mkoeppe]

Also, the docstring of compositions_mod should probably use the word "all" somewhere. Are these ALL solutions to this modular equation? Is every solution returned exactly once? etc.

Also the examples should be revised because in the output the crucial choice of the modulus for each of the components is not visible.

Overall, I think I would be happier if this whole thing could be redone in the language of point lattices (sage.modules.free_module_integer) and their cosets --- but I have not looked at how you use the result.

[git]

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

​6dca949	Trac #22067 comment:109(2): show moduli in doctests
​811d0b9	Trac #22067 comment:109(1): say that "all" tuples are returned in compositions_mod
​1636422	Trac #22067 comment:108: add a doctest to show split polyhedra

[dkrenn]

Replying to mkoeppe:

Also, the docstring of compositions_mod should probably use the word "all" somewhere. Are these ALL solutions to this modular equation? Is every solution returned exactly once? etc.

Done.

Also the examples should be revised because in the output the crucial choice of the modulus for each of the components is not visible.

Done.

Overall, I think I would be happier if this whole thing could be redone in the language of point lattices (sage.modules.free_module_integer) and their cosets --- but I have not looked at how you use the result.

The helper function compositions_mod returns the results exactly as needed in the class TransformMod. I suggest to do this "upgrade" of the function on a follow-up ticket.

[dkrenn]

Replying to mkoeppe:

This part looks a bit magical, could you illustrate this with doctests somewhere?

Not that easy, but I somehow managed to write a doctest showing some details of this specific part of the code.

[mkoeppe]

typo: "substitited"

[mkoeppe]

Replying to dkrenn:

Overall, I think I would be happier if this whole thing could be redone in the language of point lattices (sage.modules.free_module_integer) and their cosets --- but I have not looked at how you use the result.

The helper function compositions_mod returns the results exactly as needed in the class TransformMod. I suggest to do this "upgrade" of the function on a follow-up ticket.

Thanks for the changes you made. I agree, this part is sufficiently clear now

[git]

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

​d24a4ca

Trac #226067 comment:112: fix typo

[dkrenn]

Replying to mkoeppe:

typo: "substitited"

Fixed.

[mkoeppe]

Replying to dkrenn:

Replying to mkoeppe:

This part looks a bit magical, could you illustrate this with doctests somewhere?

Not that easy, but I somehow managed to write a doctest showing some details of this specific part of the code.

Thanks, this is an improvement. Now I understand that the strings that are assembled in this part of the code are just used for logging.

I think both the description of the "splitting" in the documentation and the implementation can be made more transparent.

Perhaps it should at least be said that if split=True, it uses the complement of the hyperplane_arrangements.braid.

[mkoeppe]

I was hoping to have something like TransformHrepresentation in more generality (related to #30198), but that's of course outside of the scope of this ticket

[mkoeppe]

Maybe all of the helper classes in this file should be marked as internal somehow (can we use leading underscores for class names too?) so that if this is reworked for more generality, we don't have to go through deprecation.

[mkoeppe]

Likewise for compositions_mod - it shouldn't be a public interface

[mkoeppe]

+                ieqs=[tuple(1 if i==b else (-1 if i==a or i==0 and a > b else 0)
+                            for i in range(d+1))

how about splitting out the 0th position of this tuple here to make this more transparent.

[mkoeppe]

There is a nontrivial algorithm in SplitOffSimpleInequalities._transform_, which probably needs some explanation

[mkoeppe]

Replying to dkrenn:

Replying to mkoeppe:

There is still a prefix_variable_name in a docstring

Indeed, thanks, fixed.

Following up on name/names:

+        sage: generating_function_of_integral_points(P2[0],
+        ....:     sort_factors=True, names=('a', 'b'))
+        Traceback (most recent call last):
+        ...
+        ValueError: exactly one variable name has to be provided

I don't understand this restriction. Why would the user not be allowed to provide all the names for the variables?

[dkrenn]

@mkoeppe, thank you. I brievley looked over your comments and agree that these should be incorporated. I'll be off for some time now (maybe a week) and then continue to work on this.

[git]

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

​cb021aa	Trac #22067: update file-header (year, support)
​0a40e08	Trac #22067 comment:119: make transform-helper classes internal
​122d080	Trac #22067 comment:120: make compositions_mod internal
​b086f94	Trac #22067 comment:117 and comment:121: make code for split=True more transparent
​e6f9513	Trac #22067 comment:117: document ``split`` better
​a43c6be	Trac #22067 comment:123: NotImplemented error when more than one variable names are provided

[dkrenn]

Replying to mkoeppe:

Replying to dkrenn:

Replying to mkoeppe:

This part looks a bit magical, could you illustrate this with doctests somewhere?

Not that easy, but I somehow managed to write a doctest showing some details of this specific part of the code.

Thanks, this is an improvement. Now I understand that the strings that are assembled in this part of the code are just used for logging.

I think both the description of the "splitting" in the documentation and the implementation can be made more transparent.

Documentation rewritten and extended.

Perhaps it should at least be said that if split=True, it uses the complement of the hyperplane_arrangements.braid.

Rephrased now anyways. (Not sure if bringing in two more concepts ("braid" and "complement of") would makes things more clear.)

[dkrenn]

Replying to mkoeppe:

Maybe all of the helper classes in this file should be marked as internal somehow (can we use leading underscores for class names too?) so that if this is reworked for more generality, we don't have to go through deprecation.

Now they are internal (IMO this should have been also without the fear of a deprecation).

[dkrenn]

Replying to mkoeppe:

Likewise for compositions_mod - it shouldn't be a public interface

Done.

[dkrenn]

Replying to mkoeppe:

+                ieqs=[tuple(1 if i==b else (-1 if i==a or i==0 and a > b else 0)
+                            for i in range(d+1))

how about splitting out the 0th position of this tuple here to make this more transparent.

Code majorly rewritten with the hope that it is clearer now.

[dkrenn]

Replying to mkoeppe:

Replying to dkrenn:

Replying to mkoeppe:

There is still a prefix_variable_name in a docstring

Indeed, thanks, fixed.

Following up on name/names:

+        sage: generating_function_of_integral_points(P2[0],
+        ....:     sort_factors=True, names=('a', 'b'))
+        Traceback (most recent call last):
+        ...
+        ValueError: exactly one variable name has to be provided

I don't understand this restriction. Why would the user not be allowed to provide all the names for the variables?

Can be done on a follow up ticket; it raises a NotImplementedError now.

[dkrenn]

Replying to mkoeppe:

There is a nontrivial algorithm in SplitOffSimpleInequalities._transform_, which probably needs some explanation

This is still open.