Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 1, 151-158.

Simple Counter Examples for the Unsolvability of the Fermat- and Steiner-Weber-Problem by Compass and Ruler

St. Mehlhos

B.-Brecht-Str. 6, D-07806 Neustadt an der Orla, Germany e-mail: St.Mehlhos@t-online.de

Abstract. The purpose of this short note is to give counter examples for the unsolvability of the Fermat- and Steiner-Weber-problem by compass and ruler. The used point sets made it possible to obtain for the Fermat-problem polynomials of the degree 3 and 4. Thus, for these counter examples Galois theory and computer algebra is not necessary. In the second part is given a counter example for the construction of the true length of Steiner trees in the three-dimensional space.

1. Notations

Let n points P_{i} be given. The point M, for wich the sum ∑_{i=1}^{n} ∥P_{i}M∥ is minimal is said to be the Fermat point of the given point set. The minimal spanning tree between these points is called the Steiner tree.

2. The Fermat point in the Euclidean plane for 3 and 4 points

The constructions of the Fermat point for 3 and 4 points are simple. For a convex quadrilateral we obtain the Fermat point by the intersection of the diagonals.

In the case of a triangle Figure 1 describes the construction. The triangles BAP_{3}, CBP_{1}, ACP_{2} are equilateral. These constructions and facts of the history of these problems are described by Schreiber in [3].

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2000 Heldermann Verlag

152 St. Mehlhos: Simple Counter Examples for the Unsolvability of the …

[figure: A; B; C; M; P_{2}; P_{1}; P_{3}; Figure 1; A; B; C; D; M; Figure 2]

3. The Fermat point in the Euclidean plane for arbitrary finite point sets

Theorem 1. The construction of the Fermat point, in general, is impossible for 5 and more points of the plane.

[figure: y; x; P_{3}; P_{4}; P_{1}; P_{2}; P_{5}; M] Figure 3

Proof. Let n points P_{1}, ..., P_{n} (Fig. 3) be given with

odd n even n P_{1} = (0, \sqrt{2}) P_{1} = (0, \sqrt{1.5}) P_{2} = (0, −\sqrt{2}) P_{2} = (0, −\sqrt{1.5}) P_{3} = (0, 1) P_{3} = (0, 1) P_{4} = (0, −1) P_{4} = (0, −1) P_{5} = (2, 0) P_{5} = (2, 0) = P_{6}, and if n > 5 resp. n > 6 then P_{2i} = (0, 0) P_{2i−1} = (2, 0) P_{2i+1} = (2, 0) P_{2i} = (0, 0) (3 ≤ i ≤ \frac{n−1}{2}) (4 ≤ i ≤ \frac{n}{2}).

Let M = (x, 0) be the Fermat point. Then, f(x) = ∑_{i=1}^{n} ∥P_{i}M∥ can be calculated by the formulas

f(x) = 2(\sqrt{x^{2} + 1} + \sqrt{x^{2} + 2} ) + resp. f(x) = 2(\sqrt{x^{2} + 1} + \sqrt{x^{2} + 1, 5} ) +
2 − x + (n − 5)  2(2 − x) + (n − 6)

A necessary condition for a minimum is f′(x) = 0. The derivatives are given by

f′(x) =\frac{2x}{\sqrt{x^{2} + 1}} + \frac{2x}{\sqrt{x^{2} + 2}} − 1 and f′(x) =\frac{2x}{\sqrt{x^{2} + 1}} + \frac{2x}{\sqrt{x^{2} + 2}} − 1.

To solve the equations we put cos α = \frac{−2x}{\sqrt{x^{2}+1}} and cos β = \frac{−2x}{\sqrt{x^{2}+2}}. Thus we get

−2 cos α − 2 cos β − 1 = 0 and −2 cos α − 2 cos β − 2 = 0,
cos α = −\frac{1 + 2 cos β}{2}  and  cos α = −(1 + cos β).

Hence tan α = −\frac{1}{x} yields

tan β = −\frac{\sqrt{2}}{x} = \sqrt{2}\frac{1}{−x} = \sqrt{2} tan α and tan β = −\frac{\sqrt{1.5}}{x} = \sqrt{1.5}\frac{1}{−x} = \sqrt{1.5} tan α.

Squaring equations and using

tan^{2} x = \frac{1 − cos^{2} x}{cos^{2} x}  tan x = \frac{sin x}{cos x}  sin^{2} x + cos^{2} x = 1

we now obtain

\frac{1 − cos^{2} β}{cos^{2} β} = 2(\frac{1 − (\frac{1+2cosβ}{2} )^{2}}{(\frac{1+2cosβ}{2} )^{2}} ) and \frac{1 − cos^{2}β}{cos^{2}β} = 1.5(\frac{1 − (1 + cosβ)^{2}}{(1 + cosβ)^{2}} ).

The substitution cos β = x and some elementary operations give the needed equations noted in the variable x.

