Procédure de décision qui détermine si un élément donné (souvent un polynôme) appartient à un idéal I spécifié d'un anneau ou d'une structure algébrique ; la sortie est oui/non et souvent un certificat tel qu'une écriture de l'élément comme combinaison des générateurs de l'idéal.

Principe

Transformer l'ensemble des générateurs de I en une base canonique par rapport à un ordre de monômes choisi (pour les anneaux de polynômes il s'agit typiquement d'une base de Gröbner) et réduire l'élément ciblé modulo cette base ; l'appartenance a lieu exactement quand le reste est nul après réduction par la base.

Démonstration

Dans k[x,y], pour tester si f(x,y) appartient à I = (x^2 + y, xy - 1), calculer une base de Gröbner de I pour un ordre monomial choisi, réduire f par cette base ; si la réduction donne 0, f ∈ I et les étapes de réduction donnent une combinaison explicite des générateurs égale à f.

Mauvaise application

Se fier à l'évaluation en un nombre fini de points ou à des spécialisations aléatoires pour conclure l'appartenance ; une identité polynomiale sur de nombreux points n'établit pas l'appartenance à un idéal et peut produire des faux positifs, en particulier sur des corps finis ou des schémas non réduits.

Conséquence

Un test d'appartenance correct sur des anneaux de polynômes fournit des certificats algébriques effectifs, permet des procédures d'élimination et de décision en géométrie algébrique et en algèbre computationnelle, et ramène de nombreuses questions structurelles à un calcul fini lorsque l'anneau est noethérien et que les algorithmes terminent.

Inversion

Au lieu de tester l'appartenance d'un élément à I, on peut tester si I est contenu dans un idéal J ou si un élément appartient à la racine de I ; l'inversion déplace l'objet d'étude de l'expression d'un élément par des générateurs vers des relations d'inclusion ou l'appartenance à la racine (cette dernière requérant des algorithmes différents).

Limite

Portée généralement limitée aux anneaux noethériens ou aux cadres où existent des bases canoniques et peuvent être calculées ; dans des anneaux non noethériens ou certains anneaux non commutatifs l'appartenance peut être indécidable ou intraitable ; la complexité dépend du nombre de variables, des degrés et du corps des coefficients.

Tension sémantique

Appartenance à un idéal versus appartenance à la racine et calcul des syzygies : l'appartenance directe demande une écriture par les générateurs, tandis que l'appartenance à la racine et la décomposition primaire portent sur l'appartenance modulo puissances ou composantes structurelles ; méthodes et complexité diffèrent.

Synthèse

Le test d'appartenance à un idéal ramène la question de savoir si un élément est engendré par un idéal à une réduction algorithmique via une base canonique (par exemple une base de Gröbner) ; lorsqu'il est réalisable il fournit des certificats explicites et permet de nombreuses tâches algorithmiques en algèbre, sa faisabilité étant encadrée par la nature de l'anneau, l'ordre choisi et la complexité.