Introduction + Galois Theory

[Alice Liu]

Hi my name is Alice Liu, I am a third year Maths student at UCL.

I am interested in implementing computation of Galois groups for a given polynomial, I am wondering if this is enough material for a stand-alone project? 

Also is the desired computation just for the Galois group of the splitting field of the given polynomial over ; or a more abstract and more general approach should be taken? Also do I need to aim for writing codes for the Galois correspondence of associated intermediate fields?

Also shall I aim to write a patch for the Combinatorics module or any patch I write would suffice?

Thank you!

[Aaron Meurer]

On Fri, Feb 16, 2018 at 9:08 AM, Alice Liu <wuruis...@gmail.com> wrote:

Hi my name is Alice Liu, I am a third year Maths student at UCL.

I am interested in implementing computation of Galois groups for a given polynomial, I am wondering if this is enough material for a stand-alone project? 

I'm not familiar with the algorithms required for this, but I think it should be enough material (you didn't mention it but I'm assuming this is for GSoC). 

Do you know what references you would use to implement this? If you don't know yet, I would start by looking at what algorithms GAP uses. 

 

Also is the desired computation just for the Galois group of the splitting field of the given polynomial over ; or a more abstract and more general approach should be taken? Also do I need to aim for writing codes for the Galois correspondence of associated intermediate fields?

I would definitely just focus on Q for starters, but it would be nice to design the API of the module so that it could be generalized if desired. SymPy already has a delineation of different fields in the polys module, so this shouldn't be hard. Although if a given algorithm extends nicely to other fields it would make sense to support them all from the start. 

Regarding the correspondence, I don't know. I suppose it depends if that falls out nicely from the algorithm or not. Another question: does the correspondence help to compute the roots in closed form, for the instances where the Galois group is solvable? I was never clear if knowing the Galois group helps you here or not.

 

Also shall I aim to write a patch for the Combinatorics module or any patch I write would suffice?

Technically the rules require any patch anywhere, but I would recommend making a patch to the code that you would be modifying for the project if you can. This is better because

1. a more technically complicated patch will shine better on you than a simple one, and

2. if you are accepted, it is code you would be modifying anyway. So it's good to get a head start on modifying that code. 

With that being said, don't be afraid to start somewhere simpler if you still need to get your feet wet. 

Aaron Meurer

Thank you!

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscribe@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/5aa69e5e-7a2b-4868-b4f4-861dc4ff7414%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Alice Liu]

Hi thank you for your reply! Yes this is for GSoC.

There are general steps for calculating the Galois Group (I am using "Galois Theory" by Ian Stewart as my reference), involving the tower law and working out the the Q-automorphisms of K (K being the splitting field for the given polynomial). I am not too sure about that precise algorithms.

For the tower law, I am not too sure if field extensions and its degree are implemented in SymPy? I am aware there is a algebraic field class in the polys module, that gives you Q(α) from Q. But is it worth implementing field extension Q(α)(β):Q(α) for example. Also I might need a bit of help with understanding the code (what is dtype?). 

And for example: 

def from_QQ_gmpy(K1, a, K0):
	"""Convert a GMPY ``mpq`` object to ``dtype``. """
	return K1(K1.dom.convert(a, K0))

I don't quite understand this - it seems to do with rational fields.

In GAP you mentioned, fields are generated as follows

58.1-3 Field
‣ Field( z, ... )

( function )

‣ Field( [F, ]list )

( function )

Field returns the smallest field K that contains all the elements z, ..., or the smallest field K that contains all elements in the list list. If no subfield F is given, K is constructed as a field over itself, i.e. the left acting domain of K is K. Called with a field F and a list list, Field constructs the field generated by F and the elements in list, as a vector space over F.

I am wondering if you could do similar thing in SymPy? Again I might need help understanding the field class in the polys module.

58.3-1 GaloisGroup
‣ GaloisGroup( F )

( attribute )

The Galois group of a field F is the group of all field automorphisms of F that fix the subfield K =LeftActingDomain( F ) pointwise.
Note that the field extension F > K need not be a Galois extension.
gap> g:= GaloisGroup( AsField( GF(2^2), GF(2^12) ) );;
gap> Size( g ); IsCyclic( g );
6
true
gap> h:= GaloisGroup( CF(60) );;
gap> Size( h ); IsAbelian( h );
16
true

