Thesis overview

This site is layer (b): algorithms, lemmas, proofs, and pseudocode. For agent rules, see AGENTS.md at the workspace root. Meta-level development docs live under meta/.

• Thesis: thesis/overview.md
• Meta: meta/overview.md

Overview

Note: former demo-only geometry helper has been removed in favor of the 2D/4D polytope libraries (poly2, poly4) documented in dedicated pages.

The Ekeland–Hofer–Zehnder Capacity on Convex Polytopes in R^4

This section fixes conventions and recalls the precise definition and basic properties of the Ekeland–Hofer–Zehnder (EHZ) capacity in the 4‑dimensional Euclidean symplectic space. We then specialize to convex star‑shaped polytopes, describe the induced (generalized) Reeb dynamics on their boundary, and record structural facts we will use later when designing algorithms.

Setting and Notation

We work on R^{4} with the standard symplectic form $$ \omega_0 = dx_1\wedge dy_1 + dx_2\wedge dy_2, $$ the standard complex structure (J) (so that (\omega_0(u,v)=\langle Ju, v\rangle)), and the standard Liouville 1‑form $$ \lambda_0 = \tfrac12 \sum_{i=1}^{2} \big(x_i,dy_i - y_i,dx_i\big). $$ Let (K\subset \mathbb{R}^4) be a compact, convex body that is star‑shaped with respect to the origin; write (\Sigma=\partial K). At smooth points of (\Sigma), the restriction (\alpha=\lambda_0|{\Sigma}) is a contact form with (d\alpha=\omega_0|{\Sigma}). The Reeb vector field (R_\alpha) is defined by (\alpha(R_\alpha)=1) and (d\alpha(R_\alpha,\cdot)=0). A closed characteristic on (\Sigma) is a closed orbit of (R_\alpha); for non‑smooth (\Sigma) (e.g. a polytope) we use generalized closed characteristics in the sense of convex/contact nonsmooth dynamics (the “combinatorial Reeb orbits” below), which agree with Reeb orbits after smoothing and preserve action and Conley–Zehnder index.¹

The action of a closed (generalized) characteristic (\gamma) is $$ \mathcal{A}(\gamma)=\int_\gamma \lambda_0, $$ which equals the (\omega_0)-area of any spanning disk when (\gamma) is contractible.

Definition and Basic Properties

For convex domains the Ekeland–Hofer and Hofer–Zehnder capacities coincide, and their common value is denoted (c_{EHZ}(K)). It admits the following equivalent characterizations.

• Variational/Reeb characterization (convex case). The EHZ capacity is the minimal action of a closed (generalized) characteristic on (\partial K): $$ c_{EHZ}(K) ;=; \min{\mathcal{A}(\gamma)\mid \gamma \text{ closed (generalized) characteristic on }\partial K}. $$ The infimum is attained.[^EH89][^CHLS07]²

• Hofer–Zehnder Hamiltonian characterization. Let (\mathcal{H}(K)) be the set of autonomous “admissible” Hamiltonians supported in (K) with all non‑constant periodic orbits of period strictly larger than 1. Then $$ c_{HZ}(K)=\sup{\max H\mid H\in\mathcal{H}(K)}. $$ For convex (K), (c_{HZ}(K)=c_{EHZ}(K)).[^HZ94]³

As a symplectic capacity on the class of convex sets, (c_{EHZ}) satisfies the usual axioms:

• Monotonicity: if (K\hookrightarrow K') symplectically, then (c_{EHZ}(K)\le c_{EHZ}(K')).
• Conformality: (c_{EHZ}(aK)=a^2,c_{EHZ}(K)) for (a>0).
• Normalization: (c_{EHZ}\big(B^{4}(r)\big)=\pi r^2) and (c_{EHZ}\big(Z^{4}(R)\big)=\pi R^2), where (B^{4}(r)) is the Euclidean ball and (Z^{4}(R)={(x,y)\in\mathbb{R}^{2}\times\mathbb{R}^{2}: \pi|y|^2<R^2}) the symplectic cylinder.[^HZ94]³

Remark (Minkowski billiards view). For convex Lagrangian products (K\times T\subset\mathbb{R}^{2n}), (c_{EHZ}(K\times T)) equals the minimal length of a closed ((K,T))–Minkowski billiard trajectory; this will be relevant for product examples.[^AAKO14]⁴

Reeb Dynamics on Polytopes in R^4

Let (K\subset\mathbb{R}^4) be a convex polytope that is star‑shaped with respect to the origin. The boundary (\Sigma=\partial K) is piecewise flat (a union of 3‑dimensional facets meeting along 2‑faces, 1‑faces, and 0‑faces). The classical Reeb vector field (R_\alpha) is defined and smooth on the relative interior of each facet; at non‑smooth points we use generalized characteristics (solutions to the Reeb differential inclusion), which can be defined combinatorially and arise as limits of Reeb orbits for smoothings of (K).¹

• Facets (3‑faces). If (F) is a facet with constant outer unit normal (n_F), then on (\operatorname{relint}(F)) the Reeb vector is parallel to (J n_F); thus the flow along (F) is linear, and generalized orbits are straight segments in direction (J n_F) with speed determined by the normalization (\alpha(R_\alpha)=1).¹

• Ridges/edges/vertices (2/1/0‑faces). At non‑smooth points, the Reeb vector field is not classically defined. Generalized characteristics cross these strata with velocity constrained to the “Reeb cone”, obtained by applying (J) to the outer normal cone of (K) at the point; in particular, an orbit may only spend measure‑zero time on these strata, and transitions satisfy a convex‑geometric reflection law.¹

Two structural facts are particularly important for computation and will be used later.

1. Minimal‑action orbit exists and is realized on (\partial K).
   For convex (K), (c_{EHZ}(K)) is achieved by a (generalized) closed characteristic. In 4D, recent results show the minimal‑action orbit on a convex three‑sphere bounds a disk‑like global surface of section; as a corollary, several capacities (including the cylindrical one) coincide with this minimal action. This further confirms attainment and strengthens the dynamical picture.⁵

2. “At most one visit per facet” for a minimizer on polytopes.
   There exists an action‑minimizing generalized closed characteristic whose intersection with the relative interior of each facet is empty or a single straight segment; in particular, it visits the interior of any given facet at most once. This yields a finite‑dimensional combinatorial/variational formula for (c_{EHZ}(K)) in terms of facet normals and positive weights subject to a balancing condition.⁶

Edge segments force infinite rotation (exclude 1‑faces).
Chaidez–Hutchings define a combinatorial rotation number (\rho(\gamma)) for generalized Reeb trajectories on 4D polytopes and prove that if (\gamma) contains a nontrivial segment contained in a 1‑face, then (\rho(\gamma)=\infty). Consequently, any closed orbit with finite Conley–Zehnder index (in particular, an EHZ minimizer in (\mathbb{R}^4)) cannot contain 1‑face segments; candidates may only run along facets and cross lower‑dimensional strata at isolated points.¹

Index Information in Dimension Four

When (\Sigma=\partial K) is strictly convex and (C^2), the induced contact form on (\Sigma) is dynamically convex; all contractible closed Reeb orbits have Conley–Zehnder index at least (3). Under standard non‑degeneracy assumptions, an action‑minimizing simple orbit realizing (c_{EHZ}(K)) has Conley–Zehnder index (3) and plays a distinguished dynamical role (it bounds a global surface of section and controls sharp systolic inequalities).[^HWZ98][^ABHS18]¹

We will rely on the lower bound “CZ(\ge 3)” property and, in non‑degenerate settings, on the fact that the minimizer has index (3), when pruning candidate orbits in our algorithms.

CZ Index and Rotation for 2D Return Maps

Setup. Let ((\Sigma,\alpha)) be a contact hypersurface in (\mathbb{R}^4) with Reeb field (R_\alpha). Fix a local surface of section (D\subset \Sigma) transverse to (R_\alpha); the first‑return (first‑hit) map (\Phi:D\to D) preserves the area form (d\alpha|_D) and orientation. Along a closed orbit (\gamma) intersecting (D), the linearized return (\mathrm{d}\Phi) restricts to a path in (\mathrm{Sp}(2)) (after a choice of trivialization).

Rotation number. In a 2D trivialization, write the linearized return along (\gamma) as a path (\Psi(t)\in \mathrm{Sp}(2)), (t\in[0,T]). Lifting to the universal cover of (\mathrm{Sp}(2)) defines a real rotation number (\rho(\gamma)\in \mathbb{R}_{\ge 0}). For generic (non‑degenerate) elliptic closures, the endpoint is conjugate to a rotation by angle (\theta\in(0,2\pi)), and (\rho = \theta/\pi \in (0,2)).

Conley–Zehnder index in 2D. For such generic closures one has [ \mu_{\mathrm{CZ}}(\gamma) ;=; \lceil \rho(\gamma)\rceil + \lfloor \rho(\gamma)\rfloor. ] In particular, an index‑(3) minimizer satisfies (\rho(\gamma)\in(1,2)).

Canonical charts and positivity. In our polytope setting, we fix once per ridge a canonical 2D chart determined by an orthonormal basis ((u_1,u_2)) with (\omega_0(u_1,u_2)>0). The per‑edge first‑hit maps between ridges are orientation‑preserving on admissible domains, so the per‑edge rotation increments are non‑negative and (\rho) accumulates additively along cycles.

Numerics (implementation note). We read (\rho) from the orthogonal polar factor of the 2×2 linear part of the charted map (principal angle divided by (\pi)). This is invariant under uniform scalings of the chart and does not require the Euclidean chart to be (d\alpha)–unit‑normalized.

Normalization, Systolic Ratio, and Current Status

We use the normalization above, so for any convex (K\subset\mathbb{R}^4) we define the symplectic systolic ratio $$ sys(K)=\frac{c_{EHZ}(K)^2}{2,vol(K)}. $$ Viterbo’s 2000 conjecture asked whether (\operatorname{sys}(K)\le 1) for all convex (K). This has been disproved very recently by Haim‑Kislev and Ostrover (accepted October 8, 2025, Annals of Mathematics), which in particular shows that normalized symplectic capacities need not coincide on convex domains.⁷

What We Use Later

• The facet‑linearity of the Reeb flow and the Reeb‑cone transition rule at non‑smooth strata (to build discrete search spaces of candidate orbits).¹
• The “at most one visit per facet” structure and facet‑weight formula (to derive compact finite programs).⁶
• The index constraints in 4D (to filter candidates by Conley–Zehnder index).[^HWZ98]⁸

Further algorithmic details are in Oriented‑Edge Graph Algorithm (see docs/src/thesis/capacity-algorithm-oriented-edge-graph.md) and the linear/variational formulations (docs/src/thesis/capacity-algorithm-linear-program.md).

Footnotes / references (selection; see also thesis/bibliography.md):

Deviations and clarifications for review

• “No Reeb flow on 2‑faces/1‑faces”: At non‑smooth strata the classical Reeb vector field is undefined. I replaced this with the standard “Reeb cone”/generalized‑characteristic language and cited the polytope‑specific treatment (Chaidez–Hutchings). This yields the same computational consequences (piecewise linear motion with instantaneous transitions) without overstating non‑existence.
• “Direction (J(a n_1 + b n_2)) on 1‑faces”: Rather than a specific formula, I stated the precise constraint “velocity lies in (J) of the outer normal cone,” which subsumes the two‑facet case and generalizes correctly at higher‑valence strata.
• “Segments on 1‑faces have infinite rotation”: Now asserted and cited to Chaidez–Hutchings; see “Edge segments force infinite rotation (exclude 1‑faces)”.
• “Minimum is attained”: Strengthened and cited via symplectic‑homology/smoothing arguments (and a 2024 result showing the minimizer bounds a global surface of section in 4D).
• “Visits every 3‑face at most once”: Included as an existence statement with a citation to Haim‑Kislev (2019).
• Viterbo conjecture: Updated to reflect the 2024–2025 counterexample and included the Annals acceptance dates for clarity.
• Scope: I deferred algorithmic details to the separate algorithm sections and kept this file focused on definitions/properties, as requested.

1. Chaidez, J.; Hutchings, M. Computing Reeb dynamics on four‑dimensional convex polytopes. J. Comput. Dyn. 8(4):403–445, 2021; arXiv:2008.10111. ↩ ↩2 ↩3 ↩4 ↩5 ↩6 ↩7

2. Irie, K. Symplectic homology of fiberwise convex sets and homology of loop spaces. arXiv:1907.09749 (2019→, with updates). ↩

3. Cieliebak, K.; Hofer, H.; Latschev, J.; Schlenk, F. Quantitative symplectic geometry. MSRI Publ. 54 (2007). ↩ ↩2

4. Rudolf, D. The Minkowski billiard characterization of the EHZ‑capacity of convex Lagrangian products. J. Dyn. Diff. Eq. (2024); arXiv:2203.01718. ↩

5. Abbondandolo, A.; Edtmair, O.; Kang, J. On closed characteristics of minimal action on a convex three‑sphere. preprint (2024). ↩

6. Haim‑Kislev, P. On the symplectic size of convex polytopes. Geom. Funct. Anal. 29 (2019), 440–463. ↩ ↩2

7. Haim‑Kislev, P.; Ostrover, Y. A counterexample to Viterbo’s Conjecture. Annals of Mathematics (accepted Oct 8, 2025). ↩

8. Abbondandolo, A.; Bramham, B.; Hryniewicz, U.; Salomão, P. Sharp systolic inequalities for Reeb flows on S^3. Invent. Math. 211 (2018); and Systolic ratio, index of closed orbits and convexity for tight contact forms on S^3, Compos. Math. 154 (2018). ↩

Oriented-Edge Graph Algorithm for c_EHZ in R^4

Goal

• Input:
  • Half-space description of a convex, star-shaped, non-degenerate polytope $K \subset \mathbb{R}^4$: $K={x\in \mathbb{R}^4:\langle n_f,x\rangle\le b_f\ \forall f\in \mathcal{F}_3}$, where each facet (3-face) $f$ has outward unit normal $n_f$ and support constant $b_f>0$.
  • Optionally, vertices for convenience and validation.
