Involutions

We are getting closer to Rabin-Miller primarility test and RSA. Our final prerequisites are involutions and avoiding elements, basic parts of elementary group theory.

Sources:

  • Drapal, part 2.12
  • Wiki post on involutions in general.

Theory:

Let G be a group, a,b\in G two of its elements. We say that a avoids b in G if a^i\neq b and b^i\neq a for every i\in\mathbb{Z}. Note that this condition is symmetric, i.e. a avoids b if and only if b avoids a. Realize that if G is cyclic with a generator g, then, by definition of cyclic group, there is no  b\in G such that g avoids b.

If g\in G is of order 2, then such g is said to be an involution. So, g\in G is an involution, if g^2=e and g\neq e. As an example, consider G=\mathbb{Z}_2(+). Then there is only one involution, namely a=1 (note that the order of 0 is 1, not 2).

Combining these two previous definitions, we can realize when it is the case that an element a avoids an involution u. Well, it happens if and only if a^i\neq e for every integer i (this condition is unchanged) and a\neq e (this condtitions is greatly reduced).

Properties:

  • Let G=A \times B, where A,B are finite groups, (e,f)\in G. If the number of a\in A that avoids e in G is at least \alpha\cdot|A| for some \alpha\in\mathbb{R}, then the number of elements of G that avoids (e,f) is at least \alpha\cdot|G|=\alpha\cdot|A|\cdot|B|.
  • Let G=G_1\times\dots\times G_k. The order of a=(a_1,...,a_k)\in G is the lcm\Big( ord(a_1),...,ord(a_k)\Big).
  • Let p be a prime number, 1\leq k_1,...,k_r\in\mathbb{N}. Then an element a=(a_1,...,a_r)\in\mathbb{Z}_{p^{k_1}}\times\dots\times\mathbb{Z}_{p^{k_r}} is of order p^s, where s=max\Big(k_1-v_p(a_1),...,k_r-v_p(r)\Big).
  • Suppose we have some naturals k_1\geq\dots\geq k_r\geq 1, where r\geq 2. An element a=(2^{k_1-1},...,2^{k_r-1}) is an involution in G=\mathbb{Z}_{2^{k_1}}\times\dots\times\mathbb{Z}_{2^{k_r}}. The number of elements g\in G that avoid a is at least \frac{|G|}{2}.

Examples:

Example 1:

What are the elements of G=Z_6 that avoid an element a=4?

Solution:

Use the definition of avoiding and proceed case-by-case:

  • 0: 3\cdot 4\equiv 0 – not avoiding;
  • 1: 4\cdot 1\equiv 4 – not avoiding;
  • 2: 2\cdot 2\equiv 4 – not avoiding;
  • 3: Multiples of 3 modulo 6 are 0 and 3, so no 4. Multiples of 4 modulo 6 are 0, 4, and 2, so no 3. It follows that 3 avoids 4 in G.
  • 4: 1\cdot 4\equiv 4 – not avoiding;
  • 5: 2\cdot 5\equiv 4 – not avoiding.

Therefore, 3 is the only element that avoids 4 in G.

Example 2:

Determine all involutions in G=\mathbb{Z}_4(+)?

Solution:

We can proceed case-by-case and for every element we can determine its order

  • 0 is of order 1;
  • 1 is of order 4 (what makes G a cyclic group);
  • 2 is of order 2 and hence, an involution;
  • 3 is of order 4 (another generator).

Therefore, the only involution in G is the element 2.

Example 3:

What are all the involutions in G=\mathbb{Z}_3(+)?

Solution:

Well, G is of order 3, and the mighty Lagrange theorem says that the order of any element must divide the order of the whole group. However, 2 (order of a potential involution) does not divide 3, so there is no involution in G.

Problems:

Problem 1:

What are the elements of G=Z_8 that avoid an element a=4?

Problem 2:

Find all involutions in \mathbb{Z}_{12}.

Problem 3:

Find all involutions in \mathbb{Z}_2\times\mathbb{Z}_2.

Leave a Reply

Your email address will not be published. Required fields are marked *