Partitions and Generating Functions

I asked Gemini to explain the statement:

“It’s long been known that you can associate

a polynomial equation to any partition.”

Here's what it came up with.

The statement refers to the relationship between an integer partition and a generating function, which is a way of encoding an infinite sequence of numbers as the coefficients of a formal power series. In this context, the "polynomial equation" is more accurately a generating function, which can be represented as a polynomial-like expression.

A partition of a positive integer \(n\) is a way of writing \(n\) as a sum of positive integers. The order of the addends (the parts of the partition) does not matter. For example, the partitions of the number 4 are:

• 4

• 3 + 1

• 2 + 2

• 2 + 1 + 1

• 1 + 1 + 1 + 1

The statement means that for any given integer, we can construct a polynomial-like expression (a generating function) that "encodes" all of its possible partitions.

How the Association Works

The connection is established through the concept of generating functions. The generating function for the number of partitions of an integer \(n\), denoted as \( p(n) \), can be expressed as an infinite product:$$P(x) = \sum_{n=0}^{\infty} p(n)x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}$$Let's break down this formula:

• \( p(n) \) This represents the number of partitions for an integer \(n\)

• \( \displaystyle\sum_{n=0}^{\infty} p(n)x^n \) This is the power series where the coefficient of \(x^n\) is the number of partitions of \(n\).

• \(\displaystyle\prod_{k=1}^{\infty} \dfrac{1}{1-x^k}\) This is the infinite product that generates these coefficients.

Each term in the product \( \dfrac{1}{1-x^k} \) can be expanded as a geometric series:

• \(\dfrac{1}{1-x} = 1 + x + x^2 + x^3 + \dots \) This represents using the number 1 as a part in the partition

• \(\dfrac{1}{1-x^2} = 1 + x^2 + x^4 + x^6 + \dots\) This represents using the number 2 as a part

• \( \dfrac{1}{1-x^3} = 1 + x^3 + x^6 + x^9 + \dots \) This represents using the number 3 as a part

• And so on for all integers \(k\).

When you multiply these series together, the coefficient of \(x^n\) in the resulting series will be the total number of ways to form \(n\) by adding these parts.

Examples

Let's find the partitions for the number 3. The partitions are:

• 3

• 2 + 1

• 1 + 1 + 1

There are 3 partitions of 3.

Now, let's see how the generating function gives us this result. We look at the expansion of the product:$$(1 + x + x^2 + x^3 + \dots)(1 + x^2 + x^4 + \dots)(1 + x^3 + x^6 + \dots) \dots$$To get the term \(x^3\), we can combine terms from these expansions in the following ways:

• From the first factor, take \(x^3\). This corresponds to the partition 1 + 1 + 1.

• From the first factor, take \(x^1\), and from the second factor, take \(x^2\). This corresponds to the partition 1 + 2.

• From the third factor, take \(x^3\). This corresponds to the partition 3.

The coefficient of \(x^3\) is therefore 3, which matches the number of partitions.

Here is another example for the partitions of 4, which we know is 5.

To find the coefficient of \(x^4\), we would consider combinations like:

• \(x^4\) from the first factor: 1 + 1 + 1 + 1

• \(x^2\) from the first factor and \(x^2\) from the second: 1 + 1 + 2

• \(x^1\) from the first factor and \(x^3\) from the third: 1 + 3

• \(x^4\) from the second factor: 2 + 2

• \(x^4\) from the fourth factor: 4

The total number of ways to get \(x^4\) is 5, so the coefficient is 5.

In essence, the "polynomial" or generating function provides a systematic way to count the number of partitions for any integer by looking at the coefficients of the series expansion.

Euler–Mascheroni constant and the Meissel–Mertens constant

I've not written explicitly about either the Euler–Mascheroni constant or the Meissel–Mertens constant before, although the former is made mention of in a Numberphile video that I referenced in a post titled The Harmonic Series on October 12th 2016. 

Let's recount that the harmonic series is simply \(\zeta(1)\) and so:$$\zeta(1)=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+ \dots =\sum_{n=1}^{\infty}\frac{1}{n}$$While this sequence does diverge it does so very slowly and that's what my post The Harmonic Series was all about. The Euler-Mascheroni constant can be defined as:$$\begin{align}

\gamma &= \lim_{n\to\infty}\left(-\log n + \sum_{k=1}^n \frac1{k}\right)\\

&=\int_1^\infty\left(-\frac1x+\frac1{\lfloor x\rfloor}\right)\,dx.

\end{align}$$Here, \(\lfloor x\rfloor\) represents the floor function. The numerical value of the Euler–Mascheroni constant, to 50 decimal places, is:

0.57721566490153286060651209008240243104215933593992... 

Below I've embedded the Numberphile video referred to earlier as it's really quite informative.

Like the harmonic series, the sum of the reciprocals of the prime numbers diverges also and even more slowly. The Meissel-Mertens constant is defined as:$$M = \lim_{n \rightarrow \infty } \left( \sum_{p \leq n} \frac{1}{p} - \ln(\ln n) \right)=\gamma + \sum_{p} \left[ \ln\! \left( 1 - \frac{1}{p} \right) + \frac{1}{p} \right]$$where \( \gamma \) is the Euler-Mascheroni constant. The value of M is approximately:

