0

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$.

Reinderien
  • 192
  • 1
    the solution set, before any inequalities, is what we call a lattice, on this web page integer-lattice. With $t_0, t_1, t_2$ you have a "basis." It is then possible to ask for a reduced basis, which will tend to have small coefficients for small values of the original variables. I'll do that, takes a few minutes. – Will Jagy Nov 18 '20 at 22:16

1 Answers1

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
Will Jagy
  • 139,541
  • How did you arrive at the reduced basis? – Reinderien Nov 18 '20 at 22:39
  • 1
    @Reinderien it is called LLL reduction, https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm and is, in very small dimension, guaranteed to give best possible. Available in many software packages – Will Jagy Nov 18 '20 at 22:42
  • Are there constraints on your $u$, $v$, $w$? – Reinderien Nov 18 '20 at 22:44
  • @Reinderien no, it is still necessary to work out when $a,b,c,d$ are from, I guess, $0$ to $9.$ As $a$ is divisible by $10$ you get $a=0$ fro free, so $-20v+30w=0$ – Will Jagy Nov 18 '20 at 22:49
  • OK; so my general question still stands. Is linear programming the best way to find the bounds of $t$ within the permissible simplex? – Reinderien Nov 18 '20 at 22:50
  • 1
    @Reinderien I guess so. It seems to me I found some articles, years ago, about solving one or more linear Diophantine equation(s) with positivity required for all the variables, and your question just adds an upper bound. Hot topic in theoretical computer science...Stll, you are a little ahead of the game if you can deal with integer lattices. I did not type in the way I found a basis, that is not entirely trivial. – Will Jagy Nov 18 '20 at 22:53