Asymptotics for face numbers of certain Hanner polytopes, with applications

This paper establishes asymptotic formulas for the face numbers of a specific family of Hanner polytopes, a result that nearly saturates the FLM inequality for a corresponding set of parameters.

The Gist

Imagine you are an architect trying to build the most efficient "shape" possible in a world with thousands of dimensions. You want to know: How many corners (vertices) and how many flat sides (facets) does this shape have?

This paper is about a specific family of shapes called Hanner polytopes. Think of these shapes as "Lego structures" built from two basic rules:

1. The Product Rule: You take two identical shapes and stack them side-by-side (like multiplying two blocks).
2. The Hull Rule: You take two identical shapes and stretch a rubber band around them to create a new, bigger shape (like taking the convex hull).

The author, Tomer Milo, is studying a specific way of building these shapes where he switches between these two rules based on a pattern (determined by a number $a$).

The Big Puzzle: The FLM Inequality

There is a famous mathematical rule called the FLM Inequality. It's like a law of physics for shapes. It says:

"If you have a shape that fits inside a big ball and contains a small ball, the number of its corners and the number of its sides are locked in a relationship. You can't have too many corners without having too many sides, and vice versa."

Mathematicians have been trying to find shapes that push this rule to the absolute limit. They want to know: What is the most extreme shape possible?

In previous research, they found shapes that were "almost" perfect at this limit, but there was a tiny gap. They could get close, but not quite touch the theoretical ceiling for certain types of shapes.

The New Discovery: Filling the Gap

Tomer Milo's paper says, "We can do better."

He looks at a specific family of these Lego shapes and counts their faces with extreme precision. Instead of just guessing or using rough estimates (like saying "it's roughly a million"), he calculates the exact growth rate of the number of faces as the shapes get bigger.

The Analogy of the "Recipe":
Imagine you are baking a cake.

• Previous research said: "If you follow this recipe, the cake will be roughly this big."
• This paper says: "If you follow this recipe, the cake will be exactly this big, down to the crumb."

By knowing the exact size of the cake (the number of faces), Milo can prove that these shapes get even closer to the theoretical limit of the FLM inequality than anyone thought possible.

How He Did It: The Tree Metaphor

To count the faces, Milo had to solve a very complex math problem. He turned the problem into a growing tree.

1. The Tree: Imagine a tree where every branch splits into smaller branches.
2. The Rules: Sometimes a branch splits into 2 pieces (Product Rule), and sometimes it splits into a different number of pieces (Hull Rule).
3. The Leaves: The "leaves" of the tree represent the faces of the shape.
4. The Calculation: Instead of counting the leaves one by one (which would take forever for a shape with millions of dimensions), he used the structure of the tree to predict exactly how many leaves there would be.

He proved that if you follow a specific pattern of splitting (based on the number $a$), the number of leaves grows in a very specific, predictable way.

Why Does This Matter?

You might ask, "Who cares about counting corners on 10,000-dimensional shapes?"

• Optimization: In computer science and economics, we often deal with problems that have thousands of variables (dimensions). Understanding the geometry of these high-dimensional spaces helps us solve complex optimization problems faster.
• Theoretical Limits: This paper helps mathematicians understand the absolute boundaries of geometry. It tells us what is possible and what is impossible when dealing with high-dimensional data.
• Saturating the Inequality: By getting closer to the "limit," Milo shows us the "edge cases" of geometry. It's like finding the fastest possible car; even if we can't build it, knowing how fast it could go helps us design better engines for the cars we can build.

Summary in Plain English

Tomer Milo built a mathematical "Rube Goldberg machine" (a complex chain of events) using high-dimensional shapes. He figured out exactly how many parts these machines have. By doing this, he proved that these shapes are even more efficient at breaking geometric rules than we previously thought, effectively "filling the gap" in a famous mathematical inequality.

He didn't just guess; he used a clever "tree counting" method to get a precise answer, showing that in the world of high-dimensional geometry, we can get very, very close to the theoretical limits of efficiency.

Technical Summary

Here is a detailed technical summary of the paper "Asymptotics for Face Numbers of Certain Hanner Polytopes, with Applications" by Tomer Milo.

1. Problem Statement and Context

The paper addresses the Figiel-Lindenstrauss-Milman (FLM) inequality, a fundamental result in convex geometry concerning the relationship between the number of vertices ($|V|$), the number of facets ($|F|$), and the Banach-Mazur distance to the Euclidean ball for a polytope $P \subset \mathbb{R}^n$.

The inequality states:
$$\log |V| \cdot \log |F| \cdot \left(\frac{R}{r}\right)^2 \geq c n^2$$
where $rB_2^n \subset P \subset RB_2^n$.

The Gap: Previous work (specifically reference [2] in the paper) established that this inequality is "tight" (saturated) for specific parameter regimes. However, for a third regime involving parameters $a, \delta \in (0,1)$, the existing bounds were "crude." Specifically, the bound on the number of vertices for certain sections of Hanner polytopes relied on a loose combinatorial estimate ($f_k(P) \leq \binom{f_0(P)}{k+1}$), resulting in a suboptimal exponent in the asymptotic analysis.

Objective: The paper aims to derive precise asymptotics for the face numbers of a specific family of Hanner polytopes (called "basic polytopes") to improve the bound on the FLM inequality for the third parameter regime, effectively "saturating" the inequality more closely than previously possible.

2. Methodology

