Rationalising Denominators 5: Roots of Unity

Posts in this series:

Powers

Products

Sums

Ratios

Roots of unity

Rationalising denominators

Introduction

In the previous post we defined Ratio to represent division. This lets us express numbers like ½; as well as more complicated expressions involving nth-roots, their products and their sums. We’ve seen how to remove common factors and handle negation, but the full normalisation algorithm requires one more extension to our representation: roots of unity.

Unity and its roots

“Unity” is a fancy way of referring to the number one, so a root of unity is an nth-root of one; i.e. a number which, when raised to some whole exponent, results in 1.

The first root of unity

The number 1 itself has this property, since 1ⁿ = 1 for any whole exponent n. Hence we could simply declare that 1 is the root of unity and be done with the idea.

However, 1 is simply the first root of unity (or the “oneth root”, with “fractional” exponent ¹⁄₁). If we allow the possibility that other such numbers exist, we discover a consistent theory with rich structure and useful applications.

Square roots of unity

In a previous post we implemented negative numbers by encoding a special value (commonly referred to as “-1”) as √1, such that √1² = √1⁰ = 1.

It’s no coincidence that this behaviour fits nicely into our numerical representation, since this was not a one-off hack: as the (“primitive”) square root of unity, it is part of a larger pattern.

Geometrically, the value √1 does not appear on the same “number line” as 1 (counting away from 0 using multiples of 1). Instead, it has its own number line, counting away from 0 in a different direction, using multiples of √1; i.e. the negative numbers. Since the negative numbers are a subset of the Real numbers, √1 is considered to be a Rational number, and hence why our power_is_rational function has a special-case for it.

We can think of this negative number line (associated to √1) as being a reflection of the positive number line (associated to 1). However, it is equivalent (and, as we shall see, more useful) to instead treat it as a rotation by half a turn (AKA ½τ):

Multiplying any number by √1 hence rotates that number by half a turn in this “Complex plane”. Multiplying twice rotates by a full turn (AKA 1τ).

The number 1 is a square root of unity, since 1² = 1 × 1 = 1. Notice that this self-multiplication does not produce the other square root of unity (√1).

In contrast, we call √1 the primitive square root of unity, since √1² = √1 × √1 = 1, which does create the other square root of unity (1) through self-multiplication.

Cube roots of unity

Extending this idea, we can now consider the cube roots of unity. This time there are three, which we will represent as:

• ∛1¹ = ∛1, which is the primitive cube root of unity.
• ∛1²
• ∛1³ = ∛1⁰ = 1, AKA one AKA “unity”.

Those first two numbers are less familiar than 1 or √1 (AKA -1), but they also have their own number lines; this time rotated by ⅓τ and ⅔τ, respectively:

The value ∛1 is the primitive cube root of unity, since it can form the others by self-multiplication:

• ∛1 × ∛1 = ∛1²
• ∛1 × ∛1 × ∛1 = 1

The number lines for ∛1 and ∛1² do not contain Real numbers (other than 0), so our power_is_rational function does not have any special-cases for these; or indeed for any other roots of unity.

Fourth roots of unity

Going one step further, we get the fourth roots of unity ∜1¹, ∜1², ∜1³, ∜1⁴; although these are usually normalised and given different names:

• ∜1⁴ = ∜1⁰ = 1 is the ordinary number one.
• ∜1² = √1, AKA negative one.
• ∜1¹ = ∜1 is called the imaginary unit and usually written with the symbol 𝑖.
• ∜1³ = √1 × ∜1 = -𝑖 is the negative of the imaginary unit.

Since ¼ + ¼ = ½, we can apply the laws of indices to find that ∜1² = √1; or, in more common notation, that 𝑖² = -1.

Geometrically, these four number-lines are rotated at right-angles (¼τ) from each other; and composing two right-angles gives a half-turn, corresponding to the negative number-line we saw for the (primitive) square root of unity.

Likewise, the number-line for ∜1³ is two right-angles away from that of ∜1, and is hence its negative. We can see this geometrically, or again by applying the laws of indices (this time noting that ¾ = ½ + ¼). All of the Imaginary numbers (i.e. all positive and negative multiples of 𝑖) appear on these two number-lines; and this “imaginary axis” is orthogonal (perpendicular) to that of the Real numbers.

