In this post we start our journey into the algebra of Circle STARKs. It's pretty easy actually.

The Complex Numbers

You remember the complex numbers $\mathbb{C}$ from high-school maths, right? Some high-school teachers are better at conveying this than others, but the way to "construct" the complex numbers is as a quotient of the polynomial ring $\mathbb{R}[X]$ by the ideal generated by the irreducible polynomial $X^2 + 1 \in \mathbb{R}[X]$:

$$ \mathbb{C} = \mathbb{R}[X] / (X^2 + 1) $$

In other words, polynomials plus/minus multiples of $X^2 + 1$. The more common way to think about the complex numbers is as $ a + b \cdot i$ where $i$ and $-i$ are the roots of the polynomial $X^2 + 1$, i.e. $i^2 + 1 = 0$ and $(-i)^2 + 1 = 0$. These two views are isomorphic (the same) via:

$$\phi: a + b \cdot i \mapsto a + b \cdot X$$

For completeness, let's briefly recall the algebra of complex numbers:

You add complex numbers "coordinate-wise":

$$ (a + b \cdot i) + (c + d \cdot i) = (a + c) + (b + d) \cdot i $$

This is because, as we saw, they are really just (equivalence classes of) polynomials in disguise and this is how you add polynomials. Similarly, you multiply complex numbers like this:

$$ \begin{aligned} &(a + b \cdot i) \cdot (c + d \cdot i) \\ = \\ &(a \cdot c - b \cdot d) + (a \cdot d + b \cdot c) \cdot i \end{aligned} $$

This is equivalent to multiplication of polynomials in $\mathbb{F}[X]$, followed by reduction modulo $X^2 + 1$. Finally, as a result, if you multiply a complex number by itself you get:

$$ (a + b \cdot i) \cdot (a + b \cdot i) = (a^2 - b^2) + 2 \cdot a \cdot b \cdot i $$

Because, you know, $i^2 = -1$. We also have the "complex conjugate" of a complex number $\bar{z}$, defined by flipping the imaginary component i.e. $\overline{(x + i y)} = x - i y$. This distributes over multiplication and addition: $\overline{z_1 \cdot z_2} = \bar{z_1} \cdot \bar{z_2}$ and $\overline{z_1 + z_2} = \bar{z_1} + \bar{z_2}$. Recall that both $i$ and $-i$ are roots of the polynomial $X^2 + 1$, so one can think of conjugation as switching between the arbitrary choice of $i$ and $-i$. If you feel fancy you can call such a map a field automorphism: it maps from the field to itself and preserves the field operations.

Nothing Special About The Reals

In the section above we constructed the complex numbers as a quotient of the polynomial ring $\mathbb{R}[X]$ by the ideal generated by the irreducible polynomial $X^2 + 1 \in \mathbb{R}[X]$. Exactly the same works for any field $\mathbb{F}$ ($\mathbb{F} = \mathbb{R}$ in the above example), in particular, for finite fields: suppose we have a finite field $\mathbb{F} = \mathbb{F}_q$, then you can consider the polynomial $X^2 + 1 \in \mathbb{F}_q[X]$ and extend the field with a root of this polynomial. i.e. form the "degree 2 extension" of $\mathbb{F}_q$ as:

$$\mathbb{F}_{q^2} = \mathbb{F}_q[X] / (X^2 + 1)$$

Note that $X^2 + 1$ needs to be irreducible in the field $\mathbb{F}_q$ e.g. $\mathbb{F} = \mathbb{F}_2$ won't work, since:

$$(X + 1)^2 = X^2 + 1 + 2 X = X^2 + 1$$

The Unit Circle as a Group

Do you also remember the real unit circle from high-school maths? Sure you do, here it is:

$$ \mathbb{S}^1 = \{ (x, y) \mid x^2 + y^2 = 1 \} \subset \mathbb{R}^2 $$

This just means every element of "$l^2$-norm 1" in $\mathbb{R}$: every point at "distance 1" from the origin or every vector of length one if you will.

If we consider the complex numbers with norm 1, we get the unit circle in the complex plane:

$$ \begin{aligned} \mathbb{S}^1 &= \left\{ z \in \mathbb{C} \mid \left|z\right| = 1 \right\} \\ &= \left\{ z = x + i y \in \mathbb{C} \mid z \cdot \bar{z} = 1 \right\} \end{aligned} $$

By looking at the circle like this, we can see that it is a group under multiplication, if you multiply two complex numbers $z_1, z_2 \in \mathbb{C}$ of norm 1, you get a complex number $z_1 \cdot z_2$ of norm 1, as shown below:

$$ \begin{aligned} (z_1 \cdot z_2) \cdot \overline{z_1 \cdot z_2} &= (z_1 \cdot \bar{z}_1) \cdot (z_2 \cdot \bar{z}_2) \\ &= 1 \cdot 1 = 1 \end{aligned} $$

If you were really paying attention in high-school, you might even remember Euler's formula, which is an alternate representation of complex numbers with norm 1:

$$ e^{i \theta} = \cos(\theta) + i \sin(\theta) \in \mathbb{S}^1 $$

This is useful because it translates between angles $\theta$ and points on the unit circle, as shown in the animation below:

So we can also write it as:

$$ \begin{aligned} \mathbb{S}^1 &= \{ (x, y) \mid x^2 + y^2 = 1 \} \\ &= \{ z \in \mathbb{C} \mid |z| = 1 \} \\ &= \{ e^{i \theta} \mid \theta \in \mathbb{R} \} \end{aligned} $$

