Solutions minimales des systèmes diophantiens linéaires : bornes et algorithmes

Loïc Pottier

17 septembre 1990

Institut National de Recherche en Informatique et Automatique 2004 route des Lucioles, Sophia Antipolis, 06565 Valbonne CEDEX

                                  Email : pottier@mirsa.inria.fr

Résumé : On donne de nouvelles bornes et de nouveaux algorithmes concernant les solutions minimales de systèmes diophantiens linéaires. Nos bornes sont simplement exponentielles en la dimension du système, alors que les bornes connues jusqu’il y a peu étaient doublement exponentielles.

Minimal solutions for linear diophantine systems : bounds and algorithms

Abstract : We give new bounds and algorithms for minimal solutions of linear diophantine systems. Our bounds are simply exponential, while previous known bounds were, at least until recently, doubly exponential.

1 Introduction

Un système diophantien linéaire est un ensemble d’inéquations linéaires à coefficients entiers dont on cherche les solutions entières : Ax ≤ b, où A est une matrice d’entiers à m lignes et n colonnes, b un vecteur de Z^{m}et x un vecteur de n indéterminées. Rappelons que décider si un tel système a au moins une solution entière est un problème NP-complet. On s’intéresse ici à décrire et calculer l’ensemble des solutions, cela en étudiant un problème équivalent, qui est la résolution en entiers positifs des systèmes Ax = 0. Les solutions entières positives de Ax = 0 forment un sous-monoïde M de N^{n}, engendré par ses éléments non nuls minimaux pour l’ordre partiel (x_{1},…, x_{n}) ⪯ (y_{1},…, y_{n}) ⟺ ∀i, 1 ≤ i ≤ n, x_{i} ≤ y_{i}, qui forment un ensemble fini. On appellera cet ensemble “la base de Hilbert de M” (après [F.Giles et W.R.Pulleyblank 79]), et on le notera H(M). Les deux sections suivantes sont consacrées à borner les éléments de H(M), et à les calculer. La dernière section applique les résultats précédents au problème initial, i.e. la résolution des systèmes Ax ≤ b.

2 Bornes de H(M)

On sait depuis [J.Von zur Gathen et M.Sieveking 78] que si H(M) est non vide, elle contient un élément de norme (par exemple ∥x∥_{∞}, où ∥x∥_{∞} = sup_{i}| x_{i} |) au plus simple exponentielle en la taille de A (par exemple n.m.(log∥A∥_{∞} + 2)). Mais on s’intéresse ici à borner uniformément les normes des éléments de H(M).

Soient

∥M∥_{∞} = sup_{x∈H(M)}∥x∥_{∞}

et

∥M∥_{1} = sup_{x∈H(M)}∥x∥_{1}

(avec ∥x∥_{1} = ∑_{i} | x_{i} |). [I.Borosh et L.B.Treybig 76] ont majoré ∥M∥_{∞} par une expression double exponentielle en la taille de A. A notre connaissance, deux bornes simple exponentielles existent pour majorer ∥M∥_{∞} ou ∥M∥_{1}. Nous avons donné la première dans [L.Pottier 90]. La seconde peut être déduite d’un résultat peu connu de [J.L.Lambert 87]. Ces deux bornes sont essentiellement différentes de par leurs expressions et leurs démonstrations. On donne ici deux nouvelles bornes plus fines, la première inspirée de [L.Pottier 90], la seconde de [J.L.Lambert 87] et [A.Koscielski et L.Pacholski 90]. Rappelons que dans le cas d’une équation (m = 1), [G.Huet 78] puis [J.L.Lambert 87] ont donné des bornes ne dépendant que de ∥A∥_{∞}. Dans le cas de deux équations, [J.F.Romeuf 89] donne une borne quadratique en la taille de A.

2.1 Première borne

Cette borne est inspirée de [L.Pottier 90]. Soit ∥A∥_{l} = sup_{i}{∑_{j} | a_{ij} |}.

Théorème 1

∥M∥_{1} ≤ (1 + ∥A∥_{l})^{r} = B_{0}

Preuve :

On peut sans restriction choisir r équations indépendantes de Ax = 0. Soient x = (x_{1},…, x_{n}) un élément de M non nul, p = ∥x∥_{1}, et {e_{1},…, e_{n}} la base canonique de R^{n}. Pour tout y dans R^{n}, on note C_{y} le cube de volume 1 défini par

