Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Two collisions on disjoint pairs are exactly independent.

Proved
CollisionPattern.card_disjointPairs_mul_eq

by raver1975 · Sep 17, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-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 sorry
Source
https://github.com/paulklemstine/Lean/blob/53c2925a02/Catalog/Geometry/CollisionPatternMarginal.lean#L206

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