# Representing integer points inside a polytope using a unit hypercube

Let $D\subset\mathbb{Z}\times\mathbb{Z}$ such that $D$ is formed by the points bounded by a convex polytope. Let $f:D\to\mathbb{R}$ defined by $f(x,y)=ax+by+c$, where $a,b,c\in\mathbb{R}$ and $g:D\to\mathbb{N}$.

Conjecture: We can always find a subset $\tilde{D}\subset D$, such that $\tilde{D}$ is a subset of some unit square (or maybe some other small set?) and a function $\tilde{g}:\tilde{D}\to\mathbb{N}$ such that $$\sum_{(x_i,y_i)\in D}g(x_i,y_i)f(x_i,y_i)=\sum_{(x_i,y_i)\in \tilde{D}}\tilde{g}(x_i,y_i)f(x_i,y_i)$$

Is this true considering $D\subset\mathbb{Z}^n$ and $\tilde{D}$ a subset of some unit hypercube?

-

## 1 Answer

If a,b, and c are linearly independent over the rationals, then you can translate this problem by replacing the term involving f by a 3-tuple of integers and ask if you can find a basis "inside" D that will express any nonnegative sum of elements "from" D as a positive or nonnegative combination of elements of the basis.

My guess is no. I have not worked out the details but something like the following should work. Imagine D as lying almst entirely in the positive xy quadrant, with two exceptions where one value of x is negative and y is positive, and the other with x positive and y negative, and they are far apart. Further assume g is 0 at all points except at the two extremes. Then the left hand sum could potentially have two negative components (corresponding to a and b of the tuples) while the right hand side could only manage 1 negative component because D' has to be chosen to be next to one or the other extreme points. Something similar should work for higher dimensions.

Gerhard "Ask Me About System Design" Paseman, 2011.08.12

-
I think D containing the points $(-6,1), (2,0), (5, -2)$ may be an illustrative example, as adding the two extreme points gives $c+c-a-b$, while $D'$ can contain at most one of the points of D. Gerhard "Ask Me About System Design" Paseman, 2011.08.12 –  Gerhard Paseman Aug 12 '11 at 20:28