Hence the numbers 1 and 𝑖 form an orthonormal basis spanning the entire Complex plane; with any Complex number being uniquely represented as a sum of a Real value and an Imaginary value. For example, we can rewrite the primitive cube root of unity ∛1 = -½ + ½𝑖√3.

However, notice that this form is not compatible with our encoding, since it requires a Sum of Ratio values, which we do not allow. Anyhow, this series of blog posts only aims to represent a subset of the Real numbers (those with no nested radicals), in which case the Imaginary part would always be 0i AKA 0; and we’d still have to represent the Real part somehow, which is exactly the problem we’re trying to solve!

Fifth roots of unity

The last example we’ll see is the fifth roots of unity, since they nicely demonstrate a general fact we will need about the roots of unity:

Summing roots of unity

As we can see from the diagrams above, the nth roots of unity are arranged at the corners of a regular n-gon inscribed in the unit circle. This also holds for the square root case, which we can think of as forming a regular digon. This leads to a remarkable fact about these numbers: they sum to zero!

This is immediately clear when n is even, since each root can be paired up with another exactly opposite; with each pair summing to zero, so does the whole lot.

When n is odd, it is perhaps less clear. In this case, we can consider vectors (arrows) pointing from zero to each of our roots of unity. We can then calculate their sum geometrically: by composing their corresponding vectors “tip to tail”, translating the initial tail to begin at zero, then reading the total by seeing where the final tip lands. Each of our vectors has the same length (they are all radii of the unit circle), and their orientations are distributed equally around a full turn, so their tip-to-tail composition will also form a regular n-gon. Since that is a closed shape, the final tip must land on the initial tail; since the initial tail was placed at zero, the total must also be zero!

For example, we can visualise the sum of all fifth roots of unity by first travelling along the positive number-line from 0 to ⁵√1⁰ (AKA 1). From there, we travel parallel to the number-line for ⁵√1¹ for one unit; ending up one unit to the right of ⁵√1¹ (which makes sense, since addition commutes). Next, we travel parallel to the number-line for ⁵√1², again for one unit; and so on. Our path traces out a complete, regular pentagon, ending back where we started at 0, which is the total.

Subsets, complements and negations

Given that the sum of all nth roots of unity is zero (when n > 1), consider what happens if we split those roots into two complementary subsets. The sum of both subsets together must be zero (since, together, they contain all of the roots); hence the sum of one must be the negative of the other’s sum. (Note that for a complete n-gon this is trivial: summing all of the roots gives 0, as we’ve seen; summing none of the roots is also 0, since that’s the empty Sum; and 0 is its own negative.)

For example, let’s split the fifth roots of unity into two sets. We’ll begin with the identity established above:

⁵√1⁰ + ⁵√1¹ + ⁵√1² + ⁵√1³ + ⁵√1⁴ = 0

Now we’ll pick a subset of these roots, say ⁵√1¹ and ⁵√1⁴. Subtracting those from both sides of this equation, we get:

⁵√1⁰ + ⁵√1² + ⁵√1³ = √1⁵√1¹ + √1⁵√1⁴

Hence the sum of our chosen subset is equal to the negative of the sum of its complement (those roots we didn’t pick). As always, when we find two representations that have equal values, we need to choose one of them to be the normal form!

Choosing the simplest subset

We need a consistent way of deciding which sum of roots is “simpler”, to use as our normal form. Our heuristic for simplicity is that fewer roots are simpler, falling back to lexicographical order if the number of roots is the same:

def roots_complexity(roots):
    return (
        # Fewer roots is simpler
        len(roots),
        # Fall back to lexicographic order
        sorted(roots),
    )

Finding a common denominator

The logic we’ve seen so far works well when all of our roots have the same order n, but what if we have a sum of roots of different orders, like ∛1 + ⁵√1? These belong to different polygons (a triangle and a pentagon), so we can’t compare or combine them directly.

However, we can always find a common polygon that contains vertices for both, by finding a common denominator for their exponents. For example, ⅓ can be written as ⁵⁄₁₅, and ⅕ can be written as ³⁄₁₅, so we can rewrite their sum as:

¹⁵√1⁵ + ¹⁵√1³

Now, both terms are expressed as fifteenth roots of unity, and they can be treated as vertices of a single regular 15-gon.

In general, for any collection of roots of unity, we can find a common order by calculating the least common multiple of their exponents’ denominators.

Normalising sums of roots of unity

We’ve now established enough of the theory of roots of unity to normalise Sum values containing them.

Normalising roots of unity in isolation

The following function takes a list of Fractions, representing the exponents of some roots of unity. It searches this list for subsets of elements which form part of a regular n-gon (as an optimisation: we only need to check values for n which are prime factors of the common denominator of all the roots). Such partial n-gons are compared to their negated complement, using the roots_complexity function: if the negated complement is simpler, those roots are swapped-out:

def remove_polygons(given: List[Fraction]):
    """"Look for angles that form the majority of a regular n-gon. If we find
    any, replace them with their 'negative complement'; i.e. the missing parts
    of that polygon, rotated by a half-turn. For example:
     - If we find a triangle, like [0/3, 1/3, 2/3], that's a complete loop and
       hence equivalent to not going anywhere, i.e. the empty list [].
     - If we find the first three parts of a regular pentagon [0/5, 1/5, 2/5],
       then that's not a complete loop. However, we could reach the same point
       in only two steps, if we go backwards along (i.e. add a half to) the
       missing parts, giving the list [3/10, 4/10].
     - The special case of an angle and its opposite, like [1/4, 3/4], are
       treated as a complete digon.
    """
    if len(given) == 0:
        return []

    angles = [angle % 1 for angle in given]  # Normalise to unit circle

    # Get common denominator
    q = lcm(*(f.denominator for f in angles))
    factors = prime_factors_unique(q)
    counts = Counter(angles)

    # If there are repeated values, we should loop enough times to allow every
    # copy of those values to be removed
    _, iterations = counts.most_common(1).pop()

    for _ in range(iterations):
        # We only need to look for n-gons where n is a prime factor of the
        # common denominator q of all the angles.
        for n in factors:
            step = Fraction(1, n)  # spacing between vertices of an n-gon
            # For each possible starting point mod q
            for start in map(lambda i: Fraction(i, q), range(q)):
                # Look for a vertex at each position
                found = []
                complement = []
                for pos in ((start + i * step) % 1 for i in range(n)):
                    if counts[pos] > 0:
                        found.append(pos)
                    else:
                        complement.append((pos + Fraction(1, 2)) % 1)

                if roots_complexity(complement) < roots_complexity(found):
                    # Append the complement
                    for v in complement:
                        angles.append(v)
                        counts[v] += 1
                    # Remove existing
                    for v in found:
                        angles.remove(v)
                        counts[v] -= 1
    return angles

Normalising as part of Sum values

We can apply this normalisation to Sum values using the following helper, to extract all of the roots of unity; pass them to remove_polygons; and, if any simplification occurs, reconstruct a new Sum from the simplified roots:

def _sum_roots_of_unity(s: Sum):
    irrational_coeffs, rational = _split_rational(s)
    irrational = _sum_to_products(irrational_coeffs)
    roots_of_unity = [
        one if p == {} else list(p.values()).pop()
        for p in irrational
        if is_unity(p)
    ]

    if rational > 0:
        roots_of_unity.append(one)
        rational -= 1
    if rational < 0:
        roots_of_unity.append(half)
        rational += 1

    if len(roots_of_unity) < 2:
        return s

    reduced = remove_polygons(roots_of_unity)
    if sorted(reduced) == sorted(roots_of_unity):
        return s

    # If we reach here, some reduction has occurred; so turn that into a new Sum
    remaining = [p for p in irrational if not is_unity(p)]
    rational_prod = Product(Power(rational, one)) if rational >= 0 \
        else Product(Power(abs(rational), one), power_neg)
    total = remaining + [rational_prod] + [
        Product(Power(1, exp)) for exp in reduced
    ]
    return irrationals_coefficients(total)

We can call this directly from normalise_sum as follows:

    roots = _sum_roots_of_unity(s)
    if not sums_are_same(roots, s):
        return normalise_sum(roots)

Conclusion

This _sum_roots_of_unity function is quite limited in the sorts of Sum values it can normalise; e.g. ignoring roots of unity which occur with other factors. However, the existing normalisation steps for Sum, which try holding-out unfactorable terms, and dividing-through by common factors, are intended to isolate the sorts of subexpressions that are amenable to this process; thus widening its scope considerably.

Whilst we’re aiming to normalise Real numbers, we’ll see in the next part that such Complex roots of unity are vital to our final normalisation algorithm.

The full code for this post can be found in my conjugate repo.