Core Library: Proving Theorems
Proving Geometric Theorems about Ruler-and-Compass Constructions
We introduce a new approach to proving classical theorems
about ruler-and-compass constructions. Our approach is
a randomized one -- by testing the conjecture on
randomly generating instances of a ruler-and-compass construction.
Our prover is based on a generalization of the Schwartz-Zippel
Lemma about the randomized zero testing for polynomials.
Basically, we generalize the lemma for radical expressions
(which also has division and square roots).
This result has independent interest.
A version of this prover is in the Core Library distribution
(version 1.2 onwards).
But we hope to distribute a more full-scale
version (with GUI interface, etc) at this website in the future.
For technical details, see our paper
Randomized Zero Testing of Radical Expressions
and Elementary Geometry Theorem Proving,
by D. Tulone, C. Yap and C. Li,
in Proc. Int'l Workshop on Automated Deduction
in Geometry (ADG'00), Zurich, Sep 25-27, 2000. The full version can
also be found in LNCS/LNAI 2061.
Evaluation of our Prover
Geometric theorem proving is an active area of research.
There are three general approaches:
(1) Groebner bases,
(2) Wu's Method, and
(3) Cell decomposition.
Method (1) is very general, but its worst case time is double-exponential.
Method (2) proves theorems in complex geometry
(or geometry based on any algebraically closed field) and in the worst
case is only single-exponential in complexity.
Method (3) is a universal method for real geometry, and despite
considerable theoretical advances in the 1990's, it remains slow in practice.
Our approach is restricted to only ruler-and-compass theorems,
and is based on randomization. It is closely
related to J.W. Hong's ``proving by example''.
Our method has the potential to be one of the fastest methods
for this class of theorems for two reasons:
(a) it is based on random testing, and
(b) radical expressions which is precisely the
class of algebraic expressions needed in ruler-and-compass theorems.
Our current implementation is straighforward
application of the Core Library, and not optimized.
For non-linear theorems, we are considerably
slower than S.C.Chou's implementation of Wu's method
(but, as we said, Wu's method is really about complex geometry).
For real geometry, our method is the fastest for this class of theorems.
Another interesting property: our method can
quickly reject false theorems (rejection of
theorems has no error in our method). This property
is not available in methods based on (2) or (3).
This property is useful in practice, where a researcher
may want to test many conjectures, and quickly reject false ones.
Download the prover (April 2001).