multidim_instance_exists
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
- cyclic_permutation_subtraction_set_nonemptyFor any natural numbers d, s, a, b, the finite set cyclic_permutation_subtraction_set d s a b is nonempty.
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.
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`.
uses
Nat.zero_lt_onetheorem multidim_instance_exists (D : ℕ) (hD : 1 ≤ D) : Nonempty (MultidimInstance D) := ⟨{ n := 1 hn := Nat.zero_lt_oneThe 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`.
uses
Real.zero_lt_onep := fun _ => 1 hp := fun _ => Real.zero_lt_one u := fun _ => 1 hu := fun _ => Real.zero_lt_one
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`.
uses
zero_le_one,le_rfla := fun _ _ => 1 ha_nonneg := fun _ _ => zero_le_one ha_le_one := fun _ _ => le_rfl
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.
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⟩}⟩