Theorem 1.1 — Shannon-to-min-entropy convolution bound
OpenCaiZhuInfo.Matrix.Supplement.shannon_to_min_entropy_convolutionLet be an arbitrary group, written multiplicatively (discrete; it may be infinite or noncommutative). Let and let be finitely supported probability distributions on , not necessarily identical. Let be independent with ; the convolution is the law of the ordered product . Write for the largest point probability, and for the Shannon entropy in bits. Define
and assume . Then
where and is the natural logarithm. Consequently, if , then
The loss does not depend on the group, the support sizes or the factor laws. This is the fixed-count, distinct-factor form of the entropy conversion; the mission's Corollary 4.4 is its Poisson-count, identical-factor sibling.
Formalization Note The factor laws are a family Q : Fin k → PMF G (index of the paper is Fin index ). The ordered convolution is the left fold of the published binary ordered convolution (law of with from the left law), started at the point mass at the identity, so the product is in this order. The largest point probability is the supremum of the point masses, which is a maximum because the product law is finitely supported; .
Differences from the source:
- encoding: Q₁ ∗ ⋯ ∗ Q_k, the law of Z₁⋯Z_k → left fold of the binary ordered convolution over List.ofFn Q, starting from PMF.pure 1; reason: convolving with the point mass at the identity first changes nothing, and the fold keeps the paper's factor order
- encoding: ‖P‖∞ = max_g P(g) and H∞ = −log₂‖P‖∞ → largestPoint (sSup of the range of the real point masses) and −logb 2 of it; reason: the point masses lie in [0,1] and the product law has finite support, so the supremum is the attained maximum
- encoding: k ≥ ⌈n ln 2⌉ → Nat.ceil ((n : ℝ) * Real.log 2) ≤ k; reason: same condition with the real ceiling of a nonnegative number
import Mathlib import Definitions.Def_CaiZhuInfo_Matrix_compoundPoissonPoint open scoped ENNReal
namespace CaiZhuInfo.Matrix.Supplement
open CaiZhuInfo.Matrix
/-- Cai–Zhu, STOC 2027 submission #616, Theorem 1.1, printed p.2 / PDF p.3.
`Q : Fin k → PMF G` are the (not necessarily identical) factor laws on an arbitrary
group `G`. The convolution `Q₁ ∗ ⋯ ∗ Q_k` is the law of the ordered product
`Z₁ ⋯ Z_k`, written as the left fold of the published binary ordered `convolution`
starting from the point mass at `1`. `s` is the largest support size, `n = ⌊log₂ s⌋`,
`H` the average bit entropy. Both conclusions of the theorem are stated. -/
theorem shannon_to_min_entropy_convolution {G : Type} [Group G] (k : ℕ) (hk : 1 ≤ k)
(Q : Fin k → PMF G) (hQ : ∀ i, (Q i).support.Finite)
(hs : 2 ≤ Finset.univ.sup fun i => (hQ i).toFinset.card) :
let P : PMF G := (List.ofFn Q).foldl convolution (PMF.pure 1)
let s : ℕ := Finset.univ.sup fun i => (hQ i).toFinset.card
let n : ℕ := Nat.log2 s
let H : ℝ := (1 / (k : ℝ)) * ∑ i, supportedEntropy (Q i) (hQ i)
largestPoint (mass P) ≤
C₀ * Real.exp (max ((n : ℝ) * Real.log 2 - k) 0) * (2 : ℝ) ^ (-H) ∧
(Nat.ceil ((n : ℝ) * Real.log 2) ≤ k →
H - c₀ ≤ -logTwo (largestPoint (mass P))) := by sorry
end CaiZhuInfo.Matrix.Supplement