🔢 mathematics

An Elementary Analysis of the Prime Partition Function

This paper presents a short, elementary proof establishing the asymptotic formula $\log pp(n) \sim 2\pi\sqrt{\frac{n}{3\log n}}$ for the prime partition function, offering a simpler alternative to existing complex derivations while extending to related problems.

Original authors: Asaf Cohen Antonir, Asaf Shapira

Published 2026-06-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Asaf Cohen Antonir, Asaf Shapira

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 you have a giant pile of $n$ identical LEGO bricks. Your goal is to build a tower using these bricks, but there's a rule: you can only use specific types of bricks.

The Standard Game: You can use any brick size (1, 2, 3, 4...). This is the classic "partition problem."
The Prime Game: You can only use bricks with prime sizes (2, 3, 5, 7, 11...). This is the "Prime Partition" problem, the main focus of this paper.
The Power Game: You can only use bricks whose sizes are perfect powers (like $2^2=4$ , $3^2=9$ , or $2^3=8$ ).
The 3D Game: Instead of a single tower, you are building a 3D block structure where the layers must get smaller as you go up and out. This is the "Plane Partition" problem.

The question mathematicians have asked for over a century is: As the pile of bricks ( $n$ ) gets huge, how many different ways can you build these structures?

The answer is a number so astronomically large that it's impossible to write down. So, instead of counting the exact number, mathematicians look at the logarithm of that number. Think of the logarithm as a "zoom-out lens." It compresses the massive number down to a manageable size so we can see the pattern of how fast it grows.

The Big Discovery

The authors of this paper, Asaf Cohen Antonir and Asaf Shapira, wanted to find the pattern for the Prime Game (and the others).

Historically, finding these patterns was like trying to climb a mountain using a complex, dangerous, and very long technical route. The old proofs required heavy machinery and took many pages of dense math.

This paper's main achievement is a "short, elementary recipe."
The authors show that you don't need the heavy machinery. You can use a simple, three-step "kitchen recipe" to get the correct answer (specifically, the growth rate of the logarithm) for these problems.

The "Three-Step Recipe"

The paper explains that for all these different games, the solution follows the same three steps:

The Recursive Step (The "Domino Effect"):
Imagine you want to build a tower of size $n$ . The authors show that you can figure this out by looking at smaller towers. If you take a specific brick (say, a prime number $p$ ) and put it in your tower, you are left with a smaller problem: how to build a tower of size $n-p$ . They create a formula that links the big problem to a sum of all these smaller problems. It's like saying, "To know how many ways to build a 100-story tower, just add up the ways to build 98-story, 97-story, etc., towers."
The Bounding Step (The "Safety Net"):
Once they have that sum, it's still messy. The authors use a clever trick to say, "We don't need the exact sum. We just need to know that the answer is less than (or greater than) a specific, simpler mathematical curve." They replace the messy sum with a smooth, predictable function that acts as a ceiling (upper bound) or a floor (lower bound).
The Calculation Step (The "Final Tally"):
Finally, they calculate that smooth curve. Because the curve is simple, they can solve it easily. The result tells them exactly how the number of ways grows as $n$ gets bigger.

What They Found

Using this simple recipe, they confirmed the growth rates for several famous problems:

Prime Partitions: They proved that the number of ways to write $n$ as a sum of primes grows roughly like $e^{2\pi \sqrt{n / (3 \log n)}}$ . In plain English: The number of ways explodes very fast, but the "logarithm" of that number grows like the square root of $n$ divided by the log of $n$ .
Power Partitions: They found similar growth patterns for sums of powers (like squares or cubes).
Plane Partitions: They applied the same logic to the 3D block structures, confirming how fast those numbers grow.

Why This Matters

The paper doesn't claim to find a new number that no one knew before. Mathematicians like Hardy and Ramanujan already knew the answers roughly a century ago.

The value of this paper is the method.

Old Way: "Here is a 50-page proof using complex analysis and deep theorems to show you the answer."
New Way: "Here is a 3-step, high-school-level algebra recipe that gets you the same answer in a fraction of the space."

The authors emphasize that while their method doesn't give the most precise decimal points (the "state of the art" precision), it gets the correct shape of the growth curve. It proves that you can understand these massive, complex counting problems using simple, logical steps rather than heavy, technical tools.

Summary

Think of this paper as a guide showing that you can solve a complex puzzle using a simple, universal tool. Instead of needing a master key for every different lock (Prime, Power, 3D), the authors show that one simple, elementary "skeleton key" (the three-step recipe) can open them all and reveal the same underlying pattern.

