# Theorem of Three Circles in Coq

@article{Zsido2013TheoremOT, title={Theorem of Three Circles in Coq}, author={Julianna Zsido}, journal={Journal of Automated Reasoning}, year={2013}, volume={53}, pages={105-127} }

The theorem of three circles in real algebraic geometry guarantees the termination and correctness of an algorithm of isolating real roots of a univariate polynomial. The main idea of its proof is to consider polynomials whose roots belong to a certain area of the complex plane delimited by straight lines. After applying a transformation involving inversion this area is mapped to an area delimited by circles. We provide a formalisation of this rather geometric proof in Ssreflect, an extension… Expand

#### One Citation

A Decision Procedure for Univariate Real Polynomials in Isabelle/HOL

- Computer Science
- CPP
- 2015

An Isabelle/HOL proof method was implemented to prove interesting statements about the number of real roots of a univariate real polynomial and related properties such as non-negativity and monotonicity. Expand

#### References

SHOWING 1-10 OF 28 REFERENCES

Formal proofs in real algebraic geometry: from ordered fields to quantifier elimination

- Computer Science, Mathematics
- Log. Methods Comput. Sci.
- 2012

A formalization of discrete real closed fields in the Coq proof assistant of an algebraic proof of quantifier elimination based on pseudo-remainder sequences following the standard computer algebra literature on the topic. Expand

A Revision of the Proof of the Kepler Conjecture

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2010

The current status of a long-term initiative to reorganize the original proof of the Kepler conjecture into a more transparent form and to provide a greater level of certification of the correctness of the computer code and other details of the proof is summarized. Expand

Isolating real roots of real polynomials

- Mathematics, Computer Science
- ISSAC '09
- 2009

A bisection algorithm for root isolation of polynomials with real coefficients that is deterministic and has almost the same asymptotic complexity as the randomized algorithm of [12]. Expand

When Newton meets Descartes: a simple and fast algorithm to isolate the real roots of a polynomial

- Mathematics, Computer Science
- ISSAC
- 2012

A novel algorithm denoted NewDsc, which iteratively subdivides an initial interval which is known to contain all real roots of a univariate square-free polynomial f with integer coefficients and performs exact (rational) operations on the coefficients of f in each step to isolate the real roots. Expand

Programming and certifying a CAD algorithm in the Coq system

- Mathematics, Computer Science
- Mathematics, Algorithms, Proofs
- 2005

The aim is to program a reflectional decision procedure for the Coq system, using the CAD, to decide whether a (possibly multivariate) system of polynomial inequalities with rational coefficients has a solution or not. Expand

Formalized algebraic numbers: construction and first-order theory. (Formalisation des nombres algébriques : construction et théorie du premier ordre)

- Mathematics, Computer Science
- 2012

A formalization of algebraic numbers and their theory is presented and in Coq/SSReflect a framework to work with quotient types is provided and a complete library about ordered and normed number algebraic structures is provided. Expand

Efficient real root approximation

- Mathematics, Computer Science
- ISSAC '11
- 2011

The method provides a certified answer for arbitrary real polynomials, only requiring finite approximations of the polynomial coefficient and choosing a suitable working precision adaptively, and proves a bound on the bit complexity of the algorithm in terms of degree, coefficient size and discriminant. Expand

A formal study of Bernstein coefficients and polynomials†

- Computer Science, Mathematics
- Mathematical Structures in Computer Science
- 2011

A criterion for the existence of a single root in an interval and the correctness of the de Casteljau algorithm for computing Bernstein coefficients efficiently are proved. Expand

Formalization of Bernstein Polynomials and Applications to Global Optimization

- Mathematics, Computer Science
- Journal of Automated Reasoning
- 2012

A formalization in higher-order logic of a practical representation of multivariate Bernstein polynomials and an algorithm for finding lower and upper bounds of the minimum and maximum values of a polynomial is presented. Expand