Goal. Generalize FRI, Schwartz-Zippel and FFT to a commutative ring of the form $R = \mathbb Z/m \mathbb Z$ where $m = 2^b ⋅ k$ or something similar.

We want this to be able to construct a $2^{64}$ sub-ring that captures the behaviour of binary numbers without much fuzz.

We can tweak $k$ to guarantee the existence of roots of unity of order $2^r$, which will power FRI and FFT.

The ring $R$ is

Consequently, the ring of polynomials over it, $R[X]$ is

Note. We need an integral domain in order to have the common rules on degree of the polynomial:

To do. It does seem that this only reduces the degrees of the polynomials, and potentially only with neglible probability. So much of the theory can be salvaged. (i.e. $\deg (PQ) \leq (\deg P)(\deg Q)$).

Roots of unity


Unique factorization

For some theorems we need Polynomials to have a unique factorization into irreducible factors (i.e. in Plonk's multi-set check). This requires the field to be a unique factorization domain, but it isn't. In fact, it is not even an integral ring.[X]


FFT Seems to not be an issue as long as the roots of unity exist. FRI will follow the same path.

Reed-solomon over Rings

Commutative rings

A commutative ring is a set $\mathbb R$ with two binary operations $+$ and $⋅$ and two elements $0, 1 \in \mathbb R$ s.t.:

Q: Additive inverses unique? Q: Multiplicative inverses unique?

Definition. (Additive inverse). $-a$. By the axioms these always exist.

Definition. (Multiplicative inverse). $a^{-1}$. These do not necessarily exist.

Definition. (Unit). If $a$ has an inverse, it is called a unit.

Definition. (Zero divisor). If $a$ has an element $b$ such that $ab = 0$, it is called a zero divisor.

Definition. (Nilpotent). If $a$ has a positive number $n$ such that $a^n = 0$, it is called nilpotent.

Lemma. If $a$ is nilpotent then $1-a$ is a unit.

Remco Bloemen
Math & Engineering