On the maximum product of distances of diameter $2$ point sets

This paper addresses an Erdős-Herzog-Piranian problem by proving that the maximum product of distances for diameter-2 point sets can be found among convex polygons, providing improved constructions over regular $n$-gons and demonstrating that a general characterization of extremal polygons is impossible for even orders.

The Gist

Imagine you are a city planner tasked with placing $n$ streetlights in a circular park. There is one strict rule: no two lights can be more than 2 miles apart.

Your goal isn't just to follow the rule; it's to arrange the lights in a way that maximizes a very specific "glow score." This score is calculated by taking the distance between every single pair of lights, multiplying all those distances together, and seeing how big the final number is.

This is the problem tackled in the paper "On the maximum product of distances of diameter 2 point sets." It's a puzzle that has stumped mathematicians for decades, originally posed by the legendary Paul Erdős.

Here is the story of what the authors discovered, explained without the heavy math jargon.

1. The "Perfect" Shape vs. The "Messy" Reality

For a long time, mathematicians thought the best arrangement was a regular polygon (like a perfect stop sign or a hexagon), where all lights are equally spaced.

• If you have an odd number of lights (3, 5, 7...): The perfect regular shape is the winner. It's like a perfectly balanced mobile; everything is in harmony.
• If you have an even number of lights (4, 6, 8...): The perfect regular shape is not the winner. It turns out that if you squish the lights a little bit, making some distances slightly longer and others slightly shorter, the total "glow score" actually goes up.

Think of it like a rubber band. If you stretch a rubber band into a perfect circle, it's stable. But if you pinch it in a few spots to make it look like a slightly irregular star, you might be able to pull the other parts tighter, creating a more efficient tension. The authors found that for even numbers, the "perfect" shape is actually a bit lazy.

2. The "Diameter Graph" (The Map of Longest Paths)

To solve this, the authors looked at a "map" of the longest distances. They drew a line between any two lights that were exactly 2 miles apart (the maximum allowed). They call this the Diameter Graph.

They proved a surprising rule: This map must be connected.
You can't have two separate islands of lights where no light on Island A is 2 miles from any light on Island B. If you did, you could wiggle the islands closer together to boost the score.

Furthermore, they discovered the shape of this map is very specific. It's either:

• A Caterpillar: A central spine with little legs sticking out.
• A Unicyclic Graph: A single loop with some legs sticking out.

This is like saying, "No matter how you arrange these lights, the 'longest path' connections will always look like a specific type of tree or a single ring with branches." This rules out thousands of impossible arrangements and narrows the search down to a manageable few.

3. The "Kite" and the "Wobbly Hexagon"

For small numbers of lights, the authors found the exact winners:

• 4 Lights: Instead of a square, the winner is a Kite shape. Two lights are far apart (2 miles), and the other two are tucked in a way that creates a specific, asymmetrical balance.
• 6 Lights: The winner isn't a regular hexagon. It looks like a hexagon that has been squished and twisted, with a specific symmetry that repeats every 120 degrees (like a Mercedes logo).

As the number of lights gets bigger, the shapes get weirder. They aren't smooth circles; they are jagged, irregular polygons that look like they were designed by a computer trying to find the absolute peak of a mountain range.

4. The "Infinite" Problem

The hardest part of the puzzle is what happens when you have millions of lights (an infinite number).

• The Old Guess: Many thought the score would settle at a specific number related to the regular polygon.
• The New Discovery: The authors built a new type of arrangement for even numbers that beats the regular polygon significantly.
  • They created a "wobbly" version of the regular polygon. Imagine taking a perfect circle and pushing every third light slightly inward and every other light slightly outward in a rhythmic pattern.
  • This "wobble" allows the lights to maintain the 2-mile limit while squeezing more "product" out of the distances.

They proved that as the number of lights goes to infinity, this new wobbly shape produces a score that is about 26% to 30% higher than the old regular polygon guess.

5. Why This Matters

You might ask, "Who cares about multiplying distances between dots?"
This problem is actually a deep dive into optimization. It teaches us how to arrange things to maximize efficiency under strict constraints.

• The Takeaway: Nature and math often prefer "imperfect" solutions over "perfect" ones when constraints are tight. A perfectly symmetrical shape is often just a local peak, while a slightly messy, asymmetrical shape is the true global champion.

Summary in a Nutshell

The authors took a decades-old puzzle about arranging dots in a circle. They proved that:

1. Odd numbers of dots love symmetry (regular polygons).
2. Even numbers of dots love asymmetry (weird, squished shapes).
3. The "longest connections" between dots always form a specific, simple shape (a caterpillar or a single loop).
4. By breaking the symmetry just right, you can get a much better result than anyone thought possible.

They didn't solve the whole puzzle for every single number (that's too hard!), but they built a new, better "template" that beats the old guesses and gave us a roadmap for what the perfect shapes actually look like.

Technical Summary

Here is a detailed technical summary of the paper "On the maximum product of distances of diameter 2 point sets" by Cambie, Decadt, Dong, Hu, and Tang.

1. Problem Statement

The paper addresses a classic extremal problem in discrete geometry and complex analysis, originally posed by Erdős, Herzog, and Piranian.

• Objective: Maximize the product of all pairwise distances between $n$ points in the complex plane, denoted as $\Delta(z) = \prod_{1 \le i < j \le n} |z_i - z_j|^2$, subject to the constraint that the diameter of the set is at most 2 (i.e., $|z_i - z_j| \le 2$ for all $i, j$).
• Normalization: To compare results across different $n$, the authors define a normalized discriminant $\Delta_{\text{norm}}(n) = \Delta_{\max}(n) / n^n$. This normalization is chosen because for regular even $n$-gons of diameter 2, the value is exactly 1.
• Context: This problem is equivalent to maximizing the absolute value of the discriminant of a monic polynomial with roots constrained to a set of diameter 2. While regular polygons are conjectured to be optimal for odd $n$, the behavior for even $n$ is less understood, with regular polygons known not to be optimal for small even $n$ (e.g., $n=4$).

