MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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