New bounds for the Heilbronn triangle problem

This paper improves the current upper and lower bounds for the Heilbronn triangle problem by applying concepts from the geometry of compression, establishing that the minimal triangle area $\Delta(s)$ for $s$ points on a unit disk satisfies $\Delta(s) \ll s^{-(3/2-\epsilon)}$ and $\Delta(s) \gg (\log s)/(s\sqrt{s})$.

The Gist

Here is an explanation of the paper "New Bounds for the Heilbronn Triangle Problem" by T. Agama, translated into simple, everyday language with creative analogies.

The Big Picture: The "No Tiny Triangles" Challenge

Imagine you are hosting a party in a circular room (a unit disk). You have $s$ guests (points) to seat. You want to seat them in such a way that no three guests form a tiny, skinny triangle. You want the smallest triangle formed by any three people to be as large as possible.

The Heilbronn Triangle Problem asks: No matter how many guests you invite, how big can you guarantee that the smallest triangle will be?

• The Goal: Maximize the size of the smallest triangle.
• The Old Guess: Mathematicians used to think that as you add more people, the smallest triangle would shrink very fast (like $1/s^2$).
• The Reality: It turns out you can do a little better than that guess, but not by much. The paper by T. Agama tries to find the exact limits of how big or small these triangles can get.

---

The New Tool: The "Compression Machine"

To solve this, the author introduces a new mathematical tool called the "Geometry of Compression."

The Analogy: The Elastic Rubber Sheet
Imagine your circular room is made of a giant, stretchy rubber sheet.

1. The Compression Map: The author invents a machine that stretches this rubber sheet. It pulls points that are close to the center outward and pushes points far away inward. It's like a cosmic vacuum cleaner that rearranges the furniture in the room.
2. The "Gap" (G): When the machine rearranges the points, it creates a specific amount of "space" or "gap" between them. The author calls this the Compression Gap.
   • Think of the gap as a personal bubble around each guest. If the bubble is big, the guest has plenty of room. If the bubble is tiny, they are crowded.
3. The Balls: Around every guest, the author draws a circle (a "ball") based on how big their personal bubble is.
   • The Magic Rule: If you have a guest with a big bubble, their circle is huge. If you have a guest with a tiny bubble, their circle is small. The author proves that these circles can be stacked inside one another like Russian nesting dolls.

How the Author Uses This Tool

The author uses this "Compression Machine" to prove two things: an Upper Bound (the ceiling) and a Lower Bound (the floor).

1. The Upper Bound (The Ceiling)

• The Question: "What is the absolute maximum size of the smallest triangle we can force?"
• The Logic: The author says, "Let's try to pack as many guests as possible into the room without making any tiny triangles."
• The Method: They use the compression machine to divide the room into these "personal bubble" circles.
  • Imagine trying to fit $s$ people into a room where everyone needs a certain amount of personal space (a ball).
  • The author calculates the total area of all these bubbles.
  • The "Pigeonhole" Trick: If you try to fit too many people into the room while keeping their bubbles big, the room simply runs out of space. The math forces the bubbles to get smaller and smaller.
  • The Result: Because the bubbles must shrink, the triangles formed by the guests must also shrink. The author proves the smallest triangle cannot be bigger than roughly **$1 / s^{1.5}$** (which is$1$divided by$s$times the square root of$s$). This is a new, tighter limit than what was known before.

2. The Lower Bound (The Floor)

• The Question: "Can we actually arrange the guests so that the smallest triangle is at least this big?"
• The Method: This is a construction problem. The author says, "I will build a specific seating chart that guarantees a certain size."
• The Strategy:
  • They use the compression machine to find a special "perfect circle" where the guests can sit.
  • They place the guests on this circle like beads on a necklace, spacing them out perfectly evenly.
  • They use the math of the "compression mass" (a way of measuring the total weight of the bubbles) to show that even with this tight spacing, the triangles formed by neighbors are surprisingly large.