Then they used this for the Galois group, not sure if it can tell you the abstract structure of the whole group, or just test for properties. (and I am not sure I understand how to tell what K is in this context?)

Also I am not too sure if automorphisms are implemented in SymPy? (I am aware that group isomorphism is yet to be implemented in SymPy?)

The correspondence is between the subgroups of the Galois Group and the intermediate fields of K:L, so if you draw a lattice diagram the diagram looks the same. I think this might be too difficult to implement.

Thank you!

[Aaron Meurer]

On Sat, Mar 3, 2018 at 12:56 PM, Alice Liu <wuruis...@gmail.com> wrote:

Hi thank you for your reply! Yes this is for GSoC.

There are general steps for calculating the Galois Group (I am using "Galois Theory" by Ian Stewart as my reference), involving the tower law and working out the the Q-automorphisms of K (K being the splitting field for the given polynomial). I am not too sure about that precise algorithms.

For the tower law, I am not too sure if field extensions and its degree are implemented in SymPy? I am aware there is a algebraic field class in the polys module, that gives you Q(α) from Q. But is it worth implementing field extension Q(α)(β):Q(α) for example. Also I might need a bit of help with understanding the code (what is dtype?). 

And for example: 

def from_QQ_gmpy(K1, a, K0):
	"""Convert a GMPY ``mpq`` object to ``dtype``. """
	return K1(K1.dom.convert(a, K0))

I don't quite understand this - it seems to do with rational fields.

The polys code is organized in layers. The bottommost layer, which you are looking at, deals directly with the coefficient data types (called dtypes, from numpy parlance). Here the function works specifically on gmpy data. If gmpy is not installed, a different function (most likely from_QQ_python) would be used. In these low level functions, K refers to the domain (the ring). Here (as I understand it), a is an element of K0, and it is converted to K1. K0 might be something like QQ and K1 something like QQ[x]. 

These low level functions are generally only where the polynomial algorithms are written, because that is the fastest way. For the Galois group project, I would focus on higher levels, working directly with the Poly() or ring() objects. This is what is documented at http://docs.sympy.org/latest/modules/polys/index.html. 

In GAP you mentioned, fields are generated as follows

58.1-3 Field
‣ Field( z, ... )

( function )

‣ Field( [F, ]list )

( function )

Field returns the smallest field K that contains all the elements z, ..., or the smallest field K that contains all elements in the list list. If no subfield F is given, K is constructed as a field over itself, i.e. the left acting domain of K is K. Called with a field F and a list list, Field constructs the field generated by F and the elements in list, as a vector space over F.

I am wondering if you could do similar thing in SymPy? Again I might need help understanding the field class in the polys module.

Look at the field() and ring() functions. 

58.3-1 GaloisGroup
‣ GaloisGroup( F )

( attribute )

The Galois group of a field F is the group of all field automorphisms of F that fix the subfield K =LeftActingDomain( F ) pointwise.
Note that the field extension F > K need not be a Galois extension.
gap> g:= GaloisGroup( AsField( GF(2^2), GF(2^12) ) );;
gap> Size( g ); IsCyclic( g );
6
true
gap> h:= GaloisGroup( CF(60) );;
gap> Size( h ); IsAbelian( h );
16
true

Then they used this for the Galois group, not sure if it can tell you the abstract structure of the whole group, or just test for properties. (and I am not sure I understand how to tell what K is in this context?)

Also I am not too sure if automorphisms are implemented in SymPy? (I am aware that group isomorphism is yet to be implemented in SymPy?)

The correspondence is between the subgroups of the Galois Group and the intermediate fields of K:L, so if you draw a lattice diagram the diagram looks the same. I think this might be too difficult to implement.

I don't know the answers to the group theory module questions. Someone else will need to comment. I recommend going to https://gitter.im/sympy/GroupTheory, which is the gitter group for last year's group theory GSoC project, and asking there. It may also be helpful to look at the report for that project (https://github.com/sympy/sympy/wiki/GSoC-2017-Report-Valeriia-Gladkova:-Group-Theory) to get an idea of the current state of the group theory module.

Aaron Meurer

 

Thank you!

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscribe@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/0e925b3d-412c-4bf4-bf9e-033e8389ce40%40googlegroups.com.