Number theory

Phi Phi

Posted on by John

I was reading something this afternoon and ran across φ(φ(m)) and thought that was unusual. I often run across φ(m), the number of positive integers less than m and relative prime to m, but don’t often see Euler’s phi function iterated.

Application of φ∘φ

This section will give an example of a theorem where φ(φ(m)) comes up.

First of all, Euler’s theorem says that given an integer m > 1 and an integer g relatively prime to m, then

gφ(m) = 1 (mod m).

Now Euler’s theorem gives a value of t such that gt = 1 (mod m). It doesn’t say this is the smallest t, only that it’s a possible value of t. If φ(m) is the smallest such value of t, then g is called a primitive root mod m.

For example, let m = 10. Then φ(10) = 4, and so a primitive root mod 10 is a number g such that g4 = 1 mod 10, but gt is not congruent to 1 mod 10 for t = 1, 2, or 3. Now 3 is a primitive root mod 10 because 34 ends in 1, but 3, 3², and 3³ do not end in 1.

There are no primitive roots mod 12. A primitive root mod m has to be relatively prime to m [1], and so there are only four candidates: 1, 5, 7, and 11. Each of these is congruent to 1 mod 12 when squared, so for none of them is 4 = φ(12) the smallest exponent that gives a number congruent to 1.

Now we’re ready to state our theorem, Theorem 2.34 from The Joy of Factoring by Samuel Wagstaff, Jr.

An integer m > 1 has a primitive root if and only if m = 2, m = 4, m = pe , or m = 2pe, where p is an odd prime and e is a positive integer. If m has a primitive root, then it has exactly φ(φ(m)) of them in 1 ≤ g ≤ m.

This theorem could have told us that 10 has primitive roots and 12 doesn’t, and it could tell us that 10 has exactly φ(φ(m)) = 2 primitive roots. We found one of them, 3, and the other is 7.

Higher iterates

Let φ1(n) = φ(n) and φ2(n) = φ(φ(n)). In general, let φk be the function defined by iterating the phi function k times. If we apply φ to any integer enough times, we’ll get 1. For each n, let k(n) be the smallest value of k such that φk(n) = 1. Then Erdős et al proved that k(n) is between log(n)/log(3) and log(n)/log(2).

To illustrate this, let n = 20220630. The theorem above predicts we’ll have to apply φ between 16 and 25 times before we get to 1. The following code shows k(n) = 21.

    from sympy import totient

    n = 20220630
    k = 0

    while n > 1:
        n = totient(n)
        k += 1
 
    print(k)

Note that “totient” is another name for Euler’s φ function.

Related posts

[1] If g shares a factor bigger than 1 with m, then so does every positive power of g, and so no power of g is congruent to 1 mod m. In particular, gφ(m) cannot be 1.

Infinite periodic table

Posted on by John

All the chemical elements discovered or created so far follow a regular pattern in how their electrons are arranged: the nth shell contains up to 2n – 1 suborbitals that each contain up to two electrons. For a given atomic number, you can determine how its electrons are distributed into shells and suborbitals using the Aufbau principle.

The Aufbau principle is a good approximation, but not exact. For this post we’ll assume it is exact, and that everything in the preceding paragraph generalizes to an arbitrary number of shells and electrons.

Under those assumptions, what would the periodic table look like if more elements are discovered or created?

D. Weiss worked out the recurrence relations that the periods of the table satisfy and found their solutions.

The number of elements in nth period works out to

P_n = \frac{(-1)^n(2n+3) + 2n^2 + 6n + 5}{4}

and the atomic numbers of the elements at the end of the nth period (the noble gases) are

Z_n = \frac{(-1)^n(3n+6) + 2n^3 + 12n^2 + 25n - 6}{12}

We can verify that these formulas give the right values for the actual periodic table as follows.

    >>> def p(n): return ((-1)**n*(2*n+3) + 2*n*n + 6*n +5)/4
    >>> def z(n): return ((-1)**n*(3*n+6) + 2*n**3 + 12*n**2 + 25*n - 6)/12
    >>> [p(n) for n in range(1, 8)]
    [2.0, 8.0, 8.0, 18.0, 18.0, 32.0, 32.0]
    >>> [z(n) for n in range(1, 8)]
    [2.0, 10.0, 18.0, 36.0, 54.0, 86.0, 118.0]

