Pascal Schreck
email: schreck@unistra.fr

On the Mechanization of Straightedge and Compass Constructions

Keywords: Straightedge and compass constructibility, triangle problems, geometric knowledge-based systems, Wu's method, regular chains

The geometric constructions obtained with only straightedge and compass are famous and play a special role in the development of geometry. On the one hand, the constructibility of figures is a key ingredient in Euclid geometry and, on the other hand, unconstructibility gave birth to famous open problems of the ancient Greece which were unlocked only in the nineteenth century using discoveries in algebra. This paper discusses the mechanization of straightedge and compass constructions. It focuses on the algebraic approaches and presents two methods which are implemented; one is due to Lebesgue and the other one was jointly designed by Gao and Chou. Some links between the algebraic approach of constructions and synthetic geometry are described.

Introduction

Apart from their practical use in architectural or mechanical design, geometric constructions play a very special role in mathematics. Historically they are the constructive face of the axiomatization of geometry by the ancient Greeks. In addition to the fact that the result of a construction problem is an algorithm, one can see this fundamental aspect of Greek geometry as a middle ground with the constructive Chinese point of view of mathematics [START_REF] Chemla | Les neuf chapitres -Le classique mathmatique de la Chine ancienne et ses commentaires[END_REF], Wu(2008)]. Despite its antiquity, this constructive design of geometry sounds singularly in the modern conception of mathematics and particularly in the context of computational mathematics.

The ancient Greeks considered straightedge and compass as effective tools for representing idealized lines and circles, then straightedge 1 and compass constructions, RC-constructions in short, gained a special status in geometry that remains to this day. This is especially true in education where they are an inexhaustible source of problems for exercising the imagination and the rigor of students, or as a recreational pastime [Wernick(1982), Euclidea(2016Euclidea( -2018))]. It is also worth citing educational software of dynamic geometry, like the precursor Cabri Géomètre and the renowned GeoGebra [START_REF] Laborde | Cabri-géométre: A Microworld of Geometry for Guided Discovery Learning[END_REF], [START_REF] Hohenwarter | Combination of dynamic geometry, algebra and calculus in the software system geogebra[END_REF]], that made geometry more empirical and more accessible to students.

Interestingly, RC-construction are also famous because they gave rise to problems impossible to solve which were open for about two millennia. These problems were solved thanks to a radical change of point of view about geometry rooted in "Cartesianization" of geometry and progress in algebra with Galois results on solvability of polynomial equations. As often, it was useful to get out of a theory to obtain an impossibility result about that theory. These works stressed the difference between constructibility and construction: solving a problem with straightedge and compass immediately answers the question of constructibility, but not knowing a construction does not mean that a problem is not RC-constructible. Conversely, knowing that a problem is RC-constructible does not necessary gives a (usable) construction. In a previous work with Pascal [START_REF] Mathis | Determining automatically compass and straightedge unconstructibility in triangles[END_REF]], we exploited algebraic results to automatically check a whole corpus, namely the Wernick's and Connelly's lists, about RC-constructibility of triangle problems [Connelly(2009)]. We noticed that it is easier to show that a problem is RC-unconstructible than the opposite. And when we showed that a problem was RC-constructible, we sometimes had no idea about the geometric constructions. This paper discusses this issue by studying two constructive methods due to Henri Lebesgue and to Xiao-Shan Gao and Shang-Ching Chou.

It has to be noted that the ancient Greeks knew how to solve RC-unconstructible problems like angle trisection or doubling the cube by using smart tools to draw loci more powerful than lines and circles. Conversely, the folklore of geometric constructions contains several results about less powerful tools like, for instance, using a rusted compass instead of a compass, or only a compass and no straightedge. The former example is a classical problem for students in geometry, and the second one is also classical but far from obvious. But, radically different tools can be considered. With the work of Margharita P. Beloch in 1936[Hull(2011)], origami, or rather computational origami, has regained popularity both from the practical/artistic and the mathematical points of view [Alperin(2000), [START_REF] Hiss | Formalizing polygonal knot origami[END_REF]Ida, Ghourabi, and Takahashi, Justin(1987)]. We do not discuss further these domains and we restrain ourselves to straightedge and compass constructions.

The rest of the paper is organized as follows. Section 2 presents the domain of straightedge and compass constructions and its two synthetic and algebraic faces. Section 3 focuses on the algebraic aspects of constructions, in particular the use of the Wu method and the works of Lebesgue and Gao & Chou. Section 4 describes some examples of application and briefly discusses the qualities and defects of the algebraic approach.

2 Geometric RC-constructions Geometric RC-constructions are known for millennia. But, despite polished mathematical definitions, they must be carefully specified when it comes to mechanizing them. This section discusses the specific features and how to handle them in a computational approach.

Definition and discussion

First, RC-constructibility can be classically defined as follows (this definition comes from a French book dedicated to mathematics teachers [Carréga(1981)]):

Definition 1 (RC-constructibility) Given a finite set of points B = {B 0 , . . . , Bm} in the Euclidean plane, a point P is RC-constructible from the set B if there is a finite set of points {P 0 , . . . , Pn} such that P = Pn, P 0 ∈ B and every point P i (1 ≤ i ≤ n) is either a point of B or is at the intersection either of two lines, or of a line and a circle, or of two circles, themselves obtained as follows:

any considered line passes through two distinct points from the set {P 0 , . . . , P i-1 }; -any considered circle has its center in the set {P 0 , . . . , P i-1 } and its radius is equal to the distance P j P k for some j < i and k < i.

The sequence of these points with their basic constructions in terms of intersections between lines and circles is called a RC-construction of point P .

A line is said RC-constructible from B if it contains two distinct points RCconstructible from B.

A circle is said RC-constructible from B if its center is RC-constructible from B and there are two points M and N RC-constructible from B such that M N equals its radius.

Consequently, for proving that a point or a line or a circle is RC-constructible from B, it suffices to define such a sequence of points, in addition the proof should exhibit the lines and circles used for defining these points, and also a proof of correctness. In many textbooks, the following example comes just after that definition:

