Maximal entropy of integer partitions of $n$

Question

Let $\operatorname{Part}(n)$ be the set of integer partitions of $n$.

A partition $p \in \operatorname{Part}(n)$ has $k$ summands and $d$ distinct summand $n_i$, with $d \leq k$ and $d$ frequencies $f_i$ such that $\sum_i^d f_i \cdot n_i = n$.

Notice that $\sum_i^d f_i = k$.

The probability of $n_i$ within a given partition $p$ is thus $P(n_i) = f_i/k$.

This allows to define an entropy function on $\operatorname{Part}(n)$, $H(p) = -\sum_i^d P(n_i)\cdot \log(P(n_i))$.

Note that I etched this definition of $H$ of a partition of $n$ myself so that it may be non-standard.

I am looking for the maximal value of $H$ for a given $n$: $H_{\max}(n)$.

I have crunched some values for small $n$ by enumerating $k$-compositions of $n$ and computing $H$ on the underlying partition.

The minimum of $H$ is $0$ and occurs notably when $k=1$ or $k=n$. The maximum is more interesting. For $n=12$, it apparently occurs when $k=4$. For $n=16$, when $k=5$. For $n=24$, when $k=6$. For $n=32$, when $k=7$.

I was initially looking for the maximum values for given $k$ and $n$. I am now interested in the maximum for a given $n$, regardless of $k$.

I believe this may have musical applications. My intent is to filter rhythms by the entropies of their underlying partitions using fuzzy logic. Having an easily computable function for the maximum value of $H$ would make it possible to normalize its values for a specific $p$ and filter by percentage for any $n$.

Next thing I'll try is to compute $H_{\max}(n)$ for small $n$ then fit the curve with some regression model.

UPDATE: Enlightened by aorq's comment on how to obtain the optimal $k$ given $n$, I was able to compute $H_{max}(n)$ quite rapidly for the specific values I wanted by enumerating the compositions of $k$ to obtain frequencies $f_i$ that maximize $H$.

Here are the values if you are interested:

$n=12, k=4, H_{max}=1.3862943611198906$

$n=16, k=5, H_{max}=1.6094379124341005$

$n=24, k=6, H_{max}=1.7917594692280547$

$n=32, k=7, H_{max}=1.945910149055313$

$n=96, k=13, H_{max}=2.5649493574615376$

$n=192, k=19, H_{max}=2.9444389791664403$

$n=384, k=27, H_{max}=3.2958368660043296$

Thanks again sir!!

OTHER UPDATE: $H_{max} = \log(\lfloor (\sqrt{1+8n}-1)/2\rfloor)$ or $\log(k)$.

Answer 1

To summarize and make more complete what has already been figured out:

Claim: Let $T_i = {i+1 \choose 2}$ for all $i$. Let $j$ be the integer such that $T_j \leq n < T_{j+1}$. Then $H_{max}(n) = \log(j)$.

Proof: Write $T_j = 1 + \dots + (j-1) + j$. By increasing the last summand, we obtain a partition of $n$ containing $j$ unique summands each with frequency one, achieving entropy $\log(j)$. On the other hand, there is no partition of $n$ with greater than $j$ unique summands. If there were, then $n$ would be at least $1+\dots +(j+1) = T_{j+1}$. As every partition contains at most $j$ unique summands, $H_{max}(n)$ is at most the maximum entropy of a distribution on $j$ items, $\log(j)$.

---

More detailed proof. Given a partition $p \in Part(n)$, let $d_p$ be the number of distinct summands and $P_p$ the induced probability distribution. Observe that the support size of $P_p$ is $d_p$, so $H(p) = H(P_p) \leq \log(d_p)$. (Recall $H(p)$ is defined to be the Shannon entropy of $P_p$.)

We have $\max_{p \in Part(n)} d_p = j$ where $j$ is defined in the claim. To prove this, observe that if $d_p \geq j+1$, then $n \geq 1+2+\cdots+(j+1) = T_{j+1}$, a contradiction. (In more detail, for any partition of $n$ containing at least $j+1$ distinct summands, we can sort them ascending and obtain $n \geq n_1+\cdots+n_{j+1}$ with $n_i \geq i$ for all $i$, hence $n \geq T_{j+1}$.)

By the above claims, $H_{\max}(n) \leq \max_{p \in Part(n)} \log(d_p) = \log(j)$. We now exhibit a partition $p$ of $n$ achieving this upper bound. The partition is $1+\cdots+(j-1)+x=n$, where $x = n - T_{j-1} = n - (1+\cdots+(j+1))$. By assumption of $n \geq T_j$, we have $x \geq j$, so $x$ is distinct from all other summands, which are all pairwise distinct. So $d_p = j$ and $P_p$ is the uniform distribution on $\{1,\dots,j-1,x\}$. We have $H(p) = H(P_p) = \log(j)$.

We have shown that $H_{\max}(n) \leq \log(j)$, and found a partition $p$ of $n$ with $H(p) = \log(j)$, so $H_{\max}(n) = \log(j)$.

Answer 2

That's an interesting question. There is nothing non-standard in your definition: it is precisely the standard general definition applied in a rather specific situation: the base probability space is finite with the uniform distribution, and you only consider partitions with pairwise distinct weights. According to one of the central properties of entropy, if the number of elements $N$ of a partition $\alpha$ is fixed, then the entropy $H(\alpha)$ does not exceed $\log N$, and the equality is attained if and only if all elements of $\alpha$ have the same weight $1/N$. Thus, on order to maximize entropy of partition, one should make its weight distribution as uniform as possible. However, you impose the constraint that all weights have to different. It should be quite straightforward that for $N=1+\dots +n=n(n+1)/2$ the maximum is attained for the partiton $N=1+2+\dots +n$. As for other values of $N$, it depends on how much refinement you want to achieve.