Partition Function and Waring's Problem

Hello everyone! In this post I shall briefly discuss about the partition function.

A partition of a number $n$ is a representation of $n$ as the sum of any number of positive integral parts. $p(n)$ is the number of partitions of $n$. For example $p(5)=7$ as

$5=5$
   $=4+1$
   $=3+2$
   $=3+1+1$
   $=2+2+1$
   $=2+1+1+1$
   $=1+1+1+1+1$

Generating function of $p(n)$ is given by $$1+\sum _{n=1}^{\infty }p(n)x^n=\prod _{k=1}^{\infty }{\frac {1}{1-x^k}}$$
We can rewrite the infinite product as $$(1+x+x^2+...)$$ $$(1+x^2+x^4+...)$$ $$(1+x^3+x^6+...)$$ $$\dots$$
and multiplying the series. Every partition of $n$ contributes $1$ to the coefficient of $x^n$.

From Pentagonal Number Theorem, $$\prod _{{n=1}}^{{\infty }}\left(1-x^{{n}}\right)=1+\sum _{{k=1}}^{\infty }(-1)^{k}\left(x^{{k(3k+1)/2}}+x^{{k(3k-1)/2}}\right)$$
We can derive a recurrence relation of $p(n)$ using above identity.
$$p(n)=\sum_{k=1}^{n}(-1)^{k+1}\left[p\left(n-\frac{1}{2}k(3k-1)\right)+p\left(n-\frac{1}{2}k(3k+1)\right)\right]$$
Using this recurrence we can write a program to calculate $p(n)$ in $O(n^{3/2})$ time.

import java.io.*;
import java.util.*;
import java.math.*;

public class Partition {

    public static int N = 200;
    public static BigInteger[] p = new BigInteger[N + 1];
    public static int[] x = new int[10001]; // i * (3 * i - 1) / 2
    public static int[] y = new int[10001]; // -i * (-3 * i - 1) / 2

    public static void main(String[] args) {
        double start = System.currentTimeMillis();
        int ax = 1;
        for (int i = 1; i <= 10000; i++) {
            x[i] = x[i - 1] + ax;
            y[i] = y[i - 1] + ax + 1;
            ax += 3;
        }
        p[0] = BigInteger.valueOf(1);
        p[1] = BigInteger.valueOf(1);
        for (int i = 2; i <= N; i++) {
            p[i] = BigInteger.valueOf(0);
            for (int j = 1; ; j++) {
                if (x[j] > i && y[j] > i) {
                    break;
                }
                if (j % 2 == 1) {
                    if (x[j] <= i) p[i] = p[i].add(p[i - x[j]]);
                    if (y[j] <= i) p[i] = p[i].add(p[i - y[j]]);
                } else {
                    if (x[j] <= i) p[i] = p[i].subtract(p[i - x[j]]);
                    if (y[j] <= i) p[i] = p[i].subtract(p[i - y[j]]);
                }
            }
        }
        System.out.println("P(" + N + ") = " + p[N]);
        double end = System.currentTimeMillis();
        System.out.println("Time elapsed : " + ((end - start) / 1000d) + " seconds");
    }
}

Ramanujan and G. H. Hardy derived an asymptotic formula of $p(n)$. Its derivation is beyond the scope of this article.
$${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)} \hspace{5 mm} \text{as} \hspace{5 mm} {\displaystyle n\rightarrow \infty }$$

Waring's problem is the generalization of partition function. Waring's problem asks whether it is possible to represent positive integers as sums of a fixed number $s$ of non-negative $k$-th powers.
$$n=x_1^k+x_2^k+x_3^k+ \dots + x_s^k$$ $g(k)$ is defined as the least value of $s$ such that above equation is solvable for all $n$. $G(k)$ is defined as the least value of $s$ for which above holds true for sufficiently large numbers, i.e. all numbers with at most a finite number of exceptions. So $G(k) \le g(k)$.

Let $q=\left[\left(\frac{3}{2}\right)^k\right]$. The number $n=2^kq-1 < 3^k$ can be represented by only the powers $1^k$ and $2^k$. $$n=(q-1)2^k+(2^k-1)1^k$$ So $$g(k) \geq 2^{k}+[(3/2)^{k}]-2$$
Interested reader can find detailed discussion here.

Thaks for reading :)