Consider a polynomial $f(x)$ over a finite-field $\mathbb{F}_q$ defined by its evaluations $f_i = f(\omega^i)$, where $\omega$ is the $n$-th root of unity of $A(x) = x^n - 1 = 0$. The Lagrange interpolation of $f(x)$ based on Barycentric formula is
$$ A'(x) = nx^{n-1} $$
$$ \begin{align} f(x) & = A(x)\sum_{i=0}^{n-1} \frac{f(\omega^i)}{A'(\omega^i)} \frac{1}{x - \omega^i} \\ & = \frac{x^n - 1}{n} \sum_{i=0}^{n-1} \frac{f_i }{\omega^{i(n-1)}(x - \omega^i)} \\ & = \frac{x^n - 1}{n} \sum_{i=0}^{n-1} \frac{f_i \omega^i}{x - \omega^i} \end{align} $$
Now given $m = 2^l \leq n$, we want to check that the degree of $f(x)$ is less than $m$.
Suppose $\omega_i$ ‘s are the roots of unity ordered by reverse bit order. E.g., if $n = 8$, then $[ \omega_0, ..., \omega_7] = [\omega^0, \omega^4, \omega^2, \omega^6, \omega^1, \omega^5, \omega^3, \omega^7]$. Further, let us define $y_i = f(\omega_i)$, which is the reverse-bit ordered version of $f_i$. Then, we define $\Omega = \{\omega_0, …, \omega_{m-1}\}$, and the coset $H_i = h_i \Omega$ with $h_i = \omega^i$ . For each coset $H_i$, we have
$$ B_i(x) = \prod_{x_i \in H_i} (x - x_i) = x^m-h_i^{m} $$
$$ B_i'(x) = mx^{m-1} $$
$$ \begin{align} f_i(x)& =B_i(x)\sum_{j = i m}^{(i+1)m - 1} \frac{f(\omega_j)}{B'i(\omega_j)}\frac{1}{x-\omega_j} \\ & = \frac{x^m - h_i^m}{m } \sum{j=im}^{(i+1)m - 1} \frac{y_j}{\omega_j^{m-1}(x - \omega_j)} \\ & = \frac{x^m - h_i^m}{m h_i^m} \sum_{j=im}^{(i+1)m - 1} \frac{y_j \omega_j}{x - \omega_j} \end{align} $$
To check if $f(x)$’s degree is less than $m$, we sample a random point $r$ and verify that
$$ \begin{align} f_i(r) = f_j(r), \forall i,j \end{align} $$
Note that if $m = n/2$, the check will be exactly the same as Dankrad’s.
See Dankrad's Notes and https://github.com/ethereum/research/pull/138
The FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) aims to provide a proof of a close low degree of a polynomial $f(x)$ given its evaluations $f_i$ over roots of unity $\omega^i$ (see https://vitalikblog.w3eth.io/general/2017/11/22/starks_part_2.html and https://vitalikblog.w3eth.io/general/2018/07/21/starks_part_3.html). The basic idea is to re-interpret $f(x) = q(x, x^m)$, where $m$ is a power of 2 (commonly use $m = 4$) and $q(x, y)$ is a 2D polynomial, whose degree in $x$ is less than $m$, and degree in $y$ is less than $\frac{deg(f(x))}{m}$ . If $deg(f(x))$ is less than $N$, then $f'(y) = q(r, y)$ will have degree $< \frac{N}{m}$, where $r$ is a random evaluation point. Therefore, we just need to verify the degree of $f'(y)$, which can be further done recursively. To build $f'(y)$, we have the following proposition:
Proposition: Given reversed ordered n-th roots of unity $\omega_i$, $i = 0, …, n-1$, and the evaluations $y_i = f(\omega_i)$, the reversed ordered $\frac{n}{m}$th roots of unity $\phi_i = \omega^{m}_{im}$, $i = 0, …, \frac{n}{m}-1$ , and the evaluations of $y'_i = f'(\phi_i) = f_i(r)$.
Proof: It is trivial to prove $\phi_i = \omega^{m}_{im}$. For $y'_i$, we have