AFTD Auto-Formalizing Theoretical Domains

redistribution_one_draw_gap_bounds

theoremverifiedformalization

Let n ≥ 3 and reports θ ∈ [0,1]^n. For every L-Lipschitz F, every agent i and every t: |(A F)(t) − (A_{-i} F)(t)| ≤ L d_i and |(T F)(t) − (T_{-i} F)(t)| ≤ 2 L d_i.

Statement

theorem redistribution_one_draw_gap_bounds {n : ℕ} (hn : 3 ≤ n) (θ : Fin n → ℝ)
    (hθ : ∀ j, θ j ∈ Set.Icc (0 : ℝ) 1) (i : Fin n) (F : ℝ → ℝ) (L : NNReal)
    (hF : LipschitzWith L F) (t : ℝ) :
    |redistribution_fill_in θ F t - redistribution_fill_in_without θ i F t| ≤
        L * redistribution_one_draw_gap θ i ∧
      |redistribution_trade θ F t - redistribution_trade_without θ i F t| ≤
        2 * L * redistribution_one_draw_gap θ i
Formalizes
arXiv:2610.10995 (Asymptotically optimal public project redistribution without bounded precision), Lemma 4.4.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • redistribution_fill_inThe fill-in operation on the reports θ_1..θ_n: (A f)(t) = (1/n) Σ_j f(t + θ_j).
  • redistribution_fill_in_withoutThe fill-in operation on the reports other than agent i: (A_{-i} f)(t) = (1/(n−1)) Σ_{j≠i} f(t + θ_j).
  • redistribution_tradeThe trade operation on the reports: (T f)(t) = (1/n²) Σ_{j,k} f(t − θ_j + θ_k).
  • redistribution_trade_withoutThe trade operation on the reports other than agent i: (T_{-i} f)(t) = (1/(n−1)²) Σ_{j≠i} Σ_{k≠i} f(t − θ_j + θ_k).
  • redistribution_one_draw_gapThe one-draw gap of agent i: d_i = (1/n)(θ_i + s_{−i}/(n−1)), where s_{−i} is the sum of the other reports.
Used by 1
  • redistribution_iterated_trade_boundsLet n ≥ 3, θ ∈ [0,1]^n and G(t) = max(1 − t, 0). For every k ≥ 0, T^k G and T_{-i}^k G are 1-Lipschitz, and |(T^k G)(t) − (T_{-i}^k G)(t)|…

The proof, explained

