Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Real cones, integer semigroups and the true diagonal Frobenius threshold

Definition
RelatedSchedFPTAS796_Main_Supplement_Frobenius

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

additive-combinatoricsapproximation-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

For a finite real vector set AAA, define the real cone and nonnegative integer semigroup by

Cone⁡(A)={∑a∈Aλaa:λa≥0},S~(A)={∑a∈Akaa:ka∈N}.\operatorname{Cone}(A)=\{\sum_{a\in A}\lambda_a a:\lambda_a\ge0\},\qquad \widetilde S(A)=\{\sum_{a\in A}k_a a:k_a\in\mathbb N\}.Cone(A)={a∈A∑​λa​a:λa​≥0},S(A)={a∈A∑​ka​a:ka​∈N}.

Both contain the empty sum. A shift sss covers the ambient lattice ZZZ if every x∈Zx\in Zx∈Z with x−s∈Cone⁡(A)x-s\in\operatorname{Cone}(A)x−s∈Cone(A) belongs to S~(A)\widetilde S(A)S(A). The diagonal Frobenius number is the infimum, in N∪{∞}\mathbb N\cup\{\infty\}N∪{∞}, of the natural thresholds ttt for which the shift t∑a∈Aat\sum_{a\in A}at∑a∈A​a covers ZZZ. Thus no qualifying threshold gives infinity, and a nonempty qualifying set gives its true least element.

Use the existing integer-coordinate lattice, quotient and spanner interfaces. A full-rank real lattice is represented as e(Z0)e(Z_0)e(Z0​), where Z0Z_0Z0​ is a finite-index subgroup of Zd\mathbb Z^dZd and eee is an arbitrary invertible real linear map applied to the standard integer embedding. The generators are the image of a finite integer set A0⊆Z0A_0\subseteq Z_0A0​⊆Z0​. Every full-rank real lattice and every finite subset admit this representation; no rationality of the actual vectors is imposed. Proper sublattices and cosets are checked in coordinates using the published quotient. The condition is at least two represented cosets for every proper subgroup of Z0Z_0Z0​.

Write D(A0)D(A_0)D(A0​) for the maximum absolute determinant of ddd generator columns, and set ΔZ(A)=D(A0)/[Zd:Z0]\Delta_Z(A)=D(A_0)/[\mathbb Z^d:Z_0]ΔZ​(A)=D(A0​)/[Zd:Z0​]. The factor ∣det⁡e∣|\det e|∣dete∣ in each real covolume cancels. For a given spanner bbb, det⁡(Λ)/det⁡(Z)=[Zd:⟨b⟩]/[Zd:Z0]\det(\Lambda)/\det(Z)=[\mathbb Z^d:\langle b\rangle]/[\mathbb Z^d:Z_0]det(Λ)/det(Z)=[Zd:⟨b⟩]/[Zd:Z0​]. The two exact coefficients are

2⋅3d⌈ΔZ(A)/∣A∣⌉+d,2⋅3d⌈det⁡(Λ)∣A∣det⁡(Z)⌉+d.2\cdot3^d\lceil\Delta_Z(A)/|A|\rceil+d,\qquad 2\cdot3^d\left\lceil\frac{\det(\Lambda)}{|A|\det(Z)}\right\rceil+d.2⋅3d⌈ΔZ​(A)/∣A∣⌉+d,2⋅3d⌈∣A∣det(Z)det(Λ)​⌉+d.

The finite determinant maximum is zero on the empty set; the theorems' positive dimension and coset condition exclude that case and ensure spanning. No sign, pointedness, origin-membership or unit-covolume assumption is added.

Definition code
import Mathlib
import Definitions.Def_RelatedSchedFPTAS796_Main_Lattice

set_option autoImplicit false

namespace RelatedSchedFPTAS796.Main.Supplement

open Finset

/-- Real conical hull, with real nonnegative coefficients, including the empty sum. -/
def cone {d : ℕ} (A : Finset (Fin d → ℝ)) : Set (Fin d → ℝ) :=
  {x | ∃ coeff : (Fin d → ℝ) → ℝ, (∀ a ∈ A, 0 ≤ coeff a) ∧ x = ∑ a ∈ A, coeff a • a}

/-- Additive monoid generated by A, with arbitrarily large nonnegative integer coefficients. -/
def semigroup {d : ℕ} (A : Finset (Fin d → ℝ)) : Set (Fin d → ℝ) :=
  {x | ∃ k : (Fin d → ℝ) → ℕ, x = ∑ a ∈ A, (k a : ℝ) • a}

