Skip to main content

​
Basis for Circle FFT

The circle FFT algorithm outputs coefficients cjc_j with respect to some basis bj(n)(x,y)b_j^{(n)}(x, y) such that: p(x,y)=∑j=02n−1cj⋅bj(n)(x,y)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 D3D_3, we saw that the algorithm computed the coefficient with respect to the following basis: bj(3)(x,y)=[1,x,π(x),x⋅π(x),y,y⋅x,y⋅π(x),y⋅x⋅π(x)]b^{(3)}_j(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 nn, we can show that the Circle FFT algorithm outputs coefficients with respect to the following basis [Theorem 2, Circle STARKs]: bj(n)(x,y):=yj0⋅xj1⋅π(x)j2⋅π2(x)j3⋯πn−2(x)jn−1b^{(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 0≤j≤2n−10 \leq j \leq 2^n - 1 and (j0,…,jn−1)∈{0,1}n(j_0, \ldots, j_{n-1}) \in \{0, 1\}^n is the binary representation of jj, i.e., j=j0+j1⋅2+⋯+jn−1⋅2n−1j = 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)b^{(n)}(x, y) be LN′(F)L'_N(F). The basis b(n)(x,y)b^{(n)}(x, y) has a total of N=2nN=2^n elements and thus the dimension of the space LN′(F)L'_N(F) is NN. However, the space of bivariate polynomials over the circle curve is LN(F)L_N(F), which has dimension N+1N+1 (as covered in the section on polynomials over the circle). We can identify the missing highest total degree element in LN′(F)L'_N(F) by examining the basis. The highest total degree element in basis b(n)(x,y)b^{(n)}(x, y) is: y⋅x⋅π(x)⋅π2(x)⋅π3(x)⋯πn−2(x)y \cdot x \cdot \pi(x) \cdot \pi^2(x) \cdot \pi^3(x) \cdots \pi^{n-2}(x) Using deg(πj(x)=2j)deg(\pi^j(x) = 2^j), the highest degree of XX in the above term is: 1+2+22+23+⋯+2n−2=2n−1−1=N/2−11 + 2 + 2^2 + 2^3 + \cdots + 2^{n-2} = 2^{n-1} - 1 = N/2 - 1 Since the highest degree of XX in LN′(F)L'_N(F) is N/2−1N/2 - 1, we can represent the space LN′(F)L'_N(F) as follows: LN′(F)=F[x]≤N/2−1+Y⋅F[x]≤N/2−1L'_N(F) = F[x]^{ \leq N/2 - 1} + Y \cdot F[x]^{ \leq N/2 - 1} where F[x]≤N/2−1F[x]^{ \leq N/2 - 1} represents polynomials of degree at most N/2−1N/2 - 1 with coefficients in FF. Similarly, we can represent the space LN(F)L_N(F) as: LN(F)=F[x]≤N/2+Y⋅F[x]≤N/2−1L_N(F) = F[x]^{ \leq N/2} + Y \cdot F[x]^{ \leq N/2 - 1} Thus the space LN′(F)L'_N(F) does not include the monomial XN/2X^{N/2}, which lies in the space LN(F)L_N(F). Therefore, LN(F)=LN′(F)+⟨XN/2⟩L_N(F) = L'_N(F) + \langle X^{N/2} \rangle Since the space spanned by XN/2X^{N/2} is same as the space spanned by the vanishing polynomial vn(x)v_n(x) which has degree deg(vn)=2n−1=N/2deg(v_n) = 2^{n-1} =N/2, we can also write: LN(F)=LN′(F)+⟨vn⟩L_N(F) = L'_N(F) + \langle v_n \rangle A consequence of this dimension gap is that we cannot interpolate some polynomials over the circle i.e. those with XN/2X^{N/2}. We will address how this dimension gap is handled within the FRI protocol in the upcoming sections.