8
$\begingroup$

A strong precalculus course (think AMC, JEE) will teach complex numbers, specifically $n^{\text{th}}$ roots of unity with their properties:

  • They lie equally spaced on the unit circle
  • A power of an $n^{\text{th}}$ root is another $n^{\text{th}}$ root
  • Their sum

What applications do roots of unity have in theoretical or applied math?

$\endgroup$
5
  • 2
    $\begingroup$ I've taken college courses where I need the roots of unity in quantum mechanics as solutions to exponential equations involving spin precession, and they are useful for deriving properties in signal processing like Butterworth filters and (if I recall correctly) properties of the Fourier transform (or similar complex exponentials). $\endgroup$ Commented Apr 28, 2023 at 3:44
  • 1
    $\begingroup$ Your 2nd bullet point hints at the fact that they form a group under multiplication and in particular a finite group which is typically easier to work with than an infinite group. It turns that various kinds of sums of roots of unity are also useful in representing other finite groups [character theory]. You can find finite group like behavior lurking in many places and hence collections of roots of unity-- e.g. with periodic finite state markov chains. Best to revisit this thread after studying more algebra. $\endgroup$ Commented Apr 28, 2023 at 15:53
  • 2
    $\begingroup$ They are widely used for designing discrete signal filters in control theory, every electrical engineer have a few courses using them. Look for example Root locus analysis: z plane. $\endgroup$
    – Joako
    Commented Apr 28, 2023 at 20:42
  • 1
    $\begingroup$ "A traditional precalculus course will teach ... roots of unity." I am not sure that this is correct. I've taught precalculus at five or six American universities and colleges, and none of these institutions has asked that I discuss roots of unity. This usually comes up as a topic of study much later on (e.g. complex analysis, or group theory). On what basis do you make your initial assertion? $\endgroup$
    – Xander Henderson
    Commented Apr 28, 2023 at 21:48
  • $\begingroup$ Let me cover some examples. A traditional precalculus course in India. For example, JEE covers complex numbers in detail, including roots of unity. So does AMC 12. These are strong courses, I agree. $\endgroup$
    – Starlight
    Commented Apr 29, 2023 at 6:04

4 Answers 4

9
$\begingroup$

Roots of unity underlie the Discrete Fourier transform and their very peculiar properties are the key for the Fast Fourier transform one of the most important algorithm in applied math.

enter image description here

[credits]


The connection between Discrete Fourier transform (DFT) and roots of unity is well decribed by the DFT matrix.

Let see what is the idea behind DFT for a discrete signal $x$ (i.e. a vector) with some detail for the case $N=4$ values.

Let consider a $N^{\text{th}}=4^{\text{th}}$ primitive root of unity $\omega_N=\omega_4=e^{\frac{2\pi i}4}$ and the following vectors

$$v_0=\begin{bmatrix}\omega_4^0\\ \omega_4^0\\ \omega_4^0\\ \omega_4^0\end{bmatrix}=\begin{bmatrix}1\\ 1\\ 1\\ 1\end{bmatrix},\; v_1=\begin{bmatrix}\omega_4^0\\ \omega_4^1\\ \omega_4^2\\ \omega_4^3\end{bmatrix}=\begin{bmatrix}1\\ i\\ -1\\ -i\end{bmatrix},\; v_2=\begin{bmatrix}\omega_4^0\\ \omega_4^2\\ \omega_4^4\\ \omega_4^6\end{bmatrix}=\begin{bmatrix}1\\ -1\\ 1\\ -1\end{bmatrix},\; v_3=\begin{bmatrix}\omega_4^0\\ \omega_4^3\\ \omega_4^6\\ \omega_4^9\end{bmatrix}=\begin{bmatrix}1\\ -i\\ -1\\ i\end{bmatrix}$$

It turns out that vectors $v_i$ are an orthogonal basis, since

$$\bar v_i \cdot v_j=N\delta_{ij}=4\delta_{ij}$$

therefore the DFT matrix (also known as $4^{\text{th}}$ order Fourier matrix $\mathbf{F}_{4}$)

$$\mathbf{W}=\mathbf{F}_{4}=\begin{bmatrix}v_0&v_1&v_2&v_3\end{bmatrix}=\begin{bmatrix}1&1&1&1\\ 1&i&-1&-i\\ 1&-1&1&-1\\ 1&-i&-1&i\end{bmatrix}$$

