PSE Lectures - Ep 3 - Groups (2/4)

Transcript

foreign welcome back um uh I think today we're going to step up a notch uh in terms of the difficulty level I want to remind you that it's it's important uh both for you and for me that you ask questions uh you can ask different types of questions like on notations on some argument you didn't understand

or some some questions about the the the the the the the general context and so on so I I would like to remind you to try to ask questions this will turn the the lecture into uh well more into the direction of a dialogue which is I think is is better so less time we Define the notion of a group

so a group a g well group is a set G e plus a binary operation multiplication um such that for any X Y and G um well any x y and z in G

we have associativity that is x y z is equal to X y z for any EX in G or maybe there exists uh a specified Element e which we call the neutral element and such that for any X in G e x equals to x e

equals to X and for any X in G and there exists an element x minus one such that x times x minus 1 is equal to e but also on the other side x minus 1 times x is also equal to E now a from the axioms it actually follow

that the the unit element or the neutral Element e is unique the neutral element is unique a what do I mean by that it means that um if there would be another candidate for a unit element for so if e Prime in G is such

that e Prime X equals X and also x times e Prime is also equal to X then e Prime must be equal to E well how do you see it I mean e Prime e it must be equal to e because um because if e Prime is a is a neutral

but it also must be equal to e Prime because because e is a neutral element so so you get this this small this small fact you can you cannot have two neutral elements I mean similarly the inverse of x is is also unique and what I mean by that if well if for any X

in G they would exist a let's call it x minus 1 Prime x times x minus 1 Prime is equal to E and also from the other side then x minus 1 Prime would be equal to x minus 1.

this I live I live is an exercise and the third remark is that a it's enough it's enough if we so here in the the inverse Axiom we required a a that the inverse would be a right a right inverse and also a left inverse but it is in fact enough to require that um you have a for any X you have let's

say a left inverse let me let me just say it briefly you can find the details in the notes uh it is enough and to ask for a a left or right inverse instead

of a two-sided so this you can you can try to do the exercise to do this as an exercise it is important to to do this small exercises because you get comfortable with the axioms and of course you could since you have these remarks tell you that you could have formulated the axioms uh slightly different

and you would get the same notion but but the way the way it is written here above is the standard uh the standard way to define it okay now what we also had last time is we saw we took the the the unit circle within the complex numbers and I remind you um the complex numbers I represent it is it is all the Z such that Z is

equal to R cosinos data Plus in the interval 0 up to 2 pi and so this is this is the complex numbers right this uh this is the what is called the polar representation so if you have

a complex number here here we denote the real axis and the imaginary axis right so e z z is is also X Plus i y a then this is the radius and of course this is a this is a y and and this is X and here you have Theta which is the the angle that Z creates with the the positive direction of the the x-axis or or the real axis

so under this this representation I can I can look at the the circle as simply the collection of all complex numbers such that the radius this we call um we denote the radius by by absolute value so the circle is simply the complex numbers whose absolute value is one and of course we

we have a natural operation on the on the circle um because if you take a z NZ Prime you can simply add the two angles right and you get a something like this this would be a z multiplied by Z Prime so here multiplied really means that I I simply add the two angles let's consider the equation

x to the N minus 1 equal to 0. and I Define mu n of C is the solution set over to this uh to this polynomial x x n minus 1. so it's all the all the zeros of this uh polynomial and this is called a nth roots of a Unity

so for example if you take I you know that I square is -1 I to the four is going to be 1 and therefore I I to the well I is going to be an element in mu for of C now how can we so so we I mean we fix an n and we would like to to understand the

the entire collection a mu n of C well you can see that since uh I mean this is a a complex number in in mu n of C since it it need to satisfy that Z Z to the N is equal to one it follows that the absolute value of Z is 1. because when I multiply complex numbers I multiply the radius um so the radius must be one so it means

