Real cones, integer semigroups and the true diagonal Frobenius threshold
DefinitionRelatedSchedFPTAS796_Main_Supplement_FrobeniusFor a finite real vector set , define the real cone and nonnegative integer semigroup by
Both contain the empty sum. A shift covers the ambient lattice if every with belongs to . The diagonal Frobenius number is the infimum, in , of the natural thresholds for which the shift covers . 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 , where is a finite-index subgroup of and is an arbitrary invertible real linear map applied to the standard integer embedding. The generators are the image of a finite integer set . 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 .
Write for the maximum absolute determinant of generator columns, and set . The factor in each real covolume cancels. For a given spanner , . The two exact coefficients are
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.
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