A note on equivalent systems of linear diophantine equations

Summary Another constructive proof is presented for the fact that a system of linear equations with integer coefficients in bounded integer variables is equivalent to a single equation, which is a linear combination of the original ones. The equation is obtained in a number of steps; in each step two equations are replaced by a single one. This replacement is performed subject to the condition that the remaining equations hold and a final equation with relatively small coefficients is obtained. It may be inefficient however to calculate small coefficients, as the original coefficients can be used to represent the final ones in a suitably chosen number system.

---

Zusammenfassung Ein System linearer Gleichungen mit ganzzahligen Koeffizienten in beschränkten ganzzahligen Variablen ist äquivalent zu einer einzigen Gleichung, die sich als Linearkombination der ursprünglichen Gleichungen schreiben läßt. In einem neuen konstruktiven Beweis von diesem Satz wird gezeigt, wie die endgültige Gleichung in einigen Schritten gefunden werden kann. In jedem Schritt werden zwei Gleichungen von einer einzigen ersetzt unter der Voraussetzung, daß die übrigen Gleichungen gültig bleiben.Obwohl die Koeffizienten der Endgleichung verhältnismäßig klein sind, ist es nicht immer zweckmäßig, sie in der angegebenen Weise zu berechnen, da man ein Zahlensystem anwenden kann, in dem die Koeffizienten der ursprünglichen Gleichungen zur Darstellung der neuen Koeffizienten gebraucht werden.

---

---

This note is a slightly revised version of report BW 12/71 (July 1971).     

Parallel algorithm for linear diophantine equations

We consider a parallel-sequential algorithm to find all the solution of a linear Diophantine equation a_nx_n + a_n — 1x_n — 1 + +a₁x₁ = b, a_i, b, x_i Z⁺ by the method of dynamic upper bounds. Parallel processing and dichotomizing search are responsible for logarithmic time complexity of the algorithm. The auxiliary table memory requirements are 3n words. The algorithm can be applied in linear integer programming problems.Simferopol' University. Translated from Dinamicheskie Sistemy, No. 10, pp. 111–117, 1992.     

A spectral algorithm for sequential aggregation ofm linear diophantine constraints

An algorithm is developed for the sequential determination of the coefficients of a generalized linear Diophantine constraint which is equivalent to a given system of generalized linear Diophantine constraints.

---

Zusammenfassung Ein Algorithmus wird entwickelt für die sequentielle Bestimmung der Koeffizienten einer verallgemeinerten linearen Diophantischen Restriktion, die einem vorgelegten System verallgemeinerter linearer Diophantischer Restriktionen äquivalent ist.

     

Existence and representation of diophantine and mixed diophantine solutions to linear equations and inequalities

In this paper we present necessary and sufficient conditions for the existence of solutions to more general systems of linear diophantine equations and inequalities than have previously been considered. We do this in terms of variants and extensions of generalized inverse concepts which also permit us to give representation of the set of all solutions to the systems. The results are further extended to mixed integer systems.     

A removal lemma for systems of linear equations over finite fields

We prove a removal lemma for systems of linear equations over finite fields: let X ₁, …, X _m be subsets of the finite field F _q and let A be a (k × m) matrix with coefficients in F _q ; if the linear system Ax = b has o(q ^m−k ) solutions with x _i ∈ X _i , then we can eliminate all these solutions by deleting o(q) elements from each X _i . This extends a result of Green [Geometric and Functional Analysis 15 (2) (2005), 340–376] for a single linear equation in abelian groups to systems of linear equations. In particular, we also obtain an analogous result for systems of equations over integers, a result conjectured by Green. Our proof uses the colored version of the hypergraph Removal Lemma.     

A necessary and sufficient condition for the aggregation of linear diophantine equations

Summary The set of the integer values a linear form can take may be called its spectrum. Aggregating two equations means establishing a linear combination of the two left hand side spectra, the coefficients of which are the aggregation weights. If and only if this linear combination does not contain any spectral correlation point other than the right hand side vector, the equation found by aggregation is equivalent to the two given ones.Methods for calculating the spectrum and the spectral correlation set are given.

---

Zusammenfassung Der Wertevorrat einer Diophantischen Linearform möge als deren Spektrum bezeichnet werden. Die Zusammenfassung zweier Diophantischer Gleichungen läuft auf die Bildung einer Linearkombination der Spektren hinaus, die zu den beiden auf der linken Seite stehenden Linearformen gehören. Die Koffizienten der Linearkombination sind gleich den für die Zusammenfassung verwendeten Gewichten. Wenn und nur wenn die erwähnte Linearkombination ausser dem Punkt, dessen Koordinaten die auf der rechten Seite des Gleichungssystems stehenden Zahlen sind, keine anderen Spektral-Korrelationspunkte enthält, ist die durch Zusammenfassung gebildete Gleichung äquivalent dem System der beiden Ausgangsgleichungen.Methoden für die Berechnung von einfachen und korrelierten Spektren werden gegeben.

     

A theorem in diophantine approximations

In this paper we derive, under certain conditions, an asymptotic formula for the number of solutions of diophantine inequalities involving systems of linear forms.     

Solution to a linear diophantine equation for nonnegative integers

We solve the 3-variable problem: find integers x ≥ 0, y ≥ 0, z ≥ 0 that satisfy ax + by + cz = L for given integers a, b, c, L, where 1 < a < b < c < L. The method of solution is related to the one for the Frobenius problem in three variables, which has been solved by Selmer and Beyer and by Rödseth (J. Reine Angew. Math.301 (1978), 161–178). These methods take O(a) steps, in the worst case, to find the Frobenius value. The method here, for the Frobenius value, is shown to be rapid, requiring less than O(log a) steps. The diophantine equation is then solved with little extra effort to result in an O(log a) method overall.     

On linear forms with algebraic coefficients and diophantine equations

In my paper, [Man. Math.18 (1976), Satz 1.1] I proved a result on simultaneous diophantine inequalities for p-adic linear forms with algebraic coefficients. In this paper I shall generalize this result and give a necessary and sufficient criterion for the estimation of a product of complex and p-adic linear forms with algebraic coefficients, implying a theorem of Schmidt, [Math. Ann.191 (1971), Satz 1]. Using this estimate I shall obtain the p-adic generalization of Schmidt's theorems on diophantine equations of norm form type [Ann. of Math.96 (1972)].     

A radical diophantine equation

All solutions in positive integers x, yz of the diophantine equation $\text{x}{}^{\mathrm{<mtext>1</mtext><mtext>m</mtext>}}\text{+ y}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= z}{}^{\mathrm{<mtext>1</mtext><mtext>r</mtext>}}$ are determined, where m, n, r are given positive integers. The proof makes use of a simple criterion for the irreducibility of the polynomial xⁿ ? a over the rationals, where a is a positive rational.     

A general Farkas lemma

An abstract version of the classical Farkas lemma for locally convex spaces is given. The abstract Farkas lemma is shown to imply Farkas-type results which have been obtained by Shimizu-Aiyoshi-Katayama, Schecter, Eisenberg, Zalinescu, and Smiley.