redistribution_iterated_trade_bounds
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.
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|.
uses
lipschitzWith_iff_dist_le_mul,NNReal.coe_one,one_mul,Real.dist_eq,abs_max_sub_max_le_abs,abs_negrw [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
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)).
uses
lipschitzWith_iff_dist_le_mul,NNReal.coe_one,one_mul,Real.dist_eq,mul_sub,sum_sub_distrib,sum_congr,abs_mulrw [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]
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|.
uses
Nat.cast_pos.mpr,sq_pos_of_pos,abs_of_pos,one_div_pos.mpr,abs_sum_le_sum_abs,sum_le_sumhave 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
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.
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_mulhave 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]
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.
uses
lipschitzWith_iff_dist_le_mul,NNReal.coe_one,one_mul,Real.dist_eq,mul_sub,sum_sub_distrib,sum_congr,abs_mulrw [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]
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|.
uses
sq_pos_of_pos,abs_of_pos,one_div_pos.mpr,abs_sum_le_sum_abs,sum_le_sumhave 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
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.
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_mulhave 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]
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)).
uses
mul_sub,sum_sub_distrib,sum_congr,abs_muldsimp [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]
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.
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_mulhave 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]
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.
uses
redistribution_iterated_trade_bounds_lip_G,Function.iterate_zero,id_eqhave 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
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.
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
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)|.
uses
abs_add_lehave 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 ?_
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.
uses
redistribution_iterated_trade_bounds_trade_diff_le,redistribution_one_draw_gap_bounds,NNReal.coe_one,mul_one,add_le_addhave 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
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.
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