Given a line l and a point A, it is possible to construct with straightedge and compass the line m perpendicular to l and passing through A.

The construction is easy, but the problem does not fit this definition. In fact, we have to construct or to choose two distinct points on l, to use them for the construction and to prove that the result does not depend on that choice. Usually, basic axioms for geometry impose that a line has to contain at least two or three points, or in other words, within a constructive approach, we suppose that we have a function yielding two points from a line: classically these points do not have to be RC-constructible from B since they are forgotten after the construction, but when it comes to discussing what is the underlying geometry this issue becomes questionable. We do not press this point further, but if one wants to implement a software for RC-construction, this question has to be answered. In most of the frameworks for RC-construction, this question is side-stepped by giving this construction as a primitive.

A construction problem therefore consists in a specification of a figure made of geometric relations between given points, lines or circles and sought points, lines or circles. Now, the question is "what kind of relations?". For instance, if we consider technical drawing, another domain where geometric constructions were widely used, these relations are currently called geometric constraints and are mainly related to dimensions: there are standards in this regard and CAD softwares take them into account. But the fun, in mathematics, is to impose original constraints: for instance, how to draw the bisectors of two lines which meets outside the sheet of paper? Or how to draw a perpendicular with a wood square having a broken corner? This kind of relations also tightly relies on the subtended geometry. For instance, Wu's metric geometry does not consider an order on the points of a line, then the notions of orientations are out of reach. On the other hand, Wernick's and Connelly's corpora deal with some remarkable points of the triangle and their relations with its vertexes in the R 2 Euclidean plane. These considerations must be taken into account especially when it comes to using algebra in this context.

Also, the initial points can be given in an absolute way, say by giving their coordinates in some reference system, or, alternatively, they can be given as parameters, or free points in the dynamic geometry parlance. The latter case is more problematic since the problem can be solved for some particular configurations and not for others. For instance, it is possible to cut the right angle in three using only straightedge and compass, but apart from a null set, it is not possible to do it for any angle. We face here a well known problem in rigidity theory or in mechanical geometry theorem proving where an assertion can be either generally true (that is true except for degenerate cases) or generally false, or even, true on parts/false on parts [START_REF] Botana | On the unavoidable uncertainty of truth in dynamic geometry proving[END_REF]]. This also should be taken into consideration especially when algebra is involved.

Let us now turn to the question of the form of the expected result. We said in Definition 1, that the proof of the constructibility could be constituted by a RCconstruction, that is, a sequence of points with their basic construction in terms of intersection between lines and circles. But having now, free points to consider, it could happen that:

the configuration of the free points leads to a degenerate case, -in the case of multiple intersection, like circle-circle intersection, both points lead to a solution or on the contrary, only one point leads to a solution (how to chose it?), -there are two or more different constructions producing different figures, some or all of them, meeting the requirements according to the parameters values.

Consider the following statement:

Statement 21 Two parallel lines l 1 and l 2 , and three points A on l 1 , B on l 2 and C being given in addition to a fixed length k, produce a RC-construction for a line L passing through C and cutting line l 1 in M and line l 2 in N such that AM + BN = k (See Fig. 1). This problem is RC-solvable if every solution can be constructed using only straightedge and compass from a base set containing lines l 1 , l 2 , points A, B and C, and two points giving length k.

k l L C A B N l 1 2 M K
The resolution is not complicated but a bit tricky. After adding a new point K on line l 1 such that AK = k, it is easy to see on the figure that M KN B is a parallelogram, hence the midpoint I of segment BK should also be the midpoint of segment M N . The sought line is then line CI whose RC-construction is easy to get. In fact, this is a rough analysis of the problem, there are indeed several issues:

what happens if I = C? -more subtly, what happens if C is on the line parallel to l 1 through I? -we choose one point K such that AK = k but there is another point symmetrical wrt A meeting this requirement. Do we get the same solution with both choices? -we said above that M KN B is a parallelogram (without explanations), but it also could happen that M KBN is a parallelogram (and M KN B is a cross quadrangle). In this case, a solution is the line passing through point C and parallel to line BK.

The situation is a bit more complicated than expected. We have two kinds of constructions: one is using the midpoint of (M, N ), let us call it construction of type I, and the other one is using the direction of line M N , construction of type d. Several cases can occur, we can have (See Fig. 2):

no line L at all, -two lines L 1 and L 2 : one of type I and one of type produced by a Prolog software prototype called Progé that I implemented a long time ago during my PhD (see [Schreck(1993), Schreck(1994)] for more details).

The ad-hoc geometric programming language contains special control structures like conditional and kind of iterative instructions. It was designed to implement logical structures expressing solvability into procedures. We will see below, that it is possible to give it an algebraic meaning.

RC-(un)constructibility and algebra

Proving the impossibility of having such a program of construction is more problematic. Let us spend a moment about the notion of RC-unconstructibility (or RC-unsolvability for a problem). A problem is RC-unsolvable if there are nondegenerate real solutions which are not RC-constructible.

As said in the introduction, the domain of RC-constructions is famous because of unsolvable problems like squaring the circle or doubling the cube. These problems are related to the RC-construction of numbers. Let us recall the definition:

Definition 2 (RC-construction of numbers) Given a finite set of points B = {B 0 , . . . , Bm} in the Euclidean plane, a number a is said RC-constructible from B if one can construct using only straightedge and compass a point P whose abscissa is a. A number is RC-constructible (without mention of a base set) if it is RCconstructible from {O, I}, point O having coordinates (0, 0), and I, (1, 0). It is not complicated to see that all the rational numbers are RC-constructible since there is a construction to perform the sum and the difference of any constructible numbers and then we are able to construct any integer from O and I (see Fig. 3, remark that the given construction adds algebraic distances and thus, it works for addition and substraction). On the same figure, we give a construction for the product of two constructible numbers -the construction of the quotient is Table 1 A complete construction program automatically produced by software Progé. Notice that this is Prolog code, in fact a big Prolog term, and all the variables noted with uppercase in the statement are here in lower case. Also, the names of auxiliary objects (points, lines, . . . ) are automatically given, for instance point00 taken in list00 corresponds to point K on the figure. Moreover, the existence of the intersection point of lines is not discussed in this program. 3 Constructions for the arithmetic operations. On the top of the figure, sum of a = OA and b = OB, point O is any point not on the x axis, K is the midpoint of OO , and J is the midpoint of O A; in the middle, product of a = OA and b = OB, O has coordinates (0, 0), U has coordinates (1, 0) and OP = ab (note that divisions can be constructed in he same way); at the bottom, square root of a = OA, V has coordinates (-1, 0), the circle has diameter V A and √ a = OR.

