Boolean ideals and their varieties

Ring-theoretic properties of Boolean algebras (06E20) Boolean functions (06E30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Solving polynomial systems; resultants (13P15) Symbolic computation and algebraic computation (68W30)

Abstract: We consider ideals in the ring

m a t h b b Z_{2} [x_{1}, l d o t s, x_{n}]

that contain the polynomials

x_{i}^{2} - x_{i}

for

i = 1, l d o t s, n

and give various results related to the one-to-one correspondence between these ideals and the subsets of

m a t h b b Z_{2}^{n}

. We also study the standard monomials with respect to the lexicographical ordering for these ideals and derive a distribution result.

Review text

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.

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

PolyBoRi

This page was built for publication: Boolean ideals and their varieties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2348121)