Short answer: Flex is far smaller than the class of primitive recursive (PR) functions. In particular, every Flex-function has a fixed, finite “exponential height,” so a standard PR function such as tetration n ↦ 2↑↑n (defined by g(0)=1, g(n+1)=2^{g(n)}) is not in Flex. Exponentiation is also not superfluous: without it, Flex collapses to at most polynomial growth and cannot define, e.g., n!.
What “can be made from +, −, ×, ÷, ^, ⌊·⌋” precisely means
- Interpret Flex as the set of functions f: N^k → N obtained by evaluating a single term built from variables and integer constants using the operations +, −, ×, ÷, exponentiation, and floor, with the obvious arithmetic meanings (÷ as rational division, then possibly composed with floor). You may nest these operations finitely many times, but there is no recursion, iteration, or quantification—just a single closed expression (a term).
Two basic facts
- Bounded exponential height. Fix any Flex-term T(x). Let h(T) be the maximum number of nested exponentiations in T’s parse tree (e.g., h(n+3)=0; h(2^n)=1; h(2^{2^n})=2; etc.). Then there is a polynomial p and a constant C such that, for all sufficiently large n,
T(n) ≤ E_{h(T)}(p(n)),
where E_0(t)=t and E_{k+1}(t)=2^{E_k(t)}. In other words, each individual Flex-term grows at most like a tower of twos of fixed height h(T) with a polynomial on top.
Proof sketch by structural induction on T:
- Base (constants, variables): polynomial bound.
- +, −, ×, ÷, ⌊·⌋: do not increase exponential height; they preserve a bound of the form E_h(polynomial). For h=0, you remain in polynomial bounds; for h≥1, E_h is so rapidly growing that sums, products, quotients by nonzero terms, and floors are still ≤ E_h of a (different) polynomial.
- Exponentiation u^v: increases the height by at most 1. If u ≤ E_h(p) and v ≤ E_h(q), then u^v ≤ E_{h+1}(r) for some polynomial r.
- Flex ⊊ Primitive Recursive. Consider g(0)=1, g(n+1)=2^{g(n)} (tetration). This is primitive recursive. But for any fixed h, E_h grows much slower than g: indeed, g(n) is essentially E_n(1). So no single fixed-height tower E_h can dominate g, hence no single Flex-term can equal g. Therefore Flex is strictly contained in PR.
Consequences and clarifications
-
Your conjecture “Flex = primitive recursive” is false (by the tetration counterexample). More broadly, Flex is contained in the class of elementary functions (Kalmár/Grzegorczyk E3), since “bounded exponential height” is the hallmark of elementary growth. Primitive recursive properly contains elementary.
-
MRDP (Matiyasevich–Robinson–Davis–Putnam) is not applicable here: MRDP shows that r.e. sets are existentially Diophantine, i.e., definable by ∃-quantified polynomial equations. Flex allows no quantifiers at all—only terms—so you cannot directly leverage MRDP to capture arbitrary PR predicates.
-
About your examples:
- mod, binomial coefficients, factorial, and the primality characteristic can indeed be encoded by clever closed-form identities using large parameters built from n (this is where exponentiation is extremely useful). These are nice illustrations that Flex is quite expressive despite having no recursion.
- However, such tricks do not simulate arbitrary bounded sums/products or general primitive recursion; they work in special cases where a closed-form identity exists.
-
Exponentiation is not superfluous:
- Without exponentiation, any term built from +, −, ×, ÷, ⌊·⌋ has at most polynomial growth (again by structural induction; ÷ and ⌊·⌋ do not increase degree, and × adds degrees). So functions like 2^n or n! cannot be defined without exponentiation.
- Your factorial construction crucially uses exponentials to manufacture parameters r, u that dwarf certain combinatorial error terms; without ^ you cannot do this.
What Flex really is
- Conceptually, Flex is the class of term-definable functions in the language {0,1,+,−,×,÷,^,⌊·⌋}. Each individual term has bounded exponential height, and the whole class is the union over all finite heights. This puts Flex well within the elementary functions and far below primitive recursive.
Takeaways
- Flex ⊆ elementary ⊊ primitive recursive.
- A concrete PR function not in Flex is g(n)=2↑↑n.
- Exponentiation is essential for many of your constructions (in particular, for factorial); without it the class is drastically weaker.
