PSE Lectures - Ep 7 -Deep dive into Finite Abelian Groups and it's properties

Transcript

this call is now being recorded all right so um I I want to start by a remark suppose you have a um to integers which are co-prime then less time um I said that well okay

um if if there are core Prime then uh last time we showed that a k is a generator of integers modulation so this means that there is some v such that if in particular v v k is equal to one module n which means that there is some U

such that a 3K plus u n is equal to one okay so and these These are called UV are the the zoo coefficients but which are generally not unique so just be careful but uh this this kind of statement

um has has a more General version where you could you could take a any two integers with a which are not necessarily called Prime and then the Brazil coefficients will give you a that I mean U times n plus v times K would would be equal to the gcd of K and N but we actually only use this uh this version so far so so this is a this is a proof now

we continue with the classification of uh finite a billion groups and I remind you that we write a in a billion group now with an additive notation and uh suppose

the order of the group is some well has Prime decomposition foreign [Music] the the set for now a GPI which is all the elements X in G such that the order of X is some some power of p i so p i to the n

X is equal to zero for sum n right and and N can can be different for different uh different x's in in this group and we showed that this is uh this is a subgroup of of G and furthermore and G is isomorphic to the direct sum of all the in gpis

and these are called is a primary Pi group okay of course the the order of GPI it it must be a power of P of Pi because if if there would be any other Prime that divides the order of of GPI then by

Kushi you would have an element of this order and this would contradict the definition of GPI because GPI has only elements whose order is is a power of p i the the order of GPI is some some power of Pi and since we have this isomorphism we actually get that the order must be p i to the ni right it cannot it cannot be otherwise because then I mean because the isomorphism implies uh that

the the two sides have the same order in the the order of the the right hand side is is the product of all orders so this is this is where we left off where are we heading I mean the classification of finite a billion groups would be to decompose g into a sum of of cyclic groups this is kind of the atomic units that we understand completely I mean a simply group is always isomorphic or finite safety group is always isomorphic to integers modulo

n for some n and we know uh all the generators of of integers module to n we know where that every subgroup of integers module n is cyclic and so on this we understand completely and now to to get to uh to uh um a decomposition of g into into a direct sum of of cyclic groups we need to uh to decompose each of the gpis it should be one each of the gpis into a product of

cyclic cyclic groups so the the GPI in for example it could be that you have a integers module five sorry direct sum integers module five but you could also have integers modulo 25 which which we showed less time is not isomorphic to introduce a integers module 5 times itself so this

for example for API equals five a GPI okay but but you see that even if this is a I mean in both of these cases GPI is well it might not be cyclic in itself but it is a a direct sum of secret groups we now we now go for the the main

the main Lemma to do this and this is the following g b uh finite a billion P group it means that the order of G is uh is a power of you know power of P

a and furthermore let a be an element of Maximum order this means that the order of a is is greater or equal to the order of B for any B and G and the claim of dilemma is that there

exists a subgroup okay to the group generator generated by the maximal order element direct sum k okay and the proof of dilemma is uh is rather technical so I recommend that you you follow the notes I will try to convey the proof here as well but but I mean in case you

you miss something you can always ask now but you you could also uh follow the notes after the session it's kind of a bookkeeping so there's not there's not much to understand rather than just to follow um so so consider in the set of subgroups h of of G

the intersection of the group generated by a with age is is Trivial trivial it means that it contains only the the neutral element this set is not empty I mean because you can take for for example H equals the trivial group it is finite because G is fine right

it has a an element k of maximal size so K is a is a subgroup of G with intersection A and K equal to the trivial subgroup

and the Order of K is maximal and we claim it will show that g is in fact the sum of these two groups and when I write this plus what I mean is you simply take all the all the sums so you have an element in in the first

group is a let's say r a in an element in the second group is some k so this is R is is in z and K is in k you simply take all the sums okay so that that's what we want to show towards contradiction

a g is not the sum of these two groups let B in G be a non-zero element okay such that B does not belong to the sum of these two groups now remember G is a p group since G is

a p group the order of all the elements in a pre-group are some powers of P and so there is some integer J e j times B is equal to zero there is a smallest l

