AFTD Auto-Formalizing Theoretical Domains

redistribution_characteristic_upper_norm

theoremverified

For nonnegative reports, the empirical characteristic function has norm at most one on the closed upper half-plane. Only nonemptiness of the profile and report nonnegativity are assumed.

Statement

theorem redistribution_characteristic_upper_norm {n : ℕ} (hn : 0 < n)
    (θ : Fin n → ℝ) (hθ : ∀ j, 0 ≤ θ j) (z : ℂ) (hz : 0 ≤ z.im) :
    ‖redistribution_characteristic θ z‖ ≤ 1
Source
Routine finite-characteristic-function helper for IN-251, arXiv:2610.10995 Lemma4.3 Steps1/2 and equation12. These statements do not assert the half-plane boundary integral inequality or the main harmonic error bound. No research advance.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The proof bounds the empirical characteristic function by separating the scalar factor 1/n from the sum of exponentials ∑_j exp(i * z * θ_j). Because z lies in the closed upper half-plane (Im z ≥ 0) and each report θ_j is nonnegative, the exponent has real part -Im(z) * θ_j ≤ 0, so every exponential summand has norm exp(Re(w)) ≤ 1. The triangle inequality bounds the norm of the sum by n, and multiplying by the normalization factor 1/n yields the upper bound 1.

  1. The number of agents n is strictly positive as a real number: 0 < (n : ℝ).

    The hypothesis hn : 0 < n on natural numbers is cast into the real numbers using exact_mod_cast.

    line 6

      have hnR : (0:ℝ) < n := by exact_mod_cast hn
  2. For each agent j, the complex exponential summand has norm at most 1: ‖exp(I * z * θ j)‖ ≤ 1.

    By Complex.norm_exp, the norm of exp(w) is exp(Re(w)). Setting w = I * z * θ j, expanding its real part using Complex.mul_re, Complex.I_re, and Complex.I_im gives Re(w) = -z.im * θ j. Because z.im ≥ 0 (by hz) and θ j ≥ 0 (by hθ), the product satisfies -z.im * θ j ≤ 0. By Real.exp_le_one_iff, exp(Re(w)) ≤ 1.

    lines 7–13

    uses Complex.norm_exp, Complex.mul_re, Complex.I_re, Complex.I_im, Real.exp_le_one_iff

      have hterm : ∀ j : Fin n, ‖Complex.exp (Complex.I * z * ((θ j : ℝ) : ℂ))‖ ≤ 1 := by
        intro j
        rw [Complex.norm_exp]
        have hre : (Complex.I * z * ((θ j : ℝ) : ℂ)).re = -z.im * θ j := by
          simp [Complex.mul_re, Complex.I_re, Complex.I_im]
        rw [hre, Real.exp_le_one_iff]
        nlinarith [hz, hθ j]
  3. The norm of the sum of the complex exponentials is at most n: ‖∑ j, exp(I * z * θ j)‖ ≤ n.

    By the triangle inequality (norm_sum_le), the norm of the sum is bounded by the sum of the norms. Applying the individual bound ‖exp(I * z * θ j)‖ ≤ 1 from the previous step to each term via Finset.sum_le_sum bounds this by ∑ j, 1 = n. Combining these with le_trans gives the result.

    lines 14–18

    uses le_trans, norm_sum_le, Finset.sum_le_sum

      have hsum : ‖∑ j : Fin n, Complex.exp (Complex.I * z * ((θ j : ℝ) : ℂ))‖ ≤ n := by
        refine le_trans (norm_sum_le _ _) ?_
        calc ∑ j : Fin n, ‖Complex.exp (Complex.I * z * ((θ j : ℝ) : ℂ))‖
            ≤ ∑ _j : Fin n, (1:ℝ) := Finset.sum_le_sum (fun j _ => hterm j)
          _ = n := by simp
  4. The empirical characteristic function has norm at most 1: ‖redistribution_characteristic θ z‖ ≤ 1.

    Unfolding the definition of redistribution_characteristic expresses it as (1 / n) * ∑ j, exp(I * z * θ j). By multiplicativity of the norm (norm_mul), its norm is ‖1 / n‖ * ‖∑ j, exp(...)‖. The scalar norm ‖1 / n‖ simplifies to 1 / n, which is nonnegative. Multiplying the bound ‖∑ j, exp(...)‖ ≤ n by 1 / n via mul_le_mul_of_nonneg_left gives (1 / n) * n = 1, concluding the proof.

    lines 19–25

    uses norm_mul, mul_le_mul_of_nonneg_left

      rw [redistribution_characteristic, norm_mul]
      have hnorm : ‖(1 / (n : ℂ))‖ = 1 / (n:ℝ) := by simp
      rw [hnorm]
      have hpos : (0:ℝ) ≤ 1 / (n:ℝ) := by positivity
      calc (1 / (n:ℝ)) * _
          ≤ (1 / (n:ℝ)) * n := mul_le_mul_of_nonneg_left hsum hpos
        _ = 1 := by field_simp
