You are currently browsing the monthly archive for septembre 2014.

Si vous me passez cet anglo-germanisme si inhabituel de la part d’un patriote comme moi, j’aimerais vous parler un petit peu du combinatorial nullstellensatz (CNst) d’Alon, déjà évoqué brièvement sur ce blog. Hendrik Lenstra et un de ses élèves ont trouvé une application de ce théorème en théorie de Galois : ils ont mis au point un nouveau cheminement vers le théorème de la base normale.

Ce qu’on appelle habituellement CNst est l’énoncé suivant :
Soit F un corps, et P\in F[X_1,\cdots,X_n] non-nul ; supposons que cX_1^{i_1}\cdots X_n^{i_n} soit un terme (non-nul) de degré maximal dans P. Soit S_1,\cdots,S_n des parties de F vérifiant \text{card } S_k>i_k pour tout k. Alors il existe (s_1,\cdots,s_n)\in\prod S_i tel que P(s_1,\cdots,s_n)\neq 0.

Pour mémoire, le Nullstellensatz historique de Hilbert est le suivant :
Soit F un corps algébriquement clos, et g_1,\cdots, g_m des éléments de F[X_1,\cdots,X_n]. Soit f\in F[X_1,\cdots,X_n] qui s’annule en tout n-uplet où tous les g_i s’annule. Alors il existe des polynômes h_1,\cdots,h_m et un entier k tel que f^k=\sum h_ig_i.

Une reformulation plaisante passe par la notion de variété définie par un idéal. Soit I\subset F[X_1,\cdots,X_n] un idéal ; notons
V(I)=\{ x=(x_1,\cdots,x_n)\in F^n\mid \forall f\in I,\quad f(x)=0\}.
Réciproquement, si S\subset F^n, notons Z(S)=\{f\in F[X_1,\cdots,X_n]\mid \forall x\in S,f(x)=0\}. C’est bien sûr un idéal. La grande question est alors : est-ce que par hasard Z(V(I))=I ? Et la réponse est non… la vérité, dit le Nullstellensatz est que Z(V(I))=\text{Rad }I.

Cependant, il est dur de voir le rapport entre le vrai Nst et le CNst ; on se demande bien pourquoi Alon a choisi ce nom. Surtout que dans les applications, très nombreuses, et essentiellement combinatoires, du théorème d’Alon, F est presque toujours un corps fini, et les S_i sont d’ailleurs généralement égales à F : la fonction polynomiale associée n’est pas entièrement nulle.

En fait le rapport apparaît lorsque l’on déduit le CNst du lemme suivant, cousin du théorème de Hilbert : avec les notations précédentes, si m=n et chaque g_i dépend de la seule variable x_i et est scindé, unitaire (on écrit alors g_i=\prod_{s\in S_i}(X_i-s), et alors le lieu des zéros communs des g_i est \prod S_i), alors Z(V(I))=I, et ce même si le corps n’est pas algébriquement clos. Plus précisément, il existe des polynômes h_i tels que f=\sum h_ig_i avec \text{deg }h_i\leq \text{deg }f-\text{deg }g_i. Cerise sur le gâteau : si les g_i sont tous dans un même sous-anneau, les h_i peuvent être pris dans ce sous-anneau.

La preuve de ce lemme et du CNst est facile et courte, cf l’article original de Noga Alon, qui multiplie les applications convaincantes.

Une application qui lui a échappé est le théorème de la base normale. Il dit que si k\subset L est une extension galoisienne de corps de groupe de Galois G=\{g_1,\cdots,g_n\}, il existe \alpha\in L tel que g_i(\alpha) forme une base du k-ev qu’est L.

Le lemme qui permet au CNst de faire sa besogne ici est le suivant : soit k un corps algébriquement clos et A une k-algèbre de dimension finie, de dimension n. Alors il existe une base b_1,\cdots,b_n de A et un polynôme f\in k[X_1,\cdots,X_n] de degré au plus 1 en chaque variable, tel que pour tout x_1,\cdots,x_n, on ait
\sum x_ib_i \in A^{\ast} \longleftrightarrow f(x_1,\cdots,x_n)\neq 0.

