AFTD Auto-Formalizing Theoretical Domains

nonclairvoyant_scheduling_lower_bound

def

The function nonclairvoyant_scheduling_lower_bound n lam is defined as the supremum (sSup) in Real of the set of all real numbers rob for which there exist a natural number alpha and a function p : Nat -> Real satisfying: (1) 1 <= alpha and alpha <= (n^2 + 2 * n) / (3 * n + 1) using natural number division; (2) for every natural number i with 1 <= i <= alpha, i * (2 * n + 1 - i) / 2 + (sum_{j=1}^{i-1} (n - j) * p j) + (n + 1 - i) * (n - i) * p i = rob * (i * (i + 1) / 2 + ((n + i + 1) * (n - i) / 2) * p i) where all integer quantities are cast to Real; (3) lam * n * (n + 1) / 2 = (sum_{j=1}^{alpha - 1} (n - j) * p j) + ((n + 1 - alpha) * (n - alpha) / 2) * p alpha; (4) for all i in {1, ..., alpha}, 0 <= p i and p i <= 1; (5) max (2 * n / (n + 1)) ((n - alpha) / (alpha + 1)) <= rob; and (6) rob <= (n + 1 - alpha) / alpha.

Statement

noncomputable def nonclairvoyant_scheduling_lower_bound (n : ℕ) (lam : ℝ) : ℝ
Defined in
arXiv:2610.29037 Definition 3.8 and Theorem 3.9
Verified
25 Oct 2026
Axioms
none listed

Read back from the Lean

nonclairvoyant_scheduling_lower_bound n lam is defined as the supremum (sSup) in ℝ of the set of all rob : ℝ such that there exist α : ℕ and p : ℕ → ℝ satisfying: 1. 1 ≤ α and α ≤ (n^2 + 2 * n) / (3 * n + 1) (using natural number division); 2. For all i : ℕ such that 1 ≤ i ≤ α, i * (2 * n + 1 - i) / 2 + (∑ j ∈ {1, ..., i - 1}, (n - j) * p j) + (n + 1 - i) * (n - i) * p i = rob * (i * (i + 1) / 2 + (n + i + 1) * (n - i) / 2 * p i) (with natural numbers coerced to ℝ); 3. lam * n * (n + 1) / 2 = (∑ j ∈ {1, ..., α - 1}, (n - j) * p j) + (n + 1 - α) * (n - α) / 2 * p α; 4. For all i ∈ {1, ..., α}, 0 ≤ p i ∧ p i ≤ 1; 5. max (2 * n / (n + 1)) ((n - α) / (α + 1)) ≤ rob; and 6. rob ≤ (n + 1 - α) / α.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The lower bound Phi^(n)(lambda) on robustness for non-clairvoyant scheduling. -/
noncomputable def nonclairvoyant_scheduling_lower_bound (n : ℕ) (lam : ℝ) : ℝ := sSup { rob : ℝ | ∃ (α : ℕ) (p : ℕ → ℝ),
    1 ≤ α ∧ α ≤ (n^2 + 2 * n) / (3 * n + 1) ∧
    ((∀ i : ℕ, 1 ≤ i → i ≤ α →
      (i : ℝ) * (2 * (n : ℝ) + 1 - (i : ℝ)) / 2 +
      (∑ j ∈ Finset.Icc 1 (i - 1), ((n : ℝ) - (j : ℝ)) * p j) +
      ((n : ℝ) + 1 - (i : ℝ)) * ((n : ℝ) - (i : ℝ)) * p i =
      rob * ((i : ℝ) * ((i : ℝ) + 1) / 2 + ((n : ℝ) + (i : ℝ) + 1) * ((n : ℝ) - (i : ℝ)) / 2 * p i)) ∧
    (lam * (n : ℝ) * ((n : ℝ) + 1) / 2 =
      (∑ j ∈ Finset.Icc 1 (α - 1), ((n : ℝ) - (j : ℝ)) * p j) +
      ((n : ℝ) + 1 - (α : ℝ)) * ((n : ℝ) - (α : ℝ)) / 2 * p α) ∧
    (∀ i ∈ Finset.Icc 1 α, 0 ≤ p i ∧ p i ≤ 1)) ∧
    max (2 * (n : ℝ) / ((n : ℝ) + 1)) (((n : ℝ) - (α : ℝ)) / ((α : ℝ) + 1)) ≤ rob ∧
    rob ≤ ((n : ℝ) + 1 - (α : ℝ)) / (α : ℝ) }
See it in the graphDiscuss this resultChallenge it