is equal to m p PL times B is in the group a plus k so you see if P to the J times B is equal to zero then it it clearly it um it belongs to to a plus k because a plus K contains 0.

so there is a smallest a smallest integer L such that PL times B is in this group whereas I remind you B is not in the group then element C equals P to the L minus 1. B is not in the group

in the sum of these two groups a by minimality by PC which is like a P to the L B is in this in the sum of these two groups so there

exists T in z and K in k PC is equal to a TA plus k since uh let's say the order of a is so is p to the end and since this is is is maximal

then for each X in G p n x is equal to zero right um but then in particular p uh let's let's see and p n minus one times T A Plus k p n minus 1 PC

uh so this this must be equal to zero this is p to the N times C and this this must be equal to zero p n minus 1 t a is equal to p n minus one inverse but then you see the the right hand side is in k and the left hand side is in the group generated by a and we said that K that K is uh I mean

the intersection of A and K is is trivial so p n minus 1 t a must be zero okay now since the the order of a is p to the n p n minus 1 t a is zero

it means that p n must divide p n minus 1T so I can write T equals P times something let's see P times m so using this I can do a I can write PC as well PC is like ta plus k right this this is here

but T is p is PM so I can write it as pm and this means I can write and I can write k minus PMA which is simply p times C minus Ma so now we set D to be equal to C minus m

P times d is equal to p which is equal to K so so PD is an element in K in in capital K a d is not an element in k since if D equals c minus Ma is in k

then C would be equal to D plus m a or rather M A plus d would be in the intersection of A and K which is trivial okay and C C is not a zero element uh well see by by by Design C sorry this

would mean that that C is in the sum of A and K and by Design c c was chosen to be an element not an element in G which is not in a plus K right this is a the assumption that g g is I mean a plus K is not uh is not spending uh all the elements in G now the set age

which is um all the sums of the form X Plus ZD where X is in k and Z is an integer is a subgroup of G contained in age right I mean of course I can take a I can take here the Z to be equal equal to

zero so I get all of the elements in k and K is maximal is maximal such that the the intersection of of the group generated by a with K is is trivial so by maximality okay age intersection the group generated by a must be non-trivial you actually we actually need to show

that that k at K is not is not equal to is not equal to age but this is easy because d is an element in age because it is a zero plus one D but d by Design is not an element well yeah d by Design is not an element in K let me

wait uh an issue here because I think d yeah we said that D I mean we showed that D is not an element in k so so K is not equal to to H completely and this means by maximality of K that age intersection the groups generated by a is is non-zero or

so we're we're approaching the end so let w be an element in the the intersection of H and a which is non-zero then I can write w on one hand equal to s a for some integer s and on the other hand it it is equal to say K1 Plus

Rd this for some r and s in the integers and and K1 in in capital K now I claim the gcd of P and R is 1.

I mean if if was was bigger than one since p is prime I could write r as some hey I mean as as p y for some some integer y um is PD which is k

is of course an element in capital K we have we would have a w which is non-zero it's equal to S A on one hand but it's also equal to K1 Plus Rd but R I can write is p y so pyd and and this this really means that it is a it is both an element

of the group generated by a because it is s a and it is an element in k because it is k1 plus some integer times I mean some integer times another element in K so it is it is in the intersection and and this uh this cannot happen and what this means is that the gcd so I can I can

I can find bizu coefficients for P and R a p u plus RV is equal to 1. then I can write c c is of course 1 times C which is equal to p u plus RV C

and this is equal to u p c V r c now PC is T A Plus k and RC well C is is D plus m a so I get

r D plus m a and and RD is S A minus K1 right I mean this is r plus v

S A minus or S A minus K1 plus RMA and and now the final step I open everything so this is u t a sorry and I open everything and I

I take all the elements with the factor of a I get UT plus vs plus RM UK minus V K1 and what you see here is that c is is an element in

the group generated by a intersection k this is a contradiction we chose C to be to be not in this group so this um and we we conclude that g is simply equal to a plus k so G is equal to the sum of two groups whose intersection is is trivial

