For mathematicians’ eyes only. The post doesn’t require much theoretical knowledge to understand, but I haven’t given many definitions.
In the last two posts I’ve been talking about an example I made with four-dimensional vectors such that , and . Finding it was more difficult than I at first expected, so I thought I would write the investigation up, which happily gives me an excuse to introduce a useful inequality.
My first thoughts were to choose something like and or , and then I’d got stuck choosing . So I decided to try to prove the opposite.
First of all, it’s not possible to create such an example in two dimensions. Let’s focus on selecting and first. The ordering within each vector is irrelevant, as all three norms under consideration are symmetric (they treat each coordinate equally). Since we have , and likewise implies that . This means that the sequence essentially majorizes the sequence .
Definition. A real sequence ordered such that weakly majorizes a sequence with if each initial partial sum of the first sequence is greater than the second, that is for each .
Because of majorization, we can now discover something about the norm: the function is easily seen to be strictly convex, and so we may apply a version of Karamata’s inequality!
Karamata’s inequality (alternate form). If a descending real sequence weakly majorizes , then for any non-decreasing strictly convex function we will have .
Note: the function needs only to be strictly convex and defined on a real interval containing both sequences.
You can remove the ‘non-decreasing’ condition and gain Karamata’s usual inequality, by: deleting all the ‘weakly’s in the definition and theorem above; and by requiring the two full sums to be equal: .
Therefore we have , and so , the opposite of what we wanted, meaning the inequalities we were trying to prove are not possible in two dimensions.
What about in three dimensions and higher? From the two ‘extreme’ norms, we will still have and . If we choose and such that , then we can again apply Karamata’s inequality and repeating the two-dimensional work will lead to failure. So that means we must require to have any hope of succeeding.
So I chose , and . The initial partial sums of briefly overtake those of , but fall behind again: ie. stage by stage in the addition, we have 10>9, 16<17, and 18>17. Then, fixing to be the smallest in the norm, I cheated and tried a few randomised possibilities for the coordinates of in Excel, and was quickly rewarded with: .
I specifically wanted a four-dimensional example for the post, so I added a final coordinate all equal to 1 on the end of each, which wouldn’t change any of the inequalities, and messed up the ordering of the sequences a bit.
There may be some elementary way of seeing all this, but Karamata’s inequality is neat and allows easy generalisation from the case to non-integer . This could mean salvation from the guilty temptation to incorrectly interpolate to get inequalities for such , once you have similar inequalities for the integer powers on either side.
While I’m revisiting old posts, Karamata’s inequality is a generalisation of the more widely known Jensen’s inequality, which is in turn a generalisation of the arithmetic-geometric inequality, which, perhaps surprisingly, contributed to a day of strikes in Britain. The link is a proposed change from RPI to the lower CPI in public sector pensions.
Finally, “Karamata’s inequality” doesn’t quite scan to the tune of the Katamari Damacy theme, but if singing “Na naaa na na na nana nana na na Karamata’s inequality” helps you to remember this useful but perhaps overlooked inequality, does an extra syllable really matter?