B S J O A a b B' O' K B b O A P 1 a U a 1 A R O V m a Fig.
very similar. A simple construction allows to graphically compute the square root of a constructible number. With these constructions we get that the set of RCconstructible numbers together with addition and multiplication is an Euclidean2 subfield of R. A more precise result expresses that this field is the smaller Euclidean subfield of R.

There are two famous results about RC-constructible numbers. The first one is related to the previous observation:

Theorem 1 (Wantzel) A number a is RC-constructible if and only if it can be expressed by an arithmetic expression with radicals, that is, involving only numbers in Q, arithmetic operations and square root extractions.

A consequence of this theorem is known as Wantzel's result which states that any number a RC-constructible is algebraic and [Q[a] : Q] = 2 n for some n. This result is sufficient to prove that one cannot double the unit cube using only straightedge and compass, that the trisection of π 3 angle is RC-unsolvable, and since π is not algebraic (proved by Lindenmann in 1882), that squaring the circle is also impossible.

As noted before, we consider numbers constructible from {O, I} and then, polynomials with coefficients in Q (or Z without loss of generality). This extensible to some field F which classically is a transcendental extension of Q of the form Q(u 1 , . . . , um) where u 1 , . . . , um are parameters. Also note that Wantzel's result only gives a necessary condition and cannot be used to prove that a number is RC-constructible. The following theorem is a necessary and sufficient condition for a number to be RC-constructible (see [Stewart(2003)] for instance).

Theorem 2 (Galois) An algebraic number on F is constructible if and only if the splitting field of its minimal polynomial P , is an extension of degree 2 m for some m over F . The degree of this extension, 2 m , is also the cardinal of the Galois group of P .

The latter theorem is sufficient to prove both RC-constructibility and RCunconstructibility of an algebraic number specified by its minimal polynomial and providing that we can compute the Galois group of this polynomial. In fact, this a key ingredient in the method used by the author and Mathis to automatically check and prove the RC-constructibility status of all the problems in both Wernick's and Connelly's corpora [START_REF] Mathis | Determining automatically compass and straightedge unconstructibility in triangles[END_REF]] which describe about 250 problems about triangle construction. But, when a problem is RC-solvable, Galois theorem does not give the result, that is, a procedure to construct the solutions using only straightedge and compass.

In the nineties, two methods were described and implemented to give an answer to this issue by describing a way to compute the algebraic expression -using only arithmetic and square root operations-of a constructible number. Having this expression, it is possible to translate it into elementary operations that can be performed using straightedge and compass.

The first one comes from lectures by Lebesgue in "Collège de France" in 1942 [ Lebesgue(1950)] simplified and implemented by Chen in Maple. This work was the result of an end-of-studies internship on a subject directed by the author and Dufourd and, for now, only a master thesis is available [Chen(1992)]. The second one is due to Gao and Chou and it is more in the Chinese tradition reinvigorating by Wu [Wu(2008)]. It was published by Computer Aided Design journal (CAD, Elsevier) in 1998 [START_REF] Gao | Solving geometric constraint systems. II. A symbolic approach and decision of Rc-constructibility[END_REF]].

It is to be noted that the problem of solving a RC-solvable univariate polynomial has been addressed by [START_REF] Landau | Solvability by radicals is in polynomial time[END_REF]] in the case where the coefficient field is Q. But, their algorithm is focused on univariate polynomials in Q[X] and does not extend to problems with parameters. Moreover, as far as we know, it has no been implemented yet. To our knowledge, the methods of Lebesgue and Gao-Chou are the only methods which fully address the problem of RC-solvability.

The next sections present these works and compare them on some simple examples.

RC-construction and algebra

In the previous section, we focused on the algebraic characterization of RC-constructible numbers. Now, we want to practically solve more general construction problems by using algebra. It is worth to notice that we place ourselves within the geometrical framework described by Wu, namely the metric geometry: we only consider statements that can be translated into polynomial equations. In a corpus approach like the problems from the lists of Wernick and Connelly, the translation can be automatically done [START_REF] Schreck | Automatic constructibility checking of a corpus of geometric construction problems[END_REF]].

Thus, a RC-construction problem becomes an algebraic system to be solved using only arithmetic and square root operations on a given field K which usually is a finite extension of Q: in the following, we assume that K = Q(u 1 , . . . , um) where u 1 , . . . , um are independent parameters. But treating an algebraic system is not the same as treating a single polynomial equation, and the first step consists in yielding equivalent triangular systems.

At this point, we need to ask ourselves if the needed operations are computationally feasible.

Computatbility

For commodity, we define the notion of RP-computability:

Definition 3 (RP-computability) A field F is said RP-computable if and only if:

there are data structures for representing the elements of F , -there are algorithms for computing the arithmetic operations on F , -there are algorithms for solving in F every polynomial equation in F

[X].
This definition means that such a field F can effectively be implemented and, given a polynomial with coefficients in F , we can compute all its roots belonging to F .

It is obvious that every finite field is RP-computable. The first interesting RPcomputable field is Q: data structures and algorithms for arithmetic operations are obvious, and it is well known that the rational roots of polynomial anx n + . . . a 0 whose coefficients are in Z, are of the form p/q where p is a divisor of a 0 and q a divisor of an. Using triangularization algorithms, is not difficult to prove the following theorem:

Theorem 3 A field F is RP-computable if and only if there is a factorization algorithm in F [X].
We then have the classical result:

