AFTD Auto-Formalizing Theoretical Domains

redistribution_iterated_trade_bounds

theoremverifiedformalization

Let 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)| ≤ 2 k d_i for every t.

Statement

theorem redistribution_iterated_trade_bounds {n : ℕ} (hn : 3 ≤ n) (θ : Fin n → ℝ)
    (hθ : ∀ j, θ j ∈ Set.Icc (0 : ℝ) 1) (i : Fin n) (k : ℕ) :
    LipschitzWith 1 ((redistribution_trade θ)^[k] (fun t => max (1 - t) 0)) ∧
      LipschitzWith 1 ((redistribution_trade_without θ i)^[k] (fun t => max (1 - t) 0)) ∧
      ∀ t, |(redistribution_trade θ)^[k] (fun t => max (1 - t) 0) t -
          (redistribution_trade_without θ i)^[k] (fun t => max (1 - t) 0) t| ≤
        2 * k * redistribution_one_draw_gap θ i
Formalizes
arXiv:2610.10995 (Asymptotically optimal public project redistribution without bounded precision), Lemma 4.5 (with G(t) = max(1 − t, 0), the paper's target function).
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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.
  • redistribution_one_draw_gap_boundsLet 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) −…
  • 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).

The proof, explained

The result is established by induction on the number of trading rounds k. The base case k = 0 holds because the initial surplus function G(t) = max(1 - t, 0) is 1-Lipschitz, and the difference between the full and leave-one-out operators is zero. For the inductive step, applying the redistribution operators preserves the 1-Lipschitz property because both operators are convex combinations of shifts of 1-Lipschitz functions. The distance |T^{k+1} G(t) - T_{-i}^{k+1} G(t)| is decomposed via the triangle inequality into |T(T^k G)(t) - T(T_{-i}^k G)(t)| and |T(T_{-i}^k G)(t) - T_{-i}(T_{-i}^k G)(t)|. The first term is bounded by the induction hypothesis 2 k d_i via the L^∞ non-expansiveness of T, while the second term is bounded by 2 d_i using the single-draw gap bound for 1-Lipschitz inputs, summing to 2(k + 1) d_i.

  1. The baseline function G(t) = max(1 - t, 0) is 1-Lipschitz.

    To show that G is 1-Lipschitz, we verify that |G(x) - G(y)| ≤ |x - y| for all x, y ∈ ℝ. By the standard inequality for the maximum function, |max(1 - x, 0) - max(1 - y, 0)| ≤ |(1 - x) - (1 - y)|. Simplifying (1 - x) - (1 - y) = -(x - y) and using |-a| = |a| yields |x - y|.

    lines 5–13

    uses lipschitzWith_iff_dist_le_mul, NNReal.coe_one, one_mul, Real.dist_eq, abs_max_sub_max_le_abs, abs_neg

      rw [lipschitzWith_iff_dist_le_mul]
      intro x y
      rw [NNReal.coe_one]
      simp only [one_mul]
      rw [Real.dist_eq, Real.dist_eq]
      have h := abs_max_sub_max_le_abs (1 - x) (1 - y) 0
      have h2 : |(1 - x) - (1 - y)| = |x - y| := by
        rw [show (1 - x) - (1 - y) = -(x - y) by ring, abs_neg]
      rwa [h2] at h
  2. The difference (T F)(x) - (T F)(y) can be expressed as an average of differences of F.

    Unfolding the definition of the redistribution trade operator T, the difference (T F)(x) - (T F)(y) is rewritten by factoring out the normalization factor 1/n^2 and distributing the subtraction over the double sum over all agent pairs (j, k), giving (1/n^2) ∑_j ∑_k (F(x - θ_j + θ_k) - F(y - θ_j + θ_k)).

    lines 19–34

    uses lipschitzWith_iff_dist_le_mul, NNReal.coe_one, one_mul, Real.dist_eq, mul_sub, sum_sub_distrib, sum_congr, abs_mul

      rw [lipschitzWith_iff_dist_le_mul] at hF ⊢
      intro x y
      rw [NNReal.coe_one] at hF ⊢
      simp only [one_mul] at hF ⊢
      simp_rw [Real.dist_eq] at hF ⊢
      dsimp [redistribution_trade]
      have h_sub : (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, F (x - θ j + θ k) -
          (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, F (y - θ j + θ k) =
          (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, (F (x - θ j + θ k) - F (y - θ j + θ k)) := by
        rw [← mul_sub]
        congr 1
        rw [← sum_sub_distrib]
        apply sum_congr rfl
        intro j _
        rw [← sum_sub_distrib]
      rw [h_sub, abs_mul]
  3. Each term in the double sum is bounded in absolute value by |x - y|.

    Since n > 0, the scalar factor 1/n^2 is positive and factors out of the absolute value. By the triangle inequality for sums, the absolute value of the double sum is bounded by the sum of absolute values. Because F is 1-Lipschitz, each summand satisfies |F(x - θ_j + θ_k) - F(y - θ_j + θ_k)| ≤ |(x - θ_j + θ_k) - (y - θ_j + θ_k)| = |x - y|.

    lines 35–48

    uses Nat.cast_pos.mpr, sq_pos_of_pos, abs_of_pos, one_div_pos.mpr, abs_sum_le_sum_abs, sum_le_sum

      have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn
      have hn2_pos : 0 < (n : ℝ) ^ 2 := sq_pos_of_pos hn_pos
      rw [abs_of_pos (one_div_pos.mpr hn2_pos)]
      have h_abs_sum : |∑ j, ∑ k, (F (x - θ j + θ k) - F (y - θ j + θ k))| ≤
          ∑ j, ∑ k, |F (x - θ j + θ k) - F (y - θ j + θ k)| := by
        refine (abs_sum_le_sum_abs _ _).trans ?_
        apply sum_le_sum
        intro j _
        exact abs_sum_le_sum_abs _ _
      have h_bound : ∀ j k, |F (x - θ j + θ k) - F (y - θ j + θ k)| ≤ |x - y| := by
        intro j k
        have := hF (x - θ j + θ k) (y - θ j + θ k)
        have h_diff : (x - θ j + θ k) - (y - θ j + θ k) = x - y := by ring
        rwa [h_diff] at this
  4. The redistribution trade operator T F is 1-Lipschitz.

    Summing the upper bound |x - y| over all n^2 pairs (j, k) gives n^2 |x - y|. Multiplying by the prefactor 1/n^2 and cancelling n^2 yields |(T F)(x) - (T F)(y)| ≤ |x - y|, showing that T F is 1-Lipschitz.

    lines 49–66

    uses sum_le_sum, sum_const, card_univ, Fintype.card_fin, sq, mul_le_mul_of_nonneg_left, mul_assoc, one_div_mul_cancel, ne_of_gt, one_mul

      have h_sum_le : ∑ j : Fin n, ∑ k : Fin n, |F (x - θ j + θ k) - F (y - θ j + θ k)| ≤
          ∑ j : Fin n, ∑ k : Fin n, |x - y| := by
        apply sum_le_sum
        intro j _
        apply sum_le_sum
        intro k _
        exact h_bound j k
      have h_card : ∑ j : Fin n, ∑ k : Fin n, |x - y| = (n : ℝ) ^ 2 * |x - y| := by
        simp [sum_const, card_univ, Fintype.card_fin, sq]
        ring
      rw [h_card] at h_sum_le
      have h_prod : (1 / (n : ℝ) ^ 2) * |∑ j, ∑ k, (F (x - θ j + θ k) - F (y - θ j + θ k))| ≤
          (1 / (n : ℝ) ^ 2) * ((n : ℝ) ^ 2 * |x - y|) :=
        mul_le_mul_of_nonneg_left (h_abs_sum.trans h_sum_le) (by positivity)
      refine h_prod.trans ?_
      have : (1 / (n : ℝ) ^ 2) * ((n : ℝ) ^ 2 * |x - y|) = |x - y| := by
        rw [← mul_assoc, one_div_mul_cancel (ne_of_gt hn2_pos), one_mul]
      rw [this]
  5. The difference (T_{-i} F)(x) - (T_{-i} F)(y) can be expressed as an average of differences over pairs avoiding agent i.

    Unfolding the definition of the leave-one-out trade operator T_{-i}, the difference (T_{-i} F)(x) - (T_{-i} F)(y) is rewritten by factoring out 1/(n-1)^2 and distributing the subtraction over the double sum over all pairs (j, k) in the universe of agents excluding i.

    lines 72–87

    uses lipschitzWith_iff_dist_le_mul, NNReal.coe_one, one_mul, Real.dist_eq, mul_sub, sum_sub_distrib, sum_congr, abs_mul

      rw [lipschitzWith_iff_dist_le_mul] at hF ⊢
      intro x y
      rw [NNReal.coe_one] at hF ⊢
      simp only [one_mul] at hF ⊢
      simp_rw [Real.dist_eq] at hF ⊢
      dsimp [redistribution_trade_without]
      have h_sub : (1 / ((n : ℝ) - 1) ^ 2) * ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, F (x - θ j + θ k) -
          (1 / ((n : ℝ) - 1) ^ 2) * ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, F (y - θ j + θ k) =
          (1 / ((n : ℝ) - 1) ^ 2) * ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, (F (x - θ j + θ k) - F (y - θ j + θ k)) := by
        rw [← mul_sub]
        congr 1
        rw [← sum_sub_distrib]
        apply sum_congr rfl
        intro j _
        rw [← sum_sub_distrib]
      rw [h_sub, abs_mul]
  6. Each term in the leave-one-out double sum is bounded by |x - y|.

    From n ≥ 2, we have n - 1 > 0, so 1/(n-1)^2 is strictly positive. Applying the triangle inequality to the double sum and the 1-Lipschitz property of F to each shifted difference (x - θ_j + θ_k) - (y - θ_j + θ_k) = x - y, every summand is bounded by |x - y|.

    lines 88–103

    uses sq_pos_of_pos, abs_of_pos, one_div_pos.mpr, abs_sum_le_sum_abs, sum_le_sum

      have hn_pos : 0 < (n : ℝ) - 1 := by
        have : (2 : ℝ) ≤ n := by exact_mod_cast hn
        linarith
      have hn2_pos : 0 < ((n : ℝ) - 1) ^ 2 := sq_pos_of_pos hn_pos
      rw [abs_of_pos (one_div_pos.mpr hn2_pos)]
      have h_abs_sum : |∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, (F (x - θ j + θ k) - F (y - θ j + θ k))| ≤
          ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, |F (x - θ j + θ k) - F (y - θ j + θ k)| := by
        refine (abs_sum_le_sum_abs _ _).trans ?_
        apply sum_le_sum
        intro j _
        exact abs_sum_le_sum_abs _ _
      have h_bound : ∀ j k, |F (x - θ j + θ k) - F (y - θ j + θ k)| ≤ |x - y| := by
        intro j k
        have := hF (x - θ j + θ k) (y - θ j + θ k)
        have h_diff : (x - θ j + θ k) - (y - θ j + θ k) = x - y := by ring
        rwa [h_diff] at this
  7. The leave-one-out redistribution trade operator T_{-i} F is 1-Lipschitz.

    The set of agents excluding i has cardinality n - 1, so the double sum has (n - 1)^2 terms, summing to (n - 1)^2 |x - y|. Multiplying by 1/(n-1)^2 cancels the factor, proving that |(T_{-i} F)(x) - (T_{-i} F)(y)| ≤ |x - y| and hence T_{-i} F is 1-Lipschitz.

    lines 104–126

    uses sum_le_sum, card_erase_of_mem, mem_univ, card_univ, Fintype.card_fin, Nat.cast_sub, Nat.cast_one, sum_const, nsmul_eq_mul, mul_le_mul_of_nonneg_left, mul_assoc, one_div_mul_cancel, ne_of_gt, one_mul

      have h_sum_le : ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, |F (x - θ j + θ k) - F (y - θ j + θ k)| ≤
          ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, |x - y| := by
        apply sum_le_sum
        intro j _
        apply sum_le_sum
        intro k _
        exact h_bound j k
      have h_card_erase : ((univ.erase i : Finset (Fin n)).card : ℝ) = (n : ℝ) - 1 := by
        have : (univ.erase i : Finset (Fin n)).card = n - 1 := by
          rw [card_erase_of_mem (mem_univ i), card_univ, Fintype.card_fin]
        rw [this, Nat.cast_sub (R := ℝ) (by omega : 1 ≤ n), Nat.cast_one]
      have h_card : ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, |x - y| = ((n : ℝ) - 1) ^ 2 * |x - y| := by
        simp only [sum_const, nsmul_eq_mul]
        rw [h_card_erase]
        ring
      rw [h_card] at h_sum_le
      have h_prod : (1 / ((n : ℝ) - 1) ^ 2) * |∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, (F (x - θ j + θ k) - F (y - θ j + θ k))| ≤
          (1 / ((n : ℝ) - 1) ^ 2) * (((n : ℝ) - 1) ^ 2 * |x - y|) :=
        mul_le_mul_of_nonneg_left (h_abs_sum.trans h_sum_le) (by positivity)
      refine h_prod.trans ?_
      have : (1 / ((n : ℝ) - 1) ^ 2) * (((n : ℝ) - 1) ^ 2 * |x - y|) = |x - y| := by
        rw [← mul_assoc, one_div_mul_cancel (ne_of_gt hn2_pos), one_mul]
      rw [this]
  8. The difference (T F)(t) - (T H)(t) can be written as an average of differences between F and H.

    Expanding the trade operator T for functions F and H, we factor out 1/n^2 and combine the double sums, expressing (T F)(t) - (T H)(t) as (1/n^2) ∑_{j,k} (F(t - θ_j + θ_k) - H(t - θ_j + θ_k)).

    lines 132–142

    uses mul_sub, sum_sub_distrib, sum_congr, abs_mul

      dsimp [redistribution_trade]
      have h_sub : (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, F (t - θ j + θ k) -
          (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, H (t - θ j + θ k) =
          (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, (F (t - θ j + θ k) - H (t - θ j + θ k)) := by
        rw [← mul_sub]
        congr 1
        rw [← sum_sub_distrib]
        apply sum_congr rfl
        intro j _
        rw [← sum_sub_distrib]
      rw [h_sub, abs_mul]
  9. The operator T is non-expansive in L^∞: if |F(s) - H(s)| ≤ C for all s, then |(T F)(t) - (T H)(t)| ≤ C.

    By the triangle inequality, the absolute value of the sum is bounded by the sum of absolute values. Since |F(s) - H(s)| ≤ C for all inputs, each of the n^2 terms is bounded by C. Summing them gives n^2 C, and multiplying by 1/n^2 cancels n^2, leaving the bound C.

    lines 143–169

    uses Nat.cast_pos.mpr, sq_pos_of_pos, abs_of_pos, one_div_pos.mpr, abs_sum_le_sum_abs, sum_le_sum, sum_const, card_univ, Fintype.card_fin, sq, mul_le_mul_of_nonneg_left, mul_assoc, one_div_mul_cancel, ne_of_gt, one_mul

      have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn
      have hn2_pos : 0 < (n : ℝ) ^ 2 := sq_pos_of_pos hn_pos
      rw [abs_of_pos (one_div_pos.mpr hn2_pos)]
      have h_abs_sum : |∑ j, ∑ k, (F (t - θ j + θ k) - H (t - θ j + θ k))| ≤
          ∑ j, ∑ k, |F (t - θ j + θ k) - H (t - θ j + θ k)| := by
        refine (abs_sum_le_sum_abs _ _).trans ?_
        apply sum_le_sum
        intro j _
        exact abs_sum_le_sum_abs _ _
      have h_sum_le : ∑ j : Fin n, ∑ k : Fin n, |F (t - θ j + θ k) - H (t - θ j + θ k)| ≤
          ∑ j : Fin n, ∑ k : Fin n, C := by
        apply sum_le_sum
        intro j _
        apply sum_le_sum
        intro k _
        exact hFH (t - θ j + θ k)
      have h_card : ∑ j : Fin n, ∑ k : Fin n, C = (n : ℝ) ^ 2 * C := by
        simp [sum_const, card_univ, Fintype.card_fin, sq]
        ring
      rw [h_card] at h_sum_le
      have h_prod : (1 / (n : ℝ) ^ 2) * |∑ j, ∑ k, (F (t - θ j + θ k) - H (t - θ j + θ k))| ≤
          (1 / (n : ℝ) ^ 2) * ((n : ℝ) ^ 2 * C) :=
        mul_le_mul_of_nonneg_left (h_abs_sum.trans h_sum_le) (by positivity)
      refine h_prod.trans ?_
      have : (1 / (n : ℝ) ^ 2) * ((n : ℝ) ^ 2 * C) = C := by
        rw [← mul_assoc, one_div_mul_cancel (ne_of_gt hn2_pos), one_mul]
      rw [this]
  10. The base case k = 0 holds.

    For k = 0, both T^0 G and T_{-i}^0 G are the identity applied to G, which is G itself. By the first lemma, G is 1-Lipschitz. The pointwise difference |G(t) - G(t)| is 0, which is trivially bounded by 2 * 0 * d_i = 0.

    lines 178–186

    uses redistribution_iterated_trade_bounds_lip_G, Function.iterate_zero, id_eq

      have hn_pos : 0 < n := by omega
      have hn_two : 2 ≤ n := by omega
      set G : ℝ → ℝ := fun t => max (1 - t) 0
      have hG_lip : LipschitzWith 1 G := redistribution_iterated_trade_bounds_lip_G
      induction' k with k ih
      · simp only [Function.iterate_zero, id_eq]
        refine ⟨hG_lip, hG_lip, ?_⟩
        intro t
        simp
  11. In the inductive step, the iterates T^{k+1} G and T_{-i}^{k+1} G are 1-Lipschitz.

    Writing T^{k+1} G = T(T^k G) and T_{-i}^{k+1} G = T_{-i}(T_{-i}^k G), the induction hypothesis guarantees that T^k G and T_{-i}^k G are 1-Lipschitz. Since n ≥ 3, applying the Lipschitz preservation lemmas for T and T_{-i} shows that T^{k+1} G and T_{-i}^{k+1} G are also 1-Lipschitz.

    lines 187–195

    uses Function.iterate_succ', redistribution_iterated_trade_bounds_trade_lipschitz, redistribution_iterated_trade_bounds_trade_without_lipschitz

      · rcases ih with ⟨ih_T, ih_T_without, ih_dist⟩
        rw [Function.iterate_succ' (redistribution_trade θ) k]
        rw [Function.iterate_succ' (redistribution_trade_without θ i) k]
        have hT_next : LipschitzWith 1 (redistribution_trade θ ((redistribution_trade θ)^[k] G)) :=
          redistribution_iterated_trade_bounds_trade_lipschitz hn_pos θ ih_T
        have hT_without_next : LipschitzWith 1 (redistribution_trade_without θ i ((redistribution_trade_without θ i)^[k] G)) :=
          redistribution_iterated_trade_bounds_trade_without_lipschitz hn_two θ i ih_T_without
        refine ⟨hT_next, hT_without_next, ?_⟩
        intro t
  12. The pointwise difference |T^{k+1} G(t) - T_{-i}^{k+1} G(t)| is bounded by the sum of two differences via the triangle inequality.

    We insert the intermediate term T(T_{-i}^k G)(t) and apply the triangle inequality |a + b| ≤ |a| + |b|, splitting |T^{k+1} G(t) - T_{-i}^{k+1} G(t)| into |T(T^k G)(t) - T(T_{-i}^k G)(t)| + |T(T_{-i}^k G)(t) - T_{-i}(T_{-i}^k G)(t)|.

    lines 196–210

    uses abs_add_le

        have h_tri : |redistribution_trade θ ((redistribution_trade θ)^[k] G) t -
            redistribution_trade_without θ i ((redistribution_trade_without θ i)^[k] G) t| ≤
            |redistribution_trade θ ((redistribution_trade θ)^[k] G) t -
              redistribution_trade θ ((redistribution_trade_without θ i)^[k] G) t| +
            |redistribution_trade θ ((redistribution_trade_without θ i)^[k] G) t -
              redistribution_trade_without θ i ((redistribution_trade_without θ i)^[k] G) t| := by
          have : redistribution_trade θ ((redistribution_trade θ)^[k] G) t -
              redistribution_trade_without θ i ((redistribution_trade_without θ i)^[k] G) t =
              (redistribution_trade θ ((redistribution_trade θ)^[k] G) t -
                redistribution_trade θ ((redistribution_trade_without θ i)^[k] G) t) +
              (redistribution_trade θ ((redistribution_trade_without θ i)^[k] G) t -
                redistribution_trade_without θ i ((redistribution_trade_without θ i)^[k] G) t) := by ring
          rw [this]
          exact abs_add_le _ _
        refine h_tri.trans ?_
  13. The pointwise difference is bounded by 2(k + 1) d_i, completing the induction.

    The first term |T(T^k G)(t) - T(T_{-i}^k G)(t)| is bounded by 2 k d_i using the L^∞ non-expansiveness of T and the induction hypothesis |T^k G(s) - T_{-i}^k G(s)| ≤ 2 k d_i. The second term |T(H)(t) - T_{-i}(H)(t)| for H = T_{-i}^k G is bounded by 2 * 1 * d_i = 2 d_i by the single-draw gap bound for 1-Lipschitz functions. Summing these bounds gives 2 k d_i + 2 d_i = 2 (k + 1) d_i.

    lines 211–217

    uses redistribution_iterated_trade_bounds_trade_diff_le, redistribution_one_draw_gap_bounds, NNReal.coe_one, mul_one, add_le_add

        have h_term1 := redistribution_iterated_trade_bounds_trade_diff_le hn_pos θ _ _ (2 * (k : ℝ) * redistribution_one_draw_gap θ i) ih_dist t
        have h_gap := (redistribution_one_draw_gap_bounds hn θ hθ i ((redistribution_trade_without θ i)^[k] G) 1 ih_T_without t).2
        simp only [NNReal.coe_one, mul_one] at h_gap
        have h_sum := add_le_add h_term1 h_gap
        refine h_sum.trans_eq ?_
        push_cast
        ring
lipschitzWith_iff_dist_le_mul
A function is K-Lipschitz if and only if the distance between images is bounded by K times the distance between inputs.
NNReal.coe_one
The non-negative real number 1 coerces to the real number 1.
one_mul
Multiplying by 1 on the left leaves an element unchanged: 1 * a = a.
Real.dist_eq
The metric distance between two real numbers x and y is the absolute value of their difference, |x - y|.
abs_max_sub_max_le_abs
The difference between two maxima with a common element satisfies |max(a, c) - max(b, c)| ≤ |a - b|.
abs_neg
The absolute value of the negation of a number is equal to its absolute value: |-a| = |a|.
mul_sub
Multiplication distributes from the left over subtraction: a(b - c) = ab - ac.
sum_sub_distrib
A sum of differences equals the difference of the sums: ∑ (f(x) - g(x)) = ∑ f(x) - ∑ g(x).
sum_congr
Two sums are equal if their index sets are identical and their summands are equal at every index.
abs_mul
The absolute value of a product is the product of the absolute values: |ab| = |a| |b|.
Nat.cast_pos.mpr
A natural number cast to the real numbers is strictly positive if the original natural number is strictly positive.
sq_pos_of_pos
The square of a strictly positive number is strictly positive.
abs_of_pos
The absolute value of a strictly positive number equals the number itself.
one_div_pos.mpr
The reciprocal 1/a is strictly positive if a is strictly positive.
abs_sum_le_sum_abs
The triangle inequality for finite sums: the absolute value of a sum is at most the sum of the absolute values.
sum_le_sum
A sum is bounded by another sum if each summand is pointwise bounded by the corresponding summand.
sum_const
The sum of a constant b over a finite set s equals the cardinality of s multiplied by b.
card_univ
The cardinality of the universal finset univ of a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of the standard finite set Fin n of n elements is n.
sq
The square of an element is the element multiplied by itself: a^2 = a * a.
mul_le_mul_of_nonneg_left
Multiplying an inequality b ≤ c by a non-negative number a on the left preserves the inequality: ab ≤ ac.
mul_assoc
Multiplication is associative: (ab)c = a(bc).
one_div_mul_cancel
Multiplying the reciprocal 1/a by a gives 1, provided a ≠ 0.
ne_of_gt
If b < a, then a ≠ b.
card_erase_of_mem
Removing an element from a finite set decreases its cardinality by 1.
mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Nat.cast_sub
For natural numbers m ≤ n, the cast of n - m to real numbers is the difference of their casts, n - m.
Nat.cast_one
The natural number 1 cast to real numbers is the real number 1.
nsmul_eq_mul
Scalar multiplication by a natural number n in a ring equals multiplication by n cast into the ring.
redistribution_iterated_trade_bounds_lip_G
The baseline function G(t) = max(1 - t, 0) is 1-Lipschitz.
Function.iterate_zero
The zeroth iterate of a function is the identity function.
id_eq
The identity function maps every element to itself: id(a) = a.
Function.iterate_succ'
The (n+1)-th iterate of a function f satisfies f^[n+1] = f ∘ f^[n].
redistribution_iterated_trade_bounds_trade_lipschitz
If n > 0 and F is 1-Lipschitz, then the redistribution trade operator applied to F is 1-Lipschitz.
redistribution_iterated_trade_bounds_trade_without_lipschitz
If n ≥ 2 and F is 1-Lipschitz, then the leave-one-out redistribution trade operator applied to F is 1-Lipschitz.
abs_add_le
The triangle inequality for addition: |a + b| ≤ |a| + |b|.
redistribution_iterated_trade_bounds_trade_diff_le
If two functions differ pointwise by at most C, then applying the redistribution trade operator to both yields functions differing pointwise by at most C.
redistribution_one_draw_gap_bounds
For n ≥ 3, if F is L-Lipschitz, then the difference between the full and leave-one-out trade operators applied to F is bounded by 2 L d_i.
mul_one
Multiplying by 1 on the right leaves an element unchanged: a * 1 = a.
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_iterated_trade_bounds_lip_G :    LipschitzWith 1 (fun t : ℝ => max (1 - t) 0) := by  rw [lipschitzWith_iff_dist_le_mul]  intro x y  rw [NNReal.coe_one]  simp only [one_mul]  rw [Real.dist_eq, Real.dist_eq]  have h := abs_max_sub_max_le_abs (1 - x) (1 - y) 0  have h2 : |(1 - x) - (1 - y)| = |x - y| := by    rw [show (1 - x) - (1 - y) = -(x - y) by ring, abs_neg]  rwa [h2] at hlemma redistribution_iterated_trade_bounds_trade_lipschitz    {n : ℕ} (hn : 0 < n) (θ : Fin n → ℝ) {F : ℝ → ℝ}    (hF : LipschitzWith 1 F) :    LipschitzWith 1 (redistribution_trade θ F) := by  rw [lipschitzWith_iff_dist_le_mul] at hF ⊢  intro x y  rw [NNReal.coe_one] at hF ⊢  simp only [one_mul] at hF ⊢  simp_rw [Real.dist_eq] at hF ⊢  dsimp [redistribution_trade]  have h_sub : (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, F (x - θ j + θ k) -      (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, F (y - θ j + θ k) =      (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, (F (x - θ j + θ k) - F (y - θ j + θ k)) := by    rw [← mul_sub]    congr 1    rw [← sum_sub_distrib]    apply sum_congr rfl    intro j _    rw [← sum_sub_distrib]  rw [h_sub, abs_mul]  have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn  have hn2_pos : 0 < (n : ℝ) ^ 2 := sq_pos_of_pos hn_pos  rw [abs_of_pos (one_div_pos.mpr hn2_pos)]  have h_abs_sum : |∑ j, ∑ k, (F (x - θ j + θ k) - F (y - θ j + θ k))| ≤      ∑ j, ∑ k, |F (x - θ j + θ k) - F (y - θ j + θ k)| := by    refine (abs_sum_le_sum_abs _ _).trans ?_    apply sum_le_sum    intro j _    exact abs_sum_le_sum_abs _ _  have h_bound : ∀ j k, |F (x - θ j + θ k) - F (y - θ j + θ k)| ≤ |x - y| := by    intro j k    have := hF (x - θ j + θ k) (y - θ j + θ k)    have h_diff : (x - θ j + θ k) - (y - θ j + θ k) = x - y := by ring    rwa [h_diff] at this  have h_sum_le : ∑ j : Fin n, ∑ k : Fin n, |F (x - θ j + θ k) - F (y - θ j + θ k)| ≤      ∑ j : Fin n, ∑ k : Fin n, |x - y| := by    apply sum_le_sum    intro j _    apply sum_le_sum    intro k _    exact h_bound j k  have h_card : ∑ j : Fin n, ∑ k : Fin n, |x - y| = (n : ℝ) ^ 2 * |x - y| := by    simp [sum_const, card_univ, Fintype.card_fin, sq]    ring  rw [h_card] at h_sum_le  have h_prod : (1 / (n : ℝ) ^ 2) * |∑ j, ∑ k, (F (x - θ j + θ k) - F (y - θ j + θ k))| ≤      (1 / (n : ℝ) ^ 2) * ((n : ℝ) ^ 2 * |x - y|) :=    mul_le_mul_of_nonneg_left (h_abs_sum.trans h_sum_le) (by positivity)  refine h_prod.trans ?_  have : (1 / (n : ℝ) ^ 2) * ((n : ℝ) ^ 2 * |x - y|) = |x - y| := by    rw [← mul_assoc, one_div_mul_cancel (ne_of_gt hn2_pos), one_mul]  rw [this]lemma redistribution_iterated_trade_bounds_trade_without_lipschitz    {n : ℕ} (hn : 2 ≤ n) (θ : Fin n → ℝ) (i : Fin n) {F : ℝ → ℝ}    (hF : LipschitzWith 1 F) :    LipschitzWith 1 (redistribution_trade_without θ i F) := by  rw [lipschitzWith_iff_dist_le_mul] at hF ⊢  intro x y  rw [NNReal.coe_one] at hF ⊢  simp only [one_mul] at hF ⊢  simp_rw [Real.dist_eq] at hF ⊢  dsimp [redistribution_trade_without]  have h_sub : (1 / ((n : ℝ) - 1) ^ 2) * ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, F (x - θ j + θ k) -      (1 / ((n : ℝ) - 1) ^ 2) * ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, F (y - θ j + θ k) =      (1 / ((n : ℝ) - 1) ^ 2) * ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, (F (x - θ j + θ k) - F (y - θ j + θ k)) := by    rw [← mul_sub]    congr 1    rw [← sum_sub_distrib]    apply sum_congr rfl    intro j _    rw [← sum_sub_distrib]  rw [h_sub, abs_mul]  have hn_pos : 0 < (n : ℝ) - 1 := by    have : (2 : ℝ) ≤ n := by exact_mod_cast hn    linarith  have hn2_pos : 0 < ((n : ℝ) - 1) ^ 2 := sq_pos_of_pos hn_pos  rw [abs_of_pos (one_div_pos.mpr hn2_pos)]  have h_abs_sum : |∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, (F (x - θ j + θ k) - F (y - θ j + θ k))| ≤      ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, |F (x - θ j + θ k) - F (y - θ j + θ k)| := by    refine (abs_sum_le_sum_abs _ _).trans ?_    apply sum_le_sum    intro j _    exact abs_sum_le_sum_abs _ _  have h_bound : ∀ j k, |F (x - θ j + θ k) - F (y - θ j + θ k)| ≤ |x - y| := by    intro j k    have := hF (x - θ j + θ k) (y - θ j + θ k)    have h_diff : (x - θ j + θ k) - (y - θ j + θ k) = x - y := by ring    rwa [h_diff] at this  have h_sum_le : ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, |F (x - θ j + θ k) - F (y - θ j + θ k)| ≤      ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, |x - y| := by    apply sum_le_sum    intro j _    apply sum_le_sum    intro k _    exact h_bound j k  have h_card_erase : ((univ.erase i : Finset (Fin n)).card : ℝ) = (n : ℝ) - 1 := by    have : (univ.erase i : Finset (Fin n)).card = n - 1 := by      rw [card_erase_of_mem (mem_univ i), card_univ, Fintype.card_fin]    rw [this, Nat.cast_sub (R := ℝ) (by omega : 1 ≤ n), Nat.cast_one]  have h_card : ∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, |x - y| = ((n : ℝ) - 1) ^ 2 * |x - y| := by    simp only [sum_const, nsmul_eq_mul]    rw [h_card_erase]    ring  rw [h_card] at h_sum_le  have h_prod : (1 / ((n : ℝ) - 1) ^ 2) * |∑ j ∈ univ.erase i, ∑ k ∈ univ.erase i, (F (x - θ j + θ k) - F (y - θ j + θ k))| ≤      (1 / ((n : ℝ) - 1) ^ 2) * (((n : ℝ) - 1) ^ 2 * |x - y|) :=    mul_le_mul_of_nonneg_left (h_abs_sum.trans h_sum_le) (by positivity)  refine h_prod.trans ?_  have : (1 / ((n : ℝ) - 1) ^ 2) * (((n : ℝ) - 1) ^ 2 * |x - y|) = |x - y| := by    rw [← mul_assoc, one_div_mul_cancel (ne_of_gt hn2_pos), one_mul]  rw [this]lemma redistribution_iterated_trade_bounds_trade_diff_le    {n : ℕ} (hn : 0 < n) (θ : Fin n → ℝ) (F H : ℝ → ℝ) (C : ℝ)    (hFH : ∀ s, |F s - H s| ≤ C) (t : ℝ) :    |redistribution_trade θ F t - redistribution_trade θ H t| ≤ C := by  dsimp [redistribution_trade]  have h_sub : (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, F (t - θ j + θ k) -      (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, H (t - θ j + θ k) =      (1 / (n : ℝ) ^ 2) * ∑ j, ∑ k, (F (t - θ j + θ k) - H (t - θ j + θ k)) := by    rw [← mul_sub]    congr 1    rw [← sum_sub_distrib]    apply sum_congr rfl    intro j _    rw [← sum_sub_distrib]  rw [h_sub, abs_mul]  have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn  have hn2_pos : 0 < (n : ℝ) ^ 2 := sq_pos_of_pos hn_pos  rw [abs_of_pos (one_div_pos.mpr hn2_pos)]  have h_abs_sum : |∑ j, ∑ k, (F (t - θ j + θ k) - H (t - θ j + θ k))| ≤      ∑ j, ∑ k, |F (t - θ j + θ k) - H (t - θ j + θ k)| := by    refine (abs_sum_le_sum_abs _ _).trans ?_    apply sum_le_sum    intro j _    exact abs_sum_le_sum_abs _ _  have h_sum_le : ∑ j : Fin n, ∑ k : Fin n, |F (t - θ j + θ k) - H (t - θ j + θ k)| ≤      ∑ j : Fin n, ∑ k : Fin n, C := by    apply sum_le_sum    intro j _    apply sum_le_sum    intro k _    exact hFH (t - θ j + θ k)  have h_card : ∑ j : Fin n, ∑ k : Fin n, C = (n : ℝ) ^ 2 * C := by    simp [sum_const, card_univ, Fintype.card_fin, sq]    ring  rw [h_card] at h_sum_le  have h_prod : (1 / (n : ℝ) ^ 2) * |∑ j, ∑ k, (F (t - θ j + θ k) - H (t - θ j + θ k))| ≤      (1 / (n : ℝ) ^ 2) * ((n : ℝ) ^ 2 * C) :=    mul_le_mul_of_nonneg_left (h_abs_sum.trans h_sum_le) (by positivity)  refine h_prod.trans ?_  have : (1 / (n : ℝ) ^ 2) * ((n : ℝ) ^ 2 * C) = C := by    rw [← mul_assoc, one_div_mul_cancel (ne_of_gt hn2_pos), one_mul]  rw [this]theorem redistribution_iterated_trade_bounds {n : ℕ} (hn : 3 ≤ n) (θ : Fin n → ℝ)    (hθ : ∀ j, θ j ∈ Set.Icc (0 : ℝ) 1) (i : Fin n) (k : ℕ) :    LipschitzWith 1 ((redistribution_trade θ)^[k] (fun t => max (1 - t) 0)) ∧      LipschitzWith 1 ((redistribution_trade_without θ i)^[k] (fun t => max (1 - t) 0)) ∧      ∀ t, |(redistribution_trade θ)^[k] (fun t => max (1 - t) 0) t -          (redistribution_trade_without θ i)^[k] (fun t => max (1 - t) 0) t| ≤        2 * k * redistribution_one_draw_gap θ i := by  have hn_pos : 0 < n := by omega  have hn_two : 2 ≤ n := by omega  set G : ℝ → ℝ := fun t => max (1 - t) 0  have hG_lip : LipschitzWith 1 G := redistribution_iterated_trade_bounds_lip_G  induction' k with k ih  · simp only [Function.iterate_zero, id_eq]    refine ⟨hG_lip, hG_lip, ?_⟩    intro t    simp  · rcases ih with ⟨ih_T, ih_T_without, ih_dist⟩    rw [Function.iterate_succ' (redistribution_trade θ) k]    rw [Function.iterate_succ' (redistribution_trade_without θ i) k]    have hT_next : LipschitzWith 1 (redistribution_trade θ ((redistribution_trade θ)^[k] G)) :=      redistribution_iterated_trade_bounds_trade_lipschitz hn_pos θ ih_T    have hT_without_next : LipschitzWith 1 (redistribution_trade_without θ i ((redistribution_trade_without θ i)^[k] G)) :=      redistribution_iterated_trade_bounds_trade_without_lipschitz hn_two θ i ih_T_without    refine ⟨hT_next, hT_without_next, ?_⟩    intro t    have h_tri : |redistribution_trade θ ((redistribution_trade θ)^[k] G) t -        redistribution_trade_without θ i ((redistribution_trade_without θ i)^[k] G) t| ≤        |redistribution_trade θ ((redistribution_trade θ)^[k] G) t -          redistribution_trade θ ((redistribution_trade_without θ i)^[k] G) t| +        |redistribution_trade θ ((redistribution_trade_without θ i)^[k] G) t -          redistribution_trade_without θ i ((redistribution_trade_without θ i)^[k] G) t| := by      have : redistribution_trade θ ((redistribution_trade θ)^[k] G) t -          redistribution_trade_without θ i ((redistribution_trade_without θ i)^[k] G) t =          (redistribution_trade θ ((redistribution_trade θ)^[k] G) t -            redistribution_trade θ ((redistribution_trade_without θ i)^[k] G) t) +          (redistribution_trade θ ((redistribution_trade_without θ i)^[k] G) t -            redistribution_trade_without θ i ((redistribution_trade_without θ i)^[k] G) t) := by ring      rw [this]      exact abs_add_le _ _    refine h_tri.trans ?_    have h_term1 := redistribution_iterated_trade_bounds_trade_diff_le hn_pos θ _ _ (2 * (k : ℝ) * redistribution_one_draw_gap θ i) ih_dist t    have h_gap := (redistribution_one_draw_gap_bounds hn θ hθ i ((redistribution_trade_without θ i)^[k] G) 1 ih_T_without t).2    simp only [NNReal.coe_one, mul_one] at h_gap    have h_sum := add_le_add h_term1 h_gap    refine h_sum.trans_eq ?_    push_cast    ring
See it in the graphDiscuss this resultChallenge it