M ≈ 0.2614972128476427837554268386086958590516... 

Figure 1: source

The two constants are thus intimately linked. It's easy to generate approximations of these functions using SageMathCell. See Figure 2.

Figure 2: permalink

Looking at the results in Figure 2, it can be seen that:

Approximation of Euler-Mascheroni constant up to 100000 is 0.577220664893197

Approximation of Miessel-Mertens constant up to 100000 is 0.261801821365208

The light grey digits do not correspond to the known digits for these constants. It can be seen that the approximation to the Miessel-Mertens constant is less accurate than for the Euler-Mascheroni constant, reflecting the log(log) computation for the former versus the log computation for the latter.

For a post that shows how to determine the sum of the alternating harmonic series, see my post titled Alternating Series Test from April 23rd 2021. The alternating harmonic series converges thus:$$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4} \dots=\ln(2) \approx 0.693147180559945 \dots$$See also:

• Biography of Ernet Meissel
• Biography of Franz Mertens
• Biography of Lorenzo Mascheroni
• Biography of Leonhard Euler

Collaboration between Integration and Summation

When it is permissible, it is often convenient when evaluating certain integrals to interchange the order of a summation and an integration. Let's use the following definite integral as an example to illustrate this technique:$$\int_0^{\infty}\frac{x}{e^x-1} \mathrm{d}x$$The graph is as shown in Figure 1.

Figure 1: created in GeoGebra

Let's begin the integration:$$\begin{align} \int_0^{1}\frac{x}{e^x-1} \mathrm{d}x&=\int_0^{1}\frac{x}{\dfrac{1}{e^{-x}}-1} \mathrm{d}x\\
&=\int_0^{1}\frac{x \, e^{-x}}{1-e^{-x}}\mathrm{d}x\\
&=\int_0^{1} x \, e^{-x} \left ( \dfrac{1}{1-e^{-x}} \right ) \mathrm{d}x\\
&=\int_0^{1} x \, e^{-x} \sum_{n=0}^{\infty} e^{-nx} \, \mathrm{d}x\\
&=\sum_{n=0}^{\infty} \int_0^{1} x \, e^{-x(n+1)} \, \mathrm{d}x\\
&=\sum_{n=1}^{\infty} \int_0^{1} x \, e^{-nx} \, \mathrm{d}x \\
\text{Now } \int x \, e^{-nx} \, \mathrm{d}x &= \int x \frac{\mathrm{d}}{\mathrm{d}x} \left (\frac{e^{-nx}}{-n} \right ) \, \mathrm{d}x\\
&=\frac{-x \, e^{-nx}}{n}+\frac{1}{n} \int e^{-nx} \, \mathrm{d}x\\
&=\frac{-x \, e^{-nx}}{n}- \frac{e^{-nx}}{n^2} +C\\
\text{So }\int_0^{1}\frac{x}{e^x-1} \mathrm{d}x&=\sum_{n=1}^{\infty} \left [ \frac{-x \, e^{-nx}}{n}- \frac{e^{-nx}}{n^2} \right ]_0^1\\
&=\sum_{n=1}^{\infty} \left ( \frac{-e^{-n}}{n}-\frac{e^{-n}}{n^2}+\frac{1}{n^2} \right )\\
&=\sum_{n=1}^{\infty} \frac{1}{n^2} -\sum_{n=1}^{\infty}\frac{e^{-n}}{n} -\sum_{n=1}^{\infty} \frac{e^{-n}}{n^2}\\
\text{Now }\sum_{n=1}^{\infty} \frac{1}{n^2} &=\zeta(2)\\
&=\frac{\pi^2}{6}\\
\sum_{n=1}^{\infty}\frac{e^{-n}}{n} &= 1-\ln(e-1) \\
\sum_{n=1}^{\infty}\frac{e^{-n}}{n^2} &= \text{Li}_2 \left (\dfrac{1}{e} \right )\\
\text{Hence } \int_0^{1}\frac{x}{e^x-1} \mathrm{d}x&=\frac{\pi^2}{6}+\ln(e-1) -\text{Li}_2 \left (\dfrac{1}{e} \right )-1\\
&\approx 0.777505

\end{align}$$Looking at Figure 1, it can be seen that this result looks just about right. I'm thankful to Mathematics M1's YouTube video for detailing the steps required to reach this result. I'm reproducing the steps here as a means of practising my LaTeX skills but it's also to remind me how interesting the integration technique is, specifically the way in which the integral and the summation are swapped around. Li is the Eulerian Logarithmic Integral and deserves a blog post of its own.$$ \mathrm{Li}(x)=\int_2^x \dfrac{\mathrm{d}t}{\ln t }= \mathrm{li}(x)-\mathrm{li}(2) \text{ where } \mathrm{li}(x)=\int_0^x \dfrac{\mathrm{d}t}{\ln t }$$

