The two-layer cube of (22)
DefinitionBourgainUnion_Euclidean_Supplement_CubeModeldiscrete-geometryfunctional-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with Hamming distance , and let consist of two copies and of . For put and define
This is (22). The definition gives it as a raw distance function on the point set; that it is a metric is Lemma 6.2.
Formalization Note is the type under a fresh name with no metric instance: is and is . is Mathlib's hammingDist.
Definition code
import Mathlib
set_option autoImplicit false
open scoped BigOperators ENNReal
noncomputable section
namespace BourgainUnion.Euclidean.Supplement
/-- The point set `X_m = A ⊔ B` of §6.1, p. 26: `(false, x)` is `a_x` and `(true, x)` is `b_x`,
for `x ∈ Q_m = {0,1}^m`. A plain type synonym, carrying no metric instance. -/
def Cube (m : ℕ) : Type := Bool × (Fin m → Bool)
instance (m : ℕ) : Fintype (Cube m) := inferInstanceAs (Fintype (Bool × (Fin m → Bool)))
/-- `s = √(r² + 1) − r`, p. 26. -/
def cubeS (r : ℝ) : ℝ := Real.sqrt (r^2 + 1) - r
/-- The distance (22), p. 26, as a raw function, with `Ham` the Hamming distance on `Q_m`. -/
def cubeDist (m : ℕ) (r : ℝ) : Cube m → Cube m → ℝ
| (false, x), (false, y) => Real.sqrt (hammingDist x y)
| (false, x), (true, y) => Real.sqrt (r^2 + hammingDist x y)
| (true, x), (false, y) => Real.sqrt (r^2 + hammingDist x y)
| (true, x), (true, y) => min (cubeS r * hammingDist x y) (Real.sqrt (hammingDist x y))
/-- The layer `A = {a_x : x ∈ Q_m}`. -/
def layerA (m : ℕ) : Set (Cube m) := {p | p.1 = false}
end BourgainUnion.Euclidean.Supplement
Source
Dimitar Chakarov, Sepideh Mahabadi, Yury Makarychev, Ali Vakilian, Bourgain's Theorem for a Union of Euclidean Metric Spaces, STOC 2027 submission #699 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/699.pdf, PDF = printed p. 26, §6.1, equation (22)