summaryrefslogtreecommitdiffstats
path: root/chapitres/bases-groebner.tex
blob: abc964266bc3560b90802c3924009fcad6a962eb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
%%% Emacs: -*- mode:latex; coding:utf-8; -*-
\ifx\danslelivre\undefined
\documentclass[a4paper,9pt]{amsart}
\input{../config/preambule}
\input{../config/macros}
\title{Bases de Gröbner et applications}
\externaldocument{spectre}
\externaldocument{extensions-algebriques}
\externaldocument{calculs-galois}
\begin{document}
\maketitle
\tableofcontents
\else
\chapter{Bases de Gröbner et applications}
\begingroup
\fi

\DeclareMathOperatorWithFont{\initial}{\mathtextrm}{in}


\section{Bases de Gröbner}

\subsection{Motivations}\label{section-motivations-groebner}

\subsubsection{Le cas d'une seule variable} Les idéaux de l'anneau
$k[Z]$ des polynômes univariés sont bien compris puisque cet anneau
est principal : pour tout idéal $I$ de $k[Z]$, il existe un unique
polynôme $f$ unitaire ou nul tel que $I = (f)$.  De plus, on dispose
d'une base évidente du $k$-espace vectoriel $k[Z]/I$, à savoir les
monômes $1,Z,Z^2,\ldots,Z^{\ell-1}$ où $\ell$ est le degré de $f$ si
ce dernier n'est pas nul (pour $I = (0)$ on peut prendre tous les
$Z^i$ mais ce cas ne nous préoccupera guère).

Parmi les opérations algorithmiquement faciles à effectuer,
mentionnons notamment les suivantes :
\begin{itemize}
\item donné un idéal $I = (f_1,\ldots,f_r)$ engendré par plusieurs
  éléments $f_i$ de $k[Z]$, écrire cet idéal sous la forme standard,
  c'est-à-dire $I = (f)$ avec $f$ unitaire (il suffit de prendre pour
  $f$ le pgcd de $f_1,\ldots,f_s$, ce qui se calcule avec l'algorithme
  d'Euclide) ; on pourra, de plus, explicitement convertir ce nouveau
  générateur $f$ en fonction des anciens, c'est-à-dire trouver
  $g_1,\ldots,g_r$ tels que $f = g_1 f_1 + \cdots + g_r f_r$ (avec
  l'algorithme d'Euclide étendu) ;
\item une fois fixé $I = (f)$, et connaissant un $h \in k[Z]$, décider
  si $h \in I$ ou non ; si oui, trouver un $g$ tel que $h = g f$ ; si
  non, décomposer $h$ modulo $I$ dans la base choisie de $k[Z]/I$ (il
  suffit d'effectuer la division euclidienne de $h$ par $f$ et de
  considérer son quotient ou son reste selon le problème étudié) ;
\item effectuer les opérations algébriques dans l'anneau quotient
  $k[Z]/I$.
\end{itemize}

Si de plus on suppose qu'on sait effectuer la factorisation des
polynômes de $k[Z]$, on peut alors tester si $k[Z]/(f)$ est un
\emph{corps}, c'est-à-dire si $I = (f)$ est un idéal maximal, puisque
cela revient précisément à tester si $f$ est irréductible.  (Dans ce
cas, $k[Z]/(f)$ est, bien entendu, le corps de rupture de $f$ sur $k$,
c'est notamment pour pouvoir effectuer des calculs dans celui-ci que
la question algorithmique nous préoccupe.)

\subsubsection{} Toutes ces questions deviennent beaucoup moins
évidentes lorsqu'on a affaire à un anneau $k[Z_1,\ldots,Z_d]$ de
polynômes multivariés.  Les \textbf{bases de Gröbner}, parfois aussi
appelées \textbf{bases standard} (sous différentes variantes) ont pour
but notamment d'y répondre et, de façon générale, de fournir les
outils nécessaires à la manipulation algorithmique des idéaux de
$k[Z_1,\ldots,Z_d]$.