/-- The coordinate map permits an arbitrary real full-rank lattice, not just rational points.
Every full-rank real lattice has such a presentation by taking Z=⊤ and e a basis isomorphism.
More generally det(e Z)=|det(e)|·[ℤ^d:Z], so all normalized determinant ratios cancel det(e). -/
def latticeImage {d : ℕ} (e : (Fin d → ℝ) ≃ₗ[ℝ] (Fin d → ℝ))
    (Z : AddSubgroup (Fin d → ℤ)) : Set (Fin d → ℝ) :=
  (fun z => e (toReal z)) '' (Z : Set (Fin d → ℤ))

noncomputable def generatorsImage {d : ℕ} (e : (Fin d → ℝ) ≃ₗ[ℝ] (Fin d → ℝ))
    (A : Finset (Fin d → ℤ)) : Finset (Fin d → ℝ) :=
  A.image (fun a => e (toReal a))

/-- Every proper sublattice, not merely lattice generation. Full-rank ambient Z is a separate
hypothesis on the theorems. The base quotient modL is used without a convention change. -/
def CosetCondition {d : ℕ} (Z : AddSubgroup (Fin d → ℤ)) (A : Finset (Fin d → ℤ)) : Prop :=
  ∀ Λ' : AddSubgroup (Fin d → ℤ), Λ' < Z → 2 ≤ (modL Λ' (A : Set (Fin d → ℤ))).ncard

/-- Absolute coordinate determinant of d vectors. -/
def absDet {d : ℕ} (b : Fin d → Fin d → ℤ) : ℕ :=
  (Matrix.det (fun i j => b j i)).natAbs

/-- Maximum absolute determinant, divided by ambient lattice covolume. The empty finite maximum
is 0; on the stated positive-dimensional coset-admissible instances A spans the ambient lattice.
Taking columns with repetition leaves the maximum unchanged. -/
noncomputable def deltaZ {d : ℕ} (Z : AddSubgroup (Fin d → ℤ))
    (A : Finset (Fin d → ℤ)) : ℝ :=
  let D : ℕ := (Finset.univ : Finset (Fin d → A)).sup (fun b => absDet (fun i => (b i).val))
  (D : ℝ) / (Z.index : ℝ)

/-- All lattice points of the entire translated real cone must be in the integer semigroup. -/
def ShiftCovers {d : ℕ} (Z : Set (Fin d → ℝ)) (A : Finset (Fin d → ℝ))
    (s : Fin d → ℝ) : Prop :=
  ∀ x ∈ Z, x - s ∈ cone A → x ∈ semigroup A

/-- Least natural diagonal threshold in ℕ∪{∞}. If no threshold qualifies, the infimum is ∞,
not 0; otherwise it is the true least qualifying natural. -/
noncomputable def diagonalFrobenius {d : ℕ} (Z : Set (Fin d → ℝ))
    (A : Finset (Fin d → ℝ)) : ℕ∞ :=
  ⨅ t : {t : ℕ // ShiftCovers Z A ((t : ℝ) • ∑ a ∈ A, a)}, (t.val : ℕ∞)

/-- Exactly 2·3^d·ceil(Δ_Z(A)/|A|)+d; ceiling is only around the ratio. -/
noncomputable def diagonalBound {d : ℕ} (Z : AddSubgroup (Fin d → ℤ))
    (A : Finset (Fin d → ℤ)) : ℕ :=
  2 * 3 ^ d * ⌈deltaZ Z A / (A.card : ℝ)⌉₊ + d

/-- Exactly 2·3^d·ceil(det(Λ)/(|A|det(Z)))+d for the given spanner.
In coordinate lattices det(Λ)=[ℤ^d:Λ], and both real covolumes have the same |det(e)| factor. -/
noncomputable def spannerBound {d : ℕ} (Z : AddSubgroup (Fin d → ℤ))
    (A : Finset (Fin d → ℤ)) (b : Fin d → Fin d → ℤ) : ℕ :=
  2 * 3 ^ d * ⌈(latticeGen (Set.range b)).index /
    ((A.card : ℝ) * (Z.index : ℝ))⌉₊ + d

end RelatedSchedFPTAS796.Main.Supplement
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.3, §1.1 lines 109–116; Theorem 1.4 p.4; Appendix B pp.26–27

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me