So, hypothetically, if there were an 8th row to the periodic table, it would contain 50 elements, and the last element of this row would have atomic number 168.

Related

Looking for the next prime

Posted on by John

Suppose you start with some large number x and want to find a prime number at least as big as x. First you test whether x is prime. Then you test whether x + 1 is prime. Then you test whether x + 2 is prime, and so on until you find a prime. Of course you would just test odd numbers, but how far might you have to look? How much larger than x might your result be?

Bertrand conjectured, and Chebyshev proved, that you’ll find a prime before you get to 2x. Said another way, the width of the interval you need to explore is no larger than x.

Note that if we just want to find a prime of a certain order of magnitude, the most efficient approach is to try numbers at random until you find one. But if you want to find the next prime you have to search more methodically. Maybe there’s a better way to do this than sequentially testing odd numbers. In any case, this post looks at an upper on the result you get, regardless of how you go about finding it.

New results

In [1] the authors prove that the length of the interval to search can be orders of magnitude smaller than x. For example, if

x > e60

then the interval can be of length x/1016.

The authors state their results in the form of an interval up to x rather than an interval starting at x, so their theorems immediately apply to starting at x and searching backward for the largest prime no greater than x. But by changing what you call x you could apply the results to looking forward for the smallest prime no smaller than x.

Illustration related to cryptography

Let’s see what the results in [1] might say about primes of the size used in cryptography. For example, RSA and Diffie-Hellman work with primes on the order of 22048 or 23072. More on that here.

If x is a 2048-bit integer x, then log x is around 1420. The authors in [1] show that if

log x > 1200

then the length of the interval to explore has width less than x/Δ where Δ = 3.637×10263.

Now if x is a 2048-bit number then we need to explore an interval of length less than

22048 / 3.637 × 10263 ≈ 22048/ 2857.5 = 21172.5.

So for a 2048-bit number, the length of the interval to search is a 1173 bit number. Said another way, we can turn x into a prime number by only changing the last 1173 bits, leaving the top 875 bits alone.

The number of bits in the length of the interval to search is a little more than half the number of bits in x; we can turn x into a prime by modifying a little more than half its bits.This is a general result for sufficiently large x.

The key contribution of [1] is that they’re explicit about what “sufficiently large” means for their theorems. There are other theorems that are not explicit. For example, in [2] the authors prove that for large enough x, the interval to search has width x0.525, but they don’t say how large x has to be.

If 22048 is large enough for the theorem in [2] to hold, then the length of our interval could be a 1076-bit integer.

Related posts

[1] Michaela Cully-Hugill and Ethan S. Lee. Explicit interval estimates for prime numbers. Mathematics of Computation. https://doi.org/10.1090/mcom/3719. Article electronically published on January 25, 2022

[2] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes. II, Proc. London Math. Soc. (3) 83 (2001), no. 3, 532–562.

Beatty’s theorem

Posted on by John

Here’s a surprising theorem [1].

(Beatty’s theorem) Let a and b be any pair of irrational numbers greater than 1 with 1/a + 1/b = 1. Then the sequences { ⌊na⌋ } and { ⌊nb⌋ } contain every positive integer without repetition.

Illustration

Here’s a little Python code to play with this theorem.We set a = e and make b what it has to be to make the reciprocals add to 1.

We can’t tell from a finite sample whether the sequence covers all the integers, but we can at least verify that there are no repeats.

    from math import exp, floor

    a = exp(1)
    b = 1/(1 - 1/a)
    N = 100

    nums = set()
    for n in range(1, N+1):
        nums.add(floor(n*a))
        nums.add(floor(n*b))    
    print(len(nums))

We put 200 numbers into our set, and since they’re all unique, the set will have 200 elements when we’re done.

Except it doesn’t! We get 199 elements. Is there some subtle issue with floating point accuracy, where two numbers that should have different floors happen to have the same floor?

No, it’s nothing that complicated. When n = 0, ⌊0 a⌋ and ⌊0 b⌋ are both 0.

The theorem implicitly assumes that n ranges over positive integers, not non-negative integers [2]. If we modify our loop to

    for n in range(1, N+1):