that it is on the on the unit circle and moreover well I can heuristically guess what are the possible solutions to this equation by the the geometry of of uh of the unit circle that is well of course this is one right one is always going to be a solution to the to the equation x to the N minus one equal to zero so this is always a

um in in u n but then I mean if I take an angle which is 2 pi Over N then if this is z let's say Z is equal to a cosines 2 pi over n plus I sinus then when I when I do Z to the n it's it's simply doing a a addition of

the of the the angle of z n times so I get cosines a 2 pi plus I sinus which is a by a properties of of sine and cosine it's simply a zero plus sorry one M 0i which is 1. okay so so here this is always a solution to to uh to this uh to this equation this is an nth through of unity

and in fact I can also do a a similar Thing by taking here um is it Prime for example to be m a times a 2 divided by n maybe I should say this angle I could also take a m 2 pi times 2 divided by n that's also when when I raise Z Prime to

the nth power I also get a multiple of 2 pi a so I I will also get the unit element one so also Z Prime to the n is equal to one and and similarly so I what what is happening here I can divide let's say n equals to 3 I can divide the circle into a three equal

parts so let's say um yeah m so so I have

my uh so so I want this this would be of course 120 I guess it would be something like this my my drawing skills are uh not not that good as you can see but uh but the important thing is that you divide the circle into a a three equal parts um and then so so uh you have Z1 is is simply equal to one

Z2 is whatever this is um I mean it corresponds to to Theta 120 degrees and Z3 is going to to correspond to a a 240 degrees okay and so indeed this if you if you write it in in Radiance and then this would be a 2 pi times two divided sorry 2 pi

divided by 3 and this would be a times 2 divided by 3. okay now this this kind of a a object I mean it is a group as well so note mu n is a group under the the operation uh

under a multiplication multiplication of complex numbers and a the size of mu n is simply n there are you cannot have more than a n solutions to a polynomial of degree of degree n because you can write I mean so in fact whenever whenever a zero is a solution to is a solution to the polynomial uh e x

to the N minus one for example then you can write x to the N minus 1 equals a x minus zero a times some polynomial is such that g um the degree of the degree of GDX is strictly smaller than n if I know that there can there could be at most n solutions to this equation and I heuristically I found all the N solution I mean I found and solutions it means I I described it completely and so I have the the number of elements in the

the set of n roots of unity is uh is n and the the the operation uh of multiplying complex numbers is a is giving me a group because I mean you can look at it in in this description of course if you you multiply a a two two things in this in this uh a triangle you simply add the two angles so either you add zero to 120 or you had you had the 120 to 240 you get a you get still

again the an element in this uh or you get again an nth roots of unity any questions come on guys I'm sure I'm sure uh something here might have not been completely clear hi yeah yeah one I have one question uh so I kind of missed out on how you got G1 equals C1 uh on the N equals to three

diagram could you repeat on that Z1 equals to one yeah yeah okay so I mean I I this is a a I mean you could you could say this is a a 2 pi times so I'm looking for the solutions of the equation x to the N minus one equals to zero so one one is an element in the the complex numbers right I mean you can write one plus zero I yeah okay and of course when you do one to the N minus one you get zero

right okay okay so a again the enumeration here I called it Z1 sometimes you call you start enumerating by a by zero because Z1 corresponds to a angle the angle of of Z1 with the the the axis a real is zero so in in polar coordinates at the angle of Z1 this corresponds to to Theta equal to zero okay got it yeah thanks okay and in fact

Z1 will always be so so one is in mu n of C for any n right so this is not a I mean it's not a special property of the N equals three for any n you raise 1 to the N the nth power you get one and this is the the unit element in in mu n so this is the the is a is the the unit a other questions

all right so what what is happening here we have this circle which is a group by a um by multiplication of complex numbers and within this uh within this uh within this group I have another subset let's say n is equal to three and this subset is uh is also a group under the same operation

and it also has the same neutral element right because here one is also the the neutral element of the of the group S1 so this cause for a for a new definition a GB a group a subset age in G

