A Minimal Substitution Basis for the Kalmar Elementary Functions

Basic Information

• Paper ID: 2505.23787
• Title: A Minimal Substitution Basis for the Kalmar Elementary Functions
• Authors: Mihai Prunescu, Lorenzo Sauras-Altuzarra, Joseph M. Shunia
• Classification: math.LO (Mathematical Logic), cs.CC (Computational Complexity), cs.LO (Logic)
• Publication Date: May 2025, Revised October 2025
• Paper Link: https://arxiv.org/abs/2505.23787

Abstract

This paper demonstrates that the class of Kalmar elementary functions can be inductively generated from three fundamental operations: addition, integer modulo operation, and binary exponentiation, thereby improving upon previous results by Marchenkov and Mazzanti. The paper simultaneously establishes that the substitution basis defined by these three operations is minimal and discusses alternative substitution bases under arity constraints.

Research Background and Motivation

Problem Definition

The core problem addressed in this research is to identify the minimal substitution basis for the class of Kalmar elementary functions. Kalmar elementary functions are operations on natural numbers computable in iterated exponential time, constituting the E₃ class in the Grzegorczyk hierarchy.

Significance

1. Theoretical Importance: Kalmar elementary functions encompass the majority of naturally occurring operations on natural numbers in mathematics, including factorial functions, binomial coefficients, the nth prime function, Euler's totient function, and greatest common divisor.
2. Practical Value: A substantial portion of real-world computations can be faithfully modeled within the Kalmar elementary function class, as the corresponding code avoids unbounded recursion.
3. Historical Development: Since Rödding's 1964 proof that finitely many elementary operations suffice to form a substitution basis for Kalmar elementary functions, finding substitution bases composed of "simple" arithmetic operations has remained an important problem in the field.

Limitations of Existing Approaches

• Mazzanti (2002): Proved that ⟨x+y, x∸y, xy, ⌊x/y⌋, xʸ⟩ = E₃, containing five operations
• Marchenkov (2007): Established ⟨x+y, x mod y, x², 2ˣ⟩ = E₃, reducing to four operations

The objective of this paper is to further simplify this substitution basis.

Core Contributions

1. Main Result: Proves that ⟨x+y, x mod y, 2ˣ⟩ = E₃, reducing the substitution basis to three operations
2. Minimality Proof: Rigorously establishes that this substitution basis is minimal, i.e., removing any single operation prevents the generation of the complete E₃ class
3. Expressiveness Analysis: Demonstrates how to express truncated subtraction, multiplication, and integer division using these three basic operations
4. Arity-Constrained Bases: Discusses alternative substitution bases under different arity constraints, including unary Kalmar elementary function substitution bases composed solely of unary operations, as well as complete substitution bases consisting of a single binary operation

Detailed Methodology

Task Definition

Given a set of operations F on natural numbers N, define ⟨F⟩ as the closure of F∪C∪P under substitution, where C is the set of constant operations and P is the set of projection operations. F is called a substitution basis for G if ⟨F⟩ = G.

Core Technical Approaches

1. Expression of Squaring (Theorem 2)

The key insight exploits the algebraic identity:

x² = 2²ˣ mod (2ˣ + x)

Proof Strategy:

• Since (2ˣ + x) | (2ˣ - x)(2ˣ + x) = 2²ˣ - x²
• Therefore 2²ˣ ≡ x² (mod 2ˣ + x)
• Since 0 ≤ x² < 2ˣ + x, we have x² = 2²ˣ mod (2ˣ + x)

2. Expression of Truncated Subtraction (Theorem 3)

Using composite modulo operations:

x ∸ y = [(2^(x+y) + x) mod (2^(x+y) + y)] mod (2^(x+y) + x)

3. Expression of Integer Division (Theorem 4)

Through a complex modulo operation formula:

⌊x/y⌋ = [2^(x+1) · (x ∸ (x mod y))] mod (2^(x+1)y ∸ 1)

Minimality Proof Strategy

1. Proving x+y ∉ ⟨x mod y, 2ˣ⟩ (Theorem 5)

Lemma 1: If t(x) ∈ ⟨x mod y, 2ˣ⟩, then there exists a non-negative integer B such that for each non-negative integer a, either t(a) is a power of 2 or t(a) ≤ max(B,a).

Proof: Assume x+y ∈ ⟨x mod y, 2ˣ⟩, then x+1 ∈ ⟨x mod y, 2ˣ⟩. By Lemma 1, for sufficiently large a, a+1 should be a power of 2, which is clearly impossible.