then we do indeed get 200 distinct integers.

Coverage

Beatty’s theorem says that every integer k will eventually be part of one of the two sequences. That is, there will be some n such that k either equal ⌊na⌋ or ⌊nb⌋. How big might n be relative to k?

To get an idea, let’s modify the script above to report the smallest number that hasn’t occurred and the largest number that has occurred. We do this by taking the following line on at the end.

    print(min(set(range(1, 2*N)) - nums), max(nums))

This prints 159 and 271. That is, all the numbers from 1 through 158 have appeared, as well as numbers up to 271.

Now let’s do a longer run, changing N to 1000. Our code prints 1583 and 2718. So once again the numbers are filling in somewhat in order. Over three quarters of the numbers from 1 to 2000 have occurred.

Let’s crank N up to 1,000,000. Now we get 1581978 and 2718281. Each time, the smallest number not visited seems to be going up proportionally, as well as the largest number that has been visited.

That maximum number 2718281 looks familiar. In fact, it’s approximately 1,000,000 times e. In terms of our program parameters, it’s approximately Na.

And what about the lower number? It doesn’t look familiar, but we might guess Nb, and indeed b = 1.5819767….

Theorem

Based on the experiments above, we guess the following theorem. Define

S(N) = { ⌊na⌋ | 1 ≤ n ≤ N } ∪ { ⌊Nb⌋ | 1 ≤ n ≤ N }.

Then the smallest positive integer not in S(N) is

⌊(N+1) min(a, b)⌋

and the largest element in S(N) is

⌊N max(a, b)⌋.

Without loss of generality, assume a < b.

The largest element of S(N) will occur is as large as possible, i.e. n = N, and so the largest value in S(N) will be ⌊Nb⌋.

The number ⌊(N+1) a⌋ is not in S(N) since none of the elements of the Beatty sequences repeat, and it is the smallest number not in S(N).

One more run

Let’s illustrate our new theorem with a = √2.

Or program prints 1414214 and 3414213. The smallest number not encountered is 1414214, which equals ⌊1000001 √2⌋ .

Now b = 1/(1 – 1/√2) = 3.4142135…. and the maximum is indeed ⌊1000000 b⌋.

Notes

[1] Ezra Brown and Richard K. Guy. The Unity of Combinatorics. MAA Press, 2020.

[2] This is another example of a theme I return to regularly: it helps to test a theorem with a program, even if you’re certain the theorem is correct, because you’re not only testing the theorem, you’re testing your understanding of the theorem. Beatty’s theorem has been around over a century, and if it were wrong then we’d know by now. But my initial Python script revealed a requirement that was not explicit in the given statement of the theorem.

Three paths converge

Posted on by John

When does the equation

x2 + 7 = 2n

have integer solutions?

This is an interesting question, but why would anyone ask it? This post looks at three paths that have led to this problem.

Ramanujan

Ramanujan [1] considered this problem in 1913. He found five solutions and conjectured that there were no more. Then in 1959 three authors [2] wrote a paper settling the conjecture, showing that Ramanujan was right. We don’t know what motivated Ramanujan, but the subsequent paper was a response to Ramanujan.

Nagell

T. Nagell [3] published a solution in 1960 after becoming aware of [2]. This paper republished in English a solution the author had first published in 1948 in a Norwegian journal. Nagell says he gave the problem as an exercise in a number theory textbook he wrote in 1951. By mentioning his textbook but not Ramanujan, Nagell implies that he came to the problem independently.

Golay

I ran into the problem a week ago in the course of looking at a problem that came out of Golay’s work in coding theory. A necessary condition for the existence of a perfect binary code of length n including p redundant bits that can detect up to 2 errors is

{n \choose 0} + {n \choose 1} + {n \choose 2} = 2^p

This leads, via the quadratic equation, to the equation at the top of the post.

All solutions

Each of the paths above states the problem in different notation; it’s simpler to state the solutions without variables.

  • 12 + 7 = 23
  • 32 + 7 = 24
  • 52 + 7 = 25
  • 112 + 7 = 27
  • 1812 + 7 = 215

Verifying that these are solutions is trivial. Proving that there are no more solutions is not trivial.

References

[1] K. J. Sanjana and T. P. Trivedi, J. Indian Math. Soc. vol. 5 (1913) pp. 227-228.

