# discrete convexity arising in a simple discrete optimization problem

Let $S$ be a fixed integer satisfying $S \ge 1$, let $a$ range over the integers between $1$ and $S$ inclusive, and for $i = 1, \dotsc, a$, let each $x_i$ range over the nonnegative integers, such that the $x_1 + \dotsc + x_a = S$ will be a partition of $S$.

Consider the discrete, constrained optimization problem defined by: $$f(a; S) = \max\limits_{\{ x_i\}}\Bigl[ \ln\big( \prod\limits_{i = 1}^{a} x_i \bigr) \colon \;\sum\limits_i^{a} x_i = S \Bigr]$$

It is straightforward to determine the explicit value of $f(a; S)$ in terms of the floor $\lfloor \tfrac{S}{a} \rfloor$. Basically, the $x_i$ have to be as uniform as possible while remaining positive integers summing to $S$.

Intuition and numerical evidence suggest that $f(a;S)$ is discretely concave with respect to $a$, in the sense that $$f(a; S) \ge \tfrac{1}{2} f(a-1; S) + \tfrac{1}{2} f(a+1; S)$$ for all integers $a$ in the range $1 < a <S$.

Can anyone suggest a simple proof of this fact? It is easy to show via Jensen's inequality that $f(a; S)$ lies below the concave function $a \ln (S/a)$, but that of course is not enough. Induction on $S$ does not appear terribly promising.

## 1 Answer

No sooner did I submit this than I realized that there is indeed a simple answer:

Note that $f(2a; 2S) = 2 f(a;S)$. But by writing $2S = S + S$ and partitioning one $S$ into a sum of $(a-1)$ terms and the other into a sum of $(a+1)$ terms, because $f(2a,2S)$ is defined as an optimum, we see that $f(2a, 2S) \ge f(a-1, S) + f(a+1, S)$.