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.
