MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

I've only played with this a little for the past day or so, and haven't thought about it too hard, so it might be obvious. Obviously it's not fair to ask for a "combinatorial proof" of an inequality involving real numbers, so we'll ask that the vectors be in $\mathbb{N}^n$. More concretely:

Given n boxes subdivided into a "right half" and a "left half" with $a_i$ objects in the right half of box $i$, and $b_i$ in the left half of box i, is there a natural injective function from

Two pairs (ordered, with replacement) of objects, with each pair containing one object from the left half and one object from the right half of a fixed box


A pair (ordered, with replacement) from the right half of some box, and a pair (O,WR) from the left half of some (possibly different) box?

(Sorry if this is a double; my wireless is being strange.)

share|cite|improve this question
Cauchy-Schwarz is true for reals if and only if it's true for rationals by continuity, if and only it's true for integers by homogeneity. – Qiaochu Yuan Feb 23 '10 at 7:02
Also, have you seen the discussion at… ? – Qiaochu Yuan Feb 23 '10 at 7:08
The discussion continued at…. I think the conclusion was that categorification of Cauchy-Schwarz was not possible. – David Corfield Feb 23 '10 at 9:02
I haven't finished reading it, but if you're interested in anything and everything Cauchy-Schwarz related, pick up The Cauchy-Schwarz Master Class by J. Michael Steele. – Ian Durham Feb 23 '10 at 12:30

Honestly, not really, there is no interesting combinatorial proof. Think of the most trivial case $a^2 + b^2 \ge 2 a b$. How do you prove that combinatorially? Well, arrange the terms into $(a+b)^2$ as in proving Pythagoras theorem and cut both squares by a diagonal. Now observe that reflection of white triangles will cover the blue rectangles. This proof can be stated in a purely combinatorial language, but why bother - it's a standard "book proof" you can find everywhere. Similarly, you can take: $$\sum_{i=1}^n \sum_{j=1}^n \left(a_i b_j + a_j b_i \right)^2$$ expand all the terms and get a similar flavor "combinatorial proof", more or less the same what you can find in standard books. But again why bother?

P.S. If you want to see the real power of bijective proofs, you can check out my survey of partition bijections. Sorry for the self-promotion, but there is no other such large compendium (although Stanley's "Enumerative Combinatorics" does mention many beautiful bijections, many of which hidden in the solutions to exercises).

share|cite|improve this answer
I would phrase this as follows, especially in light of the outcome of the n-category cafe discussion linked to above: there appears to be no particularly good/natural way to categorify the assertion that the square of an integer is non-negative. (An example of this is that I believe there exist generating functions whose coefficients can be proven to be non-negative integers because they are a sum of squares, but which have no known combinatorial interpretation.) – Qiaochu Yuan Feb 23 '10 at 16:42

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.