Cauchy–Schwarz for the moment sequence of a nonnegative integer statistic:
ProvedMomentHierarchy.sq_sum_pow_succ_leaether-cataloglogic
Cauchy–Schwarz for the moment sequence of a nonnegative integer statistic:
(∑ a^{k+1})^2 ≤ (∑ a^k) (∑ a^{k+2}). Proved by symmetrising the double sum and
applying the pointwise AM–GM bound.
theorem MomentHierarchy.sq_sum_pow_succ_le{ι : Type*} (s : Finset ι) (a : ι → ℕ) (k : ℕ) :
(∑ i ∈ s, a i ^ (k + 1)) ^ 2 ≤ (∑ i ∈ s, a i ^ k) * (∑ i ∈ s, a i ^ (k + 2)) := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Logic/MomentHierarchy.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Logic/MomentHierarchy.lean
import Mathlib
import Definitions.Def_Logic_MomentHierarchy
/-!
# The Burnside Moment Hierarchy
For a finite group `G` acting on a finite type `X`, write
`a g := |X^g| = Nat.card (MulAction.fixedBy X g)`
for the number of points fixed by `g`, and
`S k := ∑ g : G, a g ^ k`, `o k := #((Fin k → X) / G)`
for the `k`-th *moment* of the fixed-point statistic and the number of orbits of the
diagonal action of `G` on `k`-tuples of points of `X`.
The organising result of this file is the **moment identity**
`S k = o k * |G|` (`sum_fixedPoints_pow_eq_orbits_mul_card`)
valid for *every* `k`. Its instances are classical:
* `k = 0` : the single orbit on the one-point set of `0`-tuples (`orbitCount_zero`);
* `k = 1` : **Burnside's lemma** / the Cauchy–Frobenius orbit-counting theorem
(`moment_one`);
* `k = 2` : the number of orbits on ordered pairs, i.e. the **rank** of the
permutation action (`moment_two`).
Beyond the identity itself we develop the *hierarchy*: the sequence `k ↦ o k` inherits
strong structural properties from the fact that it is (up to the factor `|G|`) a moment
sequence of a nonnegative integer random variable:
* `orbits_pow_le_succ` : `o` is nondecreasing from `k = 1` on;
* `orbits_pow_log_convex` : `o (k+1) ^ 2 ≤ o k * o (k+2)`, i.e. the orbit-counting
sequence is **log-convex** (a Cauchy–Schwarz / AM–GM phenomenon);
* `card_pow_le_card_group_mul_orbits` and `orbits_pow_le_card_pow` : the sandwich
`|X| ^ k ≤ |G| * o k ≤ |G| * |X| ^ k`;
* `card_group_dvd_moment` : `|G|` divides every moment `S k`.
A bilinear refinement `sum_fixedPoints_mul_eq_orbits_prod_mul_card` computes
`∑ g, |X^g| * |Y^g|` as `|G|` times the number of orbits on `X × Y`; this is the
orbit-counting form of the inner product of two permutation characters.
All statements are phrased with `Nat.card`, so no decidability assumptions are needed.
-/
open MulAction Finset
open MomentHierarchy
variable {G X Y ι : Type*} [Group G] [MulAction G X] [MulAction G Y]
variable {G X Y : Type*} [Group G] [Fintype G] [MulAction G X] [MulAction G Y]
variable {G X : Type*} [Group G] [Fintype G] [MulAction G X] [Finite X]Formal statement
theorem MomentHierarchy.sq_sum_pow_succ_le{ι : Type*} (s : Finset ι) (a : ι → ℕ) (k : ℕ) :
(∑ i ∈ s, a i ^ (k + 1)) ^ 2 ≤ (∑ i ∈ s, a i ^ k) * (∑ i ∈ s, a i ^ (k + 2)) := by sorrySource