Une approche informatique pour l’approximation diophantienne Projet de Note au CRAS

Teresa Krick et Luis Miguel Pardo

Résumé – A l’aide d’outils informatiques nous décrivons une nouvelle méthode pour estimer la hauteur et le degré des polynômes qui apparaissent dans des formules de division bezoutienne et d’intersection complète.

A Computer Science approach to Diophantine Approximation

  This paper is published in
  C. R. Acad.  Sci.  Paris, 318 (1) pages 407--412, 1994.

Abstract – Based on tools from Computer Science we exhibit a new method for the estimation of heights and degrees of polynomials which appear in the division formulas of different Nullstellensaetze.

Abridged English Version. — In this note, we emphasize on a method more than on results : we apply the notion of “non-scalar straight line program” out of its usual domain (algebraic complexity theory) to provide very recent results in diophantine approximation and arithmetic intersection theory. By means of this method we obtain, in an elementary and self-contained way, some results of arithmetic division expressed in terms of non-scalar straight line programs (cf. Theorem 2 below) which lead to bounds for division in complete intersections (Theorem 1) also due to M.Elkadi ([5]) and allow to reobtain as Corollary the arithmetic Bezout identities of [4] and [1].

Let us fix some notations : we denote as usual by ZZ[X_{1}, …, X_{n}] and 0 Q[X_{1}, …, X_{n}] the rings of integer and rational polynomials in n indeterminates, and by deg F the total degree of a polynomial F belonging to these rings. Also, we set H(c) for the height (absolute value) of an integer c ∈ ZZ and H(F) for the maximal height of all the coefficients of a polynomial F ∈ ZZ[X_{1}, …, X_{n}].

First we state the mathematical results we obtain by means of this method :

Theorem 1. — (See also [5].) Let F_{1}, …, F_{s} ∈ ZZ[X_{1}, …, X_{n}] be polynomials of degrees and heights bounded by d ≥ n and H respectively which define a regular sequence in 0 Q[X_{1}, …, X_{n}], and let F ∈ ZZ[X_{1}, …, X_{n}] be a polynomial belonging to the ideal (F_{1}, …, F_{s}). Then there exist an integer c ∈ ZZ \ {0} and polynomials A_{1}, …, A_{s} ∈ ZZ[X_{1}, …, X_{n}] of degrees bounded by (d^{s} deg F)^{O(1)} such that :

– c F = A_{1} F_{1} + ⋯ + A_{s} F_{s} ,

– max{ log_{2} H(c), log_{2} H(A_{1}), …, log_{2} H(A_{s}) } ≤ (d^{s} deg F)^{O(1)} log_{2} H.

A Bertini’s reduction allows now to recover the following result, originally due to [4] and [1] :

Corollary. — Let F_{1}, …, F_{s} ∈ ZZ[X_{1}, …, X_{n}] be polynomials of degrees and heights bounded by d ≥ n and H respectively without any common zero in C^{n}.Then there exist c ∈ ZZ \ {0} and A_{1}, …, A_{s} ∈ ZZ[X_{1}, …, X_{n}] of degrees bounded by d^{O(n)} such that :

– c = A_{1} F_{1} + ⋯ + A_{s} F_{s} ,

– max{log_{2} H(c), log_{2} H(A_{1}), …, log_{2} H(A_{s})} ≤ d^{O(n)}s(log_{2} s + log_{2} H).

Finally, we give an intuitive definition of the meaning of “non-scalar straight line program” in order to state our somewhat technical result Theorem 2, which leads directly to Theorem 1.

A non-scalar straight line program is an algorithm which allows to compute the evaluation of a multivariate polynomial F ∈ ZZ[X_{1}, …, X_{n}] at any integer point, introducing if necessary some auxiliary integer elements called parameters. The size of the algorithm is measured taking linear ZZ− operations (with the parameters) for free, and its depth considers only the maximal number of intermediate polynomials recursively linked. We say that such a program produces a polynomial if it allows to evaluate it.

