🔢 mathematics

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

This paper investigates completely additive height functions with finite prime fibers, establishing their relationship with prime-height profiles via weighted-multipartition identities, providing number-theoretic proofs for Matula height bounds, and deriving conditional inverse-growth laws and average-order results using Meinardus' theorem.

Original authors: Hartosh Singh Bal

Published 2026-07-31

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Hartosh Singh Bal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a vast, infinite library where every single book has a unique number on its spine. Now, imagine a magical rule that lets you break any book down into its most basic, indivisible chapters—its "prime" chapters. In the world of mathematics, these prime chapters are the prime numbers (2, 3, 5, 7, 11, and so on), and the rule for breaking books down is called "factorization." Just as every book is made of a specific combination of chapters, every whole number is made of a specific combination of prime numbers.

Mathematicians love to ask: "How tall is a number?" In this story, the "height" of a number isn't how many digits it has, but how many steps it takes to break it all the way down to the very beginning. If you have a number like 12, you might break it into 3 and 4, then 4 into 2 and 2. If you keep applying a special "reduction" rule (like peeling an onion layer by layer), the height is the number of layers you had to peel to reach the core. This paper explores a specific type of height where the rules are "completely additive." Think of this like a game where the height of a team is simply the sum of the heights of all its players. If you know the height of every single prime number, you instantly know the height of every number in the universe. The big question the authors tackle is: If we know how many prime numbers exist at each specific "height," can we predict how many total numbers exist at that height? And conversely, if we see a pattern in the total numbers, can we figure out the pattern of the primes?

The Paper's Story: Mapping the Invisible Ladder

In this paper, the author, Hartosh Singh Bal, acts like an architect designing a new way to measure the "height" of numbers. He focuses on a special kind of height function where the rules are simple and additive: the height of a number is just the sum of the heights of its prime parts. The paper is built on a clever connection between these numbers and a concept called "multipartitions." Imagine you have a bag of colored blocks. If you have a certain number of red blocks, blue blocks, and green blocks, the number of ways you can stack them to reach a specific total height is a "partition." In this paper, the "blocks" are prime numbers, and the "colors" are their assigned heights. The author shows that if you know the "profile" (how many primes exist at height 1, height 2, height 3, etc.), you can mathematically calculate exactly how many total numbers exist at each height using a formula that looks like a giant, infinite product.

The paper makes three major discoveries, each like a different tool in a mathematician's toolbox:

First, the author proves that this connection is a two-way street. If you give him a list of how many primes are at each height (even if the list is random), he can build a valid height function that matches it. Conversely, if you have a height function, the list of prime heights completely determines the number of integers at each level. This turns a complex number theory problem into a combinatorial puzzle about stacking blocks.

Second, the paper tackles a famous puzzle involving "Matula numbers." These are numbers that correspond to tree-like structures (rooted trees). For a long time, mathematicians knew the smallest and largest numbers at a specific height, but their proofs relied on drawing pictures of trees. The author provides a brand-new, purely number-based proof for these limits. He shows that you don't need to look at the trees at all; you can deduce the largest and smallest numbers just by looking at the recursive rules of the primes and using standard estimates for how big prime numbers get. This answers a long-standing question about whether these limits could be found without the "tree" interpretation.

Third, the paper explores what happens when the number of primes at each height grows in a predictable, polynomial way (like $k^2$ or $k^3$ ). Using a powerful mathematical tool called Meinardus' theorem, the author derives a "law of inverse growth." He shows that if the prime heights grow in a certain smooth pattern, the total number of integers at a given height grows in a very specific, stretched-exponential way. However, he is careful to note that this law is "conditional." It only works if the primes are distributed evenly enough to avoid "lattice traps" (where primes only appear at even heights, for example). If that condition isn't met, the formula breaks.

The paper also dives into the "Shapiro height," a specific type of height based on the Euler totient function (a famous number-crunching tool). Here, the author moves from pure theory to computer experiments. He calculates the first 17 layers of this height structure and finds some fascinating, though not yet proven, patterns. The data suggests that the number of integers at each height grows exponentially (roughly multiplying by 2.3 each time). Even more intriguingly, the sizes of the prime numbers at a fixed height seem to follow a "bell curve" when you look at their logarithms. This means that if you pick a random prime at height 17, its size is likely to be close to a specific average, with fewer primes being extremely small or extremely large. The author proposes that these primes might follow a "height-wise central limit law," but he emphasizes that this is currently just a strong numerical suggestion based on simulations, not a proven theorem.

Finally, the paper distinguishes between two "regimes" of growth. In the "polynomial regime," where prime counts grow slowly and steadily, the author can predict the behavior of the numbers with high precision. In the "exponential regime," where prime counts explode rapidly (like in the Matula or Shapiro examples), the standard tools break down, and the behavior becomes much wilder and harder to pin down. The paper concludes by suggesting that while we can map the "vertical" growth (how many numbers are at each height), the "horizontal" structure (how the primes are distributed within that height) holds secrets that the simple counting formulas cannot see, leaving plenty of room for future exploration.

Technical Summary: Completely Additive Height Functions

Problem Statement
The paper investigates a class of functions $H: \mathbb{N} \to \mathbb{N}_0$ termed "height functions," defined as completely additive functions where $H(1)=0$ , $H(p) \ge 1$ for all primes $p$ , and the set of primes at any fixed height $n$ is finite. The central problem is to understand the relationship between the prime-height profile $\pi_k = \#\{p : H(p) = k\}$ and the height multiplicities $N_n = \#\{m : H(m) = n\}$ . While classical examples like ordinary partitions ( $\pi_k \equiv 1$ ) and plane partitions ( $\pi_k = k$ ) are well-understood, the paper seeks to generalize these relationships to recursive constructions (such as Matula numbers and Shapiro-type totient heights) and to establish analytic laws governing the growth of $N_n$ based on the asymptotic behavior of $\pi_k$ .