z ∈ C_{y} ⇔ z = y + ∑_{i=1}^{n} λ_{i}e_{i}, avec ∀i ∈ [1, n], λ_{i} ∈ [0, 1]

On va construire par récurrence une suite de N^{n} y^{0},…, y^{p} et une suite de R^{n} z^{0},…, z^{p} vérifiant :

y^{0} = 0 ≺ y^{1} ≺ … ≺ y^{p} = x.
∀k ∈ [0, p − 1], ∃j, y^{k+1} = y^{k} + e_{j}
∀k ∈ [0, p], z^{k} ∈ C_{y^{k}} ∩ [0, x].

y^{0} = z^{0} = 0 convient clairement.

Supposons y^{k} construit, 0 ≤ k ≤ p−1. [0, x]∩C_{y^{k}} est l’ensemble des z qui s’écrivent λ ∑_{i} x_{i}e_{i} avec 0 ≤ λ ≤ 1 et

∀i ∈ [1, n], y_{i}^{k} ≤ λx_{i} ≤ y_{i}^{k} + 1

Il est par hypothèse non vide, c’est un segment. Prenons z_{k+1} = λ_{k} ∑_{i} x_{i}e_{i} sa borne où λ_{k} est maximum. x est non nul, donc il existe un j tel que

λ_{k} = \frac{y_{j}^{k} + 1}{x_{j}} = inf_{i|x_{i}≠0}\{\frac{y_{i}^{k} + 1}{x_{i}}\}

Soit maintenant y^{k+1} = y^{k} + ej. On a alors

∀i ∈ [1, n], y_{i}^{k+1} ≤ λ_{k}x_{i} ≤ y_{i}^{k+1} + 1 et z^{k+1} appartient donc au cube C_{y^{k+1}}.

Les points z^{k+1} et y^{k+1} sont donc correctement construits. Enfin, si k = p − 1, y^{p} = x, car y^{p} ⪯ x et ∥y^{p}∥_{1} = p = ∥x∥_{1}, et on prend z^{p} = 0.

Soit maintenant y^{′k} = z^{k} − y^{k}. On a alors :

∀i, 0 ≤ y_{i}^{′k} ≤ 1

donc, si (Ay^{k})_{i} désigne la i^{eme} coordonnée de Ay^{k} :

| (Ay^{k})_{i} | = | (Az^{k})_{i} − (Ay^{′k})_{i} | = | (Ay^{′k})_{i} |

Comme 0 ≤ y_{i}^{′k} ≤ 1, il y donc au plus ∑_{j} | a_{ij} | + 1 valeurs possibles pour (Ay^{k})_{i} et donc au plus B_{0} vecteurs Ay^{k} distincts.

Supposons maintenant p > B_{0} . Il existe alors (lemme des tiroirs) i et j, i > j > 0 avec Ay^{i} = Ay^{j}. Soit z = y^{i} − y^{j}. On a alors Az = 0. De plus on a 0 ≺ z ≺ x, et z ∈ M. Donc x ∉ H(M).

□

2.2 Seconde borne

Soient r le rang de A, a_{ij} son terme de ligne i et de colonne j, et ∥A∥_{1} = ∑_{i,j} | a_{ij} |. Soit D la plus grande valeur absolue des mineurs de A. [J.L.Lambert 87] donne le résultat suivant :

Théorème 2 (Lambert)

∥M∥_{∞} ≤ nD

Reprenant ce résultat, ainsi que celui de [A.Koscielski et L.Pacholski 90], aussi inspiré de [J.L.Lambert 87], nous obtenons les améliorations suivantes :

Théorème 3 Soit D_{r} la plus grande valeur absolue des mineurs d’ordre r de A .

∥M∥_{∞} ≤ (n − r)D_{r} = B_{1}

d’où

∥M∥_{∞} ≤ (n − r) (\frac{∥A∥_{1}}{r} )^{r} = B_{2}

Preuve :

Soit C le cône de R^{n} des solutions réelles positives de Ax = 0. Soient C_{j} ses intersections avec les hyperplans d’équations x_{j} = 0. Il est clair que C est l’enveloppe convexe de la réunion des cônes C_{j}. On peut récursivement appliquer cette décomposition de C aux C_{j}, tant que la dimension des cônes construits est plus grande que 1. C est alors l’enveloppe convexe de la réunion de ces cônes de dimension 1, dits “arêtes” de C.