[2] Th. Skolem, S. Chowla and D. J. Lewis. The Diophantine Equation 2n+2 – 7 = x2. Proceedings of the American Mathematical Society , Oct., 1959, Vol. 10, No. 5. pp. 663-669

[3] T. Nagell, The Diophantine Equation x2 + 7 = 2n. Arkiv för Matematik, Band 4 nr 13. Jan 1960.

Thanks to Brian Hopkins for his help on this problem via his answer to my question on Math Overflow.

Turning the Golay problem sideways

Posted on by John

I’ve written a couple posts about the Golay problem recently, first here then here. The problem is to find all values of N and n such that

S(N, n) = \sum_{k=0}^n \binom{N}{k}

is a power of 2, say 2p. Most solutions apparently fall into three categories:

  • n = 0 or n = N,
  • N is odd and n = (N-1)/2, or
  • n = 1 and N is one less than a power of two.

The only two other solutions as far as I know are the two that Golay found, namely N = 23 with n = 3 and N = 90 with n = 2. Those are the only solutions for N < 30,000.

Solutions for fixed p

Phil Connor wrote me with a good suggestion: for fixed n, S(N, n) is an nth degree polynomial in N, and we can search for when that polynomial equals 2p.

Instead of looping over N and seeing whether any S(N, n) is a power of 2 comes out, we could fix p and see whether there’s a corresponding value of N.

Now

S(N, n) = (1/n!)Nn + … + 1

and so we are looking for positive integer solutions to

Nn + … + n! = n! 2p.

Using the rational root theorem

By the rational root theorem, a necessary condition for

Nn + … – n!(2p -1)= 0

to have a rational root is that N must divide the constant term

-n!(2p -1).

That means that for fixed n and fixed p there are only a finite number of Ns that could possibly be solutions, namely the divisors of

n!(2p -1).

Say we wanted to find all solutions with p = 32 and n = 3. Then we only need to check 96 values of N because 3!(232 -1) has 96 divisors as the following Python code shows.

    >>> from sympy import divisors
    >>> len(divisors(6*(2**32-1)))
    96

We could evaluate S(N, 3) for each of the divisors of 6(232 -1) and see if any of them equal 232. And since S(N, n) is an increasing function of N, we could speed things up by being a little clever in our search. For example, if S(d, 3) > 232 for a particular divisor d, there’s no need to keep trying larger divisors. More generally, we could do a binary search.

Not only could this approach be more efficient, I suspect it casts the problem in a form that would make it easier to prove theorems about.

Using the quadratic equation

The rational root theorem isn’t the only theorem we could apply to the polynomial formulation of the Golay problem. For example, if n = 2 we can use the quadratic equation and look at the discriminant to show that a necessary condition for there to be an integer solution is that

2p+3 – 7

must be a positive integer. When p = 12 we get

215 – 7 = 1812,

and this corresponds to Golay’s solution N = 90. There cannot be any solutions for larger values of p if p is odd because then 2p+3 is a perfect square and there cannot be another perfect square so close. I don’t know whether there can be larger even values of p with

2p+3 – 7

being a perfect square. If someone could show there are no such solutions, this would prove Golay found the only solution with n = 2. Maybe something similar would work for larger values of n.

Rumors of a proof

The conjecture I’ve been writing about is listed as Theorem 9.3 in Martin Erickson’s book Introduction to Combinatorics, Erickson does not give a proof but refers to Vera Pless’ book Introduction to the Theory of Error-correcting Codes, Wiley, 1989. However, people on MathOverflow who have seen Pless’ book say there’s no proof there.

Terry Tao says he doubts there is a proof:

To be honest, I doubt that this “theorem” is within the reach of existing technology. … My guess is that Erickson misread the discussion in Pless’s book.

Part of the confusion is that exceptional solutions to the problem discussed here are necessary (but not sufficient) for the existence of perfect Golay codes. It is widely reported that there is only one perfect binary Golay code, one based on S(23, 3) = 211. Some have taken that to mean that there are no more exceptional solutions, but this doesn’t follow. Maybe there are more exceptional solutions, but they don’t lead to the existence of more perfect binary Golay codes.