• The Result: They prove you can always arrange the points so the smallest triangle is at least $(\log s) / s^{1.5}$. The "log" part is a small bonus factor that comes from the clever spacing.

Why This Matters

Before this paper, mathematicians were stuck in a gap. They knew the answer was somewhere between two numbers, but the gap was wide.

• Old Upper Limit: Roughly $1 / s^{1.42}$ (based on previous work).
• New Upper Limit: Roughly $1 / s^{1.5}$.
• New Lower Limit: Roughly $1 / s^{1.5}$.

The author has pushed the ceiling down and the floor up, bringing them much closer together. It's like narrowing a hallway so that you know exactly how wide a person can be to fit through.

Summary in a Nutshell

1. The Problem: How big can the smallest triangle be when you scatter points on a disk?
2. The New Idea: Use a "Compression Machine" to stretch and squeeze the space, turning a messy geometry problem into a neat problem about fitting circles inside circles.
3. The Discovery: By analyzing how these "personal bubble" circles nest inside each other, the author proved that the smallest triangle shrinks faster than we thought (Upper Bound) but not quite as fast as the worst-case scenario (Lower Bound).
4. The Takeaway: We are getting closer to the perfect answer for this 100-year-old math puzzle, using a fresh, geometric perspective that treats points like guests needing personal space.

Technical Summary

Here is a detailed technical summary of the paper "New Bounds for the Heilbronn Triangle Problem" by T. Agama.

1. Problem Statement

The Heilbronn Triangle Problem asks for the maximal possible value of the minimal area of a triangle formed by $s$ points placed inside a convex planar region (typically the unit disk). Let $\Delta(s)$ denote the supremum of the minimal triangle area over all possible $s$-point configurations in the unit disk.

• Historical Context: Heilbronn conjectured that $\Delta(s) = O(s^{-2})$.
• Current State of Knowledge:
  • Lower Bound: The celebrated construction by Komlós, Pintz, and Szemerédi (1982) established $\Delta(s) \gg \frac{\log s}{s^2}$, disproving the conjecture that the decay is exactly $s^{-2}$ and showing a logarithmic factor is necessary.
  • Upper Bound: The best previously known upper bound was $\Delta(s) \ll \frac{e^{c\sqrt{\log s}}}{s^{8/7}}$ (Komlós, Pintz, Szemerédi), with recent minor improvements.
• Goal: The paper aims to improve both the upper and lower bounds using a novel geometric framework.

2. Methodology: The Geometry of Compression

The author introduces a new geometric framework called the geometry of compression to analyze local clustering and dispersion of point sets. This approach translates combinatorial problems into geometric packing estimates.

Core Definitions

• Compression Map ($V_m$): A map $V_m: \mathbb{R}^n \to \mathbb{R}^n$ defined for a scale $0 < m \leq 1$ as:
  $$V_m[(x_1, \dots, x_n)] = \left(\frac{m}{x_1}, \dots, \frac{m}{x_n}\right)$$
  This map rescales points, pushing those near the origin away and those far away closer.
• Mass of Compression ($M$): The sum of the components of the compressed vector:
  $$M(V_m[\vec{x}]) = \sum_{i=1}^n \frac{m}{x_i}$$
• Compression Gap ($G \circ V_m$): A metric representing the "distance" or radius induced by the compression, defined as the Euclidean norm of the difference between the original point and its compressed image:
  $$G \circ V_m[\vec{x}] = \left\| \vec{x} - V_m[\vec{x}] \right\|_2 = \left\| \left(x_1 - \frac{m}{x_1}, \dots, x_n - \frac{m}{x_n}\right) \right\|_2$$
• Induced Balls: The author defines a "ball" $B_{\frac{1}{2}G \circ V_m[\vec{x}]}[\vec{x}]$ centered at the midpoint of $\vec{x}$ and $V_m[\vec{x}]$ with radius $\frac{1}{2}G \circ V_m[\vec{x}]$.
  • Key Property: The paper establishes a nesting property (Theorem 2.14). If point $\vec{y}$ is inside the ball induced by $\vec{x}$ and is closer to the origin, the ball induced by $\vec{y}$ is nested inside the ball induced by $\vec{x}$. This allows for hierarchical packing arguments.