5 points in the plane  6 points in the plane
quartic  4x^{4} + 4x^{3} − 3x^{2} + 4x + 1 = 0 0.5x^{4} + x^{3} + 2x + 1 = 0
monic quartic x^{4} + 4x^{3} − 12x^{2} + 64x + 64 = 0 x^{4} + 2x^{3} + 4x + 2 = 0
reduced quartic x^{4} − 18x^{2} + 96x − 15 = 0  x^{4} − 6x^{2} + 40x − 3 = 0
resolvent cubic x^{3} − 48x − 8064 = 0  x^{3} − 1536 = 0

By Eisenstein’s theorem it is easy to see, that the quartics and the resolvent cubics are irreducible over ℚ. Consequently, the quartics do not have constructible solutions. Therefore, the abscissa of the minimal point M and finally the point M is not constructible. □

4. The Fermat point in the Euclidean three-dimensional space

Theorem 2. In general it is impossible to construct the minimal point for 4 and more points of the Euclidean three-dimensional space by strict usage of compass and ruler.

[figure: y; z; x; P_{1}; P_{2}; P_{3}; P_{4}]

Figure 4

Let 4 points corresponding to Figure 4 with the coordinates

P_{1} = (0, −1, 0); P_{2} = (0, 1, 0); P_{3} = (1, 0, 0); P_{4} = (1, 0, 1)

be given.

The following properties of the Fermat point M we will use by the computation of its coordinates.

1. The Fermat point M belongs to the x-z-plane.

2. The bisecting lines of the angles P_{2}MP_{1} and P_{3}MP_{4} belong to the same straight line.

3. ∠P_{2}MP_{1} = ∠P_{3}MP_{4}.

[figure: z; x; P_{1}; P_{2}; P_{3}; P_{4}; M; Figure 5; φ; z; x; P_{1}; P_{2}; P_{3}; P_{4}; M; φ; Figure 6]

Let M(x, 0, z) be the minimal point. At first we turn △P_{1}MP_{2} with the angle \frac{π}{2} in the z-x-plane corresponding to Figure 5. Now we are able to construct the minimal point if and only if the angle φ is constructible. To simplify the calculation we turn the figure with the angle φ so that \overline{P_{1}P_{2}} belongs to the z-axis (Fig. 6). The equations for the diagonales \overline{P_{2}P_{3}} , \overline{P_{1}P_{4}} are given by

z = −\frac{1 − sin φ}{cos φ} · x + 1 and z = −\frac{cos φ + sin φ + 1}{cos φ − sin φ} · x − 1.

Additional z = 0 holds. The transformation of the system of equations gives

\frac{1 − sin φ}{cos φ} = \frac{cos φ + sin φ + 1}{cos φ − sin φ}

coinciding with property 3. By substituting

sin φ = x and cos φ = \sqrt{1 − sin^{2} φ} = \sqrt{1 − x^{2}}

we have the quartic

8x^{4} − 4x^{3} − 7x^{2} + 2x + 1 = (x − 1)(8x^{3} + 4x^{2} − 3x − 1) = 0.

The root x = 1 does not solve the construction. Therefore the solution needed is a root of the cubic polynomial

8x^{3} + 4x^{2} − 3x − 1 = 0.

This polynomial has the approximate roots

x_{1} ≈ −0, 776 (8x_{1} ≈ −6, 208)
x_{2} ≈ −0, 287 (8x_{2} ≈ −2, 296)
x_{3} ≈ 0, 562 (8x_{3} ≈ 4, 496)

Since the values 8x_{1};8x_{2};8x_{3} are not integer the roots are not rational and consequently not constructible. By the condition 0 = −\frac{1−sin ϕ}{cos ϕ}x + 1 we get the minimal point with

M = (\frac{cos φ · cos φ}{1 − sin φ}; 0; \frac{cos φ · sin φ}{1 − sin φ}).

Since sin φ is not constructible, the minimal point for the given point set is also not constructible with compass and ruler. For more than 4 points we use the same point set as in the plain. If we rotate \overline{P_{3}P_{4}} around the x-axis with the angle \frac{π}{2} we get points out of the z-x-plane. The proof of Theorem 1 analogously holds. □

5. The Steiner tree in the Euclidean three-dimensional space

Theorem 3. Generally the construction of the true length of all parts of the Steiner tree is impossible for 4 or more points of the Euclidean three-dimensional space.

Let the tetrahedron P_{1}P_{2}P_{3}P_{4} with the points

P_{1} = (0, \frac{−1}{4}, 0); P_{2} = (0, \frac{1}{4}, 0); P_{3} = (1, \frac{1}{4}, 0); P_{4} = (1, \frac{1}{4}, \frac{2\sqrt{3}}{3})

be given.

[figure: P_{1}; S_{1}; P_{2}; Q_{1}; P_{3}; S_{2}; P_{4}; Q_{2}; Figure 7]

The triangles P_{1}P_{2}Q_{1} and P_{4}P_{3}Q_{2} are equilateral. We will consider the path between \overline{P_{1}P_{2}} and \overline{P_{3}P_{4}}. The Steiner points S_{1}, S_{2} are connected with exactly 3 other points of the Steiner tree. Figure 8 describes the construction in the plane.

P_{2}P_{1}  P_{3} P_{4} Q_{1}  Q_{2} S_{1} S_{2} Figure 8