And therefore, the unit circle has a group structure, that we can view in a couple of ways:

• As multiplication of complex numbers: $$ \begin{aligned} &(x_1 + i y_1) \cdot (x_2 + i y_2) \\ = \\ &(x_1 x_2 - y_1 y_2) + i (x_1 y_2 + x_2 y_1) \end{aligned} $$

• As addition of angles $\theta_1 + \theta_2$: $$ e^{i \theta_1} \cdot e^{i \theta_2} = e^{i (\theta_1 + \theta_2)} $$

The identity element is the point at angle $\theta = 0$, which is the point $(x, y)=(1,0)$ or $1 \in \mathbb{C}$:

$$1 + 0i = e^{i 0} = 1 $$

The inverse of $z = x + i y = e^{i \theta} $ is the point with the same angle, but opposite direction:

$$ J(z) = e^{i (- \theta)} = x - i y $$

This point always lies exactly opposite the point $z$ on the circle, so all we have to do is flip the y-coordinate: the complex conjugate of $z$. This is illustrated below with a point and its inverse moving around the circle:

This is clear from both interpretations of the group structure:

• As multiplication of complex numbers: $$ \begin{align} z \cdot J(z) &= (x + i y) \cdot (x - i y) \\ &= x^2 + y^2 = 1 \end{align} $$

• As addition of angles: $$ e^{i\theta} \cdot J(e^{i\theta}) = e^{i\theta} \cdot e^{-i\theta} = e^{i \theta - i \theta} = e^{i \cdot 0} = 1 $$

Since we have a group, it is natural to look at maps from the group to itself. The most central of which is going to be the humble "squaring" or "doubling" map, depending on which perspective we choose:

$$ \pi: \mathbb{S}^1 \to \mathbb{S}^1 $$

Which simply:

• Squares the complex number $z = x + iy$ of norm $1$:

$$ \begin{aligned} \pi(x + iy) &= (x + iy) \cdot (x + iy) \\ &= (x^2 - y^2) + i (2xy) \\ &= 2 x^2 - 1 + i (2xy) \end{aligned} $$

• Or, equivalently, doubles the angle of the point $z = e^{i\theta}$:

$$ \pi(e^{i\theta}) = e^{i\theta} \cdot e^{i\theta} = e^{i \cdot 2\theta} $$

Because we have $x^2 + y^2 = 1$, we can replace $y^2$ with $1 - x^2$ and write $\pi(x + i y) = 2 x^2 - 1 + i (2xy)$. Note that the x-coordinate ("real part") of the doubled point, $2 x^2 - 1$, does not depend on $y$, this means that we can compute the x-coordinate ("real part") of repeated doubling using just the x-coordinate and the formula $x_{n+1} = 2 \cdot x_n^2 - 1$, a nice optimization that will come in handy later.

How "Big" is The Circle?

We just saw that the circle is a subgroup of the multiplicative group of the complex numbers, we also saw earlier that there is nothing "special" about a degree-2 extension of the reals as opposed to any other field: notably finite fields.

The next natural question is: How "large" is this circle group that we introduced? i.e. what is its order? i.e. how many points are there on the unit circle over an arbitrary field? In order to figure this out, we create a bijective map from the circle to the projective line with an "extra point". To explore this consider the "stereographic projection" onto the y-axis with center $(-1, 0)$: the intersection between the line $((-1, 0), (x, y))$ and the y-axis. This is illustrated below:

So as we move the point around the circle we can "hit" every value on the y-axis AND a special value "at infinity" when $(x, y) = (-1, 0)$: it sends any point on the circle to $\mathbb{R} \cup \{ \infty \}$.

It is also easy to see that the mapping is injective, i.e. every point $\mathbb{R} \cup \{ \infty \}$ corresponds to a unique point on the circle. So there is an isomorphism between the unit circle and the projective line with a point at infinity. When $x \neq -1$, the explicit mapping and inverse is given by:

$$ t = \frac{y}{x + 1}, \quad (x, y) = \left( \frac{1 - t^2}{1 + t^2}, \frac{2t}{1 + t^2} \right) $$

Although the illustration above is only meaningful for the real numbers, the mapping (the equations above) works for any field $\mathbb{F}$. This means that the number of points on the unit circle over a field $\mathbb{F}$ is $|\mathbb{F}| + 1$, corresponding to the projective line $\mathbb{F}$ AND a point at infinity. When $|\mathbb{F}| = 2^k - 1$ (Mersenne prime) the unit circle has $2^k$ points i.e. it is a smooth group that we can use for FFTs and FRI as discussed in part one of this series.

As a sanity check: suppose we have an arbitrary field $\mathbb{F}$ (e.g. some prime field $\mathbb{F}_p$), the total number of elements in the degree two extension $\mathbb{C} = \mathbb{F}[X] / (X^2 + 1)$ is $|\mathbb{C}| = |\mathbb{F}|^2$ and the number of elements in the multiplicative group $\mathbb{C}^{*}$ is therefore $|\mathbb{C}^*| = |\mathbb{F}|^2 - 1$, everything except $0$ has an inverse. And hence $|\mathbb{S}_1| = |\mathbb{F}| + 1$ divides $|\mathbb{C}^{*}| = |\mathbb{F}|^2 - 1$ as expected: since the circle is a subgroup of the multiplicative group $\mathbb{C}^{*}$, this is required by Lagrange's theorem.