Suppose you know that 0 <= x1 <= x2 <= x3 <= ... etc.
How do you know whether one set of coefficients [a1, a2, ..., an]
produces numbers that are always less than another set [b1, b2, ...,
bn]?
That is, how do you determine for all
0 <= x1 <= x2 <= x3 <= ... <= xn
that
a1x1 + ... + anxn <= b1x1 + ... + bnxn ?
Primitive operations:
If you increment a coefficient, you increase the result:
[ ... +1 ... ]
If you subtract 1 from a lower coeff and add it to a higher coeff, you increase the result:
[ ... -1 .... +1 ... ]
Question: Does the cumulative operator achieve the comparison?
L = [[1 0 0 0]
[1 1 0 0]
[1 1 1 0]
[1 1 1 1]]
1. It has the correct result on the zero vector, returning 0.
2. It's linear, so we just have to show that the primitive increments have the right effect.
Increment a coefficient:
L [... +1 ...] = [0 0 ... 0 1 1 1 ... 1]
Decrement and increment:
L [... -1 ... +1 ...] = [0 0 0 -1 -1 -1 ... -1 0 0 0 0]
No go.
Hm. Maybe we need it to go right to left?
L = [[0 0 0 1]
[0 0 1 1]
[0 1 1 1]
[1 1 1 1]]
L [ ...+1...] = [1 ... 1 0 0 0 0 0]
L [ ... -1 ... +1 ...] = [0 0 0 ... 1 1 1 1 0 0 0]
Now we've got something that always increments! Excellent.