# DEEP-FRING (DEEP-FRI over Rings)

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

• Commutative
• Not integral
• Noetherian

Note. We need an integral domain in order to have the common rules on degree of the polynomial: https://en.wikipedia.org/wiki/Degree_of_a_polynomial#Behavior_under_polynomial_operations

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)$).

## 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.

https://en.wikipedia.org/wiki/Unique_factorization_domain

https://en.wikipedia.org/wiki/Polynomial_ring#Factorization_in_K[X]

## FFT+FRI

https://users.cs.duke.edu/~reif/courses/alglectures/reif.lectures/ALG3.2.pdf

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

https://hal.inria.fr/hal-00670004v2/document

## 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.:

• $+$ is closed $a + b \in \mathbb R$
• $+$ is commutative $a + b = b + a$
• $+$ is associative $(a + b) + c = a + (b + c)$
• $0$ is an additive identity $a + 0 = a$
• additive inverses $a + (-a) = 0$
• Monoid under multiplication
• $⋅$ is closed $a ⋅ b \in \mathbb R$
• $⋅$ is commutative $a ⋅ b = b ⋅ a$
• $⋅$ is associative $(a ⋅ b) ⋅ c = a ⋅ (b ⋅ c)$
• $1$ is a multiplicative identity $a ⋅ 1 = a$
• Multiplication is distributive over addition
• distributivity

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.

https://en.wikipedia.org/wiki/Root_of_unity_modulo_n

https://en.wikipedia.org/wiki/Root_of_unity_modulo_n#Finding_an_n_with_a_primitive_k-th_root_of_unity_modulo_n

Remco Bloemen
Math & Engineering
https://2π.com