La clé de la définition des bases de Gröbner consiste à trouver un
concept multivarié analogue à celui de terme dominant (c'est-à-dire,
de plus haut degré) d'un polynôme univarié.  L'ordre de divisibilité
sur les monômes (cf. ci-dessous) ne fournit qu'un ordre partiel,
tandis que la seule comparaison du degré total ne fournit qu'un
préordre (deux monômes peuvent évidemment avoir le même degré total
sans être égaux) : pour pouvoir parler de bases de Gröbner on devra au
préalable avoir fait le choix d'un ordre total sur les monômes
vérifiant certaines propriétés de compatibilité avec la structure
algébrique (on parlera d'ordre « admissible » ci-dessous), et toutes
les définitions seront relatives à ce choix d'un ordre monomial.

Pour se faire une idée du contexte dans lequel on utilisera ces
notions, on pourra notamment penser au cas, qui sera étudié plus
précisément en \ref{section-algebre-de-decomposition-universelle}
ci-dessous, où $f \in k[X]$ est un polynôme univarié irréductible et
séparable, disons $f = X^d + a_1 X^{d-1} + \cdots + a_d$ et où on
considère l'idéal $I$ de $k[Z_1,\ldots,Z_d]$ engendré par les
relations $e_i = (-1)^i a_i$ où $e_i$ désigne le $i$-ième polynôme
symétrique élémentaire en $Z_1,\ldots,Z_d$ : autrement dit, ces
relations imposent aux $Z_1,\ldots,Z_d$ d'être les racines distinctes,
dans un certain ordre, de $f$ (remarquons d'ailleurs que $f(Z_i) \in
I$ pour tout $i$), et il s'avère que l'algèbre $k[Z_1,\ldots,Z_d]/I$
est de dimension finie, réduite, et est un produit de copies du corps
de décomposition de $f$ qui s'écrivent de la forme
$k[Z_1,\ldots,Z_d]/J$ avec $J \supseteq I$ un idéal dont le calcul
équivaut essentiellement au calcul du groupe de Galois de $f$.

\subsection{Monômes et idéaux monomiaux}

On appelle \textbf{monôme} de $k[Z_1,\ldots,Z_d]$ un polynôme de la
forme $Z_1^{\ell_1}\cdots Z_d^{\ell_d}$.  On dit qu'un monôme
$Z_1^{\ell_1}\cdots Z_d^{\ell_d}$ \textbf{divise} un monôme
$Z_1^{\ell'_1}\cdots Z_d^{\ell'_d}$ lorsque $\ell_i \leq \ell'_i$ pour
tout $i$ (c'est bien la relation de divisibilité dans l'anneau
factoriel $k[Z_1,\ldots,Z_d]$, restreinte aux monômes, et le rapport
entre les deux monômes est alors lui-même un monôme).  Un
\textbf{terme} est un monôme multiplié par une constante
(c'est-à-dire, un élément de $k$) non nulle : on parle alors du monôme
\emph{de} ce terme.  Tout polynôme s'écrit de façon unique comme somme
de termes dont les monômes sont distincts : ce sont les termes de
(=intervenant dans) ce polynôme.

Commençons par la remarque suivante, qui est évidente, mais
essentielle :
\begin{proposition2}\label{divisibilite-des-monomes}
Si $s_1,\ldots,s_r$ sont des monômes de $k[Z_1,\ldots,Z_d]$, alors
pour chaque terme $c s$ de $g_1 s_1 + \cdots + g_r s_r$ (où
$g_1,\ldots,g_r \in k[Z_1,\ldots,Z_d]$) le monôme $s$ de ce terme est
divisible par l'un des $s_i$.
\end{proposition2}
\begin{proof}
En développant l'écriture $g_1 s_1 + \cdots + g_r s_r$, puisque la
somme comporte le terme $c s$, au moins un des facteurs comporte un
terme dont le monôme est $s$, ce qui montre bien que $s$ est divisible
par un des $s_i$.
\end{proof}

\begin{corollaire2}\label{composition-ideaux-monomiaux}
Si $s_1,\ldots,s_r$ sont des monômes de $k[Z_1,\ldots,Z_d]$, l'idéal
qu'ils engendrent est exactement l'idéal des polynômes dont le monôme
de chaque terme est divisible par un des $s_i$.
\end{corollaire2}
\begin{proof}
On vient de montrer que si $f$ est dans $(s_1,\ldots,s_r)$ alors le
monôme de chaque terme de $f$ est divisible par un des $s_i$.
Réciproquement, si c'est le cas, $f$ est somme de termes multiples
des $s_i$, qui appartiennent donc à l'idéal engendré par les $s_i$.
\end{proof}

\begin{corollaire2}\label{equivalences-ideaux-monomiaux}
Si $I$ est un idéal de $k[Z_1,\ldots,Z_d]$, les deux propriétés
suivantes sont équivalentes :
\begin{itemize}
\item l'idéal $I$ est engendré par des monômes (ou : par tous ses monômes),
\item tout terme d'un élément de $I$ est élément de $I$.
\end{itemize}
\end{corollaire2}
\begin{proof}
Le fait que la première propriété implique la deuxième découle
trivialement du corollaire précédent (si $I = (s_1,\ldots,s_r)$ et
si $f \in I$, alors tout terme de $f$ est divisible par un des $s_i$
donc, en particulier, appartient à $I$).

Réciproquement si $I$ vérifie la deuxième propriété, et si
$f_1,\ldots,f_t$ engendrent $I$, appelons $s_1,\ldots,s_r$ l'ensemble
de tous les monômes intervenant dans un des $f_i$ : l'hypothèse
assure que les $s_i$ appartiennent à $I$, et manifestement ils
engendrent les $f_i$, donc engendrent tout $I$, donc $f =
(s_1,\ldots,s_r)$, ce qui démontre la première propriété.
\end{proof}

On appelle \textbf{idéal monomial} un idéal de $k[Z_1,\ldots,Z_d]$ qui
vérifie les propriétés équivalentes énoncées ci-dessus.



%
\subsection{Ordres admissibles sur les monômes}

\begin{definition2}\label{definition-ordres-admissibles}
On appelle \textbf{ordre admissible} (ou \textbf{ordre monomial}) sur
les monômes de $k[Z_1,\ldots,Z_d]$ une relation d'ordre total
$\preceq$ sur les monômes de ce dernier telle que :
\begin{itemize}
\item $1 \preceq s$ pour tout monôme $s$, et
\item si $s_1 \preceq s_2$ et $s$ est un monôme quelconque, alors $s
  s_1 \preceq s s_2$.
\end{itemize}
(On notera souvent abusivement $c s \preceq c' s'$, lorsque $cs, c's'$
sont deux termes, pour signifier que leurs monômes vérifient $s
\preceq s'$.)

Si de plus l'ordre vérifie la propriété que $\deg s < \deg s'$
implique $s \preceq s'$ (autrement dit, si l'ordre considéré raffine
l'ordre partiel donné par le degré total), on dit qu'il est
\textbf{gradué}.
\end{definition2}

\begin{proposition2}\label{proprietes-ordres-admissibles}
Si $\preceq$ est un ordre admissible sur les monômes de
$k[Z_1,\ldots,Z_d]$, alors
\begin{itemize}
\item si $s_1 | s_2$ alors $s_1 \preceq s_2$,
\item $\preceq$ est un bon ordre (c'est-à-dire : tout ensemble non
  vide de monômes a un plus petit élément pour $\preceq$, ou de façon
  équivalente, il n'y a pas de suite infinie strictement décroissante
  de monômes pour $\preceq$).
\end{itemize}
\end{proposition2}
\begin{proof}
Le premier point est évident : si $s_2 = s s_1$ alors $1 \preceq s$
entraîne $s_1 \preceq s s_1 = s_2$.  Montrons le second : si $S$ est
un ensemble de monômes, soit $I$ l'idéal qu'ils engendrent ; comme
$k[Z_1,\ldots,Z_d]$ est noethérien, il existe un sous-ensemble fini
$S_0 \subseteq S$ qui engendre le même idéal $I$.  Soit $s$ le plus
petit élément de $S_0$ : on prétend que $s$ est aussi le plus petit
élément de $S$.  En effet, si $s' \in S$ alors $s' \in I$ donc $s'$
s'écrit comme combinaison d'éléments de $S_0$, mais alors
d'après \ref{divisibilite-des-monomes}, $s'$ est simplement multiple d'un
élément de $S_0$, et d'après le premier point, $s\preceq s'$, ce qui
conclut.
\end{proof}

Lorsque $d=1$, le seul ordre admissible sur les monômes est évidemment
celui donné par $Z^\ell \preceq Z^{\ell'}$ ssi $\ell \leq \ell'$
(l'ordre par le degré).

\begin{definition2}
Une fois fixé un ordre admissible $\preceq$ sur les monômes, si $f \in
k[Z_1,\ldots,Z_d]$ est non nul, on note $\initial_{\preceq}(f)$ (ou
simplement $\initial(f)$ si l'ordre est sous-entendu) et on appelle
\textbf{terme initial} (ou \textbf{terme de tête}) de $f$ le terme au
\emph{plus grand} monôme pour l'ordre en question, et le monôme
lui-même est appelé \textbf{monôme initial}, ou monôme de tête,
de $f$.  Si $f=0$ on pose (un peu abusivement) $\initial(f) = 0$.
\end{definition2}

Lorsque $d=1$, pour le seul ordre admissible sur les monômes,
$\initial(f)$ est simplement le terme dominant de $f$.

Le $(\ell_1,\ldots,\ell_d)$ pour lequel le monôme initial de $f$
s'écrive $Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ s'appelle parfois
\textbf{multidegré} de $f$ ; si on se permet d'identifier le monoïde
multiplicatif des monômes avec le monoïde $\NN^d$ des multidegrés, on
peut considérer « multidegré » comme simplement synonyme de « monôme
  initial ».

\begin{remarque2}
Si $f,g$ sont deux polynômes, alors $\initial(gf) =
\initial(g)\,\initial(f)$ : en effet, les propriétés d'un ordre
admissible (\ref{definition-ordres-admissibles}) font que le monôme
d'aucun terme de $gf$ ne peut être plus grand que le produit du monôme
initial de $g$ et de celui de $f$.

En particulier, si $cs$ est un terme (avec $c \in k$ une constante et
$s$ un monôme), alors pour tout polynôme $f$ on a $\initial(csf) =
cs\initial(f)$.
\end{remarque2}

\medbreak

Donnons maintenant quelques exemples importants d'ordres admissibles
sur les monômes.  On supposera toujours, quitte à renuméroter les
variables, que $Z_1 \preceq Z_2 \preceq \cdots \preceq Z_d$.

\subsubsection{L'ordre lexicographique (pur)}  L'\textbf{ordre
  lexicographique} est défini par $Z_1^{\ell_1} \cdots Z_d^{\ell_d}
\mathrel{\preceq_{\mathtexttt{lex}}} Z_1^{\ell'_1} \cdots Z_d^{\ell'_d}$
ssi $\ell_i < \ell'_i$ pour le \emph{plus grand} $i$ tel que $\ell_i
\neq \ell'_i$.  Autrement dit, l'ordre lexicographique compare deux
monômes en comparant leur degré en $Z_d$ ou, en cas d'égalité, de
$Z_{d-1}$ puis $Z_{d-2}$ et ainsi de suite jusqu'à $Z_1$ (la
comparaison lexicographique se fait dans cet ordre, c'est-à-dire en
donnant le poids le plus fort à l'exposant de la dernière variable, en
raison de notre choix de l'ordre des variables, $Z_1 \preceq Z_2
\preceq \cdots \preceq Z_d$ ; plus généralement, tout ordre total sur
l'ensemble des variables définit un unique ordre lexicographique pur
associé).

Pour cet ordre on a donc $1 \preceq Z_1 \preceq Z_1^2 \preceq Z_1^3
\preceq \cdots \preceq Z_2 \preceq Z_1 Z_2 \preceq Z_1^2 Z_2 \preceq
\cdots \preceq Z_2^2 \preceq Z_1 Z_2^2 \preceq \cdots \preceq Z_2^3
\preceq \cdots \preceq Z_3 \preceq Z_1 Z_3 \preceq Z_1^2 Z_3 \preceq
\cdots \preceq Z_2 Z_3 \preceq Z_1 Z_2 Z_3 \preceq \cdots \preceq
Z_3^2 \preceq \cdots \preceq Z_4 \preceq \cdots$ (l'ordinal associé à
ce bon ordre sur les monômes de $k[Z_1,\ldots,Z_d]$ vaut $\omega^d$).

\begin{proposition2}\label{caracterisation-ordre-lexicographique-pur}
Si $\initial_{\mathtexttt{lex}}(f) \in k[Z_1,\ldots,Z_t]$ (pour un $t\leq
d$) alors $f \in k[Z_1,\ldots,Z_t]$.  De plus, cette propriété
caractérise l'ordre lexicographique (parmi les ordres admissibles).
\end{proposition2}
\begin{proof}
La première affirmation est claire : tous les monômes plus petits,
pour l'ordre lexicographique, qu'un monôme dans $k[Z_1,\ldots,Z_t]$,
sont eux-mêmes dans $k[Z_1,\ldots,Z_t]$.

Supposons maintenant qu'un ordre admissible $\preceq$ soit tel que si
$\initial_{\preceq}(f) \in k[Z_1,\ldots,Z_t]$ (pour un $t\leq d$)
alors $f \in k[Z_1,\ldots,Z_t]$ : ceci signifie que tout monôme
faisant intervenir (à un degré non nul) une variable $Z_i$ avec $i>t$
est strictement supérieur à tout monôme ne faisant intervenir que
$Z_1,\ldots,Z_t$.  Considérons $s = Z_1^{\ell_1} \cdots Z_d^{\ell_d}$
et $s' = Z_1^{\ell'_1} \cdots Z_d^{\ell'_d}$ deux monômes.  Soit $i$
le \emph{plus grand} possible tel que $\ell_i \neq \ell'_i$, et disons
que $\ell_i < \ell'_i$.  Posons $\ell^0_j = \min(\ell_j,\ell'_j)$, de
sorte que $s^0 = Z_1^{\ell^0_1} \cdots Z_d^{\ell^0_d}$ soit le plus
grand diviseur commun de $s$ et $s'$, disons $s = s^0 s^1$ et $s' =
s^0 s^{1\prime}$.  La définition de $i$ assure que $s^{1\prime}$ fait
intervenir la variable $Z_i$ alors que $s^1 \in
k[Z_1,\ldots,Z_{i-1}]$.  La propriété sur $\preceq$ montre que $s^1
\preceq s^{1\prime}$, donc $s \preceq s'$.  On a donc montré que si
$s,s'$ sont dans un certain ordre pour l'ordre lexicographique, ils le
sont aussi pour l'ordre $\preceq$ : c'est bien que ces deux ordres
coïncident.
\end{proof}

\subsubsection{L'ordre lexicographique gradué}  L'\textbf{ordre
  lexicographique par degré} ou \textbf{ordre lexicographique gradué}
est défini par $Z_1^{\ell_1} \cdots Z_d^{\ell_d}
\mathrel{\preceq_{\mathtexttt{glex}}} Z_1^{\ell'_1} \cdots Z_d^{\ell'_d}$
ssi $\sum \ell_i < \sum \ell'_i$ ou $\sum \ell_i = \sum \ell'_i$ et
$\ell_i < \ell'_i$ pour le \emph{plus grand} $i$ tel que $\ell_i \neq
\ell'_i$.  Autrement dit, les monômes sont classés en priorité par
degré total puis, en cas d'égalité, par l'ordre lexicographique pur
défini ci-dessus, c'est-à-dire en donnant le plus de poids à la plus
grande variable.  (De même que ci-dessus, nous avons fixé $Z_1 \preceq
Z_2 \preceq \cdots \preceq Z_d$, mais plus généralement, il y a un
unique ordre lexicographique gradué pour chaque ordre total sur les
variables.)

Pour cet ordre, on a donc $1 \preceq Z_1 \preceq Z_2 \preceq Z_3
\preceq Z_4 \preceq \cdots \preceq Z_1^2 \preceq Z_1 Z_2 \preceq Z_2^2
\preceq Z_1 Z_3 \preceq Z_2 Z_3 \preceq Z_3^2 \preceq \cdots \preceq
Z_1^3 \preceq Z_1^2 Z_2 \preceq Z_1 Z_2^2 \preceq Z_2^3 \preceq Z_1^2
Z_3 \preceq Z_1 Z_2 Z_3 \preceq \cdots$ (l'ordinal associé à ce bon
ordre sur les monômes de $k[Z_1,\ldots,Z_d]$ vaut $\omega$ comme c'est
le cas pour tout ordre gradué).

\begin{proposition2}\label{caracterisation-ordre-lexicographique-gradue}
L'ordre $\mathrel{\preceq_{\mathtexttt{glex}}}$ est gradué au sens
de \ref{definition-ordres-admissibles}, et si
$\initial_{\mathtexttt{glex}}(f) \in k[Z_1,\ldots,Z_t]$ (pour un $t\leq
d$) avec $f$ un polynôme homogène, alors $f \in k[Z_1,\ldots,Z_t]$.
De plus, ces propriétés caractérisent l'ordre lexicographique gradué
(parmi les ordres admissibles).
\end{proposition2}
\begin{proof}
Le fait que l'ordre $\mathrel{\preceq_{\mathtexttt{glex}}}$ soit gradué
est évident sur sa définition ; pour ce qui est de la deuxième
propriété, il suffit de remarquer que tous les monômes plus petits,
pour l'ordre lexicographique gradué, et de même degré, qu'un monôme
dans $k[Z_1,\ldots,Z_t]$, sont eux-mêmes dans $k[Z_1,\ldots,Z_t]$
(puisque, étant de même degré, ils sont plus petits pour l'ordre
lexicographique pur).

Pour montrer que les propriétés énoncées caractérisent l'ordre
lexicographique gradué, on procède comme
en \ref{caracterisation-ordre-lexicographique-pur} : soit $\preceq$ un
ordre admissible gradué tel que si $\initial_{\preceq}(f) \in
k[Z_1,\ldots,Z_t]$ (pour un $t\leq d$) avec $f$ homogène alors $f \in
k[Z_1,\ldots,Z_t]$ ; ceci signifie que tout monôme faisant intervenir
(à un degré non nul) une variable $Z_i$ avec $i>t$ est strictement
supérieur à tout monôme du même degré ne faisant intervenir que
$Z_1,\ldots,Z_t$.  Si $s = Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ et $s' =
Z_1^{\ell'_1} \cdots Z_d^{\ell'_d}$ sont deux monômes de même degré
total tels que $s \mathrel{\preceq_{\mathtexttt{glex}}} s'$ (donc, vu que
le degré total est le même, $s \mathrel{\preceq_{\mathtexttt{lex}}} s'$),
la démonstration utilisée dans le cas de l'ordre lexicographique pur
montre que $s \preceq s'$, et ceci démontre que $\preceq$ coïncide
avec l'ordre $\mathrel{\preceq_{\mathtexttt{glex}}}$.
\end{proof}

\subsubsection{L'ordre lexicographique inversé gradué} L'\textbf{ordre
  lexicographique inversé par degré} (ou \textbf{...gradué}) est
défini par $Z_1^{\ell_1} \cdots Z_d^{\ell_d}
\mathrel{\preceq_{\mathtexttt{grevlex}}} Z_1^{\ell'_1} \cdots
Z_d^{\ell'_d}$ ssi $\sum \ell_i < \sum \ell'_i$ ou $\sum \ell_i = \sum
\ell'_i$ et $\ell_i > \ell'_i$ pour le \emph{plus petit} $i$ tel que
$\ell_i \neq \ell'_i$.  Autrement dit, cet ordre trie en premier lieu
par degré total puis, en cas d'égalité, classe en premier les monômes
ayant le plus grand degré dans la plus petite variable — et non pas
comme le fait l'ordre lexicographique le plus petit degré dans la plus
grande variable.  (Comme dans les cas précédents, cette définition est
faite relativement à l'ordre convenu sur les variables, et plus
généralement tout ordre sur celles-ci définit un unique ordre
lexicographique inversé gradué.)

Pour cet ordre, on a donc $1 \preceq Z_1 \preceq Z_2 \preceq Z_3
\preceq Z_4 \preceq \cdots \preceq Z_1^2 \preceq Z_1 Z_2 \preceq Z_1
Z_3 \preceq Z_1 Z_4 \preceq \cdots \preceq Z_2^2 \preceq Z_2 Z_3
\preceq \cdots \preceq Z_3^2 \preceq \cdots \preceq Z_1^3 \preceq
Z_1^2 Z_2 \preceq Z_1^2 Z_3 \preceq \cdots \preceq Z_1 Z_2^2 \preceq
Z_1 Z_2 Z_3 \preceq \cdots \preceq Z_2^3 \preceq \cdots$ (l'ordinal
associé à ce bon ordre sur les monômes de $k[Z_1,\ldots,Z_d]$
vaut $\omega$ comme c'est le cas pour tout ordre gradué).

On peut noter que $\mathrel{\preceq_{\mathtexttt{grevlex}}}$ et
$\mathrel{\preceq_{\mathtexttt{glex}}}$ coïncident lorsqu'il n'y a que
deux variables (une fois fixé l'ordre entre celles-ci).

\begin{proposition2}\label{caracterisation-ordre-lexicographique-inverse-gradue}
L'ordre $\mathrel{\preceq_{\mathtexttt{grevlex}}}$ est gradué au sens
de \ref{definition-ordres-admissibles}, et si
$\initial_{\mathtexttt{grevlex}}(f) \in (Z_1,\ldots,Z_t)$ (pour un $t\leq
d$, et en notant bien sûr $(Z_1,\ldots,Z_t)$ l'idéal engendré par ces
variables) avec $f$ un polynôme homogène, alors $f \in
(Z_1,\ldots,Z_t)$.  De plus, ces propriétés caractérisent l'ordre
lexicographique inversé gradué (parmi les ordres admissibles).
\end{proposition2}
\begin{proof}
Le fait que l'ordre $\mathrel{\preceq_{\mathtexttt{grevlex}}}$ soit gradué
est évident sur sa définition ; pour ce qui est de la deuxième
propriété, il suffit de remarquer que tous les monômes plus petits,
pour l'ordre lexicographique inversé gradué, et de même degré, qu'un
monôme dans $(Z_1,\ldots,Z_t)$, sont eux-mêmes dans
$(Z_1,\ldots,Z_t)$ : en effet, dire d'un monôme qu'il appartient à
$(Z_1,\ldots,Z_t)$ signifie qu'il a un degré $>0$ dans l'une des $t$
premières variables, et, à degré total constant, diminuer le monôme
pour $\mathrel{\preceq_{\mathtexttt{grevlex}}}$ se fait en augmentant le
degré dans la plus petite variable.

Pour montrer que les propriétés énoncées caractérisent l'ordre
lexicographique inversé gradué, on procède comme
en \ref{caracterisation-ordre-lexicographique-pur} : soit $\preceq$ un
ordre admissible gradué tel que si $\initial_{\preceq}(f) \in
(Z_1,\ldots,Z_t)$ (pour un $t\leq d$) avec $f$ homogène alors $f \in
(Z_1,\ldots,Z_t)$ ; ceci signifie que tout monôme faisant intervenir
(à un degré non nul) une variable $Z_i$ avec $i\leq t$ est strictement
inférieur à tout monôme du même degré ne faisant intervenir que
$Z_{t+1},\ldots,Z_d$.  Si $s = Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ et
$s' = Z_1^{\ell'_1} \cdots Z_d^{\ell'_d}$ sont deux monômes de même
degré total tels que $s \mathrel{\preceq_{\mathtexttt{grevlex}}} s'$,
c'est-à-dire tels que $\ell_i > \ell'_i$ où $i$ est le \emph{plus
  petit} possible tel que $\ell_i \neq \ell'_i$, on appelle comme
précédemment $s^0 = Z_1^{\ell^0_1} \cdots Z_d^{\ell^0_d}$ le plus
grand diviseur commun de $s$ et $s'$ et $s^1$ et $s^{1\prime}$ définis
par$s = s^0 s^1$ et $s' = s^0 s^{1\prime}$ : on a alors $s^1 \preceq
s^{1\prime}$ puisque $s^1$ fait intervenir $Z_i$ et non $s^{1\prime}$
(alors qu'ils sont de même degré total), donc $s \preceq s'$, et ceci
démontre que $\preceq$ coïncide avec
l'ordre $\mathrel{\preceq_{\mathtexttt{grevlex}}}$.
\end{proof}

\subsubsection{Quelques autres ordres possibles} Il est assez fréquent
qu'au lieu d'utiliser le degré total dans les définitions de l'ordre
lexicographique gradué ou lexicographique inverse gradué, on utilise
un degré pondéré dans lequel les variables ont reçu des poids
$w_1,\ldots,w_d > 0$ (autrement dit, le premier critère de comparaison
sur un monôme $Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ est son degré pondéré
$\lambda(\ell) := \sum_{i=1}^d w_i \ell_i$).

Si les variables se divisent en plusieurs blocs $\mathscr{B}_j = \{
Z_{j,1},\ldots,Z_{j,d_j} \}$, et si on dispose d'un ordre
$\mathrel{\preceq_j}$ sur les monômes sur chaque bloc, on peut
combiner ceux-ci lexicographiquement (une fois choisi un ordre entre
les blocs, disons $\mathscr{B}_1 \preceq \cdots \preceq \mathscr{B}_r$
pour fixer les idées) en décrétant que $s \preceq s'$ ssi $s_{(j)}
\mathrel{\preceq_j} s'_{(j)}$ pour le plus grand $j$ tel que $s_{(j)}
\neq s'_{(j)}$, où $s_{(j)}$ désigne le plus grand facteur de $s$
formé de variables du bloc $\mathscr{B}_j$ (c'est-à-dire le produit
des variables de ce bloc aux mêmes multiplicités qu'elles apparaissent
dans $s$).  L'ordre lexicographique pur sur $d$ variables est un cas
particulier où on combine $d$ fois l'unique ordre possible sur les
monômes en une unique variable.

\subsubsection{Ordres monomiaux définis par des vecteurs de poids}
Supposons donnés des éléments $\lambda^{(0)},\ldots,\lambda^{(r)}$ du
dual de $\RR^d$ et qui l'engendrent en tant qu'espace vectoriel (ou
simplement dont l'intersection des noyaux ne contient pas de point à
coordonnées entières).  On va poser $s \preceq s'$, avec $s =
Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ et $s' = Z_1^{\ell'_1} \cdots
Z_d^{\ell'_d}$, lorsque $\lambda^{(j)}(\ell' - \ell) > 0$ pour le plus
petit $j$ tel que $\lambda^{(j)}(\ell' - \ell) \neq 0$ (en considérant
$\ell$ et $\ell'$ comme des éléments de $\NN^d \subseteq \RR^d$) —
autrement dit, on utilise successivement les formes linéaires
$\lambda^{(j)}$ pour comparer les vecteurs d'exposants, en donnant le
poids le plus fort aux premières.  Cette définition conduit bien à un
ordre admissible sur les monômes lorsque pour tout $1 \leq i \leq d$,
pour le plus petit $j$ tel que le coefficient de $\ell_i$ dans la
forme linéaire $\lambda^{(j)}$ soit non nul, ce coefficient soit en
fait strictement positif (c'est par exemple le cas si déjà
$\lambda^{(0)}$ est à coefficients strictement positifs).  On dit que
l'ordre $\preceq$ est défini par les formes linéaires (ou
\emph{vecteurs de poids}) $\lambda^{(0)},\ldots,\lambda^{(r)}$.

Le cas de l'ordre lexicographique pur s'obtient en prenant pour
$\lambda^{(i)}$ les $d$ formes linéaires de projection sur les
coordonnées $\ell_d,\ldots,\ell_1$ de la plus grande vers la plus
petite variable ; l'ordre lexicographique gradué s'obtient en
précédant toutes ces formes $\lambda^{(i)}$ de la forme
$\lambda^{(0)}$ de degré total $(\ell_i) \mapsto \sum_{i=1}^d \ell_i$
dont tous les coefficients valent $1$ ; l'ordre lexicographique
inversé gradué utilise cette même forme $\lambda^{(0)}$ de degré total
puis les formes \emph{opposées} des projections sur les coordonnées
$\ell_1,\ldots,\ell_d$.

En fait, il est possible de montrer que \emph{tout} ordre admissible
peut être défini par des formes linéaires
$\lambda^{(0)},\ldots,\lambda^{(r)}$ comme on vient de le dire.

Remarquons que, selon les cas, une seule forme linéaire
$\lambda^{(0)}$ peut suffire à définir tout l'ordre : par exemple, en
deux variables $X,Y$, penser à l'ordre monomial admissible défini par
la seule forme linéaire $\lambda(i,j) = i + \sqrt{2}\,j$, autrement
dit $X^i Y^j \preceq X^{i'} Y^{j'}$ ssi $(i'-i) + \sqrt{2}\,(j'-j)
\geq 0$.


%
\subsection{Bases de Gröbner}

\begin{definition2}\label{definition-ideal-initial}
Si $I$ est un idéal de $k[Z_1,\ldots,Z_d]$ et $\preceq$ un ordre
admissible, on note $\initial_{\preceq}(I)$ et on appelle
\textbf{idéal initial} de $I$ (relativement à l'ordre $\preceq$)
l'idéal engendré par les $\initial_{\preceq}(f)$ pour tous les $f\in
I$ (c'est donc un idéal monomial).
\end{definition2}

En lisant cette définition, on gardera à l'esprit le
corollaire \ref{composition-ideaux-monomiaux} : on peut définir
l'idéal initial de $I$ comme l'ensemble des polynômes qui sont
combinaisons linéaires de monômes chacun divisible par un
$\initial_{\preceq}(f)$ pour $f\in I$.

\begin{proposition2}\label{inclusion-ideaux-et-egalite-ideaux-initiaux}
Si $J \subseteq I$ sont deux idéaux de $k[Z_1,\ldots,Z_d]$ et que
$\initial(J) = \initial(I)$ (relativement à un certain ordre
admissible $\preceq$), alors $J = I$.
\end{proposition2}
\begin{proof}
Si ce n'est pas le cas, soit $f \in I$ ayant $\initial(f)$ le plus
petit possible tel que $f \not\in J$.  Comme
$\initial(f) \in \initial(I) = \initial(J)$, il existe $g \in J$ tel
que $\initial(g) = \initial(f)$.  Alors
$\initial(f-g) \prec \initial(f)$ (strictement), mais on a $f - g \in
I$ et $f - g \not\in J$, ce qui contredit la minimalité de $f$.
\end{proof}

On prendra en revanche garde au fait qu'il n'y a aucune raison en
général que prendre les $\initial_{\preceq}(f)$ pour $f$ parcourant
tel ou tel ensemble de générateurs de $I$ suffise à engendrer
$\initial_{\preceq}(I)$.  La définition et la proposition qui suivent
signifient que les bases de Gröbner sont précisément les ensembles de
générateurs pour lesquels c'est le cas.

\begin{definition2}
Si $I$ est un idéal de $k[Z_1,\ldots,Z_d]$ et $\preceq$ un ordre
admissible sur les monômes de ce dernier, on appelle \textbf{base de
  Gröbner} de $I$ (relativement à l'ordre $\preceq$) un ensemble
$f_1,\ldots,f_r$ d'éléments de $I$ tels que
$\initial_{\preceq}(f_1),\ldots,\initial_{\preceq}(f_r)$
engendrent $\initial_{\preceq}(I)$.
\end{definition2}

A priori, rien ne dit que $f_1,\ldots,f_r$ engendrent $I$.  C'est
pourtant le cas :
\begin{proposition2}
Dans les conditions ci-dessus, on a $I = (f_1,\ldots,f_r)$.
\end{proposition2}
\begin{proof}
On a $(f_1,\ldots,f_r) \subseteq I$ puisque les $f_i$ sont supposés
dans $I$.  D'après \ref{inclusion-ideaux-et-egalite-ideaux-initiaux},
il suffit de montrer que $\initial(J) = \initial(I)$ où $J =
(f_1,\ldots,f_r)$.  On sait que $\initial(J) \subseteq \initial(I)$ ;
mais réciproquement, si $h \in I$, par hypothèse sur les $f_i$ on peut
écrire $\initial(h) = g_1 \initial(f_1) + \cdots + g_r \initial(f_r)$,
donc $\initial(h) \in J$ et ainsi $\initial(h) \in \initial(J)$ : ceci
montre bien $\initial(J) = \initial(I)$.
\end{proof}

\begin{proposition2}\label{existence-bases-de-groebner}
Tout idéal de $k[Z_1,\ldots,Z_d]$ admet une base de Gröbner (finie).
\end{proposition2}
\begin{proof}
La propriété noethérienne assure que parmi les $\initial(f)$ pour
$f\in I$, qui par définition engendrent $\initial(I)$, on peut
extraire un ensemble fini engendrant $\initial(I)$ — il s'agit d'une
base de Gröbner de $I$.
\end{proof}

Cette démonstration n'est manifestement pas constructive.  On va
cependant donner dans la section suivante un algorithme permettant de
calculer une base de Gröbner à partir d'un ensemble quelconque de
générateurs d'un idéal.  Commençons cependant par expliquer en quoi la
connaissance d'une base de Gröbner d'un idéal permet de résoudre la
question algorithmique de l'appartenance d'un élément à cet idéal :

\begin{algorithme2}[algorithme de division]\label{algorithme-division}
Soient $f,f_1,\ldots,f_r \in k[Z_1,\ldots,Z_d]$ et $\preceq$ un ordre
admissible sur les monômes.  Alors il existe une écriture
\[
f = g_1 f_1 + \cdots + g_r f_r + \rho
\tag{$*$}
\]
où $g_1,\ldots,g_r,\rho \in k[Z_1,\ldots,Z_d]$, où aucun des monômes
de $\rho$ n'est divisible par un des $\initial(f_i)$, et où $\initial(g_i
f_i) \preceq \initial(f)$ pour chaque $i$ ; et on va donner un algorithme
pour calculer cette écriture ; un tel $\rho$ s'appelle un
\textbf{reste} de $f$ par rapport au $f_1,\ldots,f_r$ et pour l'ordre
monomial $\preceq$ (on dit aussi que l'écriture ($*$) s'appelle une
\textbf{écriture standard} de $f$ par rapport aux $f_1,\ldots,f_r$ et
pour cet ordre monomial).

Lorsque les $f_1,\ldots,f_r$ forment une base de Gröbner (d'un
idéal $I = (f_1,\ldots,f_r)$), on a $f \in (f_1,\ldots,f_r)$ si et
seulement si $\rho = 0$, et $\rho$ est défini de façon unique par $f$.
\end{algorithme2}

\begin{proof}[Description de l'algorithme]
Si aucun terme de $f$ n'est divisible par aucun des $\initial(f_i)$,
retourner $\rho = f$ (et tous les $g_i = 0$).  Sinon, soit $c s
\initial(f_i)$ (où $c\neq 0$ est une constante et $s$ un monôme) le
$\preceq$-plus grand terme de $f$ qui soit divisible par un
des $\initial(f_i)$ : on applique récursivement l'algorithme à $f' = f -
c s f_i$ (qui vérifie $\initial(f') \preceq \initial(f)$), si $f' = g'_1 f_1
+ \cdots + g'_r f_r + \rho'$ est le résultat, renvoyer $g_j = g'_j$
sauf $g_i = g'_i + c s$, et $\rho = \rho'$.
\end{proof}

\begin{proof}
L'algorithme termine car le $\preceq$-plus grand monôme de $f$
divisible par un des $\initial(f_i)$ décroît strictement à chaque
itération, or $\preceq$ est un bon ordre
(cf. \ref{proprietes-ordres-admissibles}).  La propriété sur $\rho$
est évidente.  La propriété $\initial(g_j f_j) \preceq \initial(f)$ découle
par induction de $\initial(g'_j f_j) \preceq \initial(f') \preceq \initial(f)$
et $\initial(c s f_i) = c s \initial(f_i) = c\initial(f)$.

Si $\rho = 0$, le fait que $f \in (f_1,\ldots,f_r)$ est trivial.  Si
$f_1,\ldots,f_r$ forment une base de Gröbner et $f \in
(f_1,\ldots,f_r)$, comme on a aussi $\rho \in (f_1,\ldots,f_r)$, alors
$\initial(\rho) \in (\initial(f_1),\ldots,\initial(f_r))$, ce qui vu le fait
qu'aucun monôme de $\rho$ n'est divisible par un des $\initial(f_i)$,
n'est possible que si $\rho = 0$ (cf. \ref{divisibilite-des-monomes}) ; de
même, si $\rho$ et $\rho'$ sont deux restes différents du même $f$,
disons $f = g_1 f_1 + \cdots + g_r f_r + \rho$ et $f = g'_1 f_1 +
\cdots + g'_r f_r + \rho'$, alors $(g'_1-g_1) f_1 + \cdots +
(g'_r-g_r) f_r + (\rho'-\rho)$ est une écriture standard de $0$, donc
$\rho'=\rho$.
\end{proof}

Connaître une base de Gröbner d'un idéal $I$ permet de donc répondre à
la question de savoir si $f\in I$ pour un idéal donné.  Mieux, si
$(f_1,\ldots,f_r)$ est cette base de Gröbner, l'ensemble des classes
(modulo $I$) des monômes qui ne sont divisibles par aucun
des $\initial(f_i)$ constitue une base de $k[Z_1,\ldots,Z_d]/I$, ce
qui, avec l'algorithme de division, permet de calculer dans l'anneau
en question (cf. \ref{algorithmes-fondamentaux-anneau-quotient}).

\begin{remarque2}
On dit parfois simplement que des polynômes $f_1,\ldots,f_r$ sont
« une base de Gröbner » pour signifie qu'ils sont une base de Gröbner
de l'idéal qu'ils engendrent.
\end{remarque2}

\begin{proposition2}
Soient $f_1,\ldots,f_r \in k[Z_1,\ldots,Z_d]$ des polynômes tels que
\emph{tout} $f \in (f_1,\ldots,f_r)$ ait une écriture standard avec
reste nul.  Alors $f_1,\ldots,f_r$ sont une base de Gröbner.
\end{proposition2}
\begin{proof}
Supposons par l'absurde que $f_1,\ldots,f_r$ ne sont pas une base de
Gröbner de l'idéal $I$ qu'ils engendrent, c'est-à-dire qu'il existe $f
\in I$ tel que $\initial(f)$ ne soit pas dans l'idéal engendré par les
$\initial(f_i)$, autrement dit
(cf. \ref{composition-ideaux-monomiaux}) ne soit multiple d'aucun
des $\initial(f_i)$.  Par hypothèse, il existe une écriture $f = g_1
f_1 + \cdots + g_r f_r$ où $\initial(g_i f_i) \preceq \initial(f)$
pour chaque $i$, et en fait $\initial(g_i f_i) \prec \initial(f)$ sans
quoi $\initial(f)$ serait multiple de $\initial(f_i)$.  Mais avoir
$\initial(g_i f_i) \prec \initial(f)$ pour tout $i$ contredit
manifestement $f = g_1 f_1 + \cdots + g_r f_r$.
\end{proof}

(Le théorème \ref{critere-de-buchberger} donne un critère beaucoup
plus fort et utilisable en pratique.)

Lorsque $f_1,\ldots,f_r$ ne forment pas une base de Gröbner, on peut
très bien avoir $\rho \neq 0$ et pourtant que $\rho$
(c'est-à-dire, $f$) appartienne à l'idéal $(f_1,\ldots,f_r)$.  Par
exemple, pour deux polynômes, $g_1 f_1 + g_2 f_2$ pourrait avoir un
terme initial beaucoup plus petit que ceux de $f_1,f_2$ à cause d'une
annulation entre ceux-ci (dans ce cas, l'algorithme de division
appliqué à $g_1 f_1 + g_2 f_2$ par rapport à $f_1,f_2$ donnerait $g_1
f_1 + g_2 f_2$ lui-même comme reste, bien que ce polynôme appartienne
à $(f_1,f_2)$).  L'algorithme de Buchberger pour calculer les bases de
Gröbner se fonde sur l'idée qu'il suffit d'éviter ce phénomène.

\begin{exemple2}
Considérons dans $k[X,Y]$ muni de l'ordre lexicographique (avec $X
\preceq Y$) les polynômes $f_1 = X Y^2 + X^2 Y + 2$ et $f_2 = Y^2 + XY
+ Y^2$, et soit $f = X^3 - 2$.  L'algorithme de division explicité
en \ref{algorithme-division} conduit à l'écriture standard triviale $f
= \rho$ avec reste $\rho = X^3 - 2$ puisque le terme initial de ce
dernier n'est divisible ni par le terme initial $X Y^2$ de $f_1$ ni
par celui $Y^2$ de $f_2$.  Pourtant, il s'avère que $f$ appartient
bien à l'idéal engendré par $f_1$ et $f_2$, comme le prouve l'égalité
$f = - f_1 + X f_2$ : mais cette écriture n'est pas une écriture
standard.

Cet exemple se modifie assez facilement pour donner un exemple où il
n'y a pas d'unicité de l'écriture standard : si on pose $f^\% = X Y^2
+ f = X Y^2 + X^3 - 2$, alors l'algorithme explicité
en \ref{algorithme-division} conduit soit à l'écriture standard $f^\%
= f_1 + \rho$ avec $\rho = -X^2 Y + X^3 - 4$, soit à l'écriture
standard $f^\% = X f_2 + \rho'$ avec $\rho' = -X^2 Y - 2$.

L'un ou l'autre de ces phénomènes montre que $f_1,f_2$ ne forment pas
une base de Gröbner de l'idéal $I$ qu'ils engendrent.  En fait, il
s'avère que cet idéal $I$ est celui engendré par $f_2$ et $f = -f_1 +
X f_2$, et que ces polynômes-là en forment une base de Gröbner,
l'idéal initial $\initial_{\mathtexttt{lex}}(I)$ étant celui engendré par
$X^3$ et $Y^2$.  (Par ailleurs, si $k = \QQ$, alors $\QQ[X,Y]/I$ est
le corps $\QQ(\root3\of2, j\root3\of2)$ de décomposition de $X^3 - 2$
sur $\QQ$.)
\end{exemple2}


%
\subsection{Relations entre monômes}\label{section-relations-entre-monomes}

Si $f_1,\ldots,f_r \in k[Z_1,\ldots,Z_d]$ sont des polynômes, on
appelle \textbf{relation} ou \textbf{syzygie} entre les $f_i$ un
$r$-uplet $(g_1,\ldots,g_r)$ de polynômes tels que $g_1 f_1 + \cdots +
g_r f_r = 0$ (on dira parfois abusivement que cette égalité est la
relation) ; lorsque les $g_i$ ne sont pas tous nuls, on parle de
relation non-triviale.  Le \textbf{module des relations} (ou
\textbf{des syzygies}) entre $f_1,\ldots,f_r$ est le sous-module
de $(k[Z_1,\ldots,Z_d])^r$ formé des $(g_1,\ldots,g_r)$ tels que $g_1
f_1 + \cdots + g_r f_r = 0$.

Si $\preceq$ est un ordre monomial, on appelle de plus \textbf{monôme
  initial} (ou multidegré), pour l'ordre $\preceq$, d'une relation
$(g_1,\ldots,g_r)$ non triviale entre $f_1,\ldots,f_r$ le
$\preceq$-plus grand des monômes initiaux des $g_i f_i$.

Comme on va le voir en \ref{section-algorithme-de-buchberger}, la
question de savoir si $f_1,\ldots,f_r$ constituent une base de Gröbner
est intimement liée à celle de trouver des générateurs du module des
relations entre eux.  Avant de nous pencher sur cette question en
général, nous commençons par étudier le cas où $f_1,\ldots,f_r$ sont
des monômes (ou des termes).

On définit le pgcd de deux monômes $s$ et $s'$ étant défini comme le
plus grand monôme (pour n'importe quel ordre admissible, ou pour
l'ordre partiel de divisibilité) parmi les monômes qui divisent à la
fois $s$ et $s'$, c'est-à-dire $\pgcd(s,s') =
Z_1^{\min(\ell_1,\ell'_1)} \cdots Z_d^{\min(\ell_d,\ell'_d)}$ si $s =
Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ et $s' = Z_1^{\ell'_1} \cdots
Z_d^{\ell'_d}$.  On parlera parfois abusivement du pgcd (unitaire) de
deux termes $cs$ et $cs'$ (où $c,c' \in k^\times$ et $s,s'$ sont deux
monômes) pour désigner $\pgcd(s,s')$.  Le ppcm de deux monômes se
définit de façon analogue, ou bien par la formule $\ppcm(s,s') =
ss'/\pgcd(s,s')$.

Si $s_1,\ldots,s_r$ sont des monômes, on dispose entre eux de la
relation évidente $\sigma^{(i,j)}$ définie par $(s_j/s) s_i - (s_i/s)
s_j = 0$ où $s = \pgcd(s_i,s_j)$, c'est-à-dire $\sigma^{(i,j)}_u = 0$
sauf pour $u=i$ et $u=j$ auquel cas on a respectivement
$\sigma^{(i,j)}_i = s_j/s$ et $\sigma^{(i,j)}_j = -s_i/s$.  Plus
généralement, si $c_1,\ldots,c_r \in k^\times$, on appellera
$\sigma^{(i,j)}$ la relation entre $c_1 s_1,\ldots,c_r s_r$ définie
par $\sigma^{(i,j)}_u = 0$ sauf pour $u=i$ et $u=j$ auquel cas on a
respectivement $\sigma^{(i,j)}_i = c_j s_j/s$ et $\sigma^{(i,j)}_j =
-c_i s_i/s$ (toujours avec $s = \pgcd(s_i,s_j)$).  L'importance de ces
relations va apparaître, en lien avec le critère de Buchberger
(\ref{critere-de-buchberger} ci-dessous), dans la définition du
polynôme de syzygie standard et dans le résultat suivant :

\begin{proposition2}\label{relations-entre-monomes}
Si $s_1,\ldots,s_r$ sont des monômes, les relations $\sigma^{(i,j)}$
définies ci-dessus (pour $i<j$) engendrent le module des relations
entre les $s_i$.

De plus, si on appelle « relation purement de monôme $\mu$ »
(pour $\mu$ un monôme quelconque) une relation $(g_1,\ldots,g_r)$
entre $s_1,\ldots,s_r$ telle que chaque $g_i$ soit un terme de monôme
$\mu/s_i$ (ou bien $0$ si $s_i$ ne divise pas $\mu$), alors toute
relation entre les $s_1,\ldots,s_r$ s'écrit de façon unique comme
somme de relations purement de monôme $\mu$ où $\mu$ parcourt les
différents monômes (ces relations étant nulles sauf pour un nombre
fini de $\mu$).  Et une relation purement de monôme $\mu$ peut
s'écrire comme combinaison $\sum_{i<j} a^{(i,j)} \sigma^{(i,j)}$ des
relations $\sigma^{(i,j)}$ pour lesquelles $\ppcm(s_i,s_j)$ divise
$\mu$, le coefficient $a^{(i,j)}$ devant $\sigma^{(i,j)}$ étant un
terme de monôme $\mu/\ppcm(s_i,s_j)$.

(Ces énoncés sont bien entendu valables, \textit{mutatis mutandis},
pour des relations entre termes.)
\end{proposition2}
\begin{proof}
Commençons par expliquer pourquoi toute relation entre les monômes
s'écrit comme somme de relations purement de monôme $\mu$ pour les
différents $\mu$ : si $(g_1,\ldots,g_r)$ est une relation entre
$s_1,\ldots,s_r$, et si $g_i^{[\mu/s_i]}$ désigne le terme de $g_i$ de
monôme $\mu/s_i$ (ou bien $0$ si $s_i$ ne divise pas $\mu$), alors il
est clair que $\sum_{i=1}^r g_i^{[\mu/s_i]} s_i$ est la somme des
termes de monôme $\mu$ dans $\sum_{i=1}^r g_i s_i = 0$, donc vaut
elle-même $0$, i.e., $(g_1^{[\mu/s_1]}, \ldots, g_r^{[\mu/s_r]})$ est
une relation entre les $s_i$, et manifestement $(g_1,\ldots,g_r)$ est
la somme de ces relations.  L'unicité est claire.

Il est également évident que $\sigma^{(i,j)}$ est bien une relation
purement de monôme $\ppcm(s_i,s_j)$.

Soit maintenant $(g_1,\ldots,g_r)$ une relation purement de
monôme $\mu$ entre $s_1,\ldots,s_r$ : si la relation est nulle
(triviale), il n'y a rien à prouver.  Il n'est manifestement pas
possible qu'\emph{exactement un} des $g_i$ soit non nul : on peut donc
trouver $i,j$ distincts tels que $g_i \neq 0$ et $g_j \neq 0$, disons
$g_i = b_i \mu/s_i$ et $g_j = b_j \mu/s_j$.  Ceci suppose notamment
que $\mu$ divise à la fois $s_i$ et $s_j$, donc leur ppcm, disons $\mu
= \nu\, \ppcm(s_i,s_j)$.  (Remarquons que $\mu/s_i = \nu
s_j/\pgcd(s_i,s_j) = \nu \sigma^{(i,j)}_i$.)  Si on définit $\tilde
g_u$ par $\tilde g_u = g_u - b_i \nu \sigma^{(i,j)}_u$, alors $\tilde
g_i = 0$ et $\tilde g_u = g_u$ si $u\neq i,j$ : donc la relation
$(\tilde g_1,\ldots,\tilde g_r)$ a strictement moins de termes non
nuls que $(g_1,\ldots,g_r)$ — une récurrence évidente permet de
conclure.
\end{proof}


%
\subsection{L'algorithme de Buchberger}\label{section-algorithme-de-buchberger}

\subsubsection{Le $S$-polynôme}\label{definition-s-polynome}
Soient $f_1,f_2\in k[Z_1,\ldots,Z_d]$ : on définit le \textbf{polynôme
  de syzygie standard} ou \textbf{$S$-polynôme} $S(f_1,f_2)$ entre
$f_1$ et $f_2$ de la manière suivante :
\[
\begin{array}{c}
\displaystyle
S(f_1,f_2) = \frac{\initial(f_2)}{s} f_1 - \frac{\initial(f_1)}{s} f_2\\
\hbox{où~}
\displaystyle
s = \pgcd(\initial(f_1),\initial(f_2))
\end{array}
\]
On rappelle que le pgcd de deux termes $c_1 s_1 = \initial(f_1)$ et
$c_2 s_2 = \initial(f_2)$ est simplement défini comme le pgcd de $s_1$
et $s_2$.  Le terme initial des deux polynômes dont on a fait la
différence est donc $c_1\, c_2\, \frac{s_1\,s_2}{s} = c_1\, c_2\,
\ppcm(s_1,s_2)$) : par construction, ces deux termes s'annulent, et le
terme initial de $S(f_1,f_2)$ (s'il est non nul) est donc strictement
plus petit que $\ppcm(s_1,s_2) = \frac{s_1\,s_2}{s}$.

Soit $\rho_{i,j}$ un reste (au sens de \ref{algorithme-division}) de
$S(f_i,f_j)$ par rapport aux $f_1,\ldots,f_r$ : si les
$f_1,\ldots,f_r$ forment une base de Gröbner alors $\rho_{i,j} = 0$
puisque $S(f_i,f_j) \in (f_1,\ldots,f_r)$.  Ce qui est plus surprenant
est que la réciproque est également vraie :

\begin{theoreme2}[critère de Buchberger]\label{critere-de-buchberger}
Sous les hypothèses et avec les notations définies ci-dessus, on a
$\rho_{i,j} = 0$ pour tous $i,j$ si et seulement $f_1,\ldots,f_r$ sont
une base de Gröbner (de l'idéal qu'ils engendrent).
\end{theoreme2}
\begin{proof}
Une implication est claire, comme il a déjà été remarqué.  Supposons
que $\rho_{i,j} = 0$ pour tous $i,j$, c'est-à-dire qu'on ait une
écriture standard $S(f_i,f_j) = g^{(i,j)}_1 f_1 + \cdots + g^{(i,j)}_r
f_r$ (au sens de \ref{algorithme-division}), et supposons par
l'absurde que $f_1,\ldots,f_r$ ne sont pas une base de Gröbner de
l'idéal qu'ils engendrent, c'est-à-dire qu'il existe $h = g_1 f_1 +
\cdots + g_r f_r$ tel que $\initial(h)$ ne soit multiple d'aucun
des $\initial(f_i)$.

Soit $\mu$ le monôme maximal (pour l'ordre admissible $\preceq$ fixé)
parmi les $\initial(g_i f_i) = \initial(g_i)\, \initial(f_i)$ (si on
veut, il s'agit donc aussi du monôme maximal intervenant dans un
quelconque des $g_i f_i$).  On a évidemment $\initial(h) \preceq \mu$.
Mais si on avait $\initial(h) = a\mu$ pour $a \in k^\times$
c'est-à-dire que $\initial(h)$ soit proportionnel à l'un des
$\initial(g_i)\, \initial(f_i)$, alors il serait divisible par
$\initial(f_i)$, contredisant l'hypothèse faite sur $h$ : c'est donc
que $\initial(h) \prec \mu$ (strictement).  À présent, parmi les
expressions $h = g_1 f_1 + \cdots + g_r f_r$ (pour ce $h$ fixé),
choisissons-en une qui donne $\mu$ le plus petit possible : ceci a
bien un sens car $\preceq$ est un bon ordre
(cf. \ref{proprietes-ordres-admissibles}).

Soit $\$$ l'ensemble des $i$ tels que $\initial(g_i)\, \initial(f_i)$
soit de la forme $a\mu$.  On doit avoir $\sum_{i\in\$} \initial(g_i)\,
\initial(f_i) = 0$ puisque tout autre terme dans $\sum_{i=1}^r g_i
f_i$ a un monôme strictement inférieur à $\mu$.

Cette égalité $\sum_{i\in\$} \initial(g_i)\,\initial(f_i) = 0$
constitue une relation $\delta$ (au sens
de \ref{section-relations-entre-monomes}) entre les termes initiaux
$c_i s_i = \initial(f_i)$ (à savoir : $\delta_i = \initial(g_i)$ si $i
\in \$$ et $\delta_i = 0$ sinon).
D'après \ref{relations-entre-monomes}, cette relation est une
combinaison des $\sigma^{(i,j)}$ définis à cet endroit, disons $\delta
= \sum_{i<j} a^{(i,j)} \sigma^{(i,j)}$.  Remarquons que $\delta$ est
une relation purement de monôme $\mu$ (dans la terminologie
de \ref{relations-entre-monomes}) donc qu'on peut supposer chacun des
$a^{(i,j)}$ est un terme de monôme $\mu/\ppcm(s_j,s_j)$.

Si $\Phi\colon k[Z_1,\ldots,Z_d]^r \to k[Z_1,\ldots,Z_d]$ est
l'application qui envoie $(x_1,\ldots,x_r)$ sur $x_1 f_1 + \cdots +
x_r f_r$, alors on a $\Phi(\delta) = \sum_{i\in\$} \initial(g_i)\,f_i$
et d'autre part $\Phi(\sigma^{(i,j)}) = S(f_i,f_j)$.  Par conséquent,
l'égalité $\delta = \sum_{i<j} a^{(i,j)} \sigma^{(i,j)}$ permet
d'écrire $\sum_{i\in\$} \initial(g_i)\,f_i = \sum_{i<j} a^{(i,j)}
S(f_i,f_j)$.  En utilisant les écritures standards $S(f_i,f_j) =
g^{(i,j)}_1 f_1 + \cdots + g^{(i,j)}_r f_r$ qu'on a supposé exister,
on peut écrire $\sum_{i<j} a^{(i,j)} S(f_i,f_j) = \gamma_1 f_1 +
\cdots + \gamma_r f_r$ (avec $\gamma_u = \sum_{i<j} a^{(i,j)}
g^{(i,j)}_u$).  On a $\initial(S(f_i,f_j)) \prec \ppcm(s_i,s_j)$, donc
$\initial(\gamma_u f_u) \prec \mu$.  Si on remplace $g_i$ par $\tilde
g_i$ défini comme $g_i - \initial(g_i) + \gamma_i$ si $i \in \$$ et
$g_i + \gamma_i$ sinon, nous venons de montrer que $h = \tilde g_1 f_1
+ \cdots + \tilde g_r f_r$.  Or $\initial(\tilde g_i f_i) \prec \mu$
pour tout $i$, ce qui contredit la minimalité de $\mu$.
\end{proof}

Si $f_1,\ldots,f_r$ forment une base de Gröbner, le fait qu'on ait
$\rho_{i,j} = 0$ avec les notations ci-dessus signifie qu'on a une
écriture standard $S(f_i,f_j) = g^{(i,j)}_1 f_1 + \cdots + g^{(i,j)}_r
f_r$ (au sens de \ref{algorithme-division}), donc une relation $c_j
\frac{s_j}{\pgcd(s_i,s_j)} f_i - c_i \frac{s_i}{\pgcd(s_i,s_j)} f_j -
\sum_u g^{(i,j)}_u f_u = 0$ entre les $f_i$ (c'est-à-dire
$(\sigma^{(i,j)}_1, \ldots, \sigma^{(i,j)}_r)$ où $\sigma^{(i,j)}_u =
- g^{(i,j)}_u$ sauf si $u=i$ ou $u=j$ auquel cas $\sigma^{(i,j)}_i =
c_j \frac{s_j}{\pgcd(s_i,s_j)} - g^{(i,j)}_i$, respectivement
$\sigma^{(i,j)}_j = - c_i \frac{s_i}{\pgcd(s_i,s_j)} - g^{(i,j)}_j$).

\begin{theoreme2}[Spear-Schreyer]
Avec les notations précédentes, si $f_1,\ldots,f_r$ forment une base
de Gröbner, les relations $c_j \frac{s_j}{\pgcd(s_i,s_j)} f_i - c_i
\frac{s_i}{\pgcd(s_i,s_j)} f_j - \sum_u g^{(i,j)}_u f_u = 0$, où
$f_{i,j} = g^{(i,j)}_1 f_1 + \cdots + g^{(i,j)}_r f_r$ est une
écriture standard de $f_{i,j}$, engendrent\footnote{En fait, les
  relations en question forment elles-même une base de Gröbner du
  module des relations, si on prend la peine de définir la notion de
  « base de Gröbner » d'un module et non seulement d'un idéal, pour un
  ordre admissible sur les monômes de $k[Z_1,\ldots,Z_d]^r$ qui se
  déduit facilement de $\preceq$.} le module des relations
entre $f_1,\ldots,f_r$.
\end{theoreme2}
\begin{proof}
Supposons par l'absurde que $(g_1,\ldots,g_r)$ soit une relation entre
$f_1,\ldots,f_r$ qui ne soit pas combinaison des $\sigma^{(i,j)}$.  On
rappelle que le $\preceq$-plus grand monôme $\mu$ parmi les
$\initial(g_i f_i) = \initial(g_i)\, \initial(f_i)$ s'appelle le
« monôme initial » de la relation : choisissons la relation (parmi
celles qui ne sont pas combinaison des $\sigma^{(i,j)}$) qui ait $\mu$
le plus petit possible.  De plus, à monôme initial $\mu$ fixé,
choisissons la relation telle que l'indice $t$ du premier coefficient
$g_t$ tel que $\initial(g_t) = b_t \mu/s_t$ soit le plus grand
possible (i.e., $g_1 f_1 \prec \mu$, ..., $g_{t-1} f_{t-1} \prec \mu$
avec $t$ aussi grand que possible).

Il doit exister $t < v \leq r$ tel que $\initial(g_v) = b_v \mu/s_v$
(sinon aucun terme ne pourrait annuler $\initial(g_t)\,
\initial(f_t)$).  Si on définit $\tilde g_1,\ldots,\tilde g_r$ par
$\tilde g_u = g_u - b_t \nu \sigma^{(t,v)}_u$ où $\mu =
\nu\,\ppcm(s_t,s_v)$, alors on a défini une relation entre
$f_1,\ldots,f_r$ telle que $\initial(\tilde g_u f_u) \prec \mu$ pour
$u \leq t$ (y compris si $u=t$, le coefficient $b_t$ ayant été choisi
précisément pour annuler le coefficient dominant de $g_t$) tandis que
$\initial(\tilde g_u f_u) \preceq \mu$ pour tout $u$.  D'après les
hypothèses de minimalité faites sur $(g_1,\ldots,g_r)$, cette relation
devrait être combinaison des $\sigma^{(i,j)}$, donc la relation
d'origine aussi.
\end{proof}

\begin{proposition2}\label{division-avec-termes-de-tete-premiers-entre-eux}
(A) Les notations étant comme en \ref{definition-s-polynome}, si
  $\initial{f_1}$ et $\initial{f_2}$ sont premiers entre eux
  (c'est-à-dire qu'ils n'ont aucune variable en commun :
  $\pgcd(\initial(f_1),\initial(f_2)) = 1$), alors il existe une
  écriture standard (au sens de \ref{algorithme-division}) de
  $S(f_1,f_2) = \initial(f_2)\,f_1 - \initial(f_1)\,f_2$ dont le reste
  $\rho$ est nul.

(B) Par conséquent, dans le critère \ref{critere-de-buchberger}, on
  peut se contenter de tester la valeur de $\rho_{i,j}$ pour les
  paires $f_i,f_j$ telles que $\initial{f_i}$ et $\initial{f_j}$ ne
  soient pas premiers entre eux.

(C) Notamment, si $f_1,\ldots,f_r$ sont tels que les $\initial{f_i}$
  sont premiers entre eux deux à deux, alors ils sont une base de
  Gröbner de l'idéal qu'ils engendrent.
\end{proposition2}
\begin{proof}
Seul le (A) nécessite une démonstration, les autres affirmation en
étant une conséquence immédiate (compte tenu
de \ref{critere-de-buchberger}).

On a $S(f_1,f_2) = \initial(f_2)\,f_1 - \initial(f_1)\,f_2 = (f_1 -
\initial(f_1))\,f_2 - (f_2 - \initial(f_2))\,f_1 = p_2 f_1 - p_1 f_2$
où $p_i = f_i - \initial(f_i)$.  Ainsi, $\initial(p_i) \prec
\initial(f_i)$.  Les monômes initiaux de $p_2 f_1$ et $p_1 f_2$ ne
peuvent pas être les mêmes : en effet, les monômes initiaux de $f_1$
et $f_2$ sont premiers entre eux, donc une égalité ne serait possible
que si $\initial(p_i)$ était divisible par $\initial(f_i)$, ce qui
n'est pas le cas.  Supposons sans perte de généralité que
$\initial(p_1 f_2) \prec \initial(p_2 f_1)$ : alors le monôme
initial de $p_2 f_1 - p_1 f_2$ est celui de $p_1 f_2$, et l'écriture
$p_2 f_1 - p_1 f_2$ est une écriture standard (avec reste nul) au sens
de \ref{algorithme-division}, comme on le voulait.

\XXX — Cette démonstration est-elle bien complète ?  Pourquoi
Eisenbud, dans la solution de l'exercice 15.20 (dernière phrase)
suggère-t-il de faire une sorte de récurrence ?
\end{proof}

\begin{algorithme2}[algorithme de Buchberger]\label{algorithme-de-buchberger}
Donné $f_1,\ldots,f_r \in k[Z_1,\ldots,Z_d]$, on peut calculer
effectivement une base de Gröbner de l'idéal qu'ils engendrent.
\end{algorithme2}
\begin{proof}[Description de l'algorithme]
Calculer les $\rho_{i,j}$ définis plus hauts : si les $\rho_{i,j}$
sont tous nuls, terminer (les $f_1,\ldots,f_r$ forment une base de
Gröbner).  Si un des $\rho_{i,j}$ est non nul, dès qu'on le trouve,
ajouter ce $\rho_{i,j}$ parmi les $f_1,\ldots,f_r$ (c'est-à-dire,
recommencer l'algorithme avec $f_1,\ldots,f_r,\rho_{i,j}$).
\end{proof}
\begin{proof}
L'algorithme termine car l'idéal engendré par
$\initial(f_1),\ldots,\initial(f_r)$ ne cesse de croître strictement : le
processus doit donc terminer, ce qui ne peut se produire que parce que
tous les $\rho_{i,j}$ sont tous nuls, et le
critère \ref{critere-de-buchberger} permet de dire qu'on a bien une
base de Gröbner.
\end{proof}

\begin{remarques2}
Nous ne nous livrerons pas à une analyse de la complexité de cet
algorithme, mais signalons au moins que \emph{dans le pire cas} elle
est doublement exponentielle en le nombre de variables, donc \textit{a
  priori} prohibitive (c'est d'ailleurs à l'origine de différentes
tentatives d'utilisation des bases de Gröbner en cryptographie), mais
que malgré cela, en pratique, sur beaucoup de problèmes utiles,
l'algorithme termine en un temps raisonnable (les raisons pour ça
n'étant pas toujours évidentes, et parfois même mal comprises).

Il existe différentes optimisations permettant de gagner un peu
d'efficacité sur l'algorithme tel qu'il a été présenté (sans,
toutefois, changer fondamentalement sa complexité) : par exemple, dans
l'application du critère \ref{critere-de-buchberger}, on peut se
contenter de tester si $\rho_{i,j} = 0$ pour les paires $i,j$ telles
que $\initial(f_i)$ et $\initial(f_j)$ aient un pgcd non trivial (car
si leur pgcd vaut $1$, on peut montrer qu'il est toujours possible de
mener la division de $S(f_i,f_j)$ par les $f_k$ de manière à avoir un
reste nul).
\end{remarques2}


%
\subsection{Bases de Gröbner réduites}

\begin{definition2}
Une base de Gröbner $f_1,\ldots,f_r$ est dite \textbf{réduite}
lorsque, pour $i\neq j$, le monôme du terme $\initial(f_i)$ ne divise
aucun des monômes apparaissant dans $f_j$, et si, de plus, chacun des
termes $\initial(f_i)$ est unitaire (=la constante devant le monôme
est $1$).
\end{definition2}

\begin{algorithme2}\label{algorithme-reduction-base-de-groebner}
Donné $f_1,\ldots,f_r \in k[Z_1,\ldots,Z_d]$ une base de Gröbner, on
peut calculer effectivement une base de Gröbner réduite de l'idéal
qu'ils engendrent.
\end{algorithme2}
\begin{proof}[Description de l'algorithme]
Quitte à trier les éléments (et, évidemment, à effacer ceux qui sont
nuls), on peut supposer $\initial(f_1) \preceq \initial(f_2) \preceq
\cdots \preceq \initial(f_r)$.  On parcourt ces éléments dans cet
ordre et on efface de la liste tous dont le terme initial
$\initial(f_i)$ est multiple du terme initial $\initial(f_j)$ d'un
élément antérieur ($j<i$).  Ces effacements ne changent pas le fait
que les éléments forment une base de Gröbner, ni l'idéal $I$ engendré
(en effet, si $\initial(f_i)$ est multiple de $\initial(f_j)$ alors
l'idéal engendré par les $\initial(f_u)$ pour $u\neq i$ est le même
que celui engendré par tous les $\initial(f_u)$, et par hypothèse il
s'agit de $\initial(I)$).

On parcourt ensuite (ou dans la même boucle) les éléments dans cet
ordre et on remplace chaque $f_i$ par son reste $\tilde f_i$, donné
par l'algorithme \ref{algorithme-division}, par rapport à
$f_1,\ldots,f_{i-1}$, de manière à ce qu'aucun terme de $\tilde f_i$
ne soit divisible par l'un des $\initial(f_j)$ pour $j<i$ : cette
opération ne change pas $\initial(f_i)$ (puisque $\initial(f_i)$ n'est
multiple d'aucun des $\initial(f_j)$ pour $j<i$ d'après les opérations
du paragraphe précédent), et ne change pas le fait les éléments
forment une base de Gröbner ni l'idéal engendré ; puisque
$\initial(\tilde f_i) = \initial(f_i)$, le fait qu'on ait
$\initial(f_1) \preceq \cdots \preceq \initial(f_r)$ reste toujours
vrai.

Enfin (ou dans la même boucle) on parcourt les éléments et on remplace
$f_i$ par $f_i/c_i$ où $c_i$ est le coefficient initial de $f_i$.
\end{proof}

\begin{proposition2}\label{unicite-base-de-groebner-reduite}
Pour un idéal $I$ de $k[Z_1,\ldots,Z_d]$ et un ordre
admissible $\preceq$, il existe une unique base de Gröbner réduite (à
l'ordre des éléments près).
\end{proposition2}
\begin{proof}
L'existence a été prouvée dans le cadre de l'algorithme ci-dessus.

Supposons maintenant que $f_1,\ldots,f_r$ et $\tilde f_1,\ldots,\tilde
f_t$ soient deux bases de Gröbner réduites du même idéal, ordonnées
par $\initial(f_1) \preceq \initial(f_2) \preceq \cdots \preceq
\initial(f_r)$ et $\initial(\tilde f_1) \preceq \initial(\tilde f_2)
\preceq \cdots \preceq \initial(\tilde f_t)$.  On va montrer par
récurrence sur $i$ que $f_i = \tilde f_i$ pour $i \leq \min(r,t)$,
auquel cas il sera clair que $r=t$ (sinon les éléments supplémentaires
seraient engendrés par les précédents, ce qui contredit le fait que la
base est censément réduite).

Le monôme initial de $f_i$ est caractérisé par le fait qu'il s'agit du
plus petit monôme appartenant à $\initial(I)$ mais n'appartenant pas à
l'idéal engendré par $\initial(f_1),\ldots,\initial(f_{i-1})$.  Avec
l'hypothèse de récurrence, on voit donc qu'au moins $\initial(f_i) =
\initial(\tilde f_i)$ (les deux étant unitaires).

À présent, le polynôme $h = f_i - \tilde f_i$ appartient à $I$, et
$\initial(h) \prec \initial(f_i)$ : donc l'écriture standard de $h$
par rapport à $f_1,\ldots,f_r$ a un reste nul et ne fait intervenir
que $f_1,\ldots,f_{i-1}$ ; or l'hypothèse selon laquelle les bases
sont réduites interdit qu'il existe un terme de $h$ qui soit multiple
d'un $\initial(f_j)$ pour $j\neq i$ : donc on ne peut avoir que $h =
0$ et $\tilde f_i = f_i$.
\end{proof}

\begin{remarque2}
La base de Gröbner réduite d'un idéal $I$ (dans un anneau de polynômes
où on a fixé un ordre admissible) est évidemment minimale, pour
l'inclusion, parmi les bases de Gröbner de $I$ (si on en retire des
éléments, on ne peut plus avoir affaire à une base de Gröbner de $I$,
dans quoi les monômes initiaux de ces éléments seraient engendrés par
les monômes initiaux des autres).  Il faut se garder de croire,
cependant, qu'elle soit minimale pour l'inclusion parmi les familles
engendrant l'idéal $I$.  Par exemple, dans $\QQ[x,y]$ muni de l'ordre
lexicographique gradué pour lequel $x \succeq y$, les polynômes $x^2,
xy, y^2+x$ forment une base de Gröbner (de l'idéal qu'ils engendrent),
comme on le vérifie facilement avec le critère de Buchberger,
manifestement minimale, et pourtant le sous-ensemble $xy, y^2+x$
continue d'engendrer le même idéal puisque $x^2$ s'exprime comme
combinaison $\QQ[x,y]$-linéaire de ceux-ci.
\end{remarque2}

\XXX — Question complètement gratuite, comme ça : peut-on
caractériser les idéaux $I$ tels qu'aucun sous-ensemble strict de la
base de Gröbner réduite $B$ de $I$ n'engendre $I$ ?

\begin{proposition2}\label{bases-de-groebner-et-extensions-de-corps}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ et $B$ une base de Gröbner
(resp. la base de Gröbner réduite) de $I$ pour un certain ordre
monomial $\preceq$.  Alors, pour n'importe quelle extension de corps
$K$ de $k$, l'idéal $I \cdot K[Z_1,\ldots,Z_d]$ engendré par $I$ dans
$K[Z_1,\ldots,Z_d]$ admet encore $B$ pour base de Gröbner (resp. base
de Gröbner réduite), pour le même ordre monomial $\preceq$.
\end{proposition2}
\begin{remarque2}
Il est clair que $B$ engendre $I \cdot K[Z_1,\ldots,Z_d]$ dans
$K[Z_1,\ldots,Z_d]$.  Comme le critère de
Buchberger \ref{critere-de-buchberger} ne dépend pas du corps utilisé,
il s'agit encore d'une base de Gröbner, et de même elle est réduite
car cette condition ne dépend pas du corps utilisé.
\end{remarque2}


%
\subsection{Algorithmes fondamentaux}

Nous reprenons maintenant certains des problèmes posés dans la
section \ref{section-motivations-groebner} pour montrer en quoi les
bases de Gröbner sont utiles à leur résolution :

\subsubsection{Système canonique de générateurs} Donné un idéal $I =
(f_1,\ldots,f_r)$ de $k[Z_1,\ldots,Z_d]$ (et une fois choisi une fois
pour toutes un ordre admissibile $\preceq$), on sait en trouver une
base de Gröbner réduite d'après
\ref{algorithme-de-buchberger} et \ref{algorithme-reduction-base-de-groebner}.
Cette base est unique (si on trie ses éléments d'après leur monôme
initial) d'après \ref{unicite-base-de-groebner-reduite} : il s'agit
donc d'une représentation canonique de l'idéal $I$, qui permet, par
exemple, de tester l'égalité entre deux idéaux.

De plus, au cours de l'application des algorithmes (et surtout, à
l'intérieur de ceux-ci, de l'algorithme de
division \ref{algorithme-division}), on peut exprimer, si on le veut,
chaque nouveau polynôme introduit (notamment les restes des divisions)
comme combinaison des générateurs $f_1,\ldots,f_r$ de départ : on peut
ainsi relier la base choisie comme canonique (la base de Gröbner
réduite) à la base initiale donnée, et dans tous les calculs effectués
ensuite on pourra toujours, si on le souhaite, exprimer les membres de
l'idéal sur la base initiale.  (A contrario, le point suivant permet
d'exprimer la base initiale en fonction de la base de Gröbner
réduite.)

\subsubsection{Test d'appartenance et décompositions} Donné un $f \in
k[Z_1,\ldots,Z_d]$ et une fois obtenue une base de Gröbner de
l'idéal $I$, l'algorithme de division \ref{algorithme-division} permet
de tester si $f \in I$ et, le cas échéant, de donner une écriture de
$f$ sur la base en question.

\subsubsection{Anneau quotient}\label{algorithmes-fondamentaux-anneau-quotient} Les
classes modulo $I$ des monômes qui ne sont divisibles par le monôme
initial d'aucun élément de la base de Gröbner constituent une base
comme $k$-espace vectoriel de $k[Z_1,\ldots,Z_d]/I$, toujours d'après
l'algorithme de division \ref{algorithme-division} qui permet, en
outre, d'écrire les coordonnées sur cette base de la classe modulo $I$
d'un polynôme $f$ quelconque.

Cette base n'est pas forcément finie ($k[Z_1,\ldots,Z_d]/I$ peut être
de dimension finie ou non : en fait, il sera de dimension finie —
c'est-à-dire, artinien — exactement lorsque $I$ sera « de
  dimension $0$ » au sens de l'objet géométrique qu'il décrit), mais
même si elle est infinie, la base possède une description suffisamment
simple (il s'agit de $d$-uplets d'entiers naturels vérifiant une
combinaison booléenne d'inégalités) pour être aisément manipulable.

Ceci permet en outre d'effectuer les opérations dans l'anneau quotient
$k[Z_1,\ldots,Z_d]/I$ : l'addition, bien sûr, se fait terme à terme
sur la base évoquée, et la multiplication se fait en relevant à
$k[Z_1,\ldots,Z_d]$, en effectuant la multiplication dans celui-ci, et
en réduisant de nouveau par l'algorithme de division.


%
\subsection{Bases de Gröbner et élimination}

\subsubsection{} Si $I = (f_1,\ldots,f_r)$ est un idéal de
$k[Z_1,\ldots,Z_d]$ et $t \leq d$, l'idéal $J = I \cap
k[Z_1,\ldots,Z_t]$ est appelé un \emph{idéal d'élimination} de $I$.
Une interprétation intuitive de cette opération, justifiant le nom,
consiste à imaginer que $I$ décrit un ensemble de relations
algébriques entre les indéterminées $Z_1,\ldots,Z_d$ (relations
engendrées par les relations données $f_1,\ldots,f_r$) et que l'idéal
$J$ consiste en celles qui ne concernent que les $t$ premières
indéterminées : trouver des générateurs de $J$ revient donc à
« éliminer » les variables $Z_{t+1},\ldots,Z_d$ d'entre les équations
$f_1{=}0,\ldots,f_r{=}0$, et trouver les meilleures relations
possibles entre les $t$ variables restantes.  (En admettant certains
résultats de géométrie algébrique notamment le Nullstellensatz \XXX,
lorsque $k$ est algébriquement clos, l'ensemble $\mathscr{Z}(J)$ des
$t$-uplets $(z_1,\ldots,z_t)$ vérifiant les équations en question est
simplement l'adhérence pour la topologie de Zariski (c'est-à-dire le
plus petit $\mathscr{Z}(J)$ possible la contenant) de la projection
sur les $t$ premières coordonnées de l'ensemble $\mathscr{Z}(I)$ des
$d$-uplets $(z_1,\ldots,z_d)$ vérifiant $f_i(z_1,\ldots,z_d)=0$.)  Ce
problème de trouver des générateurs de $J$ est le problème fondamental
de la théorie de l'élimination.  Les bases de Gröbner fournissent un
algorithme permettant de le résoudre :

\begin{proposition2}\label{base-de-groebner-elimination}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ et $t\leq d$ : notons $J = I
\cap k[Z_1,\ldots,Z_t]$.  Alors on a $\initial_{\mathtexttt{lex}}(J) =
\initial_{\mathtexttt{lex}}(I) \cap k[Z_1,\ldots,Z_t]$ (où on est convenu
d'ordonner les variables de la manière $Z_1 \preceq Z_2 \preceq \cdots
\preceq Z_d$) ; et si $B = \{f_1,\ldots,f_r\}$ est une base de Gröbner
de $I$ pour l'ordre $\mathrel{\preceq_{\mathtexttt{lex}}}$, alors $B \cap
k[Z_1,\ldots,Z_t]$ est une base de Gröbner de $J$.

Plus généralement, ces affirmations (à $t$ fixé) valent pour tout
ordre admissible $\preceq$ vérifiant la propriété suivante : si
$\initial_{\preceq}(f) \in k[Z_1,\ldots,Z_t]$ alors $f \in
k[Z_1,\ldots,Z_t]$ (autrement dit, il ordonne chacun de
$Z_{t+1},\ldots,Z_d$ après tout monôme en $Z_1,\ldots,Z_t$).
\end{proposition2}
\begin{proof}
La propriété énoncée dans le second paragraphe est bien vérifiée (pour
tout $t$) par l'ordre lexicographique
d'après \ref{caracterisation-ordre-lexicographique-pur} : on va donc
montrer les résultats sous cette hypothèse.

Quitte à réordonner les $f_i$, convenons que $B \cap k[Z_1,\ldots,Z_t]
= \{f_1,\ldots,f_u\}$.

Il est clair que $(\initial(f_1),\ldots,\initial(f_u)) \subseteq
\initial(J) \subseteq \initial(I) \cap k[Z_1,\ldots,Z_t]$.  On va
montrer que $\initial(f_1),\ldots,\initial(f_u)$ engendrent
$\initial(I) \cap k[Z_1,\ldots,Z_t]$, c'est-à-dire
$(\initial(f_1),\ldots,\initial(f_u)) = \initial(J) = \initial(I) \cap
k[Z_1,\ldots,Z_t]$ : ceci prouvera à la fois que $f_1,\ldots,f_u$
forment une base de Gröbner de $J$ et que $J = I \cap
k[Z_1,\ldots,Z_t]$.

Soit $s \in \initial(I) \cap k[Z_1,\ldots,Z_t]$ un monôme (il suffit
de montrer que $\initial(f_1),\ldots,\initial(f_u)$ engendrent les
tels $s$, cf. \ref{equivalences-ideaux-monomiaux}) : comme
$\initial(f_1),\ldots,\initial(f_t)$ engendrent $\initial(I)$, il
existe $i$ tel que $\initial(f_i)$
divise $s$ (\ref{composition-ideaux-monomiaux}).  Puisque $s \in
k[Z_1,\ldots,Z_t]$, on a aussi $\initial(f_i) \in k[Z_1,\ldots,Z_t]$,
et l'hypothèse faite sur $\preceq$ impose $f_i \in k[Z_1,\ldots,Z_t]$,
c'est-à-dire $i\leq u$.
\end{proof}

\XXX — Eisenbud (proposition 15.29) prétend utiliser la
proposition \ref{inclusion-ideaux-et-egalite-ideaux-initiaux}
(lemme 15.5 chez lui).  Je ne vois pas où ça sert : me suis-je trompé
dans cette démonstration ?

(Une façon parfois plus efficace que l'ordre lexicographique pur,
\emph{si on connaît $t$ à l'avance}, consiste à prendre l'ordre sur le
degré total en les seules variables $Z_1,\ldots,Z_t$ comme premier
critère de comparaison, et en cas d'égalité comparer avec
$\mathrel{\preceq_{\mathtexttt{grevlex}}}$.)

\begin{corollaire2}\label{projection-et-extensions-de-corps}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ et $t\leq d$ : notons $J = I
\cap k[Z_1,\ldots,Z_t]$.  Alors, pour n'importe quelle extension de
corps $K$ de $k$, on a $J \cdot K[Z_1,\ldots,Z_t] = (I \cdot
K[Z_1,\ldots,Z_d]) \cap K[Z_1,\ldots,Z_t]$.
\end{corollaire2}
\begin{proof}
C'est une conséquence immédiate de la proposition précédente et
de \ref{bases-de-groebner-et-extensions-de-corps}.
\end{proof}


%
\subsection{Ajout d'une variable et calcul d'inverse}

\XXX — Il est tout pourri le titre de cette section !

\begin{proposition2}\label{borne-degre-base-groebner-sur-une-variable-dominante}
Soit $\preceq$ un ordre monomial sur $k[Z_1,\ldots,Z_d,Y]$ tel que $Y$
soit supérieur à tout monôme en $Z_1,\ldots,Z_d$.  Soient
$h_1,\ldots,h_n \in k[Z_1,\ldots,Z_d,Y]$ tels que $\deg_Y(h_i) \leq N$
pour tout $i$, où $N$ est une certaine constante (ici, $\deg_Y(h)$
désigne le degré partiel du polynôme $h$ en la variable $Y$).  Alors
la base de Gröbner $f_1,\ldots,f_r$ réduite de $I = (h_1,\ldots,h_n)$
vérifie également $\deg_Y(f_i) \leq N$ pour tout $i$.
\end{proposition2}
\begin{proof}
L'hypothèse effectuée sur l'ordre garantit que $\deg_Y(h) =
\deg_Y(\initial(h))$ pour tout $h$.  Il suffit de montrer que, dans
l'algorithme de Buchberger \ref{algorithme-de-buchberger}, aucun
polynôme de degré en $Y$ strictement supérieur à $N$ n'est jamais
ajouté à la base (et que, dans l'algorithme de
réduction \ref{algorithme-reduction-base-de-groebner} ou, en fait,
dans l'algorithme de division \ref{algorithme-division}, on n'augmente
jamais le degré en $Y$, mais c'est évident).  Le point essentiel à
vérifier est donc que si $h_i$ et $h_j$ vérifient $\deg_Y(h_i) \leq N$
alors le $S$-polynôme $S(h_i,h_j)$ défini
en \ref{definition-s-polynome} vérifie la même inégalité.  Mais son
terme initial est strictement inférieur à $\ppcm(\initial(h_i),
\initial(h_j))$, lequel a bien un degré en $Y$ majoré par $N$, donc
c'est le cas de $S(h_i,h_j)$.
\end{proof}

\XXX — Ce serait mieux de donner une démontration qui n'utilise pas
la construction algorithmique.

\begin{algorithme2}\label{algorithme-calcul-inverse-algebre-de-type-fini}
Donné un idéal $I$ (défini par ses générateurs) de
$k[Z_1,\ldots,Z_d]$, et $x$ un élément de $k[Z_1,\ldots,Z_d]/I$, on
peut déterminer si $x$ est inversible dans cette algèbre et, le cas
échéant, en calculer un inverse.
\end{algorithme2}
\begin{proof}[Description de l'algorithme]
Introduisons une nouvelle variable $Y$ : soit $\tilde I$ l'idéal de
$k[Z_1,\ldots,Z_d,Y]$ engendré par $I$ (c'est-à-dire, par les
générateurs donnés de $I$) et par $\hat x Y - 1$ (où $\hat x$ est un
relèvement quelconque de $x$ à $k[Z_1,\ldots,Z_d]$, étant évident que
$\tilde I$ ne dépend pas de ce choix).  On calcule la base de Gröbner
réduite $\tilde B$ de $\tilde I$ pour un ordre monomial $\preceq$
quelconque qui ordonne $Y$ après n'importe quel monôme en
$Z_1,\ldots,Z_d$.  Cette base est de la forme $B' \cup C$ où $B' =
\tilde B \cap k[Z_1,\ldots,Z_d]$ est la base de Gröbner réduite de $I'
= \tilde I \cap k[Z_1,\ldots,Z_d]$ (pour le même ordre monomial,
c'est-à-dire, pour sa restriction aux monômes en $Z_1,\ldots,Z_d$) et
$C$ est formé de polynômes dont le degré partiel en $Y$ vaut
exactement $1$.  L'élément $x$ est inversible si et seulement si $I' =
I$ (ce qui se teste en vérifiant que les bases de Gröbner réduites
coïncident) et que $C$ est (soit vide, soit) réduit à un unique
polynôme de la forme $Y - g$ avec $g \in k[Z_1,\ldots,Z_d]$ ; et
lorsque c'est le cas, la classe de $g$ modulo $I$ est l'inverse
recherché (quant au cas où $I'=I$ et $C$ est vide, il ne se produit
que lorsque $k[Z_1,\ldots,Z_d]/I$ est l'algèbre nulle, ce cas étant
trivial).
\end{proof}
\begin{proof}
On sait d'après \ref{base-de-groebner-elimination} que l'ensemble $B'
= \tilde B \cap k[Z_1,\ldots,Z_d]$ des éléments de $\tilde B$ ne
faisant intervenir que les variables $Z_1,\ldots,Z_d$ est la base de
Gröbner réduite de $I' = \tilde I \cap k[Z_1,\ldots,Z_d]$ (soulignons
que cet idéal contient $I$).  On sait aussi
d'après \ref{borne-degre-base-groebner-sur-une-variable-dominante} que
les degrés en $Y$ des éléments de $\tilde B$ sont majorés par $1$.  On
pose $C = \tilde B \setminus B'$ l'ensemble des éléments de $\tilde B$
faisant effectivement intervenir $Y$.

Notons $A = k[Z_1,\ldots,Z_d]/I$ : on a alors
$k[Z_1,\ldots,Z_d,Y]/\tilde I = A[Y]/(xY-1)$.  Soit $\varphi \colon A
\to A[Y]/(xY-1)$ le morphisme évident.  L'idéal $I'$ est l'image
réciproque dans $k[Z_1,\ldots,Z_d]$ du noyau de $\varphi$.

Supposons d'abord $x$ inversible dans $A$, d'inverse $x^{-1}$ : alors
$A[Y]/(xY-1) = A[Y]/(Y-x^{-1})$ et $\varphi$ est un isomorphisme.  En
particulier, $I' = I$ (puisque $\varphi$ est injectif).  D'autre part,
si $g \in k[Z_1,\ldots,Z_d]$ représente $x^{-1}$ modulo $I$, alors $Y
- g$ est dans $\tilde I$.  Cet élément a pour monôme initial $Y$ donc
il y a dans $\tilde B$ a un élément de monôme initial $Y$ (sauf si $A$
est l'algèbre nulle, cas que nous écarterons), donc dans $C$ ; et
comme la base de Gröbner $\tilde B$ était supposée réduite, cet
élément est l'unique élément de $C$, et il est manifestement de la
forme $Y - g$ avec $g$ représentant $x^{-1}$ modulo $I$.

Réciproquement, supposons que $I' = I$, c'est-à-dire que $\varphi$ est
injective, et que $C$ contient un élément de la forme $Y - g$ : alors
$\varphi$ envoie la classe de $g$ sur celle de $Y$, donc $\varphi$ est
surjectif, et c'est un isomorphisme.  En particulier, $x$ est
inversible d'inverse $\varphi^{-1}(Y)$.
\end{proof}


\section{Idéaux de dimension $0$}

\subsection{Fonction et polynôme de Hilbert-Samuel}

\begin{definition2}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$.  On appelle \emph{fonction
  de Hilbert-Samuel affine} de $I$ la fonction qui à un entier
naturel $\ell$ associe la dimension du $k$-espace vectoriel engendré
par les classes modulo $I$ de monômes de degré total $\leq\ell$.
\end{definition2}

Lorsque $I$ est l'idéal nul, la fonction de Hilbert-Samuel affine
de $I$ compte le nombre total de monômes de degré total $\leq\ell$
en $d$ variables, autrement dit, le nombre de $d$-uplets d'entiers
naturels de somme $\leq\ell$ : un raisonnement combinatoire classique
(\XXX — l'expliciter ?)  montre que ce nombre vaut
$\frac{(\ell+d)!}{\ell!\,d!} =
\frac{1}{d!}\ell(\ell-1)\cdots(\ell-d+1)$, qui est un polynôme de
degré $d$ en $\ell$ et de terme dominant $\frac{1}{d!} \ell^d$.

De façon plus générale, si $I$ est un idéal quelconque et
$f_1,\ldots,f_r$ une base de Gröbner de $I$ dont on note $c_i s_i =
\initial(f_i)$ le terme dominant (avec $s_i$ un monôme), la fonction
de Hilbert-Samuel affine de $I$ compte (cf. par
exemple \ref{algorithmes-fondamentaux-anneau-quotient}) le nombre de
monômes de degré total $\leq\ell$ en $d$ variables qui ne sont
divisibles par aucun des monômes $s_1,\ldots,s_r$, autrement dit, le
nombre de $d$-uplets $(v_1,\ldots,v_d)$ d'entiers naturels de
somme $\leq\ell$ tels que pour tout $1\leq i\leq r$ il existe $1\leq
j\leq d$ avec $v_i < w_{ij}$, où on a noté $w_{ij}$ les exposants de
$s_i$, soit $s_i = Z_1^{w_{i1}} \cdots Z_d^{w_{id}}$.  Par un
raisonnement purement combinatoire, on peut montrer :
\begin{proposition2}\label{polynomialite-hilbert-samuel}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$.  Il existe un polynôme,
prenant des valeurs entières sur tous les entiers, dont le terme
dominant est de la forme $\frac{A}{\delta!} \ell^\delta$ avec
$0\leq\delta\leq d$ et $A$ un entier naturel, et de plus $\delta=d$ si
et seulement si $I=0$, qui coïncide pour $\ell$ assez grand avec la
fonction de Hilbert-Samuel affine de $I$.
\end{proposition2}

\XXX — Le prouver ?

\begin{definition2}\label{definition-polynome-hilbert-samuel-affine}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$.  Le polynôme (manifestement
unique) coïncidant pour $\ell$ grand avec la fonction de
Hilbert-Samuel affine de $I$, et dont l'existence est garantie par la
proposition \ref{polynomialite-hilbert-samuel}, est appelé
\emph{polynôme de Hilbert-Samuel affine} de $I$.

Son degré $\delta$ est appelé \emph{dimension affine} de $I$, et
l'entier naturel $A$ tel que le coefficient dominant soit
$\frac{A}{\delta!} \ell^\delta$ est appelé \emph{degré} (affine en
dimension $\delta$) de $I$.
\end{definition2}


\subsection{Idéaux de dimension $0$ et algèbres finies}

\begin{proposition2}\label{equivalences-ideaux-affines-dimension-zero}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$.  Les affirmations suivantes
sont équivalentes :
\begin{itemize}
\item l'espace vectoriel quotient $k[Z_1,\ldots,Z_d]/I$ est de
  dimension finie sur $k$,
\item la dimension affine de $I$ (au sens
  de \ref{definition-polynome-hilbert-samuel-affine}) vaut $0$,
\item (pour $f_1,\ldots,f_r$ une base de Gröbner quelconque de $I$
  pour un ordre monomial quelconque :) pour tout $1\leq j\leq d$ il
  existe un $1\leq i\leq r$ tel que le monôme initial de $f_i$ soit
  une puissance de $Z_j$.
\end{itemize}
De plus, dans ces conditions, le degré de $I$ (au sens
de \ref{definition-polynome-hilbert-samuel-affine}) est égal à la
dimension du $k$-espace vectoriel $k[Z_1,\ldots,Z_d]/I$.
\end{proposition2}
\begin{proof}
Pour ce qui est de l'équivalence entre les deux premiers énoncés, il
est clair que la dimension de $k[Z_1,\ldots,Z_d]/I$ vaut (comme
élément de $\NN \cup \{+\infty\}$) la limite de la fonction de
Hilbert-Samuel affine de $I$, qui est bien sûr aussi la limite du
polynôme de Hilbert-Samuel affine de $I$ : ceci se produit si et
seulement si son degré $\delta$ vaut $0$, auquel cas sa limite est
égale à son coefficient constant (et unique) $A$.

Montrons maintenant l'équivalence avec le troisième énoncé.  Si
$k[Z_1,\ldots,Z_d]/I$ est de dimension finie, si $1\leq j\leq d$, la
famille (des classes) de $Z_j^u$ pour $u$ parcourant les entiers
naturels, ne peut pas être libre, donc il existe un polynôme en $Z_j$
qui appartienne à $I$, et si on appelle $Z_j^u$ son monôme initial,
celui-ci doit être divisible par le monôme initial d'un certain $f_i$
de la base de Gröbner donnée, qui est donc lui-même une puissance
de $Z_j$.  Réciproquement, si pour tout $j$ il existe $i$ tel que
$f_i$ ait pour monôme initial une puissance de $Z_j$, disons
$Z_j^{u_j}$, alors les monômes de la forme $Z_1^{v_1} \cdots
Z_d^{v_d}$, où $v_j<u_j$ pour chaque $j$, qui sont en nombre fini,
engendrent $k[Z_1,\ldots,Z_d]/I$ (cf. par
exemple \ref{algorithmes-fondamentaux-anneau-quotient}), donc
$k[Z_1,\ldots,Z_d]/I$ est bien de dimension finie.
\end{proof}

\begin{remarque2}
On verra ailleurs (\XXX) que dans le contexte de la proposition
ci-dessus sont encore équivalents les énoncés suivants :
\begin{itemize}
\item l'anneau quotient $k[Z_1,\ldots,Z_d]/I$ est artinien (i.e.,
  toute suite décroissante d'idéaux de cet anneau stationne),
\item tout idéal premier de $k[Z_1,\ldots,Z_d]/I$ est maximal (i.e.,
  sa dimension de Krull vaut $0$).
\end{itemize}
\end{remarque2}

\begin{remarque2}
La troisième propriété
de \ref{equivalences-ideaux-affines-dimension-zero} est
algorithmiquement triviale à tester dès lors qu'on dispose d'une base
de Gröbner de $I$ (en fait, de façon générale, la dimension affine ou
même le polynôme de Hilbert-Samuel affine sont calculables une fois
connue une base de Gröbner, mais le cas particulier de la
dimension $0$ est exceptionnellement simple avec le critère qu'on
vient de présenter).
\end{remarque2}

\begin{proposition2}\label{projection-de-dimension-0}
Soit $I$ un idéal de dimension $0$ de $k[Z_1,\ldots,Z_d]$.  Alors pour
tout $t\leq d$, l'idéal d'élimination $J = I \cap k[Z_1,\ldots,Z_t]$
est lui aussi de dimension $0$.  En particulier (pour $t\geq 1$), il
n'est pas nul.
\end{proposition2}
\begin{proof}
Une fois choisi un ordre convenable (par exemple l'ordre
lexicographique) sur les monômes, comme expliqué
en \ref{base-de-groebner-elimination}, une base de Gröbner de $J$
s'obtient en considérant ceux des éléments d'une base de Gröbner
de $I$ qui appartiennent à $k[Z_1,\ldots,Z_t]$.  Mais la dernière
condition de \ref{equivalences-ideaux-affines-dimension-zero} est
alors manifestement satisfaite de $J$ si elle l'est de $I$.
\end{proof}

L'énoncé suivant, passablement évident, permet de généraliser certains
faits énoncés ci-dessus à un anneau quelconque en se passant de la
notion de base de Gröbner :
\begin{proposition2}\label{trivialite-algebres-finies-libres}
Soit $k$ un anneau et $I$ un idéal de $k[Z_1,\ldots,Z_d]$ engendrée
par des polynômes $f_1,\ldots,f_d$ où $f_i$ est un polynôme ne faisant
intervenir que $Z_1,\ldots,Z_i$ et qui, vu comme polynôme en $Z_i$,
est unitaire de degré $\delta_i$.  Alors $k[Z_1,\ldots,Z_d]/I$ est
libre en tant que $k$-module et de dimension finie $\prod_{i=1}^d
\delta_i$, avec pour base l'ensemble des (classes modulo $I$ des)
monômes $Z_1^{j_1} \cdots Z_d^{j_d}$ où $j_i < \delta_i$ pour
chaque $i$.
\end{proposition2}
\begin{proof}
On procède par récurrence sur $d$ : si $I'$ est l'idéal engendré par
$f_1,\ldots,f_{d-1}$ alors $k[Z_1,\ldots,Z_d]/I = K[Z_d]/(f_d)$ où $K$
est l'anneau $k[Z_1,\ldots,Z_{d-1}]/I'$.  L'hypothèse de récurrence
montre que $K$ est un $k$-module libre de base l'ensemble des
$Z_1^{j_1} \cdots Z_{d-1}^{j_{d-1}}$ (où $j_i < \delta_i$ pour $1\leq
i \leq d-1$), et l'hypothèse faite sur $f_d$ rend clair le fait que
$K[Z_d]/(f_d)$ est un $K$-module libre de base formée des $Z_d^j$ avec
$j<\delta$ : ceci montre bien que $k[Z_1,\ldots,Z_d]/I$ est un
$k$-module libre de base l'ensemble des $Z_1^{j_1} \cdots Z_d^{j_d}$.
\end{proof}


\subsection{Algèbre de décomposition universelle d'un polynôme}\label{section-algebre-de-decomposition-universelle}

\begin{lemme2}\label{lemme-modules-de-cauchy}
Soit $\mathfrak{F}(W_1,\ldots,W_d|T) = \prod_{i=1}^d(T-W_i) \in
\ZZ[W_1,\ldots,W_d,T]$, et définissons par récurrence sur $i$
\[
\begin{array}{c}
\mathfrak{F}_1(\underline{W}|T_1) =
\mathfrak{F}(\underline{W}|T_1)\\[.75ex]
\displaystyle
\mathfrak{F}_{i+1}(\underline{W}|T_1,\ldots,T_{i+1})
= \frac{\mathfrak{F}_i(\underline{W}|T_1,\ldots,T_{i-1},T_i) -
  \mathfrak{F}_i(\underline{W}|T_1,\ldots,T_{i-1},T_{i+1})}{T_i - T_{i+1}}
\end{array}
\]
(où $\underline{W}$ est une abréviation pour $W_1,\ldots,W_d$).  Alors
$\mathfrak{F}_i(W_1,\ldots,W_d | T_1,\ldots,T_i)$ (défini pour $1\leq
i \leq d$) est un polynôme à coefficients entiers en les variables
$W_1,\ldots,W_d$ et $T_1,\ldots,T_i$, et il est complètement
symétrique en chacun de ces jeux de variables.  On a exactement
\[
\mathfrak{F}_i(W_1,\ldots,W_d | T_1,\ldots,T_i)
= \sum_{j=0}^{d-i+1} (-1)^j e_j(W_1,\ldots,W_d)\, h_{d-i+1-j}(T_1,\ldots,T_i)
\]
où $e_j$ désigne le $j$-ième polynôme symétrique élémentaire (et $e_0
= 1$) et $h_j$ le $j$-ième polynôme symétrique complet (c'est-à-dire
la somme de tous les monômes de degré $j$ en ses variables ; on pose
notamment $h_0 = 1$).

De plus, si $u_1,\ldots,u_i$ sont deux à deux distincts, alors
$\mathfrak{F}_i(W_1,\ldots,W_d | W_{u_1},\ldots,W_{u_i}) = 0$.

Enfin, l'unique polynôme $\mathfrak{C}_i(E_1,\ldots,E_d |
T_1,\ldots,T_i)$ à coefficients entiers en les variables
$E_1,\ldots,E_d$ et $T_1,\ldots,T_i$ qui vérifie
$\mathfrak{C}_i(e_1(\underline{W}),\ldots,e_d(\underline{W}) |
T_1,\ldots,T_i) = \mathfrak{F}_i(W_1,\ldots,W_d | T_1,\ldots,T_i)$ est
donné par
\[
\mathfrak{C}_i(E_1,\ldots,E_d | T_1,\ldots,T_i)
= h_{d-i+1}(T_1,\ldots,T_i) +
\sum_{j=1}^{d-i+1} (-1)^j E_j \, h_{d-i+1-j}(T_1,\ldots,T_i)
\]
et on a
\begin{align*}
X^d + \sum_{i=1}^d (-1)^i E_i X^{d-i} &=
\mathfrak{C}_1(\underline{E} | T_1) + (X-T_1)\,
\mathfrak{C}_2(\underline{E} | T_1,T_2) \\[-1.5ex]
& + \cdots + (X-T_1)\cdots(X-T_{d-1})\, \mathfrak{C}_d(\underline{E} |
T_1,\ldots,T_{d-1})\\
&+ (X-T_1)\cdots(X-T_d)
\end{align*}
(où $\underline{E}$ est une abréviation pour $E_1,\ldots,E_d$).
\end{lemme2}
\begin{proof}
Commençons par montrer la relation
\[
\mathfrak{F}_i(W_1,\ldots,W_d | T_1,\ldots,T_i)
= \sum_{j=0}^{d-i+1} (-1)^j e_j(W_1,\ldots,W_d)\, h_{d-i+1-j}(T_1,\ldots,T_i)
\]
par récurrence sur $i$.  Pour $i=1$, il s'agit simplement de la
relation $\prod_{i=1}^d(T-W_i) = \sum_{j=0}^d (-1)^j
e_j(W_1,\ldots,W_d)\, T^{d-j}$ entre coefficients d'un polynôme et
fonctions symétriques de ses racines.  La relation de récurrence
découle de
\[
(T_i - T_{i+1})\, h_n(T_1,\ldots,T_{i+1}) = h_{n+1}(T_1,\ldots,T_{i-1},T_i)
- h_{n+1}(T_1,\ldots,T_{i-1},T_{i+1})
\]
(ce qui traduit pour le membre de droite de l'égalité ci-dessus la
même relation de récurrence que pour $\mathfrak{F}_i$).  Pour montrer
cette relation, on écrit $h_{n+1}(T_1,\ldots,T_{i-1},T') =
\sum_{u=0}^{n+1} T^{\prime u} h_{n+1-u}(T_1,\ldots,T_{i-1})$, on
remplace $T'$ par $T_i$ et $T_{i+1}$ et on utilise $T_i^u - T_{i+1}^u
= (T_i - T_{i+1}) h_{u-1} (T_i,T_{i+1})$ ; enfin, $\sum_{u=1}^{n+1}
h_{u-1} (T_i,T_{i+1}) h_{n+1-u}(T_1,\ldots,T_{i-1}) =
h_n(T_1,\ldots,T_{i+1})$.

La relation en question montre bien que
$\mathfrak{F}_i(\underline{W}|\underline{T})$ est un polynôme à
coefficients entiers complètement symétrique en chaque jeu de
variables (\textit{a priori} il était défini comme fonction
rationnelle, à coefficients rationnels, de ces jeux de variables).

Le fait que $\mathfrak{F}_i$ s'annule identiquement si on substitute
aux $T_j$ un sous-ensemble des $W_j$ vient de ce que $\mathfrak{F}_1$
s'annule trivialement dans ce cas, et que la relation de récurrence
s'applique avec cette spécialisation (les dénominateurs $W_{u_i} -
W_{u_{i+1}}$ sont inversibles dans les fractions rationnelles sur
$W_1,\ldots,W_d$).

L'existence et l'unicité du polynôme $\mathfrak{C}_i$ tel que
$\mathfrak{C}_i(e_1(\underline{W}),\ldots,e_d(\underline{W}) |
T_1,\ldots,T_i) = \mathfrak{F}_i(W_1,\ldots,W_d | T_1,\ldots,T_i)$
découle du fait que $\mathfrak{F}_i$ est complètement symétrique dans
les variables $W_j$ et que les $e_j(\underline{W})$ egendrent
linéairement les polynômes en question.  L'expression trouvée pour
$\mathfrak{F}_i$ donne alors immédiatement l'expression annoncée pour
$\mathfrak{C}_i$.

Enfin, pour montrer la dernière expression annoncée, remarquons que
$X^d + \sum_{i=1}^d (-1)^i E_i X^{d-i} =
\mathfrak{C}_1(\underline{E}|X)$ (d'après l'expression qu'on vient de
montrer) et que pour chaque $i$ on a
$\mathfrak{C}_i(\underline{E}|T_1,\ldots,T_{i-1},X) =
\mathfrak{C}_i(\underline{E}|T_1,\ldots,T_i) + (X-T_i)\,
\mathfrak{C}_{i+1}(\underline{E}|T_1,\ldots,T_i,X)$ (d'après la
formule de récurrence des $\mathfrak{F}_i$), en convenant que
$\mathfrak{C}_{d+1}(E_1,\ldots,E_d|\ldots)$ vaut identiquement $0$ :
en appliquant successivement cette formule pour $i$ allant de $1$ à
$d$ on trouve ce qu'on voulait.
\end{proof}

\begin{proposition2}\label{relations-algebre-de-decomposition-universelle}
Soit $k$ un corps et $f \in k[X]$ un polynôme unitaire, disons $f =
X^d + a_1 X^{d-1} + \cdots + a_d$.  On considère l'idéal $I$ de
$k[Z_1,\ldots,Z_d]$ engendré par les relations $e_i = (-1)^i a_i$ où
$e_i$ désigne le $i$-ième polynôme symétrique élémentaire en
$Z_1,\ldots,Z_d$.  Alors $I$ est de dimension $0$, et la base de
Gröbner réduite de $I$ pour l'ordre lexicographique (où on est convenu
d'ordonner les variables de la manière $Z_1 \preceq Z_2 \preceq \cdots
\preceq Z_d$) est fournie par les
\[
q_i := h_i(Z_1,\ldots,Z_{d-i+1}) + \sum_{j=1}^i a_j h_{i-j}(Z_1,\ldots,Z_{d-i+1})
\]
où $h_n$ est le $n$-ième polynôme homogène symétrique complet de
$Z_1,\ldots,Z_d$, c'est-à-dire la somme de tous les monômes de degré
$i$ en ces variables (on pose notamment $h_0=1$), et
$h_n(Z_1,\ldots,Z_{d-i+1})$ signifie qu'il est évalué en remplaçant
les $i-1$ dernières variables par $0$.  (Notamment, une de ces
relations, $q_d$, est donnée par $f(Z_1) = 0$.)

Si $k$ est simplement un anneau et qu'on définit l'idéal $I$ de
$k[Z_1,\ldots,Z_d]$ engendré par les $e_i = (-1)^i a_i$, alors il est
encore engendré par les $q_i$ définis ci-dessus\footnote{Selon toute
définition raisonnable, les $q_i$ seraient une base de Gröbner
de $I$, mais nous avons préféré ne pas définir cette notion.}.
\end{proposition2}
\begin{proof}
Dans un premier temps, supposons simplement que $k$ est un anneau.

Avec les notations du lemme précédent, remarquons que $q_i =
\mathfrak{C}_{d-i+1}(-a_1,\ldots,(-a)^d\,a_d | Z_1,\ldots,Z_{d-i+1})$.

On en déduit l'observation suivante : si $C$ est une $k$-algèbre et si
on a $f(X)$ s'écrit comme $\prod_{i=1}^d (X - z_i) \in C[X]$ pour
certains $z_1,\ldots,z_d \in C$, alors $q_i(z_1,\ldots,z_{d-i+1}) = 0
\in C$.  En effet, on a $e_i(z_1,\ldots,z_d) = (-1)^i a_i$ donc
$q_i(z_1,\ldots,z_{d-i+1}) =
\mathfrak{C}_{d-i+1}(-a_1,\ldots,(-a)^d\,a_d | z_1,\ldots,z_{d-i+1}) =
\mathfrak{F}_{d-i+1}(z_1,\ldots,z_d | z_1,\ldots,z_{d-i+1}) = 0$.

Appelons maintenant $J$ l'idéal engendré par $q_1,\ldots,q_d$, et
posons $A = k[Z_1,\ldots,Z_d]/I$ et $B = k[Z_1,\ldots,Z_d]/J$.  Il est
clair que $f(X) = \prod_{i=1}^d (X-Z_i) \in A[X]$ en développant le
membre de droite : d'après ce qu'on vient de montrer, $q_i$ s'annule
dans $A$ (c'est-à-dire, appartient à $I$), donc $J \subseteq I$.

Mais d'autre part, si dans l'égalité $X^d + \sum_{i=1}^d (-1)^i E_i
X^{d-i} = \mathfrak{C}_1(\underline{E} | T_1) + (X-T_1)\,
\mathfrak{C}_2(\underline{E} | T_1,T_2) + \cdots +
(X-T_1)\cdots(X-T_{d-1})\, \mathfrak{C}_d(\underline{E} |
T_1,\ldots,T_{d-1}) + (X-T_1)\cdots(X-T_d)$ (qui a lieu dans
$\ZZ[E_1,\ldots,E_d,T_1,\ldots,T_d,X]$) on remplace chaque $E_i$ par
$(-1)^i a_i$ et chaque $T_i$ par $Z_i$, on trouve $f(X) = q_d +
(X-Z_1)\, q_{d-1} + \cdots + (X-Z_1)\cdots(X-Z_{d-1})\, q_1 +
(X-Z_1)\cdots(X-Z_d)$.  En particulier, dans $B$, on a $f(X) = (X-Z_1)
\cdots (X-Z_d)$, c'est-à-dire que $e_i(Z_1,\ldots,Z_d) = (-1)^i a_i$,
ou encore que cette relation est dans $J$.  On vient donc de montrer
$I \subseteq J$.

À ce stade, nous savons que $I$ coïncide avec l'idéal $J$ engendré par
$q_1,\ldots,q_d$.  Il reste encore à montrer que, lorsque $k$ est un
corps, les $q_i$ sont une base de Gröbner de $I=J$.  Mais le terme
initial de $q_i$ vaut $Z_{d-i+1}^i$, ces monômes sont deux à deux
premiers entre eux, et
\ref{division-avec-termes-de-tete-premiers-entre-eux} permet de
conclure qu'ils forment une base de Gröbner.
\end{proof}

\begin{exemple2}\label{exemple-algebre-de-decomposition-universelle-non-connexe}
Si $f = X^3 + X^2 -2 X -1$, la base de Gröbner donnée ci-dessus est
formée des trois relations : $q_3 = Z_1^3 + Z_1^2 - 2 Z_1 - 1$
(c'est-à-dire $f(Z_1)$), $q_2 = Z_2^2 + Z_1 Z_2 + Z_2 + Z_1^2 + Z_1 -
2$ et $q_1 = Z_3 + Z_2 + Z_1 + 1$.
\end{exemple2}

\begin{definition2}\label{definition-algebre-de-decomposition-universelle}
Si $k$ est un anneau et $f \in k[X]$ un polynôme unitaire de degré $d$
dont on note $a_i$ le coefficient de degré $d-i$, l'algèbre
$k[Z_1,\ldots,Z_d]/I$, où $I$ est l'idéal (décrit
en \ref{relations-algebre-de-decomposition-universelle}) engendré par
les relations $e_i = (-1)^i a_i$, ou bien par les $q_i$ définis
ci-dessus, est appelée \emph{algèbre de décomposition universelle}
de $f$.
\end{definition2}

\begin{corollaire2}\label{algebre-de-decomposition-universelle-est-finie}
Soit $k$ est un anneau et $f \in k[X]$ un polynôme unitaire de
degré $d$.  Si $k[Z_1,\ldots,Z_d]/I$ désigne son algèbre de
décomposition universelle définie
en \ref{definition-algebre-de-decomposition-universelle}, alors
celle-ci est libre de dimension $d!$ comme $k$-module.  Plus
précisément, une base comme $k$-module en est donnée par les (classes
modulo $I$ des) monômes $Z_1^{j_1} Z_2^{j_2} \cdots Z_{d-1}^{j_{d-1}}$
avec $j_i \leq d-i$.
\end{corollaire2}
\begin{proof}
Ceci découle immédiatement de la
proposition \ref{trivialite-algebres-finies-libres} appliquée aux
générateurs $q_1,\ldots,q_d$ trouvés
en \ref{relations-algebre-de-decomposition-universelle} puisque chaque
$q_{d-i+1}$ ne fait intervenir que $Z_1,\ldots,Z_i$ et est unitaire de
degré $d-i+1$ en $Z_i$.
\end{proof}

\begin{remarque2}\label{definition-recursive-algebre-de-decomposition-universelle}
On peut préférer la définition suivante de l'algèbre de décomposition
universelle d'un polynôme unitaire $f = X^d + a_1 X^{d-1} + \cdots +
a_d \in k[X]$ (avec $k$ un anneau quelconque) par récurrence sur son
degré $d$ : si $d=0$ (de sorte que $f$ est le polynôme $1$) on définit
simplement l'algèbre de décomposition universelle de $f$ comme $k$
lui-meme ; et si $d>0$, on note $K = k[X]/(f)$ l'algèbre de rupture de
$f$ et $x$ la classe de $X$ dans $K$ et $g = X^{d-1} + b_1 X^{d-2} +
\cdots + b_{d-1}$ le polynôme de $K[X]$ défini par $b_i = a_i + x
a_{i-1} + \cdots + x^{i-1} a_1 + x^i$ pour tout $1 \leq i \leq d-1$
(de sorte que $f = (X-x) g$ comme il est facile de vérifier), et
l'algèbre de décomposition de $f$ sur $k$ est alors définie comme
celle de $g$ sur $K$.  (Avec cette définition, le
corollaire \ref{algebre-de-decomposition-universelle-est-finie} est
clair.)

Pour montrer que les deux définitions coïncident, c'est-à-dire pour
montrer que la propriété de récurrence qui vient d'être donnée est
bien vérifiée pour l'algèbre de décomposition universelle telle que
définie en \ref{definition-algebre-de-decomposition-universelle}, on
utilise la proposition suivante (qui, si on appelle $Z_d$ plutôt que
$X$ la variable dans l'algèbre de rupture, exprime le fait que nos
deux présentations coïncident exactement) :
\end{remarque2}

\begin{proposition2}
Soit $k$ un anneau et $f = X^d + a_1 X^{d-1} + \cdots + a_d \in k[X]$
un polynôme unitaire de degré $d$.  Alors l'idéal $I$ de
$k[Z_1,\ldots,Z_d]$ engendré par les $e_i(Z_1,\ldots,Z_d) - (-1)^i
a_i$ coïncide avec celui $J$ engendré par les $e_i(Z_1,\ldots,Z_{d-1})
- (-1)^i b_i$ où $b_i = a_i + a_{i-1} Z_d + \cdots + a_1 Z_d^{i-1} +
Z_d^i$ et par $f(Z_d)$.
\end{proposition2}
\begin{proof}
Convenons de noter $e_i^{[d]}$ pour $e_i(Z_1,\ldots,Z_d)$ et
$e_i^{[d-1]}$ pour $e_i(Z_1,\ldots,Z_{d-1})$.  On a $e_i^{[d]} =
e_i^{[d-1]} + Z_d e_{i-1}^{[d-1]}$ et $a_i = b_i - Z_d b_{i-1}$ : donc
$(e_i^{[d]} - (-1)^i a_i) = (e_i^{[d-1]} - (-1)^i b_i) + Z_d
(e_{i-1}^{[d-1]} - (-1)^{i-1} b_{i-1})$ — ceci montre que les
$e_i^{[d-1]} - (-1)^i b_i$ engendrent les $e_i^{[d]} - (-1)^i a_i$ (la
relation $f(Z_d)$ sert lorsque $i=d$ pour annuler le terme $b_d$), et
réciproquement par récurrence que les $e_i^{[d]} - (-1)^i a_i$
engendrent les $e_i^{[d-1]} - (-1)^i b_i$.  Enfin, $f(Z_d)$ s'écrit
comme $\sum_{i=1}^d (-1)^{i+1} Z_d^{d-i} (e_i^{[d]}-(-1)^i a_i)$ grâce
à l'égalité $\sum_{i=1}^d (-1)^{i+1} Z_d^{d-i} e_i^{[d]} = Z_d^d$ (qui
est elle-même, si on ne la trouve pas évidente, une réécriture de
l'égalité $\mathfrak{F}_1(Z_1,\ldots,Z_d|Z_d) = 0$ contenue dans le
lemme \ref{lemme-modules-de-cauchy}).

\XXX — Cette démonstration est complètement pourrie.
\end{proof}

\begin{proposition2}\label{algebre-de-decomposition-universelle-separe-les-racines}
Soit $k$ est un corps et $f \in k[X]$ un polynôme unitaire
\emph{séparable}.  Si $k[Z_1,\ldots,Z_d]/I$ désigne son algèbre de
décomposition universelle définie
en \ref{definition-algebre-de-decomposition-universelle}, alors les
éléments $Z_i - Z_j$ (modulo $I$, pour $i\neq j$) y sont inversibles.
\end{proposition2}
\begin{proof}
Par symétrie, il suffit de le montrer pour $Z_1 - Z_2$.  On a vu
en \ref{relations-algebre-de-decomposition-universelle} que $I$
contient le polynôme $q_d = f(Z_1)$ (donc aussi $f(Z_2)$), et aussi $g
:= q_{d-1} = h_{d-1}(Z_1,Z_2) + a_1 h_{d-2}(Z_1,Z_2) + \cdots +
a_{d-1}$ (où comme d'habitude $f = X^d + a_1 X^{d-1} + \cdots +
a_{d-1} X + a_d$).  Comme $h_e(Z_1,Z_2) = Z_1^e + Z_1^{e-1}\,Z_2 +
\cdots + Z_2^e$ s'écrit aussi $(Z_1^{e+1}-Z_2^{e+1})/(Z_1-Z_2)$, on
peut écrire $g = \frac{f(Z_1) - f(Z_2)}{Z_1-Z_2}$.  Autrement dit :
$(Z_1-Z_2) g = f(Z_1)-f(Z_2)$.  En dérivant cette relation par rapport
à $Z_1$, on trouve : $(Z_1-Z_2) g'_1 = f'(Z_1)$ où $g'_1$ désigne la
dérivée $\frac{\partial g}{\partial Z_1}$ de $g$ par rapport à $Z_1$.
Pour montrer que $Z_1 - Z_2$ est inversible modulo $I$, il suffit de
montrer que $f'(Z_1)$ l'est.  Or l'hypothèse que $f$ soit séparable
signifie qu'il existe une relation de Bézout $uf' + vf = 1$ avec $u,v
\in k[X]$, et notamment $u(Z_1)$ est l'inverse de $f'(Z_1)$ modulo $f$
donc modulo $I$.
\end{proof}


\subsection{Idéaux radicaux de dimension $0$}\label{section-ideaux-radicaux-de-dimension-0}

On rappelle (\XXX) qu'un idéal $J$ d'un anneau $R$ est dit
\emph{radical} lorsque $x^n \in J$ implique $x \in J$ (quel que
soit $n \in \NN$), autrement dit lorsque le quotient $R/J$ est réduit.

Soit maintenant $R = k[Z_1,\ldots,Z_d]$.  Si $I$ est à la fois radical
et de dimension $0$, autrement dit si $R/I$ est réduit et artinien,
d'après \refext{Spec}{artinien réduit=produit corps}, cet anneau est
un produit de corps (extensions finies de $k$), à savoir les
$R/\mathfrak{m}$ où $\mathfrak{m}$ parcourt les idéaux maximaux de $R$
contenant $I$, qui sont en nombre fini et dont $I$ est
l'intersection (\XXX).

Dans cette situation ($I$ un idéal de dimension $0$ de $R =
k[Z_1,\ldots,Z_d]$), on dira que $I$ est \emph{géométriquement
  radical} lorsque $I$ est encore radical après passage à la clôture
algébrique $k'$ de $k$, c'est-à-dire que $I \cdot k'[Z_1,\ldots,Z_d]$
est radical ; cela revient à demander la même chose pour $k'$ la
clôture parfaite de $k$ (\XXX).  Cela équivaut à dire que $R/I$ est un
produit de corps qui soient des extensions (finies) \emph{séparables}
de $k$.  On dit aussi que $R/I$ est \emph{géométriquement réduite}.

\begin{proposition2}[« lemme 92 » de Seidenberg]\label{critere-seidenberg-ideal-radical}
Soit $I$ un idéal de dimension $0$ de $k[Z_1,\ldots,Z_d]$ (où $k$ est
un corps) tel que, pour chaque $1\leq j\leq d$, l'idéal $I$ contienne
un polynôme $g \in k[Z_j]$ (ne faisant intervenir que de la
variable $Z_j$) \emph{séparable}.  Alors $I$ est géométriquement radical.
\end{proposition2}
\begin{proof}
Puisque l'hypothèse effectuée reste vérifiée si on remplace $k$ par sa
clôture algébrique (ou parfaite), il nous suffit de montrer que $I$
est radical.

On va montrer que $I$ est intersection finie d'idéaux maximaux.

On procède par récurrence sur $d$.  Si $d=1$, comme tout diviseur d'un
polynôme séparable est lui-même séparable, le générateur unitaire
de $I$ est séparable, donc s'écrit comme produit de polynômes
séparables irréductibles deux-à-deux étrangers entre eux
$g_1,\ldots,g_r$, de sorte que (par le lemme chinois) $I$ est
l'intersection des idéaux maximaux engendrés par les différents $g_i$.

Pour $d>1$, l'hypothèse assure l'existence d'un $g \in I \cap k[Z_d]$
séparable.  Écrivons $g = g_1 \cdots g_r$ où les $g_i$ sont séparables
irréductibles et deux-à-deux étrangers entre eux.  Alors $I$ est
l'intersection des idéaux $I+(g_i)$ (\XXX).  Puisqu'on cherche à
prouver que $I$ est intersection finie d'idéaux maximaux, il suffit de
le prouver pour un $I+(g_i)$, ce qui permet de supposer que $g$ est
irréductible (et toujours séparable).

Soit $K = k[Z_d]/(g)$ le corps de rupture de $g$.  On a un morphisme
$\varphi \colon k[Z_1,\ldots,Z_d] \to K[Z_1,\ldots,Z_{d-1}]$.  L'idéal
$\varphi(I)$ vérifie les hypothèses faites sur $I$ lui-même : il est
de dimension $0$ (car l'image par $\varphi$ d'une famille finie
génératrice comme $k$-espace vectoriel de $k[Z_1,\ldots,Z_d]/I$ est
génératrice comme $K$-espace vectoriel de
$K[Z_1,\ldots,Z_{d-1}]/\varphi(I)$), et si $g^\natural \in I \cap
k[Z_j]$ est séparable alors $\varphi(g^\natural) \in \varphi(I) \cap
K[Z_j]$.  Il existe donc un nombre fini d'idéaux maximaux
$\mathfrak{m}_i$ de $K[Z_1,\ldots,Z_{d-1}]$ dont $\varphi(I)$ soit
intersection.  Mais alors $\varphi^{-1}(\varphi(I))$, qui est égal
à $I + \ker\varphi = I$, est l'intersection des
$\varphi^{-1}(\mathfrak{m}_i)$, et comme $k[Z_1,\ldots,Z_d] /
\varphi^{-1}(\mathfrak{m}_i) = K[Z_1,\ldots,Z_{d-1}] / \mathfrak{m}_i$
(puisque $\varphi$ est surjectif), ces idéaux sont maximaux.
\end{proof}

\begin{proposition2}\label{algebre-de-decomposition-universelle-est-reduite}
Soit $k$ est un corps et $f \in k[X]$ un polynôme unitaire
\emph{séparable}.  Si $k[Z_1,\ldots,Z_d]/I$ désigne son algèbre de
décomposition universelle définie
en \ref{definition-algebre-de-decomposition-universelle}, alors
celle-ci est géométriquement réduite (l'idéal $I$ est géométriquement
radical).
\end{proposition2}
\begin{proof}
La proposition \ref{relations-algebre-de-decomposition-universelle} et
sa conséquence \ref{algebre-de-decomposition-universelle-est-finie}
assurent que $I$ est de dimension $0$ et contient le polynôme
$f(Z_1)$, et aussi, pour des raisons de symétrie entre les variables,
chacun des $f(Z_j)$.  Ceci fournit précisément les hypothèses de la
proposition précédente, qui permet de conclure.
\end{proof}

\begin{remarque2}
En principe, la preuve de la
proposition \ref{critere-seidenberg-ideal-radical} est constructive en
ce sens qu'elle fournit des idéaux maximaux dont $I$ soit
l'intersection, à condition d'être capable d'effectuer des
factorisations dans tous les corps de rupture qui interviennent.  Ceci
fournira, en fait, une méthode théorique pour calculer des groupes de
Galois, à rapprocher de \XXX.
\end{remarque2}

La réciproque de \ref{critere-seidenberg-ideal-radical} est également
vraie :
\begin{proposition2}\label{critere-seidenberg-ideal-radical-reciproque}
Soit $k$ un corps, et soit $I$ un idéal de dimension $0$ et
géométriquement radical de $k[Z_1,\ldots,Z_d]$.  Alors pour tout
$1\leq j\leq d$, l'idéal $I$ contient un polynôme $g \in k[Z_j]$ (ne
faisant intervenir que de la variable $Z_j$) séparable, autrement dit
$I \cap k[Z_j]$ est lui-même géométriquement radical (i.e., engendré
par un polynôme séparable).
\end{proposition2}
\begin{proof}
Sans perte de généralité on peut supposer $j=1$.
D'après \ref{projection-de-dimension-0}, il existe un polynôme $g$ non
nul qui engendre $I \cap k[Z_1]$.

Traitons d'abord le cas où $k$ est supposé \emph{parfait}.  Si $g_1$
est la partie sans facteur carré de $g$ (i.e., le produit de ses
facteurs irréductibles distincts), alors $g_1^N$ est multiple de $g$
pour $N$ assez grand, donc $g_1^N \in I$, donc $g_1 \in I$ puisque $I$
est radical.  Ceci montre $g_1 \in I \cap k[Z_1]$, et comme $g$ était
censé engendrer $I \cap k[Z_1]$, on a $g = g_1$ sans facteur carré.
Comme $k$ était supposé parfait, $g$ est séparable.

Si maintenant $k$ n'est plus supposé parfait, soit $k'$ sa clôture
algébrique ou sa clôture parfaite.
D'après \ref{projection-et-extensions-de-corps}, on a $(I\cdot
k'[Z_1,\ldots,Z_d]) \cap k'[Z_1] = (I\cap k[Z_1]) \cdot k'[Z_1]$.
Comme $I\cdot k'[Z_1,\ldots,Z_d]$ est radical (puisque $I$ est supposé
géométriquement radical), l'idéal $(I\cap k[Z_1]) \cdot k'[Z_1]$ est
donc radical, mais cet idéal vaut $g\cdot k'[Z_1]$ : donc $g$ est
séparable (dans $k'[Z_1]$ ou dans $k[Z_1]$, cela revient au même).
\end{proof}

De façon plus concise, un idéal de dimension $0$ de
$k[Z_1,\ldots,Z_d]$ est géométriquement radical si et seulement si
tous ses idéaux d'élimination à une seule variable le sont.

Ceci nous permet de donner une conséquence algorithmique :
\begin{algorithme2}\label{algorithme-test-ideal-radical-dimension-0}
Donné un idéal $I$ (défini par ses générateurs) de dimension $0$ de
$k[Z_1,\ldots,Z_d]$, on peut tester si $I$ est géométriquement
radical.  De plus, si $k$ est parfait, on peut calculer le radical
de $I$.
\end{algorithme2}
\begin{proof}[Description de l'algorithme]
Pour chaque $j$, utiliser \ref{base-de-groebner-elimination} pour
calculer le générateur unitaire de $I \cap k[Z_j]$ (c'est-à-dire une
base de Gröbner réduite de cet idéal), et tester si ce générateur est
séparable.  S'ils le sont tous, alors $I$ est géométriquement radical,
sinon, il ne l'est pas.

Dans le cas où $k$ est parfait, si $g_j$ désigne la partie sans
facteur carré du générateur unitaire de $I \cap k[Z_j]$ (qu'on peut
calculer en évaluant de façon répétée des pgcd avec la dérivée \XXX),
le radical de $I$ est l'idéal engendré par $I$ et tous les $g_j$.
\end{proof}
\begin{proof}
Le premier paragraphe ne fait que reformuler
\ref{critere-seidenberg-ideal-radical} et
\ref{critere-seidenberg-ideal-radical-reciproque}.

Seule l'affirmation contenue dans le dernier paragraphe nécessite
encore une démonstration.  Chacun des $g_j$ est contenu dans le
radical de $I$ (puisque $g_j^N$ pour $N$ assez grand).  Si $J$ désigne
l'idéal engendré par $I$ et tous les $g_j$, alors $J$ est radical
d'après \ref{critere-seidenberg-ideal-radical} (puisque les $g_j$ sont
séparables, $k$ étant parfait) ; de plus $J$ contient $I$, et est
contenu dans le radical de $I$.  Il résulte que $J$ est le radical
de $I$ (ce dernier étant le plus petit idéal radical contenant $I$).
\end{proof}


\subsection{Idéaux premiers de dimension $0$}\label{section-ideaux-premiers-de-dimension-0}

Il revient au même de dire d'un idéal $I$ de dimension $0$ de
$k[Z_1,\ldots,Z_d]$ qu'il est premier ou qu'il est maximal (puisqu'une
algèbre finie intègre sur un corps est un corps, cf. \refext{Alg}{fini
  integre=corps} ou \refext{Spec}{artinien connexe implique local}),
autrement dit que le quotient $k[Z_1,\ldots,Z_d]/I$ est un corps.
Comme on l'a rappelé dans la section précédente (\XXX), si $J$ est un
idéal de dimension $0$ et radical de $k[Z_1,\ldots,Z_d]$, alors
$k[Z_1,\ldots,Z_d]/J$ est le produit des $k[Z_1,\ldots,Z_d]/I$ où $I$
parcourt les idéaux premiers (donc maximaux) contenant $I$, dont $J$
est alors l'intersection.

Les deux questions suivantes vont nous préoccuper ici : comment tester
algorithmiquement si un idéal de dimension $0$ et géométriquement
radical est premier, et comment, dans le cas contraire, calculer les
idéaux premiers qui le contiennent.

\begin{remarque2}\label{remarque-projection-et-ideaux-premiers}
On a vu dans la section précédente que, sur $k$ un corps parfait, un
idéal de dimension $0$ de $k[Z_1,\ldots,Z_d]$ est radical si et
seulement si tous ses idéaux d'élimination à une seule variable le
sont : on peut se demander si le même critère fonctionne pour tester
la primalité.  Il n'en est rien : si $f \in k[X]$ est un polynôme
unitaire irréductible (donc séparable, $k$ étant supposé parfait) de
degré $d$ et $k[Z_1,\ldots,Z_d]/I$ son algèbre de décomposition
universelle telle que définie
en \ref{definition-algebre-de-decomposition-universelle}, chacun des
idéaux d'élimination $I \cap k[Z_j]$ est engendré par $f(Z_j)$ comme
on l'a vu en \ref{relations-algebre-de-decomposition-universelle} (et
utilisé en \ref{algebre-de-decomposition-universelle-est-reduite} pour
conclure que $I$ est radical) ; pourtant $k[Z_1,\ldots,Z_d]/I$ n'est
pas nécessairement un corps, comme l'exemple suivant va le montrer.

Dans la situation
de \ref{exemple-algebre-de-decomposition-universelle-non-connexe},
c'est-à-dire l'algèbre de décomposition universelle de $f = X^3 + X^2
-2 X -1$, aucun des deux polynômes $Z_2 - Z_1^2 + 2$ et $Z_2 + Z_1^2 +
Z_1 - 1$ n'appartient à l'idéal $I$ des relations de l'algèbre (vu que
son terme initial n'est pas divisible par aucun de ceux de la base de
Gröbner), et pourtant leur produit $Z_2^2 + Z_2 Z_1 + Z_2 - Z_1^4 -
Z_1^3 + 3 Z_1^2 + 2 Z_1 - 2$ appartient à $I$ (il s'écrit comme $q_2 -
Z_1 q_3$).

On verra en fait (en \ref{section-calcul-galois-par-base-de-groebner}
ci-dessous) que, si $f$ est un polynôme unitaire irréductible
séparable de degré $d$, son algèbre de décomposition universelle est
un corps si et seulement si le groupe de Galois de $f$ est
$\mathfrak{S}_d$, et plus généralement le sous-groupe des permutations
des variables préservant un idéal premier fixé contenant $I$ est
justement le groupe de Galois de $f$.
\end{remarque2}

Comme on vient de le dire, il ne suffit pas (pour $I$ un idéal, même
de dimension $0$ et géométriquement radical) que les idéaux
d'élimination de $I$ à une seule variable soient premiers pour pouvoir
conclure que $I$ l'est.  Il y a cependant une situation où c'est
possible, comme on va le voir :

\begin{definition2}\label{definition-ideal-en-position-nette}
Un idéal $I$ de dimension $0$ de $k[Z_1,\ldots,Z_d]$ est dit \emph{en
  position nette} par rapport à la variable $Z_j$ lorsque le morphisme
$k[Z_j]/(I \cap k[Z_j]) \to k[Z_1,\ldots,Z_d]/I$ induit par
l'inclusion de $k[Z_j]$ dans $k[Z_1,\ldots,Z_d]$ est un isomorphisme
(c'est-à-dire, est surjectif).
\end{definition2}

\begin{remarque2}
Cette définition peut se faire pour un idéal quelconque (c'est-à-dire,
non supposé de dimension $0$), mais si $I$ est de dimension $0$, ce
qui implique la même chose pour $I \cap k[Z_j]$
d'après \ref{projection-de-dimension-0}, on peut donner la condition
équivalente suivante : les $k$-espaces vectoriels
$k[Z_1,\ldots,Z_d]/I$ et $k[Z_j]/(I \cap k[Z_j])$ ont même dimension.

Cette dernière condition est testable algorithmiquement : on sait
calculer la dimension de $k[Z_1,\ldots,Z_d]/I$ à partir d'une base de
Gröbner en comptant les monômes qui ne sont divisibles par le monôme
de tête d'aucun élément de la base de Gröbner ; et l'algorithme
d'élimination \ref{base-de-groebner-elimination} permet de calculer le
générateur unitaire de $I \cap k[Z_j]$ dont le degré est la dimension
du $k$-espace vectoriel $k[Z_j]/(I \cap k[Z_j])$.
\end{remarque2}

On peut donner un critère algorithmique encore plus précis :
\begin{proposition2}\label{critere-nettete-dimension-0}
Soit $I$ un idéal de dimension $0$ de $k[Z_1,\ldots,Z_d]$.  Alors $I$
est en position nette par rapport à $Z_1$ si et seulement si, pour
l'ordre lexicographique (où on est convenu d'ordonner les variables de
la manière $Z_1 \preceq Z_2 \preceq \cdots \preceq Z_d$), ou plus
généralement pour un ordre admissible $\preceq$ quelconque tel que
$\initial_{\preceq}(f) \in k[Z_1]$ implique $f \in k[Z_1]$, la base de
Gröbner réduite de $I$ est de la forme $h(Z_1), Z_2-g_2(Z_1), \ldots,
Z_d-g_d(Z_1)$ où $h,g_2,\ldots,g_d$ sont des polynômes uniquement en
la variable $Z_1$.
\end{proposition2}
\begin{proof}
Si la base de Gröbner réduite de $I$ est de la forme indiquée, alors
$I \cap k[Z_1]$ est l'idéal engendré par $h \in k[Z_1]$, disons de
degré $N$, et les monômes $1,Z_1,\ldots,Z_1^{N-1}$ forment à la fois
une base de $k[Z_1]/(I \cap k[Z_1])$ et de $k[Z_1,\ldots,Z_d]/I$ (ou
si l'on veut, la flèche évidente de l'un vers l'autre a une rétraction
consistant à envoyer $Z_j$ sur $g_j(Z_1)$ pour $j>1$, donc elle est
bien surjective).

Supposons maintenant que $I$ soit en position nette par rapport
à $Z_1$.  On sait d'après \ref{base-de-groebner-elimination} que la
base de Gröbner réduite $B$ de $I$ doit contenir un polynôme $h$ en la
seule variable $Z_1$, et il ne peut en contenir qu'un seul puisque $B$
est réduite, et ce polynôme engendre $I \cap k[Z_1]$.  Pour tout
$j>1$, l'hypothèse de position nette assure qu'il existe $\tilde g_j
\in k[Z_1]$ tel que $Z_j - \tilde g_j(Z_1) \in I$, et le terme initial
de ce monôme est $Z_j$ par les hypothèses faite sur l'ordre.  Quitte à
remplacer $\tilde g_j$ par le reste de sa division par $h$ dans
$k[Z_1]$, on peut supposer que $\tilde g_j$ a un degré strictement
inférieur à celui de $h$.  Pour chaque $j$, la base $B$ doit contenir
un terme dont le monôme initial divise $Z_j$, et donc soit
exactement $Z_j$.  Par minimalité, chacun de ces termes est de la
forme $Z_j - g_j(Z_1)$, et il est alors clair que les $\tilde g_j$
coïncident exactement avec les $g_j$ (même si on n'en a pas besoin
dans cette démonstration).
\end{proof}

Intuitivement (et au moins pour $I$ de dimension $0$ et
géométriquement radical), il faut comprendre que « $I$ en position
  nette par rapport à la variable $Z_j$ » signifie que la projection
sur la coordonnée $Z_j$ de l'ensemble des points défini par $I$
(disons, sur la clôture algébrique de $k$) est un isomorphisme au sens
où elle n'identifie pas de points.

Trivialement, si $I$ (idéal de dimension $0$) est en position nette
par rapport à $Z_j$, l'idéal $I$ est premier si et seulement si $I
\cap k[Z_j]$ l'est.  Lorsque c'est le cas que $I$ soit en position
nette (et on sait le détecter d'après ce qu'on a dit), il est donc
facile de tester si $I$ est premier.  Malheureusement, il n'existe pas
forcément une variable par rapport à laquelle que $I$ soit en position
nette, comme on l'a vu
en \ref{remarque-projection-et-ideaux-premiers}.  On va maintenant
chercher à expliquer pourquoi on peut néanmoins toujours (au moins si
$k$ est infini), « fabriquer » une variable $Y = c_1 X_1 + \cdots +
c_d X_d$, telle que l'idéal complété par cette relation soit en
position nette par rapport à $Y$.

\begin{proposition2}\label{nettete-projection-generique-dimension-0}
Soit $I$ un idéal géométriquement radical de dimension $0$ de
$k[Z_1,\ldots,Z_d]$ où $k$ est un corps quelconque.  Soient
$C_1,\ldots,C_d$ et $Y$ de nouvelles indéterminées, notons $K =
k(C_1,\ldots,C_d)$, et soit $\tilde I$ l'idéal de $K[Y,
  Z_1,\ldots,Z_d]$ engendré par $I$ et par $Y - (C_1 X_1 + \cdots +
C_d X_d)$.  Alors $\tilde I$ est en position nette par rapport à $Y$.
\end{proposition2}
\begin{proof}
Commençons par appeler $\dot I$ l'idéal de $K[Z_1,\ldots,Z_d]$
engendré par $I$.  Comme toute base de Gröbner de $I$ constitue une
base de Gröbner de $\dot I$
(cf. \ref{bases-de-groebner-et-extensions-de-corps}), les conditions
assurant que $I$ est géométriquement radical de dimension $0$
(\ref{equivalences-ideaux-affines-dimension-zero} ainsi que
\ref{critere-seidenberg-ideal-radical} et
\ref{critere-seidenberg-ideal-radical-reciproque}) assurent aussi
que $\dot I$ est géométriquement radical de dimension $0$.  Par
ailleurs, le quotient $K[Y, Z_1,\ldots,Z_d]/\tilde I$ est isomorphe à
$K[Z_1,\ldots,Z_d]/\dot I$, l'isomorphisme consistant à envoyer $Y$
sur $C_1 X_1 + \cdots + C_d X_d$ (modulo $\dot I$) ; ceci assure
notamment que $\tilde I$ est lui ausssi géométriquement radical de
dimension $0$.

Remarquons le fait suivant : si $h \in \dot I$ alors $\frac{\partial
  h}{\partial C_i} \in \dot I$ pour tout $1\leq i\leq d$.  En effet,
si $g_1,\ldots,g_r$ (dans $k[Z_1,\ldots,Z_d]$) sont des générateurs
de $I$, ils engendrent aussi $\dot I$ (dans $K[Z_1,\ldots,Z_d]$) et
peut écrire $h = h_1 g_1 + \cdots + h_r g_r$ pour certains $h_i \in
K[Z_1,\ldots,Z_d]$, et en dérivant cette égalité par rapport à $C_i$
(les $g_i$ ayant une dérivée nulle), on voit que $\frac{\partial
  h}{\partial C_i}$ s'écrit aussi comme combinaison des $g_i$.

Soit maintenant $f \in K[Y]$ le polynôme unitaire engendrant l'idéal
$\tilde I \cap K[Y]$, autrement dit, le polynôme minimal de (l'image
de) $Y$ dans $K[Y, Z_1,\ldots,Z_d]/\tilde I$.
D'après \ref{critere-seidenberg-ideal-radical-reciproque}, ce polynôme
est séparable : on peut donc écrire une relation $f'U + fV = 1 \in
K[Y]$.  Soit $g \in K[Z_1,\ldots,Z_d]$ défini en substituant $C_1 Z_1
+ \cdots + C_d Z_d$ à la variable $Y$ dans $f$ : ce polynôme $g$
appartient encore à $\tilde I$, et même $\dot I$, puisqu'il s'agit de
dire que son image s'annule dans $K[Y, Z_1,\ldots,Z_d]/\tilde I \cong
K[Z_1,\ldots,Z_d]/\dot I$, image qui est la même que celle de $f$.
D'après le fait remarqué plus haut, on a $\frac{\partial g}{\partial
  C_i} \in \dot I$ pour tout $1\leq i\leq d$.  Ceci signifie que
$\frac{\partial f}{\partial C_i} + Z_i f'$, une fois substitué $C_1
Z_1 + \cdots + C_d Z_d$ à $Y$, appartient à $\dot I$ (rappelons que
$f'$ désigne la dérivée de $f$ par rapport à $Y$).  Par conséquent,
$\frac{\partial f}{\partial C_i} + Z_i f'$ lui-même appartient
à $\tilde I$ (toujours en utilisant l'isomorphisme $K[Y,
  Z_1,\ldots,Z_d]/\tilde I \cong K[Z_1,\ldots,Z_d]/\dot I$).  En
multipliant par $U$, on a donc $U \frac{\partial f}{\partial C_i} +
Z_i - V f \in \tilde I$.  C'est-à-dire que $Z_i$ est congru,
modulo $\tilde I$, à un polynôme $U \frac{\partial f}{\partial C_i} -
V f \in K[Y]$, ce qui affirme bien que $K[Y]/(\tilde I \cap K[Y]) \to
K[Y, Z_1,\ldots,Z_d]/\tilde I$ est surjectif, autrement dit que
$\tilde I$ est en position nette par rapport à $Y$.
\end{proof}

\begin{proposition2}\label{existence-combinaison-lineaire-nette-des-variables}
Soit $I$ un idéal géométriquement radical de dimension $0$ de
$k[Z_1,\ldots,Z_d]$ où $k$ est un corps infini.  Alors il existe
$c_1,\ldots,c_d \in k$ tel que l'idéal de $k[Y,Z_1,\ldots,Z_d]$
engendré par $I$ et $Y - (c_1 Z_1 + \cdots + c_d Z_d)$ soit en
position nette par rapport à $Y$, et plus généralement dans n'importe
quelle partie infinie de $k$ on peut trouver de tels $c_i$.
\end{proposition2}
\begin{proof}
La proposition précédente montre que pour chaque $i$ il existe $F \in
k(C_1,\ldots,C_d)[Y]$ tel que $Z_i \equiv F(C_1,\ldots,C_d,Y)
\pmod{\tilde I}$ (avec le $\tilde I$ défini plus haut), c'est-à-dire
que $Z_i \equiv F(C_1,\ldots,C_d, (C_1 Z_1 + \cdots C_d Z_d))
\pmod{I}$.  Si $q \in k[C_1,\ldots,C_d]$ est un dénominateur commun
aux coefficients de $F$ en la variable $Y$, on a $q\cdot Z_i \equiv
q\cdot F(C_1,\ldots,C_d, (C_1 Z_1 + \cdots C_d Z_d))$ où $q \cdot F
\in k[C_1,\ldots,C_d,Y]$.  Puisque $k$ est infini, on peut trouver
$c_1,\ldots,c_d$ dans $k$ (ou dans n'importe quelle partie infinie
prescrite à l'avance de $k$) n'annulant pas $q$
(cf. \refext{Calculs}{un-ferme-de-zariski-strict-n-est-pas-plein}
\XXX) : on a alors $Z_i \equiv F(c_1,\ldots,c_d, (c_1 Z_1 + \cdots c_d
Z_d)) \pmod{I}$ en divisant par $q(c_1,\ldots,c_d)$.  C'est bien ce
qu'on voulait montrer.
\end{proof}

\begin{algorithme2}\label{algorithme-test-ideal-premier-dimension-0}
Donné un idéal $I$ (défini par ses générateurs) de dimension $0$ et
géométriquement radical de $k[Z_1,\ldots,Z_d]$, avec $k$ un corps
infini, si on sait tester l'irréductibilité des polynômes à une
variable à coefficients dans $k$, on peut tester si $I$ est premier.

(En particulier, si $k$ est un corps infini parfait, et si on sait
tester l'irréductibilité des polynômes à une variable à coefficients
dans $k$, alors donné un idéal $I$ de dimension $0$, on peut tester si
$I$ est premier.)
\end{algorithme2}
\begin{proof}[Description de l'algorithme]
S'agissant du deuxième paragraphe, sur un corps parfait un idéal est
radical si et seulement si il est géométriquement radical, on sait
tester ce fait
d'après \ref{algorithme-test-ideal-radical-dimension-0}, et si l'idéal
n'est pas radical en particulier il n'est pas premier.  Décrivons
maintenant l'algorithme pour tester la primalité d'un idéal
géométriquement radical sur un corps infini quelconque.

On trouve $c_1,\ldots,c_d$ tels que l'idéal $I$ soit en position nette
par rapport à $c_1 Z_1 + \ldots + c_d Z_d$ (avec l'abus de langage
évident, c'est-à-dire, au sens de la proposition précédente) : d'après
la proposition précédente, en prenant $c_1,\ldots,c_d$ dans un
ensemble suffisamment grand, ce sera toujours possible (formellement,
on peut commencer par tester tous les $d$-uplets d'un ensemble fini,
puis agrandir cet ensemble fini si aucun ne convient, et répéter
jusqu'à trouver un $d$-uplet qui convient, ce qui se produira toujours
si l'idéal était bien radical) : à chaque fois, on teste si on est en
position nette en utilisant \ref{critere-nettete-dimension-0} ou la
remarque qui précède.

(Remarquons que si on trouve $c_1,\ldots,c_d$ tels que $I$ soit en
position nette, on peut passer à la suite même si on n'a pas testé que
$I$ est géométriquement radical.  Cependant, le fait que $I$ soit
géométriquement radical permet de garantir que cette étape terminera
bien.)

Une fois trouvé $c_1,\ldots,c_d$ tels que $I$ soit en position nette
par rapport à $Y = c_1 Z_1 + \ldots + c_d Z_d$, on calcule le
générateur unitaire $h(Y)$ de l'idéal d'élimination de $I$ sur la
variable $Y$ (cf. \ref{base-de-groebner-elimination} et
\ref{critere-nettete-dimension-0}) : il ne reste plus qu'à tester
l'irréductibilité de $h$ dans $k[Y]$ puisque $k[Y]/(h) \cong
k[Z_1,\ldots,Z_d]/I$ est intègre si et seulement si $h$ est
irréductible.
\end{proof}

La correction de cet algorithme est claire compte tenu de ce qui a
déjà été expliqué.  Si $k$ est fini, on peut passer à
$k(C_1,\ldots,C_d)$, auquel cas l'idéal sera en position nette par
rapport à $Y = C_1 Z_1 + \ldots + C_d Z_d$
d'après \ref{nettete-projection-generique-dimension-0}, mais les
calculs seront nettement plus complexes (il vaut mieux, au moins,
passer à $k[C_1,\ldots,C_d]$ et calculer l'idéal d'élimination par
rapport à $C_1,\ldots,C_d,Y$).  Remarquons que dans ce cas, il faudra
savoir factoriser (ou au moins tester la primalité de) polynômes à
plusieurs variables (\XXX).  Par ailleurs, sous-jacent à cette
variante de l'algorithme est le résultat facile suivant :
\begin{proposition2}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ (où $k$ est un corps
quelconque) et soient $C_1,\ldots,C_m$ de nouvelles indéterminées.
Alors l'idéal $\tilde I$ engendré par $I$ dans
$k(C_1,\ldots,C_m)[Z_1,\ldots,Z_d]$ ou bien dans $k[C_1,\ldots,C_m,
  Z_1,\ldots,Z_d]$ est premier si et seulement si $I$ l'est.
\end{proposition2}
\begin{proof}
Dans le cas de $k[C_1,\ldots,C_m, Z_1,\ldots,Z_d]$, le quotient de
celui-ci par $\tilde I$ est l'anneau des polynômes en $m$ variables
$C_1,\ldots,C_m$, à coefficients dans le quotient
$k[Z_1,\ldots,Z_d]/I$.  Or il est bien connu qu'un anneau de polynômes
est intègre si et seulement si son anneau de coefficients l'est.

Dans le cas de $k(C_1,\ldots,C_m)[Z_1,\ldots,Z_d]$, on obtient
l'anneau qui inverse les éléments non nuls de $k[C_1,\ldots,C_m]$ dans
l'anneau ci-dessus : lui aussi est intègre si $I$ est premier, et a
des diviseurs de $0$ s'il y en a déjà dans $k[Z_1,\ldots,Z_d]/I$.
\end{proof}

En fait, on a fait mieux : une fois trouvés $c_1,\ldots,c_d$ tels que
$I$ soit en position nette par rapport à $c_1 Z_1 + \cdots + c_d Z_d$
au sens où l'idéal $\tilde I$ engendré par $I$ et $Y - (c_1 Z_1 +
\cdots + c_d Z_d)$ est en position nette par rapport à $Y$ dans $k[Y,
  Z_1,\ldots,Z_d]$, si $h$ est le générateur de l'idéal d'élimination
$\tilde I \cap k[Y]$, on a $k[Y]/(h) = k[Y] / (\tilde I \cap k[Y])
\cong k[Y, Z_1,\ldots,Z_d] / \tilde I \cong k[Z_1,\ldots,Z_d]/I$ : si
$h = h_1 \cdots h_r$ est la décomposition en facteurs irréductibles
de $h$ (forcément étrangers puisque $h$ est sans facteur carré), alors
le théorème chinois assure que $k[Y]/(h)$ est le produit des
$k[Y]/(h_i)$, si bien que, en appelant $g_i$ le polynôme obtenu en
substituant $c_1 Z_1 + \cdots + c_d Z_d$ à $Y$ dans $h_i$, et $J_i$
l'idéal $I + (g_i)$ de $k[Z_1,\ldots,Z_d]$, on a $k[Y]/(h_i) \cong
k[Z_1,\ldots,Z_d]/J_i$, les $J_i$ sont donc premiers et $k[Y]/(h)
\cong \prod_i (k[Z_1,\ldots,Z_d]/J_i)$.  Ceci prouve :

\begin{algorithme2}\label{algorithme-decomposition-ideal-radical-dimension-0}
Donné un idéal $I$ (défini par ses générateurs) de dimension $0$ et
géométriquement radical de $k[Z_1,\ldots,Z_d]$, avec $k$ un corps
infini, si on sait factoriser les polynômes en une variable à
coefficients dans $k$, on peut trouver les idéaux maximaux $J_i$
contenant $I$.
\end{algorithme2}

\begin{exemple2}
Reprenons l'exemple commencé en
\ref{exemple-algebre-de-decomposition-universelle-non-connexe}
et \ref{remarque-projection-et-ideaux-premiers} : soit $f = X^3 + X^2
-2 X -1$, dont l'algèbre de décomposition universelle est engendrée
par les relations $q_3 = Z_1^3 + Z_1^2 - 2 Z_1 - 1$, $q_2 = Z_2^2 +
Z_1 Z_2 + Z_2 + Z_1^2 + Z_1 - 2$ et $q_1 = Z_3 + Z_2 + Z_1 + 1$ (qui
en sont une base de Gröbner).  Si on considère $(c_1,c_2,c_3) =
(1,-1,0)$, c'est-à-dire qu'on ajoute la relation $Y - Z_1 + Z_2$,
l'idéal $\tilde I$ a alors pour base de Gröbner les éléments
suivants : $Y^6 - 14 Y^4 + 49 Y^2 - 49$, $Z_1 + \frac{3}{14} Y^4 -
\frac{5}{2} Y^2 - \frac{1}{2} Y + 5$, $Z_2 + \frac{3}{14} Y^4 -
\frac{5}{2} Y^2 + \frac{1}{2} Y + 5$ et $Z_3 - \frac{3}{7} Y^4 + 5 Y^2
- 9$.  Le premier polynôme $h(Y) = Y^6 - 14 Y^4 + 49 Y^2 - 49$ de
cette liste, se factorise comme $(Y^3 - 7 Y + 7) \penalty0\, (Y^3 - 7
Y - 7)$.  En appelant $h_1$ et $h_2$ ces deux facteurs (dans l'ordre
où on les a écrits), les deux idéaux maximaux de $\QQ[Y,Z_1,Z_2,Z_3]$
contenant $\tilde I$ sont $\tilde J_1 = \tilde I + (h_1)$ et $\tilde
J_2 = \tilde I + (h_2)$ (par exemple, $\tilde J_1$ a pour base de
Gröbner $Y^3 - 7 Y + 7$, $Z_1 - Y^2 - 2 Y + 5$, $Z_2 - Y^2 - Y + 5$ et
$Z_3 + 2 Y^2 + 3 Y - 9$), et les deux idéaux maximaux de
$\QQ[Z_1,Z_2,Z_3]$ contenant $I$ sont $J_1 = I + (g_1)$ et $J_2 = I +
(g_2)$ où $g_1 = h_1(c_1 Z_1 + c_2 Z_2 + c_3 Z_3) = h_1(Z_1-Z_2)$ et
de même pour $g_2$.  On peut bien sûr en calculer une base de Gröbner,
par exemple pour $J_1$ : $Z_1^3 + Z_1^2 - 2 Z_1 - 1$, $Z_2 - Z_1^2 +
2$ et $Z_3 + Z_1^2 + Z_1 - 1$.

Pour rendre cet exemple plus compréhensible, notons que les racines de
$f$ dans $\CC$ sont $\xi_1 = \cos\frac{2\pi}{7}$, $\xi_2 =
\cos\frac{4\pi}{7}$ et $\xi_3 = \cos\frac{6\pi}{7}$ : les relations
$q_1,q_2,q_3$ engendrent l'idéal $I$ de toutes les relations possibles
entre $\xi_1,\xi_2,\xi_3$ quelle que soit la manière dont on les nomme
$Z_1,Z_2,Z_3$, et le polynôme $h$ a pour racines les six différences
possibles $Y = Z_1 - Z_2$ où $Z_1,Z_2$ sont deux quelconques des
$\xi_i$.  Le fait de choisir d'annuler $h_1$ ou $h_2$ limite les choix
de nommages de $\xi_1,\xi_2,\xi_3$ en $Z_1,Z_2,Z_3$ à seulement trois
possibilités parmi les six : on va expliquer pourquoi ce qu'on a fait
revient exactement à calculer le groupe de Galois de $f$.
\end{exemple2}

\begin{remarque2}
On observera que si $k$ est un corps sur lequel on sait factoriser les
polynômes en une variable, sans l'hypothèse que $k$ est parfait, nous
n'avons pas donné d'algorithme permettant de décider si un idéal de
dimension $0$ de $k[Z_1,\ldots,Z_d]$ est radical, ou bien premier
(seulement pour savoir s'il est géométriquement radical, et pour
savoir s'il est premier en supposant qu'il est géométriquement
radical).  Ce n'est pas un oubli : un tel algorithme n'existe pas, car
le problème est \emph{indécidable} au sens de Church-Turing.

En effet, il existe (\XXX — référencer Fröhlich \& Shepherdson
lemme 7.21 et th. 7.27) un corps $k$ de caractéristique $p>0$ tel
qu'on sache algorithmiquement factoriser les polynômes dans $k[X]$
mais que si $k' = k[Y]/(h)$ est une certaine extension algébrique
finie purement inséparable de $k$ alors il est indécidable de savoir
si un élément $\xi$ de $k'$ a une racine $p$-ième dans $k'$.  Or si
$I_\xi$ désigne l'idéal de $k[X,Y]$ engendré par $h \in k[Y]$ et par
$X^p - \tilde\xi$ (où $\tilde\xi \in k[Y]$ est un relevé quelconque
de $\xi$, dont le choix n'a pas d'importance), alors $k[X,Y]/I_\xi =
k'[X]/(X^p-\xi)$ est un corps, ou est réduit, si et seulement si $\xi$
a une racine $p$-ième.  Donc arriver à décider si $I_\xi$ est premier,
ou radical, revient à décider si $\xi$ a une racine $p$-ième, ce qui
n'est pas possible en général.
\end{remarque2}


\section{Quelques applications}

\subsection{Application au calcul d'un groupe de Galois}\label{section-calcul-galois-par-base-de-groebner}

\subsubsection{} Plaçons-nous dans la situation suivante : $f \in
k[X]$ est un polynôme unitaire séparable de degré $d$ sur un corps
$k$, et $k[Z_1,\ldots,Z_d]/I$ est son algèbre de décomposition
universelle telle qu'introduite
en \ref{section-algebre-de-decomposition-universelle}.  On a vu en
\ref{algebre-de-decomposition-universelle-est-finie} et
\ref{algebre-de-decomposition-universelle-est-reduite} que cette
algèbre est géométriquement réduite de dimension $0$.  Il s'agit donc
(cf. les remarques initiales
de \ref{section-ideaux-premiers-de-dimension-0}) du produit des corps
$k[Z_1,\ldots,Z_d]/J_i$ où les $J_i$ sont les idéaux maximaux
contenant $I$, et on a vu
en \ref{algorithme-decomposition-ideal-radical-dimension-0} comment
calculer les $J_i$ (au moins dans le cas où $k$ est infini et où on
sait factoriser les polynômes en une variable sur $k$).

Si $J$ est un quelconque de ces idéaux maximaux contenant $I$, alors
$K := k[Z_1,\ldots,Z_d]/J$ est un corps engendré par $k$ et par les
images de $Z_1,\ldots,Z_d$.  Mais comme $I$, donc $J$, contient le
polynôme $f(Z_1)$
(d'après \ref{relations-algebre-de-decomposition-universelle}), et
aussi, pour des raisons de symétrie entre les variables, chacun des
$f(Z_j)$, les images des $Z_j$ dans $K$ sont des racines du
polynôme $f$.  Mais de plus, ces images sont deux à deux distinctes
dans $K$ car
\ref{algebre-de-decomposition-universelle-separe-les-racines} implique
que les $Z_j - Z_{j'}$ (pour $j\neq j'$) sont inversibles modulo $I$,
donc \textit{a fortiori} modulo $J$ : donc ce sont exactement les
racines de $f$ dans $K$.  Bref, $K$ est un corps extension de $k$ et
engendré au-dessus de $k$ par les $d$ racines du polynôme $f$ :
c'est-à-dire que c'est « le » corps de décomposition de $f$ sur $k$.

Le groupe de Galois de $f$ étant donc (\XXX — référence précise) le
groupe des automorphismes de $K$ au-dessus de $k$, il peut se voir
comme le groupe des permutations de $Z_1,\ldots,Z_d$ qui laissent
l'idéal $J$ invariant ; connaissant une base de Gröbner de $J$, il est
facile de tester si une permutation des variables le laisse invariant,
il suffit de tester si la permutation appliquée à chaque élément de la
base de Gröbner est encore dans l'idéal.  On a donc montré :

\begin{algorithme2}\label{algorithme-calcul-galois-par-base-de-groebner}
Donné un polynôme $f \in k[X]$, avec $k$ infini, si on sait
factoriser les polynômes en une variable à coefficients dans $k$, on
sait calculer le groupe de Galois de $f$ comme le groupe des
permutations de $Z_1,\ldots,Z_d$ qui fixent un idéal $J$ maximal
contenant l'idéal $I$ des relations de l'algèbre de décomposition
universelle de $f$ (explicité
en \ref{relations-algebre-de-decomposition-universelle}) ; et de façon
plus particulière (si on sait tester l'irréductibilité des polynômes à
une variable à coefficients dans $k$), on sait tester si ce groupe de
Galois est $\mathfrak{S}_d$ (en testant si $I$ est premier).
\end{algorithme2}

\begin{remarque2}
L'algorithme qu'on vient de présenter est à peu près équivalent au
calcul du groupe de Galois par le moyen des résolvantes
(\refext{Calculs}{strategie-algorithmique-generale-calcul-groupes-de-galois})
dans le cas des résolvantes \emph{linéaires}, à ceci près qu'on ne se
contente pas de chercher à savoir si le groupe de Galois est ou n'est
pas inclus dans tel ou tel groupe (disons, s'il est égal à
$\mathfrak{S}_d$) mais qu'on va plus loin pour le connaître
exactement, au prix de calculs de bases de Gröbner éventuellement très
lourds.
\end{remarque2}

\begin{remarque2}
Au cours de l'application de l'algorithme qu'on vient de présenter, si
on a utilisé la
proposition \ref{existence-combinaison-lineaire-nette-des-variables}
pour trouver une combinaison $k$-linéaire $c_1 Z_1 + \cdots + c_d Z_d$
des indéterminées par rapport à laquelle l'ideal $I$ (donc aussi $J$)
soit en position nette, alors l'image modulo $J$ de cette combinaison
$c_1 Z_1 + \cdots + c_d Z_d$, c'est-à-dire la combinaison
correspondante, dans $K$, des racines de $f$, fournit un \emph{élément
  primitif} de $K$.

Par ailleurs, on peut observer que
\ref{algorithme-calcul-inverse-algebre-de-type-fini} permet
d'effectuer dans le corps de décomposition $K$ des calculs d'inverse
(i.e., on en a une présentation algorithmique non seulement comme
anneau mais bien comme corps).
\end{remarque2}



\subsection{Application au calcul de racines d'un polynôme}

\subsubsection{} Plaçons-nous de nouveau dans la situation suivante : $f \in
k[X]$ est un polynôme unitaire séparable de degré $d$ sur un corps
$k$, et $k[Z_1,\ldots,Z_d]/I$ est son algèbre de décomposition
universelle telle qu'introduite
en \ref{section-algebre-de-decomposition-universelle}.  Si maintenant
$E$ est un corps extension de $k$ et dans lequel $f$ est scindé, la
donnée des racines $\xi_1,\ldots,\xi_d$ de $f$ dans $E$ définit un
morphisme $k[Z_1,\ldots,Z_d]/I \to E$ (envoyant $Z_i$ modulo $I$ sur
$\xi_i$ dans $E$).

À un tel niveau de généralité, on ne peut pas donner un sens précis à
ce qu'on veut dire par « calculer les $\xi_i$ », mais on peut
néanmoins donner une technique souvent intéressante dans ce contexte :
il s'agit de trouver une expression $\eta = P(\xi_1,\ldots,\xi_d)$ en
les $\xi_i$, où $P \in k[Z_1,\ldots,Z_d]$ qui soit d'une certaine
manière plus simple à calculer (le sens précis dépendant du type de
calcul qu'on cherche à mener) ; on peut alors séparer le calcul de la
façon suivante : d'abord calculer l'idéal d'élimination sur la
variable $Y$ de l'idéal $\tilde I = I + (Y-P)$ de
$k[Y,Z_1,\ldots,Z_d]$, ce qui fournit un polynôme $R_P$ annulateur de
$\eta$, trouver les racines de $R_P$ dans $E$ et identifier celle qui
est $\eta$, puis travailler dans l'algèbre
$k(\eta)[Z_1,\ldots,Z_d]/\hat I$ où cette fois $\hat I = I + (P -
\eta)$.  On appliquera typiquement cette idée avec $P$ un polynôme qui
soit « partiellement » symétrique en les $Z_j$ : on verra dans le
chapitre \refext{Calculs}{} que $R_P$ est une « résolvante » (\XXX) et
dans le chapitre \refext{Radicaux}{} que prendre $P = \sum \zeta^{ij}
\xi_j$, où $\zeta$ est une racine $d$-ième de l'unité, peut s'avérer
intéressant.

\XXX — Tout ceci est assez vaseux.



\ifx\danslelivre\undefined
\bibliography{../biblio/bibliographie-livre}
\bibliographystyle{../biblio/style-bib-livre}
\end{document}
\else
\endgroup
\fi