Complex.I_im
The imaginary unit i has imaginary part 1.
Complex.I_re
The imaginary unit i has real part 0.
Complex.mul_re
The real part of a product of complex numbers satisfies Re(z * w) = Re(z) * Re(w) - Im(z) * Im(w).
Complex.norm_exp
The norm of a complex exponential exp(w) equals the real exponential of its real part, exp(Re(w)).
Finset.sum_le_sum
For any finite index set s, if f(i) ≤ g(i) for all i ∈ s, then the sum of f over s is at most the sum of g over s.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
mul_le_mul_of_nonneg_left
Multiplying an inequality b ≤ c on the left by a nonnegative element a ≥ 0 preserves the inequality: a * b ≤ a * c.
norm_mul
The norm of a product equals the product of the norms: ‖a * b‖ = ‖a‖ * ‖b‖.
norm_sum_le
The triangle inequality for finite sums: the norm of a sum is at most the sum of the norms.
Real.exp_le_one_iff
For a real number x, exp(x) ≤ 1 if and only if x ≤ 0.

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

open Finset MeasureTheorytheorem redistribution_characteristic_upper_norm {n : ℕ} (hn : 0 < n)    (θ : Fin n → ℝ) (hθ : ∀ j, 0 ≤ θ j) (z : ℂ) (hz : 0 ≤ z.im) :    ‖redistribution_characteristic θ z‖ ≤ 1 := by  have hnR : (0:ℝ) < n := by exact_mod_cast hn  have hterm : ∀ j : Fin n, ‖Complex.exp (Complex.I * z * ((θ j : ℝ) : ℂ))‖ ≤ 1 := by    intro j    rw [Complex.norm_exp]    have hre : (Complex.I * z * ((θ j : ℝ) : ℂ)).re = -z.im * θ j := by      simp [Complex.mul_re, Complex.I_re, Complex.I_im]    rw [hre, Real.exp_le_one_iff]    nlinarith [hz, hθ j]  have hsum : ‖∑ j : Fin n, Complex.exp (Complex.I * z * ((θ j : ℝ) : ℂ))‖ ≤ n := by    refine le_trans (norm_sum_le _ _) ?_    calc ∑ j : Fin n, ‖Complex.exp (Complex.I * z * ((θ j : ℝ) : ℂ))‖        ≤ ∑ _j : Fin n, (1:ℝ) := Finset.sum_le_sum (fun j _ => hterm j)      _ = n := by simp  rw [redistribution_characteristic, norm_mul]  have hnorm : ‖(1 / (n : ℂ))‖ = 1 / (n:ℝ) := by simp  rw [hnorm]  have hpos : (0:ℝ) ≤ 1 / (n:ℝ) := by positivity  calc (1 / (n:ℝ)) * _      ≤ (1 / (n:ℝ)) * n := mul_le_mul_of_nonneg_left hsum hpos    _ = 1 := by field_simp
See it in the graphDiscuss this resultChallenge it