AFTD Auto-Formalizing Theoretical Domains

pmf_uniform_group_convolution_eq_uniform

theoremverifiedformalization

Let G be a finite nonempty additive commutative group. For any probability mass function p on G, the convolution of p with the uniform distribution PMF.uniformOfFintype G, defined as p.bind (fun m => (PMF.uniformOfFintype G).map (fun k => m + k)), is equal to PMF.uniformOfFintype G.

Statement

theorem pmf_uniform_group_convolution_eq_uniform {G : Type*} [AddCommGroup G] [Fintype G] [Nonempty G]
    (p : PMF G) :
    p.bind (fun m => (PMF.uniformOfFintype G).map (fun k => m + k)) = PMF.uniformOfFintype G
Formalizes
Shannon (1949), 'Communication Theory of Secrecy Systems', Theorem 6
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

Read back from the Lean

For any finite, nonempty additive commutative group $G$, and for every probability mass function $p$ on $G$, the monadic bind of $p$ with the family of distributions given by shifting the uniform distribution on $G$ by $m$ (that is, $(PMF.uniformOfFintype\ G).map\ (k \mapsto m + k)$) equals the uniform distribution on $G$ ($PMF.uniformOfFintype\ G$). In other words, the convolution of any probability mass function $p$ on $G$ with the uniform distribution on $G$ is the uniform distribution on $G$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The convolution of p with the uniform distribution is defined monadically by drawing m from p and shifting the uniform distribution by m. Because translation by any element of a finite group is a bijection, shifting the uniform distribution leaves it invariant. Replacing each shift by the uniform distribution turns the convolution into a mixture of a constant distribution, which evaluates to the uniform distribution since the total probability mass of p is 1.

  1. Translation by any element of G preserves the uniform distribution on G.

    For any m ∈ G, left-addition k ↦ m + k is an equivalence of G (Equiv.addLeft m). Pushing forward the uniform distribution on G along this equivalence leaves the uniform distribution invariant (Cslib.Probability.PMF.uniformOfFintype_map_equiv).

    lines 5–6

    uses Cslib.Probability.PMF.uniformOfFintype_map_equiv, Equiv.addLeft

      have h (m : G) : (PMF.uniformOfFintype G).map (fun k => m + k) = PMF.uniformOfFintype G :=
        Cslib.Probability.PMF.uniformOfFintype_map_equiv (Equiv.addLeft m)
  2. The convolution simplifies to the uniform distribution.

    Rewriting the integrand using the translation invariance established in the previous step replaces each translated distribution with the uniform distribution. The convolution expression then reduces to binding p to the constant uniform distribution, which equals the uniform distribution by PMF.bind_const because the total probability mass of p is 1.

    lines 7–8

    uses PMF.bind_const

      simp_rw [h]
      exact PMF.bind_const p (PMF.uniformOfFintype G)
Cslib.Probability.PMF.uniformOfFintype_map_equiv
Pushing forward the uniform distribution on a finite nonempty type along an equivalence yields the uniform distribution on the target type.
Equiv.addLeft
Left-addition by an element of an additive group is an equivalence (permutation) of that group.
PMF.bind_const
Binding any probability mass function with a constant probability distribution yields that constant distribution.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The convolution of any probability distribution with the uniform distribution on a finite additive group is the uniform distribution. -/theorem pmf_uniform_group_convolution_eq_uniform {G : Type*} [AddCommGroup G] [Fintype G] [Nonempty G]    (p : PMF G) :    p.bind (fun m => (PMF.uniformOfFintype G).map (fun k => m + k)) = PMF.uniformOfFintype G := by  have h (m : G) : (PMF.uniformOfFintype G).map (fun k => m + k) = PMF.uniformOfFintype G :=    Cslib.Probability.PMF.uniformOfFintype_map_equiv (Equiv.addLeft m)  simp_rw [h]  exact PMF.bind_const p (PMF.uniformOfFintype G)
See it in the graphDiscuss this resultChallenge it