Completely Additive Height Functions: Profile Laws, Matula Bounds, and Inverse Growth

Abstract

The height (H(n)) of an integer (n) is classically the number of iterations of Euler's totient function required to reach (1). H. N. Shapiro showed that a modification of this function is completely additive. We study completely additive height functions with finite prime fibers. Their prime-height profile (π_k) determines the height multiplicities (N_k) through the weighted-multipartition identity (\sum_k N_k q^k=\prod_j(1-q^j)^{-π_j}), and conversely every profile containing infinitely many primes is realizable. We introduce iteratively defined heights encompassing Shapiro-type totient heights and the Matula height. For the Matula height, we give purely number-theoretic proofs of the classical Gutman-Ivi'c extremal bounds, thereby answering their question whether the maximal bound can be derived without recourse to the rooted-tree interpretation. Using Meinardus' theorem in its full form, we prove a conditional inverse-growth law: if (Π_k\sim Ck^α), then (\log N_k\sim C_2 k^{α/(α+1)}), with an explicit constant. We also derive average-order results for a canonical sequential realization and report computations for the Shapiro height beyond the polynomial regime.

arXiv commentAccepted version. To appear in Integers