In Part I, we set the stage and discussed the recursive structure of the sum-check protocol. In this post, we start introducing the mathematical tooling needed to formalize sum-check as an algebraic tensor reduction. Establishing the necessary fundamentals will take some time (and several posts), but it’ll be worth it. Pinky promise.

Also, you don’t necessarily need to memorize every definition and example. Instead, the main goal of the next few posts is to give you solid reference material you can keep open on a second monitor while reading the later parts of this series. That way, you’ll be able to focus on the main arguments instead of constantly getting stuck mid-sentence because of unfamiliar math terminology.

I assume the reader is familiar with standard lingo from set theory and linear algebra. Therefore, we won’t introduce notions such as subsets, Cartesian products, groups, fields, or vector spaces, as these can be found on the first pages of any linear algebra lecture, and the average reader is likely familiar with them. Instead, we’ll focus our attention on mathematical objects and operations that are a bit less common in the cryptography literature. In particular, we’ll introduce $R$-modules, direct sums, tensor products, etc. And don’t you worry — it’ll be less scary than it sounds. We’ll provide plenty of examples and intuition along the way.

The reason we need this extra language is that, in the sum-check setting, we quickly move beyond plain vector spaces over fields. For example, a polynomial ring such as $R[X]$ can be viewed both as a ring in its own right and as an $R$-module: we can add polynomials and multiply them by scalars from $R$, even though the polynomials themselves also have their own multiplication.

This distinction becomes important later when we describe sum-check as a sequence of algebraic reductions. Some operations use the ring structure of polynomials, while others only use the fact that certain collections of objects form modules over a base ring. Having the terminology in place lets us say precisely which structure is being used at each step.

Without further ado, let’s kick things off by introducing rings and modules!

Rings

Definition

A ring is a set $R$ together with two binary operations $+$ and $\cdot$ over $R$ that satisfy the following conditions:

1. $(R,+)$ is a commutative group.

2. For all $a,b,c\in R$, we have that $(a\cdot b)\cdot c =a\cdot (b\cdot c)$.

3. For all $a,b,c\in R$, we have that $(a+b)\cdot c=(a\cdot c)+(b\cdot c)$ and $a\cdot (b+c)= (a\cdot b)+(a\cdot c)$.

A ring $R$ is called commutative if $a\cdot b=b\cdot a$ for all $a,b\in R$. A ring $R$ is called unital (or ring with identity) if it contains a multiplicative identity element (denoted $1$) such that $1\cdot a=a\cdot 1=a$ for all $a\in R$.

Examples

1. Any field is a commutative, unital ring. In particular, the real numbers $\mathbb{R}$, the complex numbers $\mathbb{C}$, and the prime fields $\mathbb{F_p}:=\mathbb{Z}/p\mathbb{Z}$ are all examples of commutative, unital rings.

2. The set of integers $\mathbb{Z}$ forms a commutative, unital ring.

3. The set $R[x_1,...,x_n]$ of polynomials in $n$ variables with coefficients in $R$ forms a commutative, unital ring if and only if $R$ is a commutative, unital ring. In particular, if $R$ is a field, then $\mathbb{}$$R[x_1,...,x_n]$ is a commutative, unital ring.

4. The set $\mathcal{M}_n(\mathbb{F})$ of $n\times n$- matrices with entries in a field $\mathbb{F}$ forms a unital ring with the identity matrix as its multiplicative identity element. However, the ring $\mathcal{M}_n(\mathbb{F})$ is not a commutative ring because, in general, $A\cdot B\neq B\cdot A$ for two matrices $A,B\in\mathcal{M}_n(\mathbb{F})$.

5. The set $2\mathbb{Z}:= \{...,-4,-2,0,2,4,...\}$ of even integers forms a commutative ring. However, the ring $2\mathbb{Z}$ is not a unital ring because the multiplicative identity element $1$ for the usual integer multiplication is not an element of $2\mathbb{Z}$.

6. The set $$ \Delta:=\left\{\begin{bmatrix}0&a&b\\ 0&0&c\\ 0&0&0\end{bmatrix}:a,b,c\in \mathbb{F}\right\} $$ of strictly upper-triangular $3\times 3$-matrices over a field $\mathbb{F}$ forms a ring that is not commutative (because matrix multiplication does not commute) and not unital (because $\Delta$ does not contain the identity matrix).

7. The set of non-negative integers $\mathbb{N}_0:=\{0,1,2,...\}$ does not form a ring. That’s because it lacks additive inverses for all elements except $0$, so that $(\mathbb{N}_0,+)$ is not a group, so that the first condition of our ring definition is violated. (Instead, $\mathbb{N}_0$ forms what’s called a semiring.)

Intuition

In this blog post series, rings will mainly appear as coefficient domains and polynomial rings. For example, if $R$ is our base ring, then $R[x_1,\ldots,x_n]$ is the ring of polynomials with coefficients in $R$. Generally, the rings one usually encounters in cryptography are both commutative and unital. Accordingly, from this point on, we will use the term “ring” to mean “commutative, unital ring.”

With this nomenclature, the only difference between the definitions of a ring and a field is that every element in a field (except $0$) has a multiplicative inverse, while that is not required for every element of a ring.

For instance, every element $x$ (except $0$) of the field of real numbers $\mathbb{R}$ has a multiplicative inverse, given by $x^{-1}:=1/x\in \mathbb{R}$. However, that is not true for (almost all) elements in the ring $\mathbb{Z}$. In $\mathbb{Z}$, only the elements $1$ and $-1$ have a multiplicative inverse (namely $1^{-1}:=1$ and $(-1)^{-1}:=-1$). All other elements of $\mathbb{Z}$ lack a multiplicative inverse since fractions of integers are, in general, not contained in $\mathbb{Z}$.

Modules

Definition

Consider a ring $R$. An $R$-module is a set $M$ together with binary operations $+:M\times M\to M$ and $\cdot :R\times M\to M$ that satisfy the following conditions:

1. $(M,+)$ is a commutative group.

2. For all $r,s\in R$ and $m,n\in M$, we have that $(r+s)\cdot m=r\cdot m+s\cdot m$ and $r\cdot (m+n)=r\cdot m+r\cdot n$.

3. For all $r,s\in R$ and $m\in M$, we have that $(r\cdot s)\cdot m=r\cdot (s\cdot m)$.

4. For all $m\in M$, we have that $1\cdot m=m$, where $1\in R$ denotes the multiplicative identity element of $R$.

The binary operations $+$ and $\cdot$ are referred to as addition and scalar multiplication, respectively.

Examples

1. Any vector space over a field is a module over that field. In particular, the vector space $\mathbb{R}^n$ is an $\mathbb{R}$-module. Similarly, $\mathbb{C}^n$ defines a $\mathbb{C}$-module, and $\mathbb{F}_p^n$ defines an $\mathbb{F}_p$-module.

2. Every ring $R$ is an $R$-module, where the module’s addition is given by the ring’s addition, and scalar multiplication is given by the ring’s multiplication.

3. More generally, for a ring $R$ and any integer $n\geq1$, the Cartesian product $R^n=R\times \cdots\times R$ ($n$ times) is an $R$-module, where addition and scalar multiplication are defined component wise: $$ (r_1,...,r_n)+(s_1,...,s_n):=(r_1+s_1,...,r_n+s_n) $$ and $$ a\cdot (r_1,...,r_n):=(ar_1,...,ar_n), $$ where $a,r_i,s_i\in R$ with $i\in \{1,...,n\}$. Also, notice that we explicitly write the $\cdot$ when referring to the scalar multiplication of the module on the left-hand side, while we omit a multiplication symbol when referring to the multiplication of the ring (i.e., we write $ar_i$ instead of $a\cdot r_i$) on the right-hand side of the definition.

4. For a ring $R$, the polynomial ring $R[x_1,...,x_n]$ is an $R$-module, where two polynomials are added in the usual way and scalar multiplication by an element $r\in R$ means multiplying every coefficient of the polynomial by $r$.

5. For a ring $R$, the set $\mathcal{M}_{m\times n}(R)$ of $m\times n$-matrices with entries in $R$ is an $R$-module, where addition and scalar multiplication are defined entrywise. Notice that this scalar multiplication should not be confused with matrix multiplication. Indeed, matrix multiplication is a binary operation, but not in the sense of our module definition. In fact, matrix multiplication is not even defined on $\mathcal{M}_{m\times n}(R)$ if $m\neq n$, since matrix multiplication requires the number of columns of the first factor to equal the number of rows of the second factor.

Intuition

A module is to a ring what a vector space is to a field. In other words, modules are a generalization of vector spaces obtained by allowing scalars to come from a ring instead of a field. If the ring $R$ happens to be a field, then an $R$-module is exactly the same thing as a vector space over $R$.

So why care about modules at all? Because many objects that are very common in mathematics are closed under multiplication by ring elements, but not by arbitrary field elements. Consider $\mathbb{Z}^n$, for example: $\mathbb{Z}^n$ is naturally a $\mathbb{Z}$-module (see Example 3. above), but it is not a vector space over $\mathbb{Z}$, since $\mathbb{Z}$ is not a field.

The main intuition you should keep in mind is that “a module is a vector space where the scalars come from a ring instead of a field.” The key difference is that in a field, every non-zero scalar is invertible, whereas in a ring, this doesn’t have to be the case. This “small” difference has an important consequence: In a vector space, scalar multiplication by a non-zero scalar can always be undone by multiplying with its inverse. That is no longer true in a general module. For instance, in the $\mathbb{Z}$-module $\mathbb{Z}$, multiplying by $2$ sends $x\in \mathbb{Z}$ to $2x\in \mathbb{Z}$, but there is no integer scalar that reverses this operation, since $\frac{1}{2}\notin\mathbb{Z}$.

Now that we’ve built some basic intuition about rings and modules, we’re ready to tackle morphisms between modules in the next post. Stay tuned!

Acknowledgements

Special thanks to Jason Park, Yoichi Hirai, Varun Thakore, 0xteddav, 0xStrapontin, Khaled Suliman, and Youssef23 for taking the time to help me polish this post.