On Integer-Division Bases for the Kalmár Elementary Functions
Abstract
Prunescu, Sauras-Altuzarra, and Shunia asked whether addition, totalized integer division, and base-two exponentiation form a substitution basis for the Kalmár elementary functions. We answer this problem negatively, even after adjoining multiplication. On independent powers of two, every fixed term built from addition, multiplication, and integer division takes only polylogarithmically many distinct values below a given bound, and the same restriction survives arbitrary nesting of 2x. No such term recovers n from 2n, so neither ⌊log2 x⌋ nor integer remainder is representable. The obstruction is not special to the base two. For every fixed integer b≥ 2, the same sparsity bound holds with constants independent of b, and ⟨ x+y,⌊ x/y⌋,bx⟩ remains a proper subclass of the elementary functions. Variable exponentiation reverses the conclusion: addition, integer division, and xy do form a substitution basis, ⟨ x+y, ⌊ x/y⌋, xy⟩=ℰ . Once the base may depend on the input, integer remainder and truncated subtraction become representable. The incomplete base-two class is nevertheless complete for truth values. Every elementary characteristic function belongs to it, as does every elementary function with a fixed finite range.
Related
- On the gauge invariant boundary condition in open XXZ chains: SoV bases, elementary blocks and overlaps
- Prime Plus a Non-Square-Free Integer: An Elementary Approach
- Estimates of Lucas series and expansions in non-integer bases
- Stacked-bases Properties, maximal ideals and polynomial closures of Rings of Integer-Valued Polynomials
- Integer group determinants for the elementary abelian group of order 49
BibTeX
@misc{shunia2026integerdivision,
title = {{On Integer-Division Bases for the Kalmár Elementary Functions}},
author = {Joseph M. Shunia},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09975},
eprint = {2610.09975},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09975},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - On Integer-Division Bases for the Kalmár Elementary Functions
AU - Joseph M. Shunia
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09975
UR - https://arxiv.org/abs/2610.09975
AB - Prunescu, Sauras-Altuzarra, and Shunia asked whether addition, totalized integer division, and base-two exponentiation form a substitution basis for the Kalmár elementary functions. We answer this problem negatively, even after adjoining multiplication. On independent powers of two, every fixed term built from addition, multiplication, and integer division takes only polylogarithmically many distinct values below a given bound, and the same restriction survives arbitrary nesting of 2^x. No such term recovers n from 2^n, so neither ⌊log_2 x⌋ nor integer remainder is representable. The obstruction is not special to the base two. For every fixed integer b≥ 2, the same sparsity bound holds with constants independent of b, and ⟨ x+y,⌊ x/y⌋,b^x⟩ remains a proper subclass of the elementary functions. Variable exponentiation reverses the conclusion: addition, integer division, and x^y do form a substitution basis, ⟨ x+y, ⌊ x/y⌋, x^y⟩=ℰ . Once the base may depend on the input, integer remainder and truncated subtraction become representable. The incomplete base-two class is nevertheless complete for truth values. Every elementary characteristic function belongs to it, as does every elementary function with a fixed finite range.
ER -