2. Methodology

The authors employ a hybrid approach combining structural graph theory, nonlinear optimization, and asymptotic analysis.

• Structural Constraints (Diameter Graphs):

  • They analyze the diameter graph $G$, where vertices are the points and edges connect pairs at distance exactly 2.
  • Using properties of harmonic functions and the maximum principle, they prove that the diameter graph of any maximizer must be connected.
  • They leverage the theory of thrackles (graphs drawn in the plane where every pair of edges intersects exactly once) to restrict the topology of $G$.
  • They utilize Nonlinear Programming (NLP) and Lagrange multipliers to derive necessary conditions (KKT conditions) that extremal configurations must satisfy.

• Numerical and Symbolic Computation:

  • For small $n$ ($3 \le n \le 12$), they enumerate admissible diameter graph types (based on the structural theorems) and use gradient descent and symbolic solvers (Maple, Julia/IPopt) to find local maxima.
  • They construct explicit geometric configurations for $n=4, 6, 8, 10, 12$ that outperform regular polygons.

• Asymptotic Constructions:

  • **Subsequence Construction ($6|n$):** They construct a specific family of polygons for$n$divisible by 6 by modifying a regular$n$-gon. The construction involves concatenating six congruent arcs and adjusting junction angles to maintain diameter constraints while increasing the product of distances.
  • Uniform Perturbation (Even $n$): To address all even $n$, they introduce a radial perturbation of the regular $n$-gon using a triangular wave function ($g(\theta) = \text{tri}(3\theta)$). This perturbation preserves the diameter constraint (keeping antipodal points at distance 2) and exploits $\pi$-antiperiodicity to cancel first-order terms in the expansion of the log-discriminant.

3. Key Contributions and Results

A. Structural Theorems

• Theorem 1 (Diameter Graph Structure): The diameter graph of an extremal configuration is either unicyclic (containing exactly one cycle) or a caterpillar (a tree where all vertices are within distance 1 of a central path).
• Theorem 10 (Refined Structure): Specifically, the graph is either a caterpillar or consists of an odd cycle with additional vertices attached to the cycle vertices. Crucially, even cycles are forbidden in the diameter graph of a maximizer.
• Proposition 7: Any maximizer must form a convex polygon.

B. Small $n$ Results and Conjectures

• Exact Values: They determine exact or highly precise values for small $n$.
  • $n=4$: The optimal shape is a "kite" (not a square), with $\Delta_{\text{norm}} \approx 1.1487$.
  • $n=6$: The optimal shape reuses the $n=4$ kite vertices plus two symmetric points, yielding $\Delta_{\text{norm}} \approx 1.3108$.
  • $n=8, 10, 12$: They provide numerical lower bounds significantly exceeding 1 (e.g., $\approx 1.29$ for $n=12$), disproving the idea that regular polygons are optimal for even $n$.
• Conjecture 4:
  • For odd $n$, the regular $n$-gon is the unique maximizer.
  • For even $n$, the maximizer has an axis of symmetry. If $6|n$, it has$D_3$dihedral symmetry (invariant under$120^\circ$ rotation).
  • The diameter graph for even $n$ is formed by attaching three pendant edges to a cycle $C_{n-3}$.

C. Asymptotic Lower Bounds

The paper provides two major asymptotic results that improve upon previous bounds (specifically those by Sothanaphan):

1. Theorem 2 (Subsequence $6|n$):
   For $n$ divisible by 6, there exists a construction such that:
   $$\lim_{n \to \infty, 6|n} \Delta_{\text{norm}}(n) = C^* = \frac{39}{4} \cdot 2^{-3} \exp\left( \frac{\pi^2 - 2\sqrt{3}\pi}{8} \right) \approx 1.304457$$
   This implies $\liminf_{n \to \infty} \Delta_{\max}(n) \ge (C^*)^{1/9} > 1$.

2. Theorem 3 (Uniform Lower Bound for All Even $n$):
   Using the triangular wave perturbation, they prove a uniform lower bound for all even $n$:
   $$\liminf_{n \to \infty, n \text{ even}} \Delta_{\max}(n) \ge \exp\left( \frac{7}{24}\zeta(3) - \frac{\pi^4}{864} \right) \approx 1.26853$$
   This constant is derived from a double integral involving the perturbation function and is strictly greater than 1, proving that regular polygons are asymptotically suboptimal for even $n$.

4. Significance

• Refutation of Naive Conjectures: The results definitively show that regular polygons are not the global maximizers for even $n$, even asymptotically. The normalized discriminant for even $n$ is strictly greater than 1.
• Structural Insight: By characterizing the diameter graph as a caterpillar or unicyclic graph with specific constraints, the paper reduces the infinite-dimensional optimization problem to a combinatorial one, providing a roadmap for future exact characterizations.
• Methodological Advancement: The combination of structural graph theory (thrackles) with high-precision numerical optimization and rigorous asymptotic analysis (using triangular wave perturbations) offers a robust framework for solving similar "product of distances" problems.
• Open Problems: The paper highlights that while the asymptotic behavior is now better understood, a complete characterization of the exact extremal polygon for general even $n$ remains out of reach due to the complexity of the combinatorial landscape. The main remaining challenge is proving the conjecture that regular polygons are optimal for all odd $n$.

In summary, this work significantly advances the understanding of the Erdős-Herzog-Piranian problem by establishing structural constraints on optimal sets, providing explicit constructions that beat regular polygons for even $n$, and proving that the maximum product of distances for even $n$ grows asymptotically faster than previously thought.