represents a change of basis that is the following transformation and its inverse

$$X= \mathbf{W} x \iff x= \frac1N \mathbf{W}^{-1}X=\frac1N \mathbf{ \overline W} X$$

In this framework, by matrix multiplication, the idea behind FFT is to factorize the DFT matrix in order to reduce the computational effort for the matrix multiplication.

As an example, in the case $N=4$ we obtain

$$\mathbf{F}_{4}= \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & i \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -i \\ \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & -1 \\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$$

and more in general for an order $N=2^m$ by this kind of factorization the computational effort is reduced from $N^2$ to $\frac N 2 \log_2 N$.

$\endgroup$
6
$\begingroup$

Since you mention precalculus, I will give an example that I think is suitable for a good high school student, and then just mention three more advanced topics.

Construction of the regular pentagon: The vertices of the regular pentagon are the 5th roots of unity. The equation $z^5=1$ leads to a very pleasant derivation of the construction of the pentagon with ruler and compass. You'll find a very thorough treatment here, but let me mention the first steps, to give the flavor.

$z^5-1=0$ factors as $(z-1)(1+z+z^2+z^3+z^4)=0$. Let $\omega$ be a primitive 5th root, say $\cos 72^\circ + i\sin 72^\circ$. Then $\omega^4=1/\omega$ and $\omega^3=1/\omega^2$, so we have $$\left(\omega+\frac{1}{\omega}\right)+\left(\omega^2+\frac{1}{\omega^2}\right)+1=0$$ Now, $(\omega+1/\omega)^2=\omega^2+2+1/\omega^2$, so letting $\psi=\omega+1/\omega$, we have $\psi^2+\psi=1$, or $$\psi=\frac{\sqrt{5}-1}{2}$$ the inverse of the golden ratio. Note also that $1/\omega=\bar{\omega}$, so $\psi$ is twice the real part of $\omega$, which has a clear geometric meaning for the pentagon: if we can construct a point with coordinate $\psi/2$ on the real axis, we can find $\omega$ by erecting a perpendicular and seeing where it intersects the unit circle. That's the basis for the pentagon construction.

The young Gauss extended this technique to construct the regular 17-gon, and more generally any regular $p$-gon where $p$ is a Fermat prime.

Gauss sums: Let $p$ be an odd prime, and let $\zeta$ be a primitive $p$-th root of unity. We have the following Lemma:

If $a\equiv 0\pmod{p}$, then $\sum_{t=0}^{p-1}\zeta^{at}=p$. Otherwise it is 0.

Proof: if $p|a$ then $\zeta^a=1$. If $a\not\equiv 0\pmod{p}$ then $\zeta^p\neq 1$ and $\sum_{t=0}^{p-1}\zeta^{at}=(\zeta^{ap}-1)/(\zeta^a-1)=0$.

A Gauss sum is a sum of the form $\sum_{t=0}^{p-1}\chi(t)\zeta^{at}=p$, where $\chi$ is a so-called multiplicative character. (The lemma deals with the most trivial kind of character.) I won't go into details, but Gauss sums play a major role in algebraic number theory. They can be used to give a slick proof of quadratic reciprocity. You can see how Gauss's work with regular polygons could have led him to study these sums.

Ireland and Rosen is a classic source for info about Gauss sums, but there may be easier texts.

Eisenstein integers: You may already know about the Gaussian integers: numbers of the form $a+bi$ with $a,b\in\mathbb{Z}$. These can be used to give an elegant treatment of Pythagorian sums $a^2+b^2$, using the factorization $a^2+b^2=(a+bi)(a-bi)$.

Eisenstein studied numbers of the form $a+b\omega$ where $\omega$ is a primitive cube root of unity and $a,b\in\mathbb{Z}$. They can be used (among other things) to prove the $p=3$ case of Fermat's Last Theorem. The argument begins this way: rewrite $a^3+b^3=c^3$ as $$a^3=c^3-b^3=(c-b)(c-\omega b)(c-\omega^2 b)$$ (The factorization just reflects the fact that if $c^3=b^3$, then $(c/b)^3=1$).