Theorem 4 Let K ⊂ F be a field extension and µ ∈ F be either transcendental or specified by its minimal polynomial. If K is RP-computable then K(µ) is also computable.

Indeed, if µ is algebraic we can then use its minimal polynomial for the computations including the factorization of polynomials (this latter proof is very close to the Lebesgue's technique used below in section 3.3). And if µ is transcendental, the factorization process is the very same than in Q.

Then, K = Q(u 1 , . . . , um) where u 1 , . . . , um is RP-computable and the finite extensions of K are also RP-computable.

We can now go back to the RC-solvability problem.

Triangularization

In Lebesgue's book, the question of the triangularization is not well developed. But recall that there was no computer at that time and he only described a theoretical method as a proof of concept. For him, the progressive elimination of variables can be done by successive uses of Euclidean division by embedding

K[X 1 , . . . X i ] in K(X 1 , . . . X i-1 )[X i ],
that is the Euclidean domain of polynomials with coefficients in the field K(X 1 , . . . X i-1 ), thus avoiding to consider the initials of the polynomial which is not very accurate as we know it now. Moreover, after that phase, each polynomial had to be factorized since Galois theory considers irreducible polynomials.

A more disciplined approach uses the Wu-Ritt's method to produce irreducible ascending sets [Wu(1984), Chou(1988)]. More precisely, if S is the given system, the method produces k triangular systems T 1 , . . . T k such that

V (S) = V (T 1 ) ∪ V (T 2 ) . . . ∪ V (T k )
There are several papers on the subject and elimination theory, see for instance [Kalkbrener(1993), [START_REF] Kapur | Comparison of various multivariate resultant formulations[END_REF], Buchberger and Winkler(1998)] and a recent comparison in [Wang(2016)]. In the following, we will use the regular chains [START_REF]On the theories of triangular sets[END_REF]Aubry, Lazard, and Moreno-Maza] which have all the required properties, in particular by producing irreducible components, for Galois's theory. More particularly, we use the Maple RegularChains tools which are implemented by Lemaire, Moreno Maza and Xie [START_REF] Lemaire | The regularchains library in MAPLE[END_REF]Lemaire, Maza, and Xie]. Then each triangular system has to be examined separately. For each non degenerate system with real solutions, T i , we have to solve the equation by beginning with the equations with least unknowns and reporting the found values in the remaining equation. The problem is then reduced to check if the roots of a polynomial are RC-constructible and to compute them. Knowing the Galois group of a polynomial does not allow to straightforwardly compute its constructible roots. On the contrary, the two algorithms presented below take parameters into account and can be used to both check the RC-solvability and formally compute the solutions.

Lebesgue's method

Original Lebesgue's method consists in decomposing a polynomial with a high degree so called the "resolving polynomial"3 . This polynomial is built from an irreducible polynomial to be solved. In 1992, Chen with Carayol from the University of Strasbourg showed that it is useless to consider that polynomial. In fact, they proved that:

Theorem 5 (Chen and Carayol) Let x be an algebraic number on a field K such that Q ⊂ Kand P be its minimal polynomial. x is RC-constructible if and only if there is a number r in K such that P is decomposable on K( √ r).

Thus, having a minimal polynomial (that is an irreducible polynomial with leading coefficient equal to 1) P , one tries to decompose P into two factors. We present the method with a simple example.

Consider P (x) = x 4 + 2x -2, which is irreducible, and K = Q, we search r ∈ Q and r > 0 such that there is a divisor of

P in K( √ r)[X].
If P has a factor of degree 1, it means that it has a root of the form a √ r + b. Thus, -a √ r + b is also a root and then x 2 -2bx + a 2 r + b 2 should be a factor in Q[X] of P . But P is irreducible. It is then useless to search factors of degree 1.

Then, we search a divisor of degree 2, that is, of the form

F (x) = x 2 + (a + d √ r)x + b √ r + c.
Remark that, since we can chose either d or b equal to 1 or -1, we have to add the equation (d 2 -1)(b 2 -1) = 0. In the following, for the sake of simplicity, we chose d = 1 forgetting solutions with d = 0 and d = -1 if any (we will see below that the case where d = -1 can be avoided). When we divide P by F the remainder should vanish everywhere. We get the polynomial (remember that we put d = 1):

((-3a + 2b)r + (-3a 2 + 2ab + 2c -r) √ r -a 3 + 2ac + 2)x (-2ab + b 2 -c)r + (-a 2 b -2ac + 2bc -br) √ r -a 2 c + c 2 -2
since we want this polynomial to be null, we have the four equations:

       -3a 2 + 2ab + 2c -r = 0 -a 3 + 2ac -3ar + 2br + 2 = 0 -a 2 b -2ac + 2bc -br = 0 (-2ab + b 2 -c)r -a 2 c + c 2 -2 = 0
After elimination of a, c and r by triangularizing the system using regular chains, we have the following equations in two components: where factor 4b 3 + 8b 2 + 1 is remarkable (see below). It is also interesting to note that a factor very similar to the initial equation appears: b 4 -2b -2, but this time we are not seeking for RC-solvability, we only want to know if it admits rational solutions. It is easy to see that none of the equations has rational roots. Checking the other cases: b = ±1 and d = -1 leads to the same systems. The equation is then not RC-solvable.

Let us try a RC-solvable case and consider the polynomial x 4 +2x 3 -3x 2 -2x+1. After dividing it by x 2 + (a + √ r)x + b √ r + c we get the system:

       -a 2 b + 2ab -2ac + 2bc -br + 3b + 2c = 0 (-2ab + b 2 + 2b -c)r -a 2 c + 2ac + c 2 + 3c + 1 = 0 -3a 2 + 2ab + 4a -2b + 2c -r + 3 = 0 (-3a + 2b + 2)r -a 3 + 2a 2 + 2ac + 3a -2c -2 = 0
Then using regular chains, we find three irreducible components: two of them have no rational roots and the third one admits the single solution a = 1, b = 0, c = -1, r = 2 giving the factor

x 2 +(1+ √ 2)x-1. The other factor is x 2 +(1- √ 2)x-1.
The four solutions of these equations are of the form:

