# An extension of the Hardy-Littlewood-Polya inequality?

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.

-
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

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);
end
end


end

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

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

-
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