Methodology
The paper employs a dual approach combining combinatorial number theory and analytic asymptotics:

Combinatorial Framework: The author establishes a bijection between integers and multipartitions. By complete additivity, the generating function for height multiplicities is identified as a weighted multipartition Euler product:
$\sum_{n \ge 0} N_n q^n = \prod_{k \ge 1} (1 - q^k)^{-\pi_k}$
This identity allows the translation of number-theoretic properties of $H$ into partition-theoretic problems.
Recursive Constructions: The paper analyzes heights defined iteratively on primes via $H(p_i) = H(f(i)) + 1$ , where $p_i$ is the $i$ -th prime. This framework encompasses the Matula height ( $f(i)=i$ ) and Shapiro-type heights derived from iterates of Euler's totient function.
Analytic Asymptotics: To derive growth laws for $N_n$ , the paper utilizes Meinardus' Theorem. This requires analyzing the Dirichlet series associated with the profile, $B_H(s) = \sum \pi_k k^{-s}$ . The analysis is conditional on the profile satisfying the theorem's hypotheses, particularly the "minor-arc" condition which rules out lattice obstructions (e.g., profiles supported only on even integers).
Average Order Reduction: For the average order of $H(n)$ , the paper reduces the summatory function $F(x) = \sum_{n \le x} H(n)$ to sums over prime values using standard techniques for additive functions.

Key Contributions and Results

Canonical Correspondence: The paper formalizes the equivalence between completely additive height functions with finite prime fibers and weighted multipartitions. It proves that any sequence of non-negative integers $(\pi_k)$ with infinite sum can be realized as the prime-height profile of some height function.
Number-Theoretic Proofs of Matula Bounds:
- The paper provides purely number-theoretic proofs for the extremal bounds of Matula numbers (integers at a fixed height in the Matula structure).
- Maximal Bound: It proves that the largest integer at height $n$ is $P(n)$ , defined recursively by nested prime indices ( $P(n) = p_{P(n-1)}$ ), resolving a question posed by Gutman and Ivić regarding whether these bounds could be derived without recourse to rooted-tree graph theory.
- Minimal Bound: It derives the unique smallest integer at height $n$ using only complete additivity and explicit bounds for the $k$ -th prime, again avoiding tree-theoretic arguments.
Conditional Inverse-Growth Law:
- The paper establishes a conditional asymptotic law for the growth of $N_n$ . If the cumulative profile $\Pi(x) = \sum_{k \le x} \pi_k$ grows as $C x^\alpha$ , and the profile satisfies the full hypotheses of Meinardus' theorem (including the minor-arc condition), then:
  $\log N_n \sim C_2 n^{\alpha/(\alpha+1)}$
  where $C_2$ is an explicit constant depending on $C, \alpha$ , and the Riemann zeta function.
- This result places ordinary partitions ( $\alpha=1$ ) and plane partitions ( $\alpha=2$ ) into a unified analytic framework.
Average Order in the Polynomial Regime:
- For profiles with polynomial growth ( $\Pi(x) \sim C x^\alpha$ ), the paper defines a "canonical sequential realization" where prime heights are non-decreasing with the prime index.
- It derives the order of magnitude for the average order of this canonical height: $F(x) \asymp x^{1+1/\alpha} / (\log x)^{1+1/\alpha}$ .
Squarefree Variants: The theory is extended to squarefree height functions (radical classes), where the Euler product changes to a distinct-part product $\prod (1+q^k)^{\pi_k}$ . The paper presents examples where recursive rules on squarefree representatives lead to finite sets of primes (Shapiro-Erdős type) or sparse, continuing sequences (Dedekind-type).
Computational Observations on Shapiro Height:
- The paper reports computational data for the modified Shapiro totient height.
- It observes that $N_h$ and the number of primes at height $h$ ( $P_h$ ) exhibit exponential growth ( $N_h \sim B^h$ ).
- It conjectures a "height-wise central limit law," suggesting that $\log p$ for primes at a fixed height $h$ follows a Gaussian distribution with mean $\mu h$ and variance $\sigma^2 h$ .
- These observations suggest that recursive heights can produce behavior outside the "universal polynomial picture," entering an exponential regime where standard partition asymptotics may not apply directly.

Significance and Claims
The paper claims to unify the study of height functions with the theory of multipartitions, providing a "canonical" organizing principle for recursive constructions. Its primary significance lies in:

Answering a specific open question: Providing the first purely number-theoretic derivation of the Gutman–Ivić extremal bounds for Matula numbers, independent of their graph-theoretic interpretation.
Establishing a conditional inverse-growth principle: Linking the polynomial growth of the prime-height profile directly to the stretched-exponential growth of the height multiplicities via Meinardus' theorem.
Highlighting limitations: Demonstrating that while the profile determines the multiplicities, it "forgets" arithmetic structure (congruences, correlations). The paper notes that recursive definitions (like Shapiro's) can impose strong arithmetic constraints that lead to behavior (exponential growth, non-lattice profiles) not captured by simple polynomial profile models.

The paper remains modest regarding the Shapiro height results, presenting them as empirical evidence and conjectures rather than proven theorems, noting that the "fine structure" of such heights lies beyond the designed profile setting treated in the main analytic sections.

Technical Summary: Completely Additive Height Functions

More like this