Basis for Circle FFT

The circle FFT algorithm outputs coefficients $c_j$ with respect to some basis $b_j^{(n)}(x,y)$ such that:

$$p(x,y)=\sum _{j=0}^{2^n-1}{c}_j\cdot b_j^{(n)}(x,y)$$

In the concrete example (covered in the Algorithm section) of Circle FFT over twin-coset $D_3$, we saw that the algorithm computed the coefficient with respect to the following basis:

$$b_j^{(3)}(x,y)=[1,x,\pi (x),x\cdot \pi (x),y,y\cdot x,y\cdot \pi (x),y\cdot x\cdot \pi (x)]$$

Using induction on $n$, we can show that the Circle FFT algorithm outputs coefficients with respect to the following basis [Theorem 2, Circle STARKs]:

$$b_j^{(n)}(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 $0\le j\le 2^n-1$ and $(j_0,\dots ,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}$$

Dimension Gap

We will now explore the space of polynomials interpolated by the Circle FFT algorithm. Let the space spanned by the basis polynomials in $b^{(n)}(x,y)$ be $L_N^{\prime }(F)$. The basis $b^{(n)}(x,y)$ has a total of $N=2^n$ elements and thus the dimension of the space $L_N^{\prime }(F)$ is $N$. However, the space of bivariate polynomials over the circle curve is $L_N(F)$, which has dimension $N+1$ (as covered in the section on polynomials over the circle).

We can identify the missing highest total degree element in $L_N^{\prime }(F)$ by examining the basis. The highest total degree element in basis $b^{(n)}(x,y)$ is: $$y\cdot x\cdot \pi (x)\cdot {\pi }^2(x)\cdot {\pi }^3(x)\cdots {\pi }^{n-2}(x)$$

Using $deg({\pi }^j(x)=2^j)$, the highest degree of $X$ in the above term is: $$1+2+2^2+2^3+\cdots +2^{n-2}=2^{n-1}-1=N/2-1$$

Since the highest degree of $X$ in $L_N^{\prime }(F)$ is $N/2-1$, we can represent the space $L_N^{\prime }(F)$ as follows:

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

where $F[x{]}^{\le N/2-1}$ represents polynomials of degree at most $N/2-1$ with coefficients in $F$. Similarly, we can represent the space $L_N(F)$ as:

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

Thus the space $L_N^{\prime }(F)$ does not include the monomial $X^{N/2}$, which lies in the space $L_N(F)$. Therefore,

$$L_N(F)=L_N^{\prime }(F)+⟨X^{N/2}⟩$$

Since the space spanned by $X^{N/2}$ is same as the space spanned by the vanishing polynomial $v_n(x)$ which has degree $deg(v_n)=2^{n-1}=N/2$, we can also write:

$$L_N(F)=L_N^{\prime }(F)+⟨v_n⟩$$

A consequence of this dimension gap is that we cannot interpolate some polynomials over the circle i.e. those with $X^{N/2}$. We will address how this dimension gap is handled within the FRI protocol in the upcoming sections.