is called a subgroup if with we need a we need a few conditions first we need the unit element or the neutral element will be in the in the candidate for uh for a subgroup two we need that the a the subgroup is closed under the the binary operation of of G that is for any

X and Y in age x times y this same operation as in G the or the only one that we are given is also an element in H and three for any X in H the inverse of X is also in H who can tell me so I claimed that a mu n sorry mu 3 in this example is a is a subgroup

should say we denote age smaller or equal to G this this is our notation for example and I I claim what we we discussed just a minute ago is that we have a a a subgroup of S1 for example a we enumerate this as a Z1 Z2

Z3 who can tell me what is the inverse of um of Z2 what is what is Z2 to the minus 1. if that's three okay so let's check let's let's say I do Z2 times Z3 then Z2 is like it's 120 degrees is a 240 degrees

so indeed when I do Z2 times Z3 I get a 360 Degrees which is which is zero so I mean zero degrees so this corresponds to one so we can say that Z2 minus 1 is Z3 and let's let's talk let's talk more about subgroups I mean this uh this entrance of unity is a nice example that we will

revisit because well okay uh we'll leave it for later but for for subgroups we have many examples actually this this is a very uh a very common object you you run into um so the first example I take a G2 bit integers with the neutral element being zero and

the operation being plus and I take age to be what I denote as NZ and Z is is the set of all numbers of integers of the form n times a or a is an integer n equals 2 is is it's all the even numbers then age is is indeed a subgroup of

of G what if I take g g the same as above so G is equal to Z a age is equal to all the odd numbers is this a group a a subgroup I mean when you add odd numbers you get an even

number exactly so so it is not it is not closed under the binary operation so this this Axiom is not satisfied but there is also another Axiom that is not satisfied what is it there is no neutral element exactly because the odd numbers do not contain 0 and 0 is the neutral element so also this Axiom is not satisfied um okay

so so this is a this is a a another example uh maybe slightly more interesting you take let's say Z mod 10 which I remind you is all the numbers up to nine I mean 0 up to nine with a a a a module 10 Edition and now I look I look at the set 0 and 5. this is a set of two elements is contained in z110 I call this H this is age and this

is gene and I claim that H is a subgroup well what do I need to check the unit so the first Axiom is the unit element or the neutral element indeed 0 is is in H then I need to I need to check that the this this subset is closed under the binary operation well if I do zero plus five I get five if I do a

five plus five I get I get zero so I mean I'm always closed under the binary operation of a modulo 10. the inverse the inverse of any element is is also in the group because a the inverse of 5 is is simplified itself okay but a note that if I take the the subset zero four for example

this is not a this is not a subgroup it is a subset but it's not a subgroup because I add a i for example I add 4 to itself I get 8 which is not an element in this a in this in the set zero form another example you take the complex numbers but you remove

and you take the the operation is is multiplication and the the unit element is one I claim that S1 is a subgroup of this and I mean what is called this is this is denoted is the is C and cross above the multiplicative group of the complex and it follows that we have like a a

sequence of subgroups so we have mu n of C is a subgroup of S1 which in turn is a subgroup of C star and of course well I mean you can check it but a subgroup of a subgroup is going to be a subgroup as well I mean so so mu n of C is in fact a subgroup also of the the multiplicative group of the complex and a a exercise

you take two groups a a g and H and you look at the Cartesian product now here inside the Cartesian product you can you can look at a a subset of the form G times the neutral element of H this is this is simply a notation to say it's the set of all pairs of the form X comma e h

where X is in H and sorry X is in G a g is going to I mean sorry j times e h is going to be a subgroup of G times h okay and similarly EG Times age is going to be a subgroup of G times h

now of course you can you can really think of EG times H is a it is like a copy of age I mean we didn't do really anything and this this is like a copy of a copy okay we will get back to this uh uh to this this issue more uh more precisely later let G be a group

