Integer partitions detect the primes
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Integer partitions detect the primes".
Emmy: Here's the gist of the paper. Integer partitions detect prime numbers in an unexpected way by showing that primes are solutions to special equations in partition functions.
Ada: This research demonstrates a deep connection between additive number theory, specifically integer partitions, and the distribution of prime numbers through partition theoretic equations.
Emmy: Detection of Primes via Partition Functions The paper establishes that for an integer n ≥ 2, n is prime if and only if certain expressions involving MacMahon’s partition functions M a(n) equal zero.
Ada: Specifically, the expression (3n cubed − 13n squared + 18n − 8)M 1(n) + (12n squared − 120n + 212)M 2(n) − 960M 3(n) vanishes if and only if n is prime.
Paper summary: Ada: We've covered the main thesis of this paper called "Integer partitions detect the primes," which is that primes satisfy certain partition function equations. Now we’re going to look at how they frame this idea more broadly.
Emmy: The paper establishes that for an integer n greater than two, n is prime if and only if certain expressions involving MacMahon’s partition functions equal zero >
Ada: Specifically, it gives us an example with three partition functions: three n cubed minus thirteen n squared plus eighteen n minus eight times M sub one of n plus twelve n squared minus one hundred twenty n plus two hundred twelve times M sub two of n minus nine hundred sixty times M sub three of n = zero > <ref:2405.06451#pg1>
Kolya: It’s interesting that they specify these exact coefficients. What about the general case, the MacMahonesque functions? They mention there are infinitely many prime detecting equations with constant coefficients involving MacMahonesque partition functions >
Emmy: They define natural generalizations, M sub a of n, and establish that arbitrary convolutions of these MacMahon series are always linear combinations of such functions with constant coefficients >
Ada: This means the connection isn't limited to just the basic partition functions; it extends to this wider class, which is really interesting because it suggests a more fundamental algebraic structure underlies this detection >
Kolya: Does this mean we can use these MacMahonesque functions to predict primes in some kind of probabilistic sense, or is this purely deterministic based on the equation vanishing? I'm wondering about the nature of these solutions >
Emmy: The paper relies heavily on quasimodular forms, which are characterized by their Fourier expansions and properties related to the q-differential operator D >
Ada: That’s where it gets really structural. They show that quasimodular forms in a specific space, denoted as Omega, are those whose Fourier coefficients b sub n of f satisfy b sub n of f greater than or equal to zero for positive n and vanish if and only if n is prime >
Kolya: So, the structure itself encodes the primality condition. That’s quite elegant. How does that relate back to the initial partition functions we were talking about? >
Ada: It connects back by relating these partition functions to generating series U sub a of q and their quasi-shuffle algebra Zq >
Emmy: The space Zq is shown to be a differential subalgebra of Q
[q: ] containing M f, which allows the product of any two MacMahon series to be computed recursively using the quasi-shuffle product >
Kolya: That recursion sounds like something that could govern how these functions interact, maybe telling us about the growth rates of these partition counts or something similar >
Conclusion: Ada: So, to wrap up this paper "Integer partitions detect the primes," we see that primes are solutions to a whole family of equations within MacMahonesque partition functions.
Emmy: The authors prove that there are infinitely many such prime detecting equations with constant coefficients, which means this detection mechanism is very general and applies across the wider class of MacMahon series >
Kolya: What’s the real-world implication here, beyond just proving a mathematical link? If this connection between partitions and primes is this deep, what does that suggest about our understanding of number theory overall? >
Ada: It suggests that there is a deep, structural relationship between additive number theory—the way we count partitions—and the distribution of prime numbers through these specific algebraic tools >
Emmy: The paper characterizes the space E intersect Omega as being generated by forms D sub n H sub k for n greater than or equal to zero and k greater than or equal to six >
Kolya: So, it seems they’ve managed to completely describe the set of quasimodular forms that detect primes, confirming that these specific combinations of Eisenstein series are all there >
Ada: It confirms the linear independence and structure of these spaces through dimension calculations >
Emmy: They also showed that all quasimodular forms are linear combinations of the symmetrized MacMahon U sym sub a of q, which adds up to a complete account >
William Craig, Jan-Willem Van Ittersum, Ken Ono
European Research Council · SFB/TRR 191
math.NT, math.CO
Submitted: 2024-05-10
Updated: 2024-07-10
Comments: Revision that correct a few minor typos caught by referees
Journal ref: Proc. Natl. Acad. Sci. USA 121 (2024), no. 39
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 82/100
The gist: Integer partitions detect prime numbers in an unexpected way by showing that primes are solutions to special equations in partition functions.
Key concepts
- MacMahon's Partition Functions (M_a(n))
- These are partition functions that count the number of ways an integer n can be partitioned into parts, where each part has a specific multiplicity. The paper uses these functions to create equations that specifically equal zero only when n is a prime number.
- Quasimodular Forms
- These are special mathematical functions characterized by their Fourier expansions and how they react to the q-differential operator D. The study shows that forms in a specific space have coefficients that are non-negative for positive integers and vanish precisely when the integer is prime.
- Quasi-shuffle Algebra (Zq)
- This is an algebraic structure related to MacMahon's generating series, which allows the product of two such series to be calculated recursively using a 'quasi-shuffle product.' This structure helps define how these partition functions interact mathematically.
- Prime-Detecting Forms
- These are specific quasimodular forms identified as those whose Fourier coefficients vanish if and only if the index n is prime. Theorem 2.3 characterizes the space containing these forms, showing they are related to combinations of Eisenstein series.
Terminology
Summary
Integer partitions detect prime numbers in an unexpected way by showing that primes are solutions to special equations in partition functions. p. 0 We show that integer partitions, the fundamental building blocks in additive number
theory, detect prime numbers in an unexpected way. Answering a question of Schneider, we show
that the primes are the solutions to special equations in partition functions. We show that integer partitions, the fundamental building blocks in additive number
theory, detect prime numbers in an unexpected way. Answering a question of Schneider, we show
that the primes are the solutions to special equations in partition functions.Where the paper says it
Where the paper says it
Detection of Primes via Partition Functions
The paper establishes that for an integer n ≥ 2, n is prime if and only if certain expressions involving MacMahon’s partition functions M a(n) equal zero. Specifically, the expression (3n cubed − 13n squared + 18n − 8)M 1(n) + (12n squared − 120n + 212)M 2(n) − 960M 3(n) vanishes if and only if n is prime. p. 1 The following are true:
(1) For positive integers n, we have
(n
2 − 3n + 2)M1(n) − 8M2(n) ≥ 0,
and for n ≥ 2, this expression vanishes if and only if n is prime. (2) For positive integers n, we have
(3n
3 − 13n
2 + 18n − 8)M1(n) + (12n
2 − 120n + 212)M2(n) − 960M3(n) ≥ 0,
and for n ≥ 2, this expression vanishes if and only if n is prime. For example, an integer
n ≥ 2 is prime if and only if
(3n
3 − 13n
2 + 18n − 8)M1(n) + (12n
2 − 120n + 212)M2(n) − 960M3(n) = 0,
where the Ma(n) are MacMahon’s well-studied partition functions. More generally, for MacMahonesque partition functions M~a(n), we prove that there are infinitely many such prime detecting
equations with constant coefficients, such as
80M(1,1,1) (n) − 12M(2,0,1) (n) + 12M(2,1,0) (n) + · · · − 12M(1,3) (n) − 39M(3,1) (n) = 0.Where the paper says it
Where the paper says it
Generalization to MacMahonesque Functions
The work extends to a broader class of partition functions, the MacMahonesque partition functions M a(n), defined by sums of monomials in part multiplicities. The authors define natural generalizations M a(n) and establish that there exist infinitely many linear equations with integer coefficients whose set of solutions for n ≥ 2 is the set of primes. p. 1 , 1) ∈ N
a
. For these generalized MacMahon functions, we establish the existence of infinitely many linear
equations with integer coefficients whose set of solutions, where n ≥ 2, is the set of primes. Such simplifications always exist. It turns out that arbitrary convolutions of MacMahonesque
functions are always linear combinations of such functions with constant coefficients.Where the paper says it
Where the paper says it
Connection to Quasimodular Forms
The proof relies heavily on the theory of quasimodular forms, which are characterized by their Fourier expansions and properties related to the q-differential operator D. The authors show that quasimodular forms in a specific space, denoted as omega, are those whose Fourier coefficients b n(f) satisfy b n(f) ≥ 0 for positive n and vanish if and only if n is prime. p. 5 We then let Ω denote the prime-detecting quasimodular forms, where a quasimodular form
f =
X
n≥0
bn(f)q
n
is prime-detecting if for positive n we have bn(f) ≥ 0, and for n ≥ 2 vanish if and only if n is prime. Based on numerical evidence, we expect that the property of vanishing of the Fourier coefficients
at primes is not satisfied by quasimodular forms which are not in the quasimodular Eisenstein
space. We give an explicit description of E ∩ Ω (see Theorem 2. To this
end, for even k ≥ 6, we define the distinguished quasimodular forms of weight k
Hk := X
n≥0
bn(Hk)q
n
:= (
1
6
(D2 − D + 1)G2 − G4
if k = 6,
1
24 (−D2Gk−6 + (D2 + 1)Gk−4 − Gk−2) if k ≥ 8.Where the paper says it
Where the paper says it
Reformulation via Generating Series
The results are further clarified by relating the partition functions to generating series U a(q) and their quasi-shuffle algebra Zq. The space Zq is shown to be a differential subalgebra of Q[[q]] containing Mf. p. 4 We also denote by Mfk the subspace of Mf
of forms with weight k, and Mf≤k the space of all quasimodular forms of mixed weight ≤ k. We require the important q-differential operator
D :=
1
2πi
d
dτ = q
d
dq (2. (1) By Theorem 1. 4 (1) and (2), every convolution product of MacMahonesque functions with
polynomial coefficients is a linear combination of such functions with rational coefficients.Where the paper says it
Where the paper says it
Characterization of Prime-Detecting Forms
Theorem 2.3 characterizes the space E ∩ omega as being generated by the forms D n H k for n ≥ 0 and k ≥ 6. p. 3 Quasimodular forms that detect primes
Central to all of our results is a theorem (see Theorem 2. 3) that characterizes quasimodular forms
in the space consisting of linear combinations of derivatives of Eisenstein series whose coefficients
are zero at primes and positive at composite n ≥ 2. Quasimodular forms that detect primes
Central to all of our results is a theorem (see Theorem 2. 3) that characterizes quasimodular forms
in the space consisting of linear combinations of derivatives of Eisenstein series whose coefficients
are zero at primes and positive at composite n ≥ 2. To prove Theorem 2. 3, we also require the following about the linear independence of the forms
DnHℓ and the spaces they generate.Where the paper says it
Where the paper says it
Where the paper says it
Verification of Key Theorems
Theorem 1.3 is confirmed by showing that for d ≥ 4, there exist relatively prime integers c a such that X a≤d c a M a(n) ≥ 0, and this expression vanishes if and only if n is prime. p. 2 If d ≥ 4, then the following are true. (1) There are relatively prime integers c~a such that for positive integers n we have
X
|~a|≤d
c~a M~a(n) ≥ 0,
and for n ≥ 2, this expression vanishes if and only if n is prime. 5) is divisible by x+ 1 one can easily infer that the rank is exactly k − 1. Therefore, the dimension of the space of polynomials satisfying (2. Since the spaces of quasimodular forms of (mixed) weight ≤ 2a is finite-dimensional, the
examples given in the Appendix can be verified by a straightforward linear algebra calculation3
. In particular, the examples in Table 1 are exactly 6H6 , 36H8 , 90H10 , 90H12 , and 30 D2 + 1
H14 +
30H16 respectively. Furthermore,
linear combinations of MacMahonesque functions with polynomial coefficients can be reduced similarly. To be precise, we have the following result which is implicit in the proof of Theorem 1. It turns out that arbitrary convolutions of MacMahonesque
functions are always linear combinations of such functions with constant coefficients. Furthermore,
linear combinations of MacMahonesque functions with polynomial coefficients can be reduced similarly. In particular, we prove the following theorem (see Theorem 4. All quasimodular forms are linear combinations of the MacMahonesque U
sym
~a (q).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Symmetric Group Action and Generation
The symmetric group action on generalized MacMahonesque q-series is used to construct canonical quasimodular forms, U sym a(q). For a consisting of only odd entries, the symmetrized series are shown to be a polynomial in U(v) for certain odd integers v. p. 3 Bachmann and K¨uhn show [10] that the MacMahonesque series generate an extraordinary
differential algebra whose arithmetic properties encode a rich web of identities satisfied by the
MacMahonesque generating functions. To make use of quasimodularity, for those ~a with odd
entries, we construct quasimodular forms U
sym
~a (q) by taking traces over the natural action of the
symmetric group Sa on U~a(q). We now turn to the problem of determining those quasimodular forms whose Fourier expansions
detect primes. To this end, we let E denote the quasimodular Eisenstein space, the subspace of
quasimodular forms generated additively by the even weight Eisenstein series and their derivatives. 1 that k and ℓ are odd is imposed to ensure fk,ℓ are quasimodular
forms. In particular, the vanishing property is true for any non-negative integers k and ℓ. Quasimodular forms that detect primes
Central to all of our results is a theorem (see Theorem 2. 3) that characterizes quasimodular forms
in the space consisting of linear combinations of derivatives of Eisenstein series whose coefficients
are zero at primes and positive at composite n ≥ 2. (1) By Theorem 1. 4 (1) and (2), every convolution product of MacMahonesque functions with
polynomial coefficients is a linear combination of such functions with rational coefficients. 3) under which their
Fourier expansions detect primes, a result which is of independent interest. In Section 3, we use
the fact that MacMahon’s q-series Ua(q) arise naturally as quasimodular forms (see [10, 12, 13]),
combined with Theorem 2.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Development of Prime Detecting Equations: The system can be programmed to search for linear combinations of MacMahon functions with polynomial coefficients that vanish precisely on prime numbers, as demonstrated by Theorem 1.1 and Theorem 2.3.
-
Generalization of Partition Functions: The AI can handle the definition and manipulation of generalized MacMahonesque partition functions M a(n) using the definition provided in equation (1.3), allowing it to explore infinitely many such prime detecting equations.
-
Quasimodular Form Identification: The system can identify quasimodular forms by checking if their Fourier expansions satisfy the conditions of Theorem 2.3, specifically recognizing forms like H k which are shown to be in the set Omega where "a quasimodular form f = X n>=0 b n(f)q n is prime-detecting if for positive n we have bn(f) >= 0, and for n >= 2 vanish if and only if n is prime."
-
Algebraic Structure Analysis: The system can leverage the theory of quasi-shuffle algebras to compute the product of MacMahonesque series recursively using the definition in equation (4.3), allowing it to verify identities such as U1(q) U2(q) = 3U3(q) + 1/6 U(3,1)(q) + 1/6 U(1,3)(q) - 1/3 U2(q).
-
Space Characterization: The system can determine the dimension of the space of elements D n H l of weight less than or equal to k by applying Lemma 2.5 and Theorem 4.4, which states that this dimension is given by X l>=3 X 2l+2n<=k 1/8 (k - 2)(k - 4).
Abstract
We show that integer partitions, the fundamental building blocks in additive number theory, detect prime numbers in an unexpected way. Answering a question of Schneider, we show that the primes are the solutions to special equations in partition functions. For example, an integer n at least 2 is prime if and only if (3n cubed - 13n squared + 18n - 8)M 1(n) + (12n squared - 120n + 212)M 2(n) -960M 3(n) = 0, where the M a(n) are MacMahon's well-studied partition functions. More generally, for "MacMahonesque" partition functions M a vector(n), we prove that there are infinitely many such prime detecting equations with constant coefficients, such as 80M(1,1,1)(n)-12M(2,0,1)(n)+12M(2,1,0)(n)+ -12M(1,3)(n)-39M(3,1)(n)=0.
Sources
- MacMahon's sums-of-divisors and allied $q$-series
- MacMahon's sums-of-divisors and their connection to multiple Eisenstein series
- Remarks on MacMahon's $q$-series
Related papers
- K ab has the Bogomolov property for canonical heights
- Quasi-Jacobi forms, Appell-Lerch functions, and false theta functions as q-brackets of functions on partitions
- Wasserstein rates of all orders for the Sato-Tate law of Kloosterman sums
- Riemann functions for almost primes and their counting errors
- Topological flatness of orthogonal spin local models
- Asymptotic counting of integers with prime factors p r a s b