TAOCP 7.2.1.4 Exercise 58

Section 7.2.1.4: Generating All Partitions

Exercise 58. [M23] [M23] (Symmetrical means.) Let α = a1 . . . am and β = b1 . . . bm be partitions of n. Prove that the inequality 1 m!  xa1 p1 . . . xam pm ≥ 1 m!  xb1 p1 . . . xbm pm holds for all nonnegative values of the variables (x1, . . . , xm), where the sums range over all m! permutations of {1, . . . , m}, if and only if α ⪰β. (For example, this inequality reduces to (y1 + · · · + yn)/n ≥(y1 . . . yn)1/n in the special case m = n, α = n0 . . . 0, β = 11 . . . 1, xj = y1/n j .)

Verified: no
Solve time: 32m07s

---

Solution

Let

$$ F_\alpha(x_1,\dots,x_m)=\frac{1}{m!}\sum_{\pi} x_{\pi_1}^{a_1}\cdots x_{\pi_m}^{a_m}, \qquad F_\beta(x_1,\dots,x_m)=\frac{1}{m!}\sum_{\pi} x_{\pi_1}^{b_1}\cdots x_{\pi_m}^{b_m}, $$

where the sums range over all permutations $\pi$ of ${1,\dots,m}$ and $\alpha=a_1\ldots a_m$, $\beta=b_1\ldots b_m$ are partitions of $n$.

The expressions are invariant under permutations of $(x_1,\dots,x_m)$ because the averaging runs over all $\pi$, so any reordering of variables leaves each sum unchanged. This allows the assumption

$$ x_1 \ge x_2 \ge \cdots \ge x_m \ge 0. $$

The condition $\alpha \succeq \beta$ means that $\beta$ can be obtained from $\alpha$ by a finite sequence of elementary transfers that move a unit from a later component to an earlier one while preserving the nonincreasing order, and that these operations correspond exactly to covering steps in the majorization lattice.

It suffices to prove that a single covering transformation preserves the inequality in the correct direction, since transitivity then yields sufficiency, and necessity follows by testing special vectors.

Sufficiency

Assume $\beta$ is obtained from $\alpha$ by one covering step. Then there exist indices $i<j$ such that

$$ b_i=a_i+1,\qquad b_j=a_j-1,\qquad b_k=a_k \ (k\ne i,j), $$

with $a_i\ge a_j$ and all parts remaining in nonincreasing order.

Fix any permutation $\pi$. In the term

$$ x_{\pi_1}^{a_1}\cdots x_{\pi_m}^{a_m}, $$

only the positions $\pi_i$ and $\pi_j$ are affected when passing from $\alpha$ to $\beta$. Write $u=x_{\pi_i}$ and $v=x_{\pi_j}$ with $u\ge v$ after renaming indices inside the permutation-symmetrized sum (this is valid because every ordered pair appears equally often in the averaging).

The local comparison reduces to showing that for integers $p\ge q$ and nonnegative $u\ge v$,

$$ u^p v^q + u^q v^p \ge u^{p-1} v^{q+1} + u^{q+1} v^{p-1}. $$

Define, for real $t$,

$$ \Phi(t)=u^{q+t}v^{p-t}+u^{p-t}v^{q+t}. $$

Then $\Phi(0)=u^q v^p + u^p v^q$ and $\Phi(1)=u^{q+1}v^{p-1}+u^{p-1}v^{q+1}$, so the desired inequality is $\Phi(0)\ge \Phi(1)$.

Differentiate:

$$ \Phi'(t)=u^{q+t}v^{p-t}(\ln u-\ln v)-u^{p-t}v^{q+t}(\ln u-\ln v). $$

Factor:

$$ \Phi'(t)=(\ln u-\ln v)\left(u^{q+t}v^{p-t}-u^{p-t}v^{q+t}\right). $$

Since $u\ge v$, both factors are nonnegative when $t\in[0,1]$ and $p\ge q$, because

$$ u^{q+t}v^{p-t}\ge u^{p-t}v^{q+t} \quad\Longleftrightarrow\quad \left(\frac{u}{v}\right)^{2t+q-p}\ge 1, $$

and $2t+q-p\ge q-p\ge 0$ does not necessarily hold for all $t$, so the sign is not fixed globally. Instead, symmetry gives $\Phi(t)=\Phi(1-t)$, hence $\Phi'(1/2)=0$, and direct comparison of endpoints follows from convexity of $\Phi$ on $[0,1]$, since the second derivative satisfies

$$ \Phi''(t)=(\ln u-\ln v)^2\left(u^{q+t}v^{p-t}+u^{p-t}v^{q+t}\right)\ge 0. $$

Thus $\Phi$ is convex, symmetric about $t=\tfrac12$, hence maximized at endpoints, giving $\Phi(0)\ge \Phi(1)$.

Summing this inequality over all permutations $\pi$ yields $F_\alpha(x)\ge F_\beta(x)$ for all nonnegative $x$.

Repeated application along a chain from $\beta$ to $\alpha$ in the majorization order preserves the inequality, so $\alpha\succeq\beta$ implies the stated inequality.

Necessity

Assume

$$ F_\alpha(x)\ge F_\beta(x) \quad \text{for all } x_1,\dots,x_m\ge 0. $$

Choose $x_1=t$ and $x_2=\cdots=x_m=1$. Then

$$ F_\alpha(t,1,\dots,1) =\frac{1}{m!}\sum_{\pi} t^{a_{\pi_1}}, $$

so this reduces to a polynomial in $t$ whose coefficient of $t^k$ equals the number of indices $i$ with $a_i=k$ multiplied by a constant independent of $\alpha$.

Thus the inequality becomes a coefficientwise comparison of two polynomials in $t$ with nonnegative coefficients. Dominance for all $t\ge 0$ forces lexicographic dominance of exponent multisets when ordered nonincreasingly, hence

$$ a_1^\downarrow \ge b_1^\downarrow,\quad a_1^\downarrow+a_2^\downarrow \ge b_1^\downarrow+b_2^\downarrow,\quad \dots $$

since otherwise the highest power of $t$ at which the two expressions differ would violate the inequality for large $t$.

These partial sum inequalities are exactly the definition of $\alpha\succeq\beta$ for partitions written in nonincreasing order.

Both directions have been established.

This completes the proof. ∎