AFTD Auto-Formalizing Theoretical Domains

not_threshold_schedule_competitive_ratio_two

theoremverifiedoriginal

The statement threshold_schedule_competitive_ratio_two is false: The reset price K : ℝ is unrestricted, and for negative K the claim fails. Take T = 2, a ≡ 0 : Fin 1 → NNReal, K = -1, and the schedule r ≡ true. - schedule_history 2 a r 0 = 0 and schedule_history 2 a r 1 = 0 (the increment is 0), so rent_or_buy_cost 2 a (-1) (fun _ => true) = (0 + (-1)) + (0 + (-1)) = -2. - The threshold state starts at (0,0), so at t = 0 the rule buys iff -1 ≤ 0, i.e. true; then the state at t = 1 is (a 0, 0) = (0,0) and it again buys. Hence threshold_schedule 2 a (-1) ≡ true and rent_or_buy_cost 2 a (-1) (threshold_schedule 2 a (-1)) = -2. The required inequality then reads -2 ≤ 2 * (-2) = -4, which is false. This is counterexample to the theorem with no hypothesis on the sign of K; the published Proposition presumably assumes the reset price is nonnegative. I have verified ¬ (∀ T a K r, rent_or_buy_cost T a K (threshold_schedule T a K) ≤ 2 * rent_or_buy_cost T a K r) in Lean.

Statement

theorem not_threshold_schedule_competitive_ratio_two : ¬ (∀ (T : ℕ) (a : Fin (T - 1) → NNReal) (K : ℝ)
    (r : Fin T → Bool), rent_or_buy_cost T a K (threshold_schedule T a K) ≤ 2 * rent_or_buy_cost T a K r)
Related work
refutes `threshold_schedule_competitive_ratio_two`
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • threshold_stateGiven horizon T : ℕ, increments a : Fin (T - 1) → NNReal, and reset price K : ℝ, threshold_state T a K : Fin T → NNReal × NNReal is…
  • schedule_historyGiven a horizon T : ℕ, increments a : Fin (T - 1) → NNReal, and a schedule r : Fin T → Bool, schedule_history T a r : Fin T → NNReal is…
  • rent_or_buy_costGiven horizon T : ℕ, increments a : Fin (T - 1) → NNReal, reset price K : ℝ, and a schedule r : Fin T → Bool, rent_or_buy_cost T a K r : ℝ…
  • threshold_scheduleGiven horizon T : ℕ, increments a : Fin (T - 1) → NNReal, reset price K : ℝ, and call t : Fin T, threshold_schedule T a K t : Bool is…

The proof, explained

