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.

  • $\begingroup$ Really, with my code you don't get a counterexample? am I doing something wrong? For $n=3$ I get counterexamples right away. $\endgroup$ – Suvrit Jan 26 '11 at 14:05

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$.

  • $\begingroup$ See counterxamples in comment to fedja's answer above for the case where we restrict to positive vectors only. $\endgroup$ – 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.

  • $\begingroup$ can you give a counterexample with all positive coordinates? $\endgroup$ – Aryeh Kontorovich Jan 26 '11 at 13:30
  • $\begingroup$ 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. $\endgroup$ – Aryeh Kontorovich Jan 26 '11 at 13:42
  • $\begingroup$ 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. $\endgroup$ – Suvrit Jan 26 '11 at 13:45
  • 1
    $\begingroup$ 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$. $\endgroup$ – Suvrit Jan 26 '11 at 13:47
  • $\begingroup$ When I replace randn by rand, I never get a counterexample. Would you be kind enough to provide one? $\endgroup$ – Aryeh Kontorovich Jan 26 '11 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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