El método de Wenjun Wu es un algoritmo para resolver ecuaciones polinómicas multivariadas introducido a finales de la década de 1970 por el matemático chino Wen-Tsun Wu . Este método se basa en el concepto matemático de conjunto característico introducido a finales de la década de 1940 por JF Ritt . Es totalmente independiente del método de base de Gröbner , introducido por Bruno Buchberger (1965), aunque las bases de Gröbner pueden utilizarse para calcular conjuntos característicos. [1] [2]
El método de Wu es poderoso para la demostración de teoremas mecánicos en geometría elemental y proporciona un proceso de decisión completo para ciertas clases de problemas. Se ha utilizado en investigaciones en su laboratorio (KLMM, Laboratorio Clave de Mecanización Matemática en la Academia China de Ciencias) y en todo el mundo. Las principales tendencias de investigación sobre el método de Wu se refieren a sistemas de ecuaciones polinómicas de dimensión positiva y álgebra diferencial donde los resultados de Ritt se han hecho efectivos. [3] [4] El método de Wu se ha aplicado en varios campos científicos, como la biología, la visión por computadora , la cinemática de robots y especialmente las pruebas automáticas en geometría. [5]
El método de Wu utiliza la división de polinomios para resolver problemas de la forma:
donde f es una ecuación polinómica e I es una conjunción de ecuaciones polinómicas . El algoritmo es completo para este tipo de problemas en el dominio complejo .
La idea central del algoritmo es que se puede dividir un polinomio por otro para obtener un resto. Si se repite la división, el resto desaparece (en cuyo caso la afirmación "I" implica que f es verdadera) o queda un resto irreducible (en cuyo caso la afirmación es falsa).
Más específicamente, para un ideal I en el anillo k [ x 1 , ..., x n ] sobre un cuerpo k , un conjunto característico (Ritt) C de I está compuesto por un conjunto de polinomios en I , que tiene forma triangular: los polinomios en C tienen variables principales distintas (ver la definición formal a continuación). Dado un conjunto característico C de I , se puede decidir si un polinomio f es cero módulo I . Es decir, la prueba de pertenencia es comprobable para I , siempre que haya un conjunto característico de I .
Un conjunto característico de Ritt es un conjunto finito de polinomios en forma triangular de un ideal. Este conjunto triangular satisface cierta condición mínima con respecto al ordenamiento de Ritt y conserva muchas propiedades geométricas interesantes del ideal. Sin embargo, puede que no sea su sistema de generadores.
Sea R el anillo polinomial multivariado k [ x 1 , ..., x n ] sobre un cuerpo k . Las variables están ordenadas linealmente según su subíndice: x 1 < ... < x n . Para un polinomio no constante p en R, la variable más grande que se presenta efectivamente en p , llamada variable principal o clase , juega un papel particular: p puede considerarse naturalmente como un polinomio univariante en su variable principal x k con coeficientes en k [ x 1 , ..., x k −1 ]. El grado de p como polinomio univariante en su variable principal también se llama su grado principal.
Un conjunto T de polinomios no constantes se denomina conjunto triangular si todos los polinomios en T tienen variables principales distintas. Esto generaliza los sistemas triangulares de ecuaciones lineales de manera natural.
Para dos polinomios no constantes p y q , decimos que p es menor que q con respecto al ordenamiento de Ritt y se escribe p < r q , si se cumple una de las siguientes afirmaciones:
De esta manera, ( k [ x 1 , ..., x n ], < r ) forma un buen orden parcial . Sin embargo, el ordenamiento de Ritt no es un orden total : existen polinomios p y q tales que ni p < r q ni p > r q . En este caso, decimos que p y q no son comparables. El ordenamiento de Ritt compara el rango de p y q . El rango, denotado por rank( p ), de un polinomio no constante p se define como una potencia de su variable principal: mvar( p ) mdeg( p ) y los rangos se comparan comparando primero las variables y luego, en caso de igualdad de las variables, los grados.
Una generalización crucial sobre el ordenamiento de Ritt es comparar conjuntos triangulares. Sean T = { t 1 , ..., t u } y S = { s 1 , ..., s v } dos conjuntos triangulares tales que los polinomios en T y S están ordenados de forma creciente según sus variables principales. Decimos que T es menor que S con respecto al ordenamiento de Ritt si se cumple una de las siguientes afirmaciones
Además, existen conjuntos triangulares incomparables con respecto al ordenamiento de Ritt.
Sea I un ideal distinto de cero de k[x 1 , ..., x n ]. Un subconjunto T de I es un conjunto característico de Ritt de I si se cumple una de las siguientes condiciones:
Un ideal polinomial puede poseer (infinitamente) muchos conjuntos característicos, ya que el ordenamiento de Ritt es un orden parcial.
El proceso Ritt-Wu, ideado primero por Ritt y posteriormente modificado por Wu, no calcula una característica de Ritt sino una extendida, llamada conjunto de características de Wu o cadena ascendente.
Un subconjunto no vacío T del ideal ⟨F⟩ generado por F es un conjunto característico Wu de F si se cumple una de las siguientes condiciones
El conjunto característico de Wu se define como el conjunto F de polinomios, en lugar del ideal ⟨F⟩ generado por F. También se puede demostrar que un conjunto característico de Ritt T de ⟨F⟩ es un conjunto característico de Wu de F. Los conjuntos característicos de Wu se pueden calcular mediante el algoritmo CHRST-REM de Wu, que solo requiere cálculos de pseudorestos y no se necesitan factorizaciones.
El método de conjuntos característicos de Wu tiene una complejidad exponencial; se introdujeron mejoras en la eficiencia computacional mediante cadenas débiles, cadenas regulares y cadenas saturadas [6].
Una aplicación es un algoritmo para resolver sistemas de ecuaciones algebraicas mediante conjuntos característicos. Más precisamente, dado un subconjunto finito F de polinomios, existe un algoritmo para calcular conjuntos característicos T 1 , ..., T e tales que:
donde W ( T i ) es la diferencia de V ( T i ) y V ( h i ), aquí h i es el producto de las iniciales de los polinomios en T i .