Theorem 2. — LetF_{1}, …, F_{s}, F ∈ ZZ[X_{1}, …, X_{n}] be polynomials in the conditions of Theorem 1. Then there exists a non scalar straight line program which produces from the coefficients of the polynomials F_{1}, …, F_{s} and F an integer c ∈ ZZ \ {0} and (the coefficients of) polynomials A_{1}, …, A_{s} ∈ ZZ[X_{1}, …, X_{n}] of degrees bounded by (d^{s} deg F)^{O(1)} such that :

– c F = A_{1} F_{1} + ⋯ + A_{s} F_{s}.

– The depth ℓ of the straight line program is bounded by O(s log_{2} d + log_{2} deg F).

– Its size L verifies the estimation (d deg F)^{O(n)}.

– The height of the parameters introduced is bounded by max{d^{O(s)}, H}.

Introduction. — Dans cette note, nous désirons mettre l’accent sur une méthode plutôt que sur des résultats : nous appliquons en dehors de son domaine habituel d’utilisation la notion de “calculs d’évaluation” (straight-line programs), classique dans la théorie de la complexité algébrique, pour retrouver des résultats actuels d’approximation diophantienne et d’intersection arithmétique. Plus précisément, l’application de cette méthode nous permet de montrer, de manière tout-à-fait élémentaire et autocontenue, un résultat de division arithmétique en intersections complètes (Théorème 1 ci-dessous), que M. Elkadi a aussi obtenu récemment par un procédé analytique ([5]), et de retrouver ainsi un énoncé sur les degrés et la hauteur dans des formules de division bezoutienne (Corollaire 2), dû à [4] et [1]. Notre travail consiste en fait en un développement ultérieur des techniques introduites dans [8] et [6] pour l’élimination effective en Calcul Formel, et ne fait appel qu’à quelques outils d’algèbre commutative élémentaire (sans aucun argument homologique), en plus de la notion mentionnée de straight-line programs (à cheval entre l’analyse numérique et l’informatique théorique). En ce sens, notre point de vue s’écarte des chemins usuels suivis en géométrie et approximation diophantiennes ([4], [1], [2], [3] et [5]). C’est peut-être pourquoi nous avons l’espoir que les fruits de cette méthode ne s’épuisent pas ici, et qu’elle permette de fournir de nouvelles applications dans le domaine de la géométrie diophantienne. Avant de procéder à la description de la méthode à laquelle nous faisons allusion, et des énoncés (pouvant sembler quelque peu techniques) qu’elle produit, nous allons signaler les deux résultats “plus mathématiques” qui en découlent. Fixons avant tout quelques notations simples: ZZ[X_{1}, …, X_{n}] et 0 Q[X_{1}, …, X_{n}] représentent les anneaux de polynônes en n indéterminées à coefficients dans l’anneau des entiers ZZ et le corps des nombres rationnels 0 Q respectivement. On indique par (F_{1}, …, F_{s}) l’idéal engendré par les polynômes F_{1}, …, F_{s} dans 0 Q[X_{1}, …, X_{n}]. Si c ∈ ZZ est un nombre entier, nous désignons par H(c) sa hauteur (ou valeur absolue); de la même manière, si F ∈ ZZ[X_{1}, …, X_{n}] est un polynôme à coefficients entiers, H(F) désigne la hauteur maximale des coefficients (entiers) de F. Nous notons aussi par deg F le degré total du polynôme F. Le premier résultat que nous énonçons maintenant concerne des bornes pour un problème de division en intersections complètes réduites.