and age a subgroup age cassette some X in G is a is something I denote as x times h this is the set of all products x h such that X sorry such that

age using h so you see I I am using this binary operation of the the group notation I mean now I I mean I use the binary operation to have a an element on one side and an asset or in fact here it's it's a subgroup on the other side um but I think it's intuitive enough that you can you can get used to it and in any way that's that's the conventional way to write it

so this this is a a the cassette defined by an element in g a a note for example e times H is simply equal to H because what is e times h i mean it's all the it's all the products of the form e times h ages in age which is simply all the age such as H is an H which is H so that's the first thing second

if um I have Alpha in xh say Alpha is equal to X time H for aging h then this this this lowercase H is unique that is if if also Alpha is equal to x times H Prime well I have x h Prime equals to x h but I can multiply this equation by x

minus 1 on the left and I get I get that H is equal to H Prime here's a question let's say a let's say age is is finite it could be like this a group of n roots of unity um what is the size of xh

anybody I mean let's say age has a six elements what is the size of xh is the same it's the same right because every element exactly has a unique representation I mean all I did here is I shifted age by by the element X but this shift is like

um I mean it's like all the X ages each of them I mean every two different I mean if age is different than H Prime then you get X age is different than xh Prime so it's it's exactly the size of age um example I take g equals to the integers and age is equal to ends n and Z which is like integers that

are multiples of a of n right this is and a such that a using Z and remember the the operation in Z in the integers is uh is plus right so I will write the corsets so for for e x in G I will write the corsets a x g sorry xh I will write X Plus H right because plus is my binary operation

so X Plus H is going to be the set of all expressions of the form X Plus H such that H is in H okay so I have for example um the coset 1 plus and z but the coset 1 plus NZ is in fact equal to the corset n plus one

plus n z this when I do I mean if you do for example you open this upbeat this is all the N plus one n a such that a is in z but if a is allowed to be in Z then I can then I can unite these two uh these two components so I get that it's the same as like saying 1 plus if you want it's one plus I mean n times

a plus one a is in Z but this is really the same as taking a simply one plus okay x and z these two these two things are equal and I can I can further uh say that this is like it's also equal to a 2N plus one thus NZ and so on it it is also going to be equal as as I said um to minus n plus one

plus NZ okay so in other words you can check that X Plus n z is equal to Y plus NZ if and only if X is equal to Y modulus n right I mean

another is another example you can take zero plus NZ this is going to be equal well to a a n plus NZ and also to 2N Plus NZ and so on now consider the set all

a cosets of NZ where X is in z this this is a set of sets right we we talked about it in the the first lecture a a remember that when we describe a set we the order doesn't matter the order of the elements doesn't matter and we also remove repetitions and here is is a a key example where a you need to remove repetitions after removing

um after removing repetitions and we can write that the set of all cassettes one way to describe it it's not the only way I can write a well I have zero plus NZ then I have 1 plus NZ and and so on up to n minus 1 and then n plus NZ is already equal to

to 0 plus NZ so I don't write it but of course I could have written it differently like this is also equal for example I replace the first element by a 2N and then I I leave the rest of the elements the same 1 plus and z of 2 N minus 1.

that's NZ okay but this this purple way to write the set of cassettes is is kind of canonical right uh we uh we have all the elements a zero up to n minus one this is kind of a familiar um the patterns for us any questions about a what we did okay so I suggest we take a 10 minutes

break see uh See you back here in 10 past 11. okay yeah okay okay so I saw uh somebody asked in the the chat uh to give give again an overview of uh where we are going um first I want to say a it's hard for me to uh to look at the

chat a while while I'm talking so please please speak up but this one I saw a a I can I can say that the plan um of next steps when we have quite a lot to to cover before we can get to elliptic curves uh with the proper background uh

um so we will need to talk about more about groups and specifically uh cushy theorem and the isomorphism theorem and and cyclic groups then we will need to talk about a fields uh here of course you know the the the main example this a prime field but in fact

