Re: Computing Galois groups

[Fabio Stumbo]

Hi Daniel,

as I said, I traced the progress of my function and I know what the 
problem is.

I extracted the relevant lines of code which go to the core of the 
problem in a simple example which can be easily followed: the problem is 
reduced to evaluating a polynomial.

Here it is, together with my considerations.

---------------------

The code:


f := x^3-1
A := rootsOf(f,x)
X : List(Expression(Integer)) := [1,2,3]
R := [
      A.1*X.1+A.2*X.2+A.3*X.3,_
      A.1*X.1+A.2*X.3+A.3*X.2,_
      A.1*X.3+A.2*X.2+A.3*X.1,_
      A.1*X.2+A.2*X.1+A.3*X.3,_
      A.1*X.2+A.2*X.3+A.3*X.1,_
      A.1*X.3+A.2*X.1+A.3*X.2 _
      ]
F := reduce(*,[x-R.i for i in 1..6])
F := F :: Expression(INT) :: POLY(INT)
discriminant(F)
factorization := factor(F)
F1 := nthFactor(F,1)
F2 := nthFactor(F,2)
F3 := nthFactor(F,3)
eval(F,x,R.1)
eval(F1,x,R.1)
eval(F2,x,R.1)
eval(F3,x,R.1)

---------------------

A few words to comment the code.

f is the polynomial of which we want to compute the Galois group (in 
this case, Z/2Z).

A is the set of its roots.

Call r the first element in X, i.e. r = R.1 = A.1*X.1+A.2*X.2+A.3*X.3

The elements of R are s.r, where s runs over all elements of S3, the 
symmetric group on {1,2,3}, acting on the indeces.

r is what is known as a "Galois resolvent", provided that all elements 
in R are different; if this is the case, r is shown (by Galois) to be a 
primitive element for the splitting field of f.

F is the polynomial (x-R.1)*...*(x-R.6), which is the Kronecker 
(polynomial) resolvent, if r is a Galois resolvent. Now we can check 
that r is actually a Galois resolvent by computing the discriminant of F.

F is in Z[x], being invariant by all permutations.

From Kronecker's theorem you deduce that if you factorize F then the 
permutations that fix a factor of F are (isomorphic to) the Galois group 
of f.

F factorizes into three factors: F=F1*F2*F3, each of degree 2 (which 
tells us that the Galois group has cardinality 2).

----------------------

The problem: by construction, r is a root of F and you can check this by

eval(F,x,R.1) = 0

Since F=F1*F2*F3 this implies that exactly one of

eval(F1,x,R.1) = 0
eval(F2,x,R.1) = 0
eval(F3,x,R.1) = 0

must hold.

The problem is that none holds.

----------------------

Questions:

1. Why?
2. How can I check which of the Fi has r as root?
3. After this, I need to evaluate that polynomial to all others elements 
of R in order to find all of its roots.

----------------------

What I could understand so far of why there is this problem:

Let's call for short a,b,c the three roots of f: (a,b,c) = (A.1,A.2,A.3).
The internal representation of a,b,c is
[a,b,c] = [%x0,%x0 %x1,- %x0 %x1 - %x0]
Again, to simplifyand have a better understanding, let u=%x0, v=%x1, so that
[a,b,c] = [u,uv,-uv-u]

Now, the three roots of f are 1,z,z^2, where z=(-1+sqrt(3))/2.

Axiom doesn't declare which is which, so you can have any order for a,b,c:

[a,b,c] = [1,z,z^2]  =>  u=1,   v=z
[a,b,c] = [1,z^2,z]  =>  u=1,   v=z^2
[a,b,c] = [z,1,z^2]  =>  u=z,   v=z^2
[a,b,c] = [z,z^2,1]  =>  u=z,   v=z=u
[a,b,c] = [z^2,1,z]  =>  u=z^2, v=z
[a,b,c] = [z^2,z,1]  =>  u=z^2, v=z^2=u

Any choice is admissible, since the only relation which is assumed is 
a+b+c=0.

Now, one among F1, F2 or F3 must be the minimal polinomial of r=a+2b+3c 
but which one is the correct one depends very much ont the choice you 
make. Case by case, you have:

   r        minimal polynomial
1+2z+3z^2     F3
1+2z^2+3z     F3
z+2+3z^2      F2
z+3+2z^2      F1
z^2+2+3z      F2
z^2+2z+3      F1


----------------------------------------


I hope to have explained myself.

Best wishes

Fabio



Il 07/05/22 16:42, Daniel Herring ha scritto:
> Hi Fabio,
>
> I don't have the time or energy to do a proper review for you.
>
> That said, trying to explain an algorithm can be an effective way of 
> finding the flaws in it.  Start with the code and derive the purpose. 
> This often reveals an inconsistency with the original high-level 
> algorithm.
>
> Unfortunately, other bugs come from an incorrect understanding of the 
> tool you are trying to use, in this case Axiom.  These can require an 
> experienced developer to find, as you see what you expect, and they 
> see what the computer actually does.  Sometimes you can reduce this 
> issue by replacing binary operators with named functions (less parsing 
> mistakes). Other times you can do "the same thing" with a different 
> choice of functions or operators, and compare results.
>
> Do you have a simple example of when the algorithm does not work? 
> Tracing its progress step by step can help spot the bug.  This 
> approach doesn't prove the overall algorithm, but it does eliminate 
> one defect.
>
> Best wishes!
>
> -- Daniel
>
>
> On Sat, 7 May 2022, Fabio Stumbo wrote:
>
> > Hi,
> >
> > I am trying to compute some Galois groups with Axiom.
> >
> > A way is to go after the example given in section 8.13 of the manual 
> > which follows closely and implements the original definition by 
> > Galois of the Galois group.
> >
> > I am trying a different way: I would like to exploit a theorem by 
> > Kronecker which provides an easy algorithm to compute the Galois 
> > group of a given polynomial.
> >
> > I wrote the function which implements the algorithm and it works... 
> > sometimes. :(
> >
> > Which means that I have some problems.
> >
> > My question is: is there anybody that is willing to help me to fix it 
> > if I post the code?
> >
> > The code is not very long (about 40-50 lines) but it needs to be 
> > explained, so I am asking before to make the effort.
> >
> > TIA
> >
> > Fabio