2
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2011 at 14:05

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ See counterxamples in comment to fedja's answer above for the case where we restrict to positive vectors only. $\endgroup$
    – Suvrit
    Jan 26, 2011 at 13:48
6
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ can you give a counterexample with all positive coordinates? $\endgroup$ Jan 26, 2011 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$ Jan 26, 2011 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, 2011 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, 2011 at 13:47
  • $\begingroup$ When I replace randn by rand, I never get a counterexample. Would you be kind enough to provide one? $\endgroup$ Jan 26, 2011 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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