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

## Roots of unity

## Schwartz-Zippel

https://mathoverflow.net/questions/186074/can-schwartz-zippel-be-formulated-for-commutative-rings-instead-of-fields

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

- Abelian group under addition.
- $+$ 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