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
