Boolean ideals and their varieties (Q2348121)

This paper is concerned with ideals in \(R = \mathbb{Z}_2[x_1,\dots,x_n]/(x_i^2-x_i, i=1,\dots,n)\). The ring \(R\) is a Boolean ring: every element is idempotent. An immediate consequence is that every ideal is principal. For example \((x_1,x_2) = (x_1x_2 + x_1 + x_2)\). For a general ideal (as a function of \(n\)) it is however not quick to write down the generator of an ideal in \(R\) (given several generators of the same ideal). The bottleneck is an explosion in the number of terms. In fact, when it comes to complexity theory, a major source of motivation for the study of \(R\) is the SAT problem of satisfyability of Boolean clauses. The main thread of this paper is a study of the relationship between the variety of an ideal \(I\subset R\) and the exponents of the monomials of the generator of \(I\). To see the connection, let \(\phi : R\to R\) be the following map. Given \(f\in R\), first compute the variety of \(f\) in \(\mathbb{Z}_2^n\). Next turn each point in the variety into a monomial, using the point as the exponent vector. Finally, sum the resulting monomials to get \(\phi(f)\). One main result of this paper is that \(\phi^4\) is the identity and on the way to this result the author notes many interesting and useful properties of ideals in~\(R\). The methods are Gröbner-free, but the paper also gives a nice account of the connections to Gröbner-basis theory and discusses complexity theoretic implications.