Opened 12 years ago

Closed 12 years ago

#9188 closed defect (fixed)

lattice_polytope.facet_normal bug with polytopes of less that full dimension

Reported by: vbraun Owned by: novoselt
Priority: major Milestone: sage-4.5.2
Component: geometry Keywords:
Cc: novoselt Merged in: sage-4.5.2.alpha0
Authors: Volker Braun Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

In general, lattice_polytope._embedding_matrix is not orthogonal. But facet_normal() implicitly makes this assumption by embedding the normals (which live in the dual vector space) by the transpose of the _embedding_matrix.

Here is an example of the incorrect result:

sage: lp = LatticePolytope(matrix([[1,1,-1,0],[1,-1,-1,0],[1,1,1,0],[3,3,3,0]]))
sage: lp.vertices()
[ 1  1 -1  0]
[ 1 -1 -1  0]
[ 1  1  1  0]
[ 3  3  3  0]
sage: lp.facet_normal(0)
(-1, 0, 1, 3)
sage: lp.vertices() * lp.facet_normal(0)
(-2, -2, 0, 0)
sage: lp.facet_constant(0)
-9

If lp.facet_normal(0) would define a facet then its equation would be satisfied at 3 out of 4 vertices.

The attached patch fixes this issue. A scale factor for the dual embedding is introduced to keep the facet normal coordinates integral. Moreover, a suitable doctest is added.

NOTE: This bug impacts the toric variety code under development in #8986, #8987:

sage: c = Cone([(1,0,0,0),(0,1,0,0),(0,0,1,0)])
sage: c.faces()
((0-dimensional face of 3-dimensional cone,), (1-dimensional face of 3-dimensional cone, 1-dimensional face of 3-dimensional cone, 1-dimensional face of 3-dimensional cone), (2-dimensional face of 3-dimensional cone, 2-dimensional face of 3-dimensional cone, 2-dimensional face of 3-dimensional cone), (3-dimensional face of 3-dimensional cone,))
sage: c = Cone([(1,1,1,3),(1,-1,1,3),(-1,-1,1,3)])
sage: c.faces()
((0-dimensional face of 3-dimensional cone,), (2-dimensional face of 3-dimensional cone,), (3-dimensional face of 3-dimensional cone,))

Attachments (2)

trac_9188_fix_facet_normal.patch (3.7 KB) - added by vbraun 12 years ago.
Updated patch
trac_9188_fix_facet_normal_reviewer.patch (6.5 KB) - added by novoselt 12 years ago.
Apply on top of the original patch.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 12 years ago by vbraun

  • Status changed from new to needs_review

comment:2 Changed 12 years ago by vbraun

I missed two doctests that were failing; Some of the old doctests actually did give the wrong facet normals :-) Also, I improved my new doctest to also check the facet_constant().

comment:3 Changed 12 years ago by novoselt

  • Owner changed from mhampton to novoselt
  • Reviewers set to Andrey Novoseltsev

This is very embarrassing... Will look over and take care of propagated errors.

comment:4 Changed 12 years ago by vbraun

I forgot one more transposition of a matrix %-) This version should be correct now. Added another doctest.

Changed 12 years ago by vbraun

Updated patch

comment:5 Changed 12 years ago by novoselt

Yeap, the first version was definitely wrong...

Changed 12 years ago by novoselt

Apply on top of the original patch.

comment:6 Changed 12 years ago by novoselt

OK, my patch looks big, but the only real change to the original is taking the absolute value of the dual scaling factor, so that normals remain inner.

In addition I (hopefully) made doctests more clear, since they do appear in the documentation. Polytopes are now created using coordinates of points with all the necessary transpositions after that. I also made doctest lines shorter for better looks of the documentation.

I have changed "parallel" to "orthogonal to integer kernel" in the description of normals (and now I do remember that I didn't like this "parallel" when I wrote it...).

If you are fine with all these changes, I will switch it to positive review. Thank you for catching this bug!

comment:7 Changed 12 years ago by vbraun

Good idea to make sure that the scaling factor is positive. I also like your work on the doctests. Looks good to me!

Note to release manager: apply both patches in order!

comment:8 Changed 12 years ago by novoselt

  • Status changed from needs_review to positive_review

comment:9 Changed 12 years ago by novoselt

Patch at #8986 still applies fine and does not expose any errors in doctests, so let's leave it as is. I will add your example from this ticket into the next patch for #8987 which I am working on now.

comment:10 Changed 12 years ago by mpatel

  • Merged in set to sage-4.5.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.