A Counterexample to Kahle-Conjecture, New Conjectures and Automated Proofs in GeometryFrancesco De Comité |
0pt In a recent paper, Matthew Kahle[Kah08] explored arrangements of points forcing small triangles inside a unit triangle, continuing the work of Alexander Soifer[Soi09].
The main question of Kahle’s paper (Question 2.5) is:
What is the minimum s of all σ such that among every five points in a triangle of unit area, some three of them form a triangle of area less than or equal to σ ?
Kahle proved that s≤ 0.24
He submits the arrangement of Figure 1 where the smallest triangle has an area of 1/6. This configuration shows that s≥ 1/6. Kahle then conjectures that s = 1/6.
In Soifer’s book[Soi09], this conjecture is named Kahle’s Conjecture (page 142).
Figure 2 exhibits a new arrangement of 5 points inside a triangle of unit area, which shows that
| s≥ 3−2 | √ |
| ≈ 0.17157287… |
(all the triangles made with 3 points among the 5 have an area greater or equal to 3−2√2)
We have also a proof that
| s ≤ 121/625=0.1936 |
In order to obtain those results, we worked in a five steps process :
First, we have searched a good arrangement of five points, by exhaustively enumerating all the arrangements of five points each in an elementary triangle inside a unit triangle (partitioned into P× P congruent elementary triangles), a method quite similar to Kahle’s method (Figure 3).
Starting from this arrangement as a clue, we generated a huge number of quintuples inside and in the neighbourhood of those triangles, keeping track of the best ones (the ones which reach the maximal value, i.e. the maximal area for the smallest triangle, hence a lower bound for s).
Looking at the coordinates of the points reaching the maximal value, we used Plouffe’s inverter [Plo] to know whether those values can be derived from ’standard’ numbers. Fortunately, Plouffe’s inverter returned interesting and simple values: it allowed us to verify that those values gave a good approximation of s, better than all the values previously found. This value is exhibited on Figure 2.
Those five points give a lower bound of 3−2√2 for s, better than Kahle’s conjecture (hence showing that the conjecture is false).
Note that Kahle’s points are all inside or around the colored triangles of Figure 3.
We now state a new conjecture:
| s=3−2 | √ |
|
In order to obtain an upper bound for s, we then wrote a program inspired by Kahle’s method of proof.
We divide the unit triangle T into P*P elementary triangles congruent to T, by drawing lines parallel to each side of T, as in step 2.1. We considered every 5-uples of triangles :
The enumeration is time-consuming, but elementary optimizations reduce the computing time.
As the result does not depend on the shape of the triangle, we can define T as an isoscele rectangle triangle with small sides of length P: all the computations are then done with integers, results are also integers. Hence σ is not subject to inferior rounding, and is a true upper bound for s. Our computation of σ as the upper bound for s is then a kind of automated theorem proving method.
We run experiments with increasing values of P, proving the upper bound
| σ=121/625=0.1936 for P=25 |
P upper bound 10 21/100=0.21 15 46/225≈ 0.2044 20 79/400=0.1975 25 121/625=0.1936
For P=10, our upper bound of 0.21 is slightly better than Kahle’s result of 0.24. The reason is that our method explored exhaustively each 5-uple of triangles, which is not the case for Kahle’s reasoning.
In order to improve the value of the lower bound, we re-ran the automated theorem proving program, for larger values of P, now assuming that the five good points are on the edges and/or vertices of the initial triangle of unit area.
This reduces the complexity of the computation, and leads to an upper bound of:
| 87/500=0.174 for P=150 |
Thus, provided that it is true that the five points giving the value s are on the perimeter of T, we can now write that we have a computer proof that:
| s≤ 87/500 |
For every integer N≥ 3, we define a Soifer Optimal N-net as a set of N points inside a triangle of unit area, such that the area of the smallest triangle defined by 3 points among the N points is maximal. Let us call σ(N) this area.
With this definition, Figure 2 is now conjectured to show a Soifer Optimal 5-net.
Proved bounds are:
| 3−2 | √ |
| ≤ σ(5)≤ 121/625 |
We investigated the cases N=6 and N=7, using the method previously used for N=5. Here are our results:
We conjecture that there are at least two optimal Soifer 6-nets, shown in Figure 5 and 6.
We proved the following bounds:
| 1/8≤ σ(6)≤ 3/20 |
Proof that σ(6)≤ 3/20 is based on the configuration of Figure 7.
| ≤ σ(7)≤ |
|
Figure 8 shows conjectured Soifer Optimal 7-net.
Proof that σ(7)≤ 23/200 is based on the configuration of Figure 9.
Note:
After the publication of this paper on arXiv[CD09], Ed Pegg Jr from Mathworld[Wei] informed us that this problem was already known as the Heilbronn Problem for triangles[Wei], and that identical configurations of points have been previously found by L.Yang, J.Z.Zhang and Z.B.Zeng[YZZ94] for N=5,6, with optimality proof and David Cantrell[Can] for N=7.David Cantrell did not give a proof of optimality.
Alexander Soifer also pointed out that the proof of optimality for N=5 was found by Royce Peng in 1989, and the outline of his proof is given in [Soi09] (section 9.3, Problem 9.3.2).
Our automated theorem proving method for finding upper bounds seems to be new.
This document was translated from LATEX by HEVEA.
