# Basic Algebraic Geometry in Circle STARK

STARKs working on small fields have become a popular method to improve efficiency. Circle STARK, as one of these, has a structure compatible with the highly efficient Mersenne31 field. However, understanding this structure requires substantial background knowledge in algebraic geometry. This foundational knowledge is also beneficial for understanding pairing-based cryptography, another popular cryptographic tool in the zero-knowledge proof area.

To fill these gaps in background knowledge, I spent considerable time identifying the necessary concepts. I believe this background should be well-summarized for those interested in understanding it. This is the motivation for writing this article. It assumes familiarity with several concepts, including group, ring, ideal, field, and field extension. Some general concepts will be built step by step, using Circle STARK as an important example. After reading this article, the following questions will be answered:

**Questions:**

1. What is the meaning of various concepts, including affine space, projective space, variety, divisor, and the Riemann-Roch theorem?
2. Why is there an isomorphism between $X^2 + Y^2 = Z^2$ and $\mathbb{P}^1$?
3. How can the Riemann-Roch theorem be used to derive the bases used by Circle Code space?

> Disclaimer: These notes are provided without responsibility for mistakes. However, if you find any, I am happy to correct them. Special thanks to Prof. Guo Yu, Wang Yao, @aleph_v, Liam Eagen for their feedback and discussion.

## Affine Space vs. Projective Space

In this article, I will use $K$ as the algebraic closure field to bypass many details. I will use $K$ as the working field by default. Affine space is symbolized by $\mathbb{A}^n$, where $n$ is a positive integer. The elements (points) in $\mathbb{A}^n$ are defined by the tuple form $(X_1, X_2, \ldots, X_n)$, where $X_i$ is defined over $K$.

Another important space is called projective space. There are some connections between these two spaces. Projective space offers a more convenient way to compute in many cases. Basically, projective space is symbolized by $\mathbb{P}^n$, where $n$ is a positive integer. The elements (points) in $\mathbb{P}^n$ are defined by the tuple form $(X_1, X_2, \ldots, X_n, X_{n+1})$, where $X_i$ is defined over $K$. Yes, an element in projective space is $n+1$ tupled. There are some important properties of the projective space.

- **Property 1**: For any non-zero $\lambda$ in $K$, $(\lambda X_1, \lambda X_2, \ldots, \lambda X_{n+1})$ is equivalent to $(X_1, X_2, \ldots, X_{n+1})$ and there is no all-zero point in $\mathbb{P}^n$. This property implies the element in projective space is defined as a vector, and $\mathbb{P}^n$ almost corresponds with $\mathbb{A}^n$.
- **Property 2**: To clarify the correspondence between these two spaces, there is a relationship $\mathbb{P}^{n+1} = \mathbb{A}^n \cup \mathbb{P}^n$. To achieve this relationship, we discuss two cases for a projective space point $(X_1, X_2, \ldots, X_n, X_{n+1})$.
- If $X_{n+1} \neq 0$, let $\lambda = 1/X_{n+1}$ and we get another equivalent point $(X_1/X_{n+1}, X_2/X_{n+1}, \ldots, X_n/X_{n+1}, 1)$, showing a relationship with $\mathbb{A}^n$.
- If $X_{n+1} = 0$, then $(X_1, X_2, \ldots, X_n, 0)$ shows a relationship with $\mathbb{P}^n$, which is called the infinity of $\mathbb{P}^{n+1}$. The infinity of $\mathbb{P}^1$ is called the infinity point, while the infinity of $\mathbb{P}^2$ is called the infinity line.
- **Property 3**: The polynomials defined in projective space $\mathbb{P}^n$ should be homogeneous polynomials, e.g., $X_1X_2+X_3^2$, $X_1 + X_2$, in which each term has the same degree. This property can derive another equation: for each homogeneous polynomial $f$ and non-zero $\lambda$, the evaluation $f(\lambda X_1, \lambda X_2, \ldots, \lambda X_{n+1})$ is equal to $\lambda^{n+1}f(X_1, X_2, \ldots, X_{n+1})$.

### Example: Circle Curve

A circle curve, defined by $C = C(F_p)$, where $F_p$ is a prime field with $p \equiv 3 \mod 4$, has two forms. $x^2 + y^2 = 1$ is defined in affine space $\mathbb{A}^2$, while $X^2 + Y^2 = Z^2$ is defined in projective space $\mathbb{P}^2$. We can show there is the same number of points (and isomorphism) between these two definitions in $C(F_p)$ by applying property 2.

For point $(X, Y, Z)$ in $X^2 + Y^2 = Z^2$, if $Z \neq 0$, we can change the coordinate to $(X/Z, Y/Z, 1)$ by multiplying $1/Z$. If $Z = 0$, we get $X^2 + Y^2 = 0$, which means both $X$ and $Y$ should be $0$. Because the all-zero point is not defined in $\mathbb{P}^2$, the circle curve has no point when $Z = 0$. □

However, this is not always a correct assertion for the circle curve defined over an extension field of $F_p$. By taking $F(i)$ as an example, we can find the equation $X^2 + Y^2 = 0$ has two solutions in $F(i)$. The two solutions are defined by $\infty = (1: +i: 0)$ and $\overline{\infty} = (1: -i: 0)$ in the Circle STARK paper. There are indeed some other solutions like $(2:-2i:0)$, but remember that these solutions are equivalent to these two points by applying property 1.

## Coordinate Ring, Rational Map, and Morphism

We want to find how the polynomials affect points on the curve. For a finite prime field $F_p$, we can define a multi-variable polynomial ring by $F[X_1, X_2, \ldots, X_n]$. Similarly, for a curve $C$ defined by polynomial $f$ in affine space, we can define a coordinate ring by $F[X_1, X_2, \ldots, X_n] / f(X_1, X_2, \ldots, X_n)$, which means two elements in the coordinate ring, say $g_1$ and $g_2$, are equivalent if and only if $g_2 - g_1$ is in the ideal generated by $f(X_1, X_2, \ldots, X_n)$, e.g., $x-x^3$ is equivalent to $xy^2$ in the circle curve.

The concept of the function field is defined by the quotient field of the coordinate ring, e.g., $\frac{x+1}{y^2}$. Note that the coordinate ring and function field are defined in affine space, but based on the properties mentioned in the previous section, we can describe the function field of projective space $\mathbb{P}^n$ as the function field of an $\mathbb{A}^n$ by using the "conversion method". We can also describe the function field of a projective space as the field of $f(x)/g(x)$, where $f$ and $g$ are homogeneous polynomials of the same degree and $g$ shouldn't be in the ideal generated by $f(X_1, X_2, \ldots, X_n, X_{n+1})$.

Now, we can define a rational map which shows the relationship between different curves. Let's say $\phi$ is a rational map from curve $C_1$ in $\mathbb{P}^{n_1}$ to curve $C_2$ in $\mathbb{P}^{n_2}$.

$$ \phi: (f_1, \ldots, f_{n_2}) $$

where $f_i$ is a rational map on $\mathbb{P}^{n_1} \rightarrow K$.

A rational map is regular at $P \in C_1$ when for all $f_i = f/g$, $g(P)$ is not zero and there is some $f_i(P) \neq 0$. The definition of regular is natural; a rational map is meaningful when it has a non-zero denominator and does not map to an all-zero point.

A "well-defined" rational map is called a morphism. By "well-defined", it means the rational map is regular for each point in curve $C_1$. It seems hard to find a morphism, but note that property 1 of projective space—multiplying the same polynomial is safe. We can first multiply a homogeneous polynomial to "clear" the denominators of all $f_i$. Then, for some "bad" points, we can multiply another homogeneous polynomial to make the rational map regular at those points. We will explain it in the example below.

### Example: Circle Group

We define a rational map $\phi$ from $X^2 + Y^2 = Z^2$ to $\mathbb{P}^1$. Here, we use the symbol $(X, Y, Z)$ to represent the point in $X^2 + Y^2 = Z^2$ and $(S, T)$ to represent the point in $\mathbb{P}^1$.

$$\phi : (X, Y) \rightarrow (S = X+Z, T = Y)$$

Let's check if $\phi$ is a morphism or not. There are no denominators in the map, so we just consider if some point will be mapped to $(0, 0)$. We solve the equation of $X+Z = 0$, $Y = 0$, and $X^2 + Y^2 = Z^2$. After some simple computation, the solution over $F_p$ is $(-1, 0, 1)$.

To solve this "bad" point, we can multiply $X-Z$ to this map.
$$\phi: ((X+Z)(X-Z), Y(X-Z)) \rightarrow (X^2-Z^2, Y(X-Z)) \rightarrow (-Y^2, Y(X-Z))$$

Then, we multiply $\frac{1}{Y}$ ($Y$ is not in the ideal generated by $f$, so it's safe to multiply this function) to this map.

$$\phi: (-Y^2 \cdot \frac{1}{Y}, Y(X-Z) \cdot \frac{1}{Y}) \rightarrow (-Y, X-Z)$$

We check the "bad" point $(-1, 0, 1)$ again. Now, it is mapped to a meaningful point $(0, -2)$, which is also $(0, 1)$, the infinity point of the $\mathbb{P}^1$.

If we can find another morphism $\psi$ from $\mathbb{P}^1$ to $X^2 + Y^2 = Z^2$ and $\phi\psi(x) = \psi\phi(x) = x$, then we can say there is an isomorphism between these two curves.

$$\psi: (S, T) \rightarrow (S^2-T^2, 2ST, S^2+T^2)$$

We can verify the rational map $\psi$ is also a morphism and $\phi\psi(x) = \psi\phi(x) = x$ is also satisfied. So, we find an isomorphism successfully.

Let $T = 1$ and $Z = 1$ to make the functions of isomorphism to be function field in affine. This isomorphism is exactly the equations in Lemma 1's proof of the Circle STARK paper, where it is called stereographic projection at $(0, -1)$.

There are indeed some other morphisms, e.g., stereographic projection at $(0, 1)$. Writing it down will be a good practice for understanding how it works.

## Order Function

In this section, we try to define the properties of a function at a point. Before that, I need to claim that all curves mentioned in this article are smooth curves. To check if it is smooth at some point $P$, it's easy to check the equation

$$\frac{\partial f}{\partial X_1} (P) = \ldots = \frac{\partial f}{\partial X_n} (P) = 0$$

If a curve is smooth, each point in the curve will satisfy the equation above. There is a related proposition about smoothness.

**Proposition**: Let $M_P$ be the ideal of all polynomials in the coordinate ring vanishing on $P$, i.e., $M_P = \{ f: f(P) = 0 \}$. The equation below is always satisfied.

$$\dim M_P/M_P^2 = \dim C = 1$$

where $\dim$ is the dimension of space, and $C$ is a curve. Although we don't define the dimension, here you can use the intuition about this concept, e.g., the dimension of an $n$-vector space is $n$, the dimension of $\mathbb{A}^2$ and $\mathbb{P}^2$ is both 2, and the dimension of a curve defined by an irreducible polynomial in $\mathbb{A}^2$ is 1.

Now, we can define the ord function of a polynomial, which maps a polynomial at a point to an integer.

$$\text{ord}_P(f) = \sup \{ d \in \mathbb{Z}: f \in M_P^d \}$$

This inaccurately means $d$ is exactly the exponent of the ideal generator contained in $f$. Naturally, we can have some properties about the order function.

- If a polynomial does not vanish at $P$, the order should be 0, because it does not belong to $M_P$.
- $\text{ord}_P(fg) = \text{ord}_P(f) + \text{ord}_P(g)$.
- $\text{ord}_P(f/g) = \text{ord}_P(f) - \text{ord}_P(g)$.
- $\text{ord}_P(f + g) = \min \{ \text{ord}_P(f), \text{ord}_P(g) \}$.

If you feel a bit confused now, do not worry and check the example for a better understanding.

### Example: Order Function of the Circle Curve

Let's examine the point $\infty = (1: i: 0)$ first, which exists only in projective space. $M_\infty$ is generated by $Z$ and $X+iY$. (Note that only homogeneous polynomials are meaningful in projective space.)

By considering $X^2 + Y^2 = Z^2$, it can be rewritten as $(X-iY)(X+iY) = Z^2$ and $X-iY$ does not vanish at $\infty$, so $\text{ord}_\infty(X-iY) = 0$ and $\text{ord}_\infty(X+iY) = 2 \times \text{ord}_\infty(Z)$, meaning the order of $X+iY$ should be at least 2. Because $\dim M_P/M_P^2 = 1$, there is a generator lying in $M_P/M_P^2$, which should be $Z$.

The polynomials $X$ and $Y$ do not vanish at $\infty$, so their order should be 0. By applying the properties of the order function, we get:

$$\text{ord}_\infty(Z) = 1, \text{ord}_\infty(X/Z) = -1, \text{ord}_\infty(Y/Z) = -1$$

Let's check another point $P = (0, 1, 1)$. $M_P$ is generated by $X$ and $Y-Z$. By considering $(Y-Z)(Y+Z) = -X^2$ and $Y+Z$ does not vanish at $P$, we achieve the result $\text{ord}_P(X) = 1$. We get:

$$\text{ord}_P(Z) = 0, \text{ord}_P(X/Z) = 1, \text{ord}_P(Y/Z) = 1$$

The same situation occurs at $\overline{\infty}$. We skip these details for brevity.

$$\text{ord}_{\overline{\infty}}(Z) = 1, \text{ord}_{\overline{\infty}}(X/Z) = -1, \text{ord}_{\overline{\infty}}(Y/Z) = -1$$

## Divisor and Riemann-Roch Theorem

Divisors are much simpler to understand. In the previous section, we described the properties of functions at a point. A divisor can be seen as a description of all points in $C$ associated with integers. A divisor can be defined by the equation below:

$$D = \sum_{P \in C} n_P (P)$$

where $n_P$ is an integer.

For example, $D = 2P_1 + 2P_2$ means that for point $P_1$, we associate with integer 2, for point $P_2$, we associate with integer 3, and for other points in the curve, we associate those points with integer 0. The symbol "+" does not have the meaning of addition, and only the same point can be "added" or "subtracted".

$D$ is called positive, represented by $D \geq 0$, if all $n*P \geq 0$ for all $P$ on the curve. The degree of a divisor $D$ is defined by $\deg D = \sum*{P \in C} n_P$.

We can consider the divisor for a function $f$, defined by the equation below:

$$\text{div}(f) = \sum_{P \in C} \text{ord}_P(f) (P)$$

**Proposition**: The degree of a divisor of a function for a smooth curve is 0. All divisors of non-constant functions have negative terms.

Finally, we reach the goal of this article, the Riemann-Roch theorem. To express the theorem well, we first define $L(D) = \{ f: \text{div}(f) + D \geq 0 \} \cup \{ 0 \}$ as a vector space and $l(D) = \dim L(D)$. $L(D)$ can be considered as those functions in the function field, whose negative terms in the divisor can be "filled" by $D$.

The Riemann-Roch theorem states that for a smooth curve $C$ and any divisor $D$, the equation below is always correct:

$$l(D) - l(K_C -D) = \deg D - g + 1$$

where $K_C$ is a canonical divisor of $C$, and $g$ is the genus of the curve.

In the context of both Circle STARK and elliptic curves, we do not even need to know the meaning of canonical divisors and genus, which depend on different curves. The genus of a circle curve is 0, while the genus of an elliptic curve is 1.

We can derive some properties from the Riemann-Roch theorem to make life easier:

- Let $D = 0$, then $l(0) - l(K_C) = \deg 0 - g + 1$. Remember $l(0)$ is exactly the dimension of constants, which is 1, so $l(K_C) = g$.
- Let $D = K_C$, then $l(K_C) - l(0) = \deg K_C - g + 1$, so $\deg K_C = 2g-2$.
- If $\deg D \geq 2g-2$, then $l(D) = \deg D -g +1$.
- If $\deg D \geq 2g-2$, then $\deg (K_C-D) = \deg K_C - \deg D \le 0$, meaning that no function is in $L(K_C-D)$ and $l(K_C-D) = 0$.

### Example: Circle Curve Space

Consider the divisor $D = \frac{N}{2} \infty + \frac{N}{2} \overline{\infty}$, where $N \geq 0$. By applying the Riemann-Roch theorem, we get $l(D) = \deg D -g +1 = \deg D + 1 = N + 1$.

But how do the functions in $L(D)$ look? In the previous example, we provided the method to analyze the order of some functions and use them here.

$\text{div}(X/Z) = - \infty - \overline{\infty} + (0, 1, 1) + (0, 1, -1)$
$\text{div}(Y/Z) = - \infty - \overline{\infty} + (1, 0, 1) + (1, 0, -1)$

We can write the basis of $L(D)$ step by step. Let's first consider the case when $N = 0$.

- When $N = 0$, $D = 0$ and the dimension $l(D)$ is 1. We need to ensure $L(D) = \{ f: \text{div}(f) \geq -D \} \cup \{ 0 \}$ holds. Only constants can hold these equations, so the basis is chosen as $\{ 1 \}$.
- When $N = 2$, $D = \infty + \overline{\infty}$ and the dimension $l(D)$ is 3. We need to find another two linearly independent bases, and these bases should ensure $L(D) = \{ f: \text{div}(f) \geq -D \} \cup \{ 0 \}$ holds. Easily, we choose $\{ X/Z, Y/Z, 1 \}$.
- When $N = 4$, $D = 2\infty + 2\overline{\infty}$ and the dimension $l(D)$ is 5. We need to find another two linearly independent bases, and these bases should ensure $L(D) = \{ f: \text{div}(f) \geq -D \} \cup \{ 0 \}$ holds. Now, we have some choices, including $(X/Z)^2, (Y/Z)^2$, and $(X/Z)(Y/Z)$. $(X/Z)^2$ and $(Y/Z)^2$ are linearly related because of $(X/Z)^2 + (Y/Z)^2 = 1$, so we can only choose one of them. Suppose we choose $(X/Z)^2$, then the basis becomes $\{(X/Z)^2, (X/Z)(Y/Z), X/Z, Y/Z, 1 \}$.

Following this pattern, we can write for any $N$. Finally, we map these bases in projective space to an affine space by setting $x = X/Z$ and $y = Y/Z$, then we get the result in the paper.

$$L(D) = \{ p(x, y) \in F[x, y]/x^2+y^2+1: \deg p < N/2 \}$$

## Conclusion
Quoting Vitalik Buterin, "The underlying math behind what the 'polynomials' that Circle FRI is operating on is quite counterintuitive, and takes a while to understand and appreciate."
This paper goes through all algebraic geometry concepts used in the Circle STARK paper and tries to use the circle curve $X^2+Y^2=Z^2$ as examples to help people understand.

Algebraic geometry is a broad topic, even within mathematics. For other aspects of algebraic geometry not covered in this article, I recommend reading the materials listed in the reference as an introduction to algebraic geometry.

## Reference

- The Arithmetic of Elliptic Curves by Joseph H. Silverman
- Algebraic Curves: An Introduction to Algebraic Geometry by William Fulton
- Finite Fields by Rudolf Lidl and Harald Niederreiter
- Álvaro Lozano-Robledo's impressive video [https://www.youtube.com/playlist?list=PLYpVTXjEi1oe1OeAllJpNhFoI4B7Ws8Yl](https://www.youtube.com/playlist?list=PLYpVTXjEi1oe1OeAllJpNhFoI4B7Ws8Yl)