polyhedra with strict inequalities and Ehrhart

[kcrisman]

Thanks to the MUCH easier install now of things like pynormaliz and latte (thanks to all who worked on those!), I can now do the following and related computations nicely.  

sage: n=1                                                                       

sage: P = Polyhedron(ieqs=[[-(n)/2,1,0,0],[-(n)/2,0,1,0],[(3*n)/2,-1,-1,-1],[0,1

....: ,0,0],[0,0,1,0],[0,0,0,1],[n,-1,0,0],[n,0,-1,0],[n,0,0,-1]],backend='norma

....: liz')                                                                     

sage: [p.factor() for p in P.ehrhart_quasipolynomial()]                         

[(1/48) * (t + 2) * (t + 4) * (t + 6), (1/48) * (t - 1) * (t + 1) * (t + 3)]

However, what I really need is an Ehrhart quasi-polynomial for some of the above inequalities to be *strict* inequalities, and I'm not sure how to do that without tedious finding of some (not all) faces and subtracting them off (which could be a nightmare and/or wrong in any case).  Unfortunately changing the non-strict inequalities "by hand" to other numbers gives the wrong answers (really unsurprising, since it's a different polytope).

Any thoughts?  Thanks!

[Matthias Koeppe]

Normaliz already supports half-open polyhedra, see section 3.12 ("open facets") in the Normaliz manual

see https://github.com/Normaliz/Normaliz/blob/master/doc/Normaliz.pdf

[kcrisman]

Normaliz already supports half-open polyhedra, see section 3.12 ("open facets") in the Normaliz manual

see https://github.com/Normaliz/Normaliz/blob/master/doc/Normaliz.pdf

Thank you!  But, based on the tickets I've just been cc:ed on, probably there is no current easy Sage interface for these?   Also, it's only certain of the inequalities I would want to be strict - is that too much to ask?  Maybe "Semiopen polyhedra" is more like what I'm looking for - I do not know the facets, only the inequalities, which in more complicated examples than the one I provided tend to have nontrivial interactions.

[Matthias Koeppe]

On Wednesday, July 7, 2021 at 2:36:27 PM UTC-7 kcrisman wrote:

Normaliz already supports half-open polyhedra, see section 3.12 ("open facets") in the Normaliz manual

see https://github.com/Normaliz/Normaliz/blob/master/doc/Normaliz.pdf

Thank you!  But, based on the tickets I've just been cc:ed on, probably there is no current easy Sage interface for these?  

That's right. You would have to use PyNormaliz directly.

Also, it's only certain of the inequalities I would want to be strict - is that too much to ask?  Maybe "Semiopen polyhedra" is more like what I'm looking for - I do not know the facets, only the inequalities, which in more complicated examples than the one I provided tend to have nontrivial interactions.

I think Normaliz only supports the special case of polyhedra with some facets removed, not the more general situation in which you would remove some lower-dimensional faces. This case would still have to be handled using a combination of techniques, including inclusion-exclusion and reciprocity (including the technique of "inside out polytopes").

sage.geometry.polyhedron.modules.FormalPolyhedraModule is a step toward expressing such decomposition and transformation techniques, see https://trac.sagemath.org/ticket/29799

 

[Dima Pasechnik]

I presume you can enumerate vertices and facets, or remove redundant inequalities in a more direct way.

Algorithmically these are easier tasks than counting integer points, IMHO.

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/0bbfa6be-7b3c-4fd5-8ab7-b63430850305n%40googlegroups.com.

[kcrisman]

I presume you can enumerate vertices and facets,

Unsure on how easy it will be to do this for my use case.

 

or remove redundant inequalities in a more direct way.

On a case-by-case basis, in principle, yes, this is the approach taken in the particular literature I'm looking at.  However, what I really want is the Ehrhart quasi-polynomials for these things, and it would be "best" to automate it completely from the original inequalities, which take a very predictable form.   Maybe it will be easiest to use non-strict inequalities, and then subtract off (as Matthias implies) the lower-dimensional equalities.  Thanks!

[Dima Pasechnik]

On Thu, Jul 8, 2021 at 7:15 PM kcrisman <kcri...@gmail.com> wrote:
>
>
>> I presume you can enumerate vertices and facets,
>
>
> Unsure on how easy it will be to do this for my use case.
>
>>
>> or remove redundant inequalities in a more direct way.
>
>
> On a case-by-case basis, in principle, yes, this is the approach taken in the particular literature I'm looking at.

However, what I really want is the Ehrhart quasi-polynomials for
these things, and it would be "best" to automate it completely from
the original inequalities, which take a very predictable form.

maybe you could actually figure out the the irredundant ones? (which
would amount - dually- to repeatedly adding inequalities to a pool
and check that the pool elements are - dually - in convex position,
removing
ones which are not.)
If this sort of sieving is not implemented in Sage then it should.

Also, aside from Normaliz, PPL
(https://www.bugseng.com/products/ppl/documentation/user/ppl-user-1.2-html/index.html),
on which Sage's rational polyhedra code is based, has all these
non-closed, half-closed, etc
things, they just have not made it fully into Sage interface.

> Maybe it will be easiest to use non-strict inequalities, and then subtract off (as Matthias implies) the lower-dimensional equalities. Thanks!
>

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/217a12f1-88df-401e-9c98-397394110808n%40googlegroups.com.

[kcrisman]

Thanks for these ideas; I'm not sure which one I will pursue but this gives a number of options.