Let E denote the class of Kalmár elementary functions, and let langle x+y,operatornametdiv(x,y),2^x rangle denote the class of functions generated by substitution from addition, totalized integer division operatornametdiv, and base-two exponentiation. The problem asks whether langle x+y,operatornametdiv(x,y),2^x rangle=E; equivalently, whether every Kalmár elementary function can be represented by a term using only these three operations.

Kalmár elementary-function substitution-basis problem

The problem asks whether addition, integer quotient, and exponentiation by $2$ generate all Kalmár elementary functions. It was posed as an open problem in a 2025 preprint.

Known results

Mazzanti (2002) and Marchenkov (2007) gave earlier substitution bases, including one using addition, remainder, squaring, and exponentiation.
Prunescu, Sauras-Altuzarra, and Shunia (2025) removed squaring: $\langle x+y,\ x\bmod y,\ 2^x\rangle=\mathcal{E}$ , with all three operations indispensable.
Their Problem 15 asked whether $\langle x+y,\ \lfloor x/y\rfloor,\ 2^x\rangle=\mathcal{E}$ ; no solution was reported there.

October 2026 claimed disproof

Joseph M. Shunia's preprint On Integer-Division Bases for the Kalmár Elementary Functions claims a sparsity obstruction: the proposed basis cannot recover $\lfloor\log_b x\rfloor$ , integer remainder, or the input from $b^n$ . If correct, this gives a negative answer to the open basis question, but the result is unrefereed and no independent assessment was found.

Current status (as of October 2026): The integer-division basis question has a claimed negative solution, but the sparsity argument is not independently verified; the remainder-based minimal basis is established in the cited preprint.

Kalmár elementary-function substitution-basis problem

Primary source

Additional references

Progress summary

Solutions 0