Counting Zeros Over Finite Fields Using Gr Obner Bases
Counting Zeros over Finite Fields UsingGröbner BasesSicun GaoMay, 2009
Contents1 Introduction22 Finite Fields, Nullstellensatz and Gröbner Bases2.1 Ideals, Varieties and Finite Fields . . . . . . . . . . . . . . . .2.2 Gröbner Bases . . . . . . . . . . . . . . . . . . . . . . . . . .2.3 Hilbert’s Nullstellensatz . . . . . . . . . . . . . . . . . . . . .6611213 Counting with Gröbner Bases263.1 Nullstellensatz in Finite Fields . . . . . . . . . . . . . . . . . 263.2 SM (J hx̄q x̄i) V (J) . . . . . . . . . . . . . . . . . . 284 Algorithm Analysis324.1 Analysis of Buchberger’s Algorithm . . . . . . . . . . . . . . . 324.2 Counting Standard Monomials . . . . . . . . . . . . . . . . . 355 A Practical #SAT Solver375.1 DPLL-based Approaches to #SAT . . . . . . . . . . . . . . . 375.2 Gröbner Bases in Boolean Rings . . . . . . . . . . . . . . . . 395.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 406 Conclusions and Future Work43Bibliography451
Chapter 1IntroductionGiven an arbitrary finite field Fq of size q (q a prime power) and a system ofmultivariate polynomials f1 , ., fm in Fq [x1 , ., xn ], we consider the problemof counting affine zeros of the ideal hf1 , ., fm i over Fq (in other words,the number of common solutions of f1 , ., fm in Fqn ). We will call this thecounting problem throughout.The counting problem established its importance in number theory sincethe work of Gauss on the law of reciprocity. The celebrated Riemann Hypothesis for curves over finite fields, formulated by Emil Artin and finallyproved by Andre Weil, is concerned with an explicit bound of the number of rational points on curves (i.e., varieties of dimension one) over finitefields [32].Methods for the counting problem have computational applications boththeoretically and practically. In coding theory, for the design of algebraicgeometric codes such as Goppa codes, curves with a large number of rationalpoints are needed, hence methods solving the counting problem are desirable [31]. In several primality testing algorithms, counting the number ofpoints on elliptic curves [16] and hyperelliptic curves [1] over finite fields isa crucial step.The special case of counting for polynomial systems over F2 , which corresponds to the so called model counting problem, has even wider applications.Model counting (#SAT) is the problem of computing the number of satisfying assignments to propositional formulas [7]. It is a natural generalizationof SAT – many AI and combinatorial problems, lying beyond the capacityof SAT solvers, can be effectively coded as #SAT problems, such as various probabilistic reasoning problems [2, 25, 27]. While solving SAT is onlyconcerned with whether the number of assignments is nonzero, solving the2
#SAT problem requires keeping information of all the solutions and is significantly harder. In fact, #SAT is #P-complete, where #P is a complexityclass known to contain the Polynomial Hierarchy [30].The counting problem has attracted considerable algorithmic investigation from two different communities:On the coding theory and algorithmic algebra side, several exact algorithms for certain special polynomials, as well as theoretical approximationalgorithms for more general cases, have been proposed. Schoof [28] gave thefirst deterministic polynomial-time algorithm for counting rational pointson elliptic curves over finite fields. Generalized methods for hyperellipticcurves were devised in [24, 14]. Approximation algorithms have been theoretically successful for single sparse polynomials [17, 21]. However, thegeneral problem for polynomial systems has been less amenable to approximation methods. The best algorithm so far [19, 18], which applies only toO(n)prime fields, has time complexity O(dn(m log p)O(1) ) (for prime fields ofsize p, n the number of variables, d the maximum degree of the polynomialsand m the number of polynomials).On the AI and Boolean modeling side, various practical solvers havebeen developed for #SAT. Currently, approaches for solving #SAT [20, 26,29] are mostly based on the DPLL algorithm [12] (with the exception ofthe method of knowledge compilation [11]). The basic idea is to extendthe DPLL algorithm with procedures for book-keeping the distribution ofsolutions in the search space.There does not exist an algorithm for the counting problem that is bothgeneral and practical. The approaches taken by the algorithmic algebracommunity usually involve sophisticated algebraic-geometric operations andremain only of theoretical interest so far – yet still, the most general theoretical (approximate) algorithm devised for the for polynomial systems [19, 18]is restricted to prime fields, and the worst-case runtime is doubly exponentialin the number of variables. On the other hand, although practical solvershave been implemented in the AI community for the #SAT problem, themethods are specifically devised for Boolean variables and do not extend toother fields. Furthermore, the practical solvers are far less successful thanDPLL approaches in tackling the SAT problem. In fact, effective heuristicsfor SAT usually aim at quick zooming-in on a particular satisfying assignment, while for counting the total number of satisfying assignments, thesolver needs to take the full solution space into account. For this reason,current DPLL-based #SAT solvers scale orders of magnitude lower thanSAT solvers [7].3
The main contribution of this thesis is a new method for solving thecounting problem which is both general and practical: It can be appliedto any polynomial systems over arbitrary finite fields, and has been implemented to solve #SAT, outperforming existing solvers on various benchmarks.The mathematical correctness of our method relies on a modified Nullstellensatz for finite field. Nullstellensatz is a celebrated theorem in classicalalgebraic geometry by David Hilbert, initially established for algebraicallyclosed fields (such as the field of complex numbers) [23]. We will show thatin the case of finite fields, any ideal I F [x1 , ., xn ] can be easily made intoa radical zero-dimensional ideal I 0 that preserves variety over the finite fieldF . It follows that the Nullstellensatz can be modified to a nice form specifically applicable to finite fields. Then we prove that, the monomials that donot appear in the set of leading monomials of I 0 (called “standard monomials”) generates a vector space over F that is isomorphic to the quotientring of F [x1 , ., xn ]/I 0 . As a consequence, the number of zeros of any systemof polynomials can be obtained by counting the number of correspondingstandard monomials.On the algorithmic side, our method is based on the powerful methodfrom computational commutative algebra called Gröbner bases [6, 5, 3]. AGröbner basis G for a system of polynomials S is an equivalent system thatpossesses useful properties, for example, that a polynomial f is a combinationof those in S if and only if the remainder of f with respect to G is 0.(Here, the division algorithm requires an order of a certain type on themonomials.) We will show that Gröbner basis computations provide analgorithmic method for counting the standard monomials, which is hence away of counting the zeros of the corresponding polynomial systems.However, a conceivable problem with our method can be the notoriouslyhigh computational complexity of Gröbner basis computations. It is knownthat Gröbner basis computations are at least EXPSAPCE-hard [22], whichtranslates to worst-case running time doubly exponential in the number ofvariables. But in fact, for the problem that we are solving, a careful analysisof the Buchberger’s Algorithm for Gröbner basis construction shows that itstays in single exponential time. Furthermore, we have evaluated the practical Gröbner of our algorithm in tackling practical problems. Experimentalresults show that our solver outperforms existing search-based solvers significantly on a number of benchmarks, and is competitive in general in terms ofthe size of problems (number of variables and clauses) that can be handled.The thesis is organized as follows. In Section 2, we review basic mathematical background, the theory of Gröbner bases and Hilbert’s Nullstellen4
satz. The materials are standard and can be found in [3, 9, 23]. In Section 3,we prove the modified Nullstellensatz for finite fields, and how Gröbner basescan be used in the counting problem. In section 4, we analyze the theoreticalworst-case complexity of our algorithm. In Section 5, we focus on our practical solver for the #SAT problem and show experimental results comparedwith existing solvers. Section 6 contains conclusions and discussion of futurework.5
Chapter 2Finite Fields, Nullstellensatzand Gröbner Bases2.1Ideals, Varieties and Finite FieldsDefinition 2.1.1. A monoid is a set M with an associative binary operation“ · ” and an element e G, such that, for all a G, e · a a.We use (M, ·, e) to denote a monoid defined as such, and often use Monly when no ambiguity arises. This tuple notation also applies for groups,rings and fields.Definition 2.1.2. A group is a set G with an associative binary operation“ · ”, such that(1) (G, ·, e) forms a monoid;(2) For all a G, there exists some b G satisfying b · a e.Definition 2.1.3. A monoid/group G is called commutative if for all a, b G, a · b b · a.Definition 2.1.4. A commutative ring with unity is a set R with twobinary operations “ ” and “ · ”, as well as two distinct elements 0, 1 R,such that(1) (R, , 0) forms a commutative group;(2) (R, ·, 1) forms a commutative monoid;(3) For all a, b, c R, a · (b c) a · b a · c.Since in this paper we do not need to consider any non-commutative ringsor rings without unity, we henceforth use “ring” to mean commutative ringwith unity as defined above.6
Definition 2.1.5. An element a in a ring R is called a zero divisor, ifa 6 0 and ab 0 for some b 6 0. An element is called a unit, or invertible,if a · c 1 for some c R.Definition 2.1.6. A polynomial ring R[x1 , ., xk ] over a ring R, is theset of polynomials with variables in x1 , ., xk and coefficients in R, togetherwith ordinary addition and multiplication defined over polynomials. 0, 1 R[x1 , ., xk ] are the same as in R.Definition 2.1.7. A field is a set F with two binary operations and · andtwo distinct elements 0, 1 F such that (F, , ·, 0, 1) forms a ring and everynonzero element a F (i.e. a 6 0) is invertible. A field is called a finitefield or Galois field when F is finite.Definition 2.1.8. Let R be a ring. A nonempty set I R is called an idealof R if:(1) For all a, b I, a b I;(2) For all a I, for all r R, a · r I.For any element r in R, we define addition and multiplication of r withan ideal I to ber I {r a : a I},andr · I {r · a : a I}.Then we are able to define:Definition 2.1.9. Let R be a ring and I an ideal in R. The quotient ringR/I is defined on the set:R/J {r J : r R}together with addition(r1 J) (r2 J) (r1 r2 ) J,and(r1 J) · (r2 J) (r1 · r2 ) J.Zero is naturally defined as 0 J and unity as 1 J.Definition 2.1.10. An ideal I R is a prime ideal if it is proper anda · b I implies a I or b I.7
Definition 2.1.11. An ideal I R is a maximal ideal, if for any otherideal J R, whenever I J, either J I or J R.Theorem 2.1.12. Let I be an ideal of R. Then the quotient ring R/M isa field if and only if I is a maximal ideal of R.Proof. Left to right:Suppose that R/I is a field and let J be an ideal of R properly containingI. Let a J and a 6 I. Then a I is not the zero element of R/I, and sothere exists b I R/I such that (a I)(b I) 1 I. Then ab 1 I .But since a J, ab J. Thus 1 J. Hence I is a maximal ideal.Right to left:Suppose that I is a maximal ideal of R and let a I be a non-zero elementof R/I. We need to show the existence of b I R/I with (a I)(b I) 1 I, namely, ab 1 I.Let I 0 denote the set of elements of R of the formar s for some r R, s I. Then I 0 is an ideal of R and properly contains I since a I 0 but a 6 I.Then I 0 R because of the maximality of I. In particular, then 1 M 0 andby definition, 1 ab c for some b R and c I. Then ab 1 I anda I has an inverse in R/I as required.Definition 2.1.13 (Field Extension). Let k be a field. If k 0 is a subset ofk which is closed with respect to the field operations of addition and multiplication in k and the additive and multiplicative inverses of every elementin k 0 are in k 0 , then we say that k 0 is a subfield of k, that k is an extensionfield of k 0 , and that k/k 0 (“k over k 0 ”) is a field extension.Definition 2.1.14. Let k be is a field extension of k 0 , then an element a kis called algebraic over k 0 , if there exists some non-zero polynomial p(x) withcoefficients in k 0 such that p(a) 0. Elements of k which are not algebraicover k 0 are called transcendental over k 0 .Definition 2.1.15 (Algebraic Extension). A field extension k/k 0 is calledalgebraic if every element of k is algebraic over k 0 .Definition 2.1.16 (Algebraically Closed Field). A field k is said to be algebraically closed if every polynomial in one variable of degree at least 1,with coefficients in k, has a root in k. An algebraic closure of a field k is analgebraic extension of k that is algebraically closed.8
Theorem 2.1.17. Let k be a field. There exists an algebraic closure k a ofk.The theme of our study will be the relation between ideals in the polynomial ring k[x1 , ., xn ] over some field k and the points in the k n . Thecorrespondence between the two sets can be captured by two functions: onefunction takes some set of points in k n and returns the ideal of polynomialsin k[x1 , ., xn ] that can vanish (i.e., be made zero) at these points; the othertakes an arbitrary ideal of polynomials, and returns the points in k n thatcan make these polynomials be zero. Formally speaking, (for simplicity wewrite R for k[x1 , ., xn ])Definition 2.1.18. V : (R) k n is defined asV (J) {ā k n : f (x̄) J, f (ā) 0}Definition 2.1.19. I : (k n ) R, s.t.I(A) {f R : ā A, f (ā) 0}Proposition 2.1.20. For any A k n , I(A) forms an ideal in R.Proof. For any A, 0 I(A), hence it’s not empty. For any f, g I(A), fand g vanish on A, hence f g also vanishes on A. For any f I(A) andh R, f h also vanishes on A, hence f g I(A).In all, I(A) forms an ideal in R.Definition 2.1.21. For any field k and any ideal J k[x1 , ., xn ], thevariety of J over the algebraic closure of k, written as V a (J), isdefined asV a (J) {ā k a [x1 , ., xn ] : f J, f (ā) 0}Definition 2.1.22. For any field k and a set of points A (k a )n ,I(A) {f k[x1 , ., xn ] : ā A, f (ā) 0}I(A) is easily verifiable as an ideal in k[x1 , ., xn ], called the vanishingideal of V. Definition 2.1.23. The radical of an ideal J, written as J, is defined as J {f R : r 0, f r J} . J is called a radical ideal if J J.9
Proposition 2.1.24. The radical J of an ideal J (in a ring R) is an ideal. Proof. Let a, b J be arbitrary. By definition there exists n, m N suchnmthat a , b J. Obviously J J, hence we only need to prove that Jis closed under addition.P n m i m n iSince (a b)m n n mab, each term contains either ani 0i or bm . Thus we have (a b)m n J. By definition, a b J.Lemma 2.1.25. Let Ji be ideals in k[x1 , ., xn ] and Ai be a subset of k n ,then:(1)V (J1 J2 ) V (J1 ) V (J2 )\[(2)V ( Ji ) V (Ji )(3)I(ii[\Ai ) iI(Ai )iProof. (1) Consider any point P V (J1 J2 ) k n , then all f J1 J2vanishes on P , in particular, J1 and J2 vanish on P . Thus P V (J1 ) V (J2 ).HenceV (J1 J2 ) V (J1 ) V (J2 ).On the other hand, consider any point P V (J1 ) V (J2 ). For anyf g J1 J2 , f J1 and g J2 both vanish on P . HenceV (J1 ) V (J2 ) V (J1 J2 ).T(2) Consider any point P in V ( i Ji ). Suppose P 6 V (Ji ) for all Ji ,then for each Ji there’sQsome fTi Ji such that fi does notT vanish on P .By definition of ideals, i fi i Ji , which means P 6 V ( i Ji ), leading tocontradiction. Hence\[V ( Ji ) V (Ji ).iiTOn the other hand, for each Ji we have V (Ji ) V ( i Ji ), for the reasonTthatat any point P V (Ji ), all f Ji must vanish, in particular, all f i Jimust vanish on P . Hence[\V (Ji ) V ( Ji )ii10
SS(3) For any f I( i Ai ), f vanishes on all the points in i Ai , thusf I(Ai ) for each Ai . Hence[\I( Ai ) I(Ai ).iiTOn the other hand, for any f S i I(Ai ), then f vanishes on all the pointsin each Ai , which means fi I( i Ai ).The size of a finite field can only be pn , where p is a prime number andn is a positive integer. When n 1, finite fields of size p (written as GF (p))are isomorphic to natural numbers modulo p, i.e., {0, 1, ., (p 1)}; whenn 1, finite fields of size pn (written as GF (pn )) are isomorphic to the fieldof equivalence classes of polynomials whose coefficients belong to GF (p).Proposition 2.1.26 (Generalized Fermat’s Little Theorem). For any finitefield of size q, every element a F satisfies:aq a.Proof. If a is zero, then 0q 0.If a is not zero, then a is in the cyclic multiplicative group (F/{0}, ·, 1)[23],by Lagrange’s theorem, aq 1 1.In both cases aq a.2.2Gröbner BasesDefinition 2.2.1 (Well-ordering). An order relation on Nn is a wellordering if every strictly decreasing sequenceα(1) α(2) · · ·eventually terminates.Definition 2.2.2 (Monomial Order). Define the set of monomials in k[x1 , ., xn ]to be: T {xα1 1 · · · xαnn : αi N} k[x1 , ., xn ]. A monomial order on T isa total well-ordering on T satisfying(1) For any t T , 1 t(2) For all t1 , t2 , s T , t1 t2 then t1 · s t2 · s.We give two examples of monomial order:11
Definition 2.2.3 (Lexicographic Order). Let α (α1 , ., αn ) and β (β1 , ., βn ). α lex β if in the vector difference α β Zn , the leftmostnonzero entry is positive.Definition 2.2.4 (Graded Lexicographic Order). Let α, β Nn . α grlex βifnnnnXXXXαi βi , orαi βi and α lex β.i 1i 1i 1i 1Definition 2.2.5. Let f α aα xα be a nonzero polynomial in k[x1 , ., xn ]and a monomial order. The multidegree of f is defined asPmultideg(f ) max(α Nn : aα 6 0) The leading coefficient of f is LC(f ) amultideg(f ) and the leading monomialis LM (f ) xmultideg(f ) . The leading term of f is LT (f ) LC(f ) · LM (f ).Proposition 2.2.6. Let f, g k[x1 , ., xn ] be nonzero polynomials and amonomial order, then:(1) multideg(f g) multideg(f ) multideg(g).(2) If f g 6 0 then multideg(f g) max (multideg(f ), multideg(g)).Theorem 2.2.7 (Multivariate Polynomial Division). Fix a monomial ordern and let F (f , ., f ) be an ordered s-tuple of polynomials in on Z 01sk[x1 , ., xn ] Then every f k[x1 , ., xn ] can be written asf a1 f1 . as fs rwhere ai , r k[x1 , ., xn ] and either r 0 or r is a linear combination ofmonomials not divisible by any of LT (f1 ), ., LT (fs ) (with coefficients in k).r is called the remainder of f on division by F .Proof. The existence of a1 , ., as and r can be shown by an algorithm asfollows:Algorithm Multivariate Polynomial DivisionInput: f1 , ., fs , fOutput: a1 , ., as , r1. a1 0, .as 0, r 02. p f3. while p 6 04.do12
5.6.7.8.9.10.11.12.13.14.15.16.17.18.i 1division occured falsewhile i s AND division occured falsedoif LT (fi ) divides pthenai ai LT (p)/LT (fi )p p (LT (p)/LT (fi ))fidivision occured trueelsei i 1 if division occured falsethenr r LT (p)p p LT (p)To prove that the algorithm works, we first show that(?) f a1 f1 . as fs p rholds as every stage. This is clearly true for the initial values.Now suppose it holds at one step of the algorithm. If next step is adivision step, then some LT (fi ) divide
2.1 Ideals, Varieties and Finite Fields De nition 2.1.1. A monoid is a set M with an associative binary operation \ " and an element e2G, such that, for all a2G, ea a. We use (M;;e) to denote a monoid de ned as such, and often use M only when no ambiguity arises. This tuple notation also applies for groups, rings and elds. De nition 2.1.2.
Aug 14, 2017 · 1. If dividing, move the decimal to the left the number of zeros the power of 10 has. Unnecessary Zeros in Decimals Rules- - Zeros that are before a whole number can be dropped. - Zeros at the end of a number AFTER THE DECIMAL can be dropped. - Zeros between two numbers
Method 2: Finding the vertex by averaging the zeros Here is how to use a quadratic’s zeros to find the coordinates of the vertex: First find the zeros by any method (such as factoring or the Quadratic Formula). Find the x-coordinate of the vertex by averaging the zeros (add the zeros then divide by 2).
Zeros of Polynomial Functions 1. No, the Rational Zero theorem does not guarantee that a polynomial function with integral coefficients has any real zeros, it only gives a list of possible rational zeros, i.e. possible rational zeros come from the list of the ratio of t
Zeros of Quadratic Functions De nition. The zeros of a function are the x values that make the function value 0, i.e., the x-intercepts of the function. To nd the zeros of f(x) set f(x) 0 and solve. Finding zeros of quadratic funtions: Finding the zeros of a quadra
Addition Anno’s Counting House Anno, Mitsumasa Climate Cactus Desert, Arctic Tundra Silver, Donald Climate Tropical Rain Forest Silver, Donald Counting 26 Letters and 99 Cents Hoban, Tana Counting Anno’s Counting Book Anno, Mitsumasa Counting Let’s Count Tana Hoban Counting The Great Pe
Step 1- Counting nickels and dimes by 5 and 10 and counting quarters (25, 50, 75, 100) Step 2- Counting dimes and nickels (start with the dimes) Step 3- Counting dimes and pennies and nickels and pennies Step 4- Counting on from quarters (25/75) with nickels and dimes Coin Cards (Use
4 32. Find the complex zeros of the polynomial function and write in factored form. 2 8 20. f fx x x x x Step 1: The degree of f is 4 so there will be 4 complex zeros. The potential rational zeros are : 1, 2, 4, 5, 10, 20. p q. Step 2: 2 4 9 10. fx x x x x ( ) ( ) (3 2) 2 1
SOL A2.8 - Algebra 2 - Formative Assessment Question #1 Which describes the zeros and maximum of this graph? Zeros are –2 and 2; maximum is 1. A Zeros are –2 and 2; maximum is – 1. B Zeros are –1 an
