redistribution_one_draw_gap_bounds
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.
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.
uses
add_sum_erase,card_erase_of_mem,card_fin,sum_sub_distrib,sum_consthave 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
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.
uses
abs_sub,abs_of_nonneghave : |a - b| ≤ |a| + |b| := abs_sub a b rw [abs_of_nonneg ha, abs_of_nonneg hb] at this exact this
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.
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_lefthave 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
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.
uses
abs_mul,abs_of_nonneg,le_trans,le_of_equnfold 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
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.
uses
LipschitzWith.of_dist_le_mul,Real.dist_eq,abs_negapply 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)
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.
uses
mul_sum,sum_congrunfold redistribution_trade redistribution_fill_in rw [mul_sum, mul_sum] apply sum_congr rfl intro j _ ring
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).
uses
sum_comm,mul_sum,sum_congrunfold 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]
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.
uses
mul_sum,sum_comm,sum_congrunfold 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
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.
uses
mul_sub,sum_sub_distrib,abs_mul,abs_of_nonneg,abs_sum_le_sum_abs,sum_le_sum,mul_le_mul_of_nonneg_leftrw [← 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
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.
uses
mul_sub,sum_sub_distrib,abs_mul,abs_of_nonneg,abs_sum_le_sum_abs,sum_le_sum,mul_le_mul_of_nonneg_leftrw [← 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
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.
uses
redistribution_one_draw_gap_bounds_fill_in_sub_without_boundconstructor · exact redistribution_one_draw_gap_bounds_fill_in_sub_without_bound hn θ hθ i F L hF t
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.
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
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.
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_bounddsimp [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
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.
uses
abs_add_le,add_le_addhave 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
- Algebraic simplifications of finite sums and rational expressions are handled by field_simp, ring, and linear arithmetic tactics (omega, linarith).
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_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