Algebraic Circuits

My tutor gave me a paper of hers to read. It is Cylotomic Identity Testing. I spent an afternoon filling out some of the stuff for the first three sections, to try and understand it, instead of studying for my collections, lol.

The exposition is below. Wherein the author attempts to explain everything, line by line by line by line.

Also note that there are rendering errors. In general I don’t like doing math on websites, so I have to get around to fixing how its rendered.

What’s the Problem?

In general, we care a lot about root-finding algorithms, because this let’s us solve minimization problems. Someone asked me once what the impact of this research is and I almost wanted to joke about that and say “this is great for solving loss for LLMs!” I’m not that stupid.

This is a root-verification problem, specifically for polynomials $f \in \mathbb{Z}[x].$ We want to know, given some input of the form $\alpha$, if $f(\alpha) = 0$. That’s it. There is not much else to it. However, for our sakes, we are only considering $\alpha$’s of a certain form, specifically those arising from cyclotomic integers.

We utilize the notion of algebraic integers to describe a class of solutions to the above polynomial. Note it’s not all of them, and I talk about this more in the next section. But ultimately, we describe algebraic integers as these elements that can be described algebraically, more specifically, as roots of monic integer coefficient polynomials.

This exposition will assume only two major results. I will leave one a secret for now, but the main one is that the ring of integers of a cyclotomic field is the integers adjoined to that root of unity, which we denote as $\zeta_n$. This may not yet make sense.

But ultimately, what it means is $\alpha$ is expressible as some $\mathbb{Z}$-linear combination of roots of unity. So, what we really have is some $f(g(\zeta_n))$, where $f \circ g \in \mathbb{Z}[x]$. So, our problem is fundamentally about checking if for some polynomial $f$ if it has the root $\zeta_n$.

That’s it. Now I explain all of this.

Primer on Algebraic Number Theory

Note we are specifically focused on one specific type of number field, but I’ll start out with the general truths.

Algebraic Numbers and Integers

We say that $\alpha \in \mathbb{C}$ is an algebraic number if it is the root of some nonzero polynomial in $\mathbb{Q}[x].$ Then, we say that the minimal polynomial of said $\alpha$ is a monic polynomial in $\mathbb{Q}[x]$ of minimal degree.

We have to show this is unique and that it has the property of irreducibility.

lemma. Let $\alpha$ be an algebraic number. Then, the minimal polynomial is unique and it coincides with the unique monic irreducible polynomial with root $\alpha$.

Proof. Let $\alpha$ be algebraic, and let $f$ be its minimal polynomial. Say that $g \in \mathbb{Q}[x]$ such that $g(\alpha) = 0$. Then $\deg(f) \leq \deg(g)$, so we can use the Euclidean Division Algorithm (as $\mathbb{Q}$ is a field) to find polynomials $q, r \in \mathbb{Q}[x]$ such that $g = qf + r$ and $\deg(r) < \deg (f)$. If $r$ is not the nonzero polynomial, note that $r(\alpha) = 0$. However, by the degree being smaller, we have a contradiction.

What this tells is that for all polynomials with $\alpha$ as a root, $f$ divides them. As $f$ is monic, this fixes it as the unique such polynomial. So, we have shown uniqueness.

Say $f$ is not irreducible, then we can write $f = gh$ for some $g, h \in \mathbb{Q}[x]$ and $g, h$ nonconstant. However, as $\mathbb{Q}[x]$ is an integral domain, as $\mathbb{Q}$ is a field, must have $\alpha$ as a root of $g$ or $h$, but $g$ and $h$ both have smaller degree than $f$. So, we have a contradiction.

This means that $f$ is irreducible. □

We say that the degree of an algebraic number is the degree of its minimal polynomial, and that the height is the largest absolute value of the coefficents of the minimal polynomial. These aren’t actually that important to understand for the sake of the paper, but are good to know.

Also, note from the definition that it is nonobvious that the set of algebraic numbers forms any sort of structure. In fact, it forms a field.

thm. The set of algebraic numbers forms a field.

Proof. Note that we have $0, 1$ as we consider the polynomials $x, x-1$.

Let $\alpha$ be an algebraic number. Let $f$ be it’s minimal polynomial. Note that $-\alpha$ is a root of $f(-x)$, and that $f(-x) \in \mathbb{Q}[x]$, so we have additive inverses.

Also note that $\alpha^{-1}$ is a root of $x^{\deg(f)}f(x^{-1}) \in \mathbb{Q}[x]$, so we have multiplicative inverses.

All that is left to show is that addition and multiplication is well defined. Let $\alpha, \beta$ be two algebraic numbers, with minimal polynomials $\alpha, \beta$ respectively. Consider the vector space $V$ spanned by $\left\langle\alpha^i\beta^j \mid i, j \in \mathbb{N}\right\rangle$ over $\mathbb{Q}$. This is spanned by at most $(\deg(f)-1)(\deg(g)-1)$ elements. Let $e_1, \ldots, e_n$ be basis vectors of $V$

Say we have $x$ such that $xV \subseteq V$. This means that we have the system of equations:

\begin{aligned} xe_1& = a_{1, 1}e_1 + \ldots + a_{1, n} e_n \end{aligned}

\begin{aligned} \vdots \end{aligned}

\begin{aligned} xe_n& = a_{n, 1}e_1 + \ldots + a_{n, n}e_n \end{aligned}

Where $a_{i, j} \in \mathbb{Q}$. Note this can be rewritten as:

\begin{aligned} (a_{1, 1} - x)e_1 + \ldots + a_{1, n} e_n& = 0 \end{aligned}

\begin{aligned} \vdots \end{aligned}

\begin{aligned} a_{n, 1}e_1 + \ldots + (a_{n, n} - x)e_n& = 0 \end{aligned}

Let $A$ be the matrix such that the $i, j$th entry is $a_{i, j}$, so $A \in \mathbb{Q}^{n \times n}.$ Note this can again be rewritten as

\begin{aligned} \det(A - xI) = 0 \end{aligned}

This is the characteristic equation of $A$. Note from the definition of the determinant that the characteristic equation lies in $\mathbb{Q}[x]$. From $xV \subseteq V$, we have that $x$ is a solution to a polynomial in $\mathbb{Q}[x]$, so $x$ must be algebraic.

Note that $(\alpha + \beta)V, (\alpha\beta)V \subseteq V$, so the sum and product of algebraic numbers is itself an algebraic number. As such, the set of algebraic numbers form a field. □

There are hints of linear algebra inside of this, mostly because it is all just linear algebra at the end of the day.

Remember that we are interested in polynomials in $\mathbb{Z}[x]$. We say $\alpha \in \mathbb{C}$ is an algebraic integer if there exists a monic polynomial $f \in \mathbb{Z}[x]$ such that $f(\alpha) = 0$.

This also has a nice algebraic structure.

thm. The set of algebraic integers form a subring of the field of algebraic numbers.

Proof. Note that again, $0$ and $1$ are algebraic integers, as $x, x-1 \in \mathbb{Z}[x]$.

Let $\alpha$ be an algebraic integer with monic polynomial $f \in \mathbb{Z}[x]$ with $f(\alpha) = 0$. Then note $(-1)^{\deg(f)}f(-x)$ has a root at $-\alpha$ and is monic and in $\mathbb{Z}[x]$, so we have additive inverses.

So, now we need addition and multiplication. The proof is almost exactly the same, only instead of $\mathbb{Q}$-linear combinations, we use $\mathbb{Z}$-linear combinations. So, let $\alpha, \beta$ be algebraic integers with polynomials $f, g$ respectively. Here, let $S$ be the finite abelian group generated by $\mathbb{Z}$-linear combinations of $\left\langle\alpha^i, \beta^j\mid i, j \in \mathbb{N} \right\rangle.$ Let $n$ be the dimension of $S$, which is at most $(\deg (f) - 1)(\deg (g) - 1)$, and let $e_1, \ldots, e_n$ be generators of $S$.

Let $x$ such that $xS \subseteq S$. Then we can write the system of equations just as before:

\begin{aligned} xe_1& = a_{1, 1}e_1 + \ldots + a_{1, n} e_n \end{aligned}

\begin{aligned} \vdots \end{aligned}

\begin{aligned} xe_n& = a_{n, 1}e_1 + \ldots + a_{n, n}e_n \end{aligned}

However, $a_{i, j} \in \mathbb{Z}$. Let $A$ be the matrix such that the $i, j$th entry is $a_{i, j}$. Then $A \in \mathbb{Z}^{n\times n}$, and we have the following equation:

\begin{aligned} \det (A - xI) = 0 \end{aligned}

Again, the characteristic polynomial in $A$ is monic and lies in $\mathbb{Z}[x]$. As $x$ is a root of this polynomial, $x$ must be an algebraic integer.

Consider $(\alpha + \beta)S, (\alpha\beta)S \subseteq S$. Then the sum and product of algebraic integers is itself an algebraic integer. Therefore the set of algebraic integers forms a subring of the field of algebraic numbers. □

So, let’s recap. The prefix of algebraic simply means it can be described as the root of something algebraic, specifically a nice enough polynomial.

We end with Gauss’s Lemma, which tells us that the minimal polynomial of an algebraic integer must also be in $\mathbb{Z}[x]$.

lemma. Let $f, g, h \in \mathbb{Q}[x]$ and all monic. If $f \in \mathbb{Z}[x]$ and $f = gh$, then $g, h \in \mathbb{Z}[x].$

Proof. Secretly, we will be using the notion of primitive. A polynomial in $\mathbb{Z}[x]$ is primitive if the gcd of the coefficients is $1$.

Write $g(x) = cg_0(x)$, $h(x) = dh_0(x)$ where $g_0, h_0 \in \mathbb{Z}[x]$, $c, d \in \mathbb{Q}$, and $g_0$ and $h_0$ are primitive. (To do this, simply clear out the denominators of $g$ and then divide by any common factors, then take the inverse.)

We wish to show that the product of primitive polynomials is itself primitive. Let $a(x), b(x)$ be primitive polynomials in $\mathbb{Z}[x]$. Consider $a(x)b(x)$. Assume towards a contradiction that it is not primitive, i.e. there exists some prime $p$ that divides all coefficients. Let $a_ix^i$ and $b_jx^j$ be the first terms of $a, b$ such that $p$ does not divide $a_i, b_j$. But then note the coefficient of $x^{i+j}$ is equal to

\begin{aligned} \ldots + a_{i+1}b_{j-1} + a_ib_j + a_{i-1}b_{j+1} + \ldots \end{aligned}

However, by virtue of being the smallest, note each other term must have $p$ as a factor. However, $a_ib_j$ is not a multiple of $p$, so we have a contradiction. As such, $a(x)b(x)$ is primitive.

This tells us that $g_0(x)h_0(x) \in \mathbb{Z}[x]$ is primitive. Note then that $cd = 1$, as $f(x) = cd g_0(x)h_0(x)$.

However, if $c$ is not $1$, then one of $c, d$ must lie in the noninteger rationals. However, as $g, h$ are monic, we must in fact have $c = d = 1$. So $g = g_0$ and $h= h_0$, so $g, h \in \mathbb{Z}[x]$. □

This result is pretty important if you do a course in any of this ring/field theory.

Cyclotomic Number Fields

Now, fix some $n \in \mathbb{N}$ to be some positive integer. We define $\zeta_n = e^{\frac{2\pi i}{n}}$. This is the nicest $n$th primitive root of unity.

We now consider the number field $\mathbb{Q}[\zeta_n]$. This is denoted as the $n$th cyclotomic field. Note that $\zeta_n$ is an algebraic integer, as it satisfies the equation $x^n - 1$. I am going to assume, without proof, the following theorem. This can be proven, but takes a lot of effort, so I will not prove it here.

thm. The ring of integers in $\mathbb{Q}[\zeta_n]/\mathbb{Q}$ is $\mathbb{Z}[\zeta_n]$.

Specifically, if $\alpha$ is an algebraic integer, then it is expressible as a $\mathbb{Z}$-linear combination of powers of $\zeta_n$. That is the key assumption here.

Let us concern ourselves with the minimal polynomial of $\zeta_n$. This section will try and show that the minimal polynomial of $\zeta_n$ has the form

\begin{aligned} \Phi_n(x) = \prod_{\substack{1 \leq k < n \ \gcd(n, k) = 1}}\left(x - \zeta_n^k\right). \end{aligned}

We define the function $\varphi(n)$ to be Euler’s Toitient function, which gives us the number of natural numbers less than $n$ coprime to $n$.

Equivalently, $\varphi(n) = \mid(\mathbb{Z}/n\mathbb{Z})^\times\mid$. Note $\deg(\Phi_n) = \varphi(n)$.

Now, we want to show that $\Phi_n$ is irreducible, monic, and lies in $\mathbb{Z}[x]$. It is clearly monic.

lemma. $\Phi_n \in \mathbb{Z}[x].$

Proof. Note we cannot immediately use Gauss’s Lemma here, as even though it is monic and divides $x^n- 1$, we do not know about the rest of the coefficients.

We prove this via induction. We have $\Phi_1(x) = x-1 \in \mathbb{Z}[x]$. Assume that for $d < n$, $\Phi_d(x) \in \mathbb{Z}[x].$

Write $f(x) = \prod_{d\mid n, d \neq n}\Phi_d(x) \in \mathbb{Z}[x]$. Note that $x^n-1 = f(x)\Phi_n(x)$.

As $f$ is monic, we can do the division algorithm to get $q, r \in \mathbb{Z}[x]$ such that $\deg(r) < \deg(f)$ and $x^n-1 = f(x)q(x) + r(x)$. Then,

\begin{aligned} f(x)q(x) + r(x)& = f(x)\Phi_n(x) \end{aligned}

\begin{aligned} r(x)& = f(x) \left( \Phi_n(x) - q(x) \right) \end{aligned}

Assume that $\Phi_n \neq q$. Then $\deg(r) \geq \deg(f)$, which is a contradiction to the division algorithm, so we must have $\Phi_n = q \in \mathbb{Z}[x]$, so $\Phi_n \in \mathbb{Z}[x]$. □

We will hold off proving that $\Phi_n$ is irreducible. Right now, this tells us that you only need up to $\varphi(n)$ elements to generate $\mathbb{Q}[\zeta_n]/\mathbb{Q}$.

Now, let’s try and figure out the automorphism group of $\mathbb{Q}[\zeta_n]$ over $\mathbb{Q}$, which is denoted $\text{Gal}(\mathbb{Q}[\zeta_n]/\mathbb{Q}).$ This is the set of all field automorphisms that fix the base field.

thm. $\text{Gal}(\mathbb{Q}[\zeta_n]/\mathbb{Q}) \cong (\mathbb{Z}/n\mathbb{Z})^\times$

Proof. Note this is determined by the generators, more specifically generated by $\zeta_n$. Let $\sigma$ be an element of the Galois Group. Then note it has to satisfy

\begin{aligned} \sigma(\zeta_n)^n& = 1 \end{aligned}

\begin{aligned} \sigma(\zeta_n)^i& \neq 1, i \not \equiv 0 \pmod{n} \end{aligned}

The second condition is necessary for the map to be surjective. What this means is that it maps $\zeta_n$ to another primitive root, of which there are exactly $\varphi(n)$ of.

Specifically, each automorphism can be determined by which coprime power of $\zeta_n$ they map $\zeta_n$ to. This naturally gives us a way to inject into and surject from $(\mathbb{Z}/n\mathbb{Z})^\times$, and so the two are isomorphic. □

Let $\alpha$ be an algebraic integer in $\mathbb{Q}[\zeta_n]$. We define the Galois Conjugates of $\alpha$ to be the image of $\alpha$ under automorphisms from the Galois Group. We then define the norm function $N$ to be the product of the Galois conjugates:

\begin{aligned} N_{\mathbb{Q}[\zeta_n]/\mathbb{Q}}(\alpha) = \prod_{\sigma \in \text{Gal}(\mathbb{Q}[\zeta_n]/\mathbb{Q})} \sigma(\alpha) \end{aligned}

We require the base field to be in the subscript as the automorphism group is dependent on it. For the rest of the paper, though, we’re just going to use this definition of the norm, as $n$ is fixed.

Note this is multiplicative, which grants it the name of the norm. (Also, you can think of this as some power of the constant term of the minimal polynomial used to describe $\alpha$, though I haven’t properly motivated this).

To prove the next theorem, we need to quickly talk about the fundamental theorem of symmetric polynomials.

Define the $k$th elementary symmetric polynomial recursively:

\begin{aligned} e_1(x_1, \ldots x_n)& = \sum_{i=1}^n x_1 \end{aligned}

\begin{aligned} e_k(x_1 \ldots x_n)& = \sum_{i =1}^{n - k + 1} x_ie_{k-1}(x_{i+1}, \ldots, x_N) \end{aligned}

Simply put, the $k$th elementary symmetric polynomial is the sum of all the products of all ordered $k$ tuples of inputs. We have this second, unproven result, for the sake of space.

thm. Every symmetric polynomial over $n$ variables can be written as $f(e_1(x_1, \ldots, x_n), \ldots, e_n(x_1, \ldots, x_n))$ where $f$ is some polynomial.

Note that Vieta’s formulae tell us that the coefficients of some polynomial is symmetric in its roots.

Now, we can move to the next result.

thm. If $\alpha$ is an algebraic integer, then $N(\alpha) \in \mathbb{Z}$.

Proof. Let $\alpha$ be an alg. integer. Define

\begin{aligned} f_{\alpha}(x) = \prod_{\sigma \in \text{Gal}(\mathbb{Q}[\zeta_n]/\mathbb{Q})} (x - \sigma(\alpha)) \end{aligned}

Then clearly the constant term of this polynomial is the norm, up to sign.

We write $\alpha = r(\zeta_n)$ where $r$ is some polynomial in $\mathbb{Z}[x]$ with degree less than $\varphi(n)$. So,

\begin{aligned} f_{\alpha}(x) = \prod_{\substack{1 \leq i < n \ \gcd(i, n) = 1}} (x - r(\zeta_n^i)) \end{aligned}

Note that each coefficient of $f_{\alpha}$ is then a polynomial symmetric in each coprime power of $\zeta_n$. By the fundamental theorem, this is some polynomial with coefficients in $\mathbb{Z}$ of the elementary symmetric polynomials over the coprime powers of $\zeta_n$. Note as $\Phi_n \in \mathbb{Z}[x]$, each elementary symmetric poly over coprime powers of $\zeta_n$ evaluates to an integer. This means that each coefficient in $f_{\alpha}$ is an integer, and in fact $f_\alpha \in \mathbb{Z}[x]$.

This tells us that $\left| N(\alpha)\right| = \left| f_{\alpha}(0)\right| \in \mathbb{Z}$. □

Note also that this gives us the immediate corollary.

cor. The only algebraic integers in $\mathbb{Q}$ are precisely the integers.

Proof. Consider $N(a)$ for $a \in \mathbb{Q}$. As the automorphism fixes $a$, this evaluates to $N(a) = a^{\varphi(n)}$. If $a$ is a rational noninteger, then its nonzero powers are also a rational noninteger, so it cannot be an algebraic integer.

As for any $a \in \mathbb{Z}$, consider the minimal polynomial $x - a$. □

So, why did we go through all of that? It’ll be a surprise. Maybe.

Irreducibility

So, the last step is to show that $\Phi_n$ is irreducible. This will actually require us to prove two quick technical lemmas, and then a theorem that is relevant to the exposition at large. The first is the freshman’s dream, the second is Fermat’s little theorem.

lemma. Let $p$ be prime. Then \begin{aligned} (x_1 + \ldots + x_n)^p \equiv x_1^p + \ldots + x_n^p \pmod{p}. \end{aligned}

Proof. Note we can induct on $n$ to make this problem only consider two variables. Then, this proof follows by binomial theorem:

\begin{aligned} (x + y)^p& \equiv \sum_{k=0}^{p} x^ky^{p-k}\binom{p}{k} \end{aligned}

\begin{aligned} & \equiv x^p + y^p + \sum_{k=1}^{p-1} x^ky^{p-k}\frac{p (p-1)!}{k!(p-k)!} \end{aligned}

As $p$ is prime, it doesn’t disappear from the binomial coefficient. As such,

\begin{aligned} (x + y)^p \equiv x^p + y^p \pmod{p} \end{aligned} □

Then, we have the following corollary.

cor. Let $p$ prime. Then $x^p \equiv x \pmod{p}$.

Proof. We can induct on $x$. Clearly this is true when $x \equiv 0 \pmod{p}$. Then, assuming this holds for $x$, we have

\begin{aligned} (x + 1)^p \equiv x^p + 1^p \equiv x+1 \pmod{p} \end{aligned}

This is the nicest proof of Fermat’s little theorem. □

This proof direction I believe was given to us by Schur, though I could be wrong.

thm. $\Phi_n$ is irreducible.

Proof. We first compute the discriminant of $x^n - 1$:

\begin{aligned} \left|\Delta\right|& = \left|\prod_{i < j} \left(\zeta_n^i - \zeta_n^j\right)^2\right| \end{aligned}

\begin{aligned} & = \left|\prod_{i \neq j} (\zeta_n^i-\zeta_n^j)\right| \end{aligned}

\begin{aligned} & = \left|\prod_{i \neq j} \zeta_{n}^i(1-\zeta_n^{i-j})\right| \end{aligned}

\begin{aligned} & = \left|\prod_{i =1}^{n} \zeta_{n}^i\prod_{k=1}^{n-1}(1-\zeta_n^{k})\right| \end{aligned}

Note that

\begin{aligned} x^n - 1& = (x-1)\prod_{k=1}^{n-1}(x-\zeta_n^{k}) \end{aligned}

\begin{aligned} \prod_{k=1}^{n-1}(x-\zeta_n^{k})& = \frac{x^n-1}{x-1} \end{aligned}

\begin{aligned} & = 1 + x + x^2 + \ldots + x^{n-1} \end{aligned}

So,

\begin{aligned} \left|\Delta\right|& = \left|\prod_{i =1}^{n} \zeta_{n}^in\right| \end{aligned}

\begin{aligned} & = n^n\left|\zeta_n^{\frac{n(n+1)}{2}}\right| \end{aligned}

\begin{aligned} & = n^n. \end{aligned}

I promise that this is important.

Let $f$ be a factor of $x^n - 1$ which lies in $\mathbb{Z}[x]$ with $\zeta_n$ as a root of $f$. We want to show that for all primes $p \not\mid n$, we have $f(\zeta_n^p) = 0$.

Assume towards a contradiction that $f(\zeta_n^p) \neq 0$. Note that $f$ is the product of linear factors, each of the form $x - \zeta_n^k$ with $k$ not equal to $p$. This means that $f(\zeta_n^p)$ is an algebraic integer that divides $n^n$.

Note by the Freshman’s Dream and Fermat’s Little Theorem, we have $f(x^p) \equiv (f(x))^p \pmod{p}$.

This tells us that $f(x^p) - f(x)^p = pg(x)$ for some $g(x) \in \mathbb{Z}[x]$. So, $f(\zeta_n^p) - f(\zeta_n)^p = f(\zeta_n^p) = pg(\zeta_n).$

This means that $p$ divides $f(\zeta_n^p)$ as an algebraic integer, which divides $n$ as an algebraic integer.

What does that mean, though? What it does tell us is that there exists some algebraic integer $\alpha$ such that $p\alpha = n$. But then $\alpha = \frac{n}{p}$, so $\alpha \in \mathbb{Q}$, but the only rational algebraic integers are the integers, so $\alpha \in \mathbb{Z}$. This means that, in the rational integers, $p \mid n$.

But this contradicts our assumption! So, we must have that $\zeta_n^p$ is a root of $f$.

Then, repeated applications of this result let us show that if $\zeta_n$ is a root of $f$, then $\zeta_n^a$ is a root of $f$ where $\gcd(a, n) = 1$, as the other root is still primitive.

Note that $\Phi_n$ is the smallest such polynomial such that the previous holds, and as such it must be irreducible. □

So, $\Phi_n$ is exactly the minimal polynomial of $\zeta_n$ in $\mathbb{Z}[\zeta_n]$. That’s one of the nicest bits of cyclotomics.

Dealing with Small Things

In general, computing a polynomial can be annoying, as we are doing arithmetic in $\mathbb{C}$. So, we want to be able to deal with it in a smaller field, a finite field hopefully.

thm. Let $p$ prime in $\mathbb{Z}$ such that $\mathbb{F}_p$ has a solution to $x^n - 1$, call it $\omega_n$. Let $g \in \mathbb{Z}[x]$, with $\overline{g}$ be the reduction of $g$ mod $p$ in $\mathbb{F}_p[x]$. Then

1. If $g(\zeta_n) = 0$, then $\overline{g}(\omega_n) = 0$.
2. If $\overline{g}(\omega_n) = 0$, then $p \mid N(g(\zeta_n))$

Proof. Define the terms as in the theorem.

Let $\text{ev} : \mathbb{Z}[x] \to \mathbb{F}_p$ be the evaluation map, defined by $\text{ev}(f) = \overline{f}(\omega_n)$.

Note for $d < n$, we have $\text{ev}(x^d - 1) \neq 0$ as $\omega_n$ is primitive. Then, as $\Phi_d \mid x^d - 1$, we have $\text{ev}(\Phi_d) \neq 0,$ as $\mathbb{F}_p$ is a field.

This tells us that $\text{ev}(\Phi_n) = 0$, as $x^n - 1$ is the product of $\Phi_d$ where $d$ divides $n$.

Note the kernel of the natural map $\pi: \mathbb{Z}[x] \to \mathbb{Z}[\zeta_n]$ has kernel generated by $\Phi_n$, as $\Phi_n$ is the minimal polynomial of $\zeta_n$. This gives us $\mathbb{Z}[\zeta_n] \cong \mathbb{Z}[x]/(\Phi_n)$, by the first isomorphism theorem.

Now, we will invoke the universal property of quotient rings, though I’ll run through the steps explicitly here.

The setup currently is we have a map $\text{ev}$ from $\mathbb{Z}[x]$ to $\mathbb{F}_p$, and a map from $\mathbb{Z}[x]$ to $\mathbb{Z}[\zeta_p]$, with kernel generated by $\Phi_n$. Note that $\Phi_n$ is in the kernel of $\text{ev}$.

Define $\text{ev}’: \mathbb{Z}[x]/(\Phi_n) \to \mathbb{F}_p$ as the map that sends $\text{ev}’(f + (\Phi_n)) = \text{ev}(f)$.

We first prove this is well-defined. Say we have two representatives of the same coset, specifically $f_1 + (\Phi_n) = f_2 + (\Phi_n).$

Then there exists some polynomial $g \in (\Phi_n)$ such that $f_1 = f_2 + g$. Then

\begin{aligned} \text{ev}’(f_1 + (\Phi_n))& = \text{ev}(f_1) \end{aligned}

\begin{aligned} & = \text{ev}(f_2) + \text{ev}(g) \end{aligned}

\begin{aligned} & = \text{ev}(f_2) \end{aligned}

\begin{aligned} & = \text{ev}’(f_2 + (\Phi_n)) \end{aligned}

So this is well defined. Also note that this is a ring homomorphism. Let $f_1, f_2 \in \mathbb{Z}[x]$. Then