• Output:
  • The EHZ capacity $c_{\mathrm{EHZ}}(K)$.
  • An action-minimizing closed characteristic $\gamma\subset\partial K$ represented combinatorially by a directed cycle of 2-faces and a fixed point in the induced affine map on the start 2-face, together with an explicit piecewise-linear lift to $\partial K$.

Setting and Assumptions

• Space and forms:
  • Standard symplectic form $\omega_0$ and Liouville form $\lambda_0$ on $\mathbb{R}^4$.
  • Fix the standard complex structure $J$ so that $\omega_0(u,v)=\langle Ju, v\rangle$ and $J^\top J=I$, $J^\top=-J$.
• Symplectic polytope hypothesis:
  • No 2-face is Lagrangian: for every 2-face $F$, the restriction $\omega_0|_{TF}\ne 0$. This matches the “symplectic polytope” condition in the Chaidez–Hutchings framework and ensures well-posed combinatorial Reeb dynamics across ridges.
• Facets and Reeb directions:
  • For each facet $f\in \mathcal{F}_3$, with plane $H_f={x:\langle n_f,x\rangle=b_f}$, trajectories of the Reeb flow on $H_f\cap\partial K$ are straight segments parallel to $v_f:=J n_f$ (speed may vary; directions are constant).
  • We only need directions to get exit points; actions are integrals of $\lambda_0$ along these straight segments.
• Genericity/non-degeneracy assumptions (used for correctness and robust numerics):
  1. For each facet $f$, and each ridge $r\subset f$ with co-facet $g\ne f$, we have $\langle v_f, n_g\rangle\ne 0$.
  2. For a fixed $f$, in the region where a particular co-facet $g$ is the first one hit along $v_f$, that co-facet is uniquely first (no ties on a set of positive measure).
  3. Action-minimizing cycles do not involve segments on 1-faces (rotation blow-up); crossings of 2-faces occur at single points.

Face Graphs

• 3-face digraph:
  • Nodes: facets $f\in \mathcal{F}_3$.
  • Oriented edges $f\xrightarrow{r} f'$ whenever facets $f\ne f'$ share a ridge $r$ and the direction $v_f$ points from a neighborhood of $r$ in $f$ into the interior of $f'$ across $r$ (equivalently: the first exit from $f$ along $v_f$ near points on $r$ is $f'$).
  • This orientation is well-defined by convexity and the genericity assumptions.
• 2-face digraph (the main search graph):
  • Nodes: ridges $i\in \mathcal{F}_2$. Each ridge $i$ is the intersection of two distinct facets $f(i)$ and $g(i)$.
  • Oriented edges: $i\to j$ labeled by the facet $F$ if $i,j\subset F$ and the flow along $v_F$ from points of $i$ first exits $F$ through $j$.
  • Multiple outgoing edges from a ridge within a common facet are possible; absent edges correspond to “no point flows $i\to j$ first”.
  • Orientation convention (decision): for every ridge $i$, fix the chart $U_i$ to be the canonical one induced by $\omega_0$ (choose an orthonormal basis $(u_1,u_2)$ of the face plane with $\omega_0(u_1,u_2)>0$). Charts are fixed per ridge (independent of the incoming facet). This pins the sign of rotation angles extracted from $D\psi_{ij}$.

Notation Recap

• Geometry: $\omega_0$ (standard symplectic form), $\lambda_0$ (Liouville), $J$ (standard complex structure) on $\mathbb{R}^4$.
• Facets: for each $F\in\mathcal{F}_3$, outward unit normal $n_F$ and support $b_F>0$, plane $H_F={x:\langle n_F,x\rangle=b_F}$, Reeb direction $v_F:=J n_F$.
• Ridges: $i\in\mathcal{F}_2$ with affine plane $R_i\subset H_F$. Charts $\pi_i:R_i\to\mathbb{R}^2$ define $A_i:=\pi_i(i)$.
• Per-edge quantities along $i\xrightarrow{F}j$:
  • Exit time $\tau_{ij}(x)$; affine on regions of constant first exit.
  • Affine map $\psi_{ij}:\operatorname{dom}\psi_{ij}\to A_j$, where $\operatorname{dom}\psi_{ij}\subset A_i$ and $\operatorname{im}\psi_{ij}\subset A_j$ are convex polygons.
  • Action increment $A_{ij}(x)=\tfrac{b_F}{2},\tau_{ij}(x)$ (affine on $\operatorname{dom}\psi_{ij}$).
  • Rotation increment $\rho_{ij}\ge 0$ (polar angle of the linear part via the orthogonal polar factor; see “Rotation and CZ index”).

Algorithm Summary (push-forward only)

• Maintain, at the current ridge, a candidate polygon $C\subset A_{i_k}$, an affine action $A:C\to\mathbb{R}$, a scalar rotation $\rho$, and an optional composed map $\Psi$ to the start chart.
• To extend along an edge $i_k\xrightarrow{F} i_{k+1}$:
  • Gate at $i_k$: intersect $C$ with $\operatorname{dom}\psi_{i_ki_{k+1}}\subset A_{i_k}$ (points that flow first to $i_{k+1}$ across $F$).
  • Push-forward candidates: $C'=\psi_{i_ki_{k+1}}!\bigl(C\cap \operatorname{dom}\psi_{i_ki_{k+1}}\bigr)\subset \operatorname{im}\psi_{i_ki_{k+1}}\subset A_{i_{k+1}}$.
  • Update action $A'$ via composition with $\psi^{-1}$ and add the per-edge increment; prune by $A'(z)\le A_{\mathrm{best}}$; update $\rho'=\rho+\rho_{i_ki_{k+1}}\le 2$.
  • Repeat; on returning to the start ridge, solve the fixed-point equation $\Psi(z)=z$ within $C$ and update the incumbent.
• Enforce “simple loop” pruning: never revisit a facet (Haim–Kislev 2019).

Per-edge Maps and Polyhedral Domains

Fix an oriented edge $i\xrightarrow{F} j$ in the 2-face graph, with $F\in \mathcal{F}_3$, $i,j\subset F$. Let $G(j,F)$ denote the co‑facet: the unique facet $G\neq F$ such that $j=F\cap G$.

• Exit-time formula on $F$:
  • For $x\in H_F$ near $i$, the first time the straight line $x + t,v_F$ hits the plane $H_{G(j,F)}$ is $$\tau_{ij}(x);=;\frac{b_{G(j,F)}-\langle n_{G(j,F)},x\rangle}{\langle n_{G(j,F)}, v_F\rangle},\quad \text{with }\ \tau_{ij}(x)>0.$$
  • The condition that $j$ is indeed first exit among all co-facets $k\subset F$ is $$\tau_{ij}(x)\le \tau_{ik}(x)\quad\text{for all admissible }k,$$ where “admissible” means $\langle n_k,v_F\rangle>0$ (the ray intersects $H_k$ forward in time). After sign normalization these comparisons are linear in $x$ and enforce that $x+t,v_F$ remains in $F$ up to the first hit.
  • Explicit half-space description of the domain $\operatorname{dom}\psi_{ij}$:
    • Let $\mathcal{K}_F$ be the set of co-facets $k$ of $F$ with $\langle n_k,v_F\rangle\ne 0$. Define $\sigma_k:=\operatorname{sign}\langle n_k,v_F\rangle$.
    • For $x\in H_F$, the comparison $\tau_{ij}(x)\le \tau_{ik}(x)$ is equivalent to $$ \sigma_k\bigl(b_{G(j,F)}-\langle n_{G(j,F)},x\rangle\bigr),\langle n_k,v_F\rangle ;\le; \sigma_k\bigl(b_k-\langle n_k,x\rangle\bigr),\langle n_{G(j,F)},v_F\rangle. $$
    • Combine these with $x\in i$ and $\tau_{ij}(x)>0$ (a single linear inequality after sign normalization). Projecting by $\pi_i$ yields $\operatorname{dom}\psi_{ij}\subset A_i$ as a convex polygon in half-space form.
• Domains and images:
  • Domain (in $A_i$): $\operatorname{dom}\psi_{ij}\subset A_i$ consists of ridge points that flow first to ridge $j$ across facet $F$ (convex polygon).
  • Image (in $A_j$): $\operatorname{im}\psi_{ij}=\psi_{ij}(\operatorname{dom}\psi_{ij})\subset A_j$ (convex polygon).
• Exit point and affine map:
  • Exit point in $F$: $x' = x + \tau_{ij}(x), v_F$, affine in $x$ on the region where $j$ is first exit.
  • Let $R_i$ and $R_j$ be the affine 2-planes containing ridges $i$ and $j$. Choose fixed linear charts (projections) $\pi_i:R_i\to \mathbb{R}^2$ and $\pi_j:R_j\to \mathbb{R}^2$ for every ridge; identify $A_i:=\pi_i(i)\subset\mathbb{R}^2$.
  • Define the per-edge affine map $$\psi_{ij}:\ \operatorname{dom}\psi_{ij}\ \to\ A_j,\qquad \psi_{ij}(\pi_i(x));=;\pi_j\bigl(x+\tau_{ij}(x),v_F\bigr),$$ with $\operatorname{dom}\psi_{ij}\subset A_i$ as above. By convexity and genericity, $\operatorname{dom}\psi_{ij}$ is a convex polygon (possibly empty), $\psi_{ij}$ is affine on it, and $\operatorname{im}\psi_{ij}$ is convex in $A_j$.

Symbol map (equations above)

• $\psi_{ij}$: push‑forward map (code: EdgeData.map_ij).
• $\operatorname{dom}\psi_{ij}\subset A_i$: domain polygon in ridge $i$ (code: EdgeData.dom_in).
• $\operatorname{im}\psi_{ij}\subset A_j$: image polygon in ridge $j$ (code: EdgeData.img_out).
• $\tau_{ij}$: first‑exit time on facet $F$ (affine on the region where $j$ is first exit).
• $A_{ij}$: action increment (code: EdgeData.action_inc).
• $\rho_{ij}$: rotation increment from the polar angle of $D\psi_{ij}$ (code: EdgeData.rotation_inc).
• $U_i,U_j$: ridge charts (code: Ridge.chart_u; left‑inverse on the plane: Ridge.chart_ut).
• $v_F=J n_F$: facet Reeb direction (code: geom4::reeb_on_facets).
• $A_i$: ridge polygon in chart $i$ (code: Ridge.poly).

Worked Example (axis‑aligned facet in the 4D cube)

Consider $K=[-1,1]^4$ in coordinates $(x_1,x_2,y_1,y_2)$ with the standard $J$ (so $v=J n$). Take the facet $F={x_1=1}$ with outward normal $n_F=e_{x_1}$ and $b_F=1$, hence $v_F=J n_F = e_{y_1}$.

• Choose ridges $i = F\cap{y_1=-1}$ and $j = F\cap{y_1=+1}$. The co‑facet for $j$ is $H_{G(j,F)}:{y_1=1}$ with $n_{G(j,F)}=e_{y_1}$, $b_{G(j,F)}=1$.
• Then $d_j=\langle n_{G(j,F)}, v_F\rangle = \langle e_{y_1}, e_{y_1}\rangle = 1 > 0$, and $$\tau_{ij}(x)=\frac{b_{G(j,F)}-\langle n_{G(j,F)},x\rangle}{d_j} = 1 - y_1.$$ All other co‑facets $k$ with $\langle n_k, v_F\rangle\le 0$ are inadmissible, so $j$ is uniquely first exit.
• Charts: the ridge planes $R_i=R_j={x_1=\pm 1,\ y_1=\mp 1}$ are spanned by the $(x_2,y_2)$ axes, so we may take $\pi_i,\pi_j$ as identity on $(x_2,y_2)$. Thus $U_iU_j^\top=I$ and the push‑forward map $\psi_{ij}$ is the identity on $(x_2,y_2)$.
• Rotation increment: $D\psi_{ij}=I_2 \Rightarrow \rho_{ij}=0$.
• Action increment: $A_{ij}(x)=\tfrac{b_F}{2}\tau_{ij}(x)=\tfrac{1}{2}(1 - y_1)$, which is affine and, in the chart, constant with respect to $(x_2,y_2)$.

Action Increment per Edge (explicit affine form)

For $x\in i$ that flows to $j$ across facet $F$, the action increment along the segment is $$ A_{ij}(x);=;\int_0^{\tau_{ij}(x)} \lambda_0\bigl(\dot \gamma(t)\bigr),dt \quad\text{with}\ \gamma(t)=x+t,v_F. $$ Using $\lambda_0(\dot\gamma)=\tfrac{1}{2}\langle J\gamma,\dot\gamma\rangle$ and $Jv_F=J(Jn_F)=-n_F$, we obtain the identity $$ A_{ij}(x);=;\frac{1}{2},\langle x, n_F\rangle\ \tau_{ij}(x)\ =\ \frac{b_F}{2}\ \tau_{ij}(x), $$ since $\langle x,n_F\rangle=b_F$ on the facet plane $H_F$. Therefore $A_{ij}$ is affine in $x$ on $\operatorname{dom}\psi_{ij}$ (because $\tau_{ij}$ is affine there). In ridge coordinates, we treat $A_{ij}$ as an affine functional on $\operatorname{dom}\psi_{ij}\subset A_i$.

Rotation and CZ index