Chacune de ces arêtes est alors l’ensemble des solutions positives d’un système d’équations obtenues en choisissant r équations indépendantes de Ax = 0, et en leur ajoutant n − r − 1 équations du type x_{j} = 0 de manière à garder le système de rang maximum, i.e. n − 1.

On peut alors obtenir des vecteurs directeurs (à coefficients entiers naturels) des arêtes en calculant les n mineurs d’ordre n − 1 pour chacun systèmes précédents, ce qui revient à calculer des mineurs d’ordre r de A.

Soient g_{1},…, g_{k} ces vecteurs, qui ont donc leurs coordonnées majorées en valeur absolue par D_{r}.

M est alors inclus dans le cône positif qu’ils engendrent (leurs combinaisons linéaires à coefficients réels positifs), qui n’est autre que C, de dimension au plus n − r. On a donç grâce au théorème de Carathéodory :

Ax = 0, x ≥ 0 ⟹ ∃j_{1},…, j_{n−r}, ∃α_{1},…, α_{n−r} ≥ 0, x = ∑_{l=1}^{n−r} α_{i}g_{j_{i}}

Si maintenant x est minimal, il est clair que les α_{i} sont strictement plus petits que 1. On obtient donc la première partie du théorème. La seconde partie est une majoration simple du déterminant d’une sous-matrice carrée A′ d’ordre r de A :

| det(A′) | ≤ ∏_{j} ∑_{i} | a′_{ij} | ≤ (\frac{∑_{i,j} | a′_{ij} |}{r})^{r} ≤ (\frac{∥A∥_{1}}{r} )^{r}

□

La borne B_{1} peut être optimale , comme on le verra sur des exemples, mais elle n’est pas raisonnablement calculable en pratique: vaut-il mieux calculer tous les mineurs principaux de A que de directement calculer H(M), par exemple avec l’algorithme de [E.Contejean et H.Devie 89] qui n’utilise pas de borne de H(M)?

2.3 Comparaison de B_{0}, B_{1} et B_{2}

Il est clair que ces trois bornes sont simple exponentielles en la taille de A. Les exemples suivants montrent qu’on ne peut comparer en général les la première et la derniére, la seconde pouvant être optimale, mais étant incalculable en pratique. On étudiera les comportements des rapports \frac{B_{2}}{B_{0}} (bornes de ∥x∥_{∞}) et \frac{nB_{2}}{B_{0}} (bornes de ∥x∥_{1}), lorsque n ou ∥A∥_{∞} tendent vers l’infini.

2.3.1 Exemple 1

Soient a un entier supérieur ou égal à 3 et A la matrice

( \begin{matrix}a & 1 − a \\ & ... & ... \\ & & a & 1 − a \end{matrix} )

où les coefficients non écrits sont nuls. On a r = m = n − 1 et H(M) n’a qu’un élement : ((a − 1)^{n−1}, a(a − 1)^{n−2},…, a^{n−1}). Ainsi :

∥M∥_{∞} = B_{1} = a^{n−1}, ∥M∥_{1} = a^{n} − (a − 1)^{n}, B_{2} = (2a − 1)^{n−1}, B_{0} = (2a)^{n−1}

B_{1} est donc optimale, B_{2} et B_{0} étant très proches. Asymptotiquement, on a enfin :

lim_{n→∞} \frac{B_{2}}{B_{0}} = 0, lim_{n→∞} \frac{nB_{2}}{B_{0}} = 0, lim_{a→∞} \frac{B_{2}}{B_{0}} = 1, lim_{a→∞} \frac{nB_{2}}{B_{0}} = ∞

2.3.2 Exemple 2 : matrices carrées magiques

Une matrice carrée est dite magique si les sommes de ses coefficients d’une ligne ou d’une colonne sont toutes égales. Les matrices carrées magiques d’ordre k à coefficients positifs sont donc les solutions positives du système Ax = 0, où n = k^{2} + 1, m = 2k et :

A = ( \begin{matrix}1 & … & 1 & & & & & −1 \\ & & & 1 & … & 1 & & −1 \\ & & & & & & ... & ⋮ \\ 1 & & & 1 & & & & −1 \\ & ... & & & ... & & … & ⋮ \\ & & 1 & & & 1 & & −1 \end{matrix} )

où les coefficients non écrits sont nuls. On a r = 2k − 1. La base de Hilbert de M est l’ensemble des matrices de permutations d’ordre k (cf [R.P.Stanley 83]). Ainsi :

