School’s started back up again. I thought I’d spend today writing a shorter post, discussing a neat result that we used last quarter here at UCLA.
The proof involves an almost-comically overpowered argument to prove an inequality that can be done by simple but inaesthetic means. (After coming up with an argument, I found on the internet that the underlying result has a name! It forms the title of this post; moreover, it seems to be somewhat-known in math competition circles.) We’ll invoke the Lebesgue FTC and some ideas from measure theory here; I feel quite tempted to post this to the MathOverflow ‘nuking mosquitoes’ page.1
A variant of Karamata’s inequality2 states the following: \((x_i)_{i = 1}^{n} \subseteq \mathbb{R}\) and \((y_i)_{i = 1}^{n} \subseteq \mathbb{R}\) are decreasing3 collections of real numbers satisfying $$\sum_{i = 1}^{k} x_i \leq \sum_{i = 1}^{k} y_i$$ in \(\mathbb{R}\) for all \(k \in \{1, \dots, n\}\). Suppose that \(f : \mathbb{R} \to \mathbb{R}\) is a convex, increasing function. Then $$\sum_{i = 1}^{n} f(x_i) \leq \sum_{i = 1}^{n} f(y_i).$$
We note that the result admits an equivalent reformulation, as follows:
Theorem: Suppose \(\Phi : (0, \infty) \to \mathbb{R}\) is such that \(t \mapsto \Phi(e^t)\) is a convex, increasing function on \(\mathbb{R}\).4 Suppose that we have collections of numbers \((a_j)_{j = 1}^{n}, (b_j)_{j = 1}^{n} \subseteq (0, \infty)\), each arranged in decreasing order, such that $$\prod_{j = 1}^{k} b_j \leq \prod_{j = 1}^{k} a_j$$ holds in \(\mathbb{R}\) for each \(k \in \{1, \dots, n\}\). Then $$\sum_{j = 1}^{n} \Phi(b_j) \leq \sum_{j = 1}^{n} \Phi(a_j).$$
The equivalence of this multiplicative statement with the additive Karamata’s inequality is quite clear: simply take \(\Phi(x) = f(\ln(x))\), and \(a_i = e^{y_i}\), \(b_i = e^{x_i}\).
We also remark that if \(\Phi(0)\) is defined and the function extends continuously to \([0, \infty)\), then the result holds in the more general setting of \((a_i)_{i = 1}^{n}, (b_i)_{i = 1}^{n} \subseteq [0, \infty)\).
This inequality is useful in certain contexts; for instance, proving the Weyl and Horn inequalities regarding the (singular/eigen)values of a compact operator on Hilbert space.
The proofs of Karamata’s inequality that I’ve found (e.g., 1, 2) are certainly elementary, but not very aesthetically-pleasing. (In my opinion, at least; not that it’s worth very much.) They reduce to the three-chords lemma for convex functions, and then perform lots of tricky summing; to me, this does not give much intuition behind the result.
Instead, we prove Karamata’s inequality by another means, using the equivalent multiplicative formulation; we follow an approach suggested by Professor Killip in Spring 2025’s MATH 255A course at UCLA.5
As Professor Killip described it, we may note that the result follows for a certain family of special functions (cones, or more precisely, ReLUs; with varying aperture and position), and then proceeds to approximate general convex functions by such (essentially, a convex function is an “average” of these “corners”). To my analysis-trained mind, this approach is much easier to follow. Here, I reproduce the proof I have in my notes, near-verbatim:
Proof: By perturbing the \(a_j\) by \(\epsilon > 0\) upwards (which also transforms each inequality to strict), then selecting \(\eta > 0\) so small that the inequalities remains valid for \(b_j + \eta\), the product property will be preserved and we may assume the \(a_j\) and \(b_j\) are all strictly positive (if they weren’t so already).
Taking logarithms, we have $$\sum_{j = 1}^{n} \log(b_j) \leq \sum_{j = 1}^{n} \log(a_j)$$ in \(\mathbb{R}\). So if \(\mathcal{F}\) is the subclass of our family under consideration for which the inequality generally holds, we have \(\log \in \mathcal{F}\).
We now claim for every \(\lambda > 0\), \(f_{\lambda} \in \mathcal{F}\), where \(f_{\lambda}(x) = \log_{+}(x / \lambda) = \max(\log(x / \lambda), 0)\). Indeed, \(f_{\lambda}(x) = \log(x) \ – \, \log(\lambda)\) for \(x \geq \lambda\), and is \(0\) otherwise. So for the first \(n_{\lambda}\)-many values of \((b_j)\) where \(b_j \geq \lambda\), we use the relevant product inequality, giving $$\sum_{j = 1}^{n_{\lambda}} \log(b_j) \leq \sum_{j = 1}^{n_{\lambda}} \log(a_j).$$ We may subtract \(n_{\lambda} \log(\lambda)\) to obtain $$\sum_{j = 1}^{n_{\lambda}} f_{\lambda}(b_j) \leq \sum_{j = 1}^{n_{\lambda}} f_{\lambda}(a_j).$$ Then for each \(j > n_{\lambda}\), we have \(f_{\lambda}(b_j) = 0\), as \(b_j < \lambda\). Meanwhile, because \(f_{\lambda}(x) = \log_{+}(x / \lambda) \geq 0\), adding \(a_j\) terms on the right only strengthens the inequality. So, adding the remaining terms, we obtain $$\sum_{j = 1}^{n} f_{\lambda}(b_j) \leq \sum_{j = 1}^{n} f_{\lambda}(a_j).$$
Thus each \(f_{\lambda} \in \mathcal{F}\). Clearly, \(\mathcal{F}\) is a positive cone. We will show that for any map \(\Phi\) meeting our specifications, on any compact \(K \subseteq \mathbb{R}\), there exists a corresponding sequence of (finite) positive linear combinations \(f_n = \sum_i c_i^n f_{\lambda_i^n}\), the \(f_{\lambda}\) as above, such that \(\lim_{n \to \infty} f_n \circ \exp = \Phi \circ \exp\) everywhere in \(K\).
We now write this inequality as $$\sum_{j = 1}^{n} (f_{\lambda} \circ \exp)(\log(b_j)) \leq \sum_{j = 1}^{n} (f_{\lambda} \circ \exp)(\log(a_j)).$$
We observe that $$(f_{\lambda} \circ \exp)(x) = \max(\log(\exp(x) / \lambda), 0) = \max(x \ – \, \log(\lambda), 0).$$
Consider any \(\Phi\) such that \(t \mapsto \Phi(e^t)\) is increasing and convex. By convexity (which implies locally-finite Lipschitz bounds), and the fundamental theorem of calculus for Lebesgue integrals, we may write \(g(t) = \Phi(e^t)\) as $$g(t) = g(a) + \int_{a}^{t} h(s) \, ds$$ for any choice of \(a \in \mathbb{R}\), where \(h(s)\) is the (a.e.-existent) pointwise derivative of \(g\). By properties of convex functions, we also know this is a.e.-equal to the everywhere-existent left (or right) derivative of \(g\), this means \(h\) can be corrected to equal an increasing function. And since \(g\) itself is increasing, the left (or right) derivative is everywhere positive.
We now observe that $$(f_{\lambda} \circ \exp)(x) = \max(x \ – \, \log(\lambda), 0) = \int_{a}^{x} \chi_{(\log(\lambda), \infty)}(t) \, dt.$$
Now, we claim that any increasing, nonnegative function \(h : \mathbb{R} \to [0, \infty)\) can be approximated locally-uniformly and from below by a sequence of positive linear combinations of indicator functions of the form $$\sum_{i = 1}^{N} c_i \chi_{R_i},$$ for \(c_i > 0\) and half-infinite rays \(R_i\) either of the form \((\log(\lambda_i), \infty)\) or \([\log(\lambda_i), \infty)\) (open or closed), where each \(\lambda_i > 0\).
Indeed, we may subdivide the (bounded) range of \(h\) on any large interval \((- L, L)\) into subintervals of length \(2^{- k}\), and by monotonicity, the preimages \(\{h > n / 2^k\}\) will be right-facing rays in \((- L, L)\). Then we form the sequence \((R_n)\). With this, we have $$\sum_{n = 1}^{M_k} \frac{1}{2^k} \chi_{R_n}(t) \leq h(t) \leq \frac{1}{2^k} + \sum_{n = 1}^{M_k} \frac{1}{2^k} \chi_{R_n}(t)$$ for all \(t \in (- L, L)\).
Since \(\log\) maps \((0, \infty)\) continuously onto \((- \infty, \infty)\), we may select appropriate \(\lambda_i\) to form the left-endpoints of the open or closed rays \(R_i\).
In this manner approximating \(h = g’\), on any interval \((- L, L)\), we obtain $$g(x) \ – \, g(- L) = \int_{- L}^{x} h(t) \, dt = \sum_{i = 1}^{M_k} 2^{- k} (f_{\lambda_i} \circ \exp)(x) + O(2^{- k} L).$$
We may select some sufficiently-large \(L > \max(|\log(a_j)|, |\log(b_j)|)\). Now, by taking positive linear combinations of the fundamental \(f_{\lambda}\)-inequality above, for various values of \(\lambda\), then passing to the limit, we obtain convergence of the Heaviside approximants to \(g(x) \ – \, g(a)\) for each term: $$\sum_{j = 1}^{n} ((\Phi \circ \exp)(\log(b_j)) \ – \, c) \leq \sum_{j = 1}^{n} ((\Phi \circ \exp)(\log(a_j)) \ – \, c)$$ (where we abbreviate \(c = (\Phi \circ \exp)(- L)\)).
Redistributing the constant, we have exactly $$\sum_{j = 1}^{n} \Phi(b_j) \leq \sum_{j = 1}^{n} \Phi(a_j).$$
Finally, our \(\epsilon\) and \(\eta\) perturbations of the sequences may be addressed, if needed, by taking the limit and using continuity of \(\Phi\) at zero.
Remarks: First, we note that this multiplicative version gives the additive version of the inequality. By the localized nature of the inequality, inspecting the proof, we can see that this result still holds when \((a_j)_{j = 1}^{n}, (b_j)_{j = 1}^{n} \subseteq I\), \(I\) an open interval, and \(\Phi\) is a convex and increasing function only defined on that bounded open interval. (Simply take the derivative of the function \(g\), above, and past the left-most and right-most endpoints from that finite set, extend it trivially by constants to create a new, globally-defined increasing derivative and (thus) convex function.)
This also gives a further improvement to the additive form of the inequality. Finally, for one final observation, we note that if \(f\) is convex but not increasing on the compact subset \(E = \text{co}((x_i), (y_i))\) of the interval \(I\) (here \(\text{co}\) abbreviates the convex hull), then we can simply add a term like \(M x\) to \(f\), where \(M \gg 1\) is very large (greater than the absolute value of the real number \(\inf_E f’ > \, – \infty\)), to get that \(x \mapsto f(x) + M x\) will be increasing. Then we have the following:
Theorem: Let \(I\) be an open interval in \(\mathbb{R}\), and let \((x_i)_{i = 1}^{n}, (y_i)_{i = 1}^{n} \subseteq I\) be two finite collections of numbers, each arranged in decreasing order. Assume we have $$\sum_{i = 1}^{k} x_i \leq \sum_{i = 1}^{k} y_i$$ for all \(k \in \{1, \dots, n\}\). Let \(f : I \to \mathbb{R}\) be a convex function.
If any one of the following two statements is true: either, in the above sum, we have equality when \(k = n\) (i.e., $$\sum_{i = 1}^{n} x_i = \sum_{i = 1}^{n} y_i$$ holds); or, \(f\) is an increasing function on \(E\): then we have the conclusion $$\sum_{i = 1}^{n} f(x_i) \leq \sum_{i = 1}^{n} f(y_i).$$
This statement gives the full form of what is commonly referenced as Karamata’s inequality.
(The second alternative has already been covered; to see the first, we simply note that we can add the \(+ M x\) to \(f\) to land us in the regime of the original result, and subtract off this excess contribution in the final sum over \(\sum_{i = 1}^{n}\), using the equality condition between the \((x_i)\) and \((y_i)\), after which only \(f\) shall remain.)
- Discovering the proof made for an interesting experience; Professor Killip sketched the first half of the argument in class (the importance of the truncated logarithms), but not the approximation procedure for the limit passage (and in lecture, the result was originally only applied to functions \(f(t) = t^p\), \(p > 0\)). Consequently, I had to figure out the approximation argument by myself, and what’s given (in the second half of the proof) are my ideas. (I really was quite lost for a while, until I recalled the in-class remark that the inequality holds for all \(\Phi\) with \(t \mapsto \Phi(e^t)\) convex and increasing. What I was essentially trying to do, up until that point, was to find the \(\lambda_i\) (using the notation from later-on above) by hand, for \(t \mapsto t^p\); this would have been a very laborious and unpleasant task to work explicitly. Thinking about the general case, for all convex increasing functions, made it far easier to see and produce a unified argument.) ↩︎
- After Jovan Karamata (1902–1967). Others (including myself) may know him more from his work in Tauberian theory, where he gave a landmark proof of a difficult result of Hardy and Littlewood: if \((a_n)_{n \in \mathbb{N}}\) is a sequence satisfying the size condition \(a_n = O(1 / n)\), and the sequence is Cesàro summable (or even just Abel summable), then \(\sum_{n = 1}^{\infty} a_n\) converges. (The Cesàro result can be shown via an argument with “delayed means”; cf. Stein & Shakarchi’s vol. I, Fourier Analysis. The Abel sum case is harder.) This may be put to good use in proving the classical Dirichlet theorem on pointwise convergence of Fourier series for functions of bounded variation. ↩︎
- A word about nomenclature on this blog: decreasing and increasing will always mean non-strictly monotone. When the inequality must be strict, we will emphasize as much. Likewise, positive and negative will always be taken in the weak sense unless prefaced otherwise (to avoid ever having to use “nonnegative” and then be forced, for the sake of consistency, to adopt the deeply-evil “nonpositive”). Set inclusions will also be taken the same way. ↩︎
- We should note that there is nothing special about \(e\) here; obviously, if this holds for \(e\), it holds for any (equiv., all) choices of base \(c > 1\). ↩︎
- I am terrible at attribution, so if this argument is originally due to somebody else, please let me know; if I have a chance, I’ll also try to ask Professor Killip (although he may very well be on sabbatical at the moment). ↩︎
Leave a Reply