Term Coding and Dispersion: Exact and Asymptotic Decision Problems
Søren Riis
cs.IT
Feb 8, 2026 · v2
TL;DR
The principal results on dispersion decision problems (threshold decidability, spectrum properties, scalar-linear criteria) are formalised and machine-checked in Lean 4 against Mathlib.
Abstract
Let t be a tuple of r terms that, under an interpretation on an n-element alphabet A, defines a map from k-tuples over A to r-tuples over A. We study the decision theory of its maximum image size, separating exact perfect dispersion from asymptotic rate. Building on the term-cut theorem of Riis and Gadouleau, we prove that every eventual threshold strictly between consecutive integer powers is decidable in polynomial time. More precisely, if a threshold is eventually greater than n to the power d and grows strictly more slowly than n to the power d plus one, then the maximum image size eventually meets that threshold exactly when the term-cut exponent is at least d plus one. For the exact problem, we introduce the perfect-alphabet spectrum and prove that it is multiplicatively closed, that a nonempty spectrum forces full rate, and that the converse fails. We completely characterize the one-output case. On square instances, perfect dispersion is precisely finite square term bijectivity. We give explicit linear-size padding reductions from three-dimensional square bijectivity to perfect dispersion for every fixed output dimension of at least three. We also characterize scalar-linear witnesses by a determinant polynomial, obtaining decidability over fixed finite fields, over extensions of a fixed characteristic, and over arbitrary finite fields. General square bijectivity remains open. The principal mathematical results have been machine-checked in Lean.
Problem
A tuple of r terms interpreted on an n-element alphabet defines a map from k-tuples to r-tuples. The question is how to decide properties of its maximum image size (dispersion), separating exact perfect dispersion (surjectivity) from asymptotic rate.
Approach
The work builds on the term-cut theorem of Riis and Gadouleau to analyse eventual thresholds between consecutive integer powers of n. For the exact problem it introduces the perfect-alphabet spectrum and gives padding reductions from three-dimensional square bijectivity to perfect dispersion. Scalar-linear witnesses are characterised via a determinant polynomial. The principal results are machine-checked in Lean 4 with Mathlib.
Results
Every eventual threshold strictly between consecutive integer powers is decidable in polynomial time via the term-cut exponent. The perfect-alphabet spectrum is multiplicatively closed, and a nonempty spectrum forces full rate but not conversely. The one-output case is fully characterised, scalar-linear witnesses are decidable over finite fields, and general square bijectivity remains open.