2
$\begingroup$

Let $A$ be a matrix with entries either 0 or 1, where each column contains at least one 1, to remove trivial degenerations.

Let $P$ be the convex hull of all integer vectors $x$ that satisfy $Ax \leq y$, and $x\geq 0$, where $y$ is some non-negative integer vector. Clearly, $P$ is an integral polytope.

For example (to address David Speyers comment), when $$A=\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}, y=(1,1,1)$$ then $P$ is the convex hull of the solutions to $Ax\leq y$, so $P$ is the convex hull of $(0,0,0),(1,0,0),(0,1,0),(0,0,1)$, the standard simplex.

Doing some computer experiments, I believe the following:

Conjecture: P is integrally closed, i.e., every integer point $p \in kP$ can be expressed as $p=p_1+p_2+\dots+p_k$ where all $p_i$ are integer points in $P$, whenever $k$ is a natural number.

In the example above, this is known to be integrally closed.

Note that there are no conditions on the minors of $A$.

Is this a known result? This seems hard, since we do not have a nice description of $P$, that is, the supporting hyperplanes, nor the vertices, are explicitly known.

$\endgroup$
  • $\begingroup$ Isn't every $p\in kP$ by definition equal to $p=q+...+q$, for $q\in P$? Or do you mean to have $p_i\neq p_j$ for $i\neq j$ ? $\endgroup$ – Dima Pasechnik May 14 '14 at 13:11
  • $\begingroup$ Oh, I need to add property of being integer point! Sorry! $\endgroup$ – Per Alexandersson May 14 '14 at 13:12
  • $\begingroup$ Isn't $x+y \leq 1$, $x+z \leq 1$, $y+z \leq 1$ and the point $(1,1,1) \in 2 P$ a counterexample? $\endgroup$ – David E Speyer May 14 '14 at 17:57
  • $\begingroup$ Ah, @DavidSpeyer, yes, that is true. I realized that I have made an additional assumption in my tests, that is, each solution also lie in a hyperplane with normal (1,1,...,1). I edit the question accordingly. $\endgroup$ – Per Alexandersson May 14 '14 at 19:06
  • $\begingroup$ Your edit doesn't match your comment: Do you want a defining inequality of the form $\sum x_i \leq c$ or a defining equality? $\endgroup$ – David E Speyer May 14 '14 at 19:07
2
$\begingroup$

No. $$x_1+x_2 \leq 1 \quad y_1 + y_2 \leq 1 \quad z_1 + z_2 \leq 1$$ $$x_1+y_1+z_1 \leq 2 \quad x_2+y_2+z_1 \leq 2 \quad x_2+y_1+z_2 \leq 2 \quad x_1 + y_2 + z_2 \leq 2$$ $$(1,1,1,1,1,1) \in 2 P.$$

Note that the first three inequalities imply $x_1+x_2+y_1+y_2+z_1+z_2 \leq 3$. If we are to sum up two such points and get a point whose coordinates sum to $6$, then the two points of $P$ must have $$x_1+x_2+y_1+y_2+z_1+z_2 = 3.$$ So we will add this equality to our list of relations.

Together with this linear inequality, the first line of inequalities cuts out a cube. Projecting onto the $(x_1, y_1, z_1)$ coordinates, it is $[0,1]^3$.

The second line of inequalities gives a tetrahedron whose vertices are four non-adjacent vertices of the cube. Projecting onto $(x_1, y_1, z_1)$ again, we are talking about $(0,0,0)$, $(1,1,0)$, $(1,0,1)$ and $(0,1,1)$.

Since $x_1+y_1+z_1$ is even for all integer points in $P$, it is impossible for $(1,1,1,1,1,1)$ to be the sum of two such points.

The tetrahedron formed by nonadjacent vertices of a cube is the standard example of a non-integrally closed polytope with integer vertices; I just had to figure out how to embed it in inequalities of the form you gave.

$\endgroup$
  • $\begingroup$ The question as originally stated was correct; is this valid in that case (or can be modified to suit that)? The equality is not what I intended, I got confused for a short while, sorry. $\endgroup$ – Per Alexandersson May 14 '14 at 19:41
  • $\begingroup$ I don't think it's originally correct. If I delete the condition that the sum of the variables is $3$, I still don't think $(1,1,1,1,1,1)$ is the sum of two integer solutions to the inequalities. $\endgroup$ – David E Speyer May 14 '14 at 19:44
  • $\begingroup$ Yes, you are right; I just checked it. Without your equality, there are 188 integer points in 2P. All of these except (1,1,1,1,1,1) can be expressed as sums of two integer points in P... So yes, the conjecture as it is now is not true. Interesting... $\endgroup$ – Per Alexandersson May 14 '14 at 19:50
  • $\begingroup$ Conceptual way to do the check: The first line of inequalities implies sum of vars $\leq 3$. So, if $p+q = (1,1,1,1,1,1)$, then the sum of var must be $3$ for both $p$ and $q$. So I don't need to put that inequality in explicitly. $\endgroup$ – David E Speyer May 14 '14 at 19:58
  • 1
    $\begingroup$ Edited so that the counterexample matches the last round of edits to the question. $\endgroup$ – David E Speyer May 14 '14 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.