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

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

##### Topic

##### Difficulty Level

##### Suggested Book

## Start with hints

- 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.

- 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.

## Watch the video

## Connected Program at Cheenta

#### College Mathematics Program

## Similar Problems

# Understand the problem

##### Source of the problem

##### Topic

##### Difficulty Level

##### Suggested Book

# Start with hints

**Pre-Solution Thoughts:**

**Lemma:**A group is finite iff the number of subgroups of a group is finite.(Check!)

- 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

##### Topic

##### Difficulty Level

##### Suggested Book

# Start with hints

- 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.

- 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!)

# 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

order 7. Then \(G \cong\) H × G/H.

##### Source of the problem

##### Topic

##### Difficulty Level

##### Suggested Book

# Start with hints

- 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.

- 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

##### Source of the problem

##### Topic

##### Difficulty Level

##### Suggested Book

# Start with hints

- 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}.

- 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

# Similar Problems

# Understand the problem

##### Source of the problem

##### Topic

##### Difficulty Level

##### Suggested Book

# Start with hints

# Watch the video

# Connected Program at Cheenta

#### College Mathematics Program

# Similar Problems

## 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

**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**

*ROTATIONS*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.

: Draw the Cayley Table for the Earth (24 hours a day) and Jupiter (10 hours a day).Exercise

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.

## 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.