AFTD Auto-Formalizing Theoretical Domains

trade_residual_error_round_one_tight

theoremverifiedoriginal

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.

  1. 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.

    lines 1–8

    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']
  2. 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.

    lines 10–24

    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']
  3. 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.

    lines 26–34

    uses trade_residual_error_round_one_tight_sum_max_theta_sub

    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
  4. 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.

    lines 37–47

    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
  5. 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.

    lines 48–57

    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, ?_⟩
  6. 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.

    lines 58–70

    uses harmonic, trade_residual_error_round_one_tight_trade_shortfall_eq, zero_sub, abs_neg, abs_of_nonneg, div_nonneg

      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]
  7. 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.

    lines 71–74

    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

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
See it in the graphDiscuss this resultChallenge it