uh then we we may Define is simply a map from g into the direct sum by taking an element X into or a I guess it's easier in the the other direction a equal G

I take s a a comma k and I simply send it to SA and you can check that this is uh this is an isomorphism I mean generally speaking if you have two groups

whose sum is the is is the whole group two subgroups whose sum is the whole group and the intersection is trivial it means that the the B Group G is is simply isomorphic to the direction so this this completes this uh this any questions about uh Buddhism

okay so with this I can formulate the uh the first version of the Structure Theory classification Theory and this this is as follows the empty

finite obedient group G is isomorphic of cyclic groups each of uh Prime power and in in symbols

it means the G is isomorphic to a P1 to the S1 Eric charm integers modulu the it's a PL to the SL the P1 up to PL are not necessarily

necessarily unique price and how do you prove it it's it's very easy using dilemma we know that G I mean let's see without loss of generality I simply write G equal to a gp1

up to gpk um where I have a the order of G is a P1 to the N1 up to PK to the NK of course each GPI is a p group or Pi group so by dilemma

is isomorphic to a cyclic group direct sum some some subgroup okay I and and of course the element a has to be of order a power of of p i repeating this and we get

the GPI omorphic to the integers modulo pi to let's say letter one pi to the better say m with of course

the sum better one beta m it must be equal to a to end pipe I mean since the order of GPI is p i to the ni okay and and I do it for all the gpis and I get uh I get the decomposition I want for G

classification theorem or the first version of the the classification theorem means a finite a billion groups group is is uh is the sum of secret groups of uh of Prime power order okay so now as an example what can you do with this uh this classification a the integer

100 can be written as a a product of prime powers in four ways a one way of course is uh you take two times two times five times five then the other way is that you take two

times two times five squared then you can do a 2 squared times five times five and the last way is to do 2 squared times 5 squared and by this by the classification theorem if G

is of size 100 it must be isomorphic to one of the four the four groups that that correspond to this uh this Prime decomposition I mean Prime power this decomposition so I have the first one would would be integers module two some integers module two some integers

some integers module five this is a in the second prime power decomposition would be introduce modulo two introduce modulo 25. and then the third the third one would be integers module four integers modulo module five

and the last one is integers modulo four integers model of 25. okay and that's it the the classification theorem tells us that this is but I mean this is all the possibilities to get a group in a billion group of order 100. so what about the integers module 100 why is it not in the list anybody

so it's it's already covered right it's one of wait our model 100 is not a PI right it is what it's not a it's not a power of a crime yeah but but the classification Theory tells me that a group of of order 100 must be isomorphic to either of these for because this is the all the the Prime power decompositions of of 100

but I know we know that there is a group z module 200 which is in a billion group of order 100. how do you settle this distension I mean I don't see I don't see so that group has an an element that is order 100 yes and none of these two why oh oh no they they do the the last one does because 425 are 1025 are co-prime

exactly okay yeah so there is no mistake in the classification ethereum it's just just another way of presenting it of course the classification is only up to isomorphism so but this is this is the best you can hope for I mean uh saying saying what are the the isomorphism types of all the all groups of our particular order okay so this this is a very powerful uh

statement if you think of it and we will see soon in the the next uh the next part of this session uh uh a pretty strong result coming from the the classification Theory are there any questions about the and what we did here okay so I suggest we we take a 10 minutes break and we come back for a the second version of the classification

theorem and some applications okay thanks see you in 10 minutes uh okay so let me pick up from this uh this last last observation which which we talked about uh less time

this has a a generalization for a more than two factors where the proposition for positive integer with a prime decomposition let's say n is

P1 to the N1 PK to the NK you can write the the group of integers module n is a direct sum of integers modulu P1 to the N1 integers module PK to the NK and the proof is very easy

because once you can do it for two factors you you can just repeat it so a a right let's say m is equal to P2 to the end too then I know that integers modulo and

must be isomorphic modulo P1 to the N1 direct sum integers modulo m of course P1 to the N1 and M are co-prime but then I just I just repeat the I I just repeat the argument by a trivial induction

I get introduce modulo n being isomorphic to this sum so this is easy but but it's a useful effect to record the next thing I want to talk about is a

