🔢 mathematics

Submultiplicative Polynomials in Combinatorics

This paper investigates the submultiplicative property of recursively defined polynomials associated with normalized sequences, establishing an effective criterion for this property as a Bessenrodt–Ono type inequality for the partition function.

Original authors: Krystian Gajdzica, Bernhard Heim, Markus Neuhauser, BłaĊej Żmija

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Krystian Gajdzica, Bernhard Heim, Markus Neuhauser, BłaĊej Żmija

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a magical factory that builds towers out of blocks. The number of blocks you use determines the height of the tower. In the world of math, there's a special rule called "submultiplicativity." It's a bit like a law of physics for these towers: if you build a tower of height $A$ and another of height $B$ , the number of ways to build them separately, multiplied together, should always be greater than or equal to the number of ways to build one giant tower of height $A+B$ .

For a long time, mathematicians knew this rule worked for some specific types of towers, like the famous "partition" towers (ways to break a number into smaller chunks). But they wondered: does this rule hold for all kinds of towers, especially when we start adding fancy decorations or changing the rules of how the blocks fit together?

Enter a team of four math explorers: Krystian Gajdzica, Bernhard Heim, Markus Neuhauser, and Błażej Żmija. They decided to investigate a whole new family of towers built using a recursive recipe. Think of this recipe as a set of instructions where the size of the next tower depends on the sizes of all the smaller towers you've already built, multiplied by some "magic numbers" (which they call a sequence $g(n)$ ).

The Big Discovery
The authors found a reliable way to predict when these decorated towers will obey the "submultiplicative" law. They didn't just guess; they built a strict mathematical test.

Here is the core of their finding: If your magic numbers ( $g(n)$ ) grow at a "just right" speed—specifically, if they are bigger than $n^\ell$ but smaller than $n^{\ell+1}$ for some whole number $\ell$ —then the tower rule holds true, provided you start your construction with a base height ( $x$ ) that is large enough.

They proved this with absolute certainty. It's not a simulation or a "maybe." They showed that if you follow their specific conditions, the inequality $P_n(x) \times P_m(x) \ge P_{n+m}(x)$ is mathematically guaranteed.

The "Magic Number" Rules
To make sure the rule works, the authors had to check the "magic numbers" carefully.

For simple, steady growth: If your magic numbers grow like $n^\ell$ (where $\ell$ is a whole number), the rule works perfectly if your starting height $x$ is at least $2^\ell$ . This means for $n^1$ , you need $x \ge 2$ ; for $n^2$ , you need $x \ge 4$ ; for $n^3$ , you need $x \ge 8$ ; and for $n^4$ , you need $x \ge 16$ .
For the "Goldilocks" zone: They also looked at cases where the magic numbers are between 1 and the sum of all divisors of $n$ $n$ (denoted as $\sigma(n)$ $σ (n)$ ). This covers a huge variety of real-world counting problems, like counting "k-colored partitions" (where blocks come in different colors).
- They proved that if your magic numbers stay within these bounds, the rule works for any starting height $x \ge 4$ .
- If you want to start at a lower height, like $x \ge 3$ , you need to pass a few extra safety checks. Specifically, the numbers for the 2nd, 3rd, 4th, and 6th steps must satisfy certain relationships (like $3g(2)(g(2)+3) \ge 2g(4)$ ). If these checks pass, the rule holds. If they don't, you just need to bump your starting height up to 4, and the rule is safe again.

What They Didn't Find (and Why It Matters)
The paper is very careful about what it doesn't claim. They didn't say this rule works for every possible sequence of numbers. If your magic numbers grow too fast or too slow, or if they behave erratically, the rule might break. They explicitly ruled out the idea that you can just pick any random sequence and expect the tower law to hold without checking the growth conditions.

They also didn't claim to solve the mystery of the "connective constant" for every lattice (a related problem in physics about how paths grow in grids), but they did show how their method connects to those famous problems.

The "Overpartition" Twist
One of the coolest parts of their work involves "overpartitions." Imagine a tower where some blocks can be "overlined" (marked as special). A mathematician named Li had a formula for this, but it was tricky because the starting number wasn't 1. The authors showed that by simply dividing the magic numbers by 2, they could fit this problem into their new framework. They proved that for these overlined towers, the submultiplicative rule holds true for any starting height $x \ge 1$ .

The Bottom Line
This paper doesn't just offer a guess; it provides a rigorous, step-by-step proof. It gives mathematicians a clear "checklist" to determine if a new type of combinatorial structure will follow the submultiplicative law. If the numbers grow at the right speed and pass the specific safety checks for small numbers, the law holds. If not, you might need to adjust your starting conditions. It's a powerful tool that turns a vague intuition about "tower building" into a precise, provable mathematical fact.

Technical Summary: Submultiplicative Polynomials in Combinatorics

