6
$\begingroup$

I made the following observation and I am wondering if it is always true.

Let $x_1$, $x_2$, $x_3$ and $x_4$ be four positive integer points in the plane ($x_i\in\mathbb{Z^2_{\geq 0}}$) forming a convex quadrilateral and let $x=x_1+x_2+x_3+x_4$. Then it seems it is always possible to write $x$ as the nonnegative integer combination of at most three integer points inside, or on the edges, of the convex quadrilateral.

Example 1. With $x_1=(0,1)$, $x_2=(0,3)$, $x_3=(2,1)$, $x_4=(2,3)$, we have $x=(4,8)$. And we can write $x$ as $x=2(2,1)+2(0,3)$.

Example 2. With $x_1=(0,2)$, $x_2=(1,3)$, $x_3=(3,0)$, $x_4=(5,1)$, we have $x=(9,6)$. And we can write $x$ as $x=(2,1)+2(2,2)+(3,1)$.

  • Is this observation true, or is there any counterexample? EDIT: Following the answer of fedja: yes it is always true, and obvious after all.
  • EDIT: In higher dimension $n\geq 3$, is it possible to generalize and say that the vector $x$, made of the sum of $2n$ integer points $x_i\in\mathbb{Z^n_{\geq 0}}$, can be written as the nonnegative integer combination of at most $2n-1$ integer points inside, or on the facets, of the convex polyhedron which has vertices $x_i$.

Thank you very much!

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ True, of course, because the parallelogram built on some 2 adjacent sides is contained in the quadrilateral, so we always have the representation of the kind $(x_1+x_2-x_3)+2x_3+x_4$ for some re-indexation of the vertices. However this is a typical MSE question, not an MO one. Ask such stuff there next time. $\endgroup$
    – fedja
    Commented Jun 28, 2018 at 9:52
  • 1
    $\begingroup$ @fedja Thank you very much for you answer! Sorry if it is too obvious. And in dimension n>=3, do you think it is possible to say that the sum of 2n integer points can always be written as a nonnegative integer combination of at most 2n-1 points? $\endgroup$
    – B. Gimazid
    Commented Jun 28, 2018 at 15:48
  • 1
    $\begingroup$ Caratheodory's Theorem states that if a point $x$ of ${\bf R}^d$ lies in the convex hull of a set $P$, then $x$ can be written as the convex combination of at most $d+1$ points in $P$ (copied from en.wikipedia.org/wiki/…). I wonder whether this theorem can be applied here. $\endgroup$
    – Gerry Myerson
    Commented Jun 28, 2018 at 23:57

1 Answer 1

Reset to default
1
$\begingroup$

I thought a few minutes on fedja's remark about a parallelogram contained inside the quadrilateral. It took me time to realize that you could "slide" an edge up with one point staying on one of the two edges until it hit the opposite side. That is, if you pick the side which, when sliding, does not get stuck by the two edges moving closer to one another (start at the narrow end, not at the wide end).

Because of the limits of two dimensions (narrow versus wide) this idea works and can be formalized. However, there is more freedom in three dimensions, so that one does not have "narrow" and "wide" to help. There may be a integral parallelogram hiding inside a convex shape defined by intersecting three intersections of pairs of half-spaces, but I am not seeing it. I suspect that if there is an integer point to be had, one has to work up to it by dimension, showing for example that there will be an integer point on a two dimensional face that can be used in the desired representation.

Gerhard "Stretching His Imagination Domain Today" Paseman, 2018.06.28.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .