Lesson 1

Consider the following polynomial: \[\begin{align*}P(x, y, z)&= \prod_{i = 1}^{n}\left( (\pi - \omega^{i}\hbar)\ x + e\ y - \omega^{i}\pi e\ z \right) + \\&+\prod_{i = 1}^{n}\left( (\hbar - \omega^{i}e)\ x + \omega^{i}\pi\ y + (\pi e - \omega^{i}\hbar)\ z \right) +\\&+\prod_{i = 1}^{n}\left( (e - \omega^{i}\pi)\ x - (\pi + \omega^{i}e)\ y + \hbar\ z \right),\end{align*}\] where \(\omega^{n}= 1\) and \(\hbar\) denotes Planck's constant. Is it equal to zero? In other words, does it evaluate to zero on all input points? One possibility to check this is to try to expand this as a sum of monomials, but this will take exponential time. A simpler example is: an expansion of \((1+x_{1})(1+x_{2})\dotsb(1+x_{n})\) has \(2^{n}\) terms.

The question above is a special case of the following computational problem known as polynomial identity testing (commonly abbreviated as PIT): given a multivariate polynomial \(P(x_{1}, x_{2}, \dotsc, x_{n})\) over a field \(\mathbb{F}\), is \(P\) the zero polynomial (i.e., does \(P(x_{1}, \dotsc, x_{n}) = 0\), for all \(x_{1}, \dotsc, x_{n} \in \mathbb{F}\))? It is straightforward to perform a check if \(P\) is specified by a list of its monomials, but, as the example above shows, this is not always the case. In general, it is common to assume that a polynomial is given as an arithmetic circuit (it roughly corresponds to a simple program that computes the polynomial step-by-step using summations and multiplications).

Designing an efficient deterministic algorithm for PIT is a challenging open problem. At the same time, PIT can be solved by an efficient randomized algorithm! The algorithm is surprisingly simple: evaluate the polynomial at a random point and report “non-zero” if the resulting value is non-zero. If, on the other hand, the result is zero, there are two cases: either the polynomial is zero or the polynomial is non-zero, but we hit its root. Below, we estimate the probability of hitting a root of a non-zero polynomial.