is_feasible_flow_zero
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.
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).
uses
is_feasible_flow,nonclairvoyant_scheduling_offline_opt_zerotheorem 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.
- The proof script was generated by an automated search trying a list of candidate tactics and lemmas; although `nonclairvoyant_scheduling_offline_opt_zero` is mentioned in `simpa using ...`, it is entirely unused because simplification alone reduces the goal to True.
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.
/-- 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)