∥M∥_{∞} = 1, ∥M∥_{1} = k + 1, B_{1} ≥ k^{2} − 2k + 2

B_{2} = (k^{2} − 2k + 2) (\frac{2k(k + 1)}{2k − 1})^{2k−1} , B_{0} = (k + 2)^{2k−1}

et :

lim_{n→∞} \frac{B_{2}}{B_{0}} = ∞, lim_{n→∞} \frac{nB_{2}}{B_{0}} = ∞

ce qui donne un comportement inverse de l’exemple précédent.

3 Algorithmes

Le sujet de cette section est le calcul de tous les éléments de H(M). Les premiers algorithmes ont été basés sur la borne de [G.Huet 78] puis celle de [J.L.Lambert 87] valables pour une équation, extensibles au cas d’un système, mais donnant des bornes double exponentielles. Ces bornes sont les suivantes :

Propriété 1 Soit x = (x_{1},…, x_{p}, y_{1},…, y_{q}) un élément de la base de Hilbert de l’équation

a_{1}x_{1} + … + a_{p}x_{p} + b_{1}y_{1} + … + b_{q}y_{q} = 0.

où les a_{i} sont positifs et les b_{j} sont négatifs. Alors :

∀i, | x_{i} | ≤ sup_{j}| b_{j} |

(Huet)

∑_{i} x_{i} ≤ sup_{j}| b_{j} |

(Lambert). (la partie concernant les y_{j} est symétrique).

H(M) est alors obtenue par énumération sous la borne, et dans le cas de plusieurs équations, on itère la méthode en injectant les solutions des équations précédentes dans la suivantes (après avoir éventuellement triangularisé la matrice A). Dans le cas de deux équations [J.F.Romeuf 89] donne une méthode originale pour construire un automate fini énumérant H(M), et une borne quadratique dans ce cas.

3.1 Algorithme de Contejean-Devie

[E.Contejean et H.Devie 89] ont trouvé un algorithme élégant ne nécessitant pas de borne de H(M). Le principe est le suivant. Ordonnons N^{n}par l’ordre ⪯ précédemment défini, ce qui nous donne un DAG (graphe acyclique) de racine 0. L’algorithme parcourt une partie de ce DAG en profondeur de la manière suivante : on commence par 0, et si on se trouve sur un vecteur x non nul tel que pour aucun de ses ancêtres y on ait A(x − y) = 0, on ne visite que ses fils x + e_{j} (e_{j} est le j^{ieme} élement de la base canonique de Z^{n}) vérifiant Ax.Ae_{j} ≤ 0 (le . désignant le produit scalaire de R^{n}). Cet algorithme a la surprenante propriété de terminer et d’être complet. En s’arrangeant pour ne pas visiter deux fois un noeud du DAG, et en ne retenant que les solutions minimales pour ⪯, on obtient H(M). Le seul résultat de complexité sur cet algorithme est, à notre connaissance, une conséquence de [L.Baratchart et L.Pottier 89], qui donne une borne double exponentielle sur le nombre de noeuds visités. Cet algorithme se comporte bien en pratique, mais est coûteux si les éléments de H(M) sont de grande norme.

3.2 Un algorithme inspiré du théorème 3

L’examen de la preuve du théorème 1 permet de modifier la méthode de l’algorithme de [E.Contejean et H.Devie 89] en se limitant à n’incrémenter un x que par les e_{l} tels que pour tout i, la i-ème coordonnée de A(x + e_{l}) soit comprise entre − ∑_{j} a_{ij}^{−} et ∑_{j} a_{ij}^{+}. Les générateurs sont alors tous obtenus comme points des suites strictement croissantes construites similairement à l’algorithme précédent.

3.3 Utilisation des bases standard