I haven’t seen a proof that Golay’s 23-bit code is the only perfect binary Golay code, though I’ve seen this theorem quoted repeatedly. It would be good to track down the proof of this theorem (if there is one!) and see whether it proves what I’m calling the Golay conjecture as an intermediate step. (Update: it does not. Seems Terry Tao was right to suspect there is no proof.)

Binomial sums and powers of 2

Posted on by John

Marcel Golay noticed that

\binom{23}{0} + \binom{23}{1} + \binom{23}{2} + \binom{23}{3} = 2^{11}

and realized that this suggested it might be possible to create a perfect code of length 23. I wrote a Twitter thread on this that explains how this relates to coding theory (and to sporadic simple groups).

This made me wonder how common it is for cumulative sums of binomial coefficients to equal a power of 2.

Define

S(N, n) = \sum_{k=0}^n \binom{N}{k}

Golay’s observation could be expressed as saying

S(23, 3) = 211.

How often is S(N, n) a power of 2?

There are two easy cases. First,

S(N, 0) = 20

for all N because there’s only one way to not choose anything from a set of N items. Second,

S(N, N) = 2N

for all N. (Proof: apply the binomial theorem to (1 + 1)N.)

If N is odd, then we have

S(N, (N-1)/2) = 2N-1

by symmetry of the binomial coefficients.

Also,

S(2p – 1, 1) = 2p

In summary, S(N, k) is a power of 2 if

  • k = 0 or k = N,
  • N is odd and k = (N-1)/2, or
  • k = 1 and N is one less than a power of two.

Are there any more possibilities? Apparently not many.

The only exceptions I’ve found are (23, 3) and (90, 2). Those are the only possibilities for N < 10,000. (Update: Searched up to 30,000.)

Golay found both of these solutions and mentioned them in [1]. In Golay’s words, “A limited search has revealed two such cases.” He didn’t say how far he looked, and apparently he didn’t have a proof that these were the only exceptional solutions.

(This post has been edited several times since I first posted it, to reflect corrections and a better understanding of the problem.)

Related posts

[1] Golay, M. (1949). Notes on Digital Coding. Proc. IRE. 37: 657.

The congruent number problem

Posted on by John

A positive integer n is said to be congruent if there exists a right triangle with area n such that the length of all three sides is rational.

You could always choose one leg to have length n and the other to have length 2. Such a triangle would have area n and two rational sides, but in general the hypotenuse would not be rational.

The smallest congruent number is 5. You can verify that 5 is congruent because the triangle with legs 20/3 and 3/2 has hypotenuse 41/6 and area 5. You can find a list of congruent numbers in OEIS A003273.

You can show that a number is congruent by demonstrating a rational right triangle with the specified area, as with 5 above. Showing that a number is not congruent is harder. How do you know you haven’t looked long enough?

There’s no simple classification of congruent numbers, but there are partial results. Jerrold Tunnell proved [1] a way to show that a number is not congruent.

It suffices to look at square-free numbers, numbers not divisible by the square of an integer. This is because if n = mk² then n is congruent if and only if m is.

Tunnell gives two necessary conditions for whether a square-free number n is congruent: one for the case of n odd and one for the case of n even.

Because Tunnell’s theorem gives necessary conditions, it can only prove that a number is not congruent.

It would be tidy if Tunnell’s conditions were also sufficient, i.e. that they could prove that a number is congruent. And they may be sufficient. Tunnell proved that if the Birch and Swinnerton-Dyer conjecture is true, then the converse of his theorem is true. If you could prove that the Birch and Swinnerton-Dyer conjecture, you could prove the converse of Tunnell’s theorem as a corollary. You could also win a million dollar prize.

Now for Tunnell’s conditions. If an odd square-free positive integer n is congruent, then there are twice as many integer solutions to

2x² + y² + 8z² = n

as

2x² + y² + 32z² = n.

And if n is even and square free, there are twice as many solutions to

4x² + y² + 8z² = n

as

4x² + y² + 32z² = n.

In general it’s hard to know how many integer solutions an equation has, but for the equations above we can find the solutions by brute force because all the terms are positive. We know each variable is between -√n and √n. We could even be more efficient and check smaller ranges of x and z because of the coefficients. And we can mostly look for solutions in the first quadrants and multiply by 8, but we need to be careful not to count solutions with zero components more than once.

