Section 13 Appendix: Error Correcting Codes

gap> R := Integers mod 2;
GF(2)
gap> x := X(R,"x");
x
gap> g := 1 + x^2 + x^3;
x^3+x^2+Z(2)^0
gap> a := x+x^2+x^4;
x^4+x^2+x
gap> b := a*g;
x^7+x^6+x^5+x^4+x^3+x^2+x

Exercise 13A.1
gap> (1+x)*g;
x^4+x^2+x+Z(2)^0
gap> (1+x^2)*g;
x^5+x^4+x^3+Z(2)^0
gap> (x+x^2)*g;
x^5+x^3+x^2+x
gap> (1+x+x^2)*g;
x^5+x+Z(2)^0
gap> IntVecFFE(CoefficientsOfUnivariatePolynomial((1+x+x^2)*g));
[ 1, 1, 0, 0, 0, 1 ]
gap> IntVecFFE(CoefficientsOfUnivariatePolynomial((1+x+x^2+x^3)*g));
[ 1, 1, 0, 1, 0, 0, 1 ]
gap> CoefficientsOfUnivariatePolynomial((1+x+x^2+x^3)*g)
> ;
<an immutable GF2 vector of length 7>

gap> Factors(g);
[ x^3+x^2+Z(2)^0 ]
gap> polyring := PolynomialRing(GF(8));
PolynomialRing(..., [ x ])
gap> factors := Factors(polyring,g);
[ x+Z(2^3)^3, x+Z(2^3)^5, x+Z(2^3)^6 ]
gap> a := -Z(2^3)^3;
Z(2^3)^3
gap> a^2; a^3; a^4; a^5; a^6; a^7;
Z(2^3)^6
Z(2^3)^2
Z(2^3)^5
Z(2^3)
Z(2^3)^4
Z(2)^0
gap> 1+a;
Z(2^3)
gap> 1+a^2;
Z(2^3)^2
gap> a+a^2;
Z(2^3)^4
gap> 1+a+a^2;
Z(2^3)^5

Exercise 13A.4
gap> Factors(polyring,x^7-1);
[ x+Z(2)^0, x+Z(2^3), x+Z(2^3)^2, x+Z(2^3)^3, x+Z(2^3)^4, x+Z(2^3)^5, x+Z(2^3)^6 ]

gap> v := x+x^2+x^5+x^6;
x^6+x^5+x^2+x
gap> v/g;
(x^6+x^5+x^2+x)/(x^3+x^2+Z(2)^0)
gap> PolynomialReducedRemainder(v,[g],MonomialTotalDegreeLess);
x+Z(2)^0
gap> w := v + x^5;
x^6+x^2+x
gap> w/g;
x^3+x^2+x

Exercise 13A.5
gap> v := x + x^4+x^5+x^6;
x^6+x^5+x^4+x
gap> v/g;
x^3+x
gap> v:= 1+x+x^2+x^4+x^5+x^6;
x^6+x^5+x^4+x^2+x+Z(2)^0
gap> v/g;
(x^6+x^5+x^4+x^2+x+Z(2)^0)/(x^3+x^2+Z(2)^0)
gap> PolynomialReducedRemainder(v,[g],MonomialTotalDegreeLess);
x^2+Z(2)^0
gap> w := v+x^3;
x^6+x^5+x^4+x^3+x^2+x+Z(2)^0
gap> w/g;
x^3+x+Z(2)^0

Section 14: Galois Theory
gap> x := X(Rationals, "x");
x
gap> Factors(x^4-10*x^2+1);
[ x^4-10*x^2+1 ]
gap> F := AlgebraicExtension(Rationals,x^4-10*x^2+1);
<field in characteristic 0>
gap> a := RootOfDefiningPolynomial(F);
(a)
gap> a^4;
(-1+10*a^2)
gap> x := X(GF(3),"x");
x
gap> Factors(x^9-x);
[ x, x+Z(3)^0, x-Z(3)^0, x^2+Z(3)^0, x^2+x-Z(3)^0, x^2-x-Z(3)^0 ]
gap> F := AlgebraicExtension(GF(3),x^2+Z(3)^0);
<field of size 9>
gap> g := GaloisGroup(AsField(GF(3),GF(81)));
<group with 1 generators>
gap> Order(g);
4
gap> Elements(g);
[ IdentityMapping( GF(3^4) ), FrobeniusAutomorphism( GF(3^4) )^2, FrobeniusAutomorphism( GF(3^4) ), 
  FrobeniusAutomorphism( GF(3^4) )^3 ]
gap> Order(Elements(g)[3]);
4
gap> Subfields(GF(81));
[ GF(3), GF(3^2), GF(3^4) ]

gap> alpha:=Sqrt(2)+Sqrt(3); MinimalPolynomial(Rationals,alpha); 
E(24)-E(24)^11-E(24)^14+E(24)^17-E(24)^19+E(24)^22
x^4-10*x^2+1

Exercise 14.1
gap> g := GaloisGroup(AsField(GF(2),GF(8)));
<group with 1 generators>
gap> Order(g);
3
gap> g := GaloisGroup(AsField(GF(2),GF(32)));
<group with 1 generators>
gap> Order(g);
5
gap> g := GaloisGroup(AsField(GF(2),GF(512)));
<group with 1 generators>
gap> Order(g);
9

Exercise 14.2
gap> g := GaloisGroup(AsField(GF(3),GF(9)));
<group with 1 generators>
gap> Order(g);
2
gap> g := GaloisGroup(AsField(GF(3),GF(3^6)));
<group with 1 generators>
gap> Order(g);
6

Exercise 14.3
gap> g := GaloisGroup(AsField(GF(9),GF(81)));
<group with 1 generators>
gap> Order(g);
2
gap> g := GaloisGroup(AsField(GF(9),GF(3^8)));
<group with 1 generators>
gap> Order(g);
4
gap> g := GaloisGroup(AsField(GF(9),GF(3^10)));
<group with 1 generators>
gap> Order(g);
5
gap> g := GaloisGroup(AsField(GF(25),GF(625)));
<group with 1 generators>
gap> Order(g);
2
gap> g := GaloisGroup(AsField(GF(25),GF(5^6)));
<group with 1 generators>
gap> Order(g);
3

Exercise 14.4
gap> g := GaloisGroup(AsField(GF(27),GF(3^6)));
<group with 1 generators>
gap> Order(g);
2
gap> g := GaloisGroup(AsField(GF(27),GF(3^9)));
<group with 1 generators>
gap> Order(g);
3

gap> x := X(Rationals,"x");
x
gap> CyclotomicPolynomial(Rationals,15);
x^8-x^7+x^5-x^4+x^3-x+1
gap> Factors(x^8-x^7+x^5-x^4+x^3-x+1);
[ x^8-x^7+x^5-x^4+x^3-x+1 ]
gap> f := CF(8);
CF(8)
gap> E(8);
E(8)
gap> E(8)^8;
1
gap> E(8)^2;
E(4)
gap> E(8)^4;
-1
gap> CyclotomicPolynomial(Rationals,8);
x^4+1
gap> Subfields(f);
[ Rationals, GaussianRationals, CF(8), NF(8,[ 1, 3 ]), NF(8,[ 1, 7 ]) ]
gap> g :=GaloisGroup(AsField(Rationals,CF(8)));
<group of size 4 with 2 generators>
gap> Elements(g);
[ IdentityMapping( CF(8) ), ANFAutomorphism( CF(8), 3 ), ANFAutomorphism( CF(8), 5 ), ANFAutomorphism( CF(8), 7 ) ]
gap> e := Elements(g);
[ IdentityMapping( CF(8) ), ANFAutomorphism( CF(8), 3 ), ANFAutomorphism( CF(8), 5 ), ANFAutomorphism( CF(8), 7 ) ]
gap> Order(e[1]);
1
gap> Order(e[2]);
2
gap> Order(e[3]);
2
gap> Order(e[4]);
2
gap> LogTo();