On donne ici un algorithme nouveau utilisant les bornes précédentes sur ∥M∥_{∞} et ∥M∥_{1}, basé sur la théorie des bases standard (ou de Gröbner). L’idée est de voir les colonnes de A comme les exposants de monômes à m variables, et les solutions de Ax = 0 dans Z^{n}commes des sisygies relatives à ces monômes. Un calcul de base standard approprié (par un algorithme de complétion semblable à celui de [B.Buchberger 83]) donne un système de réécriture canonique dont l’inverse énumère M par norme croissante . Il suffit alors de ne retenir que les solutions minimales pour ⪯ et de norme inférieure à inf{nB_{2}, B_{0}}. Soient X_{1},…, X_{m}, Y_{1},…, Y_{n}, n + m variables, et k un corps quelconque. On note a_{j} la j^{eme} colonne de A. Pour tous α ∈ Z^{m} et β ∈ Z^{n} , on note X^{α} et Y^{β} les monômes X_{1}^{α_{1}} … X_{m}^{α_{m}} et Y_{1}^{β_{1}} … Y_{n}^{β_{n}}. α^{+} est le sup de α et de zéro (pour l’ordre partiel ⪯), et α^{−} est le sup de −α et zéro. Ainsi α = α^{+} − α^{−}. Pour tout j ∈ [1, n], on définit un polynôme P_{j} de l’anneau R = k[X_{1},…, X_{m}, Y_{1},…, Y_{n}] :

P_{j} = X^{a_{j}^{+}} − Y_{j}X^{a_{j}^{−}}

Soit I l’idéal de R engendré par les P_{j} et J sa trace sur l’anneau R′ = k[Y_{1},…, Y_{n}]. Soit maintenant BI la base standard réduite de I pour l’ordre suivant sur les monômes de R : on compare d’abord lexicographiquement sur les X_{i}, puis en cas d’égalité on utilise l’ordre du degré, et enfin l’ordre lexicographique. Soit BJ l’ensemble des polynômes de BI où les X_{i} n’apparaissent pas. BJ est alors une base standard de l’idéal J pour l’ordre du degré. De plus ses éléments sont des différences de monômes (car ceux de BI le sont). Ainsi soient Y^{α_{k}} − Y^{β_{k}} les éléments de BJ , k ∈ [1, p] et Y^{α_{k}} étant monôme dominant. Maintenant, notons ⟶ la relation de réécriture corespondant à la division des polynômnes par la base standard BJ , et ⟶^{∗} sa fermeture réflexive transitive. On écrit m1 ↓ m2 lorsque deux monômes m1 et m2 se réécrivent en un même monôme, ou de manière équivalente quand m1 − m2 ⟶^{∗} 0. Alors :

Propriété 2

∀x ∈ Z^{n} , Ax = 0 ⟺ Y^{x^{+}} − Y^{x^{−}} ∈ I ⟺ Y^{x^{+}} ↓ Y^{x^{−}}

Preuve :

Facile par raisonnement équationnel sur les équations Y_{j} = X^{a_{j}^{+}}X^{−a_{j}^{−}} dérivée des polynômes P_{j}, et en utilisant la proriété fondamentale des bases de Gröbner. □

En conséquence :

Propriété 3

∀x ∈ N^{n} , x ∈ M ⟺ Y^{x} ⟶^{∗} 1

Cette derniére propriété permet de tester si M est non réduit à {0} :

Théorème 4 Le système Ax = 0 a une solution positive non nulle si et seulement si il existe dans BI un polynôme de la forme Y^{α} − 1.

On a de plus une représentation effective de M avec des règles de réécriture : Soit SR_{M} le système de règles de réécriture de monômes obtenues en inversant les polynômes de BJ :

SR_{M} = {Y^{β_{1}}⟶Y^{α_{1}},…, Y^{β_{p}}⟶Y^{α_{p}}}

Notons ⟶_{i} sa relation de réécriture (c’est la symétrique de ⟶, et elle n’est pas noethérienne). Alors

x ∈ M ⟺ 1 ⟶_{i}^{∗} Y^{x}

On peut donc engendrer tous les éléments de M en explorant l’arbre des réécritures de 1 par ⟶_{i}, et obtenir H(M) en ne gardant que les éléments minimaux, et de degré inférieur aux bornes nB_{2} et B_{0} (cette méthode est complète car ⟶_{i} fait croître les degrés des monômes, donc les normes ∥.∥_{1} des solutions). Plus précisément :

Théorème 5 L’algorithme suivant s’arrête et retourne H(M) :

1. E := {1}

2. Tant que ∃x ∈ E, y ∉ E, avec x ⟶_{i} y, et deg(y) ≤ inf{nB_{2}, B_{0}}

Faire E := E ∪ {y}

3. Rendre H(M) := éléments minimaux pour ⪯ des vecteurs d’exposants des monômes de E − {1}.

3.4 Comparaisons

4 Application à Ax ≤ b

Revenons maintenant au problème initial, i.e. la résolution d’un système Ax ≤ b. Soit C l’ensemble de ses solutions dans Z^{n}. Alors :

