Generalized digits (Definition A.1)
DefinitionLatticePrepro_Tables_DigitsLet (the base) and (the number of axes) be natural numbers. The bundle defines two functions.
- Value of an exponent vector (
digitVal): for ,
- Generalized digit vector (
gdigits): for , write with and , and let be the base- digits of . Then
Ordinary base- digits only describe numbers below . The generalized digits allow entries larger than , so that every order is the value of an exponent vector with small entries (Claim A.2). They index the interpolants that define the moment maps in Construction A.4 and the entries of the polynomial matrix in Definition A.5.
Formalization Note: Exponent vectors are functions Fin m → ℕ. Both functions are defined for all natural numbers, with Lean's conventions and ; the paper's standing assumptions and (which give ) appear as hypotheses of the lemmas about them. The monomials of Definition A.1 are not part of this bundle; they appear directly in the column sums of Construction A.4. The paper writes and for and .
import Mathlib
/-!
# Generalized digits (Definition A.1, Claim A.2)
Moment orders are written as exponent vectors `η : Fin m → ℕ` with
`val B η = ∑ h, η h * B ^ h`. The *generalized digit vector* of `k` is obtained by writing
`k = a · (B^m - 1) + b` with `0 ≤ b < B^m - 1` and taking `a · (B - 1)` plus the base-`B`
digits of `b`. It satisfies `val B (gdigits B m k) = k`, and for `k ≤ J · (B^m - 1)` all its
entries are at most `J · (B - 1)`.
-/
namespace LatticePrepro
/-- `val B η = ∑ h, η h * B ^ h`. -/
def digitVal (B : ℕ) {m : ℕ} (η : Fin m → ℕ) : ℕ := ∑ h : Fin m, η h * B ^ (h : ℕ)
/-- The generalized digit vector of `k` (Definition A.1). -/
def gdigits (B m k : ℕ) : Fin m → ℕ :=
fun h => (k / (B ^ m - 1)) * (B - 1) + (k % (B ^ m - 1)) / B ^ (h : ℕ) % B
end LatticePrepro