Roots of unity¶
Level: 201 · for anyone who has read multiplication rotates and remembers that cos 30° = √3/2
One line: Multiplying by a unit point turns the plane by its angle, so multiplying by it n times turns n times as far, and a point at 1/n of a turn is back at (1, 0) after n steps: the equation zⁿ = 1 has exactly n solutions, spaced evenly around the circle, and the program finds them with no angle computed and no square root rounded.
Where the picture pays off¶
Multiplication rotates showed that multiplying by a point of length 1 turns the plane by that point's angle and changes no lengths. It never computed an angle, and this page will not either. It asks the one question that "angles add" makes easy: what happens when a unit point is multiplied by itself, over and over?
It walks around the unit circle in equal steps. Each multiplication turns by the same angle A, so after n of them the point sits at angle nA. In cosines and sines,
which is de Moivre's formula, and it is "angles add" applied n − 1 times. Then the question splits. Most unit points walk forever and never land where they started. A few come back, exactly, after n steps: those are the n-th roots of unity, the solutions of zⁿ = 1, and there are exactly n of them.
What the program prints¶
Verified output of roots_of_unity.py — regenerated by tools/run_examples.py, never hand-typed.
1. THE POWERS OF A UNIT POINT STAY ON THE CIRCLE
z = (3/5, 4/5), the 3-4-5 point, sits at some angle A that is never
computed. Multiply it by itself:
z^0 = (1, 0) |z^0|^2 = 1
z^1 = (3/5, 4/5) |z^1|^2 = 1
z^2 = (-7/25, 24/25) |z^2|^2 = 1
z^3 = (-117/125, 44/125) |z^3|^2 = 1
z^4 = (-527/625, -336/625) |z^4|^2 = 1
z^5 = (-237/3125, -3116/3125) |z^5|^2 = 1
z^6 = (11753/15625, -10296/15625) |z^6|^2 = 1
Angles add, so z^n sits at angle nA: de Moivre's formula,
(cos A, sin A)^n = (cos nA, sin nA). For n = 2 and 3 the right-hand
side has a formula in cos A = 3/5 and sin A = 4/5, checked exactly:
(2 cos^2 A - 1, 2 sin A cos A) = (-7/25, 24/25) = z^2: True
(4 cos^3 A - 3 cos A, 3 sin A - 4 sin^3 A) = (-117/125, 44/125) = z^3: True
Clear the denominators and every power is a Pythagorean triple:
z^2: 7^2 + 24^2 = 625 = 25^2
z^3: 117^2 + 44^2 = 15625 = 125^2
z^4: 527^2 + 336^2 = 390625 = 625^2
2. THIS POINT NEVER COMES BACK
In lowest terms the denominators of z^n are exactly 5^n:
n = 1 5^1 = 5
n = 6 5^6 = 15625
n = 12 5^12 = 244140625
n = 24 5^24 = 59604644775390625
Both coordinates have denominator 5^n for every n from 1 to 24: True.
A fraction with denominator 5^n is not 1, so z^n is never (1, 0). The
3-4-5 point turns by A at every step and never completes a whole
number of turns: A is not 1/12 of a turn, or 5/17, or any fraction.
3. CARRYING sqrt(3) EXACTLY
The point at 1/12 of a turn is (cos 30, sin 30) = (sqrt(3)/2, 1/2),
and sqrt(3) is not a fraction. So the program keeps numbers of the
form a + b sqrt(3), a and b fractions, and multiplies them by
(a + b sqrt(3)) . (c + d sqrt(3)) = (ac + 3bd) + (ad + bc) sqrt(3)
sqrt(3) . sqrt(3) = 3
(1 + sqrt(3)) . (1 - sqrt(3)) = -2
(1/2 + sqrt(3)/2)^2 = 1 + sqrt(3)/2
(sqrt(3)/2)^2 + (1/2)^2 = 1 so (sqrt(3)/2, 1/2) is a unit point
Nothing is rounded. The pair rule mul() is the same four lines as in
the previous lessons: it only asks that coordinates add, subtract and
multiply, and these do.
4. THE TWELVE MARKS OF A CLOCK FACE
h = (sqrt(3)/2, 1/2), one twelfth of a turn, multiplied by itself:
k = 0 h^0 = (1, 0)
k = 1 h^1 = (sqrt(3)/2, 1/2)
k = 2 h^2 = (1/2, sqrt(3)/2)
k = 3 h^3 = (0, 1)
k = 4 h^4 = (-1/2, sqrt(3)/2)
k = 5 h^5 = (-sqrt(3)/2, 1/2)
k = 6 h^6 = (-1, 0)
k = 7 h^7 = (-sqrt(3)/2, -1/2)
k = 8 h^8 = (-1/2, -sqrt(3)/2)
k = 9 h^9 = (0, -1)
k = 10 h^10 = (1/2, -sqrt(3)/2)
k = 11 h^11 = (sqrt(3)/2, -1/2)
k = 12 h^12 = (1, 0) back at the start, exactly
Every |h^k|^2 is 1: True. Twelve steps of a twelfth of
a turn is one turn, so h^12 = 1: h is a 12th root of unity. The four
compass points are among the marks, at k = 0, 3, 6 and 9.
5. z^n = 1 HAS EXACTLY n SOLUTIONS
Each mark raised to the powers 2, 3, 4, 6 and 12. A 1 means the result
is (1, 0); a dot means it is not.
k mark z^2 z^3 z^4 z^6 z^12 first return
0 (1, 0) 1 1 1 1 1 1
1 (sqrt(3)/2, 1/2) . . . . 1 12
2 (1/2, sqrt(3)/2) . . . 1 1 6
3 (0, 1) . . 1 . 1 4
4 (-1/2, sqrt(3)/2) . 1 . 1 1 3
5 (-sqrt(3)/2, 1/2) . . . . 1 12
6 (-1, 0) 1 . 1 1 1 2
7 (-sqrt(3)/2, -1/2) . . . . 1 12
8 (-1/2, -sqrt(3)/2) . 1 . 1 1 3
9 (0, -1) . . 1 . 1 4
10 (1/2, -sqrt(3)/2) . . . 1 1 6
11 (sqrt(3)/2, -1/2) . . . . 1 12
solutions of z^n = 1: 2 3 4 6 12
The solutions of z^n = 1 are the marks k that are multiples of 12/n:
n of them, evenly spaced. A degree-n equation has at most n solutions
in a field, so these are all of them. The marks that need all twelve
steps, k = 1, 5, 7 and 11, are the primitive 12th roots of unity, and
they are exactly the k with no factor in common with 12.
6. THE CUBE ROOTS OF UNITY, AND WHERE sqrt(-3) LIVES
Mark 4 is w = (-1/2, sqrt(3)/2). Its powers:
w^1 = (-1/2, sqrt(3)/2)
w^2 = (-1/2, -sqrt(3)/2) which is mark 8: True
w^3 = (1, 0)
z^3 - 1 = (z - 1)(z^2 + z + 1), so a cube root of 1 other than 1 must
solve z^2 + z + 1 = 0:
w^2 + w + 1 = (0, 0)
The quadratic formula says z = (-1 +/- sqrt(-3)) / 2. In pairs, sqrt(-3)
is the point (0, sqrt(3)):
(0, sqrt(3)) . (0, sqrt(3)) = (-3, 0)
((-1, 0) + (0, sqrt(3))) . (1/2, 0) = (-1/2, sqrt(3)/2) which is w: True
And the roots of unity always add up to nothing:
the 3 cube roots, marks 0, 4, 8: sum = (0, 0)
the 4 fourth roots, marks 0, 3, 6, 9: sum = (0, 0)
all 12 marks: sum = (0, 0)
7. THE SAME THING IN FLOATS
Build the same points from math.sqrt(3) / 2, the nearest double to
sqrt(3)/2, and multiply with the same mul():
w = (-0.5, 0.8660254037844386)
w . w . w = (0.9999999999999998, 1.1102230246251565e-16)
off (1, 0) by (-2.220446049250313e-16, 1.1102230246251565e-16)
h = (0.8660254037844386, 0.5)
h^12 = (0.9999999999999993, 3.3306690738754696e-16)
off (1, 0) by (-6.661338147750939e-16, 3.3306690738754696e-16)
Neither is (1, 0). The rule is exact; the coordinates were rounded
once, at the start, and every multiplication carried the error along.
Exactly, w^3 = (1, 0) and h^12 = (1, 0), as sections 4 and 6 found.
De Moivre's formula, exactly¶
Section 1 takes the 3-4-5 point z = (3/5, 4/5) and multiplies it by itself. Its angle A is whatever angle a 3-4-5 triangle has, and it is never computed. Every power has squared length 1, so the powers stay on the circle, and every coordinate is an exact fraction: z² = (−7/25, 24/25), z³ = (−117/125, 44/125).
That z² sits at angle 2A can be checked without knowing A, because the double-angle formulas say what (cos 2A, sin 2A) is in terms of cos A and sin A:
Those are the coordinates of z². The triple-angle formulas, 4cos³A − 3cos A and 3 sin A − 4 sin³A, give (−117/125, 44/125), which is z³. The pair rule produced both by arithmetic. It does not know what an angle is, and it did not need to; the formulas are what "angles add" looks like written out.
Clear the denominators and every power is a Pythagorean triple: 7² + 24² = 25², 117² + 44² = 125², 527² + 336² = 625². A unit point with fractional coordinates squares to another one, and the two-squares identity of lesson 1 is the reason.
Most points never come back¶
Section 2 looks at those denominators. In lowest terms, the denominator of zⁿ is exactly 5ⁿ, for every n up to 24. A fraction with denominator 5ⁿ is not 1, so no power of the 3-4-5 point is (1, 0). Turning by A over and over never adds up to a whole number of turns, which says that A is not a fraction of a turn: not 1/12 of one, not 5/17 of one, not any p/q.
(The program checks 24 powers. That the pattern holds for all of them is a theorem: 5 never divides both numerators at once, which follows from how 5 factors among the integers a + bi. The page states it and does not prove it.)
So this is the typical unit point: it has fractional coordinates and its angle is an irrational number of turns. The points that do return are the exception, and they are what this page is about.
Carrying √3 exactly¶
The unit point at 1/4 of a turn is (0, 1), and the rotation lesson watched it come back after four steps. The one at 1/12 of a turn, 30°, is (cos 30°, sin 30°) = (√3/2, 1/2), and √3 is not a fraction. A float would round it, and then, as section 7 shows, twelve multiplications later the point is near (1, 0) and not at it. The word this page cares about is exactly, so the program does not round.
It keeps numbers of the form a + b√3 with a and b fractions, and multiplies them by
because √3 · √3 = 3. The product has the same form, so the arithmetic never leaves the set. Section 3 checks that (√3)² = 3, that (1 + √3)(1 − √3) = −2, and that (√3/2)² + (1/2)² = 1, so (√3/2, 1/2) is a unit point.
The pair rule from lesson 1 does not care what its coordinates are, so long as they can be added, subtracted and multiplied. The program's mul is the same four lines as before, and it handles fractions, fractions with √3 in them, and, in the last section, floats.
(That rule for a + b√3 is itself a rule on pairs, (a, b) · (c, d) = (ac + 3bd, ad + bc), and it is the complex rule with the −1 replaced by +3. The roadmap has the siblings of the complex numbers waiting for a page; this is one of them, met early because it was needed.)
The clock face¶
Section 4 raises h = (√3/2, 1/2) to every power from 0 to 12. It visits (√3/2, 1/2), (1/2, √3/2), (0, 1), (−1/2, √3/2), and so on around the circle to (√3/2, −1/2), and then h¹² = (1, 0): an equality of fractions, not a float near 1. Twelve steps of a twelfth of a turn is one turn.
The twelve points are the marks of a clock face, numbered counterclockwise from (1, 0). Among them are the four compass points the rotation lesson reached with quarter turns, at marks 0, 3, 6 and 9, and the eight points with coordinates ±1/2 and ±√3/2, which are the cosines and sines of 30° and 60° and their reflections.
zⁿ = 1 has exactly n solutions¶
An n-th root of unity is a solution of zⁿ = 1: a point that is back at (1, 0) after n multiplications by itself. Section 5 raises each of the twelve marks to the powers 2, 3, 4, 6 and 12 and records which results are (1, 0). Down the columns, z² = 1 has 2 solutions, z³ = 1 has 3, z⁴ = 1 has 4, z⁶ = 1 has 6, z¹² = 1 has 12. The solutions of zⁿ = 1 are the marks k that are multiples of 12/n, every fourth mark for the cube roots, every third for the fourth roots, so they are n points spaced evenly around the circle.
The table finds n solutions among the twelve marks. That they are all the solutions, anywhere in the plane, takes one more fact: a polynomial equation of degree n has at most n solutions in a field, and lesson 1 showed that the pairs are a field. So the marks are the only ones.
The last column is the first power at which each mark returns. Marks 1, 5, 7 and 11 need all twelve steps. They are the primitive twelfth roots of unity, and the powers of any one of them visit all twelve marks. Marks 2 and 10 return after six steps, so they are sixth roots of unity, and their powers visit only the even marks. In general mark k returns after 12 / gcd(k, 12) steps, and the primitive ones are the k with no factor in common with 12.
The cube roots and the quadratic formula¶
Mark 4 is w = (−1/2, √3/2), and section 6 cubes it: w³ = (1, 0). The polynomial z³ − 1 factors as (z − 1)(z² + z + 1), so a cube root of unity other than 1 must solve z² + z + 1 = 0, and the program checks that w² + w + 1 = (0, 0), exactly.
The quadratic formula solves z² + z + 1 = 0 as well, and gives (−1 ± √−3)/2. School algebra stops there, at the square root of a negative number. In pairs, √−3 is the point (0, √3): the program squares it and gets (−3, 0), then computes (−1 + √−3)/2 as a pair and gets (−1/2, √3/2), which is w. The formula was right all along; it was waiting for somewhere to put √−3, and the place is the vertical axis.
The section ends with a fact that holds for every n > 1: the n-th roots of unity add up to (0, 0). The three cube roots do, the four fourth roots do, all twelve marks do. Geometrically they are balanced around the origin. Algebraically the argument is two lines: if S is the sum and w is a primitive root, multiplying every root by w only shuffles the roots among themselves, so wS = S, so (w − 1)S = 0, and since w ≠ 1 and two nonzero pairs never multiply to (0, 0) (multiplication can be undone), S = 0.
The same thing in floats¶
Section 7 builds the same two points with math.sqrt(3) / 2, which is not √3/2 but the nearest double to it, about 10⁻¹⁶ away. Then w · w · w is not (1, 0), and h¹² is further off still. The pair rule was as exact as before; the coordinates were not, and the error in the starting point rode through every multiplication. Chapter 1 is about what happens after that. This page avoided the problem by never rounding: the symbol √3 with the rule √3 · √3 = 3 is exact in a way no float can be.
The eighth roots of unity need √2 the same way. The fifth need √5 with another square root nested inside it, and cos(360°/n) is a fraction at all only for n = 1, 2, 3, 4 and 6, which is Niven's theorem. Twelve is the largest n whose roots of unity can be written with fractions and a single square root, which is why the page stopped at the clock.
Run it yourself¶
From the root of your clone of this repository:
Po polsku, w skrócie¶
Mnożenie przez punkt okręgu jednostkowego obraca płaszczyznę o kąt tego punktu, więc mnożenie przez niego n razy obraca n razy dalej: to wzór de Moivre'a. Większość punktów okręgu nigdy nie wraca do (1, 0). Punkt (3/5, 4/5) z trójkąta 3-4-5 ma w n-tej potędze mianownik 5ⁿ, więc nigdy nie da 1: jego kąt nie jest żadnym ułamkiem pełnego obrotu. Wracają tylko punkty leżące co 1/n obrotu. Pierwiastki n-tego stopnia z jedynki to rozwiązania zⁿ = 1; jest ich dokładnie n, rozłożonych równo na okręgu, i sumują się do zera.
Program znajduje dwanaście znaków tarczy zegara dokładnie, bez zaokrągleń, niosąc √3 jako symbol z regułą √3 · √3 = 3. Na koniec pokazuje pułapkę: z liczbą zmiennoprzecinkową zamiast √3/2 dwunasta potęga nie daje dokładnie (1, 0), bo błąd z pierwszego zaokrąglenia jedzie przez wszystkie mnożenia. W zapisie z tożsamości Eulera znaki tarczy to e^{iπk/6}, a pierwiastki z jedynki to e^{2πik/n}.
Auf Deutsch: Stichwörter¶
Die n-ten Einheitswurzeln sind die n Marken auf dem Einheitskreis; mit √3 exakt gerechnet, nicht als Dezimalzahl.
Stichwörter: Einheitswurzeln, Einheitskreis, regelmäßiges n-Eck, exakte Arithmetik mit √3, zyklische Gruppe, primitive Wurzel.
See also¶
- Multiplication rotates — angles add, which this page applies n times over
- Euler's identity — the next lesson: the clock's marks named e^{iπk/6}, and the half turn reached exactly as the sixth power of the first mark
- Radians — the marks sit every π/6 radians, and why angles are measured that way
- Multiplication as pairs — the pairs are a field, which is what makes "at most n solutions" true
- Multiplication can be undone — no two nonzero pairs multiply to (0, 0), the step that makes the roots of unity add up to nothing
- Root of unity ↗ — Wikipedia
- De Moivre's formula ↗ — Wikipedia
- Niven's theorem ↗ — Wikipedia, which angles have a rational cosine
- Complex Number Primer: powers and roots, Paul's Online Notes ↗ — the same computation done with angles, the way a course does it
- Where this is taught — more notes and the textbooks