Aether Catalog definitions — Geometry_MarginalHierarchy
DefinitionGeometry_MarginalHierarchyaether-cataloggeometry
Definition bundle for the Aether Catalog module Geometry.MarginalHierarchy, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Geometry/MarginalHierarchy.lean by skeleton subtraction
import Mathlib
import Definitions.Def_Geometry_BonferroniMarginals
import Definitions.Def_Geometry_CollisionPatternMarginal
import Definitions.Def_Geometry_ExactFailureMarginal
/-
# Cycle 2: the component law, and the hierarchy of marginal-driven bounds
Research thread *Compression Beyond the Pigeonhole Bound*, cycle v19c (second
loop). Cycle 1 produced three inputs to the Bonferroni machinery:
* `Geometry.CollisionPatternMarginal` — exact marginals of a collision pattern,
computed through an explicit *collapse map*;
* `Geometry.BonferroniMarginals` — the second-moment (Chung–Erdős) machinery and
the unconditional bound `k/(M+k-1)`;
* `Geometry.ExactFailureMarginal` — the exact failure law `1-(1-1/M)^k`.
Two questions were left open by that cycle, and both are settled here.
**(A) Is the collapse-map presentation essential?** No. The marginal of an
arbitrary collision pattern is `M` to the number of *connected components* of the
pattern viewed as a graph, with no auxiliary data:
`MarginalHierarchy.card_patternEvent_eq_pow_components`. The collapse maps of
cycle 1 are then merely a computational device for evaluating the component
count, and `MarginalHierarchy.card_quotient_starPattern` shows the two agree by
*deducing* a purely graph-theoretic component count from the two counting laws.
**(B) How do the three lower bounds relate?** They form a strict hierarchy.
`MarginalHierarchy.second_moment_le_exact` proves that the exact law implies the
second-moment bound (via the integer Bernoulli-type inequality
`MarginalHierarchy.pow_pred_mul_le`), and
`MarginalHierarchy.hashing_bound_hierarchy` assembles the chain
`k/(2M) ≤ k/(M+k-1) ≤ P[failure] = 1-(1-1/M)^k ≤ k/M`
for every typical set, every `M ≥ 1`, and every `k ≤ M+1`. The Bonferroni
output of the catalog is thus located exactly: it is the weakest member of a
four-term chain whose middle terms use *only* the first two marginals.
-/
namespace MarginalHierarchy
open Finset CollisionPattern
/-! ## 1. The component law for pattern marginals -/
variable {ι : Type*} [Fintype ι] [DecidableEq ι] {M : ℕ}
/-- The adjacency relation of a collision pattern. -/
def patternRel (P : Finset (ι × ι)) : ι → ι → Prop := fun a b => (a, b) ∈ P
/-- The connectivity equivalence generated by a collision pattern: its classes
are the connected components of the pattern graph. -/
def patternSetoid (P : Finset (ι × ι)) : Setoid ι := Relation.EqvGen.setoid (patternRel P)
/-- The star pattern: every member of `T` is joined to `x`. -/
def starPattern (T : Finset ι) (x : ι) : Finset (ι × ι) := T.image (fun y => (y, x))
/-! ## 2. The hierarchy of bounds -/
variable {α : Type*} [Fintype α] [DecidableEq α]
end MarginalHierarchy