The Problem:

The following question of Horst Knörrer is a sort of toy problem coming from mathematical physics.

Let $x_1, x_2, \dots, x_n$ and $y_1,y_2,\dots, y_n$ be two sets of real numbers.

We give now a weight $\epsilon_\pi$ to every permutation $\pi$ on {1,2,...,n} as follows:

1) $\epsilon_\pi =0$ if for some $k \ge 1$, $x_k \ge y_{\pi(1)}+y_{\pi(2)}+\cdots +y_{\pi(k)}$.

2) Otherwise, $\epsilon_\pi=sg(\pi )$. ($sg (\pi )$ is the sign of the prrmutation $\pi$.)

Problem: Show that there is a constant $C>1$ such that (for every $n$ and every two sequences of reals $x_1,\dots,x_n$ and $y_1, \dots, y_n$),

$$\sum_\pi \epsilon_\pi \le C^n \sqrt{n!}.$$

Origin and Motivation from Mathematical Physics

1) The problem was proposed by Horst in a recent Oberwolfach's meeting as a combinatorial problem that arises (as a toy problem) from mathematical physics.

The context of this question is explained in Section 4 of J.Feldman, H.Kn\"orrer, E.Trubowitz: "Construction of a 2-d Fermi Liquid", Proc. XIV. International Congress on Mathematical Physics. Editor: Jean Claude Zambrini. World Scientific 2005

"In this section, we formulate an elementary question about permutations that may be connected with implementing the Pauli exclusion principle in momentum space."

The problem and some variations are directly related to "cancellations between Fermionic diagrams".

The wider picture (See the Eleven Papers by J.Feldman, H.Knörrer, E.Trubowitz) is toward mathematical understanding and formalism for highly successful physics quantum theories. (In a very very wide sense this is related to Clay's problem on Yang-Mills and Mass gap.)

Remarks and more Motivation

2) This remarkable cancellation property seems similar to cancellations that we often encounter in probability theory, combinatorics and number theory.

3) It look similar to me even to issues that came in my recent question on Walsh functions. So this question about permutations is analogous to questions asserting that for certain +1,-1,0 functions on ${-1,1}^n$ there is a remarkable cancellation when you sum over all $\pm 1$ vectors. This is true (to much extent) for very "low complexity class functions" (functions in $AC^0$) by a theorem of Linial-Mansour-Nisan, So maybe we can expect remarkable cancellation for "not too complex" functions defined on the set of permutations.

4) We can simplify in the question and replace condition 1) by

1') $\epsilon_\pi =0$ if for some $k \ge 1$, $x_k \ge y_{\pi(k)}$.

I don't know if this makes much difference.

5) An affarmative answer seems a very bold statement, so, of course, perhaps the more promising direction is to find a counter example. But I think this may be useful too.

  • Does the simplification in 4 force the value to be zero or one? Assume that the sequences $x_k$ and $y_k$ are nondecreasing. Then the condition $y_{\pi(k)}\leq x_k$ is equivalent to $\pi(k)\leq l(k)$ for some nondecreasing function $l(k)$. If $l(k)>=2$, then the total contribution for fixed $\{k:\pi(k)\leq l(1)\}$ is the determinant of the l(1)-by-l(1) all-one matrix, so zero. – Colin McQuillan Mar 25 '11 at 9:32
  • I dont think it forces the answer to be 0 or 1 – Gil Kalai Mar 25 '11 at 10:06
up vote 8 down vote accepted

The question was beautifully solved affirmatively by Nikola Djokic. His paper an upper bound on the sum of signs of permutations with a condition on their prefix sets is now posted on the arxive.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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