Basic Definitions

In this section, we introduce the basic prerequisites for understanding the proofs in this book.

Essential Algebra

In this book, we will

An example of a ring, which is not an integral domain is $\mathbb{Z}/(2^k\mathbb{Z})$, since: $$2^{k-1}\cdot 2^{k-1}=0\mathrm{mod}{2}^k$$ Which means that $2^{k-1}$ is a zero divisor.

It is also easy to see that every field is an integral domain. Broadly speaking:

• The integral domain structure will be sufficient to argue soundness.
• Sometimes, not always, we will need the additional field structure to prove completness.

The relationship between these algebraic structures can be visualized as:

Other notions exist, which are more fine-grained than the distinction above, for instance, unique factorization domains (UFDs), principal ideal domains (PIDs), and Euclidean domains. But for the purposes of this book, only these three structures will be relevant.

Integral Domains

After showing this general theorem, we are going to immediately restrict ourselves a bit, but just a bit. Namely, we are going to require that $\mathcal{F}$ is an integral domain. An integral domain is a commutative ring which has no zero divisors, which is a fancy way of saying:

$$\forall a,b\in \mathcal{F}.a\cdot b=0⟹a=0\text{ or }b=0$$

In other words: the only way to get a zero product is to multiply by zero. Fields satisfy this, the integers $\mathbb{Z}$ satisfy this, however, e.g. ${\mathbb{Z}}_{2^{32}}$ does not satisfy this:

$$2^{16}\cdot 2^{16}=2^{32}=0\mathrm{mod}{2}^{32}$$

The fact that $\mathcal{F}$ is an integral domain is important, because it allows us to conclude that if we have a product of polynomials $f(X)=f_1(X)\cdot f_2(X)$ and a point $x\in \mathcal{F}$ such that $f(x)=0$, then either $f_1(x)=0$ or $f_2(x)=0$. Combined with the factor theorem, this allows us to upper bound the number of roots of any polynomial $f(X)$ by the degree of $f(X)$.

Tensor Products & Hypercubes

The "Boolean Hypercube" is a tensor product, i.e. "all vectors with entries from", the set $\{0,1\}$:

$$\begin{array}{rl}{\mathbb{H}}_k& ={\{0,1\}}^k\subseteq {\mathbb{F}}^k\\ & =\{(x_1,\dots ,x_k)\mid x_1,\dots ,x_k\in \{0,1\}\}\end{array}$$

For instance:

$${\mathbb{H}}_2={\{0,1\}}^2=\left\{(0,0),(0,1),(1,0),(1,1)\right\}$$

It is clear that the $k$-dimensional Boolean hypercube has $2^k$ elements: $|{\mathbb{H}}_k|=2^k$. In many ways, the choice of $\{0,1\}$ is arbitrary, another popular choice is $\left\{-1,1\right\}$ which has the slight advantage that it is a group under multiplication, making some things slightly nicer.

The most important part about ${\mathbb{H}}_k$ is not the particular sets $\{0,1\}$ or $\left\{-1,1\right\}$, nor that every coordinate is from the same set, but the tensor structure, in the most general case: $$\begin{array}{rl}{\mathbb{H}}_k& =S_1\otimes S_2\otimes \dots \otimes S_k\\ & =\left\{(x_1,\dots ,x_k)\mid x_1\in S_1,\dots ,x_k\in S_k\right\}\end{array}$$ for small sets $S_1,\dots ,S_k$ in which case: $$|{\mathbb{H}}_k|=|S_1|\cdot |S_2|\cdot \dots \cdot |S_k|$$ However, most naturally $\forall i.|S_i|=2$, hence the name "Boolean hypercube".

Multivariate Polynomials

A multivariate polynomial is, as the name suggests, simply a polynomial in one or more variables.

For instance:

• $f(X_1,X_2)=X_1^2+X_2^2+X_1{X}_2+1$
  Is a multivariate polynomial of individual degrees $2$ and $2$ in the variables $X_1$ and $X_2$.
• $f(X_1,X_2)=X_1^2+X_2^2+X_1{X}_2+X_1{X}_2^3+1$
  Is a multivariate polynomial of individual degrees $2$ and $3$ in the variables $X_1$ and $X_2$.
• $f(X_1)=5\cdot X_1^6+3\cdot X_1^4+2\cdot X_1^2+1$
  Is a multivariate polynomial of individual degree $6$ in the variable $X_1$.

• $f(X_1,X_2)=8\cdot X_1{X}_2+5\cdot X_1+X_2$
• $f(X_1)=5\cdot X_1+37$

While all the earlier examples of multivariate polynomials were not multilinear polynomials.