Integration of x^x and x^(-x)

There are many YouTube videos outlining how to integrate \(x^x\) and \(x^{-x}\) but the following is the best explained that I've come across.

In the video, the function \(x^x\) is integrated from 0 to 1. In fact, this proper integral is converted into an infinite series so traditional integration is not possible. The result is quite impressive:$$\int_0^1 x^x \mathrm{d} x=\sum_0^{\infty} \frac{(-1)^n}{(n+1)^{n+1}}=1-\frac{1}{2^2}+\frac{1}{3^3}-\frac{1}{4^4}+ \dots \approx 0.783430$$The result for \(x^{-x}\) is similar:$$\int_0^1 x^{-x} \mathrm{d} x=\sum_0^{\infty} \frac{1}{(n+1)^{n+1}}=1+\frac{1}{2^2}+\frac{1}{3^3}+\frac{1}{4^4}+ \dots \approx 1.291285 $$Figure 1 shows the SageMath code to draw the two graphs in the given range and to calculate the area bounded by them:

Figure 1: permalink

Figure 2 shows the result with annotations added:

Figure 2

It's hard to see but the area bounded by the two curves is shown at the bottom left and is approximately 0.507855 square units. Figure 3 shows an alternative representation using GeoGebra:

Figure 3

These graphs, their turning points and the bounded area between them are most interesting. Let's not forget that the turning points for both graphs occur when \(x=\dfrac{1}{e}\) because:$$\begin{align} y&=x^x\\ \frac{\mathrm{d}}{\mathrm{d} x} y &=\frac{\mathrm{d}}{\mathrm{d} x } x^x\\&=\frac{\mathrm{d}}{\mathrm{d} x} e^{\,x \ln x}\\&=e^{\,x \ln x} (1+\ln x)\\&=0 \text { when }\ln x = -1 \text{ or } x=\frac{1}{e} \end{align}$$The result is the same for \(y=x^{-x}\), only the y values differ with \(e^{1/e} \approx 1.44\) for \(x^{-x}\) and \(e^{-1/e} \approx 0.69\) for \(x^x \).

The Catalan Constant

Today I turned 25977 days old and this number is prime. One of its claims to fame is that it is a member of OEIS A104919:

A104919

Primes from merging of 5 successive digits in decimal expansion of Catalan's constant.

I was familiar with Catalan numbers and in fact posted about them in this post from the 30th of September 2015 and another post from the 15th of April 2018. These numbers, and the eponymous constant, are named in honour of the Belgium mathematician Eugène Catalan. So what is the Catalan constant? It is defined as follows:$$\sum_{n=0}^{\infty} \frac{(-1)^{n}}{(2n+1)^3} = \frac{1}{1^3} - \frac{1}{3^3} + \frac{1}{5^3} - \frac{1}{7^3} + \frac{1}{9^3} - \cdots$$It is equal to 0.915965594177219015054603514932384110774 ... but the interesting thing is that no one knows whether it is irrational and, if it is, whether it is transcendental. This is odd because a similar looking sequence is known to be transcendental viz.:$$\sum_{n=0}^{\infty} \frac{(-1)^{n}}{(2n+1)^3} = \frac{1}{1^3} - \frac{1}{3^3} + \frac{1}{5^3} - \frac{1}{7^3} + \frac{1}{9^3} - \cdots = \frac{\pi^3}{32}$$As of July 16th 2019, the Catalan constant is known to 600,000,000,100 decimal places. This site lists the constant to 300,000 decimal places with the introduction:

Catalan constant to 300000 digits computed on September 29, 1996 by using a Sun Ultra-Sparc in 1 day 8 hour 15 min 15 sec 55 hsec. The algorithm used is the standard series for Catalan, accelerated by an Euler transform. The algorithm was implemented using the LiDIA library for computational number theory and it is part of the multiprecision floating-point arithmetic of the package.

This number of decimal places was the record for 1996 and it was more than sufficient for me to generate the OEIS sequence A104919 up to and including 25997. I simply copied a few thousand of the first few digits into a list and applied the SageMath algorithm shown in this permalink.

Of course, the digits can be generated using a wide variety of formulae. One of the best is the following: $$\frac{\pi}{8}\log\left(2 + \sqrt{3}\right) + \frac{3}{8}\sum_{n=0}^\infty \frac{1}{(2n+1)^2 \binom{2n}{n}}$$I tried this but wasn't successful in generating more than the first two members of the sequence so I abandoned this approach and copied and pasted instead! I'm always fascinated by these types of sequences because of their similarity to the famous Riemann zeta function:$$\zeta(s) =\sum_{n=1}^\infty\frac{1}{n^s}$$In fact the summation that generates the Catalan constant is the Dirichlet beta function (also known as the Catalan beta function) and it is closely related to the Riemann zeta function. It is defined as:$$\beta(s) = \sum_{n=0}^\infty \frac{(-1)^n} {(2n+1)^s}$$When \(s=2\), \( \beta(2)\) gives the Catalan constant. You can read more here about the Dirichlet beta function.