there are a also a fields of the form FP to the n in the to prove I mean to basically to classify all the all finite fields uh this requires um quite a lot of um of work I mean you need to to look at polynomials over fields and uh well you have a a theory of classifying all the all the finite fields then we will need to talk about the

algebraic closure the algebraic closure of a field uh we only do the the finite field the version so it's a it's a bit easier but still it requires some effort and after we we did all that we can uh we can get into elliptic curves so I know that mitso a wrote A A in his notification that we might be able to

get to the material needed for pairing but this is a I think this is too ambitious I mean in in the in in a few months I think we can get to elliptic curves uh I'm not sure if it's going to be a two months or three months but something something like that but even after we we get to elliptic curves there is still then there is a lot to uh to cover until we get to to pairings so this this is because

we are doing everything with the almost full proofs uh you could have done you could do it differently uh by uh introducing I mean using things as a as Black Box but uh that's that's a different approach than uh than what we're taking we yeah so we is somebody asked if we can skip to polynomial Rings right I I think I think

it's not it's not wise unless I mean all of you tell me that it's a this material is a you're completely fluent with and I I really kind of doubt it because uh if you didn't study a a like proper a course in in field Theory uh then at least this material uh with the algebraic closure especially you you will not you will not be completely fluent or familiar with and it is essential to uh to things we do with elliptic curves

so that's but I'm I'm open to uh to get your to get get your input uh maybe later later after the talk we have the Discord chat for that so before the break we talked about this example of a a corset and you can see that if I take the union of all cosets

X is in z I get a I get Z itself right I mean every element is a is an element in some corset I mean this this cassettes a simply cover everything um and and this this is not a coincidence this is in fact a a general phenomena is so

proposition for a group a subgroup age of cassette xh a m form uh partition

a i e the union of all corsets is G itself and two if you take two cassettes that are not equal I mean of course two cosets could be equal as we we saw in this uh uh previous example but if they are not they must be what is called disjoint it means that the intersection

is the empty set okay so the picture is like uh well I have maybe X One h 2H x3h maybe x3h is equal to x a 4-H that's also okay but but they don't have any intersection if they're not I mean two cassettes do not have any element in the intersection

unless they are equal and the union of all cassettes is a is the group G why the union of all X age is is G well um if x is in G X in particular X is equal to

um x times e and e is in age so X must be an element in xh so since this is true for any element x a one is proven now suppose you have two cosets and you have an element there exists age

and H Prime in Age Alpha on one hand is equal to xh and on the other hand is equal to xh Prime sorry 2. y h Prime any question okay so so if I have a I have an element that is in the intersection of x h and y h

then it can be expressed in two ways a first is x times H and and second is y times H but remember that a I can take inverses in in uh in a subgroup age a I can I can multiply this equation by the inverse of age on the right and I get that X is a y h Prime H minus 1.

X is in YH because it can be expressed as a y times some some element in H a and and also Y is going to be equal to X age H Prime minus one y belongs to xh because this because this element is an element in Edge

well so a but if yes so my question is so I think you just said that the union of all cosets is equal to the group right yes but the code a code set alone it does not build a group or a subgroup yeah a corset a corset alone is in fact it's not it's not it's um it's not even a subgroup yeah a typically typically but the exception is a the cassette e h is equal to age which is which is a subgroup

but the rest of them they they are not they are not subgroups because well you will see a I I I will give an example after the proof okay okay so we have we have X belongs to y h but if x belongs to y h let's call it star and this I call double star I mean from Star I can deduce that xh entirely is contained in in YH because

I mean I take an element x h then it is of the form y times a a I mean X is of the form X Y times H Prime and this times H then e it is but now I use associativity this is like y which is an element in age so this this belongs to YH and and double star similarly

