Do Diophantine solution bounds themselves require a secondary solving operation?

Question

With a Diophantine equation like

$$889a + 90b - 90c - 2000d = 0$$

Sympy provides the following solution:

$$a = 10 t_0$$ $$b = t_1$$ $$c = 79121 t_0 + 1001 t_1 + 200 t_2$$ $$d = -3556 t_0 - 45 t_1 - 9 t_2$$

where the only known constraints on all $t$ is that they're integers.

If I have other constraints: $0 \le a, b, c, d < 10$, what is the best way to determine the range of all $t$? I fear that in the general case (not knowing the degree or linearity of the original equation at compile time) this requires setting up six linear programming problems - double the number of degrees of freedom of the Diophantine solution - to minimize and maximize each degree of freedom $t$.

Answer 1

About as pleasant as it is going to get: your expression in terms of a reduced basis is $$ (a,b,c,d) = u(0,1,1,0) + v (-20,21,-21,-7) + w(30,18,-19,15)$$ You may check the dot product of the original $(889, 90, -90, -2000)$ with each of these row vectors.

? newbasis = colbasis * toreduce
%20 = 
[0 -20  30]

[1  21  18]

[1 -21 -19]

[0  -7  15]

? nt = mattranspose(newbasis)
%21 = 
[  0  1   1  0]

[-20 21 -21 -7]

[ 30 18 -19 15]

? gramnew = nt * newbasis
%22 = 
[ 2    0   -1]

[ 0 1331   72]

[-1   72 1810]

? matdet(gramnew)
%23 = 4806521