Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definition 2.3 — (γ,A)(\gamma,A)(γ,A)-isoperimetric approximate tiling of RN\mathbb R^NRN

Definition
ReplParity_Supplement_IAT

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

geometric-measure-theoryisoperimetryp2o-gran-per-chapterp2o-plan-paperp2o-v1replicabilitytilings

Let N≥1N\ge1N≥1, 0<γ<10<\gamma<10<γ<1 and A>0A>0A>0. A (γ,A)(\gamma,A)(γ,A)-isoperimetric approximate tiling (IAT) of Euclidean RN\mathbb R^NRN is a countable family {Sa}a∈L\{S_a\}_{a\in L}{Sa​}a∈L​ of sets labeled by distinct points a∈L⊆RNa\in L\subseteq\mathbb R^Na∈L⊆RN such that each SaS_aSa​ has positive volume, the interiors are pairwise disjoint, each boundary ∂Sa\partial S_a∂Sa​ is piecewise smooth, and every integer unit cube Cw=w+[0,1]NC_w=w+[0,1]^NCw​=w+[0,1]N, w∈ZNw\in\mathbb Z^Nw∈ZN, satisfies

  1. (coverage) volN(Cw∖⋃aSa)≤γ\mathrm{vol}_N\big(C_w\setminus\bigcup_a S_a\big)\le\gammavolN​(Cw​∖⋃a​Sa​)≤γ;
  2. (surface) HN−1(Cw∩⋃a∂Sa)≤A\mathcal H^{N-1}\big(C_w\cap\bigcup_a\partial S_a\big)\le AHN−1(Cw​∩⋃a​∂Sa​)≤A;
  3. (radius) ∥x−a∥2≤1/10\|x-a\|_2\le 1/10∥x−a∥2​≤1/10 for every aaa and every x∈Sax\in S_ax∈Sa​.

Here volN\mathrm{vol}_NvolN​ is Lebesgue measure and HN−1\mathcal H^{N-1}HN−1 is surface area. γ\gammaγ is the uncovered fraction and AAA the surface bound.