Problem Statement
The paper addresses the asymptotic behavior of restricted partition functions, specifically focusing on the number of ways to write an integer $n$ as a sum of elements from a specific set $A$ . The primary object of study is $pp(n)$, the number of partitions of $n$ into prime numbers. The authors aim to determine the asymptotic behavior of $\log pp(n)$ as $n \to \infty$ . While sharper estimates for this and related functions (such as partitions into $d$ -th powers or plane partitions) are known, existing proofs rely on highly involved, lengthy, and non-elementary analytic techniques. The paper seeks to provide a "short, elementary recipe" to derive the correct asymptotic behavior of the logarithm of these functions, even if it does not yield the state-of-the-art precision of the full partition function itself.

Methodology
The authors adapt an elegant inductive argument originally used by Erdős to prove a slightly weaker version of the Hardy–Ramanujan formula for the standard partition function. The methodology follows a consistent three-step process applied to various counting functions:

Recursive Formula (R1): Establish a recursive formula for the relevant partition function. For standard restricted partitions, this utilizes a known identity (Lemma 3.1) derived via double counting. For plane partitions, the authors rely on a recursion formula by MacMahon (Lemma 2.1), noting that while the derivation of MacMahon's lemma is non-elementary (using generating functions), the subsequent steps can be elementary.
Bounded Summation (R2): Utilize the recursive formula to bound the partition function by a sum of the form $\sum_{k=1}^\infty \sum_{a \in A} \phi(a)e^{-\psi(a,k)}$ . This step involves applying the induction hypothesis and elementary inequalities (such as Taylor expansions or convexity arguments) to separate the exponential growth term from the summation.
Elementary Evaluation (R3): Evaluate the resulting double sums using elementary calculus and number-theoretic estimates (such as the Prime Number Theorem for the prime partition case) to conclude the proof.

The paper distinguishes between proving upper bounds and lower bounds. While the upper bounds are often straightforward applications of the recipe, the lower bounds require more careful handling of inequalities and error terms, particularly in the case of partitions into primes.

Key Contributions and Results
The paper presents three main theorems establishing the asymptotic behavior of the logarithm of specific partition functions:

Partitions into Powers (Theorem 1.1): For $p_d(n)$ , the number of partitions of $n$ into $d$ -th powers (where $d > 0$ ), the authors prove:
$\log p_d(n) \sim c_d \cdot n^{1/(d+1)}$
where $c_d$ is a constant involving the Gamma and Riemann zeta functions. The proof is provided for integer $d$ first, then generalized to non-integer $d$ .
Partitions into Primes (Theorem 1.2): The central result of the paper concerns $pp(n)$, the number of partitions into primes. The authors prove:
$\log pp(n) \sim 2\pi \sqrt{\frac{n}{3 \log n}}$
This recovers the asymptotic behavior first established by Hardy and Ramanujan. The proof is noted as the longest in the paper but remains elementary. The authors provide detailed proofs for both the upper and lower bounds to demonstrate the efficacy of their method for establishing lower bounds.
Plane Partitions (Theorem 1.3): For $PL(n)$, the number of plane partitions of $n$ , the authors prove:
$\log PL(n) \sim (27 \cdot \zeta(3)/4)^{1/3} \cdot n^{2/3}$
The authors note that while the recursion used (MacMahon's) is non-elementary, the implementation of steps (R2) and (R3) to derive the asymptotic logarithm is elementary.

Significance and Claims
The paper claims significance not in discovering new asymptotic values (as these were previously known), but in the simplicity and accessibility of the proofs. The authors emphasize that:

The proofs are "significantly shorter" than existing literature.
The approach is "elementary," avoiding the complex analytic machinery (such as detailed generating function analysis or saddle-point methods) typically required for these results.
The method is versatile, easily adapting to yield similar asymptotic estimates for several related, extensively studied problems (powers, primes, plane partitions).
The paper serves as a demonstration that the correct asymptotic behavior of the logarithm of these functions can be derived without the "highly non-trivial arguments" usually associated with them.

The authors remain modest regarding the precision of their results, acknowledging that their proofs do not yield the "state of the art estimations" (which include lower-order terms) but successfully capture the leading-order asymptotic behavior of the logarithm. They also note that for higher-dimensional partitions, the lack of a "nice" generating function formula currently limits the state of the art to the order of magnitude of the logarithm, a gap their method does not currently bridge.

The Big Discovery

The "Three-Step Recipe"

What They Found

Why This Matters

Summary

More like this