The proof establishes bounds on how much the fill-in mechanism (A F)(t) and the trade mechanism (T F)(t) change when agent i is omitted. First, the difference |(A F)(t) - (A_{-i} F)(t)| is rewritten as an average of differences F(t + θ_i) - F(t + θ_j) and bounded by L * d_i using Lipschitz continuity and non-negativity of the reports θ. Second, the trade difference |(T F)(t) - (T_{-i} F)(t)| is bounded by 2 * L * d_i via the triangle inequality using an intermediate average M: swapping summation indices shows that both |(T F)(t) - M| and |M - (T_{-i} F)(t)| reduce to differences of averages of fill-in functions whose pointwise gaps are at most L * d_i.

  1. For n ≥ 2, the difference between the full average of v and the leave-one-out average without agent i equals 1/(n(n-1)) ∑_{j ≠ i} (v_i - v_j)

    Split the sum over all j into v_i plus the sum over j ≠ i using add_sum_erase, evaluate the cardinality of the erased set as n - 1 using card_erase_of_mem and card_fin, and distribute the subtraction using sum_sub_distrib and sum_const. Since n ≥ 2 implies n ≠ 0 and n - 1 ≠ 0, field_simp and ring verify the identity between the two rational expressions.

    lines 6–18

    uses add_sum_erase, card_erase_of_mem, card_fin, sum_sub_distrib, sum_const

      have hi : i ∈ (univ : Finset (Fin n)) := mem_univ i
      have h_split : ∑ j, v j = v i + ∑ j ∈ univ.erase i, v j := by
        rw [← add_sum_erase univ v hi]
      have h1n : 1 ≤ n := by omega
      have h_card : ((univ.erase i : Finset (Fin n)).card : ℝ) = (n : ℝ) - 1 := by
        rw [card_erase_of_mem hi, card_fin, Nat.cast_sub h1n, Nat.cast_one]
      rw [h_split, sum_sub_distrib, sum_const, nsmul_eq_mul, h_card]
      have hn0 : (n : ℝ) ≠ 0 := by positivity
      have hn1 : (n : ℝ) - 1 ≠ 0 := by
        have : (2 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn
        linarith
      field_simp
      ring
  2. For non-negative real numbers a, b ≥ 0, |a - b| ≤ a + b

    By the triangle inequality abs_sub, |a - b| ≤ |a| + |b|. Since a ≥ 0 and b ≥ 0, their absolute values equal themselves by abs_of_nonneg, giving |a - b| ≤ a + b.

    lines 22–24

    uses abs_sub, abs_of_nonneg

      have : |a - b| ≤ |a| + |b| := abs_sub a b
      rw [abs_of_nonneg ha, abs_of_nonneg hb] at this
      exact this
  3. The sum of differences |∑_{j ≠ i} (F(t + θ_i) - F(t + θ_j))| is bounded by ∑_{j ≠ i} L(θ_i + θ_j), and scaling by 1/(n(n-1)) preserves the bound

    Apply the triangle inequality abs_sum_le_sum_abs to bring the absolute value inside the sum. For each j ≠ i, Lipschitz continuity of F gives |F(t + θ_i) - F(t + θ_j)| ≤ L |θ_i - θ_j|, which is bounded by L(θ_i + θ_j) using redistribution_one_draw_gap_bounds_abs_sub_le_add_of_nonneg because θ_i, θ_j ≥ 0. Summing over j ≠ i using sum_le_sum and scaling by the non-negative factor 1/(n(n-1)) via mul_le_mul_of_nonneg_left yields the bound, after introducing the algebraic identity redistribution_one_draw_gap_bounds_sum_diff_identity.

    lines 31–53

    uses redistribution_one_draw_gap_bounds_sum_diff_identity, abs_sum_le_sum_abs, sum_le_sum, redistribution_one_draw_gap_bounds_abs_sub_le_add_of_nonneg, mul_le_mul_of_nonneg_left

      have hn2 : 2 ≤ n := by omega
      have h_id := redistribution_one_draw_gap_bounds_sum_diff_identity hn2 i (fun j => F (t + θ j))
      have h_pos : 0 ≤ 1 / ((n : ℝ) * ((n : ℝ) - 1)) := by
        apply one_div_nonneg.mpr
        have : (3 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn
        nlinarith
      have h_sum_le : |∑ j ∈ univ.erase i, (F (t + θ i) - F (t + θ j))| ≤
          ∑ j ∈ univ.erase i, ((L : ℝ) * (θ i + θ j)) := by
        refine le_trans (abs_sum_le_sum_abs _ _) ?_
        apply sum_le_sum
        intro j hj
        have h_lip : |F (t + θ i) - F (t + θ j)| ≤ (L : ℝ) * |(t + θ i) - (t + θ j)| := by
          rw [← Real.dist_eq, ← Real.dist_eq]
          exact hF.dist_le_mul (t + θ i) (t + θ j)
        have h_simp : (t + θ i) - (t + θ j) = θ i - θ j := by ring
        rw [h_simp] at h_lip
        have hθi : 0 ≤ θ i := (hθ i).1
        have hθj : 0 ≤ θ j := (hθ j).1
        have h_abs_le : |θ i - θ j| ≤ θ i + θ j := redistribution_one_draw_gap_bounds_abs_sub_le_add_of_nonneg hθi hθj
        exact le_trans h_lip (mul_le_mul_of_nonneg_left h_abs_le (NNReal.coe_nonneg L))
      have h_mul_le : 1 / ((n : ℝ) * ((n : ℝ) - 1)) * |∑ j ∈ univ.erase i, (F (t + θ i) - F (t + θ j))| ≤
          1 / ((n : ℝ) * ((n : ℝ) - 1)) * ∑ j ∈ univ.erase i, ((L : ℝ) * (θ i + θ j)) :=
        mul_le_mul_of_nonneg_left h_sum_le h_pos
  4. The fill-in function and the fill-in without agent i differ by at most L * d_i

    Unfold the definitions of the fill-in functions and the one-draw gap d_i. The difference is expressed via the algebraic identity as 1/(n(n-1)) |∑_{j ≠ i} (F(t + θ_i) - F(t + θ_j))|, which is bounded by the previous step via le_trans. Expanding ∑_{j ≠ i} L(θ_i + θ_j) = L((n-1)θ_i + ∑_{j ≠ i} θ_j) and simplifying algebraically matches the definition L * d_i using le_of_eq, abs_mul, and abs_of_nonneg.

    lines 54–67

    uses abs_mul, abs_of_nonneg, le_trans, le_of_eq

      unfold redistribution_fill_in redistribution_fill_in_without redistribution_one_draw_gap
      rw [h_id, abs_mul, abs_of_nonneg h_pos]
      refine le_trans h_mul_le ?_
      apply le_of_eq
      have hi : i ∈ (univ : Finset (Fin n)) := mem_univ i
      have h1n : 1 ≤ n := by omega
      have h_card : ((univ.erase i : Finset (Fin n)).card : ℝ) = (n : ℝ) - 1 := by
        rw [card_erase_of_mem hi, card_fin, Nat.cast_sub h1n, Nat.cast_one]
      rw [← mul_sum, sum_add_distrib, sum_const, nsmul_eq_mul, h_card]
      have hn0 : (n : ℝ) ≠ 0 := by positivity
      have hn1 : (n : ℝ) - 1 ≠ 0 := by
        have : (3 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn
        linarith
      field_simp
  5. If F is L-Lipschitz, then the reflected function s ↦ F(c - s) is also L-Lipschitz

    By LipschitzWith.of_dist_le_mul, it suffices to bound dist(F(c - x), F(c - y)) by L * dist(x, y). Using Real.dist_eq and abs_neg, |(c - x) - (c - y)| = |-(x - y)| = |x - y|, so dist(c - x, c - y) = dist(x, y), and the result follows from the Lipschitz bound for F.

    lines 71–78

    uses LipschitzWith.of_dist_le_mul, Real.dist_eq, abs_neg

      apply LipschitzWith.of_dist_le_mul
      intro x y
      have h1 : dist (c - x) (c - y) = dist x y := by
        rw [Real.dist_eq, Real.dist_eq]
        have : (c - x) - (c - y) = -(x - y) := by ring
        rw [this, abs_neg]
      rw [← h1]
      exact hF.dist_le_mul (c - x) (c - y)
  6. The trade function (T F)(t) equals the full average of fill-in functions (1/n) ∑_j (A F)(t - θ_j)

    Unfold redistribution_trade and redistribution_fill_in, distribute the scalar factors over the sums using mul_sum, and verify summand-by-summand using sum_congr that the expressions agree because (1/n) * (1/n) = 1/n^2.

    lines 83–87

    uses mul_sum, sum_congr

      unfold redistribution_trade redistribution_fill_in
      rw [mul_sum, mul_sum]
      apply sum_congr rfl
      intro j _
      ring
  7. The leave-one-out trade function equals the leave-one-out average of reflected fill-in functions without i

    Unfold redistribution_trade_without and redistribution_fill_in_without. Swapping the order of double summation over j ≠ i and k ≠ i using sum_comm, factoring 1/(n-1)^2 = (1/(n-1)) * (1/(n-1)), and rewriting F(t - θ_j + θ_k) = F(t + θ_k - (0 + θ_j)) expresses the trade function without i as an average over k ≠ i of the fill-in without i for the reflected function s ↦ F(t + θ_k - s).

    lines 93–109

    uses sum_comm, mul_sum, sum_congr

      unfold redistribution_trade_without redistribution_fill_in_without
      have h_comm : (∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, F (t - θ j + θ k)) =
          ∑ k ∈ univ.erase i, ∑ j ∈ univ.erase i, F (t - θ j + θ k) := sum_comm
      rw [h_comm]
      have h_sq : (1 : ℝ) / ((n : ℝ) - 1) ^ 2 = (1 / ((n : ℝ) - 1)) * (1 / ((n : ℝ) - 1)) := by
        simp only [one_div, sq, mul_inv]
      rw [h_sq, mul_assoc, mul_sum]
      congr 1
      apply sum_congr rfl
      intro k _
      have h_fn : (∑ j ∈ univ.erase i, F (t - θ j + θ k)) =
          ∑ j ∈ univ.erase i, (fun s => F (t + θ k - s)) (0 + θ j) := by
        apply sum_congr rfl
        intro j _
        congr 1
        ring
      rw [h_fn]
  8. The average over all agents of the fill-in without i equals the leave-one-out average of the full fill-in for the reflected function

    Unfolding both fill-in definitions expands both sides into double sums with factor 1/(n(n-1)). Swapping the sum over all agents and the sum over agents k ≠ i using sum_comm and matching the arguments t + θ_k - (0 + θ_j) = t - θ_j + θ_k shows that the two double sums are identical.

    lines 115–123

    uses mul_sum, sum_comm, sum_congr

      unfold redistribution_fill_in_without redistribution_fill_in
      simp only [mul_sum, sum_comm (s := univ)]
      apply sum_congr rfl
      intro k _
      apply sum_congr rfl
      intro j _
      have : t + θ k - (0 + θ j) = t - θ j + θ k := by ring
      rw [this]
      ring
  9. If two functions on Fin n differ pointwise by at most C, their averages over all n agents differ by at most C

    Factor out 1/n and distribute the difference across the sum using mul_sub and sum_sub_distrib. Apply the triangle inequality abs_sum_le_sum_abs, bound each term by C via sum_le_sum, and evaluate the constant sum to n * C via sum_const. Multiplying by 1/n preserves the inequality by mul_le_mul_of_nonneg_left and cancels n to leave C.

    lines 128–139

    uses mul_sub, sum_sub_distrib, abs_mul, abs_of_nonneg, abs_sum_le_sum_abs, sum_le_sum, mul_le_mul_of_nonneg_left

      rw [← mul_sub, ← sum_sub_distrib]
      have hn_pos : 0 ≤ 1 / (n : ℝ) := by positivity
      rw [abs_mul, abs_of_nonneg hn_pos]
      have : |∑ j, (f j - g j)| ≤ ∑ j, |f j - g j| := abs_sum_le_sum_abs _ _
      have h_sum_le : ∑ j, |f j - g j| ≤ ∑ j : Fin n, C := sum_le_sum (fun j _ => h j)
      have h_const : ∑ j : Fin n, C = (n : ℝ) * C := by
        simp [sum_const, card_univ]
      have h_step : |∑ j, (f j - g j)| ≤ (n : ℝ) * C := this.trans (h_sum_le.trans_eq h_const)
      have h_mul := mul_le_mul_of_nonneg_left h_step hn_pos
      have hn0 : (n : ℝ) ≠ 0 := by positivity
      have h_cancel : 1 / (n : ℝ) * ((n : ℝ) * C) = C := by field_simp
      exact h_mul.trans_eq h_cancel
  10. If two functions differ pointwise by at most C on the n - 1 agents other than i, their leave-one-out averages differ by at most C

    Similarly factor out 1/(n - 1) using mul_sub and sum_sub_distrib, apply the triangle inequality abs_sum_le_sum_abs, and bound the sum by (n - 1) * C using sum_le_sum. Scaling by 1/(n - 1) via mul_le_mul_of_nonneg_left cancels the factor (n - 1) to yield C.

    lines 145–165

    uses mul_sub, sum_sub_distrib, abs_mul, abs_of_nonneg, abs_sum_le_sum_abs, sum_le_sum, mul_le_mul_of_nonneg_left

      rw [← mul_sub, ← sum_sub_distrib]
      have hn_pos : 0 ≤ 1 / ((n : ℝ) - 1) := by
        apply one_div_nonneg.mpr
        have : (2 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn
        linarith
      rw [abs_mul, abs_of_nonneg hn_pos]
      have : |∑ j ∈ univ.erase i, (f j - g j)| ≤ ∑ j ∈ univ.erase i, |f j - g j| := abs_sum_le_sum_abs _ _
      have h_sum_le : ∑ j ∈ univ.erase i, |f j - g j| ≤ ∑ j ∈ univ.erase i, C := sum_le_sum h
      have hi : i ∈ (univ : Finset (Fin n)) := mem_univ i
      have h1n : 1 ≤ n := by omega
      have h_card : ((univ.erase i : Finset (Fin n)).card : ℝ) = (n : ℝ) - 1 := by
        rw [card_erase_of_mem hi, card_fin, Nat.cast_sub h1n, Nat.cast_one]
      have h_const : ∑ j ∈ univ.erase i, C = ((n : ℝ) - 1) * C := by
        rw [sum_const, nsmul_eq_mul, h_card]
      have h_step : |∑ j ∈ univ.erase i, (f j - g j)| ≤ ((n : ℝ) - 1) * C := this.trans (h_sum_le.trans_eq h_const)
      have h_mul := mul_le_mul_of_nonneg_left h_step hn_pos
      have hn1 : (n : ℝ) - 1 ≠ 0 := by
        have : (2 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn
        linarith
      have h_cancel : 1 / ((n : ℝ) - 1) * (((n : ℝ) - 1) * C) = C := by field_simp
      exact h_mul.trans_eq h_cancel
  11. Split the theorem into the fill-in bound and trade bound, and prove the fill-in bound

    Use constructor to split the conjunction into the two desired inequalities. The fill-in inequality |(A F)(t) - (A_{-i} F)(t)| ≤ L * d_i is proved directly by applying redistribution_one_draw_gap_bounds_fill_in_sub_without_bound.

    lines 174–175

    uses redistribution_one_draw_gap_bounds_fill_in_sub_without_bound

      constructor
      · exact redistribution_one_draw_gap_bounds_fill_in_sub_without_bound hn θ hθ i F L hF t
  12. Define an intermediate average M and bound the distance |(T F)(t) - M| ≤ L * d_i

    Let M be the average over all agents of the fill-in without agent i. Rewriting (T F)(t) as the full average of fill-in functions via redistribution_one_draw_gap_bounds_trade_eq_avg_fill_in, the difference |(T F)(t) - M| is the difference of two full averages whose terms differ by at most L * d_i (by redistribution_one_draw_gap_bounds_fill_in_sub_without_bound). Applying redistribution_one_draw_gap_bounds_sum_diff_bound_univ bounds this difference of averages by L * d_i.

    lines 176–184

    uses redistribution_one_draw_gap_bounds_trade_eq_avg_fill_in, redistribution_one_draw_gap_bounds_sum_diff_bound_univ, redistribution_one_draw_gap_bounds_fill_in_sub_without_bound

      · set M := (1 / (n : ℝ)) * ∑ j, redistribution_fill_in_without θ i F (t - θ j)
        have hn_pos : 0 < n := by omega
        have hn2 : 2 ≤ n := by omega
        have h1 : |redistribution_trade θ F t - M| ≤ (L : ℝ) * redistribution_one_draw_gap θ i := by
          rw [redistribution_one_draw_gap_bounds_trade_eq_avg_fill_in]
          apply redistribution_one_draw_gap_bounds_sum_diff_bound_univ hn_pos
          intro j
          exact redistribution_one_draw_gap_bounds_fill_in_sub_without_bound hn θ hθ i F L hF (t - θ j)
        have h2 : |M - redistribution_trade_without θ i F t| ≤ (L : ℝ) * redistribution_one_draw_gap θ i := by
  13. Bound the second difference |M - (T_{-i} F)(t)| ≤ L * d_i

    By redistribution_one_draw_gap_bounds_mid_eq_sum_fill_in and redistribution_one_draw_gap_bounds_trade_without_eq, both M and (T_{-i} F)(t) are expressed as averages over the n - 1 agents k ≠ i of the full fill-in and fill-in without i for the reflected function s ↦ F(t + θ_k - s). Since this reflected function is L-Lipschitz by redistribution_one_draw_gap_bounds_lipschitz_comp_sub, each term differs by at most L * d_i by redistribution_one_draw_gap_bounds_fill_in_sub_without_bound. Lemma redistribution_one_draw_gap_bounds_sum_diff_bound_erase then bounds this difference of averages by L * d_i.

    lines 185–191

    uses redistribution_one_draw_gap_bounds_mid_eq_sum_fill_in, redistribution_one_draw_gap_bounds_trade_without_eq, redistribution_one_draw_gap_bounds_sum_diff_bound_erase, redistribution_one_draw_gap_bounds_lipschitz_comp_sub, redistribution_one_draw_gap_bounds_fill_in_sub_without_bound

          dsimp [M]
          rw [redistribution_one_draw_gap_bounds_mid_eq_sum_fill_in, redistribution_one_draw_gap_bounds_trade_without_eq]
          apply redistribution_one_draw_gap_bounds_sum_diff_bound_erase hn2
          intro k _
          have hG_lip : LipschitzWith L (fun s => F (t + θ k - s)) :=
            redistribution_one_draw_gap_bounds_lipschitz_comp_sub hF (t + θ k)
          exact redistribution_one_draw_gap_bounds_fill_in_sub_without_bound hn θ hθ i _ L hG_lip 0
  14. Combine the two bounds via the triangle inequality to conclude |(T F)(t) - (T_{-i} F)(t)| ≤ 2 * L * d_i

    Decompose the trade difference as ((T F)(t) - M) + (M - (T_{-i} F)(t)) and apply the triangle inequality abs_add_le. Adding the two bounds of L * d_i using add_le_add gives 2 * L * d_i, completing the proof.

    lines 192–202

    uses abs_add_le, add_le_add

        have h_tri : |redistribution_trade θ F t - redistribution_trade_without θ i F t| ≤
            |redistribution_trade θ F t - M| + |M - redistribution_trade_without θ i F t| := by
          have : redistribution_trade θ F t - redistribution_trade_without θ i F t =
              (redistribution_trade θ F t - M) + (M - redistribution_trade_without θ i F t) := by ring
          rw [this]
          exact abs_add_le _ _
        refine h_tri.trans ?_
        have : (L : ℝ) * redistribution_one_draw_gap θ i + (L : ℝ) * redistribution_one_draw_gap θ i =
            2 * (L : ℝ) * redistribution_one_draw_gap θ i := by ring
        rw [← this]
        exact add_le_add h1 h2
add_sum_erase
Separating an element a ∈ s from a finite sum expresses the total sum as f(a) plus the sum over s \ {a}
card_erase_of_mem
Removing an element a ∈ s reduces the cardinality of s by 1
card_fin
The finite set Fin n has cardinality n
sum_sub_distrib
The sum of a difference of functions equals the difference of their sums
sum_const
Summing a constant over a finite set equals the cardinality of the set times the constant
abs_sub
The absolute value of a difference is at most the sum of the absolute values
abs_of_nonneg
The absolute value of a non-negative number equals itself
redistribution_one_draw_gap_bounds_sum_diff_identity
For n ≥ 2, the difference between the full average of v and the leave-one-out average without i equals 1/(n(n-1)) times the sum of v_i - v_j over j ≠ i
abs_sum_le_sum_abs
The absolute value of a finite sum is bounded by the sum of absolute values (triangle inequality)
sum_le_sum
If f(i) ≤ g(i) for all elements of a finite set, then the sum of f is at most the sum of g
redistribution_one_draw_gap_bounds_abs_sub_le_add_of_nonneg
For non-negative real numbers a, b ≥ 0, |a - b| ≤ a + b
mul_le_mul_of_nonneg_left
Multiplying an inequality by a non-negative number preserves the inequality
le_trans
If a ≤ b and b ≤ c, then a ≤ c
le_of_eq
An equality implies the corresponding non-strict inequality
abs_mul
The absolute value of a product is the product of the absolute values
LipschitzWith.of_dist_le_mul
A function whose output distance is bounded by K times input distance is K-Lipschitz
Real.dist_eq
The distance between real numbers x and y equals |x - y|
abs_neg
The absolute value of -a equals the absolute value of a
mul_sum
Distributivity of multiplication over finite sums
sum_congr
Two sums are equal if their index sets are equal and their summands agree pointwise
sum_comm
Fubini's theorem for finite sums: swapping the order of double summation
mul_sub
Left distributivity of multiplication over subtraction
redistribution_one_draw_gap_bounds_fill_in_sub_without_bound
The fill-in function and its version without agent i differ by at most L times the one-draw gap d_i
redistribution_one_draw_gap_bounds_trade_eq_avg_fill_in
The trade function equals the average of the fill-in function evaluated at shifted points t - θ_j
redistribution_one_draw_gap_bounds_sum_diff_bound_univ
If two functions on Fin n differ pointwise by at most C, their averages over the full set differ by at most C
redistribution_one_draw_gap_bounds_mid_eq_sum_fill_in
The average of fill-in without agent i over all agents equals the leave-one-out average of full fill-in for the reflected function s ↦ F(t + θ_k - s)
redistribution_one_draw_gap_bounds_trade_without_eq
The leave-one-out trade function equals the leave-one-out average of fill-in without i for the reflected function
redistribution_one_draw_gap_bounds_sum_diff_bound_erase
If two functions differ pointwise by at most C on the n-1 agents other than i, their averages over those agents differ by at most C
redistribution_one_draw_gap_bounds_lipschitz_comp_sub
Composing an L-Lipschitz function with reflection s ↦ c - s preserves L-Lipschitz continuity
abs_add_le
The absolute value of a sum is at most the sum of absolute values
add_le_add
If a ≤ b and c ≤ d, then a + c ≤ b + d

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 Finsetlemma redistribution_one_draw_gap_bounds_sum_diff_identity {n : ℕ} (hn : 2 ≤ n) (i : Fin n) (v : Fin n → ℝ) :    (1 / (n : ℝ)) * ∑ j, v j - (1 / ((n : ℝ) - 1)) * ∑ j ∈ univ.erase i, v j =    (1 / ((n : ℝ) * ((n : ℝ) - 1))) * ∑ j ∈ univ.erase i, (v i - v j) := by  have hi : i ∈ (univ : Finset (Fin n)) := mem_univ i  have h_split : ∑ j, v j = v i + ∑ j ∈ univ.erase i, v j := by    rw [← add_sum_erase univ v hi]  have h1n : 1 ≤ n := by omega  have h_card : ((univ.erase i : Finset (Fin n)).card : ℝ) = (n : ℝ) - 1 := by    rw [card_erase_of_mem hi, card_fin, Nat.cast_sub h1n, Nat.cast_one]  rw [h_split, sum_sub_distrib, sum_const, nsmul_eq_mul, h_card]  have hn0 : (n : ℝ) ≠ 0 := by positivity  have hn1 : (n : ℝ) - 1 ≠ 0 := by    have : (2 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn    linarith  field_simp  ringlemma redistribution_one_draw_gap_bounds_abs_sub_le_add_of_nonneg {a b : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b) :    |a - b| ≤ a + b := by  have : |a - b| ≤ |a| + |b| := abs_sub a b  rw [abs_of_nonneg ha, abs_of_nonneg hb] at this  exact thislemma redistribution_one_draw_gap_bounds_fill_in_sub_without_bound {n : ℕ} (hn : 3 ≤ n) (θ : Fin n → ℝ)    (hθ : ∀ j, θ j ∈ Set.Icc (0 : ℝ) 1) (i : Fin n) (F : ℝ → ℝ) (L : NNReal)    (hF : LipschitzWith L F) (t : ℝ) :    |redistribution_fill_in θ F t - redistribution_fill_in_without θ i F t| ≤      L * redistribution_one_draw_gap θ i := by  have hn2 : 2 ≤ n := by omega  have h_id := redistribution_one_draw_gap_bounds_sum_diff_identity hn2 i (fun j => F (t + θ j))  have h_pos : 0 ≤ 1 / ((n : ℝ) * ((n : ℝ) - 1)) := by    apply one_div_nonneg.mpr    have : (3 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn    nlinarith  have h_sum_le : |∑ j ∈ univ.erase i, (F (t + θ i) - F (t + θ j))| ≤      ∑ j ∈ univ.erase i, ((L : ℝ) * (θ i + θ j)) := by    refine le_trans (abs_sum_le_sum_abs _ _) ?_    apply sum_le_sum    intro j hj    have h_lip : |F (t + θ i) - F (t + θ j)| ≤ (L : ℝ) * |(t + θ i) - (t + θ j)| := by      rw [← Real.dist_eq, ← Real.dist_eq]      exact hF.dist_le_mul (t + θ i) (t + θ j)    have h_simp : (t + θ i) - (t + θ j) = θ i - θ j := by ring    rw [h_simp] at h_lip    have hθi : 0 ≤ θ i := (hθ i).1    have hθj : 0 ≤ θ j := (hθ j).1    have h_abs_le : |θ i - θ j| ≤ θ i + θ j := redistribution_one_draw_gap_bounds_abs_sub_le_add_of_nonneg hθi hθj    exact le_trans h_lip (mul_le_mul_of_nonneg_left h_abs_le (NNReal.coe_nonneg L))  have h_mul_le : 1 / ((n : ℝ) * ((n : ℝ) - 1)) * |∑ j ∈ univ.erase i, (F (t + θ i) - F (t + θ j))| ≤      1 / ((n : ℝ) * ((n : ℝ) - 1)) * ∑ j ∈ univ.erase i, ((L : ℝ) * (θ i + θ j)) :=    mul_le_mul_of_nonneg_left h_sum_le h_pos  unfold redistribution_fill_in redistribution_fill_in_without redistribution_one_draw_gap  rw [h_id, abs_mul, abs_of_nonneg h_pos]  refine le_trans h_mul_le ?_  apply le_of_eq  have hi : i ∈ (univ : Finset (Fin n)) := mem_univ i  have h1n : 1 ≤ n := by omega  have h_card : ((univ.erase i : Finset (Fin n)).card : ℝ) = (n : ℝ) - 1 := by    rw [card_erase_of_mem hi, card_fin, Nat.cast_sub h1n, Nat.cast_one]  rw [← mul_sum, sum_add_distrib, sum_const, nsmul_eq_mul, h_card]  have hn0 : (n : ℝ) ≠ 0 := by positivity  have hn1 : (n : ℝ) - 1 ≠ 0 := by    have : (3 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn    linarith  field_simplemma redistribution_one_draw_gap_bounds_lipschitz_comp_sub {L : NNReal} {F : ℝ → ℝ} (hF : LipschitzWith L F) (c : ℝ) :    LipschitzWith L (fun s => F (c - s)) := by  apply LipschitzWith.of_dist_le_mul  intro x y  have h1 : dist (c - x) (c - y) = dist x y := by    rw [Real.dist_eq, Real.dist_eq]    have : (c - x) - (c - y) = -(x - y) := by ring    rw [this, abs_neg]  rw [← h1]  exact hF.dist_le_mul (c - x) (c - y)lemma redistribution_one_draw_gap_bounds_trade_eq_avg_fill_in {n : ℕ} (θ : Fin n → ℝ) (F : ℝ → ℝ) (t : ℝ) :    redistribution_trade θ F t =    (1 / (n : ℝ)) * ∑ j, redistribution_fill_in θ F (t - θ j) := by  unfold redistribution_trade redistribution_fill_in  rw [mul_sum, mul_sum]  apply sum_congr rfl  intro j _  ringlemma redistribution_one_draw_gap_bounds_trade_without_eq {n : ℕ} (θ : Fin n → ℝ) (i : Fin n) (F : ℝ → ℝ) (t : ℝ) :    redistribution_trade_without θ i F t =    (1 / ((n : ℝ) - 1)) * ∑ k ∈ univ.erase i,      redistribution_fill_in_without θ i (fun s => F (t + θ k - s)) 0 := by  unfold redistribution_trade_without redistribution_fill_in_without  have h_comm : (∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, F (t - θ j + θ k)) =      ∑ k ∈ univ.erase i, ∑ j ∈ univ.erase i, F (t - θ j + θ k) := sum_comm  rw [h_comm]  have h_sq : (1 : ℝ) / ((n : ℝ) - 1) ^ 2 = (1 / ((n : ℝ) - 1)) * (1 / ((n : ℝ) - 1)) := by    simp only [one_div, sq, mul_inv]  rw [h_sq, mul_assoc, mul_sum]  congr 1  apply sum_congr rfl  intro k _  have h_fn : (∑ j ∈ univ.erase i, F (t - θ j + θ k)) =      ∑ j ∈ univ.erase i, (fun s => F (t + θ k - s)) (0 + θ j) := by    apply sum_congr rfl    intro j _    congr 1    ring  rw [h_fn]lemma redistribution_one_draw_gap_bounds_mid_eq_sum_fill_in {n : ℕ} (θ : Fin n → ℝ) (i : Fin n) (F : ℝ → ℝ) (t : ℝ) :    (1 / (n : ℝ)) * ∑ j, redistribution_fill_in_without θ i F (t - θ j) =    (1 / ((n : ℝ) - 1)) * ∑ k ∈ univ.erase i,      redistribution_fill_in θ (fun s => F (t + θ k - s)) 0 := by  unfold redistribution_fill_in_without redistribution_fill_in  simp only [mul_sum, sum_comm (s := univ)]  apply sum_congr rfl  intro k _  apply sum_congr rfl  intro j _  have : t + θ k - (0 + θ j) = t - θ j + θ k := by ring  rw [this]  ringlemma redistribution_one_draw_gap_bounds_sum_diff_bound_univ {n : ℕ} (hn : 0 < n) (f g : Fin n → ℝ) (C : ℝ)    (h : ∀ j, |f j - g j| ≤ C) :    |(1 / (n : ℝ)) * ∑ j, f j - (1 / (n : ℝ)) * ∑ j, g j| ≤ C := by  rw [← mul_sub, ← sum_sub_distrib]  have hn_pos : 0 ≤ 1 / (n : ℝ) := by positivity  rw [abs_mul, abs_of_nonneg hn_pos]  have : |∑ j, (f j - g j)| ≤ ∑ j, |f j - g j| := abs_sum_le_sum_abs _ _  have h_sum_le : ∑ j, |f j - g j| ≤ ∑ j : Fin n, C := sum_le_sum (fun j _ => h j)  have h_const : ∑ j : Fin n, C = (n : ℝ) * C := by    simp [sum_const, card_univ]  have h_step : |∑ j, (f j - g j)| ≤ (n : ℝ) * C := this.trans (h_sum_le.trans_eq h_const)  have h_mul := mul_le_mul_of_nonneg_left h_step hn_pos  have hn0 : (n : ℝ) ≠ 0 := by positivity  have h_cancel : 1 / (n : ℝ) * ((n : ℝ) * C) = C := by field_simp  exact h_mul.trans_eq h_cancellemma redistribution_one_draw_gap_bounds_sum_diff_bound_erase {n : ℕ} (hn : 2 ≤ n) (i : Fin n) (f g : Fin n → ℝ) (C : ℝ)    (h : ∀ j ∈ univ.erase i, |f j - g j| ≤ C) :    |(1 / ((n : ℝ) - 1)) * ∑ j ∈ univ.erase i, f j -     (1 / ((n : ℝ) - 1)) * ∑ j ∈ univ.erase i, g j| ≤ C := by  rw [← mul_sub, ← sum_sub_distrib]  have hn_pos : 0 ≤ 1 / ((n : ℝ) - 1) := by    apply one_div_nonneg.mpr    have : (2 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn    linarith  rw [abs_mul, abs_of_nonneg hn_pos]  have : |∑ j ∈ univ.erase i, (f j - g j)| ≤ ∑ j ∈ univ.erase i, |f j - g j| := abs_sum_le_sum_abs _ _  have h_sum_le : ∑ j ∈ univ.erase i, |f j - g j| ≤ ∑ j ∈ univ.erase i, C := sum_le_sum h  have hi : i ∈ (univ : Finset (Fin n)) := mem_univ i  have h1n : 1 ≤ n := by omega  have h_card : ((univ.erase i : Finset (Fin n)).card : ℝ) = (n : ℝ) - 1 := by    rw [card_erase_of_mem hi, card_fin, Nat.cast_sub h1n, Nat.cast_one]  have h_const : ∑ j ∈ univ.erase i, C = ((n : ℝ) - 1) * C := by    rw [sum_const, nsmul_eq_mul, h_card]  have h_step : |∑ j ∈ univ.erase i, (f j - g j)| ≤ ((n : ℝ) - 1) * C := this.trans (h_sum_le.trans_eq h_const)  have h_mul := mul_le_mul_of_nonneg_left h_step hn_pos  have hn1 : (n : ℝ) - 1 ≠ 0 := by    have : (2 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn    linarith  have h_cancel : 1 / ((n : ℝ) - 1) * (((n : ℝ) - 1) * C) = C := by field_simp  exact h_mul.trans_eq h_canceltheorem redistribution_one_draw_gap_bounds {n : ℕ} (hn : 3 ≤ n) (θ : Fin n → ℝ)    (hθ : ∀ j, θ j ∈ Set.Icc (0 : ℝ) 1) (i : Fin n) (F : ℝ → ℝ) (L : NNReal)    (hF : LipschitzWith L F) (t : ℝ) :    |redistribution_fill_in θ F t - redistribution_fill_in_without θ i F t| ≤        L * redistribution_one_draw_gap θ i ∧      |redistribution_trade θ F t - redistribution_trade_without θ i F t| ≤        2 * L * redistribution_one_draw_gap θ i := by  constructor  · exact redistribution_one_draw_gap_bounds_fill_in_sub_without_bound hn θ hθ i F L hF t  · set M := (1 / (n : ℝ)) * ∑ j, redistribution_fill_in_without θ i F (t - θ j)    have hn_pos : 0 < n := by omega    have hn2 : 2 ≤ n := by omega    have h1 : |redistribution_trade θ F t - M| ≤ (L : ℝ) * redistribution_one_draw_gap θ i := by      rw [redistribution_one_draw_gap_bounds_trade_eq_avg_fill_in]      apply redistribution_one_draw_gap_bounds_sum_diff_bound_univ hn_pos      intro j      exact redistribution_one_draw_gap_bounds_fill_in_sub_without_bound hn θ hθ i F L hF (t - θ j)    have h2 : |M - redistribution_trade_without θ i F t| ≤ (L : ℝ) * redistribution_one_draw_gap θ i := by      dsimp [M]      rw [redistribution_one_draw_gap_bounds_mid_eq_sum_fill_in, redistribution_one_draw_gap_bounds_trade_without_eq]      apply redistribution_one_draw_gap_bounds_sum_diff_bound_erase hn2      intro k _      have hG_lip : LipschitzWith L (fun s => F (t + θ k - s)) :=        redistribution_one_draw_gap_bounds_lipschitz_comp_sub hF (t + θ k)      exact redistribution_one_draw_gap_bounds_fill_in_sub_without_bound hn θ hθ i _ L hG_lip 0    have h_tri : |redistribution_trade θ F t - redistribution_trade_without θ i F t| ≤        |redistribution_trade θ F t - M| + |M - redistribution_trade_without θ i F t| := by      have : redistribution_trade θ F t - redistribution_trade_without θ i F t =          (redistribution_trade θ F t - M) + (M - redistribution_trade_without θ i F t) := by ring      rw [this]      exact abs_add_le _ _    refine h_tri.trans ?_    have : (L : ℝ) * redistribution_one_draw_gap θ i + (L : ℝ) * redistribution_one_draw_gap θ i =        2 * (L : ℝ) * redistribution_one_draw_gap θ i := by ring    rw [← this]    exact add_le_add h1 h2
See it in the graphDiscuss this resultChallenge it