-(1/2) √ 2 -1/2 ± (1/2) 7 ± 2 √ 2 .
This method immediately extends to higher degree by searching factors of degree 2, 3, . . . with an Euclidean division and making the remainder vanish: a factor F of degree k of P (x) in K[ √ r] is of the form:

x k + m k-1 x k-1 + . . . m 0 + √ r(n k-1 x k-1 + . . . n 0 ) .
And the remainder of P by the division by F is a polynomial of the form:

(A k-1 (m, n) √ r + B k-1 (m, n))x k-1 + . . . A 0 (m, n) √ r + B 0 (m, n)
where m = (m 0 , . . . m k-1 ), n = (n 0 , . . . n k-1 ) and, A i (m, n) and B i (m, n) are polynomials with coefficient in K. This remainder equals the null polynomial if and only if F is a factor of P . This leads to an algebraic system with 2k + 1 and 2k equations: we just add the equation (n 0 -1)(n 1 -1) . . . (n k-1 -1) = 0 as we did in our example. Now, we have to solve this system in K which, by chance, is RP-computable.

If we find some solution in r which permits the factorization, we continue with each factors until the polynomial is discomposed in factors of degree 1 [Lebesgue(1950), Chen(1992)].

Gao and Chou's method

Gao and Chou used another characterization of RC-constructible numbers:

Theorem 6 Let K be a field as in the previous theorem and p be an algebraic number on K. p is RC-constructible if and only if there is a sequence of numbers α 1 , . . . αn such that

-[K(α 1 ) : K] = 2, -[K(α i+1 , . . . , α 1 ) : K(α i , . . . , α 1 )] = 2, for i = 1, . . . n -1, -p = αn
In our case, saying that a root p of polynomial P (x) = x 4 + 2x -2 means that the algebraic system has x 2 = p as solution (and x 1 = α 1 with the notations of the above theorem):

x 2 1 -r = 0 x 2 2 + (x 1 + a)x 2 + bx 1 + c = 0
where r, a, b, c are in Q and all the variables are unknowns. But, eliminating x 1 in this system leads to the minimal polynomial of p which is P (x). It then comes:

x 4 + 2x -2 ≡ x 4 + 2ax 3 + (-r + 2c + a 2 )x 2 + (2ac -2br)x -b 2 r + c 2 .
Symbol ≡ stands for equality of polynomials. Thus coefficients of both polynomials can be identified, and we get:

       2a = 0 -r + 2c + a 2 = 0 -2br + 2ac -2 = 0 -b 2 r + c 2 + 2 = 0
Eliminating a, r and c leads to the equation b 4 (4b 3 + 8b 2 + 1) = 0 (*). The obvious solution b = 0 gives by replacement the equation c 2 + 2 = 0 which has no rational solution. The second factor 4b 3 +8b 2 +1 has not rational root. Thus the polynomial P is not solvable by square radicals.

For the RC-solvable polynomial x 4 + 2x 3 -3x 2 -2x + 1, the identification with the polynomial x 4 + 2ax 3 + (a 2 + 2c -r)x 2 + (2(ac -br))x -rb 2 + c 2 gives the system:

       b 2 r -c 2 + 1 = 0 2 -2a = 0 -a 2 -2c + r -3 = 0 -2ac + 2br -2 = 0
The triangularization yields two irreducible systems: the first one does not have any rational solution and the second one correspond to the solution found by Lebesgue's method. This method is extended to higher degrees but even for polynomial of degree 8, the system to be solved is very complicated.

Comparison of the two methods with an example

Both methods are quite similar but Gao-Chou method seems more efficient than the Lebesgue's one, at least for the quartic equations. But the idea of factorizing the polynomial was not fully exploited by Lebesgue and computing the remainder brings complications.

Let us re-examine the first example where

P (x) = x 4 + 2x -2. Using conjugation, we can see that if this polynomial is reducible in Q( √ r)[x],
we have:

x 4 + 2x -2 ≡ (x 2 + (a + √ r)x + b √ r + c)(x 2 + (a - √ r)x -b √ r + c)
identifying the coefficients, we get the system:

       2a = 0 a 2 + 2c -r = 0 2ac -2br -2 = 0 -b 2 r + c 2 + 2 = 0
which is exactly the same system as in Gao-Chou method. The comparison for higher degrees is difficult because the polynomials found are very complicated. We guess that this idea of factorizing the minimal polynomial by identification could lead to some simplifications, but this is a subject for future research.

Examples and further discussions

In the previous sections, we only give tiny examples, without parameters, and we observe that the results are complicated. We will see these methods at work on some classical examples of construction problems.

A simple example

Let us begin with Example 21 of section 2. In order to translate the problem into algebra, we have to choose the coordinate system. We fix point B to coordinates (0, 0) and line l 2 will be the x-axis. Then, as point A can be chosen almost anywhere, it has coordinates (p 2 , p 3 ) where p i are parameters. It is the same for C whose coordinates are (p 4 , p 5 ). The last parameters correspond to the sum of distances AM + BN which is fixed to be equal to p 1 (that is k = p 1 , we change the name for the sake of homogeneity). Then, points M and N are respectively located at (x 1 , p 3 ) and (x 2 , 0). Expressing that points C, M and N are collinear is straightforward and corresponds to the polynomial:

f 1 : (x 2 -x 1 )p 5 -p 3 (x 2 -p 4 ) .
It is also not difficult to translate the constraint AM + BN = p 1 , and we get:

f 2 : (x 1 -p 2 ) 4 + x 4 2 + p 4 1 -2((x 1 -p 2 ) 2 p 2 1 + x 2 2 p 2 1 + (x 1 -p 2 ) 2 x 2 2 ) .
After triangularization by using Maple's RegularChains tools, we obtain four irreducible systems. We describe and comment on the first and the third ones:

First system. (p 3 -p 5 )x 2 -p 3 p 4 + x 1 p 5 = 0 (p 3 -2p 5 )x 1 + (p 3 -p 5 )p 1 + (-p 3 + p 5 )p 2 + p 3 p 4 = 0
with the additional conditions