We obtain the tree in the space analogously if we rotate the triangles in such a way that Q_{1}Q_{2} belongs to the plane of △P_{4}P_{3}Q_{2} and of △P_{1}P_{2}Q_{1}. That means, we have to determine the angle α for the rotation of △P_{1}P_{2}Q_{1} around the axis P_{1}P_{2} and the angle β for the rotation of △P_{4}P_{3}Q_{2} around the axis P_{3}P_{4}. Thus we get the formulas

1 + cos β^{\begin{matrix}1 \\ √ & 3 \end{matrix}} = tan α  1 + \begin{matrix}√ & 3 \\ 4 \end{matrix} cos α^{{1 \atop 4}} = tan β

for the x-y-plane and the x-z-plane. Simple transformations give

cos β = \begin{matrix}1 \\ √ & 3 \end{matrix} cot α − 1 {1 \atop 4 + √3 cos α} = tan β.

With tan β = ^{\begin{matrix}√ & 1−cos^{2} β \\ cos β \end{matrix}} we get

{1 \atop 4 + √3 cos α} = \begin{matrix}√ & 1 − (\begin{matrix}1 \\ √ & 3 \end{matrix} cot α − 1)^{2} \\ \begin{matrix}1 \\ √ & 3 \end{matrix} cot α − 1 \end{matrix}

and squaring the equation gives

(\frac{2}{\sqrt{3}} cot α − \frac{1}{3} cot^{2} α)(3 cos^{2} α + 8\sqrt{3} cos α + 17) = 1.

Now we substitute \sqrt{3} cos α = x and cot α = \sqrt{\frac{x^{2}}{3−x^{2}}} . Thus we obtain

(\frac{2}{\sqrt{3}} · \sqrt{\frac{x^{2}}{3 − x^{2}}} − \frac{1}{3} · \frac{x^{2}}{3 − x^{2}} )(x^{2} + 8x + 17) = 1.

Through simple transformations the octic polynomial is given as

13x^{8} + 208x^{7} + 1232x^{6} + 2912x^{5} + 154x^{4} − 9648x^{3} − 10152x^{2} + 81 = 0.

Replacing x by \frac{X}{13} and multiplying by 13^{7}, we now obtain the monic polynomial

X^{8} + 208X^{7} + 16016X^{6} + 492128X^{5} + 338338X^{4} − 275556528X^{3} −
3769366536X^{2} + 5082629877.

Since the polynomial is seperable we can use the fact that the Galois group of f(x) in ℤ_{p} is a subgroup of the Galois group in ℤ. If f(x) has a factorisation

f(x) = (x^{n} + ... + a_{n}) · ... · (x^{m} + ... + b_{m})

then the Galois group contains a permutation consistung of m and n cycles. The factorisations in ℤ_{p} give:

(1) p = 7 1x^{8} + 5x^{7} + 0x^{6} + 0x^{5} + 5x^{3} + 2x^{2} + 0x + 3

(1x + 2)(1x^{2} + 6x + 6)(1x^{5} + 4x^{4} + 6x^{3} + 1x^{2} + 4x + 2)

(2) p = 23 1x^{8} + 1x^{7} + 8x^{6} + 20x^{5} + 8x^{4} + 9x^{3} + 10x^{2} + 0x + 16

(x^{1} + 14)(1x^{7} + 10x^{6} + 6x^{5} + 5x^{4} + 7x^{3} + 3x^{2} + 14x + 11)

(3) p = 79 1x^{8} + 50x^{7} + 58x^{6} + 37x^{5} + 60x^{4} + 54x^{3} + 43x^{2} + 0x + 4

is irreducible over ℤ_{79}.

Thus the Galois group of f(x) contains an 8-cycle, a 7-cycle and a transposition. These permutations generate the symmetric group S_{8}. Consequently the polynomial is not solvable by radicals and so the roots are not constructible. Numerical calculations demonstrate the fact that the considerd tree is the shortest of the three possible spanning trees. □

Acknowledgments. Thanks to O. Neumann (Jena) for the introduction into the problems and to P. Schreiber (Greifswald) for hints in working out the manuscript.

References

[1] Baja, Ch.: The Algebraic Degree of Geometric Optimization Problems. Discrete Comput. Geom. 3 (1988), 177–191.

[2] Cieslik, D.: Steiner Minimal Trees. Kluwer Academic Publishers Dordrecht, Boston, London 1998.

[3] Schreiber, Peter: Zur Geschichte des sogenannten Steiner-Weber-Problems. Wiss. Zeitschr. Ernst-Moritz-Arndt-Univ. Greifswald, Math.-nat.wiss. Reihe 35 (3X1986), 53– 56.

[4] Sturm, R.: Über den Punkt kleinster Entfernungssumme von gegebenen Punkten. J. Reine Angew. Math. 97 (1884), 49–61.

[5] Weber, A.: Über den Standort der Industrien. Erster Teil. Reine Theorie der Standorte. Mit einem math. Anhang v. G. Pick. Verlag J. C. B. Mohr Tübingen 1909.

Received May 3, 1998, revised version November 25, 1998