A Counterexample to Kahle-Conjecture, New Conjectures and Automated Proofs in Geometry

Francesco De Comité
Laboratoire d’Informatique Fondamentale de Lille
University of Science and Technology Lille (France)
Francesco.De-Comite@univ-lille1.fr
  Jean-Paul Delahaye
Laboratoire d’Informatique Fondamentale de Lille
University of Science and Technology Lille (France)
delahaye@lifl.fr

Abstract: In this paper, we propose a counterexample to Kahle’s conjecture and several new conjectures about the arrangement of N points in a triangle of unit area with the largest small triangle, for N=5,6,7, called Soifer Optimal Net. We also propose new bounds to those optimal nets, obtained by a method of automated theorem proving.

1  Introduction

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 1: Kahle’s conjecture s=1/6

2  A counterexample to Kahle’s conjecture, and a new bound for s

Figure 2 exhibits a new arrangement of 5 points inside a triangle of unit area, which shows that

s≥ 3−2
2
≈ 0.17157287…

(all the triangles made with 3 points among the 5 have an area greater or equal to 3−2√2)


Figure 2: A new conjecture for N=5: s=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 :

2.1  Exhaustive preliminary search

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).


Figure 3: An upper bound for N=5: 121/625

2.2  Massive search around the best arrangement

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).

2.3  Formulating a conjecture with Simon Plouffe’s Inverter

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:

Conjecture 1  
s=3−2
2
and the best arrangement of five points is the one shown on Figure 2

2.4  An automated proof of a new upper bound for s

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

Pupper bound
1021/100=0.21
1546/225≈ 0.2044
2079/400=0.1975
25121/625=0.1936
Figure 4: Evolution of the upper bound for σ as P increases.

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.

2.5  Improvement of the lower bound under some assumptions

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

3  Soifer Optimal N-nets and conjectures for N=6 and N=7

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
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:

N=6

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.

N=7

7
72
≤ σ(7)≤
23
200

Figure 8 shows conjectured Soifer Optimal 7-net.

Proof that σ(7)≤ 23/200 is based on the configuration of Figure 9.


Figure 5: Conjecture for N=6: σ(6)=1/8


Figure 6: Conjecture for N=6: σ(6)=1/8


Figure 7: Upper bound for N=6: σ(6)≤3/20=0.15


Figure 8: Conjecture for N=7:
σ(7)=7/72=0.0922…


Figure 9: σ(7)≤ 23/200

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.

References

[Can]
David Cantrell. The heilbronn problem for triangles. http://www2.stetson.edu/~efriedma/heiltri/.
[CD09]
Francesco De Comite and Jean-Paul Delahaye. A counterexample to kahle-conjecture, new conjectures and automated proofs in geometry. 2009.
http://arxiv.org/abs/0911.4375v2.
[Kah08]
Matthew Kahle. Points in a triangle forcing small triangles. Geombinatorics, XVIII:114–128, 2008.
http://arxiv.org/abs/0811.2449v1.
[Plo]
Simon Plouffe. Plouffe’s inverter. http://pi.lacim.uqam.ca/.
[Soi09]
Alexander Soifer. How Does One Cut a Triangle ? Springer, 2009.
[Wei]
Eric W. Weisstein. Heilbronn triangle problem. From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/HeilbronnTriangleProblem.html.
[YZZ94]
L. Yang, J.Z. Zhang, , and Z.B. Zeng. On the heilbronn numbers of triangular regions. Acta Math Sinica, 37, 1994.

This document was translated from LATEX by HEVEA.