• See background: CZ Index and Rotation for 2D Return Maps (Docs: docs/src/thesis/Ekeland-Hofer-Zehnder-Capacity.md#cz-rotation).
• Ridge charts. For each ridge $i$, we fix once and for all an orthonormal Euclidean basis $(u_1,u_2)$ of the ridge plane with the canonical symplectic orientation $\omega_0(u_1,u_2)>0$ (as implemented in code). Charts do not depend on which facet we arrive from.
• Rotation per edge. For the affine map $y_j = M_{ij} y_i + t_{ij}$ on charts, define the rotation increment by the orthogonal polar factor: write $M_{ij}=R_{ij}S_{ij}$ with $R_{ij}\in \mathrm{SO}(2)$ and $S_{ij}\succ 0$, and set $\rho_{ij} := \operatorname{arg}(R_{ij})/\pi \in [0,1]$. This is invariant under uniform scalings of $M_{ij}$ and does not require $\det M_{ij}\approx 1$ in Euclidean charts.
• Positivity of increments. In canonical charts the first‑hit map is orientation‑preserving on admissible domains, so $\rho_{ij}\ge 0$; we never subtract rotation along edges.
• Area preservation. The first‑hit map between transverse sections preserves the $d\alpha$‑area on facets. Our Euclidean orthonormal charts may scale $d\alpha$ by a positive constant per ridge, so $\det M_{ij}$ need not be exactly $1$ in these coordinates; this does not affect $\rho_{ij}$ computed via the polar factor.
• Accumulation and index. Along a closed cycle, let $\rho=\sum \rho_{ij}$. For generic (non‑degenerate) closures in 2D, the Conley–Zehnder index satisfies $\mu_{\mathrm{CZ}} = \lceil \rho\rceil + \lfloor \rho\rfloor$. In particular, an index‑$3$ minimizer has $\rho\in(1,2)$. We therefore prune whenever the accumulated $\rho$ exceeds $2$; this threshold is theory‑fixed (not tunable) and cannot be lowered without risking the loss of the true minimizer.

Search Over Directed Cycles (push-forward variant)

We now describe the core enumeration and pruning in the 2-face digraph using push-forwards (no pull-backs of polytopes).

Notation for a path $p=(i_1\xrightarrow{} i_2\xrightarrow{}\cdots\xrightarrow{} i_k)$:

• Candidate set (current ridge coordinates): $C_p\subset A_{i_k}$, a convex polygon.
• Accumulated action (affine functional on $A_{i_k}$): $A_p(z)$.
• Accumulated rotation (scalar): $\rho_p$.
• Accumulated map to the start chart: $\Psi_p := \psi_{i_1i_2}\circ\cdots\circ \psi_{i_{k-1}i_k}$ when needed to close a cycle.

Initialization at a start ridge $i_1$:

• $C_{(i_1)} := A_{i_1}$,
• $A_{(i_1)}(z) := 0$,
• $\rho_{(i_1)} := 0$,
• $\Psi_{(i_1)} := \mathrm{Id}$.

Path extension by an edge $i_k \xrightarrow{} i_{k+1}$:

1. Push-forward candidates: $C' := \psi_{i_ki_{k+1}}( C_p \cap \operatorname{dom}\psi_{i_ki_{k+1}} ) \subset \operatorname{im}\psi_{i_ki_{k+1}}\subset A_{i_{k+1}}$. Reject if empty.
2. Update action: $A'(z) := A_p\bigl(\psi_{i_ki_{k+1}}^{-1}(z)\bigr) + A_{i_ki_{k+1}}\bigl(\psi_{i_ki_{k+1}}^{-1}(z)\bigr)$ on $C'$.
3. Prune by action budget: intersect $C' \leftarrow C' \cap {z:\ A'(z)\le A_{\mathrm{best}}}$. Reject if empty.
4. Update rotation: $\rho' := \rho_p + \rho_{i_ki_{k+1}}$. Reject if $\rho'>2$.
5. Update map: $\Psi' := \Psi_p\circ \psi_{i_ki_{k+1}}$ if we plan to close at $i_1$ soon; otherwise we can maintain only the last few factors and recompute on demand.
6. Continue DFS with the new state $(C',A',\rho',\Psi')$.

Closing a cycle at $i_1$:

• When $i_{k+1}=i_1$, solve the fixed-point problem $\Psi_p(z)=z$ in $A_{i_1}$; keep any fixed point $z_\star\in C_p$; set $A_\star:=A_p(z_\star)$; if $A_\star<A_{\mathrm{best}}$, update the incumbent $(A_{\mathrm{best}}, \text{cycle}, z_\star)$.
• If no eligible fixed point exists in $C_p$, discard the cycle.

Heuristics and ordering:

• Prefer edges with small lower bounds on $A_{ij}$ (minimize the affine functional on $\operatorname{dom}\psi_{ij}$ via a tiny LP); break ties by smaller $\rho_{ij}$.
• Prefer short cycles first; try immediate back-edges that close at the start ridge early.
• Maintain a visited set of start ridges to avoid duplicate work; optionally restrict to simple cycles unless we decide otherwise (see Open Questions).

Fixed-point solver (deterministic and robust)

• Write $\Psi_p(z)=Mz+t$ in the start chart. Solve $(I-M)z=t$:
  • If $\det(I-M)\ne 0$: unique fixed point $z_\star=(I-M)^{-1}t$, accept if $z_\star\in C_p$.
  • If $\det(I-M)=0$: use SVD to check feasibility; the fixed-point set is empty or an affine line. Intersect with $C_p$ and minimize $A_p(z)$ over this intersection (1D LP). Reject if empty.
• Tolerances: treat $|\det(I-M)|<\varepsilon$ as degenerate; enforce feasibility and membership with a consistent tolerance shared with tie-breaking $\varepsilon_\tau$.

Symbol map (fixed‑point and tolerances)

• $M,t$: entries of the composed affine map $\Psi_p$ (code: State.phi_start_to_current).
• $z,z_\star$: points in the start ridge chart (code: Vec2; returned by dfs_solve_with_fp helpers).
• $C_p$: candidate polygon at the start ridge (code: State.candidate on closure).
• $A_p$: accumulated action on the start chart (code: State.action).
• $\varepsilon_{\det}$: determinant threshold (code: GeomCfg.eps_det).
• $\varepsilon_{\mathrm{feas}}$: feasibility/membership slack (code: GeomCfg.eps_feas).
• $\varepsilon_{\tau}$: tie‑breaking and admissibility slack (code: GeomCfg.eps_tau).

• Implementation guardrails:
  • fixed_point_in_poly handles both branches and switches to a 1D LP when $(I-M)$ is nearly singular so that we never rely on unstable matrix inverses.
  • rotation_angle returns None only for orientation‑reversing maps; canonical chart construction rules those out, so failures signal numerical bugs instead of algorithmic cases.

Choosing Budgets and Bounds

• Upper bound $A_{\mathrm{best}}$:
  • Practical: use that $K\subset B_R$ implies $c_{\mathrm{EHZ}}(K)\le c_{\mathrm{EHZ}}(B_R)=\pi R^2$. Compute $R$ from vertices or support data for a quick initial bound.
  • Tighter: use the volume-capacity inequality documented in Docs: docs/src/thesis/Ekeland-Hofer-Zehnder-Capacity.md#volume-upper-bounds once we finalize the preferred constant $C_{\mathrm{vol}}$. Reference that doc (not this page) whenever we update $C_{\mathrm{vol}}$ so the inequality stays centralized.
• Lower bound for progress reporting: $c_{\mathrm{EHZ}}(K)\ge \pi r^2$ if $B_r\subset K$ (inradius).

Correctness Sketch (informal)

1. Every closed characteristic in the generic polytope case intersects ridges at isolated points and travels linearly on facets parallel to $v_f$.
2. Such a trajectory maps to a directed cycle in the 2-face digraph; the per-edge maps and domains capture exactly the “first exit” geometry.
3. The action along a cycle equals the sum of per-edge increments evaluated at the unique fixed point $z_\star$ of the composed affine map in the start chart.
4. Minimizing action over all closed characteristics is thus equivalent to minimizing over all directed cycles and their fixed points.
5. The push‑forward pruning is sound: removing paths with empty candidate sets, with $A>A_{\mathrm{best}}$, or with $\rho>2$ cannot delete the true minimizer (index‑3 implies $\rho\in(1,2)$).

Orientation lemma (canonical charts)

Lemma. Let $i\subset F$ and $j\subset G$ be ridges such that $\omega_0|{Ti}\ne 0$ and $\omega_0|{Tj}\ne 0$. With our canonical 2‑face charts $U_i,U_j$ (orthonormal bases oriented by $\omega_0(u_1,u_2)>0$), the Reeb first‑hit map $\psi_{ij}:U_i(i)\to U_j(j)$ is orientation‑preserving: $\det D\psi_{ij}>0$ wherever defined.

Proof (sketch). On each facet $F$, $\alpha:=\lambda_0|F$ is a contact form and $R$ the Reeb vector field satisfies $\mathcal{L}R\alpha=i_R d\alpha+d(\alpha(R))=0$, so the Reeb flow preserves both $\alpha$ and $d\alpha$.¹ A local surface of section $D\subset F$ transverse to $R$ inherits the positive area form $d\alpha|D$; the Poincaré first‑hit map preserves $d\alpha|D$ and hence orientation on $D$.² In our chart $U_i$, $d\alpha|{Ti}=\omega_0|{Ti}$ is $c,dy_1\wedge dy_2$ with $c>0$ by construction; therefore $\det D\psi{ij}>0$ in $y$‑coordinates. The same holds at $j$, so $\psi{ij}$ preserves the canonical $\mathbb{R}^2$ orientation.

Remark. If a ridge were Lagrangian ($\omega_0|_{Ti}=0$), it would not define a transverse section and no return map is available. Our genericity excludes this case and matches the combinatorial Reeb model on 4D polytopes.³

Rotation implementation details (guards)

• Numerical extraction. Compute the orthogonal polar factor via SVD ($M=U\Sigma V^\top$, $R=UV^\top$) and set $\operatorname{rot}(M)=\operatorname{atan2}(R_{12},R_{11})\in[-\pi,\pi]$, $\rho=|\operatorname{rot}|/\pi\in[0,1]$. Reject orientation‑reversing cases.
• Alternatives. Trace‑angle and eigen‑angle formulas are equivalent for orthogonal/elliptic cases but we prefer polar/SVD for robustness in floating point.
• Guards and tolerances. Clamp trigonometric arguments to $[-1,1]$; treat $|\operatorname{tr}(R)|\approx 2$ as a near‑identity degeneracy. With non‑Lagrangian ridges and canonical charts, $0<\rho_{ij}<1$ holds in practice, with $\rho_{ij}=0$ only in genuine symmetries (e.g., axis‑aligned cube faces).

Complexity and Practical Pruning

• Number of ridges and edges is polynomial in the input size, but cycle enumeration is exponential in worst case; pruning is essential.
• Fast rejections:
  • Precompute emptiness table for two-step patterns $(i\to j\to k)$ by checking whether $\psi_{ij}(\operatorname{dom}\psi_{ij})$ lies entirely outside $\operatorname{dom}\psi_{jk}$ (LP feasibility).
  • Cache affine maps and half-space transforms to avoid recomputation.
  • Early action lower bounds from per-edge minima give a Dijkstra-like ordering over partial paths.
  • No facet revisits for minimizers: by Haim–Kislev’s “simple loop” theorem (2019), there exists a minimizer that visits the interior of each facet at most once. We therefore restrict to cycles that do not repeat a facet (and hence not a 2‑face), which sharply reduces the search.

Tie-breaking (deterministic and performant)

When exit times to multiple co-facets are equal within tolerance, we need a deterministic choice that does not affect results but impacts performance.

• Options:
  • Lexicographic: choose the co-facet with smallest global index among the minimizers. Deterministic, O(1) overhead after scanning candidates.
  • Numeric ε‑slack: add a tiny $\varepsilon$ to denominators or RHS to break ties consistently (scale by facet norms to be dimensionless).
  • Seeded randomized: break ties using a seeded RNG per facet, fixed across runs for reproducibility.
• Implementation choice: Lexicographic with a symmetric tolerance window $|\tau_{ij}-\tau_{ik}|\le \varepsilon_\tau$. We set $\varepsilon_\tau = \varepsilon_{\mathrm{rel}}\cdot \max(1, \min(\tau_{ij},\tau_{ik})) + \varepsilon_{\mathrm{abs}}$ with small defaults (documented in code).

Implementation Plan (Rust, with PyO3 bindings later)

• Geometry kernels (nalgebra):
  • Types for affine maps on $\mathbb{R}^2$ (Mat2, Vec2, offset), half-space representations in 2D, and simple 2D LP feasibility (or call out to a tiny solver).
  • Builders for domains $\operatorname{dom}\psi_{ij}$ from facet normals $(n_f,b_f)$ via the exit-time inequalities.
• Graphs:
  • Build 2-face digraph with per-edge data: $\operatorname{dom}\psi_{ij}$, $\psi_{ij}$, $\operatorname{im}\psi_{ij}$, $A_{ij}$, $\rho_{ij}$ (constant).
  • Optional: boolean table for $(i,j,k)$ emptiness.
• Search:
  • DFS with incumbent bound, candidate-set push-forward, action/rotation pruning, and fixed-point solve on closure.
  • Deterministic ordering for reproducibility; debug counters for pruned branches, visited edges, cycle lengths, etc.
• Output:
  • Best cycle, fixed point $z_\star$, action $A_\star$; lifted 4D polygonal curve via stored charts; provenance sidecar.

Type Coverage and Assumptions

• We target Type 1 combinatorial orbits (segments inside facets; crossings at ridges) under the symplectic‑polytope assumption (no Lagrangian 2-faces). This aligns with the CH framework and the “simple loop” theorem in Haim–Kislev ensuring a minimizer visits each facet at most once.

Pseudocode (Rust‑ish)

struct RidgeId(u32);
struct FacetId(u32);

struct Aff2 { m: Mat2, t: Vec2 }  // z ↦ m*z + t
struct Aff1 { a: Vec2, b: f64 }   // z ↦ a·z + b

struct EdgeData {
    from: RidgeId,
    to: RidgeId,
    facet: FacetId,
    psi: Aff2,         // ψ_ij
    A_inc: Aff1,       // A_ij on domain
    rho_inc: f64,      // ρ_ij
    dom_i: Poly2,      // dom ψ_ij ⊂ A_i
    img_j: Poly2,      // im ψ_ij ⊂ A_j
}

struct State {
    ridges: Vec<RidgeId>,  // path
    facets_seen: BitSet,    // for no-revisit pruning
    C: Poly2,               // candidate polygon in A_{last}
    A: Aff1,                // accumulated action on A_{last}
    rho: f64,               // accumulated rotation
    Psi: Aff2,              // composed map to the start chart
}

fn extend(state: &State, e: &EdgeData, A_best: f64) -> Option<State> {
    if state.facets_seen.contains(e.facet) { return None; }
    let C_dom = intersect_poly(&state.C, &e.dom_i)?;
    let C1 = aff_image(&e.psi, &C_dom);
    let rho1 = state.rho + e.rho_inc;
    if rho1 > 2.0 { return None; }
    let A1 = compose_aff1(&state.A, &e.psi.inv()) + compose_aff1(&e.A_inc, &e.psi.inv());
    let C2 = intersect_halfspace(&C1, A1, A_best)?;  // { z : A1(z) ≤ A_best }
    Some(State {
        ridges: push(state.ridges, e.to),
        facets_seen: add(state.facets_seen, e.facet),
        C: C2, A: A1, rho: rho1,
        Psi: compose_aff2(&state.Psi, &e.psi),
    })
}

Experiments To Validate Design

• Sanity cases:
  • Polydisks and ellipsoids approximated by tight polytopes; check that results converge to the known $c_{\mathrm{EHZ}}$.
  • Boxes and cross-polytopes in canonical positions; compare against literature/known inequalities for capacities and systolic ratio.
• Ablations:
  • With/without $(i,j,k)$ precomputation; effect on pruning rates.
  • Pull-back vs. push-forward candidate updates; wall time and numerical stability.
• Scaling:
  • Random convex 4D polytopes with controlled facet counts; report cycles visited, pruned branches, and time-to-incumbent.

Notes on Previous Draft

Code Links

• Rust workspace entry: Cargo.toml
• Native library (algorithms): crates/viterbo
• Python bindings (optional): crates/viterbo-py
• Orchestrator/pipelines: src/viterbo/
• Reproduction script: scripts/reproduce.sh

Reviewer Checklist (delete after use)

• Assumptions match our intended class (non-Lagrangian 2-faces)?
• Rotation via polar factor and CZ relation stated?
• Numerical tolerances (ε_det, ε_feas, ε_τ) defaults acceptable?
• Default A_best strategy OK until volume-based constant is cited?
• “Simple loop” pruning enabled by default (per HK 2019)?
• Chart orientation convention acceptable for cross-ridge rotation sign?

Clarifications (unstable, unsorted)

• 1-faces not needed: under the stated genericity assumptions, minimizing cycles do not traverse 1-faces; the algorithm uses flow on facets and crossings at ridges only. The helper geom4::reeb_on_edges_stub() remains intentionally unimplemented.
• Orientation convention: we adopt the unique “natural” convention induced by the ambient symplectic form (require the chart orientation to agree with ω₀|_{face}). The implementation enforces this choice; no runtime toggle exists.
• TODO (owner): write down the quick proof that Lagrangian 2-faces are never crossed in their interior, so omitting them from the graph is safe. Once captured, fold it into the “Setting and Assumptions” section and remove this reminder.

1. Standard fact in contact dynamics: for a contact form α with Reeb vector field R_α, the flow φ_t satisfies φ_t^*α=α and φ_t^*dα=dα since 𝓛_{R_α}α=i_{R_α}dα+d(α(R_α))=0. ↩

2. Poincaré first‑return maps of Reeb flows on 3‑dimensional contact manifolds are area‑preserving with respect to dα on any transverse surface of section; see e.g. Albers–Geiges–Zehmisch (2018). ↩

3. Chaidez–Hutchings (2021): “Computing Reeb dynamics on four‑dimensional convex polytopes”, J. Comput. Dyn. 8(4):403–445; arXiv:2008.10111. ↩

LP/QP Programs for c_EHZ on Convex Polytopes in R^4

Purpose. This chapter turns the Haim–Kislev combinatorial formula for the Ekeland–Hofer–Zehnder capacity into optimization programs that an implementer can assemble from facet data. We give the exact nonconvex QP arising from the formula, practically useful convex relaxations (LP/SDP) that certify bounds, and an implementation and validation plan that integrates with the oriented‑edge and billiard solvers.

Scope. Convex, star‑shaped, non‑degenerate polytopes in (R^4, ω_0). Inputs are in H‑representation with outward unit facet normals and support numbers. See the background on c_EHZ and Reeb dynamics in Ekeland‑Hofer‑Zehnder‑Capacity.md and the oriented‑edge and billiard algorithm chapters:

• Docs: thesis/capacity-algorithm-oriented-edge-graph.md
• Docs: thesis/capacity-algorithm-minkowski-billiard.md

Setting and Notation

• Fix the standard symplectic form ω(u,v) = u^T J v on R^4 with J = [[0, I_2], [-I_2, 0]].
• Let K ⊂ R^4 be a convex polytope with 0 ∈ int K and H‑representation K = { x ∈ R^4 : ⟨a_i, x⟩ ≤ h_i, i = 1,…,m }, where each a_i ∈ R^4 is the outward unit normal of facet i and h_i = h_K(a_i) > 0 is the (oriented) support number.
• Stack A ∈ R^{m×4} with rows a_i^T, h ∈ R^m with entries h_i. Define W := A J A^T ∈ R^{m×m} with entries W_{ij} = ω(a_i,a_j).

Remark (translation/scaling invariance). c_EHZ is translation invariant and 2‑homogeneous under scaling. If 0 ∉ int K, translate once to put 0 inside and recompute h_i; if K is scaled by s>0, then h_i ← s h_i and c_EHZ(sK) = s^2 c_EHZ(K).¹

Literature: exact combinatorial program and “simple loop”

Haim–Kislev give a finite‑dimensional, implementable formula for polytopes; it rests on a “simple loop” property: there exists a minimal‑action generalized closed characteristic that visits the interior of each facet at most once (no facet revisits).¹ In particular:

• Define the feasible weight polytope B_K := { β ∈ R_+^m : A^T β = 0, h^T β = 1 }.
• Then the EHZ capacity of K is c_EHZ(K) = 1 / (2· M_K), where M_K := max_{β ∈ B_K, σ ∈ S_m} Σ_{1 ≤ j < i ≤ m} β_{σ(i)} β_{σ(j)} · ω(a_{σ(i)}, a_{σ(j)}).

This is Equation (1) in Haim–Kislev’s result, restated explicitly also in Leipold–Vallentin (their Eq. (1)) in the P(A,b) convention.[^HK19]² The permutation σ encodes the (single‑visit) order in which the minimizing loop traverses the facets. A reduction narrows σ to cycles of a directed graph built from facet adjacencies, which is useful algorithmically and connects to our oriented‑edge search.[^HK19, Remark 3.11]

Complexity. Computing c_EHZ of polytopes is NP‑hard (even for simplices) by reduction to a quadratic assignment structure hidden in M_K.² Practical algorithms therefore combine exact solves on small/structured inputs with certified convex bounds and specialized search.

Exact nonconvex QP (fixed order) and global mixed QP/QAP

We separate the permutation (order) and the nonnegative weights β.

Program A — nonconvex QP for a fixed order

Inputs: A ∈ R^{m×4}, h ∈ R^m, W = A J A^T, an index order σ of a subset S ⊆ {1,…,m}. Entries with i ∉ S are allowed but will get β_i=0.

Decision variables:

• β ∈ R_+^m (nonnegative facet weights).

Constraints:

• A^T β = 0 (four linear equalities; closure)
• h^T β = 1 (normalization)
• β_i = 0 for i ∉ S (if restricting to a chosen subset/order).

Objective (maximize):

• Q(β;σ) := Σ_{1 ≤ j < i ≤ m} β_{σ(i)} β_{σ(j)} · W_{σ(i),σ(j)}.

Return c(σ) := 1/(2· Q*(σ)) with Q*(σ) the optimal objective value. The exact capacity is c_EHZ(K) = min_σ c(σ) when σ ranges over all orders allowed by the simple‑loop theorem; in practice, restrict σ as in the “Permutation pruning” note below.

Notes:

• This QP is in general indefinite (nonconvex) because W is skew‑symmetric and the lower‑triangular selection depends on σ. Modern global solvers (e.g., Gurobi/CPLEX/SCIP) accept such QPs and solve them via spatial branch‑and‑bound with McCormick relaxations and cuts. Provide and record a global optimality certificate (gap ≤ ε_gap).³
• The four equalities A^T β = 0 enforce the vector equilibrium Σ β_i a_i = 0 which encodes closedness; h^T β = 1 pins the scale (action normalization).

Program B — unified mixed QP/QAP (optional, small m)

Let P ∈ {0,1}^{m×m} be a permutation matrix (P e = e, P^T e = e) and define the strictly lower‑triangular mask L ∈ {0,1}^{m×m} with L_{ij}=1 for i>j and 0 otherwise. Then the objective can be written as Q(β,P) = ⟨ L ∘ (P W P^T), β β^T ⟩, where ∘ is the Hadamard product and ⟨·,·⟩ the Frobenius inner product. This yields a compact mixed 0–1 nonconvex quadratic program over (β,P). It is exact but only practical for very small m due to the QAP‑type combinatorics.[^LV24]³

Permutation pruning. Use Haim–Kislev’s reduction to cycles of a directed graph on facets (edge i→j present when the Reeb velocity can switch from facet i to j) to shrink σ to “combinatorially allowed” orders; this is exactly the graph our oriented‑edge chapter builds on (2‑faces drive feasible switches).¹ In practice we enumerate simple cycles up to a cutoff length L (≤ m), set β_i=0 for i outside the cycle, and run Program A per cycle.

Convex relaxations and bounds (LP/SDP)

Because M_K is a maximum of a bilinear form over a polytope, convex outer approximations in the lifted space give certified bounds. Let y_{ij} ≈ β_i β_j. The constraints A^T β=0, h^T β=1, β ≥ 0 define a compact polytope B_K with explicit upper bounds 0 ≤ β_i ≤ 1/ min(h_i,1e9) since h_i>0 and h^T β=1.

• LP (McCormick) relaxation — lower bound on c_EHZ:

  • For a fixed σ define y_{ij} for i>j and enforce McCormick envelopes over boxes [0,U_i]×[0,U_j]: y_{ij} ≥ 0; y_{ij} ≤ U_i β_j; y_{ij} ≤ U_j β_i; y_{ij} ≥ β_i + β_j − U_i − U_j, with U_i := 1/h_i.
  • Maximize Σ_{i>j} W_{σ(i),σ(j)} y_{σ(i)σ(j)} subject to β ∈ B_K and the envelopes.
  • Call the optimum \hat M_σ ≥ M_σ (outer relaxation). Then c_EHZ(K) ≥ 1/(2· max_σ \hat M_σ).
  • This is fast (HiGHS/CP‑SAT) and scales; it certifies a rigorous lower bound on c_EHZ.

• SDP (Shor/CP) relaxations — stronger lower bounds:

  • Lift to Y ≽ 0 with Y_{ij} ≈ β_i β_j, add linear side constraints Y e = β, diag(Y) ≤ U ∘ β, β ≥ 0, A^T β = 0, h^T β = 1, and maximize ⟨S_σ, Y⟩ with S_σ := L ∘ (P_σ W P_σ^T).
  • Replacing the completely positive cone by the PSD cone gives a tractable SDP; multiple SDP rounds over selected σ produce tight certified lower bounds.³

Upper bounds on c_EHZ. Any feasible (β,σ) yields M ≤ M_K and thus c_EHZ(K) ≤ 1/(2M). Heuristics (local ascent for β on each σ, greedy σ from W’s positive entries, or rounding from relaxations) produce candidates; we then reconstruct a closed polygonal orbit and measure its action (next section), also cross‑checking with the oriented‑edge solver.

Reconstructing a polygonal certificate from (β,σ)

Given a feasible (β,σ), define segment directions v_i := J a_{σ(i)} and positive times t_i := λ β_{σ(i)} for some λ>0. Choose λ so that Σ t_i h_{σ(i)} = 1 (normalization). The closure condition A^T β = 0 implies Σ t_i v_i = 0, so the concatenation gives a closed polygonal loop on ∂K with edges parallel to v_i. Its action equals A = 1 / (2· Σ_{j<i} β_{σ(i)} β_{σ(j)} ω(a_{σ(i)}, a_{σ(j)})) = 1/(2·Q(β;σ)), matching the program’s value; this is the certificate we store (order, nonzero facets, times t_i, action).[^HK19]³

Numerical tolerances for the certificate:

• Closure residual: ||Σ t_i v_i||_2 ≤ τ_close (default 1e−10 · Σ t_i).
• Facet support consistency: |⟨a_{σ(i)}, x⟩ − h_{σ(i)}| ≤ τ_face when sampling a point x on each segment (diagnostic only).
• Action check: recompute polygonal action directly from vertices; relative mismatch ≤ 5e−9.

Implementation Plan

Data plumbing.

• Accept H‑rep with unit normals: A ∈ R^{m×4}, h ∈ R^m, 0 ∈ int K. If normals are not unit, renormalize a_i ← a_i/||a_i||, h_i ← h_i·||a_i||.
• Build W = A J A^T once. Precompute facet graph used by the oriented‑edge chapter; reuse its cycle enumeration to prune σ.

Solvers.

• Exact/upper‑bound candidates: Program A with a global nonconvex QP solver (Gurobi/CPLEX/SCIP). Keep ε_gap ≤ 1e−6 and record solver’s optimality certificate (gap, best bound, node count, time).
• Lower‑bound certificates: LP McCormick (HiGHS) by default; optional SDP (MOSEK/SDPA) for tighter bounds on small m.
• Optional unified Program B for tiny m (≤ 14) to cross‑check reductions.

Assembly details.

• Rust: create crates/viterbo/src/capacity/lpqp.rs with:
  • build_data(hrep: &HPoly4) -> (A: DMatrix<f64>, h: DVector<f64>, W: DMatrix<f64>)
  • enumerate_cycles(g: &FacetGraph, max_len: usize) -> impl Iterator<Item=Vec<usize>>
  • solve_qp_fixed_order(W, A, h, order) -> QpResult { beta, q_value, action, cert }
  • relax_lp_mccormick(...) -> LpBound { m_hat }
• Python: thin wrappers in src/viterbo/rust/ and a stage module src/viterbo/capacity.stage_lpqp.py to drive experiments and write provenance sidecars (viterbo.provenance.write(...)).
• Expose a unified compute_capacity_lpqp(K) that returns:
  • action estimate(s) with certificate(s),
  • lower bound (LP/SDP) and any exact matches,
  • solver logs (gap/time) for reproducibility.

Defaults and budgets (safe wrapper).

• LP/graph enumeration: 10 s budget for m ≤ 80.
• Exact QP per order: 1–5 s; stop after best‑so‑far is within factor 1.02 of LP lower bound or after 120 s total.
• SDP (optional): 60–180 s small‑m runs only.

Validation Plan

Against oriented‑edge algorithm (general polytopes).

• On each test polytope, run the oriented‑edge solver to get an action candidate A_oe. From LP/QP, collect:
  • an upper‑bound candidate A_up (from a feasible (β,σ)),
  • a lower bound A_low (from convex relaxation).
• Validate: A_low ≤ c_EHZ(K) ≤ min(A_oe, A_up) and, when oriented‑edge feasibility gives a simple loop, min(A_oe, A_up) agrees with A_low within tolerance.

Against Minkowski billiard (Lagrangian products).

• For K×T ⊂ R^4, run the billiard algorithm; the returned action must match the LP/QP result (best feasible candidate) within 1e−7 when both are exact.⁴

Sanity set.

• Balls/ellipsoids approximated by tight polytopes (convergence to π r^2).
• Centrally symmetric polytopes with symmetry pairs (use Haim–Kislev’s symmetric simplification).¹
• Small simplices (compare with values obtained in NP‑hardness constructions for cross‑checks).²

Guarantees, Tolerances, and Failure Modes

• Correctness (exact run). If Program A is solved globally for a σ that belongs to the reduced set covering all simple loops, the produced action equals c_EHZ(K). The certificate is the polygonal loop reconstructed above.
• Bounds. For any σ, LP/SDP relaxations certify c_EHZ(K) ≥ 1/(2·\hat M_σ). Any feasible (β,σ) yields c_EHZ(K) ≤ 1/(2·Q(β;σ)).
• Numerics. Use absolute tolerance 1e−9 on linear equalities, 1e−12 clipping for β ≥ 0, and a solver relative gap ≤ 1e−6 for declaring “exact”.
• Degeneracies. If some facets are nearly parallel or h_i very small, rescale K to unit inradius∈[0.5,2] before assembly; undo scaling on output. Fall back to oriented‑edge feasibility if β concentrates on <3 facets (degenerate paths).

References (footnotes)

512b964 (Done. Canonical 2‑face orientation is now enforced everywhere; the knob is gone.)

1. Haim‑Kislev, P. On the Symplectic Size of Convex Polytopes. Geom. Funct. Anal. 29 (2019) 440–463; arXiv:1712.03494. Key results: simple‑loop theorem; combinatorial formula (their Eq. (1)); permutation reduction via a facet graph. Also see the arXiv version for a complete statement. ↩ ↩2 ↩3 ↩4

2. Leipold, K., Vallentin, F. Computing the EHZ capacity is NP‑hard. Proc. Amer. Math. Soc. Ser. B 11 (2024), 603–611; arXiv:2402.09914. Restates the Haim–Kislev formula in P(A,b) form and proves NP‑hardness via reduction to a maximum acyclic subgraph/QAP. ↩ ↩2 ↩3

3. Krupp, S. Calculating the EHZ Capacity of Polytopes. PhD thesis, Univ. Köln (2020). Chapter 5 formulates the maximization, QAP view, and convex (CP/SDP) relaxations that yield strong certified bounds and often exact optima on small instances. ↩ ↩2 ↩3 ↩4

4. Rudolf, D. The Minkowski billiard characterization of the EHZ‑capacity of convex Lagrangian products. J. Dyn. Diff. Eq. (2024); arXiv:2203.01718. Used for cross‑validation on product‑structured examples. ↩

Visualization & Verification

Meta Documentation

This section hosts documentation about meta-level development workflows (not object-level content).

• Agent onboarding and always-relevant rules: see AGENTS.md at the workspace root.
• Topic-specific meta docs that only some tickets need live here (e.g., data IO, CI/tooling).
• Paper + helper scripts: see docs/src/meta/misc-tools.md when you need local copies of bibliography items.

Benchmarks → Docs Pipeline

This note records the Phase 1 design + Phase 2 implementation work for surfacing Criterion micro-benchmarks inside the mdBook site. It follows the flow described in AGENTS.md: tickets → specs → code/tests → data.

Layout, naming, retention

• Raw output lives under target/criterion/... while cargo bench runs. scripts/rust-bench.sh copies only the criterion subtree into data/bench/criterion/ (Git LFS) right after the run so we keep curated JSON without polluting data/ with arbitrary build detritus.
• Build junk (data/bench/release, tmp/, .rustc_info.json) stays untracked via .gitignore. If Cargo drops new cache directories, add them here before running benches on a ticket.
• Derived tables land in docs/assets/bench/ as <timestamp>_<group>.csv plus a Markdown twin for mdBook. Each CSV gets a .run.json sidecar with git_commit, UTC timestamp, host/rust info, and the row count. Small symlinks (current.csv, current_<group>.csv, current_<group>.md) point at the latest export so docs can {{#include}} a stable path.
• Retention: the Python stage keeps the most recent five exports per group by default (value stored in configs/bench/docs_local.json). Older CSV/MD pairs + their .run.json sidecars are deleted to avoid asset bloat while still keeping short-term history for review diffs.

How to run

1. Make sure the benches you want exist (currently crates/viterbo/benches/poly2_bench.rs) and hydrate Git LFS for data/** if needed.
2. Run the benches through the wrapper (safe-wrapped):

   bash scripts/safe.sh --timeout 300 -- bash scripts/rust-bench.sh
   # optional envs: BENCH_EXPORT_DIR=/tmp/bench, BENCH_RUN_POSTPROCESS=1 (to immediately run the stage)
   

   This writes raw Criterion JSON to target/criterion, rsyncs the curated snapshot into data/bench/criterion, and leaves Cargo caches alone.
3. Refresh the docs tables via the Python stage (defaults live in configs/bench/docs_local.json):

   bash scripts/safe.sh --timeout 120 -- uv run python -m viterbo.bench.stage_docs \
     --config configs/bench/docs_local.json
   # add --bench-root /custom/path or --keep 10 if you need overrides
   

4. Commit the tiny files in docs/assets/bench/ together with the data/bench/criterion/** snapshot (Git LFS handles the bulk). If you want the wrapper to handle step 3 automatically, export BENCH_RUN_POSTPROCESS=1 when invoking scripts/rust-bench.sh.

scripts/reproduce.sh now runs both steps (bench + docs stage) unconditionally so every thesis build and mdBook render derives from freshly generated measurements. Whenever a ticket adds a new artifact or visualization, update reproduce.sh in the same PR.

Latest snapshot

The Markdown fragment below is generated by python -m viterbo.bench.stage_docs and pulled in verbatim so reviewers always see the freshest numbers without copy/paste.

Updated 2025-11-11 01:41:11Z · commit 585a129 · host ab5b4864ef14 · rustc rustc 1.91.1 (ed61e7d7e 2025-11-07)

Interpretation cheat sheet

• Both halfspace_intersection and push_forward_strict scale roughly super-linear with the number of halfspaces m, but the latter is consistently ~3× slower for the same m because it performs an extra affine transform before the set operation.
• For tiny polytopes (m ≤ 10) the kernel stays in the sub-microsecond regime, which makes it viable to run exhaustive smoke tests inside CI; by m=100 we are in the ~5 μs (intersection) and ~15 μs (push-forward) range, which is still cheap for batched evaluation.
• The stddev columns are low relative to the mean for larger inputs, which indicates the batches are deterministic enough that storing a single snapshot per commit is meaningful.
• If you see samples < 100, it means Criterion bailed early because the stage was faster than the configured measurement window; rerun with --significance-level tweaks if you need denser samples.

Script internals (reference)

• viterbo.bench.stage_docs parses estimates.json and sample.json for each <group>/<bench>/<param> tuple, computes min, mean, stddev, and copies system metadata from git, platform, and rustc --version.
• Output schema matches the CSV header, so CSVs remain diffable while Markdown renders nicely inside mdBook; both variants share the same timestamp + provenance file.
• Symlinks are relative so Git diffs stay stable and docs can just use the include macro for the “current” snapshot. For example (shown literally, not executed): {{# include ../assets/bench/current_<group>.md}} (note the space after # prevents mdBook from treating this as a real include).
• Use uv run python -m viterbo.bench.stage_docs --config configs/bench/docs_local.json --keep 10 if you need a longer breadcrumb trail before trimming old exports.

Oriented‑Edge: Charts and Rotation

Purpose. Capture the invariants and rationale behind our choice of ridge charts and how we compute and use rotation ρ in the oriented‑edge algorithm, to avoid regressions and unnecessary toggles.

Key decisions

• Fixed per ridge: Each 2‑face (ridge) has a single chart chosen once and used from any incoming facet to keep signs consistent and avoid path‑dependent artifacts.
• Canonical orientation: The ridge basis (u₁,u₂) is orthonormal (Euclidean) and satisfies ω₀(u₁,u₂) > 0. This ties chart orientation to the ambient symplectic form and ensures per‑edge first‑hit maps are orientation‑preserving on admissible domains.
• Rotation from polar factor: For the 2×2 linear part M of the charted per‑edge map, compute the orthogonal polar factor R (M = R S, S ≻ 0) and define ρ := arg(R)/π ∈ [0,1]. This is robust in floating point and invariant to uniform scaling of M; we do not require det M ≈ 1.
• Area‑preserving vs Euclidean charts: First‑hit maps preserve dα‑area, not Euclidean area. Our orthonormal Euclidean charts scale dα by a positive ridge‑dependent constant, so det M need not equal 1; ρ via the polar factor is unaffected. We intentionally do not dα‑normalize charts (see “No toggles” below).
• Accumulation and index: Along closed cycles, ρ accumulates additively and the (generic, 2D) Conley–Zehnder index satisfies μ_CZ = ceil(ρ) + floor(ρ). The index‑3 minimizer has ρ ∈ (1,2), so the search prunes when ρ > 2. This bound is theory‑fixed, not a hyperparameter.

Non‑goals and avoided toggles

• No dual chart mode. We deliberately do not support an opt‑in dα‑unit chart mode (which would enforce det M ≈ 1) because it increases maintenance and test burden without improving rotation computation or pruning.
• No runtime orientation flips. Charts are fixed per ridge; we do not allow user‑configurable orientation switches.

Asserts and guards

• Orientation preservation: debug‑assert det M > 0 on per‑edge maps between canonical charts.
• Rotation extraction: ensure the polar factor R has det R > 0 and clamp arguments for atan2; treat |tr R| ≈ 2 as a near‑identity degeneracy.
• Domain construction: enforce τ > 0 and compare τ_j ≤ τ_k only for forward‑hitting co‑facets (⟨n_k, v_F⟩ > 0), with consistent epsilons.

Cross‑refs

• Background theory: CZ and rotation (Docs: thesis/Ekeland-Hofer-Zehnder-Capacity.md#cz-rotation).
• Algorithm spec: rotation and pruning policy (Docs: thesis/capacity-algorithm-oriented-edge-graph.md).

Git History Cleanup (Situational)

Use only when the owner explicitly requests a repo history rewrite and has scheduled downtime. Escalate first; confirm a backup exists. This page replaces the removed section in AGENTS.md to keep onboarding lean.

Steps (quick guide)

• Pause other worktrees/sessions; get explicit go‑ahead.
• Capture baseline for provenance:
  • git rev-parse main
  • git count-objects -vH
  • git lfs ls-files | wc -l
• Work in a mirror clone:
  • git clone --mirror /workspaces/rust-viterbo /tmp/history-cleanup.git
  • cd /tmp/history-cleanup.git
• Remove legacy bench artifacts:
  • git filter-repo --force --invert-paths --path data/bench/release --path data/bench/release/ --path data/bench/tmp --path data/bench/tmp/ --path data/bench/.rustc_info.json --path data/target --path data/target/ --message-callback 'return message + b\"\n[chore] Drop legacy bench artifacts (Ticket <uuid>)\n\"'
• Verify:
  • git rev-list --objects --all | grep data/bench/release (should be empty)
  • git fsck --full
  • git lfs fetch --all && git lfs fsck
• Publish to staging:
  • Push rewritten result to a staging branch in /workspaces/rust-viterbo (e.g., main-clean).
  • Owner force‑pushes to GitHub; local worktrees rehydrate LFS:
    • git lfs pull --include "data/**" --exclude ""
  • Run quick loops:
    • bash scripts/python-lint-type-test.sh
    • bash scripts/rust-test.sh
• Record actions: commands run and key hashes in the ticket; no extra files are required for the rewrite itself.

Notes

• Do not attempt without owner approval and a quiet window; history rewrites disrupt collaborators’ clones and LFS pointers.
• Prefer targeted filters over broad path patterns; test in a mirror clone first.

Protocol — Meeting on 2025-11-04 (10:00–11:50)

Date. 4 November 2025.
Attendees. Jörn Stöhler; Prof. Kai Cieliebak; Prof. Elisabeth Gaar (University profile).
Purpose. Present the thesis topic and current algorithm, collect Prof. Gaar’s feedback on combinatorial/optimization aspects, and align experiments plus correctness levers for the MSc thesis on systolic ratios of convex polytopes in $\mathbb{R}^4$. The agenda follows Kai’s thesis brief on “Probing Viterbo’s conjecture.”¹

This protocol records the decisions, rationale, and next steps that emerged from the meeting. Full technical notes sit in the appendix for Jörn’s execution.

Context and Purpose

We compute the minimal Reeb action on 4D convex polytopes and report the induced systolic ratio. The protocol captures what we decided, how it affects the project, and the immediate tasks ahead.

Decisions and Rationale

• Focus on 4D convex polytopes; always report both minimal Reeb action and the systolic ratio, starting with simplices and product families.
• Apply a rotation-based prune capped at $\rho \le 2$, using the guarantee that an action minimizer exists with at most that rotation.
• Keep the “visit each facet at most once” prune behind a feature flag until its hypotheses are verified for our model.
• Continue using the 2-face graph $G_2$ representation (details in the appendix) for pruning and evaluation.
• Report strict-admissibility results only; retain a clearly labeled relaxed mode exclusively for upper bounds.

Next Steps

• Supervisors (Kai Cieliebak, Elisabeth Gaar). No immediate actions; optionally confirm default/optional levers and flag constraints for early experiments.
• Author (Jörn Stöhler). Implement ordering and de-dup variants, document toggles, run first sweeps on simplices and products, and maintain technical guardrails/logs. A detailed checklist appears in §7.

Open Questions

• Which classes of polytopes or products should we prioritize (or avoid) in early experiments?
• Any objection to strict-mode results as canonical outputs, with relaxed mode reserved purely for upper bounds and exploratory intuition?
• Which references should we cite for explicit constants when seeding upper bounds?

Reading Guide

The remainder of this page provides the complete notes and follow-ups. Read sequentially for narrative or jump to appendix sections tied to pruning and evaluation details.

1) Executive Summary (Decisions and Impact)

• Working model. Study 4D convex polytopes, compute minimal Reeb action on $\partial X$ and the systolic ratio, and retain both H- and V-representations with cached 2-/3-face incidence so the stable data model remains intact.
• Search representation. Use the 2-face graph $G_2$ with per-step affine transitions and nonnegative action increments (zeros permitted) for pruning strength.
• Rotation prune. Enforce a hard prune at $\rho = 2$ for minimizer candidates; rotation is monotone on convex hypersurfaces and at least one minimizer satisfies $\rho \le 2$.²
• Admissibility. Default to strict admissibility (reject cycles whose reconstructed orbits exit the traversed 2-faces). Keep a separate relaxed mode that may accept inadmissible cycles solely as upper bounds [:?] so correctness stays clear while relaxed runs support optimization.
• “Facet-visit once.” Treat “the minimizer visits each 3-face at most once” as an optional prune behind a flag [:?] and enable it only after checking its hypotheses, since it could dramatically reduce the search space when justified.³
• Ordering and de-duplication. Maintain depth-first search; compare edge-count-first with action-lower-bound-first ordering; enable start-face de-duplication (do not reuse a start 2-face once exhausted). These choices improve pruning and runtime.
• Initial upper bound. Keep the current seed bound, drop $A_{\mathrm{ub}}$ to the first admissible cycle, and investigate the best explicit constant $C$ in $A_{\min} \le \sqrt{C,\mathrm{vol}(X)}$ applicable to our setting [:?] to accelerate convergence with proper citations.
• Experiments. Run experiments on mixed-family 4-simplices to probe the conjectural $\mathrm{sys}(X) \le 3/4$, on broader Lagrangian products $K\times L$, and on counterexamples beyond “pentagon × 90°-rotated pentagon” for thesis-grade coverage.

2) Background Definitions (for clarity; not all discussed live)

• Setting. Work in $\mathbb{R}^4 = \mathbb{C}^2$ with the standard Liouville form $\lambda_{\mathrm{st}} = \tfrac12 \sum_{i=1}^{2}(x_i,dy_i - y_i,dx_i)$. For convex, star-shaped $X \subset \mathbb{R}^4$ with boundary $Y = \partial X$, the Reeb field $R$ satisfies $\iota_R d\lambda_{\mathrm{st}} = 0$ and $\lambda_{\mathrm{st}}(R) = 1$. A closed Reeb orbit $\gamma \subset Y$ has action $A(\gamma)=\int_\gamma \lambda_{\mathrm{st}}$.
• Minimal action and systolic ratio (4D). $A_{\min}(X) = \min_\gamma A(\gamma)$ and $\mathrm{sys}(X) = \dfrac{A_{\min}(X)^2}{2,\mathrm{vol}(X)}$, matching the $n=2$ specialization of the thesis brief’s general definition.¹
• Rotation number and Conley–Zehnder. For nondegenerate $\gamma$, $CZ(\gamma) = \lfloor \rho(\gamma)\rfloor + \lceil \rho(\gamma)\rceil$. On convex $Y \subset \mathbb{R}^4$ we rely on: (i) $\rho(\gamma) > 1$ for all $\gamma$; (ii) some action minimizer $\gamma_{\min}$ exists with $\rho(\gamma_{\min}) \le 2$ (nondegenerate case: $1<\rho(\gamma_{\min})<2$ and $CZ(\gamma_{\min}) = 3$). These facts support pruning.²
• Relevant faces. Orbits flow through 3-faces and cross 2-faces. The algorithm ignores 1-faces/0-faces: a minimizer does not flow through 1-faces (rotation would diverge), and crossings of 1-faces are, at worst, a generic technicality that does not change the algorithm [:?].

3) Meeting Narrative (chronological)

1. Project introduction. Jörn framed the problem via the polytope model, treated the action integral as a positive black box, and illustrated the 4D problem using a 3D/2D skeleton. Outcome: shared understanding of inputs/outputs, including the working equivalence “full orbit $\Longleftrightarrow$ point on the orbit $\Longleftrightarrow$ point on a 2-face of the orbit.”
2. Problem statement, admissibility, objective. Objective: compute $A_{\min}$ and $\mathrm{sys}(X)$ for 4D convex polytopes, focusing on polytopes and Lagrangian products. Admissibility means the reconstructed orbit stays inside its 2-faces. Decision: default strict admissibility; consider a separate relaxed pass where inadmissible cycles supply only upper bounds [:?].
3. Graphs.
   • $G_3$ (3-face graph). Nodes: facets $F$; edges $F\to F'$ when the Reeb flow in $F$ can enter $F'$; data lives on edges, which is awkward to store at nodes.
   • $G_2$ (2-face graph, used). Nodes: 2-faces $E$; edge $E\to E'$ if the flow passes through some 3-face $F$ from $E$ to $E'$. Each step stores an affine map $x' = A_F x + b_F$, a nonnegative action lower bound $\Delta A_{\min}$ (possibly zero), and a rotation lower bound. Edges are colored by the supporting 3-face; nodes can equivalently be colored by entry or exit 3-face (implementation choice pending).
4. Rotation pruning. Enumerate path prefixes and prune whenever the accumulated rotation lower bound exceeds $2$, since rotation is monotone and cannot drop when closing a cycle. This is a hard prune for minimizer candidates, justified by the existence of a minimizer with $\rho \le 2$.²
5. Cycle evaluation and admissibility. For a closed word in $G_2$, compose affine maps to obtain $x \mapsto Ax+b$. If $(I-A)$ is invertible, solve $x^{*} = (I-A)^{-1}b$, compute action, and verify the orbit stays within the traversed 2-faces. Inadmissible cycles might offer upper bounds by analogy with capacity programs, but this pipeline is not yet proven here; treat it as a separate relaxed mode [:?].
6. “Visit each 3-face at most once.” A cited result states that a minimal-action closed characteristic on convex polytopes visits each facet interior at most once. We will expose this as an optional prune behind a flag after validating the hypotheses (default off). [:?]³
7. Ordering and pruning ideas. Compare edge-count-first versus action-lower-bound-first ordering; consider adding a beam later. Additional future levers include (a) incremental admissible-subset tracking on the start 2-face; (b) two-edge feasibility prechecks (defer unless profiling demands); (c) upper-bound seeding via explicit constants and Newton-driven periodic orbits [:?].
8. Representations and performance. Retain H + V representations with cached incidence; conversions are cheap, and precomputing affine data plus lower bounds is also inexpensive. Runtime is dominated by the search tree, so additional pruning and moving work outside the inner loop matter most. A rough desktop measurement was ~100 ms for a 10-facet instance (not a benchmark).
9. Experiments.
   • 4-simplices: treat $\mathrm{sys}(X) \le 3/4$ as conjectural; test multiple families; avoid using this as a prune; locate near-extremizers or violations.
   • Lagrangian products $K\times L$: sweep beyond dual pairs (e.g., triangles × rotated triangles); revisit 2024 counterexample results for inspiration [:?].
   • Counterexamples: extend beyond “pentagon × 90° pentagon” via random and structured sampling.
10. Open theoretical question (Prof. Gaar). “Does any oriented graph occur as a polytope’s Reeb-transition graph?” Interesting but out of thesis scope; parked.

4) Algorithm (current state; optional coding detail is flagged)

1. Precompute. Build $G_2$. For each allowed step $E \xrightarrow{F} E'$, store the local 2D affine map $x' = A_F x + b_F$, nonnegative $\Delta A_{\min}$ (zero allowed), and a per-step rotation lower bound. (Optional later: two-edge feasibility cache.)
2. Enumerate (DFS). Maintain the current 2-face sequence with cumulative lower bounds for action and rotation. Prune when the action lower bound exceeds $A_{\mathrm{ub}}$ or when rotation exceeds $2$ for minimizer candidates.
3. Fixpoint and action. For a closed word, compose to $x \mapsto Ax+b$ and solve $x^{*} = (I-A)^{-1}b$ when the matrix is invertible; compute action from per-edge data. (Optional numerics: guard on $I-A$ condition number with a Newton fallback [:?].)
4. Admissibility.
   • Strict mode (default): check that the reconstructed orbit stays in the traversed 2-faces; reject otherwise.
   • Relaxed mode (separate): allow inadmissible cycles only to tighten $A_{\mathrm{ub}}$; never return them as outputs; clearly label runs [:?].
5. No 3-face repeats (optional). If the facet-repeat theorem applies, reject sequences that revisit a 3-face; keep the toggle off until verified [:?].
6. Start-face de-dup. Once a start 2-face is exhausted, do not reuse it within the same run.
7. Data retention. Track the current path, rotation/action lower bounds, and the best admissible cycle so far. Output the best admissible cycle with its piecewise-linear path and action.

5) Experiments and Mathematical Questions

5.1 Four-simplices and the “3/4” conjecture

Treat $\mathrm{sys}(X) \le 3/4$ for 4-simplices as conjectural. Sample multiple simplex families, log per-family hit rates, and search for near-extremizers; do not enforce the conjecture as a prune.

5.2 Lagrangian products

Enumerate $K\times L$ broadly (symmetric/asymmetric, including rotated polygons) and tabulate high systolic ratios together with structural patterns.

5.3 Upper bounds and seeding

• Maintain the current seed bound and drop it to the first admissible cycle.
• Explore aggressive seeds such as $\sqrt{C,\mathrm{vol}(X)}$ using the best literature constant $C$ [:?].
• Use heuristics that launch random trajectories and apply Newton continuation to find periodic orbits that tighten bounds quickly.

5.4 Covering approach for 4-simplices (research plan)

• Parameter count claim: 5 faces $\Rightarrow$ 20 parameters $\Rightarrow$ 17 after modding out affine symplectomorphisms [:?].
• Focus on small-angle regimes; test whether affine symplectomorphisms enlarge minimal dihedral angles enough for finite coverings.
• Over each covering set, combine upper bounds on action and lower bounds on volume to control $\mathrm{sys}$; consider ellipsoidal coverings aligned to sensitive directions.

6) Decisions vs. Plans vs. Uncertainties

7) Action Items

Immediate

0. Send this protocol to Kai (photos of the blackboard are illegible).
1. Extend the thesis draft with the formal problem, referenced theorems, the algorithm specification with toggles, and the experiments plan.

Algorithm

2. Implement start-face de-duplication per polytope run.
3. Implement ordering variants plus logging (nodes expanded, prune reasons, cycles/sec, wall-time), and consider a small beam later.
4. Implement incremental admissible-subset tracking in local 2D while retaining the final fixed-point check.
5. Add an ill-conditioning guard for $(I-A)$ and a robust fallback [:?].
6. Expose the no-3-face-repeat rule as a toggle, keeping it off until the hypotheses are verified [:?].

Bounds and literature

7. Extract explicit constant(s) $C$ for $A_{\min} \le \sqrt{C,\mathrm{vol}(X)}$ in our setting and log the citations [:?].
8. Document the external facts used for pruning with precise hypotheses (rotation bounds/monotonicity; facet-visit property) and explain their applicability to our model.[^CH]³

Experiments

9. Run mixed-family sampling on 4-simplices, test $\mathrm{sys} \le 3/4$, map near-extremizers, and log per-family hit rates.
10. Sweep across $K\times L$ products, identify high systolic ratios, and capture emerging patterns.
11. Standardize the benchmark harness (CPU, compiler, flags) and record graph sizes, nodes expanded, prune counts, depth histograms, cycles/sec, and wall-time.

8) Appendices

A. Optional implementation notes (for Jörn)

• 2-face coloring. Choose entry- or exit-3-face labeling per node and keep the choice consistent for caching.
• Zero increments. Allow $\Delta A_{\min} = 0$ with no epsilon shift so minima stay unbiased.
• Admissibility modes. Strict mode enforces point-in-polygon tests on each traversed 2-face. Relaxed mode accepts inadmissible cycles only as upper bounds and never as outputs; label runs clearly [:?].
• Numerics. Add a condition-number check for $I-A$; fall back to a robust linear solve or Newton iteration if ill-conditioned [:?].
• Two-edge cache. Defer, because incremental admissible-subset tracking likely dominates.
• Ordering. Implement both edge-count-first and action-lower-bound-first ordering; later add a small beam on the two-score tuple.
• Metrics. Log nodes expanded; prune reasons (action, rotation, admissibility, face repeat); cycles/sec; wall-time; depth histograms; percentage of closed words failing admissibility.

B. Haim–Kislev’s capacity program vs. our graph search

• Haim–Kislev’s method maximizes a finite-dimensional functional using facet normals/coefficients to compute a capacity for convex polytopes.
• Our method enumerates/evaluates cycles in $G_2$ using affine transitions and admissibility checks.
• The relationship is limited: the idea of an “LP on $G_3$” is heuristic, and Haim–Kislev do not present a $G_2$-style affine graph program. We borrow only facts such as “facet-visit once,” not an algorithmic equivalence [:?].³

C. Experiment details (sampling families and products)

• 4-simplices. Vertices-first: sample five points, take their convex hull, rescale to fixed volume, and reject near-degenerate angle sets. Facets-first: sample five oriented planes (normals + offsets), fix the volume, and take the polar if needed. Split compute budgets, log per-family hits, and search for near-extremizers or violations of the conjectural $3/4$.
• Products $K\times L$. Cover symmetric/asymmetric pairs, include rotated configurations, and consider polygons beyond pentagons; tabulate the highest ratios and associated structures.
• Counterexamples. Run random and guided sweeps beyond “pentagon × 90° pentagon.”

D. Covering argument sketch for simplices (research plan)

• Parameter count (meeting claim): 5 faces $\Rightarrow$ 20 parameters $\Rightarrow$ 17 after quotienting by affine symplectomorphisms [:?].
• Identify small-angle regimes as critical; test whether symplectomorphisms can boost minimal angles enough to enable a finite covering.
• For each cover element, bound action from above and volume from below to control $\mathrm{sys}$; ellipsoidal coverings aligned to sensitive directions seem promising.

E. Completeness mapping (from bullet notes to sections)

• Polytope-first introduction and the 3D/2D skeleton correspond to §3.1.
• Problem inputs/outputs and “orbit ↔ point ↔ 2-face point” correspond to §2 and §3.1.
• High- versus low-action behavior appears in §3.2 and §4 (pruning).
• The $\sqrt{C,\mathrm{vol}}$ cutoff, the “$C\approx 4$?” question, and the TODO for the best $C$ sit in §5.3 and §6 [:?].
• $G_3$ versus $G_2$ definitions and the “HK capacity vs. our pipeline” contrast live in §3 and Appendix B.
• Node/edge coloring, zero increments, and early termination topics appear in §3.2 and §4.
• Rotation facts and the prune (including $1<\rho<2$ for a minimizer) appear in §2 and §4.
• The “facet-visit once” topic shows up in §3.2 and §4.3 and is flagged for verification [:?].
• The claim that 1-faces/0-faces are irrelevant (with a generic crossing claim) appears in §2.2 [:?].
• Enumeration, fixpoint, admissibility, and relaxed-mode ideas appear in §4 [:?].
• Ordering, aggressive first guesses, and Newton heuristics appear in §3.2, §4.4, and §5.3.
• Incidence and H↔V remarks (cheap) plus “search dominates” appear in §3 and §8.
• Start-face de-dup appears in §4 and §7.
• Profiling guidance appears in §8 and §7.11.
• The unanswered graph-realizability question sits in §3.10.
• Experiments on simplices, products, and counterexamples appear in §§5.1–5.2 and §3.9.
• Coverings, parameter counts, small angles, and the “3:1 odds” note appear in §5.4 [:?].
• The full action-item list appears in §7.

References

• Chaidez, J.; Hutchings, M. “Computing Reeb dynamics on 4d convex polytopes.” arXiv:2008.10111. Used for rotation bounds for a minimizer and rotation monotonicity on convex hypersurfaces.²
• Haim–Kislev, P. “On the symplectic size of convex polytopes.” arXiv:1712.03494 (v3, 2019). Source for “visits each facet at most once” for a minimal-action closed characteristic (polytope setting).³
• Haim–Kislev, P.; Ostrover, Y. “A Counterexample to Viterbo’s Conjecture.” arXiv:2405.16513. Context: conjecture fails; motivates our exploration of where/how it fails.⁴
• Cieliebak, K. “Thesis topics — Probing Viterbo’s conjecture.” Internal brief that defines $\mathrm{sys}(X)$ and frames the computational task.¹

1. “Thesis topics — Probing Viterbo’s conjecture” (Kai Cieliebak). Matches our 4D systolic ratio definition and frames the computational task. ↩ ↩2 ↩3

2. We rely on (i) the existence of an action minimizer with $\rho \le 2$ (nondegenerate case: $1 < \rho < 2$, $CZ = 3$) and (ii) monotone, nondecreasing rotation along Reeb trajectories on convex hypersurfaces, which together justify pruning partial paths that already exceed $2$. ↩ ↩2 ↩3 ↩4 ↩5

3. We intend to apply the facet-visit property only as an optional prune once its hypotheses match our polytope model. ↩ ↩2 ↩3 ↩4 ↩5 ↩6

4. Disproof of $\mathrm{sys}(X) \le 1$ (Viterbo) via explicit polytopes; sets context but does not affect algorithmic correctness. ↩

2D Convex Polytopes — Design Notes

Goal: extremely fast, robust‑enough 2D routines for half‑space polytopes used at scale (≈1e9 instances) in oriented‑edge DFS. We bias for simple data layout and branch‑light code. Degeneracy handling is intentionally minimal per ticket.

Representation

• Two-tier 2D H-rep:
  • Loose (HPoly2): bag of half‑spaces n·x <= c; no guarantees on order, normalization, or redundancy. Fast to build/compose.
  • Strict (HPoly2Ordered): unit normals, angle‑sorted by atan2, and parallels coalesced (keep most restrictive c). Preserves invariants on insert/merge and after push‑forward.
• Keep vectors contiguous; strict form is cache‑friendly and enables adjacency‑based algorithms.

Core Ops (hot path)

• Push‑forward under affine map y = Mx + t (M invertible): A' = A M^{-1}, b' = b - A' t. Pure algebra; no vertex construction.
  • Code: HPoly2::push_forward, HPoly2Ordered::push_forward, Affine2.
• Intersect with a half‑space / polytope: append (HPoly2) or ordered insert/merge (HPoly2Ordered).
• Membership: n·x <= c + eps for all rows.
• Emptiness:
  • Loose (generic heuristic): test pairwise boundary intersections + probes (HPoly2::is_empty).
  • Strict (exact via HPI): classical half‑plane intersection with deque; includes a quick contradictory‑pares check for opposite parallels (HPoly2Ordered::hpi).

Less‑frequent Ops

• Extremal value of an affine functional f(x)=w·x+a: compute on discovered boundary vertices (same candidate set as emptiness). Returns (min, argmin, max, argmax) or None if no finite vertex is found.
• Affine utilities: inverse, composition, fixed point.
• CZ‑index related rotation of an orientation‑preserving map: stub (cz_index_rotation_stub) until specified in thesis math section.

Interop and Helpers

• Build from 2D points by convex hull (Andrew’s monotone chain) → outward half‑spaces. Useful when projecting 4D faces to 2D.
  • Code: Poly2::from_points_convex_hull.

Random 2D Polygons

• Purpose: provide small, deterministic test instances for Mahler‑product experiments and algorithm smoke tests.
• Location: crates/viterbo/src/geom2/rand.rs (module geom2::rand).
• API:
  • draw_polygon_radial(cfg, token) -> Poly2: radial jitter model over n equally spaced angles with bounded angular (angle_jitter_frac) and radial (radial_jitter) noise.
  • recenter_rescale(poly, Bounds2) -> (Poly2, r_in, r_out): translate to the area‑centroid and scale about the origin to satisfy in‑/out‑radius bounds when consistent.
  • polar(poly) -> Poly2: compute the polar polygon K^\\circ in H‑rep (requires origin in the interior).
• Replay tokens: (seed: u64, index: u64). The sampler uses StdRng::seed_from_u64(mix(seed,index)) so that:
  • Same (seed,index) → same polygon.
  • Different index values partition the stream reproducibly, independent of call order.

Conventions

• Tolerance: eps = 1e-9 for predicates; scale‑agnostic inputs preferred.
• Orientation: standard 2D orientation; outward normal constructed by 90° CCW rotation of hull edges.
• Style: small, explicit functions; explain the “why” in file headers; property tests optional (smoke tests suffice here).

Rationale and Trade‑offs

• H‑rep keeps push‑forwards and intersections O(m) without hulls/vertices.
• Strict vs loose split makes invariants explicit: algorithms that rely on angle order and adjacency run in O(m) after a one‑time O(m log m) normalization; loose remains flexible for fast construction and composition.
• Degenerate cases (parallel strips, nearly co‑incident lines) are rare on hot paths; when needed, strict HPI resolves edge cases.

4D Convex Polytopes — Design Notes

Goal: clear, explicit 4D operations with both H/V representations and simple, reliable conversions. Scale is moderate (≈1e6), so naive enumeration is acceptable and keeps dependencies light.

Representations

• H‑rep: half‑spaces n·x <= c, n ∈ R^4.
• V‑rep: vertices x_i ∈ R^4.
• Poly4 stores both; each side may be empty and is filled on demand (ensure_*).

Conversions

• H→V: enumerate all 4‑tuples of inequalities, solve the equalities, keep feasible points. Deduplicate by metric tolerance.
• V→H: enumerate 4‑tuples of vertices, form the unique hyperplane through them using a 3×4 cofactor‑based nullspace (no SVD). Keep only supporting planes (all vertices on one side); orient as n·x <= c.

These are O(N^4) but used infrequently; they keep the implementation compact and transparent.

Faces

• Derive from H‑rep via vertex saturation:
  • 3‑faces (facets): vertices saturating a single inequality.
  • 2‑faces: vertices saturating a pair.
  • 1‑faces (edges): vertices saturating a triple.
  • 0‑faces: the vertices themselves.
• Return simple structs with facet indices and the corresponding vertex list. For downstream geometry we often only need vertices; equalities are kept as indices for traceability.

Symplectic Helpers

• J‑matrix in 4D: J = [[0, -I],[I, 0]].
• Symplectic check: M^T J M ≈ J (tolerance 1e-8).
• Reeb flow on 3‑faces: R_i = J n_i (unnormalized). 1‑faces: stub until the derivation is written in the thesis.

2‑Face → 2D Mapping

• Given two facet indices (i,j), the 2‑face is the plane orthogonal to span{n_i,n_j}.
• Build an orthonormal basis (u1,u2) of that plane via Gram–Schmidt in 4D; map x ↦ y = Ux with U ∈ R^{2×4} (inverse on the plane is x = U^T y).
• Orientation: we expose a boolean to pick the sign; a precise orientation convention (e.g., (u1,u2,n_i,n_j) positively oriented) can be fixed later if needed by algorithms. See “Open Questions”.
• Project the face’s vertices and construct a 2D polytope in H‑rep via Poly2::from_points_convex_hull, giving a faithful 2D model of the face.

Affine Maps

• Push‑forward (H & V): algebraic transform on H‑rep and direct transform on vertices, requiring M invertible.
• Inversion: (M,t) ↦ (M^{-1}, -M^{-1}t).

Open Questions / Escalations

• Orientation of 2‑faces “as crossed by the Reeb flow”: likely induced by the ambient symplectic 2‑form; we left a design hook (sign boolean) and will add a proof‑based convention on request.
• Reeb flow on 1‑faces: placeholder stub until the derivation is added.

Conventions

• Tolerance eps = 1e-9 for feasibility/equality; 1e-8 for symplectic check.
• Keep code explicit and small; use math comments to tie back to this page.
• Tests: smoke tests for cubes/simplex; property tests optional.

4D Volume Algorithm

Context — The experiments now rely on exact 4D volumes for convex, star-shaped polytopes that already ship with explicit H/V conversions. We compared the first two implementation options: (1) call an existing library such as Qhull/VolEsti via FFI, or (2) implement a bespoke algorithm. Borrowing a library would drag in new build dependencies, FFI wrappers, and conflicting tolerance policies, so we instead coded a self-contained facet-fan algorithm that matches the repository’s explicit enumeration style.

Setting and Notation

• Ambient space: (\mathbb{R}^4) with polytopes given as Poly4, i.e. cached half-spaces n_i \cdot x \le c_i and optional vertex lists.
• Polytopes are convex, star-shaped, and non-degenerate; constraints come from generators that already enforce boundedness.
• enumerate_faces_from_h yields all 0/1/2/3-faces by tracking which inequalities are tight at each vertex; indices reference the original half-spaces.
• We may push forward polytopes under invertible affine maps, so the volume routine must be invariant under volume-preserving transformations.

Definitions

1. Facet fan: for a 3-face (F) we form tetrahedra with vertices (facet_centroid, triangle_on_F) where the triangles tessellate (\partial F). Coning those tetrahedra with an interior polytope point produces 4-simplices.
2. Interior anchor: the centroid of all vertices returned by the H→V enumeration. Convexity guarantees that this barycenter lies in the interior.^¹
3. Ordered ridge polygon: each 2-face inherits a cyclic vertex order by projecting onto the local 2D tangent basis obtained via Gram–Schmidt inside the 4D ambient space.^²
4. Volume decomposition: the polytope is the disjoint union (up to measure-zero overlaps) of 4-simplices formed by (interior_anchor, facet_centroid, triangle vertices) across every triangulated ridge.

Main Facts / Theorems

1. Correctness of the fan decomposition. The surface integral form of Gauss’ divergence theorem states ( \operatorname{Vol}(P) = \tfrac{1}{4} \sum_F h_F \operatorname{Vol}3(F) ) for interior anchor (0).^[^Zie95] By subdividing each (F) into tetrahedra that share a point (p_F) we rewrite that sum as ( \sum_{F,\triangle\subset F} \operatorname{Vol}(\operatorname{conv}{0,p_F,\triangle})). Translating by the actual centroid (c_P) preserves determinants, so summing 4-simplex determinants recovers the true volume without explicit facet areas.
2. Robust ordering of ridge polygons. Because each 2-face lies in a 2D affine plane, Gram–Schmidt on difference vectors returns an orthonormal basis of that plane. Projecting onto the basis, sorting by polar angle, and triangulating with a fan produces a manifold triangulation regardless of vertex order in the cache. The tolerance FEAS_EPS = 1e-9 keeps numerics stable for the moderate coordinate ranges produced by the generators.
3. Breadth-first reuse of enumerations. The algorithm only needs the outputs of enumerate_faces_from_h (vertices + 2/3-faces). No convex-hull rebuild is necessary, so the asymptotic cost stays at (O(H^4)), matching the existing conversion routines.
4. Affine invariance. Each 4-simplex volume is |det([v_1-c, v_2-c, v_3-c, v_4-c])|/24, so composing Poly4::push_forward with a matrix of determinant 1 leaves every determinant unchanged. Unit tests assert invariance under shears with det=1.0 and random translations.
5. Failure modes surface early. Degenerate 2-faces (<3 vertices) or facets (<4 vertices or missing incident ridges) raise a VolumeError, feeding precise debug info back to experiment drivers before any silent mis-computation.

What We Use Later

• viterbo::geom4::volume::{volume4, volume_from_halfspaces, VolumeError} provide Rust callers with a fallible API that can be memoized alongside other Poly4 data.
• PyO3 exposes poly4_volume_from_halfspaces, and viterbo.rust.volume.volume_from_halfspaces adds a typed Python helper; smoke tests cover the binding.
• Criterion benchmark volume4_bench samples bounded random polytopes of varying facet counts to watch for regressions in scripts/rust-bench.sh.
• Docs/tests reference hypercubes and simplices as canonical fixtures; invariance tests guard against accidental determinant scaling.

Deviations and Notes for Review

• We clone 2-face vertex lists to keep the ordering logic simple. Should benchmarks show pressure, revisit this by storing indices instead of full vectors.
• The enumeration routine currently recomputes vertices from H-reps for each call. If repeated volume queries dominate a workload, promote the vertex list to a shared cache or accept vertices/V-rep as inputs to skip the extra pass.

1. Grünbaum (2003), Convex Polytopes (2nd ed.), Springer. Proposition 2.2.6 shows that convex combinations of all vertices lie in the interior. ↩

2. Ziegler (1995), Lectures on Polytopes, Springer. Chapter 5 covers face lattices and volume formulas. ↩

Random Polytope Generators

Goal: define a plug-and-play catalogue of random (and enumerative) 4D polytopes that feed the atlas dataset and future experiments. Every generator must be reproducible, emit only valid polytopes, and surface enough metadata for downstream provenance sidecars.

Generator Interface Conventions

• Inputs = (params, seed) for stochastic streams, or (params, index) for deterministic enumerations. params captures the distribution (facet counts, radii ranges, polygon choices, etc.), while the seed/index replay token pins down the first row produced by that generator.
• Outputs = structured rows: one coherent polytope representation (we standardize on Poly4 with both H- and V-reps available) plus the replay token that regenerates the same row on demand.
• Validity-first = generators may internally sample/reject invalid candidates, but they must yield only valid, star-shaped, origin-containing polytopes. Throughput is secondary to correctness.
• Enumerations = allowed to stop after finitely many rows. They accept cutoff parameters (e.g., max number of facets) and may order outputs arbitrarily as long as replay tokens (index tuples) are stable.
• Single vs stream APIs:
  • generate_single(params, seed) returns one polytope and the canonical replay token.
  • generate_stream(params, seed) yields successive rows (possibly infinite). Streams expose a next() API but also allow replaying an individual row via the accompanying token without iterating the full stream.
• Reproducibility = every row stores the params snapshot and replay token next to the data artifact. When hydrating the dataset, we rebuild rows by calling generate_single with that information.

Implementation note: the rand4 Rust module materializes these conventions via GeneratorParams, ReplayToken, PolytopeSample4, and the PolytopeGenerator4 trait. Python orchestrators can call into PyO3 bindings once exposed.

Algorithm Families

1. Centrally Symmetric Random Halfspaces

• Idea: sample m random directions on the 3-sphere (Gaussian → normalize) and add paired halfspaces ±n·x <= r, where r is drawn from [r_min, r_max].
• Params: number of directions, radius range, optional linear map to inject anisotropy.
• Replay: RNG seed. Replaying re-samples the identical sequence of normals/radii, so the first yielded polytope matches exactly.
• Validity: origin is always feasible (0 <= r). Paired halfspaces enforce boundedness; we reject configs where the linear map is singular.
• Use cases: broad “background” distribution for the atlas dataset; easy to tune between cubes (low variance) and rounded bodies (high m).

2. Mahler Product Sampler (2D × Polar)

• Idea: draw a random 2D convex polygon K (e.g., via radial samples), compute its polar K^◦, then form K × K^◦ ⊂ ℝ⁴. This family stays within the Mahler/Viterbo equivalence regime.
• Params: vertex count range for K, radial jitter budget, minimum/maximum in-radius to keep K full-dimensional.
• Replay: base seed + index mixed into the 2D sampler’s ReplayToken. Replaying regenerates the exact polygon, its polar, and their product.
• Validity: K contains the origin after recenter_rescale; the polar remains bounded. Cartesian products naturally yield star-shaped polytopes.
• Implementation: rand4::MahlerProductGenerator backed by geom2::rand::{draw_polygon_radial, recenter_rescale, polar}. Atlas stages can stream rows or rehydrate via the replay token.

3. Regular Polygon Product Enumerator

• Idea: enumerate tuples (n₁, n₂, rotation₁, rotation₂, scale) and build the lagrangian product of two regular n‑gons. Each tuple deterministically identifies a single 4D polytope.
• Params: discrete sets (or ranges) for n_i, rotation grids (e.g., multiples of π/32), and per-factor scales.
• Replay: the tuple itself. generate_single simply rebuilds the cartesian-product vertex set.
• Validity: direct product of convex polygons, so convex/stable automatically. Enumerations terminate once all tuples are exhausted or a cutoff is hit.

4. Perturbed Special Polytopes

• Idea: start from a catalog (cube, cross-polytope, Viterbo counterexample) and apply small randomized symplectic or affine perturbations. Useful for stress-testing capacity algorithms along known families.
• Params: base polytope id, perturbation budget, symplectic/affine toggle.
• Replay: (base_id, seed); deterministic perturbation sequences.
• Open question: best way to constrain perturbations so that invariants (symplectic, lagrangian product structure) remain intact—escalate before implementing.

5. Streaming Filters / Rejection Pipelines

• Idea: wrap any generator with a predicate (e.g., “systolic ratio ≥ 0.9”) and expose a filtered stream. Inputs add a filter_seed for deterministic acceptance/rejection.
• Policy: the wrapped generator still owns the replay token; the filter stores “skip counts” so that regenerating row k repeats the same sequence of rejections before yielding.

Integration with the Atlas Dataset

• Row schema: {"polytope": Poly4, "generator": name, "params": json, "replay_token": value}. The atlas build stage reads this schema to call generate_single when regenerating artifacts.
• Config knobs: each dataset config lists generators with explicit rows (or max_rows for enumerations). Scaling up/down means editing those integers directly, which keeps per-source cost controls obvious (e.g., “Mahler = 40 rows, Regular products = 10 rows, Catalog = 5 rows”).
• Testing: smoke configs cap each generator at ≤3 rows to keep tests/smoke under 10 seconds; full configs rely on scripts/reproduce.sh.
• Escalation hooks: if a generator cannot hit requested constraints (e.g., Mahler sampler fails to find a polygon with desired in-radius), it should emit structured errors referencing this page and the originating ticket.

Next Steps

1. Surface the rand4 module via PyO3 bindings so Python stages can stream polytopes without re-implementing algorithms.
2. Add benchmark hooks to record generation time per row (to correlate distributions with compute cost).
3. Expand the generator catalogue with sphere packings, zonotopes, and EHZ-focused adversarial shapes once the current families cover the baseline dataset needs.

Implementation Status — Mathematician FAQ

This page wires the current code, tests, and benchmark assets to the concrete questions mathematicians keep asking about the project:

1. What mathematical structures do we already implement?
2. How trustworthy are the numeric kernels today (order-of-magnitude error bounds, failure modes)?
3. Which tests exercise the algebraic paths (as opposed to “it runs” tests)?
4. Where do we already compute $c_{EHZ}$ and the systolic ratio against trusted values?
5. How long does a full systolic-ratio evaluation take on typical inputs (e.g., nine facets)?
6. Which polytope families are covered (Lagrangian products vs. generic/symmetric shapes)?

Each section cross-references the relevant thesis pages, Rust modules, and benchmark snapshots so you can keep drilling down.

1. What features exist today?

Summary: All math-facing layers (geometry, oriented-edge search, generators, atlas pipeline) now run off the same native solver; remaining work is about confidence (more fixtures, telemetry), not missing features.

2. Correctness levels and numerical tolerances

Expectation for large batches (1e6 polytopes). The geometry kernels (H/V conversions, volume, 2D push-forward) already run deterministically with stable tolerances, so we do not anticipate catastrophic drift at scale. The atlas builder now invokes the oriented-edge solver for every row; when the solver fails to find a minimizer the row is explicitly marked as NaN. Achieving “0 false systolic ratios” therefore boils down to tracking/understanding those fallbacks rather than wiring new features.

3. Mathematically meaningful tests

• Graph construction & $\tau$-domain sanity: crates/viterbo/src/oriented_edge/tests.rs::smoke_graph_build_cube_edges_exist and ::tau_domain_basic_properties_on_cube show every ridge/facet pairing respects the analytic inequalities derived in the thesis.
• Fixed-point closure: ::cycle_closure_unique_fixed_point_on_tiny_graph constructs a contraction with known fixed point $z^*$ and verifies the recovered action matches zero.
• Capacity invariants: ::golden_capacity_product_of_squares_matches_min_area, ::golden_capacity_hypercube_minus1_1_pow4_is_4, and ::invariance_under_block_rotation_symplectomorphism compare against Siburg’s area formula and symplectic invariance, catching regressions in both graph building and DFS.
• Non-product shapes: ::cross_polytope_and_simplex_smoke_capacities exercises the solver on the $\ell_1$ ball and the orthogonal simplex (after H-rep conversion), ensuring we cover symmetric/non-generic catalogs.
• Python orchestration: tests/e2e/test_atlas_build.py rebuilds a tiny atlas config, checks the hypercube row, and confirms the preview asset is non-empty—linking the native kernels to stage_save semantics.
• Random generator replay: The rand4 module replays every generated polytope via stored tokens so atlas provenance can be trusted.

Together these tests cover every mathematical code path, from native solvers to the Python atlas orchestration.

4. Where we already compute capacities

No published literature provides “trusted” values for generic random polytopes, so atlas now streams solver outputs directly from the native bindings; future work is to compare aggregates (e.g., by family) and watch for anomalous clusters.

5. Performance snapshots (including nine facets)

Volume scaling. Criterion benches on random H-reps highlight how 4D volume cost grows with facet count:

Updated 2025-11-11 01:41:11Z · commit 585a129 · host ab5b4864ef14 · rustc rustc 1.91.1 (ed61e7d7e 2025-11-07)

Oriented-edge internals. Microbenchmarks for the $\psi_{ij}$ push-forward, $\tau$ inequality, and per-edge lower bound kernels (derived from the cube fixture) show sub-millisecond latencies:

Updated 2025-11-11 01:41:11Z · commit 585a129 · host ab5b4864ef14 · rustc rustc 1.91.1 (ed61e7d7e 2025-11-07)

End-to-end systolic ratio for nine facets. A deterministic “cube with an oblique cap” (eight axis-aligned halfspaces plus $ (1,1,1,1)/2 \cdot x \le 1.8$) gives us the requested data point:

Measured with cargo run -p viterbo --example systolic_ratio --release on 2025-11-08 16:34:12 UTC (commit 7bd6b64)

Interpretation:

• Volume dominates only for very large facet counts (≥48); for nine facets, the facet-fan kernel finishes in ~0.08 ms.
• The oriented-edge solver spends ≈0.65 ms on the nine-facet sample (including graph build + DFS). Because both steps are deterministic, a full systolic ratio evaluation currently lands well under 1 ms on this hardware.
• The atlas builder uses this same native solver at dataset time; tests/e2e/test_atlas_build.py asserts the hypercube capacity ($4$) and systolic ratio ($0.5$) so regressions surface immediately.

6. Supported polytope families

Bottom line: We already support both Lagrangian product families and the generic “atlas background” polytopes. Symmetric shapes are part of the fixture catalog, the solver has dedicated tests for them, and atlas rows now carry finite capacity_ehz / systolic_ratio values unless the solver reports “no cycle”.

7. Outstanding gaps & next steps

1. Instrument solver fallbacks: record how many atlas rows return None (degeneracies, rotation budget hits) and surface that statistic next to dataset summaries.
2. Expand golden fixtures beyond products/symmetric bodies (e.g., orthogonal simplex values, Chaidez–Hutchings counterexample) once their analytic capacities are derived in the thesis.
3. Document failure budgets: classify the fallback causes (e.g., canonicalization errors vs. true absence of admissible cycles) so mathematicians know what “NaN” means operationally.

Keeping this page updated whenever a new generator, test, or visualization lands will make it trivial to answer “are we ready?” the next time the conjecture discussion resurfaces.