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

  • 7
    $\begingroup$ 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. $\endgroup$ Feb 23 '10 at 7:02
  • $\begingroup$ Also, have you seen the discussion at golem.ph.utexas.edu/category/2007/04/… ? $\endgroup$ Feb 23 '10 at 7:08
  • 1
    $\begingroup$ The discussion continued at golem.ph.utexas.edu/category/2007/05/…. I think the conclusion was that categorification of Cauchy-Schwarz was not possible. $\endgroup$ Feb 23 '10 at 9:02
  • 3
    $\begingroup$ 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. $\endgroup$
    – 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).

  • 1
    $\begingroup$ 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.) $\endgroup$ Feb 23 '10 at 16:42
  • $\begingroup$ Also adding to it : Professor Richard P. Stanley's problem set on bijective proofs has some really magnificent gems hidden in the problems. Anyone dedicating his or her time and energy in figuring our solutions to the problems (of course solving all the problems may take some extra ordinary skills), will really discover by self a lot about how bijective proofs. $\endgroup$ Mar 15 '20 at 14:34

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.