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