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
    Commented 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
    Commented 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$ Commented 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$ Commented 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
    Commented 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
    Commented 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$ Commented Jan 26, 2011 at 13:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .