an algebraic variety for a boolean circuit

Question

There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$.

I mean there is polynomial reduction $F$ such that for every boolean circuit $g(x_1,\ldots, x_n)$ the corresponding system of polynomial equations $F(g) = \begin{cases} f_1(x_1, \ldots, x_n)=0 \\ \ldots \\ f_m(x_1, \ldots, x_n)=0 \end{cases} $

satisfies the following property: $ \forall (x_1, \ldots, x_n) \in \mathbb{F}_2^n: g(x_1, \ldots, x_n)=1 \Leftrightarrow (x_1,\ldots, x_n)$ is the solution of $F(g)$.

So, every boolean circuit corresponds to an algebraic set. To use power of algebraic geometry we wish this set has some nice properties. Is there a polynomial reduction such that every circuit corresponds to an absolute irreducible algebraic set?

UPD: in fact it is also interesting to find answers on weaker questions: is there a reduction to an algebraic variety with poly$(n)$ equations, can this reduction be calculated by using poly$(n)$ memory and so on.

Answer 1

Are you willing to allow adding additional coordinate variables $y_1,\ldots,y_m$ that are unused in $g$? (I mean that, for any $x_1,\ldots,x_n,y_1,\ldots,y_m \in \mathbb{F}_2$, the variety will have the $\mathbb{F}_2$-point $(x_1,\ldots,x_n,y_1,\ldots,y_m)$ iff $g(x_1,\ldots,x_n)=1$. Note that I am asserting the equivalence for an abitrary value of the $y_j$, not just with the existence of such a value: so it is enough if I have an unlimited supply of unused variables to draw from.)

If so, the following can be done: find $f_1,\ldots,f_m \in \mathbb{F}_2[x_1,\ldots,x_n]$ as you described. We can assume that the $f_j$ have degree at most $1$ in each variable and are linearly independent over $\mathbb{F}_2$. Define $\widehat{f_j} \in \mathbb{F}_2[x_1,\ldots,x_n,y_1,\ldots,y_m]$ by $\widehat{f_j} := y_j^2 - y_j - f_j$ (the minus signs are purely decorative here, of course, and are merely there to emphasize that this is an Artin-Schreier equation). Since for $z\in\mathbb{F}_2$ the equation $y^2 - y - z = 0$ in the unknown $y$ over $\mathbb{F}_2$ has a solution iff $z=0$, in which case it has both $y=0$ and $y=1$, the variety $V := \{(\forall j) \widehat{f_j}=0\}$ defined by the $\widehat{f_j}$ has the property I stated above. It remains to determine whether it is absolutely irreducible.

Now the morphism from $V$ to $\mathbb{A}^n$ consisting of projecting to the first $n$ coordinates is étale. This is simply by the Jacobian criterion: $\frac{\partial}{\partial y_j}\widehat{f_{j'}} = \delta_{j,j'}$ (with $\delta_{j,j}=1$ and $\delta_{j,j'}=0$ if $j\neq j'$, of course). See, e.g., Milne's Lectures on Étale Cohomology, prop. 2.1. In particular, $V$ is smooth (or just use the Jacobian criterion directly for smoothness), so to show that it is geometrically integral, it is equivalent to show that it is geometrically connected (see, e.g., here).

Now this in turn is equivalent to the field extension $L = K(y_1,\ldots,y_m)$ of $K := k(x_1,\ldots,x_n)$ (where $k$ is the algebraic closure of $\mathbb{F}_2$) generated by the equations $y_j^2 - y_j - f_j$ being of the right degree (namely, $2^m$). But these equations are Artin-Schreier equations, and by Artin-Schreier theory (Lang, Algebra, chapter VI theorem 8.3), it is enough for the $f_j$ to be $\mathbb{F}_2$-linearly independent with a span in direct sum with $\wp K := \{h^2-h : h\in K\}$. But since we assumed that the $f_j$ were $\mathbb{F}_2$-linearly independent and their span consists entirely of polynomials of degree $<2$ in each variable, which are certainly not in $\wp K$ except for zero, this is indeed the case.