Problem Statement
The paper investigates the submultiplicative property of recursively defined polynomials $P_n^g(x)$ associated with normalized arithmetic sequences $(g(n))_{n \in \mathbb{N}}$ (where $g(1)=1$ ). The property in question is the inequality:
$P_n^g(x) P_m^g(x) \geq P_{n+m}^g(x)$
for all $n, m \geq 1$ and $x$ within a specific domain. This property generalizes the Bessenrodt–Ono inequality for the partition function $p(n)$ and extends known results regarding $k$ -colored partitions and D'Arcais polynomials. The central problem is to establish effective, verifiable criteria under which this submultiplicative behavior holds for broad classes of sequences $g(n)$ , particularly those related to partition functions and combinatorial structures like commuting permutations.

Methodology
The authors employ a recursive analysis of the polynomials defined by:
$P_n^g(x) := \frac{x}{n} \sum_{k=1}^n g(k) P_{n-k}^g(x), \quad P_0^g(x) = 1.$
The core methodological contribution is the derivation of a sufficient criterion (Theorem 3.1) for submultiplicativity. This criterion relies on verifying a specific inequality at a base point $x_0$ :
$(\ast_n) \quad P_n^g(x_0) \geq \max_{1 \leq k \leq n} \frac{g(n+k)}{g(k)}.$
The proof strategy involves:

Inductive Proofs: Establishing that if $(\ast_n)$ holds for all $n$ , the submultiplicative inequality holds for all $a, b \geq 1$ and $x \geq x_0$ . This is demonstrated through Lemmas 3.2 and 3.3, which utilize induction on $n = a+b$ and the derivative properties of the polynomials (Lemma 2.1).
Estimation of Bounds: For specific sequences $g_\ell(n)$ satisfying growth conditions $n^\ell \leq g_\ell(n) \leq n^{\ell+1}$ , the authors estimate the maximum ratio $\max \frac{g(n+k)}{g(k)}$ and compare it against the polynomial values $P_n^g(x_0)$ .
Case Analysis: The authors perform detailed case-by-case verification for small values of $n$ (specifically $n \leq 8$ ) and use asymptotic estimates for larger $n$ to determine the threshold $x_0$ required for the inequality to hold.
Generalization: The framework is extended to sequences bounded by the divisor sum function $\sigma(n)$ , leading to conditions involving specific values of $g(2), g(3), g(4),$ and $g(6)$ .

Key Contributions and Results

Theorem 1.1 (Power Growth Sequences): For sequences $g_\ell(n)$ satisfying $n^\ell \leq g_\ell(n) \leq n^{\ell+1}$ , the polynomials $P_n^{g_\ell}(x)$ are submultiplicative for all $x \geq x_0$ , where $x_0 = g_\ell(2)$ . The validity of the criterion $(\ast_n)$ is confirmed for specific ranges of $n$ depending on $\ell$ (e.g., $n \leq 8$ for $\ell=1$ , $n \leq 3$ for $\ell=2$ , etc.).
Theorem 1.2 (Bounded by Divisor Sum): For any normalized sequence $g(n)$ such that $1 \leq g(n) \leq \sigma(n)$ , the submultiplicative property holds for all $x \geq 4$ . Furthermore, if the sequence satisfies specific algebraic conditions on $g(2), g(3), g(4),$ and $g(6)$ (specifically $3g(2)(g(2)+3) \geq 2g(4)$ and $g(3)(2g(3)+9g(2)+9) \geq 2g(6)$ ), the property holds for the tighter bound $x \geq 3$ .
Applications to Specific Combinatorial Objects:
- D'Arcais and Plane Partitions: The results generalize submultiplicativity for polynomials associated with $\sigma_d(n)$ (related to plane partitions for $d=2$ ) and $\lambda_\ell(n)$ (related to commuting $\ell$ -tuples in symmetric groups).
- $k$ -Regular and $k$ -Colored Partitions: The paper confirms that the sequence of $k$ -regular partitions with $r$ -colors is submultiplicative for all $k > 1$ and $r \geq 3$ .
- Overpartitions: The authors apply a modified version of their criterion to the overpartition function (Li's polynomials), proving submultiplicativity for $x \geq 1$ .
Corollaries: Specific bounds for $x$ are provided for families $P_{\sigma_d}^n(x)$ ( $x \geq 2d+1$ ), $P_{\lambda_\ell}^n(x)$ ( $x \geq 2^{\ell+1}-1$ ), and $P_{\psi_\ell}^n(x)$ ( $x \geq 2^\ell$ ).

Significance
The paper provides a unified and effective criterion for establishing the submultiplicative property of a wide class of combinatorial polynomials. By abstracting the problem to the behavior of the generating sequence $g(n)$ , the authors generalize previous isolated results concerning the partition function, $k$ -colored partitions, and D'Arcais polynomials. The work bridges the gap between specific combinatorial inequalities (like Bessenrodt–Ono) and a broader structural theory of recursively defined polynomials. The authors explicitly state that their results cover all possible $A$ -partition functions where $A$ is a subset of natural numbers containing 1, thereby offering a comprehensive tool for analyzing the multiplicative behavior of partition-related sequences. The paper does not claim to solve the general problem for all possible sequences but provides a robust framework for a significant and diverse set of arithmetic functions arising in combinatorics and statistical physics.

More like this