All proofs
Project-declaredLean 4.31.0 · mathlib@fabf563a7c95

Prob coeff eq prob affine

ProximityGap.prob_coeff_eq_prob_affine

Plain-language statement

The coefficient-parameterised probability equals the subtype probability. The map r ↦ u₀ + ∑ rᵢ • dᵢ has constant-cardinality fibers (cosets of the kernel of the linear part), so pushforward of uniform gives uniform.

Exact Lean statement

theorem prob_coeff_eq_prob_affine {k : ℕ} [NeZero k]
    (u0 : ι → F) (dirs : Fin k → ι → F)
    (P : (ι → F) → Prop) :
    Pr_{let r ← $ᵖ (Fin k → F)}[P (u0 + ∑ i : Fin k, r i • dirs i)] =
    Pr_{let y ← $ᵖ (Affine.affineSubspaceAtOrigin (F := F) u0 dirs)}[P ↑y]

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
theorem prob_coeff_eq_prob_affine {k : } [NeZero k]    (u0 : ι  F) (dirs : Fin k  ι  F)    (P : (ι  F)  Prop) :    Pr_{let r  $ᵖ (Fin k  F)}[P (u0 + ∑ i : Fin k, r i • dirs i)] =    Pr_{let y  $ᵖ (Affine.affineSubspaceAtOrigin (F := F) u0 dirs)}[P ↑y] := by  classical  -- Reduce both sides to cardinality fractions via prob_uniform_eq_card_filter_div_card.  rw [prob_uniform_eq_card_filter_div_card (fun r : Fin k  F => P (u0 + ∑ i, r i • dirs i))]  rw [prob_uniform_eq_card_filter_div_card    (fun y : ↥(Affine.affineSubspaceAtOrigin (F := F) u0 dirs) => P ↑y)]  -- Define the map g : (Fin k → F) → affineSubspaceAtOrigin  set A := Affine.affineSubspaceAtOrigin (F := F) u0 dirs with hA_def  have hg_mem :  r : Fin k  F, u0 + ∑ i, r i • dirs i  A := fun r =>    (Affine.mem_affineSubspaceFrom_iff (F := F) u0 dirs _).mpr r, rfl  let g : (Fin k  F)  A := fun r => u0 + ∑ i, r i • dirs i, hg_mem r  -- Key: g r₁ = g r₂ ↔ linear parts equal  have hg_eq :  r₁ r₂ : Fin k  F,      g r₁ = g r₂  ∑ i, r₁ i • dirs i = ∑ i, r₂ i • dirs i := by    intro r₁ r₂    constructor    · intro h; exact add_left_cancel (congrArg Subtype.val h)    · intro h; exact Subtype.ext (congrArg (u0 + ·) h)  -- Auxiliary: linear part of (r - r₀)  have hlin_sub :  (r r₀ : Fin k  F),      ∑ i, (r - r₀) i • dirs i = ∑ i, r i • dirs i - ∑ i, r₀ i • dirs i := by    intro r r₀; simp [Pi.sub_apply, sub_smul, Finset.sum_sub_distrib]  -- g is surjective  have hg_surj : Function.Surjective g := by    intro y, hy    obtain β, rfl := (Affine.mem_affineSubspaceFrom_iff (F := F) u0 dirs y).mp hy    exact β, rfl  -- Fiber cardinality is constant: use translation r ↦ r - r₀ to biject fibers.  set K := ((Finset.univ : Finset (Fin k  F)).filter (g · = g 0)).card with hK_def  have hg_fib :  b  Finset.univ.image g,      ((Finset.univ : Finset (Fin k  F)).filter (g · = b)).card = K := by    intro b hb    obtain r₀, _, hr₀ := Finset.mem_image.mp hb    subst hr₀    -- Bijection: fiber(g r₀) ≃ fiber(g 0) via r ↦ r - r₀    apply Finset.card_equiv (Equiv.subRight r₀)    intro r    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Equiv.subRight_apply]    constructor    · intro h      rw [hg_eq] at h ; rw [hlin_sub]      simp only [Pi.zero_apply, zero_smul, Finset.sum_const_zero]      rw [h]; abel    · intro h      rw [hg_eq] at h ; rw [hlin_sub] at h      simp only [Pi.zero_apply, zero_smul, Finset.sum_const_zero] at h      have := sub_eq_zero.mp h; rw [this]  -- K > 0 since fibers are nonempty  have hK_pos : 0 < K := by    rw [hK_def]    exact Finset.card_pos.mpr 0, Finset.mem_filter.mpr Finset.mem_univ _, rfl⟩⟩  -- Step 1: |Fin k → F| = K * |A|  have hcard_eq : Fintype.card (Fin k  F) = K * Fintype.card A := by    rw [show Fintype.card (Fin k  F) = (Finset.univ : Finset (Fin k  F)).card from rfl]    rw [Finset.card_eq_sum_card_image g Finset.univ, Finset.sum_const_nat hg_fib,        Finset.image_univ_of_surjective hg_surj, Finset.card_univ, mul_comm]  -- Step 2: LHS filter = K * RHS filter  have hfilt_eq :      (Finset.filter (fun r : Fin k  F => P (u0 + ∑ i, r i • dirs i)) Finset.univ).card =      K * (Finset.filter (fun y : A => P ↑y) Finset.univ).card := by    -- Rewrite LHS as filter by g    have hfilt_rw :        (Finset.filter (fun r : Fin k  F => P (u0 + ∑ i, r i • dirs i)) Finset.univ) =        (Finset.filter (fun r => P (g r).val) Finset.univ) := by      ext r; simp only [Finset.mem_filter, Finset.mem_univ, true_and, g]    rw [hfilt_rw, Finset.card_eq_sum_card_image g _]    -- For each b in image of the filter, inner filter card = K    have hfib_K :  b  (Finset.filter (fun r => P (g r).val) Finset.univ).image g,        ((Finset.filter (fun r => P (g r).val) Finset.univ).filter (g · = b)).card = K := by      intro b hb      obtain r₀, hr₀_mem, hr₀_eq := Finset.mem_image.mp hb      have hPb : P (g r₀).val := (Finset.mem_filter.mp hr₀_mem).2      subst hr₀_eq      have : (Finset.filter (fun r => P (g r).val) Finset.univ).filter (g · = g r₀) =          Finset.univ.filter (g · = g r₀) := by        ext r; simp only [Finset.mem_filter, Finset.mem_univ, true_and]        constructor        · exact And.right        · intro hr; exact by rwa [show (g r).val = (g r₀).val from congrArg Subtype.val hr], hr      rw [this]      exact hg_fib (g r₀) (Finset.mem_image_of_mem g (Finset.mem_univ r₀))    rw [Finset.sum_const_nat hfib_K]    -- Show: image of {r | P(g r)} under g = {y ∈ A | P ↑y}    have himg : (Finset.filter (fun r => P (g r).val) Finset.univ).image g =        Finset.filter (fun y : A => P ↑y) Finset.univ := by      ext y, hy      simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and]      constructor      · rintro r, hPr, hr_eq        rwa [show (g r).val = y from congrArg Subtype.val hr_eq] at hPr      · intro hPy        obtain r, hr := hg_surj y, hy        exact r, by rwa [show (g r).val = y from congrArg Subtype.val hr], hr    rw [himg]; ring  -- Step 3: The probabilities are card fractions that simplify.  simp only [hfilt_eq, hcard_eq]  push_cast  exact ENNReal.mul_div_mul_left _ _ (by exact_mod_cast hK_pos.ne') (ENNReal.natCast_ne_top K)
Project
ArkLib
License
Apache-2.0
Commit
fad5cbf80877
Source
ArkLib/Data/CodingTheory/ProximityGap/BCIKS20/AffineSpaces.lean:410-511

Reuse this declaration

Bring the exact result into your workflow

The import identifies the source module. Your project still needs the pinned package dependency shown on this page.

What this badge means

This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.

Continue in this project

Related declarations

Project-declaredLean 4.31.0

Affine gaps lifted to interleaved codes

affine_gaps_lifted_to_interleaved_codes

Project documentation

This lemma proves the final algebraic step in the DG25 Theorem 3.1 proof. It shows that if R > e + 1, then e * (R / (R - 1)) < e + 1. The intuition is that the fraction R / (R - 1) is always greater than 1, but as R gets larger, it gets closer to 1. The hypothesis R > e + 1 provides a strong enough bound to ensure the product e * (fraction) do...

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Gadget Decompose coeff

ArkLib.Lattices.Ajtai.gadgetDecompose_coeff

Plain-language statement

The k-th coefficient (k < deg φ) of a gadget-decomposition block is exactly the corresponding digit of the corresponding input coefficient.

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Gadget Decompose lawful

ArkLib.Lattices.Ajtai.gadgetDecompose_lawful

Plain-language statement

The base-b gadget decomposition is a lawful gadget decomposition.

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record