Euler’s Totient function is a simple tool in number theory. But it has deep connection with Group Theory. Learn more about it.
Tag: group theory
Understand the problem
Let G be a finite group and g ∈ G an element of even order. Then we
can colour the elements of G with two colours in such a way that x and
gx have different colours for each x ∈ G.
can colour the elements of G with two colours in such a way that x and
gx have different colours for each x ∈ G.
Source of the problem
TIFR GS 2018 Part A Problem 24
Topic
Abstract Algebra
Difficulty Level
Hard
Suggested Book
Abstract Algebra, Dummit and Foote
Start with hints
Do you really need a hint? Try it first!
One needs to know the basics of Graph Theory to understand the solution.
- As noted Colouring is a fundamental topic in Graph Theory,so we need to convert the problem into a graph theory problem.
- Consider the elements of the group G as the vertices and consider edges between two elements say x and y if x=gy or \(x=(g^{-1})x\). Call graph G*.
- Check that x—y—z (x is adjacent to y and y is adjacent to z) iff \(y = (g^{-1})x , z = (g^{-1})y = (g^{-2})x\) or \(y = x , z = (g)y = (g^2)x\).We will assume left multiplication by g ( the proof for \(g^{-1}\) is exactly the same.)
- Now observe that we need to answer whether this graph G* is 2-colourable.
- There is an elementary result in graph theory characterizing the 2-colourable graphs.
Theorem 1 : A graph is 2-colourable iff it is bipartite.
Theorem 2: A graph is bipartite iff it has no odd-cycle.
- Thus Theorem 1 and Theorem 2 ⇒ G* is 2 -colourable iff it has no odd cycle.
- Now what does odd cycle mean in here in terms of group.
- A path of odd length means that \(x—gx—(g^2)x—…—(g^k)x\) in odd number of steps i.e. k is odd.
- A cycle of odd length means that \((g^k)x=x ⇒ g^k=1\).
- We are given that g is even ordered so it can only happen if k is even.
- Hence an odd cycle cannot exist and we can colour G* with 2 colours.
The answer is therefore True.
Watch the video
Connected Program at Cheenta
College Mathematics Program
The higher mathematics program caters to advanced college and university students. It is useful for I.S.I. M.Math Entrance, GRE Math Subject Test, TIFR Ph.D. Entrance, I.I.T. JAM. The program is problem driven. We work with candidates who have a deep love for mathematics. This program is also useful for adults continuing who wish to rediscover the world of mathematics.
Similar Problems
Understand the problem
A countable group can have only countably many distinct subgroups.
Source of the problem
TIFR GS 2018 Part A Problem 21
Topic
Group Theory
Difficulty Level
Easy
Suggested Book
Abstract Algebra, Dummit and Foote
Start with hints
Do you really need a hint? Try it first!
This is a really artistic problem.
Pre-Solution Thoughts:
Lemma: A group is finite iff the number of subgroups of a group is finite.(Check!)
The lemma is a way to understand that an infinite group will have infinite number of subgroups.
- We are considering here set of all subsets of a countable group G, which is a subset of the Power Set of G.
- Given G is countable the Power Set of G is uncountable.
- Now we know that \(2^d\), where d is the set of natural numbers denotes the cardinality of the Power Set of G which is an uncountable set as it is bijective to the Real Numbers [Here d is not finite by the way, d is countably infinite].
- So it is kinda intuitive that it may be uncountable.
- First I took the group (Z,+), but we all know that the subgroups of Z are nZ only. This doesn’t solve our purpose.
- So naturally the next choice was the group (Q.+) whose subgroup is (Z,+).
- While understanding the subgroups of (Q.+), the question is solved.
- We need to understand the subgroups of (Q.+).
- Consider any rational number q and the subgroup qZ of (Q.+) generated by q.
- What if we take two rational numbers?
- For simplicity check the subgroup generated by {1/2 , 1/3}.
- Prove that the subgroup generated by {1/2 , 1/3} is (1/2.3)Z.{Observe that co-prime property of 2 and 3 is playing an important role}.
- Now what if we take three mutually coprime natural numbers say a,b,c and see the subgroup generated by { 1/a , 1/b ,1/c}. In fact for simplicity take a,b,c to be primes.
- Observe that it is of the form (1/a.b.c)Z.
- Hence for every finite subset of primes, we generate a distinct subgroup of (Q,+).
- Hence the total number of subgroups contained all the subsets of primes, which has a bijection with the Real Numbers as mentioned above.
- So the answer is False.
Exercise
- Find all the subgroups of (Q,+) with proof.
Watch the video
Connected Program at Cheenta
College Mathematics Program
The higher mathematics program caters to advanced college and university students. It is useful for I.S.I. M.Math Entrance, GRE Math Subject Test, TIFR Ph.D. Entrance, I.I.T. JAM. The program is problem driven. We work with candidates who have a deep love for mathematics. This program is also useful for adults continuing who wish to rediscover the world of mathematics.
Similar Problems
Understand the problem
The multiplicative group \(F^*_7\) is isomorphic to a subgroup of the multiplicative group \(F^*_{31}\).
Source of the problem
TIFR GS 2018 Part A Problem 17
Topic
Abstract Algebra
Difficulty Level
Medium
Suggested Book
Dummit and Foote
Start with hints
Do you really need a hint? Try it first!
We will write them as (Z/7Z)* and (Z/31Z)* respectively instead of the notations used.
- Observe that (Z/7Z)* has order 6 and (Z/31Z)* has order 30.So there is a possibility that (Z/7Z)* is a subgroup of (Z/31Z)* by Lagrange’s Theorem.
- So we need to go into the structure of the groups to solve this problem.Hence we proceed!
- Let us investigate the group (Z/7Z)*.It consists of {1,2,3,4,5,6 mod 7}.Observe that 3 mod 7 generates the group.
- So naturally the next question is that whether (Z/31Z)* rather is there any general result?
- In fact the following theorem is true and describes the cyclicity (Z/nZ)* to some extent.
- Theorem: If p is a prime then (Z/pZ)* is cyclic. (Check!) {Check the bonus question for the complete characterization of cyclicity of (Z/nZ)* done by Gauss.}
- So (Z/7Z)* and (Z/31Z)* are cyclic groups of order 6 and 30 respectively with generators say A and B respectively.
- Now take the element \(B^5\).The following Lemma describes its order.
- Lemma: If g is the generator of the cyclic group of order n. Then \(g^k\_ has order n/gcd(n,k).(Check !)
- So \(B^5\) has order 6 and hence it is isomorphic to (Z/7Z)*.
- Hence the answer is True.
Bonus Problem:
- Theorem: The group (Z/nZ)* is cyclic if and only if n is \(1, 2, 4, p^k or 2.p^k\), where p is an odd prime and k > 0. This was first proved by Gauss. (Wow!)
Solve and Salvage if Possible.
Watch the video
Connected Program at Cheenta
College Mathematics Program
The higher mathematics program caters to advanced college and university students. It is useful for I.S.I. M.Math Entrance, GRE Math Subject Test, TIFR Ph.D. Entrance, I.I.T. JAM. The program is problem driven. We work with candidates who have a deep love for mathematics. This program is also useful for adults continuing who wish to rediscover the world of mathematics.
Similar Problems
Understand the problem
Let G be a finite group with a normal subgroup H such that G/H has
order 7. Then \(G \cong\) H × G/H.
order 7. Then \(G \cong\) H × G/H.
Source of the problem
TIFR GS 2018 Part A Problem 23
Topic
Group Theory
Difficulty Level
Medium
Suggested Book
Dummit and Foote
Start with hints
Do you really need a hint? Try it first!
This is also an interesting question.First of all we need to understand something in general.
If G is a finite group and H Δ G. So Consider the quotient group G/H.
Observe the following!
- Lemma: If G ≈ H x G/H , then G/H is isomorphic to a normal subgroup of G. [Consider the projection homomorphism of G to (H,1) which contains G/H as the kernel.]
- But in general G/H is not even a subgroup of G.
We will illustrate this by giving a simple example.
- Naturally we took the group (Z,+) and we know all the subgroups of Z are nZ ,which are normal subgroups as Z is an abelian group.
- Consider the quotient group Z/nZ.We know that this is not even isomorphic to a subgroup of Z.
- Hence comes our counter-example.
- G=Z, H=7Z. G/H =Z/7Z. But G is not isomorphic to 7Z x Z/7Z as Z/7Z is not isomorphic to a subgroup of Z.
- Hence the answer is False.
- But we will give an example where the given statement is also False.
- Consider the Dihedral group on n elements\(D_n\) as a subgroup of O(2) [The orthogonal group in R^2.] There is a homomorphism (Determinant) from O(2) → {-1,1},whose kernel is SO(2).
- Hence consider the homomorphism from \(D_n\) → {-1,1} formed by the composition of inclusion homomorphism and the determinant homomorphism.
- Observe that the Kernel of the above defined homomorphism is the Rotation Group of angle 2 π /n and the Quotient Group is the Reflection Group around a specific line(?)[Which is essentially Z/2Z.]
- But observe that Dn is not isomorphic to Rotation Group of angle 2 π /n x Z/2Z .[As there is an interaction between rotation and reflection. \(ref.rot.ref=rot^{-1}\) .]
- Prove that the finite subgroups of the group of rigid body motion are only
- Rotation Group of Angle 2 π /n for all n in N.
- Dihedral Group \(D_n\)
Watch the video
Connected Program at Cheenta
College Mathematics Program
The higher mathematics program caters to advanced college and university students. It is useful for I.S.I. M.Math Entrance, GRE Math Subject Test, TIFR Ph.D. Entrance, I.I.T. JAM. The program is problem driven. We work with candidates who have a deep love for mathematics. This program is also useful for adults continuing who wish to rediscover the world of mathematics.
Similar Problems
Understand the problem
The permutation group \(S_{10}\) has an element of order 30.
Source of the problem
TIFR 2018 Part A Problem 23
Topic
Group Theory
Difficulty Level
Easy
Suggested Book
Dummit and Foote
Start with hints
Do you really need a hint? Try it first!
Consider S={1,2,…,10}.\(S_{10}\) be the permutation group on S.
What will you do if one asked for a subgroup of order 3!=6?
- We all would have taken the subgroup of \(S_3\) embedded in \(S_{10}\) right? Call the subgroup H taking identity transformation on {4,5,6,..10} and embedding in {1,2,3}.
What do you do if one asked for a subgroup of order 5?
- We will try to form a cyclic subgroup of order 5. We need to find a generator. Can you see it?
- Keeping {1,2,.,5} same and taking 5 elements {6,7,..,10} and observe the permutation \(i\mapsto i+1\) for i=6,7,8,9 and \(10\mapsto 7\).Take the subgroup generated by this element.Observe this is a cyclic subgroup of order 5.Call this subgroup K.
- Now any idea how to combine this?
- Observe that HK is a set of 30 elements. Does it seem HK is a subgroup?
- Lemma: H and K are two subgroups of G. HK is a subgroup of G iff KH=HK.
- Using the lemma prove that HK is really a subgroup of \(S_{10}\) of order 30.
- Observe that the selection of disjoint elements of H and K is the main reason behind this!
- Hence the answer is True.
Watch the video
Connected Program at Cheenta
College Mathematics Program
The higher mathematics program caters to advanced college and university students. It is useful for I.S.I. M.Math Entrance, GRE Math Subject Test, TIFR Ph.D. Entrance, I.I.T. JAM. The program is problem driven. We work with candidates who have a deep love for mathematics. This program is also useful for adults continuing who wish to rediscover the world of mathematics.
Similar Problems
Understand the problem
Let G, H be finite groups. Then any subgroup of G × H is equal to A × B for some subgroups A<G and B<H
Source of the problem
TATA INSTITUTE OF FUNDAMENTAL RESEARCH -GS-2018 (Mathematics) -Part A -Question 9
Topic
Group Theory
Difficulty Level
Medium
Suggested Book
Abstract Algebra Dummit and Foote
Start with hints
Do you really need a hint? Try it first!
Consider K \(\leq\) G x H . Now if ( a , b ) \(\to\) K then \( a^{-1} , b^{-1}\) \(\to\) K . Also if ( a , b) , ( p,q ) \(\in\) K then ( ap , bq ) , ( pa , qb ) \(\in\) K So , G \(|_k\) = { g \(\in\) G | ( g , h ) \(\in\) K for some h \(\in\) H } is a subgroup of G . Similarly, H \(|_k\) \(\leq\) H .
We have arrived to the conclusion that G\(|_k\) \(\leq\) G & H\(|_k\) \(\leq\) H . Now use this as a fact to guess the answer . Are you sure that G\(|_k\) x H\(|_k\) = K ? I mean that who confirms that K can be within as A X B
Yes this is true that for every g \(\in\) G\(|_K\) \(\exists\) k s.t ( g , h ) \(\in\) K . But G\(|_K\) x H\(|_K\) contain ( g , h ) \(\forall h\) \(\in\) H\(|_K\) . This is certainly having a bigger expectation .
So , here is a nice counter example . Take G = \(\mathbb{Z_2}\) & H = \(\mathbb{Z_4}\) Consider a cyclic subgroup of G x H ; < ( 1 , 1 ) > = { ( 1 , 1 ) , ( 0, 2 ) , ( 1, 3) , (0,0) } Observe that G\(|_k\) = G & H\(|_k\) = H But < ( 1 , 1 ) > \(\neq\) G x H Hence , the answer is false.
Watch the video
Connected Program at Cheenta
College Mathematics Program
The higher mathematics program caters to advanced college and university students. It is useful for I.S.I. M.Math Entrance, GRE Math Subject Test, TIFR Ph.D. Entrance, I.I.T. JAM. The program is problem driven. We work with candidates who have a deep love for mathematics. This program is also useful for adults continuing who wish to rediscover the world of mathematics.
Similar Problems
Categories
Research Track Day 1 Group Theory
Group Theory
Group Theory is the study of groups in mathematics and abstract algebra.
This is an excerpt from Cheenta Research Track training burst. Research Track program has two components.
- Training burst (a sequence of 3/4 sessions to help students acquire necessary background knowledge). This may happen in certain months of the year.
- Weekly / biweekly meetings (to work on a specific problem)
Group
Group is a collection of ‘forces’ that can move points in a space. (This is not definition of a group, just a way to think about it). Understanding the ‘action’ of a group on a ‘space’ helps us to understand the group better.
Groups are usually big (containing infinitely many elements). We want to break it down into smaller blocks. This is similar to factorization of large numbers into prime factors. In fact, it is a common theme all across life: see a big problem? Break it down into small, manageable parts and try to understand the parts.
How do we factorize groups?
One way is to understand group action on a space. We won’t give definitions here. Rather, we will give examples.
First example
Consider the group of integers: {0, 1, -1, 2, -2 .. }
Why is this set a group? It satisfies the four conditions that make a set a group:
- Add any two and you will get a third element of the set (hence set of odd numbers is not a group. )
- There is an identity element (the do-nothing element). In this set it is 0. Add it to any other element a. You will get a back.
- Each number has inverse — the undo operation. For example element 2 has an inverse: -2
- addition is associative
Next consider the space of real line (\( \mathbb{R}\). It is the set of real numbers.
Finally consider the action of G (group) on the S (space). Here is the catch – point. You have to image each group element as a force which can potentially move a point in the space using a certain rule.
There can be many rules. We are interested in some. They should have a couple of desirable properties:
- The do-nothing element of the group (identity element) should literally be the 0-force and not move any element of the space at all.
- If \( g_1, g_2 \) be two forces and P be a point in the space. Suppose applying the force \( g_1 \) to P it moves to Q. Then applying \(g_2\) to Q, it goes to R. But the action is such that you are allowed to do a different thing: combine the forces \(g_2, g_1\) inside the group and then apply the resulting force to P and you will reach R.
If you know the basic definition of group action, even then it helps to think about it in this way.
Group Theory Action
What will the force 2 do to the point 5.3?
It may send 5.3 —> 7.3. It may send 5.3 —> 3.3. We can define other weird rules as well. For example \( 5.3 —> 5.3^2 \). Somehow we have to use the numbers 5.3 and 2 and think about 5.3 as a point on the line and 2 as a force.
If the rule is translate to the right then we get the circle from the line! This was discussed in the very last section of this session (fundamental group).
Do you know that CLOCKS add numbers in a different way than we do? Do you know that ROTATIONS can also behave as numbers and they have their own arithmetic? Well, this post is about how clock adds numbers and rotations behave like numbers. Let’s learn about clock rotation today
Consider the clock on earth.
So, there are 12 numbers {1,2, …, 12 } are written on the clock. But let’s see how clocks add them.
What is 3+ 10 ?
Well, to the clock it is nothing else than 1. Why?
Say, it is 3 am and the clock shows 3 on the clock. Now you add 10 hours to 3 am. You get a 13th hour of the day. But to the clock, it is 1 pm.
So, 3 + 10 = 1.
If you take any other addition, say 9 + 21 = 6 to the clock ( 9 am + 21 hours = 6 pm ).
Now, you can write any other Clocky addition. But you will essentially see that the main idea is :
The clock counts 12 = 0.
Isn’t it easy? 0 comes as an integer just before 1, but on the clock, it is 12 written. So 12 must be equal to 0. Yes, it is that easy.
Cayley’s Table
This is a handsome and sober way to write the arithmetic of a set. It is useful if the set is finite like the numbers of the CLOCK Arithmetic.
Let me show you by an example.
Consider the planet Cheenta. A day on Cheenta consists of 6 earth hours.
So, how will the clock on Cheenta look like?
Let’s us construct the Cayley Table for Cheenta’s Clocky Arithmetic. Check it really works as you wish. Here for Cheenta Clock, 3 = 0.
Exercise: Draw the Cayley Table for the Earth (24 hours a day) and Jupiter (10 hours a day).
Nice, let’s move on to the Rotato part. I mean the arithmetic of Rotation part.
Let’s go through the following image.
Well, let’s measure the symmetry of the figure. But how?
Well, which is more symmetric : The Triskelion or the Square (Imagine).
Well, Square seems more right? But what is the thing that is catching our eyes?
It is the set of all the symmetric positions, that capture the overall symmetry of a figure.
For the Triskelion, observe that there are three symmetric operations that are possible but that doesn’t alter the picture:
- Rotation by 120 degrees. \(r_1\)
- Rotation by 240 degrees. \(r_2\)
- Rotation by 360 degrees. \(r_3\)
For the Square, the symmetries are:
- Rotation by 90 degrees.
- Rotation by 180 degrees.
- Rotation by 270 degrees.
- Rotation by 360 degrees.
- Four Reflections along the Four axes
For, a square there are symmetries, hence the eyes feel that too.
So, what about the arithmetic of these? Let’s consider the Triskelion.
Just like 1 interact (+) 3 to give 4.
We say \(r_1\) interacts with \(r_2\) if \(r_1\) acts on the figure after \(r_2\) i.e ( 240 + 120 = 360 degrees rotation = \(r_3\) ).
Hence, this is the arithmetic of the rotations. To give a sober look to this arithmetic, we draw a Cayley Table for this arithmetic.
Well, check it out.
Exercise: Can you see any similarity of this table with that of anything before?
Challenge Problem: Can you draw the Cayley Table for the Square?
You may explore this link:- https://www.cheenta.com/tag/level-2/
And this video:- https://www.youtube.com/watch?v=UaGsKzR_KVw
Don’t stop investigating.
All the best.
Hope, you enjoyed. 🙂
Passion for Mathematics.
Categories
Group Theory open seminar
Abstract
A great way to study groups is to study group automorphisms. They are structure-preserving maps from a group to itself.
Some subgroups are ‘invariant’ under all group automorphisms. They are known as characteristic subgroups.
One example of the characteristic subgroup is the commutator subgroup.
In this seminar, we will explore these ideas.
Who can attend this seminar:?
Anyone interested in beautiful, deep mathematics
Do I need to know group theory?
No. We will start from scratch.
Is there an entry fee
No. It is part of the Cheenta Open Slate program. Anyone can attend this for free.
Is this online?
Yes. You need to be online from
Make sure that you have the latest chrome or firefox browser.
Here is the link to the skype group. Class link will be posted there.
https://join.skype.com/jWv6y9miiGER
When is this seminar?
April 20, Saturday, 6 PM I.S.T.