p 3 -2p 5 = 0 p 3 -p 5 = 0
These conditions express that point C cannot be on l 1 and cannot be the line parallel to l 1 through I. This is a linear system and the solutions are easy to obtain:

x 1 = -p 1 p 3 -p 1 p 5 -p 2 p 3 + p 2 p 5 + p 3 p 4 p 3 -2p 5 and x 2 = p 1 p 5 -p 2 p 5 + p 3 p 4 p 3 -2p 5 and we have x 1 + x 2 = -p 1 + p 2 . This corresponds to a construction of type I with point K to the left of A. The second system (not described here) corresponds to the construction of type I with point K to the right of A. These constructions are valid even in the degenerate case where l 1 = l 2 .

Third system

(p 3 -p 5 )x 2 + x 1 p 5 -p 3 p 4 = 0 p 3 x 1 + (-p 3 + p 5 )p 1 + (-p 3 + p 5 )p 2 -p 3 p 4 = 0
with the additional conditions

p 3 = 0 p 3 -p 5 = 0
The conditions now express that point C cannot be on l 1 and line l 1 has to be distinct from line l 2 . The solutions of that system are expressed by:

x 1 = p 1 p 3 -p 1 p 5 + p 2 p 3 -p 2 p 5 + p 3 p 4 p 3 and x 2 = - p 1 p 5 + p 2 p 5 -p 3 p 4 p 3 .
We observe here that x 1 -x 2 = p 1 + p 2 meaning that this corresponds to a construction of type d with point K to the right of A. The fourth system corresponds to a construction of type d with point K to the left of A.

We retrieve our four kinds of constructions, but the conditions are not as precise as the regions we found in Section 2. This is because using algebra we implicitly consider complex numbers and the distance between two points can be negative leading to more solutions than considering only real number.

This example illustrates the link between structuring the solution into different cases for both geometric construction programs and the decomposition of irreducible ideals but it does not show how the methods of section 3 can be used. This is the aim of the next example.

Example 119 from Wernick's list

This problem comes from a list of problems established by Wernick. The goal is to construct, if it is possible, a triangle being given three characteristic points among the vertices, the circumcenter, the midpoints of the sides and the gravity center, the feet of the altitudes and the orthocenter, and finally, the feet of the inner bisectors and the incenter. If a problem is not RC-solvable, a proof of its RC-unsolvability has to be produced. Problem 119 can be expressed as it follows:

Statement 41 (Wernick 119) Let I, G, Ha be three given points, construct points A, B and C such that I is the innercenter of triangle ABC, G its isobarycenter and Ha the foot of the altitude from A.

This problem is RC-solvable [START_REF] Schreck | Automatic constructibility checking of a corpus of geometric construction problems[END_REF]]. Our proof of its RCsolvability uses the algebraic approach. We first choose a cordinate system by taking the following coordinates: I(0, 0), Ha(1, 0) and G(a, b) where a and b are parameters. Then, translating the constraints into algebraic expressions where (x A , y A ), (x B , y B ) and (x C , y C ) are the coordinates of points A, B and C to be constructed, we get the system:

                       -x A x 2 B y B -x A x 2 B y C + 2x A x B x C y B -x A y 3 B + x A y 2 B y C + x 3 B y A + x 3 B y C -x 2 B x C y A -x 2 B x C y B + x B y A y 2 B -2x B y A y B y C + x B y 2 B y C + x C y A y 2 B -x C y 3 B = 0 x 3 A y B + x 3 A y C -x 2 A x B y A -x 2 A x B y C -x 2 A x C y A -x 2 A x C y B + 2x A x B x C y A +x A y 2 A y B + x A y 2 A y C -2x A y A y B y C -x B y 3 A + x B y 2 A y C -x C y 3 A + x C y 2 A y B = 0 (x A -1)(x C -1) + y A y C = 0 (1 -x B )(y C -y B ) -y B (x B -x C ) = 0 3a -x A -x B -x C = 0 3b -y A -y B -y C = 0
The triangularization of this system gives six irreducible systems with the last five being degenerate and the first one containing 5 linear equations and one polynomial equation with the single unknown y C : and to compute its Galois group by identification [Hulpke(1999)]. The order of this group is 8, hence the problem is RC-constructible.

Py C : c 4 y 4 C + c 3 y 3 C + c 2 y 2 C + c 1 y C + c 0 = 0 N B C M A P G Fig.
It is also possible to use Gao-Chou's method: considering quadratic polynomial Pyc the equation (*) of degree 3 described in section 3.4 is now a sum of 237 monomials in y, a and b where y is the unknown. This polynomial is reducible meaning that it has solutions in Q(a, b); hence the equation in y C is RC-solvable and triangle ABC is RC-constructible. Maple gives a factor of this equation and then, a solution for y. This solution can be used to find r, as described above, and the coefficient of a quadratic equation with coefficients in Q(a, b, √ r) whose y C is a solution. It is is clear that the exact formulation of this solution does not matter when it comes to producing a RC-construction.

The next example shows that this can be worst.

Cramer Castillon

The problem of Cramer-Castillon is a classical problem which is RC-constructible, and, even if the known construction is complicated, it is very simple to express:

Statement 42 (Cramer-Castillon) Let A, B and C be three given points and G be a given circle, construct three points M , N and P on G, such that, A is on line M P , B is on line N P and C is on line M N (See Fig. 4)

Without loss of generality, we can suppose that the radius of G equals 1 and its center has coordinates (0, 0). We can also suppose that C is on the x axis. Naming the coordinates of points, we get: A(p 1 , p 2 ), B(p 3 , p 4 ), C(p 5 , 0) and M (x 1 , x 2 ), N (x 3 , x 4 ), P (x 5 , x 6 ). Thus we have the system:

               f 1 : (x 1 -p 1 )(x 6 -p 2 ) -(x 2 -p 2 )(x 5 -p 1 ) f 2 : (x 1 -p 5 )x 4 -(x 3 -p 5 )x 2 f 3 : (x 5 -p 3 )(x 4 -p 4 ) -(x 3 -p 3 )(x 6 -p 4 ) f 4 : x 2 1 + x 2 2 -1 = 0 f 5 : x 2 3 + x 2 4 -1 = 0 f 6 : x 2 5 + x 2 6 -1 = 0
