NUMEROS ALGEBRAICOS EN SQUEAK

Nuestro trabajo (realizado por Gerardo Richarte y Ariel Pacetti) fue la enseñanza al Squeak de los números algebraicos. Para esto debimos modear primero algunas otras clases, como la clase polinomios, matrices, tuplas, reductor de matrices y un caso un poco más general que es el reductor Euclídeo. Un resumen de dichas clases es el siguiente:

  1. Tuplas (Tuple): esta clase es una cadena de elementos ordenados de longitud dada ( para los que nunca lo vieron pueden pensar por ahora que estos elementos son números , como en R n , y las operaciones se definen de forma análoga a los vectores). Para ver las especificaciones de las mismas, pueden ver el "?" en el browser del Squeak, y ahí esta un poco explicado como se implemento y los métodos mas importantes.
  2. Matrices (Matrix): esta clase son las matrices (la definición matemática de las mismas), la única observación es que las matrices en general no tienen por que tener solo números, en general pueden tener otros objetos. En cuanto a la implementación y los métodos mas importantes, la sugerencia es la misma que con las Tuplas.
  3. Polinomios (Polynomial): todos sabemos lo que son los polinomios, pero esta clase fue implementada de una forma un poco más complicada, ya que modelamos polinomios en general, en varias variables. Lo mas complicado de esta clase es que un polinomio en varias variables puede ser visto de varias formas. Por ejemplo:

F (x) = x 2 * y + x * y = (x 2 * x) * y (esta última visto como polinomio en y)

Esta forma se usa cuando uno quiere derivar un polinomio respecto de una variable, o quiere especializar un polinomio simplemente en algunas variables. Para información en cuanto a la implementación y métodos, mirar en polinomios "?" y fíjense la jerarquía de clases del mismo , para ver todas las clases involucradas, y que función cumple cada una (entre otras: Variable, RaicedVariable, Monomial, MonicMonomial, Polynomial).

4) Reductor de Matrices (MatrixReducer): esta clase contiene un caso particular, en el cual las matrices tienen elementos en un cuerpo, con lo cual usa los inversos, que en general no tiene por que haber. En el caso que los elementos estén en un anillo, se usa la clase EuclideanMatrixReducer, que supone que el anillo es Euclídeo, con lo cual usa la función Euclídea para reducir la matriz. Ambas reducciones se usan en el caso de los números algebraicos para poder calcular determinantes, y el anillo en cuestión será el de los polinomios con coeficientes enteros.

