Descomposición triangular

En álgebra computacional , una descomposición triangular de un sistema polinomial S es un conjunto de sistemas polinomiales más simples S ₁ , ..., S _e tales que un punto es una solución de S si y solo si es una solución de uno de los sistemas S ₁ , ..., S _e .

Cuando el objetivo es describir el conjunto de soluciones de _{S en} la clausura algebraica de su cuerpo de coeficientes , esos sistemas más simples son cadenas regulares . Si los coeficientes de los sistemas polinómicos S₁ , ..., Sₙ son números reales, entonces las soluciones reales de S se pueden obtener mediante una descomposición triangular en sistemas semialgebraicos regulares . En ambos casos, cada uno de estos sistemas más simples tiene forma triangular y propiedades notables, lo que justifica la terminología.

El método del conjunto característico es el primer algoritmo sin factorización, propuesto para descomponer una variedad algebraica en componentes equidimensionales. Además, el autor, Wen-Tsun Wu , implementó este método y presentó datos experimentales en su artículo pionero de 1987 titulado "Un teorema de estructura cero para la resolución de ecuaciones polinómicas". ^{[ 1 ]} Para contextualizar este trabajo, recordemos cuál era la idea común de descomposición de conjuntos algebraicos en el momento en que se escribió este artículo.

Sea K un cuerpo algebraicamente cerrado y k un subcuerpo de K. Un subconjunto V ⊂ K ⁿ es una variedad algebraica (afín) sobre k si existe un conjunto polinomial F ⊂ k [ x ₁ , ..., x _n ] tal que el conjunto cero V ( F ) ⊂ K ⁿ de F es igual a V.

Recordemos que se dice que V es irreducible si para todas las variedades algebraicas V ₁ , V ₂ ⊂ K ⁿ la relación V = V ₁ ∪ V ₂ implica o bien V = V ₁ o bien V = V ₂ . Un primer resultado de descomposición de variedades algebraicas es el famoso teorema de Lasker-Noether , que implica lo siguiente.

Teorema (Lasker - Noether). Para cada variedad algebraica V ⊂ K ⁿ existen un número finito de variedades algebraicas irreducibles V ₁ , ..., V _e ⊂ K ⁿ tales que tenemos

${\displaystyle V=V_{1}\cup \cdots \cup V_{e}.}$

Además, si V _i ⊈ V _j se cumple para 1 ≤ i < j ≤ e, entonces el conjunto { V ₁ , ..., V _e } es único y forma la descomposición irreducible de V.

Las variedades V ₁ , ..., V _e en el teorema anterior se denominan componentes irreducibles de V y pueden considerarse como una salida natural para un algoritmo de descomposición, o, en otras palabras, para un algoritmo que resuelve un sistema de ecuaciones en k [ x ₁ , ..., x _n ] .

Para generar un programa informático, esta especificación del algoritmo debe prescribir cómo se representan los componentes irreducibles. Joseph Ritt ^{[ 2 ]} introduce dicha codificación mediante el siguiente resultado.

Teorema (Ritt). Si V ⊂ K ⁿ es una variedad no vacía e irreducible, entonces se puede calcular un conjunto triangular reducido C contenido en el ideal.${\displaystyle \langle F\rangle }$generado por F en k [ x ₁ , ..., x _n ] y tal que todos los polinomios g en${\displaystyle \langle F\rangle }$se reduce a cero por pseudodivisión con respecto a C.

Llamamos al conjunto C en el teorema de Ritt un conjunto característico de Ritt del ideal.${\displaystyle \langle F\rangle }$Consulte la noción de conjunto triangular en la sección de cadenas regulares .

Joseph Ritt describió un método para resolver sistemas polinomiales basado en la factorización de polinomios sobre extensiones de cuerpos y el cálculo de conjuntos característicos de ideales primos.

Sin embargo, derivar una implementación práctica de este método fue y sigue siendo un problema difícil. En la década de 1980, cuando se introdujo el Método del Conjunto Característico , la factorización de polinomios era un área de investigación activa y ciertas cuestiones fundamentales sobre este tema se resolvieron recientemente ^{[ 3 ].}

Hoy en día, descomponer una variedad algebraica en componentes irreducibles no es esencial para resolver la mayoría de los problemas de aplicación, ya que bastan nociones más débiles de descomposición, que requieren menos recursos computacionales.

El método del conjunto característico se basa en la siguiente variante del teorema de Ritt.

Teorema (Wen-Tsun Wu). Para cualquier conjunto polinomial finito F ⊂ k [ x ₁ , ..., x _n ] , se puede calcular un conjunto triangular reducido.${\displaystyle C\subset \langle F\rangle }$de tal manera que todos los polinomios g en F se reducen a cero por pseudodivisión con respecto a C.