But unfortunately, the triangularization of this system fails due to a lack of memory using a standard 2018 PC with 8Go of memory.

On the other hand, replacing the parameters by integers chosen at random, the triangularization is easily done and produce several degenerate cases (seven with my examples) and one containing only linear and quadratic equations. Thus, we can suspect that this problem is RC-constructible but we have no proof of it.

Discussion and last example

These examples highlight some aspects of the algebraic approach in RC-construction:

algebra allows a systematic way to check if a problem is RC-solvable or not; -when a problem is RC-constructible, it is possible to have the exact solutions and to extract a RC-construction; -these techniques are in practice limited by a heavy complexity both in time and in space, and the current computer tools are unable to perform even the triangularization of a small algebraic system with parameters;

The picture is rather disturbing: the algebraic tools are very powerful but poorly usable to find the solutions. Let us say that, first it is important to know the existence of these methods as they fix some theoretical limits. Second, they are useful when it comes to proving RC-unconstructibility since they are actually almost the unique tool we have. For instance, with Pascal Mathis, we use them to automatically check the RC-constructibility (that is, proving RC-constructibility or finding counter-example) of both Wernick's and Connelly's lists. We then found the status, constructible, unconstructible or miss-constrained, for all the problems of these lists and resolving this way some open problems: most of these previously open problems are RC-unconstructible with some notable exceptions like Problem 119 of the Wernick's list and Problem 108 of that list which I present below. Notice that we proved that Problem 119 is RC-constructible and we are, in theory, able to produce a RC-construction, but the expression will be awful and not in the spirit of geometric construction.

Let us now present problem 108 of Wernick's list: Problem 108 is stated as RC-unconstructible in [Meyers(1996)]. But, using the algebraic tools described above, we find that this problem is RC-solvable. Moreover it is easy to prove this.

Thus, we consider the general case with the parameterized polynomial system by putting coordinates (0, 0) for point Ta, (1, 0) for point Ma and (a, b) for point H. The triangularization yields after filtering the following triangular system:

               x C + x B -2 = 0 -a 2 -by A + x 2 B + 2a -2x B = 0 y C = 0 y B = 0 x A -a = 0 a 3 + aby A -a 2 + y 2 A = 0
which is obviously RC-solvable, no need for Galois theory. The solutions are:

y A = a 2 -b ± √ b 2 -4a + 4 x C = 1 ± a 2 + b.y A -2.a + 1 x B = 2 -x C .
Hence, we can produce a construction with only straightedge and compass mimicking the calculi. For instance, the expression for y A immediately translates into a geometric construction (See Fig. 6) It can be observed that a simple calculation gives rise to a very complicated construction which has to be carefully handled. However, this construction is not satisfactory for the RC-construction fans since the fun of an elegant geometry reasoning is missing. Now, in this example, we see that the quantity b 2 -4a + 4 = (2 -a) 2 + b 2 -a 2 plays a special role. This seems to indicate that the point P at location (2 -a, -b) could be interesting. Actually point P is a characteristic point of triangle ABC4 : P is the symmetric of H with respect to Ma. This leads us to explore the figure very carefully and we find two useful properties:

a yA yA b2-4a b 4a b2 -1 4 4 1 b -1 O 1 a -b circle for square root extraction of = b2-4a+4 sqrt( ) = b2-4a+4 ∆ ∆ ∆ ∆ ∆ sqrt( ) ∆ -b-sqrt( ) -b+sqrt( ) ∆ a(-b+sqrt( )) Fig. 6 Construction of y A = a 2 (-b + √ b 2 -4a + 4) by constructing the sequence of numbers b 2 , 4a, b 2 -4a, b 2 -4a + 4, √ b 2 -4a + 4
, and so on.

the inner angle bisector from A is also the inner angle bisector of the altitude AH and the ray AO where O is the circumcenter of triangle ABC. -point P is also the symmetric of A with respect to O.

The construction is then as follows (see also Fig. 7). Line BC is known since point Ma and Ta are given. By projecting H on BC we have the foot Ha of the altitude from A and the altitude HHa itself. From the first property above, Ta is the center of the circle Γ tangent to HHa and AO, and passing through Ha. This circle is then constructible. Point P is also constructible: it is the symmetric of H wrt Ma. Since P is on line OA, this line passes through P and is tangent to circle Γ : line OP is constructible by using the circle with diameter P Ta. O is constructible as it is the intersection of this tangent and the perpendicular to line BC passing by Ma. We then have point A, the circumcircle of ABC and, finally, points B and C.

This suggests a heuristic approach to help solving a construction problem:

check if the problem is RC-constructible or not, -if it is, try to solve it algebraically and check the quantities under the square roots, -ask for a characteristic point related to this quantities with data mining techniques (for instance, see [START_REF] Song | Retrieving geometric information from images: the case of hand-drawn diagrams[END_REF] for techniques of exploration of a figure and features extraction) and find the associated geometric relations.

Of course, the pertinence and the properties of the points found with heuristics have to be formally verified, for instance by using a CAS.

Fig. 7 A simple geometric construction for example 3, done by using point P .

Related works

On the one hand, considering the mathematical aspects of RC-constructions, thousands of articles and hundreds of books have been published over the centuries. In particular, following Lindenmann's result on the transcendence of π, the French "Académie des sciences" refused to publish the many false proofs of the problem of squaring the circle. Yet, they still receive papers claiming it solved! Recently, in the field of logic, especially intuitionistic logic in foundations of geometry, some works were already done within the framework of constructive geometry [Beeson(2012)].

On the other hand, as far as I know, very little has been done on the automation of ruler and compass constructions. Apart from the algebraic approaches described in this paper, the other works mainly follow a synthetic geometric approach.

