# The Davis Pigeonhole — v2

Revision after review. Changes from v1:

1. The time separation $T$ is now prescribed independently of the Lipschitz constant. In v1, $\delta = \varepsilon/\Lambda$ made the conclusion follow from the Lipschitz bound alone.
2. The theorem is stated for an arbitrary map into a metric space with finite covering number. No continuity needed.
3. A separate return theorem with an excursion hypothesis; the near-repeat theorem is satisfied by a constant map.
4. The radial-frame bound on $\Lambda$ now carries the hypotheses $r_0 < \mathrm{inj}(p)$ and $\sqrt{\kappa}\,r_0 \leq c$.
5. Line 12 ($L^* \sim N(\varepsilon)/\kappa$) withdrawn. Replaced by the Lipschitz threshold.
6. Minor: line 8 restricted to small $\varepsilon$; $\Lambda = 0$ and $\kappa = 0$ handled; cover assignment made definite; product order corrected for both the loop holonomy and the arbitrary-frame segment transport; $N_X(\varepsilon) < \infty$ stated as a hypothesis; $L^*$ called a sufficient horizon.

## Theorem A (metric pigeonhole)

Let $(X, d)$ be a metric space, $\varepsilon > 0$, and assume the covering number $N = N_X(\varepsilon)$ is finite; let $B_1, \dots, B_N$ be balls of radius $\varepsilon$ covering $X$. Let $H : [0, L] \to X$ be any map and $T > 0$ any separation.

If $L \geq N_X(\varepsilon)\,T$, then there exist $s, t \in [0, L]$ with

$$|s - t| \geq T \qquad\text{and}\qquad d\big(H(s), H(t)\big) \leq 2\varepsilon.$$

Proof. The samples $t_j := jT$, $j = 0, 1, \dots, N$, lie in $[0, L]$ since $NT \leq L$. Assign each $j$ the first ball in the fixed ordering containing $H(t_j)$. There are $N + 1$ samples and $N$ balls, so some $i \neq j$ share a ball, giving $d(H(t_i), H(t_j)) \leq 2\varepsilon$ and $|t_i - t_j| \geq T$. $\square$

$L^* := N_X(\varepsilon)\, T$ is a sufficient horizon. The proof establishes a bound, not that this is the earliest length at which the conclusion holds; a cover can overestimate how many mutually separated states exist.

## Remark (Lipschitz threshold)

Suppose $H$ is $\Lambda$-Lipschitz with $\Lambda > 0$, and set $T_0 := 2\varepsilon/\Lambda$. For $T \leq T_0$, the conclusion follows directly from the Lipschitz bound: the pair $(0, T)$ satisfies it whenever $L \geq T$, since $d(H(0), H(T)) \leq \Lambda T \leq 2\varepsilon$. For larger $T$, that estimate alone no longer guarantees it. (The conclusion may still be automatic for other reasons — for instance if the image of $H$ has diameter at most $2\varepsilon$ — and a Lipschitz constant need not be optimal.)

If $\Lambda = 0$, $H$ is constant and the conclusion holds for every $0 < T \leq L$.

## Theorem B (return)

Fix $R > 2\varepsilon$ and $\tau > 0$. Suppose $H$ leaves every $R$-ball within time $\tau$: for every $s \in [0, L - \tau]$ there is $u \in [s, s + \tau]$ with $d(H(u), H(s)) > R$.

If $L \geq N_X(\varepsilon)\,\tau$, then there exist $s < u < t$ in $[0, L]$ with

$$d\big(H(s), H(t)\big) \leq 2\varepsilon \qquad\text{and}\qquad d\big(H(u), H(s)\big) > R.$$

Proof. Theorem A with $T = \tau$ gives $s < t$, $t - s \geq \tau$, $d(H(s), H(t)) \leq 2\varepsilon$. The excursion hypothesis gives $u \in [s, s + \tau] \subseteq [s, t]$ with $d(H(u), H(s)) > R > 2\varepsilon$; in particular $u \neq t$. $\square$

Note: if $H$ is $\Lambda$-Lipschitz with $\Lambda > 0$, the excursion hypothesis forces $\tau > R/\Lambda > T_0$ (strict, since the excursion exceeds $R$), so Theorem B automatically sits above the Lipschitz threshold.

## Geometric instance

**1.** Let $(M, g)$ be a Riemannian manifold.

**2.** Let $\gamma : [0, L] \to M$ be a smooth unit-speed path.

**3.** Let $P_\gamma\big|_{[0,t]} : T_{\gamma(0)}M \to T_{\gamma(t)}M$ be parallel transport along $\gamma$.

**4.** Fix a smooth orthonormal frame field $F(t)$ along $\gamma$. Define
$$H(t) := \big[\,P_\gamma\big|_{[0,t]}\, F(0)\,\big]_{F(t)} \in \mathrm{SO}(n), \qquad H(0) = I.$$

**5.** Assume $|K| \leq \kappa$.

**6.** Let $\omega$ be the connection form of $g$ in the frame $F$ and $\Lambda := \sup_t \|\omega(\gamma'(t))\|$. Writing $E = FH$ for the parallel frame, $\nabla_{\gamma'}E = 0$ and $\nabla_{\gamma'}F = F\,\omega(\gamma')$ give $H' = -\omega(\gamma')H$, so in the bi-invariant metric
$$d_{\mathrm{SO}(n)}\big(H(s), H(t)\big) \leq \Lambda\,|s - t|.$$
If $F$ is the radial frame from $p$ (parallel transport along radial geodesics), $\gamma \subset B(p, r_0)$, $r_0 < \mathrm{inj}(p)$, and $\sqrt{\kappa}\,r_0 \leq c$ for a fixed sufficiently small universal constant $c > 0$, then $\omega(\partial_r) = 0$ and the tangential components are $O(\kappa r)$ by the Jacobi-field estimate in normal coordinates, so
$$\Lambda \leq C(n)\,\kappa\, r_0.$$
Choosing $r_0 \sim 1/\sqrt{\kappa}$ gives $\Lambda \leq C(n)\sqrt{\kappa}$, but only if $\mathrm{inj}(p)$ permits it; a sectional-curvature bound alone does not.

**7.** Let $\varepsilon > 0$ and $N(\varepsilon) := N_{\mathrm{SO}(n)}(\varepsilon)$, the covering number in the bi-invariant metric. Finite: $\mathrm{SO}(n)$ is compact.

**8.** With the metric normalized once and for all, $N(\varepsilon) \leq C(n)\,\max\{1, \varepsilon^{-n(n-1)/2}\}$.

**9.** Choose a separation $T > 0$. Samples $t_j := jT$, $j = 0, \dots, N(\varepsilon)$.

**10.** If $L \geq N(\varepsilon)\,T$: two samples share a ball, $d(H(t_i), H(t_j)) \leq 2\varepsilon$, $|t_i - t_j| \geq T$. (Theorem A.)

**11.** **Theorem.** $L^* = N(\varepsilon)\,T$. For $L \geq L^*$ the parallel-transported frame, read in $F$, comes within $2\varepsilon$ of an earlier reading at least $T$ earlier.

**12.** **Lipschitz threshold.** Under the radial-frame hypotheses of line 6, for $\Lambda > 0$ and $\kappa > 0$,
$$T_0 = \frac{2\varepsilon}{\Lambda} \;\geq\; \frac{2\varepsilon}{C(n)\,\kappa\,r_0}.$$
For $T \leq T_0$ the conclusion of line 11 follows directly from line 6; for larger $T$, that estimate alone no longer guarantees it. Curvature sets a floor on the separation below which a near-repeat is already guaranteed by this Lipschitz estimate; compactness supplies the sufficient horizon above it. If $\Lambda = 0$ (in particular in flat space with the radial frame, where $H \equiv I$), the conclusion holds for every $0 < T \leq L$: the frame never moved, so there is nothing to return to.