Un autre lemme important est le suivant : soit S_k l’ensemble des polynômes en n variables dont le combinatorial nullstellensatz assure qu’ils ne sont pas entièrement nuls sur k^n. Si le corps est infini, c’est k[X_1,\cdots,X_n]\setminus\{0\}. S’il est fini de cardinal q=p^m, ce sont les polynômes qui ont un terme T de plus haut degré tel que pour tout i, deg_{X_i} T\leq q-1. Soit \phi\in GL_n(k). Alors \phi (S_k)=S_k.

Une fois ces lemme démontrés, on n’a pas de difficulté à conclure.

Dans un commentaire au post précédent, 2pac signalait un problème apparenté et fort classique : montrer que si k vecteurs e_1,\cdots,e_k existent dans \mathbb{R}^n avec \forall i\neq j\quad e_i\cdot e_j \prec 0 alors k\leq n+1. On dit qu’une telle famille est strictement obtusangle ; on peut reformuler ce qui précède en disant que le rang d’une famille strictement obtusangle est d’au moins son cardinal moins un. C’est classique pour un sup ou un spé et un corrigé se trouve ici : http://exo7.emath.fr/ficpdf/fic00130.pdf (c’est l’exercice 3).

Dans le même ordre idée, considérons une famille obtusangle, mais pas forcément strictement, i.e. e_1,\cdots,e_k dans \mathbb{R}^n tous non-nuls avec \forall i\neq j e_i\cdots e_j \leq 0. Quelle peut être la taille d’une telle famille ? On a déjà des exemples strictement obtusangles de taille n+1 mais peut-on faire mieux ? Oui facilement en fixant une BON e_1,\cdots,e_n et en prenant les \pm e_i, ce qui fait déjà 2n vecteurs.

Je prétends que k\leq 2n, et je le prouve. Je raisonne par récurrence sur n ; pour n=1 c’est évident. Supposons le résultat acquis pour toutes les dimensions jusqu’à n\succ 1 et fixons une famille obstusangle e_1,\cdots,e_k dans \mathbb{R}^{n+1}. Discutons selon la taille maximale \ell d’une sous-famille strictement obtusangle dans cette famille ; sans perte de généralité admettons que e_1,\ldots,e_{\ell} est strictement obtusangle. Si \ell=1, alors les produits scalaires sont deux à deux nuls ; autrement dit famille est forcément une BON donc ça taille ne dépasse pas n, qui est lui-même plus petit que 2n. En général, si \ell\geq 2, une telle sous-famille est de rang au moins \ell -1 ; soit E le SEV qu’elle engendre et F son orthogonal. Projetons orthogonalement les autres vecteurs de la famille obtusangle sur E : soit e'_i le projeté de e_i. Pour j\leq\ell, on a e'_i\cdot e_j=e_i\cdot e_j\leq 0.

Euh là j’ai cru que c’était forcément 0… en fait c’est certain quand le rang est \ell -1 et non l. Mais quand c’est \ell que dire…
On pourrait essayer de raisonner sur la taille maximale d’une famille strictement obtusangle de rang son cardinal moins un… mais c’est fumeux. Ce serait intéressant pour prouver que la taille d’une famille obtusangle sachant qu’elle contient une famille strictement obtusangle de taille k, rang k-1, est au plus 2(n+1)-k.

Une méthode plus sûre est la deuxième du lien indiqué, un peu adaptée. Donc encore par récurrence. C’est vrai en dimension un ; supposons acquis le résultat jusqu’à la dimension n et soit x_1,\cdots, x_p en dimension n+1. On prend les projetés orthogonaux sur l’orthogonal de x_p, qui forment à leur tour une famille obtus angle en dimension n. Donc y en a au plus 2n, donc p\leq 2n+1. Bizarre ! L’erreur, c’est qu’en fait il pourrait bien y avoir un projeté orthogonal nul… Mais seulement un, car il ne peut y avoir outre x_p qu’un seul vecteur x_i colinéaire à x_p, non-nul et ayant un ps négatif avec lui.

Au passage on voit, par récurrence, que les familles de taille maximale (2n) sont faites d’une base orthogonale et de n vecteurs négativement colinéaires.