AFTD Auto-Formalizing Theoretical Domains

is_feasible_flow_zero

theoremverified

For any natural number k, the zero flow (fun _ _ => 0) on Fin k is a feasible flow for the zero demand vector 0 : Fin k → ℝ.

Statement

theorem is_feasible_flow_zero (k : ℕ) : is_feasible_flow (fun (_ _ : Fin k) => (0 : ℝ)) (0 : Fin k → ℝ)
Source
arXiv:2611.05669, Section 4.1
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_feasible_flowA signed flow F on Fin k is feasible for a demand vector a : Fin k → ℝ if F is skew-symmetric (F i j = -F j i for all i, j) and the net…
  • nonclairvoyant_scheduling_offline_opt_zeroFor any natural number n, the offline optimal total completion time of the all-zero job processing vector (fun (_ : Fin n) => (0 : ℝ)) is…

Read back from the Lean

For any natural number $k$, the all-zero function on $\text{Fin } k \times \text{Fin } k$ (assigning $0$ to every pair of vertices) is a feasible flow with respect to the all-zero divergence/demand vector $0 : \text{Fin } k \to \mathbb{R}$.

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

To show that the zero flow is feasible for the zero demand vector, the proof unfolds the definition of feasibility into skew-symmetry and demand conservation. Both conditions equate zero to zero, which standard algebraic simplification evaluates to true.

  1. The zero flow on Fin k is feasible for the zero demand vector. automation

    The proof uses a `first` block trying several candidate tactics. The winning branch unfolds the definition of `is_feasible_flow` using `simp only [is_feasible_flow] at *`, which reduces the feasibility claim to two conditions: skew-symmetry (0 = -0 for all pairs) and demand conservation (the sum over all destinations of 0 equals 0). The `simpa` tactic simplifies both conditions to True using standard arithmetic on real numbers (negation of zero is zero, and a sum of zeros is zero).

    line 2

    uses is_feasible_flow, nonclairvoyant_scheduling_offline_opt_zero

    theorem is_feasible_flow_zero (k : ℕ) : is_feasible_flow (fun (_ _ : Fin k) => (0 : ℝ)) (0 : Fin k → ℝ) := by first | exact nonclairvoyant_scheduling_offline_opt_zero | (apply nonclairvoyant_scheduling_offline_opt_zero <;> assumption) | (apply nonclairvoyant_scheduling_offline_opt_zero <;> simp_all) | simpa using nonclairvoyant_scheduling_offline_opt_zero | (simp only [is_feasible_flow] at *; first | exact nonclairvoyant_scheduling_offline_opt_zero | (apply nonclairvoyant_scheduling_offline_opt_zero <;> assumption) | (apply nonclairvoyant_scheduling_offline_opt_zero <;> simp_all) | simpa using nonclairvoyant_scheduling_offline_opt_zero)
is_feasible_flow
A flow F is feasible for demand vector a if F is skew-symmetric (F i j = -F j i) and satisfies the demand conservation equations (∑ j, F i j = a i).
nonclairvoyant_scheduling_offline_opt_zero
The offline optimal cost in nonclairvoyant scheduling for a zero input vector is 0.

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

/-- The zero flow is feasible for the zero demand vector. -/theorem is_feasible_flow_zero (k : ℕ) : is_feasible_flow (fun (_ _ : Fin k) => (0 : ℝ)) (0 : Fin k → ℝ) := by first | exact nonclairvoyant_scheduling_offline_opt_zero | (apply nonclairvoyant_scheduling_offline_opt_zero <;> assumption) | (apply nonclairvoyant_scheduling_offline_opt_zero <;> simp_all) | simpa using nonclairvoyant_scheduling_offline_opt_zero | (simp only [is_feasible_flow] at *; first | exact nonclairvoyant_scheduling_offline_opt_zero | (apply nonclairvoyant_scheduling_offline_opt_zero <;> assumption) | (apply nonclairvoyant_scheduling_offline_opt_zero <;> simp_all) | simpa using nonclairvoyant_scheduling_offline_opt_zero)
See it in the graphDiscuss this resultChallenge it