# Number of integral points in a polytope

I'm trying to count the number of integral solutions to the set of equations and inequalities

$$$$\begin{split} a_0 + a_1+a_2+a_3+a_4 = C \\ a_i \geq 0 \quad i \in\{0,1,2,3,4\} \\ a_0 \geq a_1 \geq a_2 \\ a_0 \geq a_3 \geq a_4 \\ \end{split}$$$$

I know that the number of integral solutions for the first two equations is $$\binom{C+4}{4}$$. I've also seen when the $$a_i$$ are bounded by constants which has a nice generating function formulation. But I am stuck in figuring it out with the multivariable constraints.

I would greatly appreciate any help or ideas in how to solve this problem.

• en.wikipedia.org/wiki/Partition_(number_theory) – Dave Dec 27 '19 at 5:56
• Hi Dave, anything more specific? – WorkerBee Dec 27 '19 at 6:04
• What you're looking for is the number of integer partitions of $C$ with at most five parts (it is at most since you are allowing zeros). See en.wikipedia.org/wiki/… specifically. – Dave Dec 27 '19 at 6:06
• First, while I think the problems are related, they are not exactly the same since the solutions I'm looking for allow for different order of summands which partition theory ignores, unless you have a link where they don't. Second, I am not just trying to partition into 5 parts but also constraint the size of each part dependent on the sizes of the others. – WorkerBee Dec 27 '19 at 6:12
• The constraint that $a_0\geq a_1\geq\cdots\geq a_4$ takes care of the order. An equivalent definition of a partition of $C$ is a sequence $(a_j)_{j\geq 0}$ such that $a_j\geq a_{j+1}$ and $\sum_j a_j=C$. – Dave Dec 27 '19 at 6:14

Let us define $$f(n)$$ as the number you are looking for, with $$C$$ replaced by $$n$$.

The sequence $$(f(n))_n$$ satisfies the linear recurrence relation: $$f(n) - f(n-1) - f(n-2) + f(n-5) + f(n-6) + f(n-7) - f(n-8) - f(n-9) - f(n-10) + f(n-13) + f(n-14) - f(n-15) = 0.$$

From here, you can use any of your favorite method to solve it.

The characteristic polynomial decomposes as $$(x - 1)^5(x + 1)^2(x^2 + 1)(x^2 + x + 1)(x^4 + x^3 + x^2 + x + 1).$$ It can also be written as $$(x - 1)(x^2 - 1)(x^3 - 1)(x^4 - 1)(x^5 - 1)$$. Notice that every root is a root of unity, with common multiple $$60$$. Hence the $$60$$ subsequences $$(f(60n + k))_n$$ are all polynomials (of degree $$4$$) in $$n$$.