Théorème 1. — (Voir aussi [5].) Soient F_{1}, …, F_{s} ∈ ZZ[X_{1}, …, X_{n}] des polynômes de degrés et de hauteur majorés respectivement par d ≥ n et H, qui forment une suite régulière dans 0 Q[X_{1}, …, X_{n}]. Soit F ∈ ZZ[X_{1}, …, X_{n}] un polynôme appartenant à l’idéal (F_{1}, …, F_{s}). Il existe alors un entier non nul c ∈ ZZ et des polynômes A_{1}, …, A_{s} ∈ ZZ[X_{1}, …, X_{n}] de degrés majorés par (d^{s} deg F)^{O(1)} tels que les conditions suivantes sont vérifiées :

– c F = A_{1} F_{1} + ⋯ + A_{s} F_{s} ,

– max{ log_{2} H(c), log_{2} H(A_{1}), …, log_{2} H(A_{s}) } ≤ (d^{s} deg F)^{O(1)} log_{2} H.

En opérant la réduction de [6] à l’aide d’une version effective du Théorème de Bertini, on retrouve le résultat suivant, montré initialement dans [4] et [1] :

Corollaire. — Soient F_{1}, …, F_{s} ∈ ZZ[X_{1}, …, X_{n}] des polynômes de degrés et de hauteur majorés respectivement par d ≥ n et H sans zéros communs dans C^{n}. Il existe alors c ∈ ZZ \ {0} et A_{1}, …, A_{s} ∈ ZZ[X_{1}, …, X_{n}] de degrés majorés par d^{O(n)} tels que :

– c = A_{1} F_{1} + ⋯ + A_{s} F_{s},

– max{ log_{2} H(c), log_{2} H(A_{1}), …, log_{2} H(A_{s}) } = d^{O(n)}(log_{2} s + log_{2} H) }.

Observons que le Corollaire entraîne directement des estimations de zéros pour l’approximation diophantienne de type Gelf’ond (voir [4]).

Approche informatique par des calculs d’évaluation. —Pour certains polynômes qui sont usuels dans les applications mathématiques, il est souvent plus économique de les évaluer que de passer naïvement à leur écriture dense (c’est-à-dire, à l’écriture sous forme de vecteur complet des coefficients qui accompagnent les monômes). Un exemple classique de cette observation est donné par le déterminant d’une matrice d’ordre n: pour l’écrire, on a besoin de n! sommes de produits de n termes, i.e O(n^{\frac{n}{2}} ) opérations, pour l’évaluer seulement de l’ordre de n^{3} opérations. Nous nous restreindrons dans la suite à des calculs d’évaluation qui ne font pas intervenir de divisions : un calcul d’évaluation (straight-line program) sans divisions dans ZZ[X_{1}, …, X_{n}] est une liste finie de polynômes de ZZ[X_{1}, …, X_{n}] (les résultats intermédiaires) telle que tout polynôme de la suite est ou bien une variable X_{1}, …, X_{n}, ou bien un élément de l’anneau ZZ (paramètre), ou bien la somme, la différence ou le produit de deux polynômes antérieurs de la liste. Nous renvoyons à [7] et [9] pour plus de précisions sur cette notion. Du point de vue de la croissance des résultats intermédiaires, les étapes du calcul d’évaluation correspondant à des opérations ZZ−linéaires ne jouent pas le même rôle que celles faisant intervenir des multiplications essentielles (non-scalaires). De même, il est important de contrôler aussi le nombre de polynômes de la liste enchaînés récursivement par des opérations (profondeur du calcul). Pour considérer ces situations, on introduit la présentation suivante (dite non-scalaire) du calcul d’évaluation :

Définition. — Fixons n, ℓ ∈ IN et \underline{L} = (L_{0}, L_{1}, …, L_{ℓ}) ∈ IN^{ℓ+1}. Dans le modèle de complexité non-scalaire, on donne un calcul d’évaluation (sans divisions) en n variables, de profondeur ℓ et de niveaux \underline{L} par un graphe acyclique orienté Γ(n, ℓ, \underline{L}) à n + 1 nœuds d’entrée 1, X_{1}, …, X_{n} (nœuds de profondeur ou de niveau 0) et où, à chaque nœud Q_{i,j}, 0 < i ≤ ℓ, 1 ≤ j ≤ L_{i} de niveau i, correspond l’opération suivante:

Q_{i,j} = (  ∑_{r≤i−1,1≤s≤L_{r}} a_{i,j}^{r,s} Q_{r,s}).(  ∑_{r′≤i−1,1≤s′≤L_{r′}} b_{i,j}^{r′,s′} Q_{r′,s′}).

Ici \underline{a} := (a_{i,j}^{r,s}), \underline{b} := (b_{i,j}^{r′,s′}) sont les paramètres de l’anneau ZZ introduits au cours du calcul.

Cette écriture exprime tout simplement le fait qu’à chaque niveau de profondeur i un nœud s’obtient comme le produit de deux combinaisons linéaires d’un nombre arbitraire de nœuds de niveaux précédents. Les combinaisons ZZ−linéaires sont alors considérées comme étant gratuites, ne comptant que les multiplications essentielles. Le graphe correspondant Γ(n, ℓ, \underline{L}) est de profondeur ℓ, possède L_{i} nœuds à chaque niveau i, 0 ≤ i ≤ ℓ et est donc de taille L := L_{1} + … + L_{ℓ}. Chaque résultat intermédiaire Q_{i,j} est un polynôme en les paramètres (\underline{a}, \underline{b}) et en les variables X_{1}, ⋯, X_{n} à coefficients dans ZZ. Le degré du polynôme Q_{i,j} par rapport aux variables X_{1}, ⋯, X_{n} est majoré par 2^{i} (et est indépendant de j). On peut donc écrire :

Q_{i,j} = ∑_{|μ|≤2^{i}} Q_{i,j}^{μ}X_{1}^{μ_{1}} … X_{n}^{μ_{n}}.

où Q_{i,j}^{μ} sont des polynômes en les paramètres (\underline{a}, \underline{b}) et à coefficients dans ZZ et μ := (μ_{1}, …, μ_{n}). Un examen minutieux du calcul d’évaluation donné par Γ(n, ℓ, \underline{L}) permet de contrôler les degrés et les hauteurs des polynômes Q_{i,j}^{μ} en les paramètres (\underline{a}, \underline{b}). On obtient deg Q_{i,j}^{μ} ≤ 2^{i+1} − 2 et H(Q_{i,j}^{μ}) ≤ 2^{(i+1)2^{i−1}n}L^{2^{i}−2}. Si, d’autre part, les paramètres (\underline{a}, \underline{b}) introduits dans le calcul sont tous de hauteur majorée par H, on observe la croissance suivante :

H(Q_{i,j}^{μ}(\underline{a}, \underline{b})) ≤ 2^{(i+1)2^{i−1}n}L^{2^{i}−2}H^{2^{i+1}−2}.

Nous sommes maintenant en conditions de formuler le résultat principal de cette note, qui implique le Théorème 1 ci-dessus.

Théorème 2. — Soient F_{1}, …, F_{s} ∈ ZZ[X_{1}, …, X_{n}] des polynômes de degrés et de hauteur majorés respectivement par d ≥ n et H, qui forment une suite régulière dans 0 Q[X_{1}, …, X_{n}]. Soit F ∈ ZZ[X_{1}, …, X_{n}] un polynôme appartenant à l’idéal (F_{1}, …, F_{s}). Il existe alors un calcul d’évaluation non-scalaire Γ qui produit à partir des coefficients des polynômes F_{1}, …, F_{s} et F un entier non nul c ∈ ZZ et des polynômes A_{1}, …, A_{s} ∈ ZZ[X_{1}, …, X_{n}] de degrés majorés par (d^{s} deg F)^{O(1)} tels que les conditions suivantes sont vérifiées :

– c F = A_{1} F_{1} + ⋯ + A_{s} F_{s}.

