Teste 4
Matemática Discreta LEIC 2011/2012

50 minutos
Enunciado A
Não é permitido o uso de máquina de calcular nem de qualquer  tipo de consulta. 

Número:                            Nome:

Grupo I (10 val)

Obtenha, usando a transformada de Fourier discreta e sua inversa nas raízes da unidade apropriadas, o produto dos polinómios p(x) = 3 x - 4 e q(x) = 2 (x^2)+ x.

Como o polinómio p tem grau 1 e o polinómio q tem grau 2, o produto dos dois será um polinómio de grau 1+2=3, pelo que trabalharemos com as raízes da unidade de ordem 4.

Representamos o polinómio p por (Subscript[DFT, 4])(-4,3,0,0)=(-1,-4+3i,-7,-4-3i) pois

(Subscript[DFT, 4])(-4,3,0,0)=(-1,-4+3i,-7,-4-3i)   em (1,i,-1,-i)
|
------------------------------
|                                                              |
           (Subscript[DFT, 2])(-4,0)=                       (Subscript[DFT, 2])(3,0) =
                 (-4,-4)                                   (3,3)          em (1,-1)
|                                                              |
---------------                                --------------
      |                              |                             |                            |      
(Subscript[DFT, 1])(-4)=          (Subscript[DFT, 1])(0)=        (Subscript[DFT, 1])(3)=     (Subscript[DFT, 1])(0)=
 (-4)                      (0)                       (3)                   (0)    em (1)

Representamos o polinómio q por (Subscript[DFT, 4])(0,1,2,0)=(3,-2+i,1,-2-i) pois

(Subscript[DFT, 4])(0,1,2,0)=(3,-2+i,1,-2-i)   em (1,i,-1,-i)
|
------------------------------
|                                                              |
           (Subscript[DFT, 2])(0,2)=                       (Subscript[DFT, 2])(1,0) =
                 (2,-2)                                   (1,1)          em (1,-1)
|                                                              |
---------------                                --------------
      |                              |                             |                            |      
(Subscript[DFT, 1])(0)=          (Subscript[DFT, 1])(2)=        (Subscript[DFT, 1])(1)=     (Subscript[DFT, 1])(0)=
 (0)                      (2)                       (1)                   (0)    em (1)

Tem-se então que o polinómio p\[Cross]q é representado por 
(-1,-4+3i,-7,-4-3i)\[Cross](3,-2+i,1,-2-i)=(-3,5-10i,-7,5+10i).

Calculando (Subscript[DFT, 4]^(-1))(-3,5-10i,-7,5+10i)=(1/4).(Subscript[DFT, 4])(-3,5+10i,-7,5-10i),

(Subscript[DFT, 4])(-3,5+10i,-7,5-10i)=(0,-16,-20,24)   em (1,i,-1,-i)
|
------------------------------
|                                                              |
           (Subscript[DFT, 2])(-3,-7)=                       (Subscript[DFT, 2])(5+10i,5-10i) =
                 (-10,4)                                   (10,20i)          em (1,-1)
|                                                              |
---------------                                --------------
      |                              |                             |                            |      
(Subscript[DFT, 1])(-3)=          (Subscript[DFT, 1])(-7)=        (Subscript[DFT, 1])(5+10i)=     (Subscript[DFT, 1])(5-10i)=
 (-3)                      (-7)                         (5+10i)                (5-10i)    em (1)

tem-se então (Subscript[DFT, 4]^(-1))(-3,5-10i,-7,5+10i)=((0/4),((-16)/4),((-20)/4),(24/4))=(0,-4,-5,6) e tem-se 
p\[Cross]q(x)=6(x^3)-5(x^2)-4x.

Grupo III (8 val)

Confirme que G={x+y+2(y^2),2 y+x y,- x+(x^2)} é uma base de Gröbner em (Subscript[ℤ, 3])[{x,y}]. Será reduzida? Justifique. 
Verifique se o polinómio 2 (x^2) (y^2) + (y^2)- 1 pertence ao ideal gerado por G.

p1:2(y^2)+x+y
p2:x y+2y
p3:(x^2)-x

B(p1,p2)=x(2(y^2)+x+y)-2y(x y+2y)=2x (y^2)+(x^2)+x y-2x (y^2)-4(y^2)(Subscript[=, 3])(x^2)+x y-(y^2)

(x^2)+x y-(y^2)                              |   (x^2)-x
                                                              -------------
-(x^2)+x                                              1
--------------------                                                              
    x y-(y^2) +x                             |   x y+2y
                                                               --------------
-x y-2y                                         1
--------------------                                                   
         -(y^2) +x-2y                          |   2(y^2)+x+y           
                                                               ---------------
   -2(y^2)-x-y                           1
---------------------                                              
0

B(p1,p3)=(x^2)(2(y^2)+x+y)-2(y^2)((x^2)-x)=2(x^2) (y^2)+(x^3)+(x^2)y-2(x^2) (y^2)+2x (y^2)=(x^3)+(x^2)y+2x (y^2)

(x^3)+(x^2)y+2x (y^2)                          |   (x^2)-x
                                                              -------------
-(x^3)+(x^2)                                                  x+y+1
--------------------                                                              
(x^2)y+2x (y^2) +(x^2)                                         
-(x^2)y+x y                                            
--------------------                                                          
2x (y^2) +(x^2)+x y                                         
-(x^2)+x                               
--------------------                                                        
     2x (y^2) +x y+x                         |  2(y^2)+x+y
                                                               --------------
-2x (y^2)-(x^2)-x y                                   x
--------------------                                                   
          -(x^2)+x                                   |    (x^2)-x          
                                                               ---------------
    (x^2)-x                                          -1
---------------------                                              
0

B(p2,p3)=x(x y+2y)-y((x^2)-x)=(x^2)y+2x y-(x^2)y+x y=3x y(Subscript[=, 3])0

Como todos os polinómios de Buchberger se reduzem a 0 módulo G, G é de facto uma base de Grobner. A base não é reduzida pois o polinómio p1 não é mónico.

O polinómio 2(x^2) (y^2)+(y^2)-1 não pertence ao ideal pois não se reduz a 0. De facto:

2(x^2) (y^2)+(y^2)-1                             |   2(y^2)+x+y
                                                           -------------
-2(x^2)(y^2)-(x^3)-(x^2)y                                       (x^2)
--------------------                                                              
-(x^3)-(x^2)y+(y^2)-1                     |   (x^2)-x
                                                             --------------
(x^3)-(x^2)                                             -x-y-1
--------------------                                                   
             -(x^2)y-(x^2)+(y^2)-1                                                                               
(x^2)y -x y                      
---------------------                                              
-(x^2)+(y^2)-x y -1
(x^2)-x
---------------------                                               
(y^2)-x y -x-1                            | x y+2y
                                                             --------------
 x y+2y                                            -1                      
---------------------                                              
 (y^2)-x+2y-1                             | 2(y^2)+x+y
                                                             --------------
2(y^2)+x+y                                    -1
--------------------                                                   
      -1

e -1 é irredutível.