Technical Tools

• Asymptotic Analysis: The proofs rely on the behavior of the compression gap as $n \to \infty$ with $m = m(n) = o(1)$.
• Area Estimation: The area of the circle induced by a point in $\mathbb{R}^2$ is directly related to the square of the compression gap: $\delta(V_m[\vec{x}]) = \frac{\pi}{4}(G \circ V_m[\vec{x}])^2$.
• Pigeonhole Principle: Used in the upper bound proof to force the existence of a small triangle by partitioning the domain into compression-induced balls.

3. Key Contributions and Results

The paper presents two main theorems that improve upon the known bounds for $\Delta(s)$.

A. Improved Upper Bound

Theorem 1.2: The minimal area satisfies:
$$\Delta(s) \ll \frac{1}{s^{3/2 - \epsilon}}$$
where $\epsilon = \epsilon(s) > 0$ is a small, slowly varying function.

• Proof Sketch:
  1. The $s$ points are partitioned into "compression balls."
  2. The total area available for these balls is estimated.
  3. Using a pigeonhole/counting argument, the author forces the existence of a triangle with an area bounded by the density of these balls.
  4. By optimizing the scale $m$ and the distribution of points (specifically choosing $x_j \approx 1 + \frac{\log s}{\sqrt{s}}$), the bound improves from the previous $s^{-8/7}$ to approximately $s^{-1.5}$.

B. Improved Constructive Lower Bound

Theorem 1.3: The minimal area satisfies:
$$\Delta(s) \gg \frac{\log s}{s\sqrt{s}} = \frac{\log s}{s^{3/2}}$$

• Proof Sketch:
  1. Construction: Points are explicitly placed on a "compression circle" (an induced ball) with equidistant chords.
  2. Admissible Points: The author places $s$ points such that they are "admissible" (lying on the boundary of the induced ball).
  3. Area Calculation: The minimal triangle area is estimated by calculating the area of the sectors formed by adjacent points.
  4. Optimization: By choosing the scale $m$ and the coordinates $x_j$ carefully (involving logarithmic terms), the author derives the lower bound.
  5. Significance: This improves the classic Komlós–Pintz–Szemerédi lower bound of $\frac{\log s}{s^2}$ to $\frac{\log s}{s^{1.5}}$.

4. Significance and Implications

• Narrowing the Gap: The paper significantly narrows the gap between the lower and upper bounds for the Heilbronn problem.
  • Previous Gap: Between $O(s^{-2} \log s)$ and $O(s^{-1.14})$.
  • New Gap: Between $\Omega(s^{-1.5} \log s)$ and $O(s^{-1.5+\epsilon})$.
  • The bounds are now essentially of the same order ($s^{-1.5}$), suggesting that the true asymptotic behavior of $\Delta(s)$ is likely close to $s^{-1.5}$.
• Novel Framework: The "geometry of compression" provides a unified language for quantifying local clustering. It bridges combinatorial sums and geometric packing, offering a new toolset for extremal geometry problems.
• Constructive vs. Existential: The lower bound is constructive, providing an explicit method for placing points to achieve the bound, whereas many previous lower bounds relied on probabilistic or complex combinatorial constructions.

5. Conclusion

T. Agama's work represents a substantial advancement in the Heilbronn Triangle Problem. By introducing the geometry of compression, the author successfully pushes both the upper and lower bounds to the $s^{-3/2}$ regime. This suggests that the Heilbronn conjecture of $s^{-2}$ is indeed far from the truth, and the optimal decay rate is likely governed by the $s^{-1.5}$ scaling, with logarithmic corrections. The methodology offers a promising new direction for tackling other problems in discrete geometry involving point distribution and minimal area constraints.