would would imply that the whole cassette y age is included in xh both of these things imply that xh is equal to YH and this this is a method that we will repeat I mean to show it's like to show the two two numbers are equal you show that the first is is smaller equal than the the second and the second is smaller equal to the first and and the the analog in sets is uh to uh to show the the inclusion of both sides okay so what what we deduced so of

course if if the two two cassettes are not equal I mean if they if they have even one then they must be equal so it means that if if they are not equal they don't have any common element this this finish the proofs now a Lemma

look for age a subgroup of G is above a now I want a criteria so when two cosets are equal we saw that in this example two the two cassettes for example one plus NZ was equal to n plus one but what is the general criteria this

this example of integers modulo n is kind of a uh may be too simplistic we don't know so the criteria is the following Lemma two cassettes are equal if and only if x minus 1 Y is an element in H and of course the roles of X and Y here are symmetrics so you could equally well write y minus 1 is an element image so this if and only if this blue a

symbol it means that I need to prove both directions I mean I need to prove that if the two cosets are equal then x minus 1 Y is in age and a conversely if x minus 1 Y is in h then the two cosets are equal so let us start so suppose a xh is equal to YH since

Y is in in y h which is which is equal to xh so there exists some age in age Y is equal to xh but then a I can multiply all this equation by x minus 1 and I get that x minus 1 Y is H which is an element in H

so this this is the this is the easy Direction and conversely x minus 1 Y is in age we write x minus 1 Y is equal to some h then I multiply all this equation by a by a by X and I get Y is equal to XA to xh

I.E y is an element in xh and as we saw it it really means that the whole y h is included in xh because an element in in y h would be so y h and y is some xh so let's say this is YH Prime this is going to be x h Prime and and this is in in English but also so if I have this

I can write let's say x minus 1 is equal to a y minus 1. ah you know what there is a simpler a simpler way to do it now I want to show that X is an element in YH but X is equal

y minus 1 y y minus 1 . a sorry X right this is a I want I have this is is the same as like saying X is equal a y minus 1 h so I write it as

in fact we don't by what we saw there is a simpler argument so uh so been what we saw I mean why of course is is is an element in y h uh and Y is also an element in X Age and and we saw that two cosets are either equal or disjoint so since in this case they have a common element they they must be equal

okay I'm sorry for the the unnecessary complication suppose age subgroup of G X and Y in G are such a

x x age is different than YH Define a function let's call it f from xh to YH if I I need to tell you what it does on I mean every element Alpha here it can be uniquely written as some x

times H that this H is is unique so I can Define the function on this expression xh and what I do I send it to y h very very intuitive and then and first you can see that that f is if it's rejective because if you give me some element uh you give me some element better in y h then this beta is of the form

a y h and and so f of x h is going to be is going to be um Y8 if you write Alpha equals to xh then F of alpha is equal to Beta um but but also AF is injective um if you have two elements Alpha and

Alpha Prime so say Alpha is equal to xh and Alpha Prime is equal to x h Prime then of course a age must be so e if I have two different elements Alpha and Alpha Prime then age must be different than H Prime right because if they would be equal I could I could multiply by x minus one and get that H would be then equal to H why age must be different

I have now f f of x h which I know by definition is YH and I have f of x h Prime this is like maybe we we turn another step so I have I have F of alpha this is by definition of alpha this is f of x h and by definition of f this is f sorry this is YH

and on the other hand I have F of alpha which by definition of alpha Prime is x f of x h Prime and by definition of f x y h Prime um and why age cannot be equal to um to YH Prime a because uh if they were equal I could multiply by y y minus 1 on on the left H H equal to H Prime and that's that's a contradiction I mean we we assumed

that Alpha is different than Alpha Prime and this means that that H is different than H Prime so this is all to say that f is injective as well and what we get is a bijective map from xh to YH H is finite all the cosets are of equal size the the

number of elements in xh is going to be the same as the number of elements in YH for any X and Y but if this is true for any X and Y this is also true for a a x being the unit element so it's it's like it's going to be equal to the number of elements in E times H which is simply the number of elements in age so in fact we can revisit the the picture if this is G and so if G is finite then I get like a