2. Proving x mod y ∉ ⟨x+y, 2ˣ⟩ (Theorem 6)

Lemma 2: If t(x) ∈ ⟨x+y, 2ˣ⟩ is a non-constant function, then t(x) is strictly increasing.

Proof: x mod 2 is not strictly increasing, but if x mod y ∈ ⟨x+y, 2ˣ⟩, then x mod 2 should also be in it, a contradiction.

3. Proving 2ˣ ∉ ⟨x+y, x mod y⟩ (Theorem 7)

Lemma 3: If t(x) ∈ ⟨x+y, x mod y⟩, then t(x) < Ax+B for some non-negative integers A,B.

Proof: The growth rate of 2ˣ exceeds any linear function, making it impossible to belong to ⟨x+y, x mod y⟩.

Experimental Results and Analysis

Main Results

The primary results of this paper are theoretical, established through rigorous mathematical proofs:

1. Sufficiency: ⟨x+y, x mod y, 2ˣ⟩ = E₃
2. Necessity: The substitution basis is minimal
3. Completeness: All important arithmetic operations can be expressed

Counterexample Analysis

The paper also proves that certain seemingly reasonable sets cannot form a substitution basis for E₃:

• ⟨2ˣ, x mod y, 2ˣ⟩ ⊈ E₃ (Theorem 8)
• ⟨x mod y, x+1, 2ˣ⟩ ⊈ E₃ (Theorem 9)
• ⟨x mod y, x∸y, 2ˣ⟩ ⊈ E₃ (Corollary 3)

Special Cases

The paper raises an open question: Does ⟨x+y, ⌊x/y⌋, 2ˣ⟩ equal E₃?

Related Work

Historical Development

1. Rödding (1964): First proved that finitely many elementary operations suffice to form a substitution basis
2. Marchenkov (1980): Proved ⟨x+1, ⌊x/y⌋, xʸ, φ(x,y)⟩ = E₃
3. Mazzanti (2002): Established ⟨x+y, x∸y, xy, ⌊x/y⌋, xʸ⟩ = E₃
4. Marchenkov (2007): Improved to ⟨x+y, x mod y, x², 2ˣ⟩ = E₃

Contribution of This Paper

By eliminating the squaring operation, this paper further simplifies the substitution basis to three operations and proves its minimality.

Conclusions and Discussion

Main Conclusions

1. Proves that ⟨x+y, x mod y, 2ˣ⟩ is the minimal substitution basis for the Kalmar elementary function class
2. Establishes explicit formulas for expressing other important arithmetic operations using these three basic operations
3. Provides general methods for determining whether certain operation sets cannot form a substitution basis

Limitations

1. Open Questions: The status of ⟨x+y, ⌊x/y⌋, 2ˣ⟩ remains undetermined
2. Practical Applicability: Although theoretically minimal, expressing certain functions may require complex formulas
3. Computational Complexity: Some constructions in the paper may result in high computational complexity

Future Directions

1. Resolve whether ⟨x+y, ⌊x/y⌋, 2ˣ⟩ equals E₃
2. Investigate optimal substitution bases under different computational models
3. Explore substitution bases for higher levels of the Grzegorczyk hierarchy

In-Depth Evaluation

Strengths

1. Theoretical Rigor: Proofs are rigorous with clear logical structure
2. Optimality of Results: Achieves the minimal substitution basis known in the literature
3. Technical Innovation: Provides clever algebraic constructions for expressing complex operations
4. Completeness: Proves not only sufficiency but also rigorously establishes necessity

Weaknesses

1. Limited Practical Utility: Some constructions are overly complex with limited practical application value
2. Unresolved Questions: Important theoretical problems remain open
3. Computational Efficiency: Insufficient discussion of computational complexity of proposed constructions

Impact

1. Theoretical Contribution: Holds important status in recursive function theory and computational complexity theory
2. Methodological Value: Proof techniques can be applied to similar problems
3. Completeness: Essentially resolves the classical problem of finding the minimal substitution basis for Kalmar elementary functions

Applicable Scenarios

1. Theoretical Research: Research in recursive function theory and computational complexity theory
2. Formal Verification: Scenarios requiring work within restricted arithmetic systems
3. Teaching: Serves as a classical example for computational theory courses

References

This paper cites key literature in the field, including original work by Grzegorczyk, important contributions by Marchenkov and Mazzanti, and other research by the authors in related areas. Particularly noteworthy is Emil Jeřábek's contribution to certain results, reflecting the collaborative nature of research in this field.