Let’s prove that 11 is not a congruent number.

How many solutions to

2x² + y² + 8z² = 11

are there?

Clearly z can only possibly be ±1 or 0. If z = ±1 then x = ±1 and y = ±1. If z = 0 then the only solutions are x = ±1 and y = ±3. So we have 14 solutions: eight of the form (±1, ±1, ±1) and two of the form (±1, ±3, 0).

For the equation

2x² + y² + 32z² = 11

z must be 0, and so we have the eight solutions we found before: all combinations of (±1, ±3, 0).

Our first equation has 14 solutions and the second has 4, and so 11 must not be congruent.

 

[1] Tunnell, Jerrold B. (1983), “A classical Diophantine problem and modular forms of weight 3/2”, Inventiones Mathematicae, 72 (2): 323–334, doi:10.1007/BF01389327

 

Estimating the number of integer partitions

Posted on by John

Last week I wrote a few posts that included code that iterated over all partitions of a positive integer n. See here, here, and here. How long would it take these programs to run for large n?

For this post, I’ll focus just on how many partitions there are. It’s interesting to think about how you would generate the partitions, but that’s a topic for another time.

Ramanujan discovered an asymptotic formula for p(n), the number of partitions of n. As n increases,

p(n) \sim \frac{1}{4n\sqrt{3}} \exp\left( \pi \sqrt{\frac{2n}{3}} \right)

The ratio of the two sides of the equation goes to 1 as n → ∞, but how accurate is it for the sizes of n that you might want to iterate over in a program?

Before answering that, we need to decide what range of n we might use. Let’s be generous and say we might want to look at up to a trillion (1012) partitions. How big of a value of n does that correspond to? The estimate above shows p(200) is on the order of 4 × 1012, so we only need to be concerned with n ≤ 200. (See the next post for how to exactly solve for a n that gives a specified value.)

Here’s a plot to show the relative error in the approximation above.

Here’s the Mathematica code that made the plot.

    approx[n_] := Exp[Pi Sqrt[2 n/3]]/(4 n Sqrt[3])
    DiscretePlot[ 1 - approx[n]/PartitionsP[n], {n, 200}]

So the estimate above is always an under-estimate, at least about 4% low over the range we care about. It’s good enough for a quick calculation. It tells us, for example, to be very patient if we’re going to run any program that needs to iterate over all partitions of an integer even as small as 100.

The function PartitionsP above returns the number of partitions in its argument. It returned quickly, so it certainly did not generate all partitions and count them. Algorithms for computing p(n) might make an interesting blog post another time.

Even though it would be impractical to iterate over the partitions of larger values, we still might be curious what the plot above looks like for larger arguments. Let’s see what the plot would look like for n between 200 and 2000.

The shape of the curve is practically the same.

The relative error dropped by about a factor or 3 when we increased n by a factor of 10. So we’d expect if we increase n by another factor of 10, the relative error would drop about another factor of 3, and indeed that’s what happens: when n = 20,000, the relative error is about -0.003.

Partitions and Pentagons

Posted on by John

This post will present a remarkable theorem of Euler which makes a connection between integer partitions and pentagons.

Partitions

A partition of an integer n is a way of writing n as a sum of positive integers. For example, there are seven unordered partitions of 5:

  • 5
  • 4 + 1
  • 3 + 2
  • 3 + 1 + 1
  • 2 + 2 + 1
  • 2 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1

Note that order does not matter. For instance, 4 + 1 and 1 + 4 count as the same partition. You can get a list of partitions of n in Mathematica with the function IntegerPartitions[n]. If we enter IntegerPartitions[5] we get

     {{5}, {4, 1}, {3, 2}, {3, 1, 1}, {2, 2, 1}, 
      {2, 1, 1, 1}, {1, 1, 1, 1, 1}}

We say a partition is distinct if all the numbers in the sum are distinct. For example, these partitions of 5 are distinct

  • 5
  • 4 + 1
  • 3 + 2

but these are not

  • 3 + 1 + 1
  • 2 + 2 + 1
  • 2 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1

because each has a repeated number.

We can divide distinct partitions into those having an even number of terms and those having an odd number of terms. In the example above, there is one odd partition, just 5, and two even partitions: 4 + 1 and 3 + 2.

