##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>0$ such that

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

##Origin, remarks and Motivation

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. I dont remember the precise context from physics, but I will add more information about it when I will have an opportunity.

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.