The work of Scandura et al. seems to be the first one to describe a systematic way, with higher order geometric rules, to solve RC-constructions problems [START_REF] Scandura | Higher order rule characterization of heuristics for compass and straight edge constructions in geometry[END_REF]. The geometric aspects are derived from Polya's work [Polya(1965)], but this work is more focused on pedagogical considerations about structural learning. To our knowledge, there is no implementation of this study.

In 1975, Buthion also worked on geometric construction and implemented his work in FORTRAN. Unfortunately, this work is only published in French [Buthion(1979)]. Without mentioning straightedge and compass, Aldefeld implement a synthetic geometric solver adapted to Computer Assisted Design, CAD, [Aldefeld(1988)] using ideas similar to those of Buthion. Also adopting a synthetic point of view, I developed in 1992 the notion of geometric universe and geometric construction program. This work is supported by a knowledge based system to exploit this notion to produce a highly parameterizable software able, inter alia to solve RC-problems taking degenerate cases and multiple possibilities into account. This approach for solving construction problem was called universal approach [Schreck(1994)]. This work also was specialized by Mathis and Schreck to CAD in particular by using decomposition of problems invariant by direct isometries or even by similarities [START_REF] Dufourd | Geometric construction by assembling solved subfigures[END_REF]Schreck, Schreck andMathis(2006)].

It also worth citing the work of Gao et al. about the so-called reparameterization of 3D CAD-systems by using the so-called Locus Intersection Method (LIM) [START_REF] Gao | Solving spatial basic geometric constraint configurations with locus intersection[END_REF]. In this work, LIM is implemented by a simple solver whose result is in turn used by another solver based on a sampling method to numerically yield the solutions.

More recently Marinković and Janičić worked on a corpus approach in automatic RC-construction [START_REF] Marinković | Towards understanding triangle construction problems[END_REF]]. The problem is to fully automatically solve Wernick's corpus by giving a RC-construction when it is possible, and then to automatically prove that the construction really meets the statement specifications. For RC-unconstructible problems, they follow a reduction method to RC-irreducible problems [START_REF] Schreck | Constructibility classes for triangle location problems[END_REF] or algebraic methods [START_REF] Marinkovic | Computer theorem proving for verifiable solving of geometric construction problems[END_REF].

Finally, Gulwani and his teams at Microsoft in program synthesis presented a very original approach using techniques of automatic program synthesis from a specification [START_REF] Gulwani | Synthesizing geometry constructions[END_REF].

Conclusion

This paper mainly compares two different algebraic methods which theoretically are able to solve RC-construction problems, more precisely, able to detect if a problem is RC-solvable or not, and if it is, to express the solutions using only arithmetic operations and square root. We see on some examples that the algebraic tools used are effective in proving unconstructibility but when it comes to computing the solutions of constructible problems, they lack efficiency. However, some progress in information retrieval could possibly exploit the algebraic forms of the solutions, in simple cases, to retrieve relevant geometric constructions which is very helpful in the domain of computer aided education.

Fig. 1

 1 Fig. 1 Figure corresponding to Statement 21

  dpdir(a, di) l2 := dpdir(b, di) circle00 := ccr(a, k) list00 := [intercl1(circle00, l1), intercl2(circle00, l1)] for point00 in list00 do list01 := [pll(point00,m,b,n), pll(point00,m,n,b)] for case00 in list01 do if case00 = pll(point00, m, b, nl2) verify(m is_onl l) verify(n is_onl l) verify(c is_on l) verify(dist(a,m) + dist(b, n) == k) verify(l1 diff l2) end

b 4 -

 4 2b -2 = 0 or, in the second component 4b 3 + 8b 2 + 1 = 0

  d, or both of the same type I or d, -infinitely many lines if C = I or C = I .Back to RC-construction, we can see that, when line L specified by the statement exists, it is always RC-constructible. The problem is then RC-solvable and the very solution of Statement 21 is a procedure to construct all the possible lines L in every cases. This can be formalized by the notion of program of construction which is a formal way to express geometric constructions. With the previous example, we could get the program given on Table1. This program is automatically Different areas where point C can be located according to the construction cases: I (resp. I , d, d ) means that point I (resp. point I , direction d, direction d ) is used in the RC-construction, ∅ indicates that there is no solution (constructible or not) in the area. If C equals I or I , there are infinitely many solutions. If C is on an oblique line there are two solutions on the frontier of two solution area and only one solution on a frontier with an area labeled by ∅.

			I,I'
		I',d'				I,d
	K'	φ	I'	A	d,d'	I	K	φ
		I',d			B		I,d'
		d			I,I'		d'
	Fig. 2

4

  The problem ofCramer and Castillon (Statement 42) wherec 4 = 19683a 9 -59049a 8 +(78732b 2 +61236)a 7 +(-183708b 2 -20412)a 6 +(118098b 4 + 166212b 2 -4374)a 5 + (-196830b 4 -72900b 2 + 2754)a 4 + (78732b 6 + 148716b 4 + 10692b 2 + 324)a 3 + (-78732b 6 -61236b 4 + 3564b 2 -108)a 2 + (19683b 8 + 43740b 6 + 18954b 4 -756b 2 -21)a -6561b 8 -8748b 6 -3078b 4 -108b 2 -1, the other coefficients c 3 , . . . c 0 being of the same kind. Maple is able to check if polynomial Py C is irreducible on Q(a, b)[X]

  Statement 43(Wernick 108) Let Ta, Ma and H be three given points, construct a triangle ABC such that H is its orthocenter, Ma the midpoint of edge BC and Ta the foot of the inner bisector from A Illustration of Statement 43: points M a, T a and H are given, and the problem is to construct the triangle ABC (the gray lines are the inner bisector from A and two altitudes, and they are figured here to recall the definitions of T a and H).

	A
	H
	B
	Ma
	Ta
	C
	Fig. 5

Euclidean means stable by the square root operation.

Résolvante de Galois in French

It is to be noted that there are thousands of such characteristic points as it can be seen in Clark Kimberling's Encyclopedia of Triangle Centers (http://faculty.evansville.edu/ck6/ encyclopedia/ETC.html)[START_REF] Narboux | Towards A Certified Version of the Encyclopedia of Triangle Centers[END_REF]