a partition of G let's say this is x1h this is x2h x3h maybe x3h is equal to x4h and so on but the the size of the slices is exactly the same okay and there is an immediate corollary for this this is called LaGrange theorem G is a finite

age is a subgroup of G so of course age then must be finite the number of elements in H must divide the number of elements in G and a the proof is it's basically what we saw I mean we can write G as the union of all cosets here in the union there is repetition somehow because it could be right that xh is equal to to y h this we saw that

this this happens if uh even on if y minus 1 x is in H a but regardless of whether there is repetition or not this these sets in in purple are of equal size so I get that the number of elements in G is some a some C times the number of elements in age where C is the a number of a distinct

cassettes any questions we we did quite a quite a bit by now so this would be a good opportunity with a number of elements which are prime that those groups don't have a

subgroup exactly apart from a a I mean you always have the trivial a so if new is is a group then first of all G in itself is always a subgroup and also the uh the set with only the unit element is also a sample these are called a trivial subgroups so what you say is is exactly right I mean if a if G is of prime order and

this is the reason that we use a groups of prime order in in cryptography then there is no non-trivial subgroup a4g and so this this has a this has implication in in the the uh the The cryptographic Primitives that that we that we construct other questions I guess maybe we let's call it the

definition and suppose a g G and H is above they don't need to be a not necessarily finite for for two elements X Y in G

I have the corset X age and I have the coset YH and I can do a binary operation by saying that the multiplication of these two cassettes is defined to be x y and I can also do inverse I take this coset xh and I you want to you want to know what is the inverse I

tell you what is the inverse is like x minus 1 H it's another cassette Okay so a location we call a you have a subgroup h of G um and the set of all cassettes I'm not sure if I if I said it before

but I denote it is a this G divided by h this is like the set of all X age X in G a I can talk I can tell you a bit more about the intuition for this notation but for now just think of it is like in in in the example we had of the a the corset age is equal to to n and Z then the set of all cassettes

was like a zero plus NZ up to n minus 1. and z and this this really remember this this really resembles the uh the mod n i mean the the integers modulo n so it is like I took a I took integers and if I divide it by the the subgroup of all integers that are multiple of N I got something that is uh similar to a integers modular hand so this uh this is maybe a heuristic justification for this

notation the the main the main issue of this this is called it is called the quotient a of G by h this definition is is telling you something uh in fact I would like to say so this this definition is like defining a binary operation on the uh

on the set Gmod h and uh of course we we wanted this binary operation will be will be a group it is a it looks like this definitely but there is an essential condition that we need to to add in order for this to uh to happen and this is the proposition G is a billion that is X Y is equal to y x for any x y

star induces a a group structure on Gmod h and now how do you prove it well first and this this is a repeated the uh a repeated principle in a definitely in

questions but we we will run into it in a I mean later on as well um I gave you a definition and maybe you're you're not that experienced but um nobody nobody told you that what I what I defined is indeed well defined uh why because I took um I took a the representatives X and Y and I multiplied them but it could be so need to check a the binary operation on

Gmod age is well defined a why I mean you I mean you gave me xh and y h and I told you okay I I can multiply I do xh sorry X Y times h but a suppose you now tell me okay but instead of X age I give you X prime age

an X prime age is equal to xh but X is not equal to X Prime I give you instead of Y Prime y h Prime y Prime h and these two cosets y h and y Prime H are equal but Y and Y y Prime are not necessarily equal then I get a cassette like this and I need to I need to show that these two cosets are

I mean this is what it means to to be well defined I mean it means that it does not depend on the the representative of the the cassette that I chose is equal to X Prime h x minus one X Prime belongs to age and if I know that a y h

is equal to Y Prime h then I know that y minus 1 y Prime also belongs to H and now to show x y h to X Prime y Prime h it is it is enough equivalent enough to

