View PDF HTML (experimental)

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.

Submission history

From: Soren Riis [view email]
[v1] Sun, 8 Feb 2026 20:17:15 UTC (28 KB)
[v2] Tue, 1 Sep 2026 11:35:44 UTC (34 KB)