– La profondeur ℓ du calcul d’évaluation Γ est majorée par O(s log_{2} d + log_{2} deg F).

– Sa taille L vérifie l’estimation L ≤ (d deg F)^{O(n)}.

– La hauteur des paramètres entiers introduits dans Γ est majorée par max{d^{O(s)}, H}.

La preuve complète de ce théorème se trouve dans [11]; elle s’obtient récursivement à partir du lemme de division suivant, après une préparation adéquate obtenue grâce à une réduction à la Bertini et un procédé de normalisation au sens de Noether :

Lemme. — Soient F_{1}, …, F_{n−i} et G ∈ ZZ[X_{1}, …, X_{n}] des polynômes de degrés majorés par d ≥ n. Supposons que les polynômes F_{1}, …, F_{n−i} forment une suite régulière dans 0 Q[X_{1}, …, X_{n}] et engendrent un idéal radical I, et que G n’est pas un diviseur de zéro modulo I. Supposons de plus que les variables X_{1}, …, X_{n} se trouvent en position normale de Noether par rapport à l’idéal I, c’est-à-dire que l’extension d’anneaux 0 Q[X_{1}, …, X_{i}] ↪ 0 Q[X_{1}, …, X_{n}]/I est entière. Soit F ∈ ZZ[X_{1}, …, X_{n}] un polynôme tel que G divise F modulo I. Posons R := ZZ[X_{1}, …, X_{i}], et désignons par deg^{o}F le degré du polynôme F par rapport aux variables X_{1}, …, X_{i} et par deg^{∗}F son degré par rapport aux variables X_{i+1}, …, X_{n}. Il existe alors un calcul d’évaluation non-scalaire Γ qui produit à partir des coefficients des polynômes F_{1}, …, F_{n−i}, G et F, en tant que polynômes de R[X_{i+1}, …, X_{n}], un polynôme ρ ∈ R et les coefficients dans R d’un polynôme A ∈ R[X_{i+1}, …, X_{n}] tels que les conditions suivantes sont vérifiées :

– ρ F ≡ A G (mod I) et ρ divise A dans 0 Q[X_{1}, …, X_{n}].

– Le degré de A par rapport aux variables X_{i+1}, …, X_{n} est majoré par (n−i) (d−1), et son degré par rapport aux variables X_{1}, …, X_{i} par deg^{o}F + (1+deg^{∗}F +deg G)d^{O(n−i)}.

– La profondeur ℓ du calcul d’évaluation Γ est majorée par O((n−i) log_{2} d+log_{2}(deg F)).

– Sa taille L vérifie l’estimation L ≤ (d deg^{∗}F)^{O(n−i)}.

– La hauteur des paramètres entiers introduits dans Γ est majorée par d^{O(n−i)}.

Esquisse de la preuve. — Tous les polynômes sont ici considérés comme étant à coefficients dans R. Le calcul d’évaluation Γ produit plus précisément le polynôme ρ ∈ R et une matrice M formée d’éléments de R qui transforme linéairement les coefficients du polynôme F en les coefficients du polynôme A. Les entrées de Γ sont les coefficients des polynômes F_{1}, …, F_{n−i} et G, le rôle de F étant représenté seulement par son degré en X_{i+1}, …, X_{n}. Un premier aspect de la preuve consiste à remplacer les polynômes par les matrices des endomorphismes de multiplication qu’ils définissent dans 0 Q(X_{1}, …, X_{i})[X_{i+1}, …, X_{n}]/I par rapport à une base convenablement choisie. L’élection de cette base, ainsi que le calcul des matrices de multiplication, se fait suivant les procédés introduits dans[8] (à l’aide du calcul d’un élément primitif). On applique ensuite la théorie de la dualité pour les algèbres Gorenstein ([12]), et on calcule une trace au moyen d’un déterminant pseudo-jacobien, d’après les méthodes développées dans [6]. Les bornes sur la profondeur du calcul d’évaluation Γ s’obtiennent d’un examen minutieux de ces procédures du point de vue non-scalaire; on remarque aussi que les seuls paramètres introduits dans Γ proviennent de l’utilisation de techniques contrôlées d’interpolation ([10]) et sont de hauteur bornée par d^{O(n−i)}.