Una vez terminada la introducción, vamos a los números algebraicos propiamente dichos. Un numero algebraico es una raíz de un polinomio en Z[x] (claramente, los racionales son números algebraicos). Luego un numero algebraico queda totalmente determinado por un polinomio, que podemos suponer sin raíces múltiples (si no dividimos al polinomio por el máximo común divisor entre el y su derivado, que obviamente esta implementado en Polynomial bajo el nombre #squareFree), que lo tenga como raíz, y un intervalo en el cual sea la única raíz. (Notar que esta ultima condición es necesaria, ya que si tomamos por ejemplo el polinomio x 2 - 2, claramente las raíces son sqrt Ö 2 y -Ö 2 , y claramente no son iguales, a pesar de que ambas tienen el mismo polinomio).

Fíjense que en la definición de los números algebraicos, usamos un intervalo que tuviera al número en cuestión como única raíz, lo cual se puede hacer usando el método de Sturn (para mayor información mirar la clase Sturn, que esta explicada, y tiene ejemplos). El mismo método fue usado en la suma, producto y otras operaciones de los números algebraicos. Para una explicación completa, con varias propiedades, le pueden mandar un mail al Dr. Leandro Caniglia pidiéndole el del mismo.

La implementación que usamos, muestra al número algebraico (en el #printOn:) como una aproximación numérica con floats del mismo; dicha aproximación puede ser mejorada cuanto se quiere mediante el método #aproximationError: (lean el comentario del mismo para saber bien de que se trata, aunque ya se deben imaginar), tambien existe un mensaje #asFloat que responde el Float que más cerca esta al número algebraico en cuestión.

Por último, fíjense que los números algebraicos, fueron hechos de forma tal que saben convivir con el ambiente, en el sentido de que un numero algebraico sabe sumarse a un entero, evaluarse en un polinomio y varias otras cosas que pueden investigar.

En cuanto a las propiedades y demostraciones que usamos al hacer las cuentas con números algebraicos, a continuación adjuntamos un apunte teórico que preparo Ariel al cursar la materia "Objetos Matemáticos en Smalltalk", dictada por el profesor Dr. Leandro Caniglia el segundo cuatrimestre del año 1997.

Por cualquier duda o sugerencia , nos pueden escribir a las por e-mail a Ariel Pacetti o a Gerardo Richarte (esta preferentemente).

Números Algebraicos - Resultante

DEFINICION: dados dos polinomios f , g en A[X] , donde A es un anillo , se define la resultante entre f y g como:

Si f = å ai (x i ) y g = å bi (x i )

 

| a0 0 0 b0 0 ... 0 |

| a1 0 0 b1 b0 ... 0 |

| . 0 . . 0 |

| . . . . . |

| . . . . b0 |

Res (f , g) = det | . a0 . . b1 |

| . a1 bm bm-1 . |

| an an-1 . 0 bm . |

| 0 an . 0 0 . |

| . 0 . . . . |

| . . . . . . |

| 0 0 an 0 0 bm |

 

Propiedad: si dados dos polinomios , la resultante entre ambos es cero , entonces existen polinomios P y Q en A[X] con deg (P) < deg (g) y deg (Q) < deg (f) tal que P * f + Q * g = 0.

Demostración: sea L una transformación bilineal de An-1 [X] x Am-1 [X] ® An+m-1 [X] la función que vale:

L( r , s ) = r * f + s * g. Queda como ejercicio ver que es bilineal.

Si estudiamos el núcleo de L , son las funciones que cumplen deg (r) < deg (g) y deg (s) < deg (f) tal que r * f + s * g = 0. Como L es lineal , si calculo la matriz de L , el núcleo es no trivial si y solo si el determinante de la matriz es cero ; pero dicho determinante es exactamente la resultante.

Propiedades:

    1. Res ( x , g ) = (-1)deg (g) * g(0). (g como antes )

Dem:

|0 0 ... 0 b0 |

|1 0 ... 0 b1 |

|0 1 ... 0 b2 |

Res ( x , g ) = det | . . . . |

| . . . . |

|0 0 1 bm |

Consideremos la función f = x m+1 - g. Luego det (x * Id - R) = f (x) ( es la matriz compañera) ; donde Id es la matriz identidad y R es la matriz de la resultante. Luego , especializando en cero tenemos que f (0) = -g (0) = det (-R) = - (-1) m *det (R) ; con lo cual g (0) = (-1) m * Res (x , g).

    1. Res (x-a , g) = (-1) m * g (a) . La demostración queda como ejercicio ; considerar el cambio de variables y = x-a.
    2. Res (x * f , g) = (-1) m * g (0) * Res (f , g). Sugerencia para la demostración: escribir quien es la matriz de la resultante y desarrollar por la primer fila el determinante. Recordar que b0 = g (0).
    3. Como Res (x , g) = (-1) m * g (0) , se tiene que Res (x * f , g) = Res (x , g) * Res (f , g).
    4. Res ((x-a) * f , g) = Res (x-a , g) * Res (f , g).
    5. Res (P (X - ai) , g) = P Res ((X - ai) , g). Sugerencia: usar inducción.
    6. De lo anterior se deduce que si f = k * (x - a0) * (x - a1) * ... * (x - an) entonces la Res (f , g) = k (deg (g)) * (-1) (deg (f) * deg (g)) * g(a0) * g(a1)* ... * g(an).

Propiedad: dados dos polinomios en dos variables f(x , y) g(x , y) se tiene que Resy (f , g) (a) = Res (f (a , y) , g (a , y)) si y solo si no se anulan los coeficientes principales de f y g como polinomios en A[x] [y] en el punto a. Sugerencia: escribir la Resy (f , g) , y ver que especializar antes de tomar determinante o después da lo mismo.

 

 

Ideales

Definición: dado A un anillo , un subconjunto I de A se llama ideal si cumple que I es un subgrupo y que " a e A , i e I se cumple que (i * a) e I. ( I * A Ì I). Queda como ejercicio ver que es lo mismo pedir que I + I Ì I y que I * A Ì I.

Un ideal se dice generado por {a1 , a2 , . . . , an} si todo elemento del ideal se escribe como combinación lineal de ellos , donde los escalares están en A. Verificar que el ideal < a1 , a2 , . . . , an > ( el generado por {a1 , a2 , . . . , an} realmente es un ideal.

Proposición: todo ideal de K[X] , donde K es un cuerpo es cíclico (generado por un solo polinomio).

Dem: sea I un ideal de K[X]. Si I = {0} entonces es el generado por el cero. Si tiene algún elemento distinto de cero , sea:

D = { deg (f) / f e I , f ¹ 0 }

Luego D es un subconjunto no vacío de los naturales , con lo cual tiene un primer elemento n. Sea f un elemento de I de grado n. Afirmo D = < f > (generado por f ).

Si g es un elemento de I , deg (g) <= deg (f). Como K es un cuerpo , tengo un algoritmo de división para polinomios , luego f = q * g + r , con r = 0 o deg (r) < deg (f). Si s ¹ 0 , r e I pues

r = f - q * g , y deg (r) < deg (f) que era el primer elemento de D .Absurdo. Luego D = < f >.

Definición: un número real a se dice algebraico si existe un polinomio f e Q[X] tal que f (a) = 0. Notar que Q Ì { números algebraicos}. Si q e Q , el polinomio f (x) = x - q esta en Q[x] y f (q) = 0.

 

 

Dada la noción de u número algebraico se define el polinomio minimal de a como el polinomio de grado mínimo que se anula en a. Veamos que esta bien definido el minimal.

Sea D = { f e Q[X] / f (a) = 0 }.

Verificar que D es un Ideal de Q[x]. Luego por ser un ideal se tiene que D es cíclico , digamos que

D = < q >. Ejercicio , probar que q es el minimal . (Sug. Ver que si existe f e Q[x] , deg (f) < deg (g) entonces g no genera , lo cual es un absurdo).

Observación: notar que puede haber varios polinomios minimales , pero como todos son del mismo grado y se tienen que dividir entre ellos , en realidad están difiriendo en constantes.

Ejercicio: probar que si f e Q[x] , f es irreducible y f (a) = 0 entonces f es minimal. (f irreducible quiere decir que si g \ f con g e Q[x] entonces g = f * k con k constante)

De ahora en mas nos vamos a preocupar en probar el siguiente teorema:

 

 

Teorema: los numero algebraicos forman un cuerpo.

Lo que hay que probar es que 0 y 1 son algebraicos (lo son porque están en Q) , que dados a y b algebraicos , a + b , a * b , 1 / a , -a son también algebraicos.

  1. Si a es algebraico , se f e Q[x] tal que f (a) = 0 ; veamos algún polinomio que mate a 1 / a.

Si f = S ai * (x i) , al hacer f (1 / a) = S ai * ((1 / a) i) . Si sacamos (1 / a)^ n de factor común (donde n = deg (f) ) tenemos:

(1 / a) n * f (1 / a) = (1 / a) n * S ai * (a n-i). Si consideramos g (x) = S a n-i * (x i). Tenemos que g (1 / a) = 0 , y g e Q[x]. Como queríamos ver.

  1. Para el caso -a basta probar que el producto de algebraicos es algebraico , pues -a = (-1) * a y (-1) e Q luego es algebraico.
  2. Veamos el caso de la suma de a + b . Sean f y g e Q[x] dos polinomios irreducibles tal que

f (a) = 0 y g (b) = 0 , queremos hallar un polinomio que mate a a + b. Si hallamos dos polinomios en dos variables tal que al especializar ambos en (a + b , d) se anulan , con d e R , al hallar la resultante respecto de y de ambos , si los coeficientes principales no se anulan en a + b , sirve.

Sean F (x , y) = f (x - y) y G (x , y) = g (y). Ambos se anulan en (a + b , b) , con lo cual solo restaría verificar la otra condición , que queda como ejercicio. ( usar que tanto f como g los supuse irreducibles).

  1. Resta ver el caso producto de dos números algebraicos. Para eso voy a introducir una pequeña noción de polinomio homogéneo.

 

 

Definición: un polinomio f e R [x , y] se dice homogéneo de grado k si " (x , y) e R 2 se tiene que si x e R es f (x * x, x * y) = x k * f (x , y). Notar que esta noción se puede extender a polinomios en una cantidad arbitraria de variables.

Ahora si estamos en condiciones de hallar un polinomio para el producto. Como en el punto 3) , vamos a construir dos polinomios en dos variables tal que al especializar en (a * b , b) se anulen.

Sean G (x , y) = g (y) y F (x , y) el homogeneizado de f, que se construye de la siguiente manera:

Si f (x) = S ai x i , entonces F (x , y) = S ai x i y n-i donde n = deg (f).

Queda como ejercicio verificar que F (x , y) es realmente homogéneo. Luego vale que:

F (a * b , b) = b n * F (a , 1) = b n * f (a) = 0 ; además G (a * b , b) = 0. Luego dejo como ejercicio verificar que el coeficiente principal de F y G al escribirlos como polinomios en y no se anulan , con lo cual la resultante respecto de y verifica que Ry (a * b) = 0 , y como F y G e Q [x , y] ,

Ry (x) e Q [x] , como queríamos ver.

 

Propiedades:

    1. Si a e R , y f (x) e Q [x] tal que f (a) = 0 , entonces quién mata a a ½ ? Es fácil verificar que si consideramos el polinomio g (x) = f (x 2) cumple lo pedido anteriormente.
    2. Si a e R , y f (x) e Q [x] tal que f (a) = 0 , entonces quién mata a a 2 ?

Si f (x) = x * F (x 2) + G (x 2) , entonces vale que G 2 (x) - x * F 2 (x) es un polinomio en Q [x] que mata a a 2 . Notar que G 2 (x) - x * F 2 (x) = ( G (x) + x ½ * F (x)) * ( G (x) - x ½ * F (x)) en R [x] , y dicho polinomio claramente se anula en a 2 , como queríamos ver.

Ejercicio: probar que si f (x) es irreducible en Q [x] , y F (x) ¹ 0 , entonces G 2 (x) - x * F 2 (x) es irreducible en Q [x].