uh is a nice corollary of the the as a Corollary of the classification theorem we claim finite obedient groups admit

in the converse of a LaGrange theorem and what I mean by the Congress of LaGrange theorem is I mean LaGrange tells you that if you have a subgroup of of G then the order of the subgroup must divide the order of G the converse of LaGrange says that if you have any integer that divides the order of G then you have you actually have a subgroup of

of this order we we talked about koshy theorem because she tells you that uh if if you have a prime that divides the order of G then uh you definitely you you know that you have a subgroup of this of this order this Prime order but in fact using the the classification theorem we can extend it for every divisor of the order of G um the way to go about it is well I mean if you think of what the classification does for you it decomposes g into a sum

so whatever you want to prove you first you first prove on cyclic groups and then if it's true for cyclic groups then uh you you typically can extend it for a for any finite a billion group so let's do the 60 case in the G be a cyclic group generated by by lowercase G he cyclic and suppose that n divides the order of

n times k equal to the order of G and since lowercase G is a generator it means that the order of of lowercase G is n times k and and if the order of of G is n times K I can look at the group generated by G to the power of K this is the set of well e which is a g k to the zero

GK up to GK to the N minus 1. okay when I do GK to the N I get I get the unit element I guess in our annotation we we don't use e we use a zero but this is a subgroup of order n okay so so the the converse of LaGrange

is true for cyclic groups but then you we can use the classification theorem yes Corollary the better name be a finite obedient group and and divides the order of G

then there exists a subgroup h of G whose order is exactly n ope okay so how do you prove this let's say m is is the order of G and I I take the prime decomposition of M

and say this is a P1 to the Alpha One up to PK to the alpha k without loss of generality I can simply write G equal instead of isomorphic to the sum of the the primary primary P groups primary AP subgroups so gp1 some and for each

I less than equal I know that the GPI is a direct sum of 60 groups of of a pi a Pi power order so uh let's say Z p i to the better one integers modulo pi to the beta and I I put an index depending on on I so I call it Li

and of course the sum of all the better eyes let's say beta J equals 1 up to l i it must be equal to I find n divides M which I remind you is a P1 to the alpha one up to PK to the

alpha k we can write and as a P1 to the Gamma One up to PK to the gamma okay where the the gamma eyes are of course they must be a smaller equal than the alpha I and they could possibly be zero so it's bigger equal to zero you can find

Delta one Delta l i the sum of the let's put it like this is equal to gamma I and and I also and of course so the the delta Delta J must be smaller equal to Beta J

and possibly zero okay so all I'm doing I mean this decomposition is not unique of I mean the decomposition of gamma I into a a sum of l i uh positive integers is not unique but I I don't care I I only I only need one such decomposition and once I have it um of course p i to the Delta I or sorry pi to the Delta J

is going to divide to the beta J but p i to the I mean here I have a integers modulo pi to the beta J and this is the secret group and for secret groups we know that E I mean we know the converse of a LaGrange um there exists age let's call it like this age

i j a subgroup of integers modulo p I to the beta J is exactly pi to the Delta J okay but then so I have here I have a h i

this is a subgroup of the first component and I also have h i l i which is a subgroup of the the less and I can take the direct sum of all these subgroups and I

of um well of of GPI right and the order of the subgroup let's call it let's call it hi the order of h i is a the product of all orders and so this is a pi to the Delta 1 plus Delta l i but the Deltas were chosen to

be um such that their sum is gamma I so this is h i it's a subgroup of order p i to the gamma I and remember gamma I mean we we started with an integer n dividing the order of the group G we decomposed it into our a a product of prime powers a pi to the gamma I and now we have found a a subgroup of each of the gpis of order exactly

pi to the gamma I so now we take the prod I mean the direct sum of all these groups H1 h k this is of course a subgroup of G I mean it's a subgroup of a gp1 jpk which which is G by assumption

let's call it age the order of age is of course the product of all orders so I P1 to the Gamma 1 up to PK to the gamma k which is simply the integer n Okay so so this this completes the profile we found a uh a subgroup of G of exactly order n any questions about this uh

