Larman's bound $n\,2^{d-3}$

Read-back of Hirsch.larman_bound.

For every pair of natural numbers $d, n \ge 0$, every family of vectors $a_1, \dots, a_n \in \mathbb{R}^d$ (the Euclidean space $\mathbb{R}^d$ with its standard inner product), and every family of reals $b_1, \dots, b_n \in \mathbb{R}$, consider the set

i.e. the solution set of the $n$ linear inequalities (with no assumption that the $a_i$ are nonzero or distinct; when $n = 0$ this is all of $\mathbb{R}^d$). Under the two hypotheses that $P$ is nonempty and that $P$ is bounded (as a subset of the metric space $\mathbb{R}^d$), the theorem asserts the following, where the bound is the natural number

with truncated natural-number subtraction in the exponent: $d - 3 = 0$ whenever $d \le 3$, so for $d \in \{0,1,2,3\}$ the bound is $B = n$, and $B = 0$ whenever $n = 0$.

The conclusion is the predicate "$\mathrm{DiamLE}(P, B)$", which unfolds to: for every two extreme points $u, v$ of $P$ (an extreme point of $P$ is a point of $P$ that does not lie in the open segment between any two points of $P$ other than itself), there exists a sequence of points $w_0, w_1, w_2, \dots \in \mathbb{R}^d$ (defined for all indices) such that

• $w_0 = u$ and $w_B = v$, and
• for every index $i < B$, either $w_i = w_{i+1}$ (a stationary step), or $w_i$ and $w_{i+1}$ are "adjacent on $P$", meaning: $w_i \ne w_{i+1}$ and the closed segment $[w_i, w_{i+1}]$ is an extreme subset of $P$ — that is, $[w_i, w_{i+1}] \subseteq P$, and whenever a point of $[w_i, w_{i+1}]$ lies strictly between two points $x, y \in P$ (in the open segment from $x$ to $y$), both $x$ and $y$ already belong to $[w_i, w_{i+1}]$.

In words: any two extreme points of $P$ are joined by a walk of exactly $B$ steps, each step either staying put or moving along a segment that is an extreme subset of $P$; because stationary steps are allowed, this expresses that any two extreme points are connected by at most $B$ such moves. The intermediate points $w_i$ are quantified only through these step conditions — they are not separately required to be extreme points of $P$ (though each adjacency step forces its endpoints to lie in $P$). Note the degenerate instances included by the quantifiers: if $n = 0$ then $B = 0$ and the conclusion demands $u = v$ for all extreme points $u, v$ of $P = \mathbb{R}^d$ (the boundedness hypothesis then restricts this case to $d = 0$); if $P$ has no extreme points, or fewer than two, the conclusion is vacuous or trivial. The theorem is universally quantified over all $d$, $n$, $a$, $b$ satisfying the two hypotheses, and the stated inequality on the walk length is non-strict ($\le B$ in effect, via the stationary steps), with $B$ computed as the natural number $n \cdot 2^{d-3}$ exactly as above.