×

zbMATH — the first resource for mathematics

Boolean ideals and their varieties. (English) Zbl 1318.13045
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.

MSC:
13P15 Solving polynomial systems; resultants
06E20 Ring-theoretic properties of Boolean algebras
06E30 Boolean functions
68W30 Symbolic computation and algebraic computation
12Y05 Computational aspects of field theory and polynomials (MSC2010)
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Software:
PolyBoRi
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Atiyah, M. F.; MacDonald, I. G., Introduction to commutative algebra, (1969), Addison-Wesley Reading, MA · Zbl 0175.03601
[2] Bardet, M.; Faugère, J.-C.; Salvy, B.; Spaenlehauer, P.-J., On the complexity of solving quadratic Boolean systems, J. Complex., 29, 1, 53-75, (2013) · Zbl 1255.65090
[3] Brickenstein, M.; Dreyer, A., Polybori: a framework for Gröbner-basis computations with Boolean polynomials, J. Symb. Comput., 44, 9, 1326-1345, (2009) · Zbl 1186.68571
[4] Brickenstein, M.; Dreyer, A.; Greuel, G.-M.; Seelisch, F.; Wienand, O., New developments in the theory of Gröbner bases and applications to formal verification, J. Pure Appl. Algebra, 213, 8, 1612-1635, (2009) · Zbl 1164.68019
[5] Cerlienco, L.; Mureddu, M., From algebraic sets to monomial linear bases by means of combinatorial algorithms, Discrete Math., 139, 73-87, (1995) · Zbl 0834.13019
[6] Cox, D.; Little, J.; O’Shea, D., Ideals, varieties, and algorithms, (2007), Springer
[7] Felszeghy, B.; Ráth, B.; Rónyai, L., The lex game and some applications, J. Symb. Comput., 41, 6, 663-681, (2006) · Zbl 1128.13012
[8] Ferrarello, D.; Fröberg, R., The Hilbert series of the clique complex, Graphs Comb., 21, 4, 401-405, (2005) · Zbl 1095.13022
[9] Gerdt, V.; Zinin, M., A pommaret division algorithm for computing Gröbner bases in Boolean rings, (ISSAC ’08, (2008)), 95-102
[10] Hendricus, J.; Lint, V., Introduction to coding theory, (1982), Springer-Verlag New York
[11] Sato, Y.; Inoue, S.; Suzuki, A.; Nabeshima, K.; Sakai, K., Boolean Gröbner bases, J. Symb. Comput., 46, 5, 622-632, (2011) · Zbl 1211.68519
[12] Schwartz, J. T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 4, 701-717, (2011) · Zbl 0452.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.