The core of the methodology involves a rigorous combinatorial and analytic study of the face numbers of basic Hanner polytopes ($P_n^a$), defined inductively based on a density parameter $a \in (0,1)$.

A. Recursive Structure and Generating Functions

The polytopes are constructed inductively in dimension $d=2^n$:

• If $n \in A_a$ (a set with density $a$), $P_n^a = P_{n-1}^a \times P_{n-1}^a$ (Cartesian product).
• If $n \notin A_a$, $P_n^a = \text{conv}(P_{n-1}^a \cup P_{n-1}^a)$ (Convex hull of two copies).

Let $a_{n,k}$ be the number of $k$-dimensional faces. The author derives a recurrence relation for $a_{n,k}$ based on the operations:

• Product step: $a_{n+1, k} = \sum a_{n,j} a_{n, k-j}$.
• Convex hull step: $a_{n+1, k} = 2a_{n,k} + \sum a_{n,j} a_{n, k-1-j}$.

This is translated into a recurrence for the generating function $F_n(t) = \sum a_{n,k} t^k$:
$$F_{n+1}(t) = \begin{cases} F_n(t)^2 & n \in A_a \\ tF_n(t)^2 + 2F_n(t) & n \notin A_a \end{cases}$$

B. Tree Representation

To solve this recurrence asymptotically, the author maps the iteration of the generating function to a weighted tree structure.

• The composition of operators (squaring vs. $tx^2+2x$) over a block of $Q$ steps is represented as a function $\phi_{Q,m}$.
• The coefficient $a_{Qm, k}$ (face count at dimension $2^{Qm}$) is expressed as a sum over a set of trees$\mathcal{T}_m^K$of height$m$.
• Each tree $T$ has a weight $W(T)$ determined by the coefficients of the polynomial operators at its internal nodes.
• Key Insight: The number of leaves $L(T)$ in these trees corresponds roughly to the exponential growth of the face numbers.

C. Asymptotic Analysis

The paper establishes upper and lower bounds for $\log a_{Qm, k}$ by analyzing the properties of these trees:

1. Upper Bound: Proves that only trees with a limited number of "non-standard" degree nodes (nodes where the degree is not the dominant $2p(Q,m)$) contribute significantly. This restricts the search space and allows for a tight bound on the growth rate.
2. Lower Bound: Constructs a specific family of trees with a high number of leaves that satisfy the constraints, proving that the upper bound is asymptotically tight.

3. Key Contributions and Results

A. Precise Asymptotics for Face Numbers (Theorem 1.6)

The main technical result provides the asymptotic behavior of $\log f_{\lfloor d\delta \rfloor}(P_n^a)$, the logarithm of the number of faces of dimension $\lfloor d\delta \rfloor$ in a polytope of dimension $d=2^n$.

• Case 1: $a \in \mathbb{Q}$ (Rational):
  $$\log f_{\lfloor d\delta \rfloor}(P_n^a) \sim d^{a + \delta(1-a)}$$
• Case 2: $a \notin \mathbb{Q}$ (Irrational):
  $$\log f_{\lfloor d\delta \rfloor}(P_n^a) = d^{a + \delta(1-a) + o_d(1)}$$
  The error term $o_d(1)$ is explicitly bounded by $O(1/\sqrt{\log d})$ when choosing the block size $Q \sim \sqrt{n}$.

B. Improved FLM Inequality (Theorem 1.3)

By applying the new face number asymptotics to sections of these polytopes, the paper improves the known bounds for the FLM inequality in the regime where $a, \delta \in (0,1)$.

Previously, the product of the logarithmic terms was bounded by $O(n^{2+a})$. The new result tightens this to:
$$\log |V_n| \cdot \log |F_n| \cdot \left(\frac{R_n}{r_n}\right)^2 = O(n^{2 + a(1-\delta)})$$
This represents a significant improvement, bringing the bound closer to the theoretical limit of $O(n^2)$ (saturation) as $\delta \to 1$.

C. Handling Rational vs. Irrational Parameters

The paper distinguishes between rational and irrational $a$. For rational $a$, the sequence of operations is periodic, leading to a clean power-law asymptotic. For irrational $a$, the sequence is aperiodic, requiring a more delicate analysis using block sizes $Q(n)$ that grow with $n$ to approximate the density $a$, resulting in a small error term.

4. Significance

1. Resolution of a Tightness Question: The paper moves the understanding of the FLM inequality from "crude bounds" to "precise asymptotics" for a specific family of polytopes. It demonstrates that the inequality is nearly saturated for a wider range of parameters than previously proven.
2. Combinatorial Innovation: The use of tree representations to solve non-linear recurrences of generating functions is a powerful technique. It allows for the precise counting of faces in complex, recursively defined geometric objects where standard combinatorial bounds fail.
3. Geometric Insight: The results clarify the interpolation between the $\ell_1$ ball (cross-polytope) and the $\ell_\infty$ ball (cube). The parameter $a$ controls this interpolation, and the paper quantifies exactly how the face numbers scale as one moves between these extremes.
4. Foundation for Future Work: By providing explicit error terms ($O(1/\sqrt{\log d})$) and handling irrational parameters, the paper sets a rigorous standard for future investigations into the geometry of high-dimensional polytopes and the limits of the FLM inequality.

In summary, Tomer Milo's work provides a definitive asymptotic formula for the face numbers of Hanner polytopes, utilizing a novel tree-based combinatorial method to significantly tighten the bounds of a central inequality in convex geometry.