MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $x,y$ be vectors in $\mathbb{R}^n$ and let's use the notation $\hat x$ for the vector $x$ with its components sorted in increasing order. The Hardy-Littlewood-Polya inequality states that $$ x\cdot y \leq \hat x\cdot \hat y.$$ Let us also use the notation $xy\in\mathbb{R}^n$ to denote the coordinate-wise product of $x$ and $y$. I conjecture that $$ \frac{ ||xy||_p ||xy||_r}{||xy||_q} \le \frac{ ||\hat x\hat y||_p ||\hat x\hat y||_r}{||\hat x\hat y||_q} $$ for all $1\le p\le q\le r$. For $q=p$ and $q=r$, my conjectured inequality is true by the HLP inequality. Any ideas for a proof?

UPDATE: thank you for the quick answers. The counterexamples indeed work when negative coordinates for x and y are allowed. However, when all the coordinates of x and y are required to be positive, the conjecture seems to hold.

UPDATE 2: so the conjecture is totally false; see below for counterexamples.

share|cite|improve this question
Really, with my code you don't get a counterexample? am I doing something wrong? For $n=3$ I get counterexamples right away. – Suvrit Jan 26 '11 at 14:05
up vote 2 down vote accepted

Here is a Matlab script that will generate a quick counterexample for you:

function [x,y]=testIneq(n, p, q, r)

% x and y are length n vectors
% Try: [x,y]=testIneq(2,1,2,3) to get a counterexample!

flag = 1;
iter = 0;

while (flag)

    iter = iter + 1;
    x = randn(n,1);
    y = randn(n,1);

    xh = sort(x);
    yh = sort(y);

    xy = x .* y;
    xyh = xh .* yh;

    lhs = norm(xy,p) * norm(xy,r) / norm(xy,q);
    rhs = norm(xyh,p) * norm(xyh,r) / norm(xyh,q);

    if (rhs < lhs)
        flag = 0;
        fprintf('Found countex after %d tries\n', iter);


Example: $x =[-2.1384,-0.8396]$, $y =[1.3546,-1.0722]$, with $p=1$, $q=2$, $r=3$.

share|cite|improve this answer
See counterxamples in comment to fedja's answer above for the case where we restrict to positive vectors only. – Suvrit Jan 26 '11 at 13:48

Rather for a counterexample. Let's say all coordinates are positive.

The inequality is equivalent to the claim that $f(t)=\frac{\|xy\|_t}{\|\hat x\hat y\|_t}$ satisfies $f(s)f(t)\le f(1)$ for $s\le 1\le t$ ($1\le p$ is not really a restriction due to the possibility to raise to positive powers inside and outside, so only the ratios $p/q$ and $r/q$ really matter). Also sums can be replaced by averages. Now, as $s\to 0$, we have the geometric means in the limit, which do not feel the rearrangements, so $f(0+)=1$. Also, $f(\infty)=1$ if only the maxima match in the original arrangements. But $f(1)<1$ unless the orderings are exactly the same.

share|cite|improve this answer
can you give a counterexample with all positive coordinates? – Aryeh Kontorovich Jan 26 '11 at 13:30
I don't follow your argument that my claim is equivalent to $f(s)f(t)\le f(1)$ -- the latter is indeed easily falsifiable. – Aryeh Kontorovich Jan 26 '11 at 13:42
Just try my code below with testIneq(10,1,2,10) and you will get a quick countexexample; replace the 'randn' by 'rand' to get all positive coordinates. – Suvrit Jan 26 '11 at 13:45
another simpler example is: $x =[0.0062,0.5198,0.4350]$, $y =0.0515,0.9148,0.5404]$, with $p=1$, $q=2$, $r=10$. – Suvrit Jan 26 '11 at 13:47
When I replace randn by rand, I never get a counterexample. Would you be kind enough to provide one? – Aryeh Kontorovich Jan 26 '11 at 13:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.