Corollaire 1 Il existe deux parties finies C_{1} et C_{2} de Z^{n} telles que :

x ∈ C ⇔ x = x_{1} + x_{2} + … + x_{k}, avec x_{1} ∈ C_{1}, et x_{2},…, x_{k} ∈ C_{2}

et

∀x ∈ C_{1} ∪ C_{2}, ∥x∥_{1} ≤ (2 + ∥A∥_{1,∞} + ∥b∥_{∞})^{r}

Preuve :

On va se ramener à des systèmes d’équations homogènes à résoudre dans N.

Soit une ψ un endomorphisme de R^{n} qui ne fait que changer le signe de certaines coordonnées de son argument, et ψ(A) la matrice obtenue en changeant de signe les colonnes correspondantes de A. Soient y = (y_{1},…, y_{m}) un vecteur de m nouvelles variables, z une dernière variable, t le vecteur obtenu en concaténant x, y,et z, et ϕ la projection envoyant t sur x. Soit A′ la matrice obtenue en concaténant ψ(A), l’identité d’ordre m et l’opposé de b. On a alors clairement l’équivalence :

Ax ≤ b ψ(x) ∈ N^{n} ⟺ ∃t ∈ N^{n+m+1}, A′t = 0, z = 1, x = ψ(ϕ(t))

De plus rang(A′) = rang(A), et ∥A′∥_{1,∞} ≤ ∥A∥_{1,∞} + 1 + ∥b∥_{∞}.

Soient H la base de Hilbert de A′t = 0, et C_{1}^{ψ} (resp. C_{2}^{ψ}) l’image par ϕ des éléments de H tels que z = 1 (resp. z = 0).

On prend alors C_{1} (resp. C_{2}) égal à la réunion des C_{1}^{ψ} (resp. C_{2}^{ψ}) pour les 2^{n} choix possibles de ψ. Comme ∥ψ(x)∥_{1} = ∥x∥_{1} et ∥ϕ(t)∥_{1} ≤ ∥t∥_{1}, la deuxième partie du résultat s’en suit. □

Références

[L.Baratchart et L.Pottier 89] “Un résultat sur les systèmes d’addition de vecteurs”, manuscrit, INRIA Sophia Antipolis, France, fév. 1989.

[I.Borosh et L.B.Treybig 76] “Bounds of non-negative integral solutions of linear diophantine equations”, Proc. AMS v.55, n.2, mars 1976.

[B.Buchberger 83] “Gröbner basis: an algorithmic method in polynomial ideal theory” Camp. Publ. Nr. 83-29. 0, nov. 1983.

[E.Contejean et H.Devie 89] “Solving systems of linear diophantine equations”, UNIF’89, proc. of the third international Workshop on unification, Lambrecht, RFA 89.

[F.Giles et W.R.Pulleyblank 79] “Total dual integrality and integer polyedra” Linear algebra and its applications, 25, pp191-196, 1979.

[G.Huet 78] “An algorithm to generate the basis of solutions to homogeneous linear diophantine equations”, Information Processing Letters, vol.3, No.7, 1978.

[A.Koscielski et L.Pacholski 90] “Exponent of periodicity of minimal solutions of word equations”, manuscrit, Université de Wroclaw, Pologne, juin 90.

[J.L.Lambert 87] “Une borne pour les générateurs des solutions entières positives d’une équation diophantienne linéaire.” Comptes Rendus de l’Académie des Sciences de Paris, t.305, Série I, pp39-40, 1987.

[J.L.Lambert 87] “Un problème d’accessibilité dans les réseaux de Petri” Thèse de doctorat, théorème I.5., p 18, Université de Paris-Sud, Orsay, 1987.

[L.Pottier 90] “Bornes et algorithmes de calcul des générateurs des solution de systèmes diophantiens linéaires”, note aux Comptes Rendus de l’Académie des Sciences de Paris, septembre 1990.

[J.F.Romeuf 89] “Solutions of a linear diophantine system”, UNIF’89, proc. of the third international Workshop on unification, Lambrecht, RFA 89.

[R.P.Stanley 83] “Combinatorics and commutative algebra”, Progress in Mathematics, Birkäuser ed., 1983.

[L.B.Treybig 75] “Bounds in piecewise linear topology”, Trans.AMS, v.201, 1975.

[J.Von zur Gathen et M.Sieveking 78] “A bound on solutions of linear integer equalities and inequalities” Proc. AMS 72, pp155-158, 1978.