redistribution_fill_in_const
The fill-in operation maps a constant function to itself.
Statement
theorem redistribution_fill_in_const {n : ℕ} (hn : 0 < n) (θ : Fin n → ℝ) (c t : ℝ) : redistribution_fill_in θ (fun _ => c) t = c
- Source
- Sanity check of the definitions of arXiv:2610.10995 (Asymptotically optimal public project redistribution without bounded precision): the operations average, so they fix constants.
- Verified
- 09 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- redistribution_fill_inThe fill-in operation on the reports θ_1..θ_n: (A f)(t) = (1/n) Σ_j f(t + θ_j).
The proof, explained
The fill-in operation computes the average over the $n$-element index set $\\mathrm{Fin}(n)$. For a constant function $c$, each term in the sum is $c$, so the sum evaluates to $n \\cdot c$. Since $n > 0$, $n$ is non-zero in $\\mathbb{R}$ and cancels with $1/n$, yielding $c$.
The fill-in operation on a constant function reduces to $\\frac{1}{n} \\cdot (n \\cdot c) = c$.
Unfolding the definition of `redistribution_fill_in`, the operation is the average $\\frac{1}{n} \\sum_{j \\in \\mathrm{Fin}(n)} c$. The sum has $n$ constant terms equal to $c$, so it simplifies to $n \\cdot c$.
uses
Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mulunfold redistribution_fill_in simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul]
$n \\neq 0$ as a real number.
Since $n > 0$ as a natural number, $n \\neq 0$, which casts to $n \\neq 0$ in the real numbers.
have : (n : ℝ) ≠ 0 := by exact_mod_cast hn.ne'
$\\frac{1}{n} \\cdot (n \\cdot c) = c$.
Clearing denominators and cancelling the non-zero factor $n$ completes the proof.
field_simp
Finset.sum_const- Summing a constant value $b$ over a finite set $s$ equals $|s| \\cdot b$ (represented as scalar multiplication by the natural number $|s|$).
Finset.card_univ- The cardinality of the universal finset of a finite type is the cardinality of the type.
Fintype.card_fin- The type $\\mathrm{Fin}(n)$ of natural numbers strictly less than $n$ has cardinality $n$.
nsmul_eq_mul- Scalar multiplication by a natural number $n \\bullet a$ coincides with ring multiplication by the cast of $n$.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem redistribution_fill_in_const {n : ℕ} (hn : 0 < n) (θ : Fin n → ℝ) (c t : ℝ) : redistribution_fill_in θ (fun _ => c) t = c := by unfold redistribution_fill_in simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] have : (n : ℝ) ≠ 0 := by exact_mod_cast hn.ne' field_simp