this proposition okay so this this shows you the the power of this classification result this is this is a much stronger result than what we had before what we had before is only only cushy theorem we can use

the decompose the the classification theorem the decomposition integers module n is a direct sum of integers modulo P1 to the N1 integers modulo PK to the NK

right and is to prove well to get another um classification Theory and let me do this by example so suppose I have a

as a direct sum of integers modulo two integers module 4 integers module three integers module 9 81 integers modulo 25 integers modulo 125.

we arrange or prime powers as a as the following I put basically it's it's by order but I put it in a table so so 2 2 square and then three three Square and 3 to the 4.

this is 81 and then and then I have 5 Square and 5 Cube okay and now I take I take each of these columns and I put it

I put it in a in one factor so so I can write G the integers module to three integers modulo two integers modulo 3 Square modulo 5 Square integers modulo 2 square

I guess instead of the Prime Powers let me just write the numbers so here I have a nine and 25 and here I have four 125. observe that this guy for example is a direct term

of groups of a of order which is a pairwise co-prime so this guy is isomorphic to uh to the integers of the the product of all these guys the product uh turns out to be 450. and same goes for this guy it will be isomorphic to integers modulo the product the product is a 40 500.

the way I constructed The Columns is say the product of all the numbers in one column divides the product of all the numbers in the in the subsequent column right because you have three dividing Three Square for example and the same is true for the the second dividing in the product of the the Third three divides 450 and 450

divides forty five hundred okay so what we did here is we decomposed g into a product of cyclic groups and the Order of each of the cyclic group is is dividing the the order of the the next one and what I did in this example it can always be done it only depends on I mean the way I can arrange the the table of prime powers this cannot always

be done this is the second version so the classification hearing from finite the billion groups so the G

Onna finite billion whoop to the sum of cyclic groups integers module N1 modulo NK and I divides an i plus 1 for each eye

between 1 and K minus 1. and the proof I live I live for for you as an exercise this is this is really an exercising kind of uh formal manipulation I mean what you need to do is for a general Prime decomposition or Prime power this decomposition you need to figure out the way how to to arrange all the prime powers in a table that will will satisfy two properties

one is that the product of all all numbers in one column divides the product of all uh numbers in the the next column and two that the that all the numbers in one column in a given column are a pairwise core Prime once you did it you you do exactly what you what we have here okay so this is a this is basically what I wanted to to say about the finite obedient groups

of course the main example and we will use it later on an example if e is an elliptic curve which we haven't discussed but I think you you already saw the the definition maybe actually in the first uh the first session I I I gave a definition so if you look at an elliptic curve and you look at the set of solutions I

mean so e is let's say y square equals x cubed plus a x plus b A and B elements of the the prime field and in our notation so far we called it the E I mean zp but this is often denoted as FP and now you can look at the set of solutions e over FP all the

all the elements X comma y in in FP times FP such that a y squared is equal to X cubed plus a x and we will prove that this is an abelian group which of course it it is finite because it's it's the set of all all pairs um I mean of of a finite I mean a finite

Cartesian product so by the the the classification theorem we we have a lot of power we we know exactly what are the the possibilities of a elliptic curve I mean the the billion group structure of the the elliptic curve so this this will be very useful what's coming up next and I think we will leave it into the the next session is uh is finite Fields so the the second ingredient before we we get to elliptic curves is to do classification of of

finite fields so of course there is ffp but there are other other fields other finite fields that are that are not FP and it will again be important for us because um I mean you could look at the the elliptic curve Solutions over over any finite field and the class the classification of of all finite Fields will will help us to to organize this picture okay so this this is what what is coming

up next any questions remarks so far so good I mean I hope you got the feeling of what it means also to be rigorous I mean so far we did the classification of fine at the billion groups with essentially all the details I hope we can do the same for the classification of finite fields it ends later on in this uh in these

sessions I mean we will we will not be 100 rigorous uh so it means we we will introduce uh some black boxes but a quite not not that often so uh so this this is this is what I mean when I say most of what we will do will be regrowth it means with complete proofs if there are no further questions I I

suggest we stop here perfect just uh thank you so much for um your time to