Diferentes conceptos y algoritmos ampliaron el trabajo de Wen-Tsun Wu . A principios de la década de 1990, la noción de cadena regular , introducida independientemente por Michael Kalkbrener en 1991 en su tesis doctoral y por Lu Yang y Jingzhong Zhang ^{[ 4 ],} condujo a importantes descubrimientos algorítmicos.

En la visión de Kalkbrener, ^{[ 5 ]} las cadenas regulares se utilizan para representar los ceros genéricos de las componentes irreducibles de una variedad algebraica. En el trabajo original de Yang y Zhang, se utilizan para determinar si una hipersuperficie interseca una cuasi-variedad (dada por una cadena regular). De hecho, las cadenas regulares poseen varias propiedades interesantes y son la noción clave en muchos algoritmos para descomponer sistemas de ecuaciones algebraicas o diferenciales.

Las cadenas regulares se han investigado en muchos artículos. ^{[ 6 ] [ 7 ] [ 8 ]}

La abundante literatura sobre el tema se explica por las numerosas definiciones equivalentes de cadena regular. De hecho, la formulación original de Kalkbrener difiere bastante de la de Yang y Zhang. Un punto de encuentro entre estas dos nociones, el punto de vista de Kalkbrener y el de Yang y Zhang, aparece en el artículo de Dongming Wang. ^{[ 9 ]}

Hay varios algoritmos disponibles para obtener la descomposición triangular de V ( F ) tanto en el sentido de Kalkbrener como en el sentido de Lazard y Wen-Tsun Wu . El algoritmo Lextriangular de Daniel Lazard ^{[ 10 ]} y el algoritmo Triade de Marc Moreno Maza ^{[ 11 ]} junto con el método del conjunto característico están disponibles en varios sistemas de álgebra computacional, incluidos Axiom y Maple .

Sea k un cuerpo y x ₁ < ... < x _n variables ordenadas. Denotamos por R = k [ x ₁ , ..., x _n ] el anillo de polinomios correspondiente . Para F ⊂ R , considerado como un sistema de ecuaciones polinómicas, hay dos nociones de una descomposición triangular sobre la clausura algebraica de k . La primera es descomponer perezosamente, representando solo los puntos genéricos del conjunto algebraico V ( F ) en el llamado sentido de Kalkbrener.

${\displaystyle {\sqrt {(F)}}=\bigcap _{i=1}^{e}{\sqrt {\mathrm {sat} (T_{i})}}.}$

El segundo consiste en describir explícitamente todos los puntos de V ( F ) en el llamado sentido de en Lazard y Wen-Tsun Wu .

${\displaystyle V(F)=\bigcup _{i=1}^{e}W(T_{i}).}$

En ambos casos T ₁ , ..., T _e son un número finito de cadenas regulares de R y${\displaystyle {\sqrt {\mathrm {sat} (T_{i})}}}$denota el radical del ideal saturado de T _i mientras que W ( T _i ) denota el cuasi-componente de T _i . Consulte la cadena regular para obtener definiciones de estos conceptos.

Supongamos de ahora en adelante que k es un cuerpo real cerrado . Consideremos S un sistema semialgebraico con polinomios en R. Existen ^{[ 12 ]} un número finito de sistemas semialgebraicos regulares S ₁ , ..., S _e tales que tenemos

${\displaystyle Z_{\mathbf {k} }(S)=Z_{\mathbf {k} }(S_{1})\cup \cdots \cup Z_{\mathbf {k} }(S_{e})}$

donde Z _k ( S ) denota los puntos de k ⁿ que resuelven S . Los sistemas semialgebraicos regulares S ₁ , ..., S _e forman una descomposición triangular del sistema semialgebraico S .

Denotemos Q el cuerpo de los números racionales . En${\displaystyle Q[x,y,z]}$con orden variable${\displaystyle x>y>z}$Consideremos el siguiente sistema polinómico:

${\displaystyle S={\begin{cases}x^{2}+y+z=1\\x+y^{2}+z=1\\x+y+z^{2}=1\end{cases}}}$

Según el código de Maple :

con ( RegularChains ) : R := PolynomialRing ([ x , y , z ]) : sys := { x ^ 2 + y + z - 1 , x + y ^ 2 + z - 1 , x + y + z ^ 2 - 1 } : l := Triangularize ( sys , R ) : map ( Equations , l , R ) ;

Una posible descomposición triangular del conjunto de soluciones de S utilizando la biblioteca RegularChains es:

${\displaystyle {\begin{cases}z=0\\y=1\\x=0\end{cases}}\cup {\begin{cases}z=0\\y=0\\x=1\end{cases}}\cup {\begin{cases}z=1\\y=0\\x=0\end{cases}}\cup {\begin{cases}z^{2}+2z-1=0\\y=z\\x=z\end{cases}}}$

• Método de Wu para el conjunto de características
• Cadena regular
• Sistema semialgebraico regular