Bug in lattice_polytope.positive_integer_relations

[edd8e884-f507-429a-b577-5d554626c0fe]

Reported on this ask question:

sage: vertices = [(1,1,-1,-1,-1),(-1,-1,1,1,-1),(1,-1,-1,-1,1),(-1,1,1,1,1),(1,-1,1,-1,-1)]
sage: p = LatticePolytope(vertices)
sage: lattice_polytope.positive_integer_relations(p.vertices().column_matrix())
TypeError: unable to make sense of Maxima expression '"Problemnotfeasible!"' in Sage

Note that there is a non-negative nontrivial integer relation:

sage: p.vertices().column_matrix().right_kernel()
Free module of degree 5 and rank 1 over Integer Ring
Echelon basis matrix:
[1 1 1 1 0]

CC: @videlec @fchapoton @mkoeppe @rwst

Component: geometry

Author: Vincent Delecroix

Branch/Commit: public/19365 @ 651684a

Reviewer: Andrey Novoseltsev, Thierry Monteil

Issue created by migration from https://trac.sagemath.org/ticket/19365

[kcrisman]

comment:1

See also #19367, which however I think is, if not orthogonal, at least not spanned by this question.

[videlec]

comment:2

... changed a missing ) in the description...

[videlec]

Description changed:

--- 
+++ 
@@ -3,7 +3,7 @@

sage: vertices = [(1,1,-1,-1,-1),(-1,-1,1,1,-1),(1,-1,-1,-1,1),(-1,1,1,1,1),(1,-1,1,-1,-1)] sage: p = LatticePolytope(vertices) -sage: lattice_polytope.positive_integer_relations(p.vertices().column_matrix() +sage: lattice_polytope.positive_integer_relations(p.vertices().column_matrix()) TypeError: unable to make sense of Maxima expression '"Problemnotfeasible!"' in Sage

[videlec]

Author: Vincent Delecroix

[videlec]

Commit: 6f9c086

[videlec]

Branch: public/19365

[videlec]

comment:3

Simple solution.

---

New commits:

6f9c086

Trac 19365: fix positive_integer_relations

[kcrisman]

comment:4

-        if x.str() == r'?Problem\not\feasible\!':
-            raise ValueError("cannot find required relations")

Why wasn't this triggered in the old code?

I suggest you run some timing on this code too, and see what it reports when there isn't a relation, etc. I wonder why this non-generic code was used?

[videlec]

comment:5

Replying to @kcrisman:

-        if x.str() == r'?Problem\not\feasible\!':
-            raise ValueError("cannot find required relations")

Why wasn't this triggered in the old code?

I suggest you run some timing on this code too, and see what it reports when there isn't a relation, etc. I wonder why this non-generic code was used?

Timing against what? The old code crashes on most examples...

[novoselt]

comment:6

The new version obviously has a different return type.

There is also some helper Maxima method that can be removed if it is not used anymore.

Timings against the old code are indeed irrelevant - that was just something that I managed to get into a working code back when I was young ;-)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

51e2751	Trac 19365: fix return type
651684a	Trac 19365: deprecate sage->maxima helper

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6f9c086 to 651684a

[videlec]

comment:8

Replying to @novoselt:

The new version obviously has a different return type.

Right. Fixed.

There is also some helper Maxima method that can be removed if it is not used anymore.

Right. Deprecated.

[novoselt]

Reviewer: Andrey Novoseltsev

[edd8e884-f507-429a-b577-5d554626c0fe]

Changed reviewer from Andrey Novoseltsev to Andrey Novoseltsev, Thierry Monteil

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:10

The example provided in the doc is:

      sage: points = [(1,1,-1,-1,-1), (-1,-1,1,1,-1), (1,-1,-1,-1,1),
      ....:           (-1,1,1,1,1), (1,-1,1,-1,-1)]
      sage: positive_integer_relations(points)
      [(1, 0, 0, 1, 0)]

Could you explain how (1,1,-1,-1,-1) + (-1,1,1,1,1) == 0 ?

The result should be [(1, 1, 1, 1, 0)], see the ask question for the expected answer.

Given a list of tuples, is it more natural to interpret it as a list of vectors, or as a list of rows of a matrix whose columns are vectors ? We might argue that the doc says that the points "are given as columns of a matrix". But when the doc writes points = [(1,1,-1,-1,-1), (-1,-1,1,1,-1), (1,-1,-1,-1,1), (-1,1,1,1,1), (1,-1,1,-1,-1)], should the user consider this as a natural way to define the vectors [(1, -1, 1, -1, 1), (1, -1, -1, 1, -1), (-1, 1, -1, 1, 1), (-1, 1, -1, 1, -1), (-1, -1, 1, 1, -1)] ?

It could be even worse if the user explicitely writes points = [vector([1,1,-1,-1,-1]), vector([-1,-1,1,1,-1]), vector([1,-1,-1,-1,1]), vector([-1,1,1,1,1]), vector([1,-1,1,-1,-1])] so that no ambiguity appears on her side, but the first line of the code M = matrix(points), silently forgot all this information.

[novoselt]

comment:11

Good point. The old code would break right away on anything but the matrix and it looked at first as a good idea to have matrix constructor built in, but apparently it is not. I agree that both input and output formats of this function are not the best possible ones, but that's what it has been for ages (like since 2006/7), so let's keep it. Those who want to use this function have to do the conversion or write a new one and deprecate this one.

Interestingly, it is not used anywhere in Sage (I thought that somewhere in toric code it may be handy) but I am pretty sure I used it at some point in my worksheets.

[mkoeppe]

comment:12

This method was changed in #20766. Dup?

[mkoeppe]

comment:13

After #20766, the example in the description gives:

sage: vertices = [(1,1,-1,-1,-1),(-1,-1,1,1,-1),(1,-1,-1,-1,1),(-1,1,1,1,1),(1,-1,1,-1,-1)]
sage: p = LatticePolytope(vertices)
sage: lattice_polytope.positive_integer_relations(p.vertices().column_matrix())
MIPSolverException: PPL : There is no feasible solution