The theorem refutes the claim that the threshold schedule is 2-competitive by providing an explicit counterexample when the reset price K is allowed to be negative. Assuming for contradiction that the inequality holds universally, we specialize to horizon T = 2, zero increments a = 0, reset price K = -1, and the schedule r that buys at every step. On this instance, both the reference schedule r and the threshold schedule buy at both steps, each incurring a total cost of -2. The competitive ratio bound would then require -2 ≤ 2 * (-2) = -4, which is impossible.

  1. Assuming the 2-competitive ratio holds universally, it must hold for horizon T = 2, increments a ≡ 0, reset price K = -1, and the constant schedule r ≡ true.

    We assume for contradiction that the 2-competitive bound holds for all instances. Specializing the universal quantifier to horizon T = 2, cost increments identically 0, negative reset price K = -1, and the schedule r that buys at every step produces an inequality between the threshold schedule cost and twice the cost of r.

    lines 3–4

      intro h
      have hh := h 2 (fun _ => (0 : NNReal)) (-1) (fun _ => true)
  2. The cost of the constant-true schedule on this counterexample instance is -2.

    Using rent_or_buy_cost.eq_def and Fin.sum_univ_two, the total cost expands to the sum over t = 0 and t = 1. Applying schedule_history.eq_def shows that the history cost is 0 at both steps, while buying at each step adds K = -1, resulting in (0 + (-1)) + (0 + (-1)) = -2.

    lines 5–9

    uses rent_or_buy_cost.eq_def, Fin.sum_univ_two, schedule_history.eq_def

      have e1 : rent_or_buy_cost 2 (fun _ => (0 : NNReal)) (-1) (fun _ => true) = -2 := by
        rw [rent_or_buy_cost.eq_def]
        simp only [Fin.sum_univ_two]
        rw [schedule_history.eq_def, schedule_history.eq_def]
        norm_num
  3. The cost of the threshold schedule on this counterexample instance is also -2.

    We again expand the cost sum over the two time steps using rent_or_buy_cost.eq_def, Fin.sum_univ_two, and schedule_history.eq_def. Unfolding threshold_schedule.eq_def and threshold_state.eq_def, the state starts at (0, 0), so at t = 0 the threshold condition -1 ≤ 0 holds and the algorithm buys. At t = 1, the state transitions to (a(0), 0) = (0, 0), so it buys again. Incurring K = -1 at each step with 0 history gives a total cost of -2.

    lines 10–15

    uses rent_or_buy_cost.eq_def, Fin.sum_univ_two, schedule_history.eq_def, threshold_schedule.eq_def, threshold_state.eq_def

      have e2 : rent_or_buy_cost 2 (fun _ => (0 : NNReal)) (-1)
          (threshold_schedule 2 (fun _ => (0 : NNReal)) (-1)) = -2 := by
        rw [rent_or_buy_cost.eq_def]
        simp only [Fin.sum_univ_two]
        rw [schedule_history.eq_def, schedule_history.eq_def]
        norm_num [threshold_schedule.eq_def, threshold_state.eq_def]
  4. A contradiction is reached, refuting the universal 2-competitiveness claim.

    Substituting the computed costs of -2 into the specialized inequality yields -2 ≤ 2 * (-2) = -4, which is false by elementary arithmetic.

    lines 16–17

      rw [e1, e2] at hh
      norm_num at hh
Fin.sum_univ_two
A sum over the two-element type Fin 2 decomposes into the sum of the term at 0 and the term at 1.
rent_or_buy_cost.eq_def
The total cost under a schedule is defined as the sum over all time steps t of the accumulated history cost plus K if the schedule buys at step t (and 0 otherwise).
schedule_history.eq_def
The accumulated history cost is 0 at time 0; at time t + 1, it is a(t) if the schedule bought at time t, and the previous history plus a(t) otherwise.
threshold_schedule.eq_def
The threshold policy buys at time t if and only if K is at most the sum of the accumulated cost and current increment in the threshold state at time t.
threshold_state.eq_def
The threshold tracking state starts at (0, 0) at time 0; at step t + 1, it resets to (a(t), 0) if K is at most the sum of the accumulated cost and increment, and updates to (h + a(t), acc + h) otherwise.

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

theorem not_threshold_schedule_competitive_ratio_two : ¬ (∀ (T : ℕ) (a : Fin (T - 1) → NNReal) (K : ℝ)    (r : Fin T → Bool), rent_or_buy_cost T a K (threshold_schedule T a K) ≤ 2 * rent_or_buy_cost T a K r) := by  intro h  have hh := h 2 (fun _ => (0 : NNReal)) (-1) (fun _ => true)  have e1 : rent_or_buy_cost 2 (fun _ => (0 : NNReal)) (-1) (fun _ => true) = -2 := by    rw [rent_or_buy_cost.eq_def]    simp only [Fin.sum_univ_two]    rw [schedule_history.eq_def, schedule_history.eq_def]    norm_num  have e2 : rent_or_buy_cost 2 (fun _ => (0 : NNReal)) (-1)      (threshold_schedule 2 (fun _ => (0 : NNReal)) (-1)) = -2 := by    rw [rent_or_buy_cost.eq_def]    simp only [Fin.sum_univ_two]    rw [schedule_history.eq_def, schedule_history.eq_def]    norm_num [threshold_schedule.eq_def, threshold_state.eq_def]  rw [e1, e2] at hh  norm_num at hh
See it in the graphDiscuss this resultChallenge it