AFTD Auto-Formalizing Theoretical Domains

multidim_instance_exists

theoremverified

For every natural number D ≥ 1, there exists an instance of multidimensional scheduling with D resources.

Statement

theorem multidim_instance_exists (D : ℕ) (hD : 1 ≤ D) : Nonempty (MultidimInstance D)
Source
arXiv:2611.07905 Tight Worst-Case Completion-Time Bounds for Dominant Resource Fairness, Section 2.1
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • MultidimInstanceAn instance of multidimensional scheduling with D resource types and zero release times, consisting of a positive number of jobs n with…
Used by 1

Read back from the Lean

For every natural number $D$ with $D \ge 1$, the type MultidimInstance D is non-empty (i.e., there exists an inhabitant of MultidimInstance D).

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 is proved by explicitly constructing a valid multidimensional scheduling instance with a single job (n = 1). All processing times, utilities, and resource demands are set to 1, which trivially satisfy the required positivity and unit bound conditions. The hypothesis 1 ≤ D guarantees that resource index 0 is valid, providing a dominant resource with demand 1 for the job.

  1. We initiate the construction of a valid scheduling instance with a single job (n = 1) and verify that 0 < 1.

    An explicit instance is constructed to show that the type `MultidimInstance D` is nonempty. The number of jobs `n` is set to 1, and positivity is verified using `Nat.zero_lt_one`.

    lines 2–4

    uses Nat.zero_lt_one

    theorem multidim_instance_exists (D : ℕ) (hD : 1 ≤ D) : Nonempty (MultidimInstance D) := ⟨{
      n := 1
      hn := Nat.zero_lt_one
  2. The job has processing time 1 and utility 1, both strictly positive.

    The processing time function `p` and utility function `u` are each defined to be constantly 1 on all jobs. Their positivity is established by `Real.zero_lt_one`.

    lines 5–8

    uses Real.zero_lt_one

      p := fun _ => 1
      hp := fun _ => Real.zero_lt_one
      u := fun _ => 1
      hu := fun _ => Real.zero_lt_one
  3. All resource requirements are set to 1, satisfying the lower bound 0 and upper bound 1.

    The resource demand matrix `a` assigns a requirement of 1 for every job and resource. The condition `0 ≤ 1` is proved by `zero_le_one`, and `1 ≤ 1` is proved by reflexivity with `le_rfl`.

    lines 9–11

    uses zero_le_one, le_rfl

      a := fun _ _ => 1
      ha_nonneg := fun _ _ => zero_le_one
      ha_le_one := fun _ _ => le_rfl
  4. Every job has a dominant resource where its requirement is 1.

    For the single job, resource 0 is provided as a witness. This is a valid resource index in `Fin D` because 0 < D follows from 1 ≤ D (`hD`), and the requirement at resource 0 is 1 by definition.

    lines 12–13

      ha_dominant := fun _ => ⟨⟨0, hD⟩, rfl⟩
    }⟩
Nat.zero_lt_one
Zero is strictly less than one in the natural numbers.
Real.zero_lt_one
Zero is strictly less than one in the real numbers.
zero_le_one
Zero is less than or equal to one.
le_rfl
The ordering relation is reflexive: any element is less than or equal to itself.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Witness that MultidimInstance D is nonempty for D ≥ 1. -/theorem multidim_instance_exists (D : ℕ) (hD : 1 ≤ D) : Nonempty (MultidimInstance D) := ⟨{  n := 1  hn := Nat.zero_lt_one  p := fun _ => 1  hp := fun _ => Real.zero_lt_one  u := fun _ => 1  hu := fun _ => Real.zero_lt_one  a := fun _ _ => 1  ha_nonneg := fun _ _ => zero_le_one  ha_le_one := fun _ _ => le_rfl  ha_dominant := fun _ => ⟨⟨0, hD⟩, rfl⟩}⟩
See it in the graphDiscuss this resultChallenge it