Question

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.

Answer 1

I don't have an answer but here is a formulation which seems a bit more combinatorial.

Let's start defining some objects. Let $S_n$ be the set of all vectors which are a permutation of $\{1,2,\dots,n\}$, and let's add a partial order structure given by dominance (majorization), $(\sigma(1),\dots,\sigma(n))\succ (\tau(1,\dots,\tau(n)))$ iff $$\sum_{i=1}^k \sigma(i)\geq \sum_{i=1}^k \tau(i)$$ for all $1\le k\le n$. Now, when given $y_1,y_2,\cdots,y_n$, let us reorder them in non-inreasing order $y'1\geq\cdots\geq y'_n$, this clearly doesn't affect the problem. One observation is that if $\epsilon(\pi)\neq 0$ and $\pi'\succ \pi$ in $(S_n,\succ)$ then $\epsilon(\pi') \neq 0$. This implies that for every $\vec{x},\vec{y}$, the set of permutations $\sigma\in S_n$ for which $\epsilon(\sigma) \neq 0$ is an upper set, or actually an order ideal of $(S_n,\succ)$ since there is a maximal element.

Let's define $\chi(P)$ for an upper set in $(S_n,\succ)$ as $\sum_{\sigma\in P} \operatorname{sgn} (\sigma)$, so that now the problem becomes

Show that $\chi(P)\le C^n \sqrt{n!}$ for all upper sets $P$.

We have $\chi{S_n}=0$ and $\chi$ of a chain is almost bounded (the signs alternate), which makes this result close to following from a Dilworth type result. Unfortunately the chains aren't long enough to partition an upper set in a "small" number of chains (i.e. there are large antichains). However $\chi$ seems very close to some sort of Mobius function for this poset, showing the similarity you mention in the post. Maybe there is an argument that can prove the inequality from here...

Edit: Let me also add that our poset's diagram seems to be the Permutohedron plus a few more edges between consecutive levels. In particular it seems to have (almost) the same grading. Just intuition tells me that the maximum should be achieved when $P$ is the upper half of the poset. That is $\chi$ is at most of the order of the alternating sum $\sum_{k=0}^{\frac{1}{2}\binom{n}{2}} (-1)^k a(k)$ where $a(k)$ is the number of permutations with $k$ inversions. Maybe this can be made rigorous?

Also, some googling reveals that once one puts a weight on each element of the poset, there is a problem of determining the ideal of maximum weight (sum of weights of its elements), so maybe some of that literature might be helpful.