Formalization Note The implicit convention N≥1N\ge1N≥1 excludes the undefined codimension-one measure at N=0N=0N=0. HN−1\mathcal H^{N-1}HN−1 is the normalized (N−1)(N-1)(N−1)-dimensional Hausdorff measure π(N−1)/2Γ((N−1)/2+1) 2N−1μHN−1\frac{\pi^{(N-1)/2}}{\Gamma((N-1)/2+1)\,2^{N-1}}\mu_H^{N-1}Γ((N−1)/2+1)2N−1π(N−1)/2​μHN−1​ on RN\mathbb R^NRN with the Euclidean metric, the normalization that agrees with surface area (Mathlib's μH\mu_HμH​ is unnormalized). The paper does not define "piecewise smooth boundary"; it is read as: ∂Sa\partial S_a∂Sa​ lies in a finite union of images fj(Kj)f_j(K_j)fj​(Kj​) of compact sets Kj⊆RN−1K_j\subseteq\mathbb R^{N-1}Kj​⊆RN−1 under C1C^1C1 maps fj:RN−1→RNf_j:\mathbb R^{N-1}\to\mathbb R^Nfj​:RN−1→RN. Coverage bounds the uncovered volume by γ\gammaγ, as printed on p.12. Volumes are outer measures in [0,∞][0,\infty][0,∞].

Definition code
import Mathlib

set_option autoImplicit false

namespace ReplParity

namespace Supplement

open MeasureTheory

/-- **Surface area in Euclidean `ℝ^N`: the normalized `(N−1)`-dimensional Hausdorff measure.**
`H^{N−1} = (α_{N−1} / 2^{N−1}) · μH[N−1]`, where `α_s = π^{s/2} / Γ(s/2 + 1)` is the volume of the
unit ball of `ℝ^s` and `μH[s]` is Mathlib's (unnormalized, `diam^s`) Hausdorff measure on
`EuclideanSpace ℝ (Fin N)` with its `ℓ²` metric. With this normalization `H^s` agrees with
`s`-dimensional surface area on `C¹` surfaces. -/
noncomputable def surfaceArea (N : ℕ) : Measure (EuclideanSpace ℝ (Fin N)) :=
  ENNReal.ofReal (Real.sqrt Real.pi ^ (N - 1) / Real.Gamma (((N - 1 : ℕ) : ℝ) / 2 + 1) /
      2 ^ (N - 1)) • μH[((N - 1 : ℕ) : ℝ)]

/-- The closed integer unit cube `C_w = w + [0, 1]^N`, `w ∈ ℤ^N`. -/
def unitCube (N : ℕ) (w : Fin N → ℤ) : Set (EuclideanSpace ℝ (Fin N)) :=
  {x | ∀ i, (w i : ℝ) ≤ x i ∧ x i ≤ (w i : ℝ) + 1}

/-- A piecewise smooth boundary: the topological boundary of `T` lies in a finite union of images
`f_j(K_j)` of compact sets `K_j ⊆ ℝ^{N−1}` under `C¹` maps `f_j : ℝ^{N−1} → ℝ^N`. -/
def HasPiecewiseSmoothBoundary (N : ℕ) (T : Set (EuclideanSpace ℝ (Fin N))) : Prop :=
  ∃ k : ℕ, ∃ f : Fin k → EuclideanSpace ℝ (Fin (N - 1)) → EuclideanSpace ℝ (Fin N),
    ∃ K : Fin k → Set (EuclideanSpace ℝ (Fin (N - 1))),
      (∀ j, ContDiff ℝ 1 (f j)) ∧ (∀ j, IsCompact (K j)) ∧ frontier T ⊆ ⋃ j, f j '' K j

/-- **Definition 2.3 (Isoperimetric approximate tiling [HIK+24]).** Shen, Zhong, *Replicable Parity
Learning: Cubic Sample Complexity and a Geometric Characterization*, STOC 2027 submission (manuscript
sha256 40424491…), Definition 2.3, pp.11–12 (PDF pp.13–14): "Let 0 < γ < 1 and A > 0. A
(γ, A)-isoperimetric approximate tiling (IAT) of ℝ^N is a countable family {S_a} of sets labeled by
points a ∈ ℝ^N. The sets have positive volume, pairwise disjoint interiors, and piecewise smooth
boundaries, and every integer unit cube C_w = w + [0, 1]^N with w ∈ ℤ^N satisfies the following
conditions. (i) (coverage) vol_N(C_w \ ⋃_a S_a) ≤ γ, (ii) (surface) H^{N−1}(C_w ∩ ⋃_a ∂S_a) ≤ A,
and (iii) (radius) ‖x − a‖₂ ≤ 1/10 for every a and every x ∈ S_a. Here vol_N denotes volume and
H^{N−1} denotes surface area."

The family is given by its set of labels `L ⊆ ℝ^N` and the tile map `a ↦ T a`; the tiles are the
sets `T a` with `a ∈ L` (distinct labels, so each tile has its own label).

**Formalization Note.**
* `ℝ^N` is `EuclideanSpace ℝ (Fin N)`; `vol_N` is its Lebesgue measure `volume`, and `H^{N−1}` is
  `surfaceArea N`, the normalized Hausdorff measure (Mathlib's `μH[N−1]` alone is off by an
  `N`-dependent factor). `∂S_a` is the topological boundary `frontier`.
* "Piecewise smooth boundary" (undefined in the paper) is `HasPiecewiseSmoothBoundary`: the
  boundary lies in finitely many `C¹` images of compact subsets of `ℝ^{N−1}`. The field `dim_pos`
  records the implicit positive-dimension convention, avoiding truncated `N - 1` at `N = 0`.
* Coverage (i) bounds the uncovered volume by `γ`, as printed on p.12 (the paper notes that
  [HIK+24]'s Definition 4.6(4) is misprinted).
* Volumes and surface areas are outer measures; they are `ℝ≥0∞`-valued and compared with
  `ENNReal.ofReal γ`, `ENNReal.ofReal A`. -/
structure IsIAT (N : ℕ) (γ A : ℝ) (L : Set (EuclideanSpace ℝ (Fin N)))
    (T : EuclideanSpace ℝ (Fin N) → Set (EuclideanSpace ℝ (Fin N))) : Prop where
  dim_pos : 1 ≤ N
  params : 0 < γ ∧ γ < 1 ∧ 0 < A
  countable : L.Countable
  pos_volume : ∀ a ∈ L, 0 < volume (T a)
  disjoint_interiors : L.Pairwise (fun a b => Disjoint (interior (T a)) (interior (T b)))
  smooth_boundary : ∀ a ∈ L, HasPiecewiseSmoothBoundary N (T a)
  coverage : ∀ w : Fin N → ℤ, volume (unitCube N w \ ⋃ a ∈ L, T a) ≤ ENNReal.ofReal γ
  surface : ∀ w : Fin N → ℤ,
    surfaceArea N (unitCube N w ∩ ⋃ a ∈ L, frontier (T a)) ≤ ENNReal.ofReal A
  radius : ∀ a ∈ L, ∀ x ∈ T a, dist x a ≤ 1 / 10

end Supplement

end ReplParity
Source
Shen, Zhong, Replicable Parity Learning: Cubic Sample Complexity and a Geometric Characterization, STOC 2027 submission (manuscript sha256 40424491d00eef39c790dd41b7557e0ffdf9de2d14d95ddcd611aeacb0f77a50), Definition 2.3, pp.11-12 (PDF pp.13-14), after [HIK+24, Definition 4.6]

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me