Pentagonal numbers

The pentagonal numbers are defined by counting the number of dots in a graph of concentric pentagons: 1, 5, 12, 22, …. This is OEIS sequence A000326.

The jth pentagonal number is

Pj = j(3j – 1) / 2.

We can define negative pentagonal numbers by plugging negative values of j into the equation above, though these numbers don’t have the same geometric interpretation. (I think they do have a geometric interpretation, but I forget what it is.)

Euler’s pentagonal number theorem

Leonard Euler discovered that the number of even distinct partitions of n equals the number of odd distinct partitions, unless n is a pentagonal number (including negative indices). If n is the jth pentagonal number, then the difference between the number of even and odd distinct partitions of n equals (-1)j. In symbols,

D_e(n) - D_o(n) = \left\{ \begin{array}{ll} (-1)^j & \mbox{if } n = P_j \\ 0 & \mbox{otherwise} \end{array} \right.

Here De is the number of even distinct partitions and Do is the number of odd distinct partitions.

Euler discovered this by playing around with power series and noticing that the series involved were generating functions for pentagonal numbers. Jordan Bell has written a commentary on Euler’s work and posted it on arXiv.

Mathematica examples

Let’s look at the partitions of 12, the 3rd pentagonal number.

IntegerPartions[12] shows there are 77 partitions of 12. We can pick out just the partitions into distinct numbers by selecting partition sets that have no repeated terms, i.e. that have as many elements as their union.

    Select[IntegerPartitions[12], Length[Union[#]] == Length[#] &]

This returns a list of 15 partitions:

    {{12},      {11, 1},   {10, 2},      {9, 3},    {9, 2, 1}, 
     {8, 4},    {8, 3, 1}, {7, 5},       {7, 4, 1}, {7, 3, 2}, 
     {6, 5, 1}, {6, 4, 2}, {6, 3, 2, 1}, {5, 4, 3}, {5, 4, 2, 1}}

Of these sets, 7 have an even number of elements and 8 have an odd number of elements. This matches what Euler said we would get because

7 – 8 = (-1)3.

We’d like to eplore this further without having to count partitions by hand, so let’s define a helper function.

    f[list_] := Module[
        {n = Length[Union[list]]}, 
        If [n == Length[list], (-1)^n, 0]
    ]

This function returns 0 for lists that have repeated elements. For sets with no repeated elements, it returns 1 for sets with an even number of elements and -1 for sets with an odd number of elements. If we apply this function to the list of partitions of n and take the sum, we get

De(n) – Do(n).

Now

    Total[Map[f, IntegerPartitions[12]]]

returns -1. And we can verify that it returns (-1)j for the jth pentagonal number. The code

    Table[Total[Map[f, IntegerPartitions[j (3 j - 1)/2]]], {j, -3, 3}]

returns

    {-1, 1, -1, 1, -1, 1, -1}

We can compute De(n) – Do(n) for n = 1, 2, 3, …, 12 with

    Table[{n, Total[Map[f, IntegerPartitions[n]]]}, {n, 1, 12}]

and get

    {{1, -1}, {2, -1}, {3,  0}, {4,  0}, 
     {5,  1}, {6,  0}, {7,  1}, {8,  0}, 
     {9,  0}, {10, 0}, {11, 0}, {12, -1}}

which shows that we get 0 unless n is a pentagonal number.

Euler characteristic

Euler’s pentagonal number theorem reminds me of Euler characteristic. Maybe there’s a historical connection there, or maybe someone could formalize a connection even if Euler didn’t make the connection himself. In its most familiar form, the Euler characteristic of a polyhedron is

V – E + F

where V is the number of vertices, E is the number of edges, and F is the number of faces. Notice that this is an alternating sum counting o-dimensional things (vertices), 1-dimensional things (edges), and 2-dimensional things (faces). This is extended to higher dimensions, defining the Euler characteristic to be the alternating sum of dimensions of homology groups.

We can write De(n) – Do(n) to make it look more like the Euler characteristic, using Dk(n) to denote the number of distinct partitions of size k.

D0(n) – D1(n) + D2(n) – …

I suppose there’s some way to formulate Euler’s pentagonal number theorem in terms of homology.