Integer partitions detect the primes

arXiv:2405.06451 · math.NT, math.CO · Submitted 2024-05-10 · Read on arXiv

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

DOI: 10.1073/pnas.2409417121

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

Where the paper says it

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.

This research demonstrates a deep connection between additive number theory, specifically integer partitions, and the distribution of prime numbers through partition theoretic equations. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

More generally, the authors prove there are infinitely many such prime detecting equations with constant coefficients involving MacMahonesque partition functions M a(n). p. 0
Where the paper says it

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.

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

Where the paper says it

, 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.

This involves showing that arbitrary convolutions of MacMahonesque functions are always linear combinations of such functions with constant coefficients. p. 2
Where the paper says it

Such simplifications always exist. It turns out that arbitrary convolutions of MacMahonesque functions are always linear combinations of such functions with constant coefficients.

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

Where the paper says it

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.

The space of such forms is characterized by specific distinguished forms Hk. p. 5
Where the paper says it

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.

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

Where the paper says it

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.

This structure allows the product of any two MacMahon series to be computed recursively using the quasi-shuffle product, leading to Theorem 1. p. 2
Where the paper says it

(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.

4.

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

Where the paper says it

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.

This theorem provides a complete description of quasimodular forms that detect primes, confirming that these forms are related to specific combinations of Eisenstein series. p. 3
Where the paper says it

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.

The dimension calculations confirm the linear independence and structure of these spaces. p. 6
Where the paper says it

To prove Theorem 2. 3, we also require the following about the linear independence of the forms DnHℓ and the spaces they generate.

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

Where the paper says it

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.

The proof for the converse relies on the dimension of the space of polynomials satisfying a specific condition derived from vanishing at primes. p. 8
Where the paper says it

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.

Theorem 1.2 is verified by showing that examples in Table 1 are exactly linear combinations of the forms Hk. p. 8
Where the paper says it

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.

The final result shows that the expression in Theorem 1. p. 2
Where the paper says it

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.

1(1) can be reduced to a linear expression in MacMahonesque functions with constant coefficients. p. 2
Where the paper says it

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.

The paper concludes by showing that all quasimodular forms are linear combinations of the symmetrized MacMahonesque U sym a(q). p. 3
Where the paper says it

In particular, we prove the following theorem (see Theorem 4. All quasimodular forms are linear combinations of the MacMahonesque U sym ~a (q).

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

Where the paper says it

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).

These forms additively generate the space Mf≤k. p. 5
Where the paper says it

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.

This generation property is established by induction on the depth of the forms, confirming that all quasimodular forms are accounted for. p. 4
Where the paper says it

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 ℓ.

The paper demonstrates that the space Zq is strictly larger than the space of quasimodular forms but remains closed under differentiation by D. p. 3
Where the paper says it

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.

It is also shown that any derivative of a MacMahon series is a linear combination of MacMahonesque series U a. p. 2
Where the paper says it

(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.

The final result confirms that the power series multiplication of generalized MacMahon series can be computed recursively using the quasi-shuffle product. p. 3
Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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."

  4. 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).

  5. 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

Related papers