Problem 21 - A Computational Introduction to Number Theory and Algebra

Question

Suppose \(2_{R} \in R^{*}\) and \(\omega \in R\) is a primitive \(2^{n}\) th root of unity. (a) Let \(k\) be any integer, and consider gcd \(\left(k, 2^{n}\right),\) which must be of the form \(2^{m}\) for some \(m=0, \ldots, n .\) Show that \(\omega^{k}\) is a primitive \(2^{n-m}\) th root of unity. (b) Show that if \(n \geq 1,\) then \(\omega-1_{R} \in R^{*}\) (c) Show that \(\omega^{k}-1_{R} \in R^{*}\) for all integers \(k \not \equiv 0\left(\bmod 2^{n}\right)\). (d) Show that for every integer \(k,\) we have $$ \sum_{i=0}^{2^{n}-1} \omega^{k i}=\left\\{\begin{array}{ll} 2_{R}^{n} & \text { if } k \equiv 0\left(\bmod 2^{n}\right) \\ 0_{R} & \text { if } k \neq 0\left(\bmod 2^{n}\right) \end{array}\right. $$ (e) Let \(M_{2}\) be the 2 -multiplication map on \(R^{\times 2^{n}},\) which is a bijective, \(R\) -linear map. Show that $$ \mathcal{E}_{n, \omega} \circ \mathcal{E}_{n, \omega^{-1}}=\boldsymbol{M}_{2}^{n}=\mathcal{E}_{n, \omega^{-1}} \circ \mathcal{E}_{n, \omega} $$ and conclude that \(\mathcal{E}_{n, \omega}\) is bijective, with \(M_{2}^{-n} \circ \mathcal{E}_{n, \omega^{-1}}\) being its inverse. Hint: write down the matrices representing the maps \(\mathcal{E}_{n, \omega}\) and \(\mathcal{E}_{n, \omega^{-1}}\).

Step-by-Step Solution

Answer

a. To show that \(\omega^k\) is a primitive \(2^{n-m}\)th root of unity, we first showed that \((\omega^k)^{2^{n-m}} = 1_R\). Next, we proved that \((\omega^k)^j \neq 1_R\) for any integer \(1 \leq j < 2^{n-m}\). b. We demonstrated that \(\omega - 1_R \in R^*\) by showing that the sum \(\left(\omega^{2^{n-1}} + 1_R\right)\left(\omega - 1_R\right)\) is invertible in \(R\). c. For \(k \not \equiv 0 \pmod{2^n}\), we showed that \(\omega^k - 1_R \in R^*\) by proving that \(2^m | j\) is a contradiction, given the conditions in part (a). d. We found that the sum of \(\omega^{ki}\) is equal to \(2_R^n\) when \(k\) is congruent to 0 modulo \(2^n\), and equal to 0 when it's not. e. We showed that the composition of maps \(\mathcal{E}_{n, \omega}\) and \(\mathcal{E}_{n, \omega^{-1}}\) is equal to the multiplication map \(M_2^n\), proving that \(\mathcal{E}_{n, \omega}\) is bijective and its inverse is given by \(M_2^{-n} \circ \mathcal{E}_{n, \omega^{-1}}\).

Step 1: a. Primitive Roots of Unity

To show that \(\omega^k\) is a primitive \(2^{n-m}\)th root of unity, we need to show that \((\omega^k)^{2^{n-m}} = 1_R\) and for any integer \(1 \leq j < 2^{n-m}\), \((\omega^k)^j \neq 1_R\). Given that \(\omega^{2^n} = 1_R\), we have: \((\omega^k)^{2^{n-m}} = (\omega^{2^n})^s\) for some integer \(s\), such that \(sk = 2^m s = 2^n\), which implies \(\omega^k\) is a \(2^{n-m}\)th root of unity. Now we need to show that \((\omega^k)^j \neq 1_R\) for any integer \(1 \leq j < 2^{n-m}\). Suppose there exists a \(j\) such that \((\omega^k)^j = 1_R\), then: \((\omega^{2^n})^t = 1_R\) for some integer \(t\), such that \(j k = 2^m j = 2^n t\). This means that \(2^{m} | j\), a contradiction since \(j < 2^{n-m}\). Therefore, \(\omega^k\) is a primitive \(2^{n-m}\)th root of unity.

Step 2: b. \(\omega - 1_R \in R^*\)

To prove that \(\omega - 1_R \in R^*\), we need to show that the sum \(\left(\omega^{2^{n-1}} + 1_R\right)\left(\omega - 1_R\right)\) is invertible in \(R\). Now, calculate the product: \(\left(\omega^{2^{n-1}} + 1_R\right)\left(\omega - 1_R\right) = \omega^{2^{n-1}+1} - \omega + \omega^{2^{n-1}} - 1_R\) Using the fact that \(\omega^{2^n} = 1_R\), we have: \(\omega^{2^{n-1}+1} = \omega^{2^n}\omega^{-1} = \omega^{-1} \in R^*\) Therefore, \(\omega - 1_R \in R^*\).

Step 3: c. \(\omega^k - 1_R \in R^*\) for \(k \not \equiv 0 \pmod{2^n}\)

Using gcd\((k, 2^n) = 2^m\) and part (a), we have: \(\omega^{2^m} - 1_R = \left(\omega^k\right)^{2^{n-m}} - 1_R\) Now, consider the sum: \(\left(\omega^{2^m} + 1_R\right)\left(\omega^{2^m} - 1_R\right) = \omega^{2^{m+1}} - 1_R\) As \(\omega^{2^n} = 1_R\), we know that \((\omega^{2^m})^{2^{n-m}} = 1_R\): \(\omega^{2^{m+1}} - 1_R = \omega^{2^{n-m}} - 1_R \in R^*\) Hence, \(\omega^k - 1_R \in R^*\) for integers \(k \not \equiv 0 \pmod{2^n}\).

Step 4: d. Sum of \(\omega^{ki}\)

For \(k \equiv 0 \pmod{2^n}\), we have: \(\sum_{i=0}^{2^n - 1} \omega^{ki} = \sum_{i=0}^{2^n - 1} \omega^{0 i} = \sum_{i=0}^{2^n - 1} 1_R = 2_R^n\) For \(k \neq 0 \pmod{2^n}\), consider the sum: \(\sum_{i=0}^{2^n - 1} \omega^{ki} = \frac{\omega^{k(2^n - 1)} - 1_R}{\omega^k - 1_R}\) As \(\omega^{2^n} = 1_R\), the numerator becomes: \(\omega^{k(2^n - 1)} - 1_R = 1_R - 1_R = 0_R\) Thus, \(\sum_{i=0}^{2^n - 1} \omega^{ki} = 0_R\) for \(k \neq 0 \pmod{2^n}\).

Step 5: e. Bijectiveness of \(\mathcal{E}_{n, \omega}\)

Based on the definition of the given maps, we have the matrices representing \(\mathcal{E}_{n, \omega}\) and \(\mathcal{E}_{n, \omega^{-1}}\) as \(A\) and \(B\), respectively: \(A = \begin{bmatrix} 1_R & 1_R & 1_R & \cdots & 1_R \\ 1_R & \omega & \omega^2 & \cdots & \omega^{2^{n}-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1_R & \omega^{2^{n-1}} & \omega^{2^{n-2}} & \cdots & \omega^{2^{n-1}(2^{n}-1)} \end{bmatrix}, B = \begin{bmatrix} 1_R & 1_R & 1_R & \cdots & 1_R \\ 1_R & \omega^{-1} & \omega^{-2} & \cdots & \omega^{-2^{n}+1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1_R & \omega^{-2^{n-1}} & \omega^{-2^{n-2}} & \cdots & \omega^{-2^{n-1}(2^{n}-1)} \end{bmatrix}\) The product of these matrices will be: \(AB = \begin{bmatrix} 2_R^n & 0_R & 0_R & \cdots & 0_R \\ 0_R & 2_R^n & 0_R & \cdots & 0_R \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0_R & 0_R & 0_R & \cdots & 2_R^n \end{bmatrix} = M_2^n\) And similarly, we can obtain \(BA = M_2^n\). Since the composition of both maps \(\mathcal{E}_{n, \omega}\) and \(\mathcal{E}_{n, \omega^{-1}}\) is equal to the multiplication map \(M_2^n\), we have that \(\mathcal{E}_{n, \omega}\) is bijective, and \(M_2^{-n} \circ \mathcal{E}_{n, \omega^{-1}}\) is its inverse.

Key Concepts

Roots of Unity

The concept of "Roots of Unity" concerns special numbers that, when raised to certain powers, give a result of one. Specifically, the primitive roots of unity are the base building blocks of these numbers in a cyclic group.
In mathematics, a primitive \(n^{th}\) root of unity, denoted as \( \omega \), is a complex number that satisfies two main conditions:

• \( \omega^n = 1 \): Raising \( \omega \) to the power of \( n \) gives one.
• \( \omega^k eq 1 \) for any integer \( 1 \leq k < n \): The powers of \( \omega \) should cycle through all distinct roots before reaching one again.

For example, if you consider the 4th roots of unity, they are solutions to the equation \( x^4 = 1 \). Among these, the primitive 4th roots will have unique properties of not becoming one when raised to powers less than four. Understanding these roots is crucial in fields like signal processing and quantum physics, where they help in analyzing periodic functions.

Bijective Maps

In mathematics, and particularly in function analysis, bijective maps, or bijections, are functions that establish a perfect "one-to-one" correspondence between two sets. This means each element from one set has a unique partner in another set, and vice versa.

• A bijective map is both injective (one-to-one function) and surjective (onto function).
• Such maps are essential in understanding the structure and behavior of mathematical systems.
• They help prove the equivalence and isomorphism of algebraic structures.

When dealing with bijections in the context of roots of unity, they allow us to map complex structures such as polynomial roots or cyclic groups both ways without any loss of information. In algebra, studying bijective mappings can elucidate deeper properties of these systems, revealing fundamental symmetries and forming the basis of transformations like Fourier transforms.

GCD and Modular Arithmetic

GCD (Greatest Common Divisor) and modular arithmetic are pivotal concepts in number theory and have wide-ranging applications.

• The GCD of two integers is the largest integer that can exactly divide both numbers without leaving a remainder. It is key in simplifying fractions and understanding divisibility properties.
• Modular arithmetic, on the other hand, is a system of arithmetic for integers, where numbers "wrap around" after reaching a certain value known as the modulus.
• It is often described as "clock arithmetic" due to its cyclical nature, fundamentally impacting cryptography and computer science algorithms.

Involving both concepts together, as in the case of roots of unity, provides a framework for finding multiplicative inverses and understanding residue classes. For instance, the formula \( \omega^k - 1_R \in R^* \) can be evaluated using modular constraints based on \( k \) and \( 2^n \), where \( \omega \) is a root of unity. Mastery of these allows students to tackle complex problems in both pure and applied mathematics.