show X Y minus one times x Prime is an element in H x x x y minus 1 this is in any group is going to be equal to a y minus 1 x x minus 1.

what we need to show is that a y minus 1 x minus 1 X Prime and what I have is the two the two blue boxes that I started with I mean I started with a two different representations of the the corset and and they gave me the the blue boxes um but now I use a I use the fact that the G is a billion if G is a billion then I can write it as um I can just uh

order all these symbols in in whatever order I choose so I choose x minus 1 x times a y minus one the the first blue box tells me that this is an element in age the second blue box tells me that this is an element in age so all all in all the entire the entire product must be an element in age because age is a subgroup

and it is closed under uh under products so okay so this is this is all to say that the the the definition is well defined um but now the rest of the axioms of a group they follow a they follow immediately so um associativity um unitary or even charity and existence of inverse

um these axioms in in Gmod age from these properties in in G because for example multiplied by YH and then you you multiply the result by some z h

well if I mean now that we have a well-defined binary operation we do this is xh sorry x y h multiplied by z h which is X y z h but since a the binary operation on on the elements X Y and Z is associative it is also equal to x times y y z H and if you if you open it from the the other direction what you get is like the

this is this is simply its age multiplied by in a white age zh so so you get you get associativity of a multiplication of cassettes a unitary unitarity is is in the same the same way I mean of course uh xh times e h by definition is x times e h so it is it is simply X age and the uh the existence of inverse well x x h

times x minus 1 H is going to be equal to x x minus 1 H which is simply e h okay so this this finishes the proof we get uh under the condition that g is a billion the a this collection Gmod h is is a group and a let me give like a quick example I mean we have a running example remember a you take G to be equal to the integers

that's that's in a billion group so we are okay and H is multiples of n g mode h we saw that as a set it is it is like zero plus NZ um up to n minus 1 but now the the the the the less proposition tells tells us that this this thing has a group structure and the group structure is a a you take a coset zero sorry X

and you want to add it to a cassette y well then you just do X Plus y in the in the the ambient group page and you add it to the cassette NZ but we saw that um X Plus Y and Z is the same as X Plus mod n a plus NZ

right two cosets in this running example two cosets are equal if and only if their representatives are equal up to a a modulo n so in fact what is happening here is that we have it's like a funny a a funny way we um we have instead of the the numbers 0 up to n minus one with a a a a module an operation we have this a funny cassettes but eventually the operation is the same so we could identify

um Gmod h is going to be identified with simply the integers modulu and because it it's like a it has the the same number of of elements and the the multiplication table if you will is a is the same but if they are not equal right I mean they are different sets so we will need to make uh make sense of this this equality in a in uh in a precise manner but for now you can you can at least maybe grasp it intuitively that this is another another angle to a to look at

the the group of integers modulus okay this will be the end of the material for today but of course now is a is a good time for a for questions hello are you sure that you don't have with a billion property necessary um there is uh there is another uh so it

it is a it is sufficient but not necessary right so in mathematics we I mean this is how we call I mean a condition is sufficient if you know if it is it gives you what what you want but sufficient and necessary is like if and only if uh so the condition that g is a billion is a sufficient condition but it's not necessary uh in fact even when G is not obedient then you have a con if if age a satisfy a condition called a normal then a the same the same proposition

holds for our purposes we will uh only I mean almost only uh do quotient groups of of a billion groups so I think it's a good compromise to to skip a this complication of the uh non-obedient case and and just do do it like this okay thanks all right so I hope you didn't get to uh

too bored I think we covered quite a lot today eventually it may look funny because we come back it like it looks like we we come back in circles to this integers module n but a if you really think of it we are taking different angles of the same uh the same object and different angles they they add up something to our understanding so uh so instead of like moving in circles you can think of we move in in kind of a spiral it means we we do progress because we add another angle of uh I mean another point of view for the object we care about

all right so uh see you next week I hope thank you thank you thanks thank you