It is possible to write down a list of all these polynomials. They will look like: $$\begin{eqnarray*} f(60n + 0) &=& 27000n^4 + 8100n^3 + 855n^2 + 39n\\ f(60n + 1) &=& 27000n^4 + 9900n^3 + 1305n^2 + 71n\\ f(60n + 2) &=& 27000n^4 + 11700n^3 + 1845n^2 + 127n + 2\\ f(60n + 3) &=& 27000n^4 + 13500n^3 + 2475n^2 + 195n + 5\\ f(60n + 4) &=& 27000n^4 + 15300n^3 + 3195n^2 + 293n + 9\\ f(60n + 5) &=& 27000n^4 + 17100n^3 + 4005n^2 + 409n + 14\\ f(60n + 6) &=& 27000n^4 + 18900n^3 + 4905n^2 + 561n + 23\\ f(60n + 7) &=& 27000n^4 + 20700n^3 + 5895n^2 + 737n + 33\\ f(60n + 8) &=& 27000n^4 + 22500n^3 + 6975n^2 + 955n + 48\\ f(60n + 9) &=& 27000n^4 + 24300n^3 + 8145n^2 + 1203n + 65\\ f(60n + 10) &=& 27000n^4 + 26100n^3 + 9405n^2 + 1499n + 88\\ f(60n + 11) &=& 27000n^4 + 27900n^3 + 10755n^2 + 1831n + 115\\ f(60n + 12) &=& 27000n^4 + 29700n^3 + 12195n^2 + 2217n + 150\\ f(60n + 13) &=& 27000n^4 + 31500n^3 + 13725n^2 + 2645n + 189\\ f(60n + 14) &=& 27000n^4 + 33300n^3 + 15345n^2 + 3133n + 238\\ f(60n + 15) &=& 27000n^4 + 35100n^3 + 17055n^2 + 3669n + 294\\ f(60n + 16) &=& 27000n^4 + 36900n^3 + 18855n^2 + 4271n + 361\\ f(60n + 17) &=& 27000n^4 + 38700n^3 + 20745n^2 + 4927n + 436\\ f(60n + 18) &=& 27000n^4 + 40500n^3 + 22725n^2 + 5655n + 526\\ f(60n + 19) &=& 27000n^4 + 42300n^3 + 24795n^2 + 6443n + 625\\ f(60n + 20) &=& 27000n^4 + 44100n^3 + 26955n^2 + 7309n + 741\\ f(60n + 21) &=& 27000n^4 + 45900n^3 + 29205n^2 + 8241n + 869\\ f(60n + 22) &=& 27000n^4 + 47700n^3 + 31545n^2 + 9257n + 1016\\ f(60n + 23) &=& 27000n^4 + 49500n^3 + 33975n^2 + 10345n + 1178\\ f(60n + 24) &=& 27000n^4 + 51300n^3 + 36495n^2 + 11523n + 1362\\ f(60n + 25) &=& 27000n^4 + 53100n^3 + 39105n^2 + 12779n + 1562\\ f(60n + 26) &=& 27000n^4 + 54900n^3 + 41805n^2 + 14131n + 1788\\ f(60n + 27) &=& 27000n^4 + 56700n^3 + 44595n^2 + 15567n + 2034\\ f(60n + 28) &=& 27000n^4 + 58500n^3 + 47475n^2 + 17105n + 2308\\ f(60n + 29) &=& 27000n^4 + 60300n^3 + 50445n^2 + 18733n + 2604\\ f(60n + 30) &=& 27000n^4 + 62100n^3 + 53505n^2 + 20469n + 2933\\ f(60n + 31) &=& 27000n^4 + 63900n^3 + 56655n^2 + 22301n + 3287\\ f(60n + 32) &=& 27000n^4 + 65700n^3 + 59895n^2 + 24247n + 3677\\ f(60n + 33) &=& 27000n^4 + 67500n^3 + 63225n^2 + 26295n + 4096\\ f(60n + 34) &=& 27000n^4 + 69300n^3 + 66645n^2 + 28463n + 4554\\ f(60n + 35) &=& 27000n^4 + 71100n^3 + 70155n^2 + 30739n + 5045\\ f(60n + 36) &=& 27000n^4 + 72900n^3 + 73755n^2 + 33141n + 5580\\ f(60n + 37) &=& 27000n^4 + 74700n^3 + 77445n^2 + 35657n + 6150\\ f(60n + 38) &=& 27000n^4 + 76500n^3 + 81225n^2 + 38305n + 6769\\ f(60n + 39) &=& 27000n^4 + 78300n^3 + 85095n^2 + 41073n + 7428\\ f(60n + 40) &=& 27000n^4 + 80100n^3 + 89055n^2 + 43979n + 8139\\ f(60n + 41) &=& 27000n^4 + 81900n^3 + 93105n^2 + 47011n + 8894\\ f(60n + 42) &=& 27000n^4 + 83700n^3 + 97245n^2 + 50187n + 9707\\ f(60n + 43) &=& 27000n^4 + 85500n^3 + 101475n^2 + 53495n + 10568\\ f(60n + 44) &=& 27000n^4 + 87300n^3 + 105795n^2 + 56953n + 11491\\ f(60n + 45) &=& 27000n^4 + 89100n^3 + 110205n^2 + 60549n + 12467\\ f(60n + 46) &=& 27000n^4 + 90900n^3 + 114705n^2 + 64301n + 13510\\ f(60n + 47) &=& 27000n^4 + 92700n^3 + 119295n^2 + 68197n + 14611\\ f(60n + 48) &=& 27000n^4 + 94500n^3 + 123975n^2 + 72255n + 15785\\ f(60n + 49) &=& 27000n^4 + 96300n^3 + 128745n^2 + 76463n + 17020\\ f(60n + 50) &=& 27000n^4 + 98100n^3 + 133605n^2 + 80839n + 18334\\ f(60n + 51) &=& 27000n^4 + 99900n^3 + 138555n^2 + 85371n + 19716\\ f(60n + 52) &=& 27000n^4 + 101700n^3 + 143595n^2 + 90077n + 21181\\ f(60n + 53) &=& 27000n^4 + 103500n^3 + 148725n^2 + 94945n + 22719\\ f(60n + 54) &=& 27000n^4 + 105300n^3 + 153945n^2 + 99993n + 24347\\ f(60n + 55) &=& 27000n^4 + 107100n^3 + 159255n^2 + 105209n + 26053\\ f(60n + 56) &=& 27000n^4 + 108900n^3 + 164655n^2 + 110611n + 27855\\ f(60n + 57) &=& 27000n^4 + 110700n^3 + 170145n^2 + 116187n + 29741\\ f(60n + 58) &=& 27000n^4 + 112500n^3 + 175725n^2 + 121955n + 31729\\ f(60n + 59) &=& 27000n^4 + 114300n^3 + 181395n^2 + 127903n + 33807\\ \end{eqnarray*}$$