Récursion finale pour la preuve du Théorème. — On effectue préalablement la préparation nécessaire de l’idéal (F_{1}, …, F_{s−1}) pour le placer dans les conditions du Lemme, à l’aide d’une réduction à la Bertini et d’une mise en position au sens de Noether. Après cela, dans la première étape on applique le lemme pour l’idéal (F_{1}, …, F_{s−1}) et les polynômes F^{(1)} := F, G^{(1)} := F_{s}; on considère ensuite l’idéal (F_{1}, …, F_{s−2}) et théoriquement les polynômes F^{(2)} := F^{(1)} − \frac{A^{(1)}}{ρ^{(1)}} G^{(1)} et G^{(2)} := F_{s−1}, et ainsi successivement. Les bornes annoncées proviennent essentiellement du fait qu’à l’étape i (correspondant à l’idéal (F_{1}, …, F_{s−i})) la profondeur du calcul est majorée par le degré (contrôlé) en les variables X_{n−(s−i)+1}, …, X_{n} du dividende F^{(i)}, et que les divisions en principe nécessaires pour éviter de traîner les polynômes parasites ρ^{(i)} se regroupent en une seule division à la fin de la procédure (il est clair que tous ces calculs théoriques dans 0 Q[X_{1}, …, X_{n}] se font dans ZZ[X_{1}, …, X_{n}] modulo un dénominateur commun c). On fini en applicant une technique d’évitation des divisions avec des paramètres de hauteur controlée.

Références Bibliographiques

[1] C.Berenstein et A.Yger, Effective Bezout identities in 0 Q[z_{1}, …, z_{n}], Acta Math., 166, 1991, p. 69-120.

[2] J.-B.Bost, H.Gillet et C.Soulé, Un analogue arithmétique du théorème de Bézout, C.R.Acad.Sci. Paris, 312, Série I, 1991, p. 845-848.

[3] J.-B.Bost, H.Gillet et C.Soulé, Heights of projective varieties and positive Green forms, Manuscrit IHES, 1993.

[4] D.Brownawell, Local diophantine Nullstellen inequalities, J. Amer.Math.Soc. 1, 1988, p. 311-322.

[5] M.Elkadi, Bornes pour le degré et les hauteurs dans le problème de division, A paraître dans Michigan Math. J., 1993.

[6] N.Fitchas, M.Giusti et F.Smietanski, Sur la complexité du théoréme des zéros, Manuscrit EcolePolytechnique, 1993.

[7] J.von zur Gathen, Parallel arithmetic computations: a survey, Proc.13th Symp. MFCS 1986, Springer LN Comput.Sci. 233, 1986, p. 93-112.

[8] M.Giusti et J.Heintz, La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, A paraître dans Proc.Int.Meeting on Commutative Algebra, Cortona, 1991.

[9] J.Heintz, On the computational complexity of polynomials and bilinear mappings, Proc.AAECC 5, Springer LNCS 356,1989, p. 269-300.

[10] J.Heintz et C.P.Schnorr, Testing polynomials which are easy to compute, Proc.12th Ann.ACM Symposium on Computing, 1980, p. 262-268.

[11] T.Krick et L.-M.Pardo, Heights and straight-line programs in the Nullstellensatz, Manuscrit Univ.Cantabria, 1993.

[12] E.Kunz, Kähler Differentials, Advanced Lectures in Mathematics, Vieweg Verlag, 1986.

T. K. : Instituto de Cálculo, Universidad de Buenos Aires,

1428 Buenos Aires, Argentine;

L.-M. P. : Dept. Matemáticas, Universidad de Cantabria, 39071 Santander,Espagne.