# Example for a Schur-convex function that is not convex

Let $x \succ y$ be the majorization pre-order on real vectors. (Wikipedia link)

We say a function from real vectors to the reals is Schur convex if $x\succ y$ implies $f(x) ≥ f(y)$. With the result that if $x \succ y$ the vector $y$ is in the convex hull of permutations of $x$ is is easy to show that each convex and symmetric function is Schur convex.

Wikipedia states that the converse is not true (link). However each Schur-convex function is supposed to be symmetric.

Can anyone provide an example of a Schur-convex function that is not convex?

I know about the extra condition

$$(x_1 - x_2)\left(\frac{\partial{f}}{\partial{x_1}} - \frac{\partial{f}}{\partial{x_2}}\right) \le 0$$

for Schur-convexity but failed to construct a counter example with it for now. Maybe just some intuition is missing on how to use it?

• $f(x)=\log\sum_i x_i$, perhaps? – Michael Grant Feb 28 '15 at 23:14
• Also: $f(x)=-\prod_i x_i$ (defined for positive $x$). – Michael Grant Feb 28 '15 at 23:17
• @Michael While the $\log \sum_i x_i$ seems to me quite convex (as log of a convex function?) the second one does the job. Thank you! Do you want provide it as an answer? So i could accept it. – Permutation Mar 1 '15 at 11:20
• @Permutation $\log x$ is not convex... – Macavity Mar 1 '15 at 12:17
• The logarithm is definitely not convex. Indeed it seems to me that your stumbling block is an improper understanding of convexity, if you think that the log of a convex function should automatically be convex. – Michael Grant Mar 1 '15 at 15:09

## 1 Answer

Here's a straightforward way to construct a counterexample.

1. Select any nondecreasing non-convex real scalar function: $\log x$, $\sqrt{x}$, $-e^{-x}$, $\min\{x,0\}$, $x^3$, etc. Note that the first two of these are defined for positive/nonnegative $x$.
2. Apply that function to $\sum_i x_i$: $\log \sum_i x_i$, $\sqrt{\sum_i x_i}$, $-e^{-\sum_i x_i}$, $\min\{\sum_i x_i,0\}$, $\left(\sum_i x_i\right)^3$, etc.

The resulting functions are Schur-convex but not convex. That said, they are somewhat trivially Schur-convex, because $f(x)=f(y)$ if $\sum_i x_i=\sum_i y_i$, and the remaining conditions for majorization are irrelevant. In particular, they are not strictly Schur-convex.

$f(x)=-\prod_i x_i$ is an example that doesn't fit this mold, and is non-trivially Schur convex. Note that $f(x)=-\left(\prod_i x_i\right)^{1/n}$ is actually concave in $x$.

• May i add a suggestion how to generate examples that are strictly Schur-convex but not convex? Wouldn't this be possible by replacing in your step 2 the $\sum_i x_i$ by any strictly Schur-convex function like $\sum_i x_i^2$ for example? (And in addition choosing in step 1 an increasing function.) – Permutation Mar 2 '15 at 0:10
• Yes, it would seem to me something like that will work, some of the time. There will be certain cases where the composition will happen to turn out convex, though. For instance, $\sqrt{x}$ composed with $\sum_i x_i^2$ is the Euclidean norm! and therefore convex. The minimum and the cube will also be convex in that case. – Michael Grant Mar 2 '15 at 3:42