Of course there's much more to the proof, but you can already see how Eisenstein integers can shed much light on the number theory of ordinary integers.

The Cubic Formula: 16th century Italian mathematicians found the formula for the solution of the cubic equation $ax^3+bx^2+cx+d=0$. It's messy, but it has the form $$-\frac{b}{3a}+\sqrt[3]{A+\sqrt{B}}+\sqrt[3]{A-\sqrt{B}}$$ where $A$ and $B$ are rational functions of the coefficients.

Now a cubic generally has three roots. We get these from the formula by realizing that a complex number $C$ has three cube roots: $\sqrt[3]{C}$, $\omega\sqrt[3]{C}$, and $\omega^2\sqrt[3]{C}$. Here $\omega$ is a primitive cube root of unity, and $\sqrt[3]{C}$ is any one of the cube roots. Conventionally, if $C$ is real we let $\sqrt[3]{C}$ be the unique real cube root.

Suppose the coefficients are all real. Excluding cases with repeated roots, the cubic can then have either (1) one real root and two conjugate complex roots, or else (2) three real roots. In case (1), $B$ turns out to be positive, so $\sqrt{B}$ is real, as is $C=A+\sqrt{B}$ and $D=A-\sqrt{B}$. We can evaluate the cubic formula without straying into the complex numbers. This gives the real root. The other two roots are obtained by using $\omega\sqrt[3]{C}+\omega^2\sqrt[3]{D}$ and $\omega^2\sqrt[3]{C}+\omega\sqrt[3]{D}$ in the formula.

Case (2) is called the casus irreducibilis. Here $B$ turns out to be negative, so the formula forces us to take cube roots of complex numbers. We get real results because $\sqrt[3]{C}+\sqrt[3]{D}$ is the sum of a conjugate pair, and likewise for the other two roots. The Italian mathematician Bombelli first noticed this phenomenon.

You can see a three-fold symmetry at work. For the quadratic, we have the two-fold symmetry given by the $\pm$ sign in the quadratic formula. Here the triple $1,\omega,\omega^2$ plays a similar three-fold role.

In fact, it can be shown that any formula for the roots in the casus irreducibilis, using only $n$-th roots and rational operations, will involve an excursion into the complex numbers. Roughly speaking, that's because $\mathbb{R}$ is missing $\omega$ and $\omega^2$, and so can't provide the necessary "three-fold elbow room". Galois theory, which studies this kind of symmetry, enables us to turn these vague ideas into a rigorous proof. The linked Wikipedia article sketches the argument.

$\endgroup$
5
$\begingroup$

The number of solutions of a congruence $f(x_1,x_2,\dots,x_n)\equiv0\bmod p$ is given by $(1/p)\sum_{x_1}\sum_{x_2}\cdots\sum_{x_n}\sum_te^{2\pi itf(x_1,x_2,\dots,x_n)/p}$. Here, all the variables run from zero to $p-1$, and $p$ is prime. Often, it is possible to get a nontrivial estimate for that sum of roots of unity, and thus get a nontrivial estimate for the number of solutions of the congruence.

$\endgroup$
1
$\begingroup$

The roots of unity have an intimate relationship with divisibility problems. I used them to solve the pizza problem. This problem is given we have two people, we cut the pizza in half and have two slices. However if a third person joins us and we cut the pizza into thirds, reusing as many cuts as we can, we will have four slices, two of size $\frac13$ and two of size $\frac16$. Adding a fourth person, then a fifth person and so on, how many slices will we have after $n$ people join us?

I modeled the slices as the $n$-th roots of unity and argued that new slices would correspond to the numbers of roots that don't divide $n$ which are counted by Euler's totient function $\phi(k)$ at the $n$-th step. Then the number of slices is $\sum_{k=2}^n \phi(k)$. So I was able to use the geometry of the roots to model the pizza slices and some number theoretic reasoning so solve the counting problem.

Algebraicly we also have some nice polynomials called the cyclotomic polynomials whose roots are the $n$-th roots of unity. These polynomials have a number of nice properties like being monic, having integer coefficients and being irreducible over $\mathbb{Q}$. This allows us to construct the cyclotomic fields as a quotient of the polynomial ring $\mathbb{Q}[x]$ modulo the chosen cyclotomic polynomial. I found this construction so pretty that I chose it as my username.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .