> ## Documentation Index
> Fetch the complete documentation index at: https://docs.starknet.io/llms.txt
> Use this file to discover all available pages before exploring further.

# Circle Evaluations and Polynomials

A polynomial can be represented in two main ways:

1. **Point-value representation**: as evaluations over a domain
2. **Coefficient representation**: as coefficients with respect to some basis

The conversion from point-value representation to coefficient representation is called *interpolation* and the conversion from coefficient representation to point-value representation is called *evaluation*. Both these conversions are based on fast Fourier transform (FFT), which will be covered in the upcoming sections.

In this subsection, we will look at the implementations of both these representations in S-two and the respective functions defined on them to interpolate and evaluate polynomials.

## Point-value representation

In S-two, the evaluations of a polynomial over a `CircleDomain` are stored using the struct `CircleEvaluation`, implemented as follows:

```rust theme={null}
pub struct CircleEvaluation<B: ColumnOps<F>, F: ExtensionOf<BaseField>, EvalOrder = NaturalOrder> {
    pub domain: CircleDomain,
    pub values: Col<B, F>,
    _eval_order: PhantomData<EvalOrder>,
}
```

Here, the domain (i.e. `CircleDomain`) and the evaluations (i.e. `values`) have the same ordering (i.e. `EvalOrder`) which can either be `NaturalOrder` or `BitReversedOrder`.

Now given the evaluations over a domain as `CircleEvaluation` we can interpolate a circle polynomial using the following functions:

```rust theme={null}
impl<B: PolyOps> CircleEvaluation<B, BaseField, BitReversedOrder> {
    /// Computes a minimal [CirclePoly] that evaluates to the same values as this evaluation.
    pub fn interpolate(self) -> CirclePoly<B> {
        let coset = self.domain.half_coset;
        B::interpolate(self, &B::precompute_twiddles(coset))
    }

    /// Computes a minimal [CirclePoly] that evaluates to the same values as this evaluation, using
    /// precomputed twiddles.
    pub fn interpolate_with_twiddles(self, twiddles: &TwiddleTree<B>) -> CirclePoly<B> {
        B::interpolate(self, twiddles)
    }
}
```

Here, `PolyOps` is a trait that defines operations on `BaseField` polynomials, such as interpolation and evaluation. Now before looking into the representation of the circle polynomial (i.e. `CirclePoly`), let us first look into some theory on polynomials over the circle.

## Polynomials over the circle

Let $F$ be an extension of the Mersenne prime field $\mathsf{M31}$. Then $F[x, y]$ represents the ring of bivariate polynomials with coefficients in $F$. The *circle polynomials* are bivariate polynomials over $F$ quotient by the ideal $\left(x^2 + y^2 - 1\right)$. The space of these bivariate polynomials over the circle curve of total degree $\leq N/2$ is denoted by $L_N(F)$.

$L_N(F) = F\left[x, y\right] / \left(x^2 + y^2 - 1\right)$

For any polynomial $p(x, y) \in L_N(F)$, we can substitute all the higher degree terms of $y$ with the equation of circle $y^2 = 1 - x^2$ and reduce $p(x, y)$ to the form:

$p(x, y) = p_0(x) + y \cdot p_1(x),$

The above form is called the *canonical representation* of any polynomial $p(x, y) \in L_N(F)$. Since $p(x, y)$ is of total degree $\leq N/2$, $p_0$ has degree $\leq N/2$ and $p_1$ has degree $\leq N/2 - 1$. Thus an alternate representation of the space $L_N(F)$ is as follows:

$L_N(F) = F[x]^{ \leq N/2} + y \cdot F[x]^{ \leq N/2 - 1}$

From the above representation we can see that the space $L_N(F)$ is spanned by the following monomial basis:

$1, x, \ldots, x^{N/2}, y, y \cdot x, \ldots, y \cdot x^{N/2 - 1}$

The dimension of $L_N(F)$ is the number of monomial basis elements, which is $N + 1$.

As a developer, you can usually ignore most of these details, since concepts like polynomial space and basis do not explicitly appear in the S-two implementation. However, they do arise implicitly in the Circle FFT algorithm, as we will see in the next section.

Now let us describe the coefficient representation and how the circle polynomials are implemented in S-two.

## Coefficient representation

Given the evaluations over a domain (i.e. `CircleEvaluation`) we can compute the coefficients of a polynomial (i.e. `CirclePoly`) with respect to some basis using the `interpolate` function. The coefficients are stored as follows:

```rust theme={null}
pub struct CirclePoly<B: ColumnOps<BaseField>> {
    /// Coefficients of the polynomial in the FFT basis.
    /// Note: These are not the coefficients of the polynomial in the standard
    /// monomial basis. The FFT basis is a tensor product of the twiddles:
    /// y, x, pi(x), pi^2(x), ..., pi^{log_size-2}(x).
    /// pi(x) := 2x^2 - 1.
    pub coeffs: Col<B, BaseField>,
    /// The number of coefficients stored as `log2(len(coeffs))`.
    log_size: u32,
}
```

The `interpolate` function computes the coefficients with respect to the following basis:

$b^{(n)}_j(x, y) := y^{j_0} \cdot x^{j_1} \cdot \pi(x)^{j_2} \cdot \pi^2(x)^{j_3} \cdots \pi^{n-2}(x)^{j_{n-1}}$

where

* $\pi$ is the squaring map on the $x$-coordinate i.e. $\pi(x) = 2x^2 - 1$ and $\pi^i$ is applying the squaring map $i$ times, for example $\pi^2(x) = \pi(\pi(x))$
* $n$ is log of the size of the `CircleDomain`
* $0 \leq j \leq 2^n - 1$ and $(j_0, \ldots, j_{n-1}) \in \{0, 1\}^n$ is the binary representation of $j$, i.e., $j = j_0 + j_1 \cdot 2 + \cdots + j_{n-1} \cdot 2^{n-1}$

Thus the `interpolate` function computes coefficients $c_j$ for polynomials $p(x, y)$ of the form:

<span id="eq-circle-poly" />

$p(x, y) = \sum_{j=0}^{2^n-1} c_j \cdot y^{j_0} \cdot x^{j_1} \cdot \pi(x)^{j_2} \cdot \pi^2(x)^{j_3} \cdots \pi^{n-2}(x)^{j_{n-1}}$

This polynomial form and its underlying basis are implicit in the Circle FFT construction, as we will see in the next section. However, as discussed earlier, you can largely ignore these details and simply view a polynomial as a set of evaluations over a domain, with its coefficients computed via the FFT algorithm.

Now given the coefficient representation as `CirclePoly`, we can evaluate the polynomial over a given domain (i.e. compute the `CircleEvaluation`) using the following functions:

```rust theme={null}
    /// Evaluates the polynomial at all points in the domain.
    pub fn evaluate(
        &self,
        domain: CircleDomain,
    ) -> CircleEvaluation<B, BaseField, BitReversedOrder> {
        B::evaluate(self, domain, &B::precompute_twiddles(domain.half_coset))
    }

    /// Evaluates the polynomial at all points in the domain, using precomputed twiddles.
    pub fn evaluate_with_twiddles(
        &self,
        domain: CircleDomain,
        twiddles: &TwiddleTree<B>,
    ) -> CircleEvaluation<B, BaseField, BitReversedOrder> {
        B::evaluate(self, domain, twiddles)
    }
```

In the next section, we will see how the evaluations and polynomials are represented over the `SecureField`.