Cotype of random polytopes

This paper establishes a dimension-independent lower bound on the cotype constant for normed spaces generated by random polytopes with Gaussian vertices, demonstrating that under specific density conditions on the number of vertices relative to dimension, these spaces satisfy a cotype inequality with high probability.

The Gist

Imagine you are a master chef trying to bake the perfect cake. But instead of flour and sugar, your ingredients are randomness and geometry.

This paper, written by Han Huang and Konstantin Tikhomirov, is about a very specific kind of "cake" (a mathematical shape called a random polytope) and how "stiff" or "flexible" it is. They discovered that no matter how big the cake gets, it always has a specific, predictable level of stiffness.

Here is the breakdown of their discovery using simple analogies.

1. The Ingredients: The Random Polytope

Imagine you are in a giant, empty room (this is $n$-dimensional space). You throw $N$ darts at the walls. Each dart lands at a random spot.

• The Polytope ($P_{N,n}$): Now, imagine stretching a rubber band around all those dart points. The shape formed inside the rubber band is your "polytope."
• The Twist: The authors specifically used "Gaussian" darts. Think of these as darts thrown by a very skilled, slightly nervous archer who aims for the center but wanders off in a bell-curve pattern.

This shape isn't just a static object; it defines a new way to measure distance. In this new world, the "distance" between two points is how far you have to stretch a rubber band to connect them while staying inside the shape.

2. The Problem: Is the Shape "Stiff" or "Wobbly"?

In the world of mathematics, shapes (or "Banach spaces") are judged by a property called Cotype.

• Low Cotype (Stiff): Imagine a steel beam. If you push on it from different random directions, it resists. It doesn't wiggle much.
• High Cotype (Wobbly): Imagine a bowl of jelly. If you poke it randomly, it wiggles wildly.

The authors wanted to know: If we build this shape using random darts, is it a steel beam or a bowl of jelly?

Specifically, they were worried about a "wobbly" shape that contains tiny, perfect cubes inside it. In math, if a shape contains a perfect cube (called $\ell_\infty$), it is considered "infinitely wobbly" (infinite cotype). This is bad news for certain types of mathematical calculations.

3. The Discovery: The "Universal Stiffness"

The authors proved a surprising result: These random shapes are always "stiff" enough.

They showed that for a wide range of sizes (as long as you have enough darts relative to the room size), the resulting shape cannot contain those perfect, wobbly cubes. It has a "finite cotype."

The Analogy:
Imagine you are building a fortress out of random rocks. You might worry that if you arrange them randomly, you'll accidentally leave a giant, hollow, square hole in the middle that makes the whole wall collapse.
Huang and Tikhomirov proved: No matter how you arrange the rocks (as long as you use enough of them), the fortress will never have a giant square hole. It will always be structurally sound enough to hold up a specific type of weight.

4. Why Does This Matter? (The "Local Inhomogeneity")

The paper also tackles a concept called Local Inhomogeneity.

• The Concept: Imagine a city. Is the city uniform? Are the buildings in the north district exactly the same as in the south?
• The Finding: In most random shapes, the "north district" might look very different from the "south district." The authors found that these random polytopes are actually extremely diverse locally.
• The Metaphor: Think of a kaleidoscope. If you look at a small slice of it, it looks totally different from another small slice. The authors proved that these random shapes are the "ultimate kaleidoscopes." They are so diverse that you can find almost any small shape inside them, but they are also "stiff" enough to prevent the worst kind of mathematical chaos.

5. The Big Picture: A New Mathematical Tool

The paper concludes by building a super-structure (a new infinite-dimensional space) using these random shapes.

• They took many of these "stiff but diverse" shapes and stacked them together.
• The result is a mathematical object that is perfectly balanced: It is stiff enough to be useful (finite cotype) but diverse enough to be the most complex shape possible (maximal local inhomogeneity).

Summary for the Everyday Reader

Think of this paper as a study on structural integrity in a chaotic world.

1. The Setup: We build complex shapes using random ingredients.
2. The Fear: We worry these shapes will be too floppy and collapse under pressure (infinite cotype).
3. The Proof: We proved that nature has a safety mechanism. Even with randomness, these shapes maintain a "minimum stiffness." They are never too floppy.
4. The Bonus: These shapes are also incredibly varied in their local details, making them the "champions" of complexity.

The authors didn't just find a new shape; they found a rule of nature that guarantees stability even in the most random, high-dimensional environments. This helps mathematicians and computer scientists understand how to process data in massive, messy datasets without the math breaking down.

Technical Summary

Here is a detailed technical summary of the paper "Cotype of Random Polytopes" by Han Huang and Konstantin Tikhomirov.

1. Problem Statement and Context

The paper investigates the geometric and probabilistic properties of random polytopes in high-dimensional Euclidean space, specifically focusing on the cotype of the normed spaces generated by these polytopes.

• The Object of Study: Let $X_1, \dots, X_N$ be independent and identically distributed (i.i.d.) standard Gaussian vectors in $\mathbb{R}^n$. The random polytope is defined as the symmetric convex hull:
  $$P_{N,n} := \text{conv}\{\pm X_i : 1 \le i \le N\}.$$
  This polytope induces a norm on $\mathbb{R}^n$ via its Minkowski functional: $\|x\|_{P_{N,n}} = \inf \{ \lambda > 0 : \lambda^{-1}x \in P_{N,n} \}$.
• The Core Question: Does the normed space $(\mathbb{R}^n, \|\cdot\|_{P_{N,n}})$ possess a finite cotype that is independent of the dimension $n$?
  • A Banach space $X$ has cotype $q \in [2, \infty)$ if there exists a constant $C_q$ such that for any finite collection of vectors $y_1, \dots, y_k \in X$:
    $$\mathbb{E}_\sigma \left\| \sum_{i=1}^k \sigma_i y_i \right\|_X^q \ge \frac{1}{C_q^q} \sum_{i=1}^k \|y_i\|_X^q,$$
    where $\sigma_i$ are independent Rademacher random signs.
  • Finite-dimensional spaces always have finite cotype, but the constants usually depend on the dimension. The authors seek a bound where $q$ and $C_q$ depend only on the ratio $N/n$ (specifically $K \le N/n \le K'$), not on $n$.
• Motivation: This relates to the "local inhomogeneity" of Banach spaces. Spaces with infinite cotype (like $\ell_\infty$) can contain subspaces arbitrarily close to $\ell_k^\infty$ with low distortion. The authors aim to show that random Gaussian polytopes, despite being "random," do not contain such subspaces, implying they have finite cotype.

2. Methodology and Proof Strategy

The proof is highly technical, combining tools from high-dimensional probability, convex geometry, and Banach space theory. The argument proceeds through several reduction steps:

A. Global Geometric Properties

The authors first establish that for typical realizations of the Gaussian matrix $A = [X_1, \dots, X_N]$, the polytope $P_{N,n}$ has a well-behaved in-radius (bounded away from zero and infinity) and that the singular values of submatrices of $A$ are stable. This ensures the norm $\|\cdot\|_{P_{N,n}}$ is comparable to the Euclidean norm in a global sense.

B. Coefficient Vectors and Incompressibility

A crucial innovation is the introduction of coefficient vectors $\beta(y)$. For any $y \in \mathbb{R}^n$, $\beta(y) \in \mathbb{R}^N$ satisfies $y = \sum \beta_j X_j$ and $\|\beta(y)\|_1 = \|y\|_{P_{N,n}}$.

• Key Lemma (Lemma 3.4): The authors prove that for typical realizations, any unit vector $\beta$ such that $\sum \beta_i X_i = 0$ is incompressible. That is, $\beta$ cannot be approximated by a sparse vector; its mass is spread out across many coordinates.
• This "incompressibility" is the engine of the proof. It prevents the coefficient vectors of low-distortion embeddings from being "spiky" (concentrated on few coordinates).

C. Discretization and Union Bounds

To prove the result for all subspaces, the authors cannot check every possible set of vectors. They employ a discretization argument using $\epsilon$-nets on the Grassmannian (the space of $k$-dimensional subspaces).

• They utilize a novel representation formula (Lemma 2.11) expressing the projection onto an arbitrary subspace as an infinite sum of projections onto a fixed net of subspaces.
• This allows them to control the statistics of projections of Gaussian vectors uniformly over all subspaces.

D. Two-Case Analysis of Vector Configurations

The proof analyzes a potential low-distortion embedding of $\ell_k^\infty$ into $(\mathbb{R}^n, \|\cdot\|_{P_{N,n}})$ by examining the coefficient vectors $\beta(y_i)$ of the basis vectors. They split the analysis into two cases based on the "spikiness" of these coefficients:

1. The "Flat" Case (Controlled Decay): If the coefficients decay smoothly (not spiky), the authors show that the vectors can be "truncated" to create new vectors $\tilde{y}_i$ with comparable Euclidean and polytope norms. This reduces the problem to Proposition 3.12, which proves that such configurations cannot exist because the random sign sums would be too large in the polytope norm compared to the Euclidean norm.
2. The "Spiky" Case: If the coefficients are spiky (concentrated on a small set of indices), the authors use the incompressibility of zero-sum combinations (Lemma 3.4) to derive a contradiction. Specifically, if the coefficients were spiky, one could construct a zero-sum combination that is compressible, violating the incompressibility lemma.

3. Key Contributions and Results

Main Theorem A (Cotype of Gaussian Polytopes)

For any $K' \ge N/n \ge K > 1$, there exist constants $q \in [2, \infty)$ and $C_q$ depending only on $K$ and $K'$ (independent of $n$) such that with probability $1 - O(1/n)$, the space$(\mathbb{R}^n, |\cdot|{P{N,n}})$has cotype$q$with constant$C_q$.

Theorem B (Sections of Gaussian Polytopes)

The paper establishes a lower bound on the Banach-Mazur distance between any $k$-dimensional subspace $E$ of $(\mathbb{R}^n, \|\cdot\|_{P_{N,n}})$ and the space $\ell_k^\infty$:
$$d_{BM}(E, \ell_k^\infty) \ge c k^\alpha$$
for some universal constant $\alpha > 0$. This confirms that random Gaussian polytopes do not contain "flat" subspaces that resemble $\ell_\infty^k$.

Theorem C (Maximal Local Inhomogeneity)

Combining their cotype result with Gluskin's construction (which shows that random polytopes can be far apart in Banach-Mazur distance), the authors construct a separable Banach space of finite cotype that exhibits maximal local inhomogeneity.

• Specifically, they construct a space $X$ with finite cotype such that the quantity $D_X(k)$ (the maximal Banach-Mazur distance between two $k$-dimensional subspaces of $X$) satisfies $D_X(k) = \Theta(k)$ as $k \to \infty$.
• This resolves a long-standing question: spaces with finite cotype are not necessarily "close" to Hilbert spaces in terms of local structure; they can be as "inhomogeneous" as possible.

4. Significance and Impact

1. Dimension-Independent Bounds: The result provides the first dimension-independent cotype bounds for the specific class of random polytopes generated by Gaussian vectors. This is a significant step in understanding the "typical" geometry of high-dimensional convex bodies.
2. Resolution of Extremal Problems: The construction in Theorem C demonstrates that the class of Banach spaces with finite cotype is rich enough to contain spaces with maximal local inhomogeneity. This challenges the intuition that finite cotype implies some form of "Hilbertian" regularity.
3. Methodological Advancement: The paper introduces powerful new techniques, particularly the use of incompressibility of coefficient vectors and the pseudo-incompressibility of random linear combinations, to analyze the local geometry of random polytopes. The discretization technique for the Grassmannian (Lemma 2.11) is also highlighted as a contribution of independent interest.
4. Connections to Open Problems: The authors discuss open problems regarding the optimal cotype constant (conjectured to be close to 2) and the behavior of random projections of cross-polytopes, setting the stage for future research in asymptotic geometric analysis.

In summary, Huang and Tikhomirov prove that random Gaussian polytopes are "well-behaved" in terms of cotype (finite and dimension-independent) despite being "wild" in terms of their global Banach-Mazur distances, thereby constructing a new class of Banach spaces that are simultaneously well-structured (finite cotype) and maximally irregular (maximal local inhomogeneity).