Two collisions on disjoint pairs are exactly independent.
ProvedCollisionPattern.card_disjointPairs_mul_eqaether-cataloggeometry
Two collisions on disjoint pairs are exactly independent. For the event
H p = H q ∧ H r = H s with p, q, r distinct, p ≠ s and r ≠ s, the
probability is exactly 1/M² — the same second marginal as the vertex-sharing
pattern above. Note that q = s is allowed: the proof only needs the two
collapsed vertices p, r to be distinct from each other and from their targets.
Hence the Bonferroni input is a function of the component count of the pattern
only, and not of its geometry.
theorem CollisionPattern.card_disjointPairs_mul_eq{p q r s : ι} (hpq : p ≠ q) (hrs : r ≠ s)
(hpr : p ≠ r) (hps : p ≠ s) (hqr : q ≠ r) :
M ^ 2 * ((collisionEvent M p q) ∩ (collisionEvent M r s)).card
= M ^ Fintype.card ι := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Geometry/CollisionPatternMarginal.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Geometry/CollisionPatternMarginal.lean
import Mathlib
import Definitions.Def_Geometry_AlmostLosslessCore
import Definitions.Def_Geometry_CollisionPatternMarginal
/-
# Which marginals? Exact marginals of an arbitrary collision pattern
Research thread *Compression Beyond the Pigeonhole Bound*, cycle v19c.
The Bonferroni / second-moment machinery of `Geometry.AlmostLosslessConverse` and
`Geometry.BonferroniMarginals` is indifferent to *which* events it is fed; the
content of a failure bound is entirely in the marginals. `AlmostLosslessCore`
supplies one exact marginal (`card_collisionEvent_mul`, a single pair) and
`AlmostLosslessConverse` one inequality (`card_doubleCollision_mul_le`, two
pairs through a common vertex). This file computes **all** of them at once.
The organising principle is geometric: a *collision pattern* `P` is a graph on
the index set `ι`, a codebook satisfying the pattern is a function constant on
each connected component, and the marginal is therefore `M^{#components}`.
Rather than developing quotient combinatorics we encode the component structure
by an idempotent **collapse map** `f : ι → ι` (a choice of representative per
component), whose image is the component set.
Main results.
* `CollisionPattern.card_collapseEvent` — for any idempotent `f : ι → ι`, the set
of codebooks constant on the fibres of `f` has cardinality exactly
`M ^ |image f|`. (Bijection with functions on the image.)
* `CollisionPattern.card_patternEvent_of_collapse` — the exact marginal of a
collision pattern presented by a collapse map.
* `CollisionPattern.card_starEvent` — the **star marginal**: the event that a
whole set `T` of competitors collides with a fixed `x ∉ T` has cardinality
`M ^ (|ι| - |T|)`, i.e. probability `M^{-|T|}`. All higher Bonferroni terms of
the almost-lossless analysis are instances.
* `CollisionPattern.card_collisionEvent_eq` — recovers
`AlmostLossless.card_collisionEvent_mul` (`|T| = 1`).
* `CollisionPattern.card_doubleCollision_mul_eq` — **upgrades**
`AlmostLossless.card_doubleCollision_mul_le` from `≤` to an *equality*: two
collisions through a common vertex have probability exactly `1/M²`.
* `CollisionPattern.card_disjointPairs_mul_eq` — two collisions on four distinct
vertices are *exactly independent*, again `1/M²`. So the two very different
geometries of a pair of edges (sharing a vertex or not) have the *same*
second marginal: the Bonferroni input is blind to the shape of the pattern and
sees only its component count.
-/
open CollisionPattern
open Finset AlmostLossless
variable {ι : Type*} [Fintype ι] [DecidableEq ι] {M : ℕ}
/-! ## 1. Collapse maps and their exact marginals -/
/-! ## 2. The star marginal: `|T|` competitors colliding with a fixed point -/
/-! ## 3. Consequences: the catalog marginals, exactly -/Formal statement
theorem CollisionPattern.card_disjointPairs_mul_eq{p q r s : ι} (hpq : p ≠ q) (hrs : r ≠ s)
(hpr : p ≠ r) (hps : p ≠ s) (hqr : q ≠ r) :
M ^ 2 * ((collisionEvent M p q) ∩ (collisionEvent M r s)).card
= M ^ Fintype.card ι := by sorrySource