Lemma 6.10 — a coordinate box of half-widths lies in the spanner parallelepiped
ProvedRelatedSchedFPTAS796.Main.lemma_6_10latticeslinear-algebrap2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be linearly independent. Write and let , so that . Then
In the proof of Theorem 1.3 this shows that a progression of side in direction has spanner coordinates in .
Differences from the source:
- encoding: for the lattice generated by → of the matrix with rows ; reason: the determinant of a lattice with basis is
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace RelatedSchedFPTAS796.Main
/-- **Lemma 6.10**, p.22 (proof Appendix A, pp.25–26). Let `N_1, …, N_d > 0` and let
`b_1, …, b_d ∈ ∏_i [−N_i, N_i]` be linearly independent, `Φ = ∏_i N_i`, and
`Λ = span_ℤ{b_1, …, b_d}`, so `det(Λ) = |det(b_1, …, b_d)|`. Then
`{∑_i x_i e_i : |x_i| ≤ N_i det(Λ)/(d^d Φ) ∀ i} ⊆ {∑_j t_j b_j : |t_j| ≤ 1 ∀ j}`. -/
theorem lemma_6_10 {d : ℕ} (N : Fin d → ℝ) (hN : ∀ i, 0 < N i) (b : Fin d → Fin d → ℝ)
(hbox : ∀ j i, |b j i| ≤ N i) (hli : LinearIndependent ℝ b) (x : Fin d → ℝ)
(hx : ∀ i, |x i| ≤ N i * |(Matrix.of b).det| / ((d : ℝ) ^ d * ∏ i, N i)) :
∃ t : Fin d → ℝ, (∀ j, |t j| ≤ 1) ∧ x = ∑ j, t j • b j := by sorry
end RelatedSchedFPTAS796.Main
Source
Lin Chen, Tingwei Hu, Jiayi Lian, Yuchen Mao, Guochuan Zhang, Faster Approximation Schemes for Scheduling on Related Machines, STOC 2027 submission #796 (October 2026), source.pdf SHA-256 5d7d0135eed9cbe942c80598e2bb07d8c56ab67aec0d6e8486a067237654f7f3, p.22, Lemma 6.10 (proof Appendix A, pp.25–26)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.