trade_residual_error_round_one_tight
There exists a real constant c > 0 such that for every natural number n ≥ 3, there exists a profile θ : Fin n → ℝ with each θ i in [0, 1] and positive sum ∑ i, θ i > 0 such that c * (∑ i, θ i) / (n * (harmonic 1 : ℝ)) ≤ |redistribution_trade_error θ 1 (∑ i, θ i)|.
Statement
theorem trade_residual_error_round_one_tight :
∃ c > (0 : ℝ), ∀ (n : ℕ) (hn : 3 ≤ n),
∃ (θ : Fin n → ℝ) (hθ : ∀ i, θ i ∈ Set.Icc (0 : ℝ) 1) (hs : 0 < ∑ i, θ i),
c * ((∑ i, θ i) / (n * (harmonic 1 : ℝ))) ≤
|redistribution_trade_error θ 1 (∑ i, θ i)|- Related work
- arXiv:2610.10995 Remark 6.2
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- redistribution_trade_errorThe m-th order error function E_m = (I - T)^m G after m rounds of trade error correction on the shortfall function G(t) = max(1 - t, 0).
- redistribution_shortfallThe shortfall function G(t) = max(1 - t, 0), representing the amount by which a total report falls short of the project cost 1.
- redistribution_tradeThe trade operation on the reports: (T f)(t) = (1/n²) Σ_{j,k} f(t − θ_j + θ_k).
Read back from the Lean
There exists a real constant $c > 0$ such that for every natural number $n \ge 3$, there exists a vector $\theta : \mathrm{Fin}\, n \to \mathbb{R}$ satisfying: 1. $\theta_i \in [0, 1]$ for every $i \in \mathrm{Fin}\, n$, 2. $\sum_{i \in \mathrm{Fin}\, n} \theta_i > 0$, such that: $$c \cdot \frac{\sum_{i \in \mathrm{Fin}\, n} \theta_i}{n \cdot (\mathrm{harmonic}(1) : \mathbb{R})} \le \left| \mathrm{redistribution\_trade\_error}(\theta, 1)\left(\sum_{i \in \mathrm{Fin}\, n} \theta_i\right) \right|$$
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem establishes that the harmonic residual error bound for one round of trade is tight up to a constant c = 1/2. For any n ≥ 3, the proof constructs an extremal profile θ by placing mass 1 on a single coordinate and 0 on all others, giving total sum 1. The one-round trade on the shortfall function evaluates to (n - 1) / n^2, and because the baseline shortfall at t = 1 is 0, the absolute residual trade error is exactly (n - 1) / n^2. This exceeds the theoretical lower bound (1/2) / n since n^2 ≤ 2n(n - 1) holds for all n ≥ 3.
For any index i₀ ∈ Fin n, the sum of 1 - 𝟏_{k = i₀} over all k ∈ Fin n equals n - 1.
We rewrite the indicator of k ≠ i₀ as 1 - 𝟏_{k = i₀}. Splitting the sum gives the sum of 1 over Fin n minus the sum of the single-point indicator 𝟏_{k = i₀}. Since Fin n has cardinality n, the constant sum is n, and the single-point indicator sums to 1, leaving n - 1.
uses
Finset.sum_sub_distrib,Finset.sum_const,Finset.card_univ,Fintype.card_fin,Finset.sum_ite_eq'lemma trade_residual_error_round_one_tight_sum_ite_ne (n : ℕ) (i₀ : Fin n) : ∑ k : Fin n, (if k = i₀ then (0 : ℝ) else 1) = n - 1 := by have : (fun k : Fin n => (if k = i₀ then (0 : ℝ) else 1)) = fun k => 1 - (if k = i₀ then 1 else 0) := by funext k split_ifs <;> ring rw [this, Finset.sum_sub_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin] simp [Finset.sum_ite_eq']
For the one-hot profile θ centered at i₀, the double sum ∑ j, ∑ k, max (θ j - θ k, 0) equals n - 1.
For any pair (j, k), θ j - θ k is 1 when j = i₀ and k ≠ i₀, and at most 0 otherwise, so max (θ j - θ k, 0) is 1 exactly when j = i₀ and k ≠ i₀. Summing this over k for fixed j gives n - 1 when j = i₀ (by trade_residual_error_round_one_tight_sum_ite_ne) and 0 when j ≠ i₀. Summing over all j picks out the single non-zero value at j = i₀, yielding n - 1.
uses
trade_residual_error_round_one_tight_sum_ite_ne,Finset.sum_ite_eq'lemma trade_residual_error_round_one_tight_sum_max_theta_sub (n : ℕ) (i₀ : Fin n) : let θ : Fin n → ℝ := fun i => if i = i₀ then 1 else 0 ∑ j, ∑ k, max (θ j - θ k) 0 = (n - 1 : ℝ) := by intro θ have h_term (j k : Fin n) : max (θ j - θ k) 0 = if j = i₀ then (if k = i₀ then 0 else 1) else 0 := by dsimp [θ] by_cases hj : j = i₀ <;> by_cases hk : k = i₀ <;> simp [hj, hk] simp_rw [h_term] have h_inner (j : Fin n) : ∑ k, (if j = i₀ then (if k = i₀ then (0 : ℝ) else 1) else 0) = if j = i₀ then (n - 1 : ℝ) else 0 := by by_cases hj : j = i₀ · simp [hj, trade_residual_error_round_one_tight_sum_ite_ne] · simp [hj] simp_rw [h_inner] simp [Finset.sum_ite_eq']
For the one-hot profile θ centered at i₀, the one-round redistribution trade of the shortfall function at t = 1 equals (n - 1) / n^2.
Unfolding the definitions of redistribution trade and redistribution shortfall, the trade at t = 1 is (1 / n^2) ∑ j, ∑ k, max (1 - (1 - θ j + θ k), 0). The argument simplifies to θ j - θ k, so the double sum is ∑ j, ∑ k, max (θ j - θ k, 0). Applying trade_residual_error_round_one_tight_sum_max_theta_sub evaluates this sum to n - 1, giving (n - 1) / n^2.
uses
trade_residual_error_round_one_tight_sum_max_theta_sublemma trade_residual_error_round_one_tight_trade_shortfall_eq (n : ℕ) (i₀ : Fin n) : let θ : Fin n → ℝ := fun i => if i = i₀ then 1 else 0 redistribution_trade θ redistribution_shortfall 1 = (n - 1 : ℝ) / (n : ℝ) ^ 2 := by intro θ dsimp [redistribution_trade, redistribution_shortfall] have h_simp (j k : Fin n) : (1 : ℝ) - (1 - θ j + θ k) = θ j - θ k := by ring simp_rw [h_simp] rw [trade_residual_error_round_one_tight_sum_max_theta_sub n i₀] ring
We choose the constant c = 1/2 > 0 and, for any n ≥ 3, fix the index i₀ = 0 ∈ Fin n and candidate profile θ = 𝟏_{i₀}.
We set c = 1/2, which is strictly positive by numerical normalization. For n ≥ 3, n is strictly positive, so 0 is a valid index i₀ ∈ Fin n. We define θ to be the indicator profile taking value 1 at i₀ and 0 at all other coordinates.
theorem trade_residual_error_round_one_tight : ∃ c > (0 : ℝ), ∀ (n : ℕ) (hn : 3 ≤ n), ∃ (θ : Fin n → ℝ) (hθ : ∀ i, θ i ∈ Set.Icc (0 : ℝ) 1) (hs : 0 < ∑ i, θ i), c * ((∑ i, θ i) / (n * (harmonic 1 : ℝ))) ≤ |redistribution_trade_error θ 1 (∑ i, θ i)| := by use 1 / 2 refine ⟨by norm_num, fun n hn => ?_⟩ have hn_pos : 0 < n := by omega have hn_real : (3 : ℝ) ≤ n := by exact_mod_cast hn let i₀ : Fin n := ⟨0, hn_pos⟩ let θ : Fin n → ℝ := fun i => if i = i₀ then 1 else 0
The profile θ takes values in [0, 1] and has strictly positive sum ∑ i, θ i = 1.
Each coordinate θ i is either 1 (if i = i₀) or 0 (if i ≠ i₀), both of which belong to [0, 1]. Summing over all coordinates contains exactly one non-zero term equal to 1, so ∑ i, θ i = 1 > 0.
uses
Finset.sum_ite_eq'have hθ : ∀ i, θ i ∈ Set.Icc (0 : ℝ) 1 := fun i => by dsimp [θ] split_ifs <;> simp have hs_val : ∑ i, θ i = 1 := by dsimp [θ] simp [Finset.sum_ite_eq'] have hs : 0 < ∑ i, θ i := by rw [hs_val] norm_num refine ⟨θ, hθ, hs, ?_⟩
The first harmonic number is 1, and the absolute redistribution trade error at t = ∑ i, θ i = 1 equals (n - 1) / n^2.
Since ∑ i, θ i = 1, the error is evaluated at t = 1. The first harmonic number harmonic 1 equals 1. The one-round trade error is the difference between the baseline shortfall and the trade outcome: redistribution_shortfall 1 = max (1 - 1, 0) = 0, while the trade outcome is (n - 1) / n^2 by trade_residual_error_round_one_tight_trade_shortfall_eq. The difference is 0 - (n - 1) / n^2 = -(n - 1) / n^2. Since n ≥ 3, (n - 1) / n^2 is non-negative, so its absolute value is (n - 1) / n^2.
uses
harmonic,trade_residual_error_round_one_tight_trade_shortfall_eq,zero_sub,abs_neg,abs_of_nonneg,div_nonnegrw [hs_val] have h_harm : (harmonic 1 : ℝ) = 1 := by simp [harmonic] rw [h_harm] have h_trade : redistribution_trade θ redistribution_shortfall 1 = (n - 1 : ℝ) / (n : ℝ) ^ 2 := trade_residual_error_round_one_tight_trade_shortfall_eq n i₀ have h_err : |redistribution_trade_error θ 1 1| = (n - 1 : ℝ) / (n : ℝ) ^ 2 := by change |redistribution_shortfall 1 - redistribution_trade θ redistribution_shortfall 1| = _ have h_sf : redistribution_shortfall 1 = 0 := by simp [redistribution_shortfall] rw [h_sf, h_trade] simp only [zero_sub, abs_neg] rw [abs_of_nonneg] apply div_nonneg <;> nlinarith rw [h_err]
The required lower bound inequality c * (∑ i, θ i) / (n * harmonic 1) ≤ |error| holds for all n ≥ 3.
The left-hand side simplifies to (1/2) * (1 / (n * 1)) = 1 / (2n), while the right-hand side is (n - 1) / n^2. Since both 2n and n^2 are strictly positive for n ≥ 3, cross-multiplying via div_le_div_iff₀ transforms 1 / (2n) ≤ (n - 1) / n^2 into n^2 ≤ 2n(n - 1) = 2n^2 - 2n. This is equivalent to 0 ≤ n(n - 2), which holds by arithmetic because n ≥ 3.
uses
div_le_div_iff₀have h_lhs : (1 : ℝ) / 2 * (1 / (↑n * 1)) = 1 / (2 * (n : ℝ)) := by ring rw [h_lhs] rw [div_le_div_iff₀ (by positivity) (by positivity)] nlinarith
Finset.sum_sub_distrib- The sum of a difference of two functions over a finite set equals the difference of their sums.
Finset.sum_const- The sum of a constant value over a finite set equals the cardinality of the set multiplied by that constant.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin- The cardinality of the standard finite set Fin n is n.
Finset.sum_ite_eq'- Summing over a finite set an indicator that is non-zero only at a single element a evaluates to the value at a, provided a is in the set.
trade_residual_error_round_one_tight_sum_ite_ne- The sum over Fin n of the indicator that an index is not equal to i₀ equals n - 1.
trade_residual_error_round_one_tight_sum_max_theta_sub- For the indicator profile concentrated at i₀, the double sum ∑ j, ∑ k, max (θ j - θ k) 0 equals n - 1.
trade_residual_error_round_one_tight_trade_shortfall_eq- For the indicator profile concentrated at i₀, the redistribution trade of the shortfall function at 1 is (n - 1) / n^2.
harmonic- The harmonic number function on natural numbers, with harmonic 1 = 1.
zero_sub- Subtracting an element from zero gives its negation: 0 - a = -a.
abs_neg- The absolute value of the negation of a number equals the absolute value of the number: |-a| = |a|.
abs_of_nonneg- If a number is non-negative, its absolute value equals the number itself: if 0 ≤ a then |a| = a.
div_nonneg- The quotient of two non-negative numbers is non-negative.
div_le_div_iff₀- For strictly positive denominators, a / b ≤ c / d if and only if a * d ≤ c * b.
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.
lemma trade_residual_error_round_one_tight_sum_ite_ne (n : ℕ) (i₀ : Fin n) : ∑ k : Fin n, (if k = i₀ then (0 : ℝ) else 1) = n - 1 := by have : (fun k : Fin n => (if k = i₀ then (0 : ℝ) else 1)) = fun k => 1 - (if k = i₀ then 1 else 0) := by funext k split_ifs <;> ring rw [this, Finset.sum_sub_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin] simp [Finset.sum_ite_eq']lemma trade_residual_error_round_one_tight_sum_max_theta_sub (n : ℕ) (i₀ : Fin n) : let θ : Fin n → ℝ := fun i => if i = i₀ then 1 else 0 ∑ j, ∑ k, max (θ j - θ k) 0 = (n - 1 : ℝ) := by intro θ have h_term (j k : Fin n) : max (θ j - θ k) 0 = if j = i₀ then (if k = i₀ then 0 else 1) else 0 := by dsimp [θ] by_cases hj : j = i₀ <;> by_cases hk : k = i₀ <;> simp [hj, hk] simp_rw [h_term] have h_inner (j : Fin n) : ∑ k, (if j = i₀ then (if k = i₀ then (0 : ℝ) else 1) else 0) = if j = i₀ then (n - 1 : ℝ) else 0 := by by_cases hj : j = i₀ · simp [hj, trade_residual_error_round_one_tight_sum_ite_ne] · simp [hj] simp_rw [h_inner] simp [Finset.sum_ite_eq']lemma trade_residual_error_round_one_tight_trade_shortfall_eq (n : ℕ) (i₀ : Fin n) : let θ : Fin n → ℝ := fun i => if i = i₀ then 1 else 0 redistribution_trade θ redistribution_shortfall 1 = (n - 1 : ℝ) / (n : ℝ) ^ 2 := by intro θ dsimp [redistribution_trade, redistribution_shortfall] have h_simp (j k : Fin n) : (1 : ℝ) - (1 - θ j + θ k) = θ j - θ k := by ring simp_rw [h_simp] rw [trade_residual_error_round_one_tight_sum_max_theta_sub n i₀] ring/-- Tightness of the harmonic residual error bound for m = 1 round of trade (OP-158 base case). -/theorem trade_residual_error_round_one_tight : ∃ c > (0 : ℝ), ∀ (n : ℕ) (hn : 3 ≤ n), ∃ (θ : Fin n → ℝ) (hθ : ∀ i, θ i ∈ Set.Icc (0 : ℝ) 1) (hs : 0 < ∑ i, θ i), c * ((∑ i, θ i) / (n * (harmonic 1 : ℝ))) ≤ |redistribution_trade_error θ 1 (∑ i, θ i)| := by use 1 / 2 refine ⟨by norm_num, fun n hn => ?_⟩ have hn_pos : 0 < n := by omega have hn_real : (3 : ℝ) ≤ n := by exact_mod_cast hn let i₀ : Fin n := ⟨0, hn_pos⟩ let θ : Fin n → ℝ := fun i => if i = i₀ then 1 else 0 have hθ : ∀ i, θ i ∈ Set.Icc (0 : ℝ) 1 := fun i => by dsimp [θ] split_ifs <;> simp have hs_val : ∑ i, θ i = 1 := by dsimp [θ] simp [Finset.sum_ite_eq'] have hs : 0 < ∑ i, θ i := by rw [hs_val] norm_num refine ⟨θ, hθ, hs, ?_⟩ rw [hs_val] have h_harm : (harmonic 1 : ℝ) = 1 := by simp [harmonic] rw [h_harm] have h_trade : redistribution_trade θ redistribution_shortfall 1 = (n - 1 : ℝ) / (n : ℝ) ^ 2 := trade_residual_error_round_one_tight_trade_shortfall_eq n i₀ have h_err : |redistribution_trade_error θ 1 1| = (n - 1 : ℝ) / (n : ℝ) ^ 2 := by change |redistribution_shortfall 1 - redistribution_trade θ redistribution_shortfall 1| = _ have h_sf : redistribution_shortfall 1 = 0 := by simp [redistribution_shortfall] rw [h_sf, h_trade] simp only [zero_sub, abs_neg] rw [abs_of_nonneg] apply div_nonneg <;> nlinarith rw [h_err] have h_lhs : (1 : ℝ) / 2 * (1 / (↑n * 1)) = 1 / (2 * (n : ℝ)) := by ring rw [h_lhs] rw [div_le_div_iff₀ (by positivity) (by positivity)] nlinarith