\begin{aligned} \text{ev}’((f_1 + (\Phi_n)) + (f_2 + (\Phi_n))& = \text{ev}’((f_1 + f_2) + (\Phi_n)) \end{aligned}

\begin{aligned} & = \text{ev}(f_1 + f_2) \end{aligned}

\begin{aligned} & = \text{ev}(f_1) + \text{ev}(f_2) \end{aligned}

\begin{aligned} & = \text{ev}’(f_1 + (\Phi_n)) + \text{ev}’(f_2 + (\Phi_n)). \end{aligned}

Note that $\text{ev}’ \circ \pi = \text{ev}$. In this way, $\text{ev}$ factors into $\text{ev}’$. In fact, $\text{ev}’$ is the unique map that factors this way, as the other function must agree with the definition of $\text{ev}’$.

Note that I was using $\mathbb{Z}[x]/(\Phi_n)$. As this is isomorphic to $\mathbb{Z}[\zeta_n]$ by sending every $x$ to a $\zeta_n$, we can then say that $\text{ev}’$ is a homomorphism that factors $\text{ev}$. More specifically, $\text{ev}’ : \mathbb{Z}[\zeta_n] \to \mathbb{F}_p$ sends all $\zeta_n$’s to $\omega_n$’s.

This seems like a whole lot of yap for not much. However! Let’s say that $f \in \mathbb{Z}[x]$ such that $f(\zeta_n) = 0$. Then,

\begin{aligned} \overline{f}(\omega_n) \equiv \text{ev}’(f(\zeta_n)) \equiv \text{ev}’(0) \equiv 0 \pmod{p}. \end{aligned}

This proves the first part. Now, for the second part, we have to prove that the preimage of a prime ideal under a ring homomorphism is a prime ideal. Again, we will translate it into language specific to here, but it is true in general.

Note that the ideal $(0)$ is prime in $\mathbb{F}_p$ as it contains no zero divisors. Let $a, b \in \mathbb{Z}[\zeta_n]$ and $ab \in \ker(\text{ev}’)$. Then we have $\text{ev}’(a)\text{ev}’(b) = 0$, so either $a, b$ is in the kernel. This tells us that the kernel of $\text{ev}’$ is a prime ideal in $\mathbb{Z}[\zeta_n]$, which we denote as $\mathfrak{p} = \ker(\text{ev}’)$

Also note that $\mathfrak{p}$ lies over $p$, i.e. $\mathbb{Z} \cap \mathfrak{p} = p\mathbb{Z}.$ Note if $\overline{f}(\omega_n) = 0$, then $f(\zeta_n) \in \mathfrak{p}$. Then all the Galois conjugates of $f(\zeta_n)$ are in other prime ideals (consider the image of $\mathfrak{p}$ under the automorphism) that lie over $p$. As the norm of an algebraic integer is in $\mathbb{Z}$, and these are all ideals, the norm must be inside of all of these ideals, which means it must be in $p\mathbb{Z}$.

This means $p \mid N(f(\zeta_n))$, which proves statement 2. □

This idea from above is the core of the rest of the paper.

Anywho, this is everything on algebraic number theory that’s somewhat relevant for the rest of the paper, which is to come shortly. There will be more on algebraic numbers, though in the context of other objects, such as algebraic circuits and probability.

I hope this isn’t too messy! It’s mostly for my own eyes, but I hope that this acts as a good way to refresh some core proofs and basics around cyclotomic fields.

Algebraic Circuits

I’m intentionally holding off from stating the problem as is, and instead focusing more on the underlying mathematics that makes it all work out.

However, we do eventually need to have some metric of quantifying the size of the problem to say how much time it does take. And so I begin.

Polynomials as Instructions

What exactly is a polynomial? In some sense, it’s a list of instructions, which rely on the output of previous instructions and combine them in a ring-like way.

To capture this, we formally define an algebraic circuit. An algebraic circuit $C$ is a directed acyclic graph with labeled edges and vertices.

Vertices of in-degree zero are the “input” vertices, each of which is labeled with a monomial (which is some element of $\lbrace x^e\mid e \in \mathbb{N}\rbrace $, in which $0 \in \mathbb{N}$). Every other vertex has in-degree two and is labeled with a $+, \times$.

Moreover, the incoming edges to $+$ labeled vertices have labels in $\mathbb{Z}$, to denote it as an integer weighted sum. Finally, there is a unique vertex of out-degree zero which is the output vertex of the circuit.

This is how we represent the instructions of a polynomial in $\mathbb{Z}[x]$. Note that there can be multiple equivalent circuits, and the problem of checking if two circuits are the same is called polynomial identity testing.

Now, the setup to the cyclotomic identity testing question asks if we are given a circuit $C$ and an integer $n$, does $C$ evaluate to $0$ on $\zeta_n$?

We define the size of $C$ to be the number of edges and bit-length of all integer constants that appear in $C$.

Note that each algebraic integer $\alpha \in \mathbb{Z}[\zeta_n]$ can be written as $f(\zeta_n)$ where $f \in \mathbb{Z}[x]$. We then say that $\alpha$ has description of size $s$ if it can be computed by a circuit $C$ and $s$ is the sum of the size of $C$ and the bit-length of $n$.

Properties of Algebraic Circuits

Perhaps intuitively, we can write a bound on an algebraic integer given its description. The intuition may be that the description captures the size of the bit-length of the coefficients in the polynomial. Sadly, the bound is quite ugly.

prop. Let $\alpha \in \mathbb{Z}[\zeta_n]$ have description of size $s$. Then $\left| N(\alpha)\right| \leq 2^{2^{2s}}.$

Proof. Write $\alpha = \sum_{i=0}^{n-1}a_i\zeta_n^i$. Then let $H = \sum_{i=0}^{n-1}\mid a_i\mid.$

Say $\alpha$ is computed by a circuit of size $c$. We induct on $c$ to describe how large $H$ can be as a function of $c$. Specifically, we want to write $H \leq 2^{2^{c}}.$.

Clearly, if $c$ is $0$, then $\alpha$ is a monomial, so the largest coefficient is $1$. Then $1 < 2^{2^0} = 2.$

Say $c > 0$ and for all smaller sizes that bound works. We do casework on the output vertex. If the output vertex is a $\times$, then we have two sub-circuits of size $c_1, c_2$ that get passed into the last vertex. Note then that $c_1, c_2 < c - 1$, as it uses up one edge for each input to the last vertex.

Then note that the sum of all the coefficients of the output is the same as taking the sum of all of the coefficients of the polynomials computed by the subcircuits. This gives us the upper bound on $H$,

\begin{aligned} H \leq 2^{2^{c_1}} 2^{2^{c_2}} \leq 2^{2^{c_1}+2^{c_2}} < 2^{2^{c}} \end{aligned}

So, we move to the other case. Note that for an addition vertex, we have to consider $4$ things instead of two.

Say the last vertex is labeled with $+$. Then consider the subcircuits of size $c_1, c_2$, and integer weights with bit-length $b_1, b_2$. Then again note that $c_1, c_2 < c - 2$ by the edges and the weights, and that $b_1, b_2 < c - 2$ similarly.

Then, the sum of them is at most the sum of each coefficient. This gives us the upper bound

\begin{aligned} H \leq 2^{b_1}2^{2^{c_1}} + 2^{b_2}2^{2^{c_2}} < 2^{c-2}(2^{2^{c-2}} + 2^{2^{c-2}}) = 2^{c-1+2^{c-2}} \end{aligned}

Then, as $c - 1 < 2^{c-2}$ when $c \geq 3$, this holds. Note the $c = 2$ case is not possible if the last label is a $+$ vertex. So, $H < 2^{2^{c}}.$

Note that the norm is equal to the product of the Galois conjugates. We then have

\begin{aligned} \left| N(\alpha)\right|& = \left| N\left(\sum_{i=0}^{n-1} a_i\zeta_n^i\right)\right| \end{aligned}

\begin{aligned} & = \prod_{\sigma \in \text{Gal}(\mathbb{Q}[\zeta_n]/\mathbb{Q})}\left|\sigma\left(\sum_{i=0}^{n-1} a_i\zeta_n^i\right)\right| \end{aligned}

\begin{aligned} & = \prod_{k \in (\mathbb{Z}/n\mathbb{Z})^{\times}}\left|\sum_{i=0}^{n-1} a_i\zeta_n^{ik}\right| \end{aligned}

\begin{aligned} & \leq \prod_{k \in (\mathbb{Z}/n\mathbb{Z})^{\times}}\sum_{i=0}^{n-1} \left| a_i\mid\mid\zeta_n^{ik}\right| \end{aligned}

\begin{aligned} & = \prod_{k \in (\mathbb{Z}/n\mathbb{Z})^{\times}} H \end{aligned}

\begin{aligned} & \leq H^{n} \end{aligned}

\begin{aligned} & \leq 2^{n2^{c}} \end{aligned}

Note that $s$ is the description of $\alpha$, specifically the sum of the bit-length of $n$ and $c$. Note that $n \leq 2^{\lceil\log_2(n)\rceil},$ which gives us

\begin{aligned} \left| N(\alpha)\right|& \leq 2^{2^{c + \lceil\log_2(n)\rceil}} = 2^{2^{s}} \end{aligned}

This in fact completes the proof, since, uh, well, $2s > s$, so, uh, yeah, the absolute value of the norm is at most $2^{2^{2s}}$.

□

I don’t actually like the proof given, as it uses $n$ elements to expand $\alpha$, instead of a more succinct $\varphi(n)$ number. But I don’t think this actually makes it any more efficient to write, and $\varphi(n)$ can only be one away from $n$ when $n$ prime, anywho.

Probabilities

Now we are moving into the realm of probability. This paper is eventually about a randomized algorithm, after all.

There wouldn’t be anything weird here then, right?

Nothing weird…

We have the following technical lemma. This is almost a standard argument.

prop. Fix $m \in \mathbb{N}$ and draw $k$ uniformly at random from the set $\lbrace 1, \ldots, m - 1\rbrace $. Let $A$ be the event that $\gcd(k, m) = 1$ and let $B$ be the event that $m, k$ share no common prime divisor $p < 10 \log_2(m)$. Then $\mathbb{P}(A \mid B) > 0.9$ for $m$ sufficiently large.

Proof. Note that $\mathbb{P}(B \mid A) = 1$.

Let $m = p_1^{e_1} \ldots p_r^{e_r}$ for $p_i$ prime and $e_i$ a positive integer. Let $E_i$ be the event that $p_i \not \mid k$. Note each $E_i$ is independent.

We do this almost by definition:

\begin{aligned} \mathbb{P}(A \mid B)& = \frac{\mathbb{P}(A \cap B)}{\mathbb{P}(B)} \end{aligned}

\begin{aligned} & = \frac{\mathbb{P}(A)}{\mathbb{P}(B)} \end{aligned}

\begin{aligned} & = \frac{\mathbb{P}\left(\bigcap_{i=1}^{r} E_i\right)}{\mathbb{P}\left(\bigcap_{p_i < 10 \log_2(m)} E_i\right)} \end{aligned}

\begin{aligned} & = \prod_{p_i \geq 10 \log_2(m)} \mathbb{P}(E_i) \end{aligned}

So, we have to compute each $\mathbb{P}(E_i)$. It is clear that there are $\frac{m}{p_i} - 1$ elements that $k$ can be such that $p_i \mid k$, so $\mathbb{P}(E_i) = 1 - \frac{m - p_i}{mp_i - p_i} \geq 1 - \frac{1}{p_i}.$ As such

\begin{aligned} \mathbb{P}(A \mid B)& \geq \prod_{p_i \geq 10 \log_2(m)} \left(1 - \frac{1}{p_i}\right) \end{aligned}

\begin{aligned} & \geq \prod_{p_i \geq 10 \log_2(m)} \left(1 - \frac{1}{10 \log_2(m)}\right) \end{aligned}

\begin{aligned} \mathbb{P}(A \mid B)& \geq \left(1 - \frac{1}{10 \log_2(m)}\right)^{\log_2(m)} \end{aligned}

Note $m$ has at most $\log_2(m)$ factors, and each element in the product is less than $1$. Then,

\begin{aligned} \mathbb{P}(A \mid B)& \geq \left(1 - \frac{1}{10 \log_2(m)}\right)^{\log_2(m)} \end{aligned}

As $m \to \infty$, this trends to $e^{-0.1} \approx 0.9048$, so for sufficiently large $m$, $\mathbb{P}(A \mid B) > 0.9.$ □

Any reasonable person would look at the $10\log_2(x)$ originally and go “what! what the hell are you doing!” and then by the end of the proof go “ahhh, you’re being reasonable.” Though I’d laugh and point “aha! you’ve assumed 0.9 is reasonable.”

Though it actually is, since its a small enough constant. I’ll get to that by the end.

We use this to get an error bound on finding primitive roots.

prop. Let $p$ be prime. For sake of rendering, let $A = \mathbb{F}_p^{\times}$. Let $h$ be chosen uniformly at random from the set

\begin{aligned} \left\lbrace a \in A \mid \bigwedge_{\substack{2 \leq q < 10 \log_2(p-1) \ q \mid p-1}} a^{\frac{p-1}{q}} \not\equiv 1 \pmod{p}\right\rbrace . \end{aligned}

Then $h$ is a primitive root of unity with probability at least $0.9$ for large enough $p$.

Proof. Let $g$ be a primitive root of $\mathbb{F}_p^{\times}$. Note that for $a$ distributed uniformly over $\mathbb{F}_p^{\times}$, we have $\log_g(a)$ uniformly distributed over $\lbrace 0, \ldots, p-2\rbrace $.

We need a quick tidbit. Specifically, if $q \mid p-1$, then if $q$ divides $\log_g(a)$ then $a^{\frac{p-1}{q}} \equiv 1 \pmod{p}.$

Say that $q$ divides $\log_g(a)$. Then we have $\left(g^{\frac{\log_g(a)}{q}}\right)^{p-1} \equiv 1 \pmod{p}$ by Fermat’s little theorem, which tells us that $a^{(p-1)/q} \equiv 1 \pmod{p}$.

Note that original set then tells us that $\log_g(h)$ is distributed uniformly at random over the set of elements in $\lbrace 1, \ldots, p-2\rbrace $ that do not share a divisor less than $10 \log_2(p-1)$ with $p-1$.

We use that previous lemma, which states for large enough $p-1$, then the probability that $\log_g(h)$ is coprime to $p-1$ is at least $0.9$, as the condition has been met.

What this tells us is that $h$ is a primitive root with probability at least $0.9$, for sufficiently large $p$. □

So, if we have some (large) prime $p$ that has an $n$th root of unity, then we can find it! We just have to find a primitive root, then raise it to the $(p-1)/n$th power.

But, note the only primes that have solutions to $x^n-1$ are precisely those that have $n \mid p-1$, or, when $p \equiv 1 \pmod{n}.$

Note there’s an infinite number of these by Dirichlet’s theorem on AP’s. But, like, how do we get one? We also need it to be large!

The Generalized Riemann Hypothesis?!

So, uh, remember when I said we were only assuming two things? The ring of integers and the elementary symmetric polynomials? I lied. We’re assuming a third big thing.

thm. Let $a \in \mathbb{N}$ be less than $n$ and coprime to $n$. Write $\pi_{n, a}(x)$ to be the number of primes less than $x$ that are congruent to $a$ mod $n$. Under the Generalized Riemann Hypothesis (GRH), there exists a real positive constant $C$ such that for all $x$,

\begin{aligned} \pi_{n, a}(x) \geq \frac{x}{\varphi(n) \log_2(x)} - C\sqrt{x}\log_2(x). \end{aligned}

Unconditionally (e.g. without assuming GRH), there exists two real positive constants $C_1, C_2$ such that for all $n < C_1x^{C_1}$ we have

\begin{aligned} \pi_{n, a}(x) \geq \frac{C_2x}{\varphi(n)\sqrt{n}\log_2(x)} \end{aligned}

Yeah, so I am not getting into that GRH business. Stuff is whack.

However, this does let us write down probability bounds.

prop. Let $\alpha \in \mathbb{Z}[\zeta_n]$ be nonzero whose description has size at most $s$. Suppose that $p$ is chosen uniformly at random from $\lbrace q \in \mathbb{N}: q\leq 2^{5s}, q \equiv 1 \pmod{n}\rbrace $.

1. Assuming GRH, $p$ is prime with probability at least $\frac{1}{6s}$ for $s$ large enough.
2. If $p$ is prime, then the probability that it divides $N(\alpha)$ is at most $2^{-s}.$

Proof. We’re going to use that first bit of the theorem from before. Assume GRH. Then, let $C$ be the positive real constant from the previous theorem. Then, the probability that $p$ is prime is

\begin{aligned} \frac{\pi_{n, 1}(2^{5s})}{\lfloor 2^{5s}/n\rfloor}& \geq \frac{n\pi_{n, 1}(2^{5s})}{2^{5s}} \end{aligned}

\begin{aligned} & \geq \frac{n}{\varphi(n)\log_2(2^{5s})} - \frac{Cn\log_2(2^{5s})}{\sqrt{2^{5s}}} \end{aligned}

\begin{aligned} & \geq \frac{1}{5s}\cdot\frac{n}{\varphi(n)} - \frac{Cn5s}{2^{2.5s}} \end{aligned}

\begin{aligned} & \geq \frac{1}{5s} - \frac{C2^s5s}{2^{2.5s}} \end{aligned}

\begin{aligned} & = \frac{1}{5s} - \frac{C5s}{2^{1.5s}} \end{aligned}

Note for $s$ sufficiently large, we have $150Cs^2 < 2^{1.5s}$. When this occurs, we have

\begin{aligned} \mathbb{P}(p \text{ is prime})& \geq \frac{1}{6s} \end{aligned}

So we have proven the first part. We actually need to go back and use the bound on the norm that we proved, which tells us that the absolute value of the norm of $\alpha$ is at most $2^{2^{2s}}$.

This tells us that $N(\alpha)$ has at most $2^{2s}$ distinct prime factors (as they’re all at least $2$). Thus, for $s$ sufficiently large, the probability that $p$ divides $N(\alpha)$ given $p$ prime is:

\begin{aligned} \mathbb{P}(N(\alpha) \equiv 0 \pmod{p} | p \text{ is prime})& = \frac{|\lbrace \text{primes } \mid N(\alpha)\rbrace |}{|\lbrace \text{primes total}\rbrace |} \end{aligned}

\begin{aligned} & \leq \frac{2^{2s}}{\lfloor\frac{2^{5s}}{n} \rfloor\cdot \frac{1}{6s}} \end{aligned}

\begin{aligned} & \leq \frac{2^{2s}6s}{2^{5s}/n -1} \end{aligned}

\begin{aligned} & = \frac{6sn2^{2s}}{2^{5s}-n} \end{aligned}

\begin{aligned} & \leq \frac{6s2^{3s}}{2^{5s}-n} \end{aligned}

As $n$ is fixed, for $s$ large enough, this is at most $2^{-s}$. This completes the second part of the proof. □

I dislike the ending of this proof, mostly because the paper ignores the fact that it’s rounding. It’s definitely true, but I think it just demonstrates my mathematical immaturity for wanting to point it out.

But now we have an “effective” way to get primes that hopefully do not divide the norm!

Algorithm

First, we should say what we’re hoping to achieve.

Complexity Classes

We’re just going to be focused on two complexity classes here, specifically $\text{coNP}$ and $\text{BPP}.$

A problem is in the class $\text{coNP}$ if the no-instance of the problem can be proven in polynomial time. This stands for the complementary questions of NP type.

Consider the fact that satisfiability is clearly NP (the proof certificate is some boolean assignment that works, and the proof is verifying it). Then, unsatisfiability is in coNP, where the question is “does this Boolean expression evaluate to false on all inputs?” The proof certificate is exactly the same.

This other class is $\text{BPP}$, or Bounded-error Probabilistic Polynomial time. Specifically, a problem is in $\text{BPP}$ if for all inputs which it should answer yes, it gets it right more than $3/4$th of the time, and if for all inputs which it should answer no, it gets it wrong less than $1/4$th of the time.

In some sense this is just saying “majority” rules.

Big Result

So, time for the big result.

thm. The CIT problem is in $\text{BPP}$ assuming GRH, and is in $\text{coNP}$ unconditionally.

Proof. The proof itself will be the algorithm, and we will prove its correctness along the way.

The input to the problem is some algebraic circuit $C$ and integer $n$, both written in binary, of combined size $s$. We write $f \in \mathbb{Z}[x]$ to be the polynomial that $C$ represents.

We output ‘zero’ if we think that $f(\zeta_n) = 0$, and ‘non-zero’ if we don’t.

First, we pick some $p$ uniformly at random from

\begin{aligned} \lbrace q \in \mathbb{N}: q\leq 2^{5s}, q \equiv 1 \pmod{n}\rbrace . \end{aligned}

On average, it should take $O(s)$ random samples until we get a prime $p$.

Say $p$ is prime, with $p \equiv 1 \pmod{n}$. Again, for the sake of rendering, let $A = \mathbb{F}_p^{\times}.$ Now, pick $h$ uniformly at random from

\begin{aligned} \left\lbrace a \in A \mid \bigwedge_{\substack{2 \leq q < 10 \log_2(p-1) \ q \mid p-1}} a^{\frac{p-1}{q}} \not\equiv 1 \pmod{p}\right\rbrace . \end{aligned}

With probability at least $0.9$ this is a primitive root. We bound the error by assuming that $h$ is primitive. Then $\omega_n = h^{(p-1)/n}$ is a solution to $\Phi_n$ in $\mathbb{F}_p$ by a previous lemma.

Then we have two cases. If $f(\zeta_n) = 0$, then $\overline{f}(\omega_n) = 0$, where $\overline{f}$ is the reduction of $f$ in $\mathbb{F}_p$. In this case we output ‘Zero.’ Note the only source of error is if $h$ is not a primitive root. This means on inputs that should evaluate to zero, we get them correct at least $9/10$ths of the time, which is larger than $3/4$ths.

If instead $f(\zeta_n) \neq 0$, then we output ‘Non-zero’ if $\overline{f}(\omega_n) \not \equiv 0 \pmod{p}$, which happens when $p \not \mid N(f(\zeta_n))$. Note this happens with probability at least $1 - 2^{-s}$. Note for all nontrivial circuits, we have $s > 2$, and then $2^{-s} < 1/4$, so we have bounded the error in the other case.

So, under GRH, the errors line up. Note that everything here is polynomial time, as evaluating a polynomial in $\mathbb{F}_p$ has a maximum possible element, so it is bounded time to compute.

So, we have to modify this algorithm for it to lie in $\text{coNP}$, which means we need to figure out the no-certificate and proof.

Suppose that $f(\zeta_n) \neq 0$. Then, we use the second part of the scary unconditional bound.

Let $C_1, C_2 > 0$ be the constants from the theorem on $\pi_{n, a}$. Then, let $s’ > M = \max(4s, (s-\log_2(C_1))/C_1)$. Note $M$ grows $O(s)$.

Then, as $n < 2^{s} = C_12^{s - \log_2(C_1)} < C_12^{C_1s’}$, we have

\begin{aligned} \pi_{n, 1}(2^{s’})& \geq \frac{C_22^{s’}}{\varphi(n)\sqrt{n}\log_2(2^{s’})} \end{aligned}

\begin{aligned} & \geq \frac{C_22^{s’}}{s’\varphi(n)\sqrt{n}} \end{aligned}

\begin{aligned} & \geq 2^{2s} \cdot \frac{C_22^{s}}{s’} \end{aligned}

So, we need to set $s’$ such that $C_22^s > s’.$ As $C_2$ is constant, there exists $s$ sufficiently large such that $(M, C_22^{s})$, as $M$ grows linearly. So, for $s$ sufficiently large, we have

\begin{aligned} \pi_{n, 1}(2^{s’})& > 2^{2s}. \end{aligned}

Remember that $N(f(\zeta_n)) < 2^{2^{2s}}$ has at most $2^{2s}$ distinct prime factors. What this tells us is there exists some $p \equiv 1 \pmod{n}$ such that $p$ is prime, does not divide $N(f(\zeta_n))$, and $p < 2^{s’}$.

Then, the polynomial length certificate of non-zeroness of $f(\zeta_n)$ is the factors of $p-1$ and a primitive root $h$ of $\mathbb{F}_p$, which can be proven to be primitive by considering all $h^{(p-1)/q} \not \equiv 1 \pmod{p}$ for $q \mid p-1$.

Then, you compute $\omega_n = h^{(p-1)/n}$, which is an $n$th primitive root of unity in $\mathbb{F}_p$. Then, as $p$ does not divide $N(f(\zeta_n))$, we have $\overline{f}(\omega_n) \not \equiv 0 \pmod{p}$. This proves that $f(\zeta_n) \neq 0$, and as such, CIT is in $\text{coNP}$ unconditionally. □

And that’s pretty much it! The only part I don’t feel comfortable on here is saying that it takes polynomial time to find that prime at the beginning, but I digress.

Monte-Carlo

Note that this can be made into a proper Monte-Carlo algorithm (as we sample at different primes) by utilizing the Miller-Rabin test (a probabilistic test for primality).

For sake of time and succintness, I’m not going to prove the correctness of this algorithm (yikes, 4 counts of not proving big things!). Instead, I’m just going to write down the algorithm.

We are given some $n$ and want to see if it is prime. We write $n-1$ as $2^kd$ for $d$ odd. Choose $a \in \mathbb{Z}/n\mathbb{Z}$. Compute the sequence $a^{n-1}, a^{(n-1)/2}, \ldots, a^{(n-1)/2^k}$. Note if $n$ is prime, then this sequence is only $\pm 1$’s, or in general, it must start out as $1$s until it hits a $-1$. Output yes if this is the case, and no otherwise.

In general, the probability that any composite number $n$ passes this test is at most $1/4$th, which puts Miller-Rabin in BPP.

I don’t actually understand the bit in the paper, as it feels like its pulling the polynomial exponents out of nowhere.

As this is doing only choosing one element, we need $O(s)$ random bits to get it to have error at most $4^{-s}$, and as we’re doing exponentiation, we need $O(s^3)$ arithmetic operations over $\mathbb{F}_p$. Still polynomial, still BPP.

Then, as we have to do this $O(s)$ times to find a prime $p$, we expect to do $O(s^4)$ arithmetic operations. For some reason, the paper says we need $O(s^3)$ random bits, but I don’t understand where this comes from, as as only seem to do randomized things $O(s^2)$ number of times.

Then when we compute the primitive root of unity, you need $O(s^3)$ many operations to check if its in the set, and then $O(1)$ random bits to get something from the set. Then computing the reduced polynomial can be done in $O(s)$ time.

So everything is polynomial, so it is randomized Monte-Carlo.

I feel like this last section is dirty and wrong. I don’t like it. I need to revisit it post talking to people, since this doesn’t feel accurate at all. However, it’s not the core idea (in my opinion), as the BPP algorithm is what matters more.

Worries

I think this is me being an immature mathematician, but I am forever worried by the “for sufficiently large” elements claims. What if we aren’t large enough? In some sense, we have an upper bound on $p$, so we need to motivate that it is large enough to satisfy the proposition and the condition, which I believe is really only dealt with at the end when showing its in $\text{coNP}$. Inherently, you need $p$ to be large enough so that when you pick it, the probability from the technical lemma gaurentees the probability is at least $0.9$. But also, we only need to beat $0.75$, so it works out.

I left those 4 things unproven. Specifically, the ring of integers in a cyclotomic field is $\mathbb{Z}[\zeta_n]$, the fundamental theorem of elementary symmetric polynomials, the GRH bound, and the fact that Miller-Rabin lies in BPP.

I feel as though it’s important to get that out of the way before moving on to the future.

The Rest of the Paper

The rest of the paper worries about variations of the CIT problem. First, it talks about the Bounded-CIT problem, in which case we are given an upper bound on its syntatic degree.

The syntatic degree of an algebraic circuit is defined recursively. The syntatic degree of the input vertices is all $1$. For an addition vertex, it is the maximum of the two vertices pointing into it. For a multiplication vertex, it is the sum of the two vertices pointing into it. This reflects adding and multiplying polynomials.

Note, however, that algebraic circuits take monomials as input, and so it is only a weak notion of “degree.”

However, you can get a randomized NC algorithm for Bounded-CIT. Nick’s Class is the class of problems that can be solved on polynomially many cores, each in logarithmic time. This is done by way of numerical computation, as the idea is once you are sure of how close you are, then it must be zero. Note that the algorithm is randomized, so it lies in randomized NC.

The next section talks about compressed words and powerful skew circuits. This has to do with the fact that polynomial testing is the same as cehcking two compressed words, but I will not go into that here.

The next section is on an NC algorithm for Sparse-CIT, which deals with algebraic circuits with only $+$ gates. And in some sense that makes sense, as this is the simplest class of algebraic circuits, so of course its a lot easier! The proof itself requires spaces of vanishing sums.

Finally, the paper finishes by considering diagonal circuits, which considering polynomials of the form $f = \sum_{i=1}^s g_i^{d_i}$ where $g_i$ are linear forms and $d_i$ are integers. This is a generalization of Sparse-CIT, in some sense, and they prove that if this is solvable in polynomial time, then the polynomial identity question for algebraic circuits of size $s$ and degree $d \leq s$ is solvable in $s^{O(\sqrt{d})}$ time. They then go on to show that under GRH, Diagonal CIT is in fact solvable in polynomial time.

And that goes to show there’s a lot of rabbits, all the way down.

Cyclotomics?

And besides? Why only Cyclotomics? There is future work on this here. Arc (the browser) classified as “Quantum Algorithms Research,” though the paper doesn’t have a single mention of quantum in it?

Anyway, the idea is that Galois conjugates act nicely. When we have the evaluation map from before, note that $\omega_n$ is really any Galois conjugate of the $n$th root of unity. This is the same notion of why you can’t really distinguish between $i$ and $-i$ in finite fields.

However, if you wanted to do this over real radicals, you might end up with a Galois conjugate inside of the finite field, which means that the technical lemma about factoring the evaluation map might not immedaitely hold. This is because simply adjoining the rationals with a real radical isn’t itself Galois.

That’s hopefully it! If you want the PDF instead, drop me an email, and I’m happy to send it over.