Explanation on the recurrence relation:

It is possible to deduce that recurrence relation by hand.

Firstly, we calculate $$f(n)$$ by partitioning the set: there are four subsets, $$A = \{a_2 = 0\}$$, $$B = \{a_4 = 0\}$$, $$C = \{a_2 = a_4 = 0\}$$, $$D = \{a_2 \neq 0 \neq a_4\}$$. It is clear that $$f(n) = |A| + |B| - |C| + |D|$$.

It is also clear that $$|A| = |B| = |\{(a_0, a_1, a_2, a_3):a_0 + a_1 + a_2 + a_3 = n, a_0 \geq a_1 \geq a_2 \geq 0, a_0 \geq a_3 \geq 0\}|.$$We denote this number by $$g(n)$$.

We also have $$|C| = |\{(a_0, a_1, a_3):a_0 + a_1 + a_3 = n, a_0 \geq a_1 \geq 0, a_0 \geq a_3 \geq 0\}|.$$ We denote this number by $$h(n)$$.

Finally, by mapping every $$a_i$$ to $$a_i - 1$$, we see that $$|D| = f(n - 5)$$.

Thus we obtain: $$f(n) = 2g(n) - h(n) + f(n - 5)$$.

Now if we do the same analysis for $$g(n)$$ (i.e. partitioning into $$\{a_2 = 0\}$$, $$\{a_3 = 0\}$$, $$\{a_2 = a_3 = 0\}$$, $$\{a_2 \neq 0 \neq a_3\}$$), and also for $$h(n)$$, we get similar recurrence relations, but involving again new functions such as $$|\{(a_0, a_1, a_2): a_0 + a_1 + a_2 = n, a_0 \geq a_1 \geq a_2 \geq 0\}|$$.

Each step will reduce the problem to simpler functions. Repeating this procedure, we will finally arrive at a recurrence formula for the original function $$f$$.

While this is totally doable by hand, it's probably a complicated task and has to be done very carefully. Therefore, I didn't use this approach.

Instead, seeing that a linear recurrence relation (of reasonable order, say $$< 100$$) must exist, I wrote a program to generate the sequence and then found the recurrence relation directly, by solving linear equations. That's the result in the beginning of the answer.

• Please tell me you used some kind of software to generate that list, and that you didn't type it all by hand... – Math1000 Dec 27 '19 at 7:23
• I'm impressed but a little bit confused. Can you elaborate how you converted my problem into that recurrence relationship? – WorkerBee Dec 27 '19 at 8:15
• @Math1000 Yes, some kind of software was used to generate that list (: – WhatsUp Dec 27 '19 at 15:07
• @WorkerBee I'll add some explanation. – WhatsUp Dec 27 '19 at 15:07