Solving A System Of Linear Diophantine Equations With Bounded Variables

Diophantine equation theory can be traced back to very early, especially linear Diophantine equation problem. With the rapid development of computer science in many fields, the peoblem of linear Diophantine equations has attracted more attention again. In fact, most practical problems of linear Diophantine equations contain constraint conditions. So far, there have been many studies to the problems with constraint conditions, some of which make some good results. The first chapter of this paper is devoted to a number of classic and current popular method of solving linear Diophantine equations. However, these methods fail to give a complete characterization of constraint problems in the mathematical theory , but only in some special conditions. In computation, these algorithms are still very worthy of recognition and serve as new tools for other issues. In the second and third chapter, we develop a algebraic geometry method based on the integer programming, which gives a better answer of the constraint problems in both theory and computation.General linear Diophantine equations problem is to compute the integer solution x∈Zⁿ of the linear system Ax = b, A = (a_i,j)∈Z^m×n,b = (b_j)∈Z^m. If all the solutions are confined to a certain constraints, the problem belongs to the category of the linear Diophantine equations problem with constraints. This problem has been recognized as NP-complete problem, and there are two kinds of the most representative and the most widely used problems as follows.1. Half bounds: the solvability of linear Diophantine system with the constraints x∈Nⁿ.2. Full bounds: the solvability of linear Diophantine system with the con- straints l≤x≤r∈Zⁿ.For the problem with full bounds, the system {Ax = b : l≤x≤r∈Zⁿ} can be converted to {Ax' = b':0≤x≤u∈Nⁿ} with x' = x - l, u = r - l. So we can directly consider the simplification of the problem with full bounds.The method in this paper is based on the subalgebra or ideal membership problem in algebraic geometry. In integer programming, there is a classic method that convert linear system to a equivalent ideal. For the linear system above, define a mapUsing the ring of Laurent polynomials, we can replace z₁^-1,…, z_m^-1} with a single variable t. Then the polynomials above are equivalent towith a'_i,j = a_i,j - e_j, e_j = min{a_i,j : a_i,j < 0}, b'_i = b_i - e, e = min{b_i : b_i < 0}.The problem with half bounds can be converted to the membership problem of the ideal J1 =〈tz₁…z_m - 1, f₁ - y₁,…, f_n - y_n〉∈k[t, z₁,…,z_m,y₁,…,y_n]. Let G_J1 be the reduced Gr(?)bner basis of J1 with respect to the elimination order:{t,z_i} (?) y_j. Forα∈Zⁿ, let a⁺ = max{α,0},α^- = max{-α,0},α=α⁺ -α^-.Theorem 1. Let f, J1, G_J1 as before, and (?) is the remainder of f by G_J1, then (?) is a monomial; Specially, if (?)∈k[y₁,…,y_n], then (?)α∈In this paper, we convert the problem with full bounds to another ideal membership problem. Similarly, let J2 =〈tz₁…z_m - 1, w₁f₁ - v₁,…,w_n f_n - v_n〉∈k[t, z₁,…,z_m,v₁,…,v_n,w₁…,w_n], and G_J2 is the reduced Gr(?)bner basis of J2 with respect to the elimination order:{t, z_i}(?) Let M = {x∈Nⁿ : Ax = b, 0≤x≤u∈Nⁿ\ {0} }. Theorem 2. Let h =(?), and the solution set Mas before, then M≠(?) if and only if h ^J2∈k[v₁,…v_n,w₁,…, w_n] ; Especially,if (?) , thenα∈M.Next, there is some discussions of the computation of the Hilbert basis of the homogeneous linear Diophantine system and all the solutions of the problem with full bounds. Simply speaking, if we regrad all non-trivial solutions of the Diophantine linear system Ax = 0 as a poset with respect to a order defined in§1.2.1. Then all the minimal elements in the poset is said to be the Hilbert basis (Defmition1.2), and denoted H. The computation of the Hilbert basis is the key of solving the problem with half bounds. Similar to the computation of classic toric ideal, the following proposition can improve the method of the computation of the Hilbert basis. Denoted k[t, Z, V, W] = k[t, z₁,…, z_m, v₁,…, v_n, w₁,…, w_n].Proposition 1. Let {α₁,…,α_p} be a lattice basis of ker(A)∩Zⁿ, defineαideal J' =(?) Let S be the subset of J'∩k[V, W] consisting of elements of the form V^α-W^αfor someα∈Nⁿ. Then {α: V^α- W^α∈S} is the Hilbert basis H.let G'_J2 be the reduced Gr(?)bner basis of J2 with respect to the new elimination order:(?). So we can develop a algorithm to compute all the solutions of the problem with full bounds.Proposition 2. Let h =f·W^u, if (?), thenα∈M, and V^αW^u-α is the smallest of the set {V^βW^u-β :β∈M} with respect to the elimination order: (?).Let the elimination order in the above Proposition be the lex order: (?), then the partV^αof V^αW^u-α is the biggest element in {V^x : 0≤x≤u, Ax = b} with respect to (?). For all the solutionsβ∈M, the corresponding monomial V^βmust be smaller than other V^α. So all the elements in M can be computed effectively. See Algorithm2.1 in§2.3.2.Thus, the method in this paper have been able to characterize the problem of linear Diophantine equations with bounded variables completely in theory. The following discussion is on the problems in computations.Definition 1. Letα_i, i = 1,…,n be the i column of the matrix A. An ideal I is said to be the toric ideal of A, if the ideal I∈k[X] is the kernal of the map (?).With the appropriate selection of X , Tand A, it is easy to verify that all the following ideals are toric ideals.In [14], there is a detailed description of the properties of the toric ideal (?). With the appropriate selection of X , Tand A, it is not difficult to be extended the properties in [14] to thetoric ideal considered in this paper. Taking Buchberger algorithm for example, the advantages in the computation of Gr(?)bner basis of toric ideal is that the structure of polynomial can be replaced by the vector structure, i.e. replacing (?) byα∈Zⁿ. And the computation of the polynomial reductions and S polynomial is equal to the subtraction of the corresponding vectors. So the Gr(?)bner basis of toric ideal can be defined in the vector form and the algorithm3.1 is an equivalent algorithm. To a certain extent, these properties can accelerate the speed of computation and also reflect some intrinsic relations between the method in this paper and the traditional linear algebra method.At last, we have made an attempt to compute the Gr(?)bner basis of toric ideal using F₅ algorithm and proved that the generated polynomial sequence of the toric ideals in this paper is a regular sequence (see Definition3.3). In [22] there is a property that all the critical pairs can not be reduced to zero if the input polynomials is a regular sequence in F₅ algorithm. So all the unnecessary reductions, which is the main reason for the complexity, will not be computed in F₅ algorithm. But F₅ algorithm askes for the homogeneous input polynomials, and the homogenization with a additional variable despoils of these good properties of toric ideal. However, we conjecture that the homogenization of the generated polynomial sequence of the toric ideals is still a regular sequence. In fact, we do not want to lose the properties of toric ideal, so we propose another conjecture that: the homogeneous polynomials in F₅ algorithm can be replaced by some specialΓ-homogeneous polynomials with some special gradings, so we can effectively compute the Gr(?)bner basis and the d-Gr(?)bner basis(see Definition2.4) which defined by the special gradings of the problem with constraints.Inspired by F₅ algorithm, we want to compute the d-Gr(?)bner basis instead of the original Gr(?)bner basis using a new grading defined by the bound u or the linear system A, b. Especially, we have made an attempt to compute the toric ideal ,J2 = (?) in§2.3. Define the gradingΓin k[t, Z, V, W] byΓ(?), withα∈N,b∈N^m, andα= {α₁,…,α_n},β= {β₁,…,β_n}∈Nⁿ. Then the generating polynomial of ,J2 arcΓ-homogcneous. Let d_u =Γ(h) = u₁ +…+ u_n, then it will reduce the computation in computing d_u-Gr(?)bner basis only to some extent. More general method need to be studied further.