## Side by side

| | Classic | Davis |
|---|---|---|
| Holes | A finite set $B$ | $N(\varepsilon)$ balls of radius $\varepsilon$ covering $\mathrm{SO}(n)$ |
| Why finite | Given | Compactness (line 7) |
| How many | $|B|$, given | $N(\varepsilon) \leq C(n)\max\{1, \varepsilon^{-n(n-1)/2}\}$ (line 8) |
| Pigeons | A finite set $A$ | Sample times $t_j = jT$, $j = 0, \dots, N(\varepsilon)$ (line 9) |
| Why that many | $|A|$, given | $L \geq N(\varepsilon)T$ fits them in |
| The map $f$ | Given | $j \mapsto$ first ball containing $H(t_j)$ |
| Hypothesis | $|A| > |B|$ | $L \geq N(\varepsilon)\,T$ |
| Conclusion | $\exists\, a \neq a'$: $f(a) = f(a')$ | $\exists\, i \neq j$: $d(H(t_i), H(t_j)) \leq 2\varepsilon$, $|t_i - t_j| \geq T$ |
| Role of compactness | None | Makes the holes finite |
| Role of curvature | None | Bounds $\Lambda$; sets the floor $T_0$ below which the Lipschitz estimate already gives the conclusion |
| Slogan | More pigeons than holes | More path than precision |

Theorem A is the classic theorem applied to one specific $f$; finite-cover pigeonholing is a standard compactness argument. The geometric interpretation is that compactness supplies finitely many orientation bins, while path length supplies samples at a prescribed separation. An excursion hypothesis upgrades a near-repeat to a return.

## Withdrawn from v1

The corollary $L^* \sim N(\varepsilon)/\kappa$. From $\Lambda \leq C\kappa r_0$ one gets a lower bound on $\varepsilon/\Lambda$, not a scaling, and in v2 $\Lambda$ no longer appears in the horizon at all. The lines "high curvature, short horizon" and "the horizon scales as states over curvature" are not supported and should not be spoken.

## Minor corrections carried in

Line 8: $\max\{1, \cdot\}$ and a fixed normalization. Lipschitz threshold: $\Lambda = 0$ and $\kappa = 0$ treated. Theorem A: first containing ball in a fixed ordering. Line 6 remark: with the radial frame, the holonomy of the loop $p \to \gamma(s) \to \gamma(t) \to p$ in the base-point frame is $H(t)H(s)^{-1}$; $H(s)^{-1}H(t)$ is conjugate to it, and the bi-invariant distance is conjugation-invariant, so $d(H(s), H(t)) = d(I, H(t)H(s)^{-1})$ either way. For an arbitrary frame $F$ there is no geometric closing path; the matrix of the segment transport $P_{s \to t} : T_{\gamma(s)}M \to T_{\gamma(t)}M$ in the frames $F(s)$, $F(t)$ is
$$[P_{s \to t}]_{F(s), F(t)} = H(t)\,H(s)^{-1},$$
transport relative to $F$, not a loop holonomy.

## Effect on the video

Lines 1 through 8: overlays stand (line 6 gains the $r_0$, $\mathrm{inj}$, $\sqrt{\kappa}r_0$ hypotheses in the notes, not on screen; line 8 gains $\max\{1,\cdot\}$). Lines 9, 10, 11 change: step $\varepsilon/(C(n)\kappa)$ becomes a free separation $T$; conclusion gains $|t_i - t_j| \geq T$ and $2\varepsilon$. Line 12 is replaced entirely by the Lipschitz threshold; wherever the video asserts the curvature bound, keep the small-ball restriction ($r_0 < \mathrm{inj}(p)$, $\sqrt{\kappa}\,r_0 \leq c$) visible. The spoken script for 9 through 12 and the closing paragraph about curvature need to be re-recorded.