A Minimal Substitution Basis for the Kalmar Elementary Functions

2025/05/24 by Prunescu, Mihai, Sauras-Altuzarra, Lorenzo, Shunia, Joseph M. · 1 citation
#03B70 #03D20 (Primary) #03D55 #68Q15 (Secondary) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2505.23787

Abstract

We show that the class of Kalmar elementary functions can be inductively generated from the addition, the integer remainder, and the base-two exponentiation, hence improving previous results by Marchenkov and Mazzanti. We also prove that the substitution basis defined by these three operations is minimal. Furthermore, we discuss alternative substitution bases under arity constraints.

Citations

• On modular representations of C-recursive integer sequences
• On arithmetic terms expressing the prime-counting function and the n-th prime
• Arithmetic-Term Representations for the Greatest Common Divisor
• On other two representations of the C-recursive integer sequences by terms in modular arithmetic
• On the representation of C-recursive integer sequences by arithmetic terms

Cited by

• Elementary closed-forms for non-trivial divisors

Related

• On Finitely Stable Additive Bases
• Slim normal Bases and Basefield Transforms
• Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions, dissertation
• Critical bases for ternary alphabets
• Looking for good Hofmeister and Braunschadel bases