Efficient patterns of zeros of certain polynomials


In STARKs the computation is unrolled into a table:


Think of the columns as registers and the rows as sequential states in the computation.

The columns in table are interpreted as polynomials evaluated on powers of a root of unity $\omega$.

Constraints are now expressed as rational functions. Consider the constraint that $P_2$ is the sum of previous $P_1$ and $P_2$ (Fibonacci constraint):

$$ \frac{ P_2(\omega\cdot x) - P_1(x) - P_2(x) }{ (x^n - 1)/(x - \omega^{n-1}) } $$

The numerator is an expression that is zero whenever the constraint holds between two rows. The denominator is zero whenever the constraint should hold. The division is exact only when the trace table is valid.

In STARKs, the verifier needs to evaluate the constraints once, given values of $P_i$. For an efficient proof system, this the expression should be evaluable in complexity at most logarithmic in $n$.

The above can be evaluated in $O(\log n)$ using binary exponentiation.


Consider a large prime field $\mathbb{F}_p$ with a $n = 2^k$ order root of unity $\omega$. That is, $\omega^n = 1$.

We are interested in constructing efficient polynomials which have their zeros at certain powers of this root. Efficient here means it can be evaluated in $O(\log(n))$ given arbitrary preprocessing.

Which patterns of zeros can be efficiently computed?

Positive examples


Open questions

Is there an efficient evaluation of the polynomial that is zero at $\omega^0, \dots, \omega^{n/2}$, i.e. only the first half of the table.

What about arbitrary ranges?

Prelimiary results

Appendix: why is this field interesting

Arithmetic circuits are a generalization of boolean circuits. Finite fields offer richter math than booleans and some researcher believe this has opertunities for solving hard complexity theory problems.

I also believe the results in the field are not as widely known as they should be, for example, many people believe Horner's evaluation is optimal. Given a polynomial

$$ P(x) = c_0 + c_1 x^1 + c_2 x^2 + \cdots + c_n x^n $$

Horner's schema allows this to be evaluated using $n$ multiplications and $n$ additions:

$$ \begin{align} p_0 &= 1 \\ p_{i+1} &= p_{i} \cdot x + c_{n-i} \\ P(x) &= p_n \end{align} $$

Which takes $n$ multiplications. But Rabin-Winograd (1972) showed that any polynomial can be evaluated in $\frac{n}{2} + \log n$ multiplications. In the following, assume $n = 255$. The method generalizes for arbitrary degree in the paper.

We first turn $P$ monic by dividing by the leading term, in the end we will multiply by it again:

$$ c'_i = \frac{c_i}{c_n} $$

$$ P(x) = c_n (c'_0 + c'_1 \cdot x + c'_2 \cdot x^2 + \dots + x^n) $$

Now we pick $i = \frac{n + 1}{2} = 128$ and split the polynomial in two:

$$ P(x) = Q(x) \cdot (x^{128} + a) + R(x) $$

Where $Q$ and $R$ are monic with degree $127$. The coefficients of $Q$ are simply $c'_{129}, \dots, c'_{255}$. The value of $a$ is $c_{128} - 1$. From this we can compute the coefficients of $R$, they are $r_i = c'_i - c \cdot q_i$ and $r_{127} = 1$.

We apply this splitting recursively untill we are left with many monic polynomials of degree 3: $S(x) = s_0 + s_1 x + s_2 x^2 + x^3$. These are computed using:

$$ S(x) = (x^2 + s_1) \cdot (x + s_2) + b $$

where $b$ is $s_0 - s_1 s_2$. All in all, the method requires about $n/2$ multiplications, about half of Horners method. To this we need to add the $\log n$ squarings required to get the required powers of $x$.

With $N$ a power of two:

$$ P(X) = (X - \omega_N^0) (X - \omega_N^1) \cdots (X - \omega_N^{N/2}) $$

$$ P(X) = (X - 1) (X - \omega_N)(X - \omega_N^2) \cdots (X + 1) $$

Conjecture. In $\mathbb C$ the coefficients of $P$ alternate between real multiples of $\omega_4^0, \omega_4^1, \omega_4^2, \omega_4^3$.

Conjecture. Furthermore, the scalar factors are symmetric in the sens that $c_i = c_{N/2 - i}$.

Conjecture. Furthermore, the scalar factors follow a bell curve.

To do. Propose concrete formula for coefficients.

To do. This seems to generalize to composite $N$.

Symmetries: Take $P(X)$ to be the polynomial with zeros on $\omega_N^0, \dots \omega_N^{N/2}$. It should have the following symmetries based on observations of patterns of roots:







To do. Try decomposition methods. Observe that $X^{2^k}-1 = (X^2 -1) \circ (X^2) \circ \cdots \circ (X^2)$. The rhs can be evaluated in $O(k)$ operations.



Does not seem to work for small examples: https://www.wolframalpha.com/input/?i=Decompose%5B%28x-i%29%28x-1%29%28x%2B1%29%2C+x%5D even though $X^4-1$ works https://www.wolframalpha.com/input/?i=Decompose%5B%28x-i%29%28x-1%29%28x%2B1%29%28x%2Bi%29%2C+x%5D


$$ \begin{aligned} P(z) &= \sum_i a_i ⋅ L_i(z) \\&= \sum_i a_i ⋅ \frac{𝜔^i}{n} \frac{z^n - 1}{z - 𝜔^i} \\&= \frac{z^n - 1}{n} \sum_i \frac{a_i ⋅ 𝜔^i}{z - 𝜔^i} \end{aligned} $$

where $a_i = \begin{cases} 0 & i \le N/2 \\ \ne 0 & otherwise \end{cases}$.

$$ \frac{z^n - 1}{n} \sum_{i \in (N/2, N)} \frac{a_i \cdot 𝜔^i}{z - 𝜔^i} $$

This reduces the problem to computing the sum in $\log N$ time, plus we are allowed to multiply each term of the sum by a nonzero factor of our choosing. First of, let's absorb the other factors in $a_i$:

$$ (z^n - 1) \sum_{i \in (N/2, N)} \frac{a_i}{z - 𝜔^i} $$

The integral related to the sum seems solvable: https://www.wolframalpha.com/input/?i=Integrate%5B1%2F%28a-b%5Ex%29%2C+x%5D

The series seems related to the digamma function: https://en.wikipedia.org/wiki/Digamma_function#Evaluation_of_sums_of_rational_functions http://mathworld.wolfram.com/q-PolygammaFunction.html

There is potentially a closed form solution, at least for complex numbers:



Remco Bloemen
Math & Engineering