ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.3. <s> A tamper-evident top closure lid construction for a container. The lid is integrally formed from a plastic cover member, the member carrying a main and a secondary paperboard insert on its upper surface, the member and insert being bonded together. The plastic cover member has an integral tongue to define, upon tongue pivoting, an opening in the member. The main paperboard insert is hinged about a contiguous pivot axis. The secondary insert carries a pull tab. If formed from a brittle plastics material, pulling the pull tab breaks the plastics member at its tongue hinge. The pull tab is so formed as to indicate tampering to a prospective purchaser of the container provided with the top closure lid construction of this invention. The lid may also be provided with an upstanding rim to facilitate stacking. <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.3. <s> A sweep auger radially mounted within a storage bin is rotatable horizontally across the bin floor about a vertical axis located centrally of the bin. An upright distributing auger arranged coaxially with the vertical axis has its lower end adjacent the inner end of the sweep auger and its upper end spaced from the roof of the bin. The sweep auger is of a construction such that for each complete revolution across the bin floor it moves predetermined volumes of material over given axial sections thereof for delivery to the distributing auger. The material or grain discharged from the distributing auger is spread across the top surface of the grain stored in the bin. All of the grain in the bin is thus acted upon continuously for circulation through the bin for drying purposes. Field grain may be introduced through the roof of the bin for concurrent distribution and circulation with the grain already in the bin. A bin unloading auger is located below the bin floor to receive grain directly from the sweep auger for discharge exteriorly of the bin. <s> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.3. <s> Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets. <s> BIB003 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.3. <s> Let $P\in\mathbb{Z[X]}$ be a polynomial of degree p with coefficients in the monomial basis of bit-size bounded by τ. If P is positive on [−1,1], we obtain a certificate of positivity (i.e., a description of P making obvious that it is positive) of bit-size O(p 4(τ+log 2 p)). Previous comparable results had a bit-size complexity exponential in p and τ (Powers and Reznick in Trans. Am. Math. Soc. 352(10):4677–4692, 2000; Powers and Reznick in J. Pure Appl. Algebra 164:221–229, 2001). <s> BIB004 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.3. <s> We prove explicit bounds on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semi-algebraic set $S \subset \mathbbm{R}^k$ defined by a quantifier-free formula involving $s$ polynomials in $\mathbbm{Z}[X_1, ..., X_k]$ having degrees at most $d$, and whose coefficients have bitsizes at most $\tau$. Our bound is an explicit function of $s, d, k$ and $\tau$, and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of $S$ (including the unbounded components). While asymptotic bounds of the form $2^{\tau d^{O (k)}}$ on these quantities were known before, some applications require bounds which are explicit and which hold for all values of $s, d, k$ and $\tau$. The bounds proved in this paper are of this nature. <s> BIB005 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.3. <s> We give a specific method to solve with quadratic complexity the linear systems arising in known algorithms to deal with the sign determination problem. In particular, this enable us to improve the complexity bound for sign determination in the univariate case. <s> BIB006
Certain quantitative results in metric semi-algebraic geometry. In the case D = Z, a careful analysis of the algorithm in Theorem 2.15 produces an explicit upper bound on the radius of a ball centered at the origin which is guaranteed to meet every semi-algebraically connected component of any P-semialgebraic set in terms of s, d, k and a bound on the bit-size, τ , of the coefficients of P. This and related bounds of this type are often needed in designing other algorithms (for instance, in order to compute certificates of positivity by sub-division method as done in BIB004 ). The following rather technical but completely explicit estimate appears in BIB005 (the same paper contains several other explicit estimates of similar types). Notation 3. Given an integer n, we denote by bit(n) the number of bits of its absolute value in the binary representation. Note that . . , X k ] and suppose that P ∈ P have degrees at most d, and the coefficients of P ∈ P have bitsizes at most τ . Then there exists a ball centered at the origin of radius intersecting every semi-algebraically connected component of the realization of every realizable sign condition (resp. realizable weak sign condition) on P. were known before BIB003 BIB002  . One point which needs some explanation is the fact that s plays a role in the estimate in Theorem 2.16, while it does not appear in the formula 2 . This is because the total number of polynomials of degree at most d in k variables with bitsizes bounded by τ is bounded by (2 τ +1 ) ( 2.4. Singly exponential quantifier elimination algorithms. The algorithm with singly exponential algorithm for computing sample points in every semialgebraically connected component of every realizable sign condition of a family of polynomials used in a parametrized way is a very important ingredient in designing algorithms with singly exponential complexity for real quantifier elimination. More precisely, it allows us to eliminate one whole block of variables (quantified by the same quantifier) at one time, unlike in algorithms based on cylindrical algebraic decomposition, where the elimination has to proceed one variable at a time regardless of the block structure of the quantifiers. The singly exponential algorithm for eliminating one block of variables at a time is formalized as the Block Elimination Algorithm BIB003 Chapter 14] and does the following. Given a finite family of polynomials , the Block Elimination Algorithm produces as output a family of polynomials BElim The family BElim X (P) has the following important property that justifies its name. For each semi-algebraically connected component, C ⊂ R , of each realizable sign condition of BElim X (P), the set of realizable sign conditions of P(y) ⊂ R[X 1 , . . . , X k ] stay invariant as y is allowed to vary over C. The Block Elimination Algorithm also produces a set of parametrized (by y) sample points which are guaranteed to meet each semi-algebraically connected component of the set of realizable sign conditions of P(y) ⊂ R[X 1 , . . . , X k ]. The complexity of this algorithm is bounded by , where as usual s = card P and d is a bound on the degrees of the polynomials in P. , where d is a bound on the degrees of the polynomials in P and Q. This algorithm was first discovered by Ben-Or, Kozen and Reif BIB001 and extended by Roy and Szpirglas  (see also BIB006 for recent improvements). This algorithm has also been generalized to the multi-variate case (where the zeros of Q could be positive dimensional), and this is described below in Section 3.3.