MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 5 added 905 characters in body

Origin , remarks 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. I dont remember the precise

The context from physicsof this question is explained in Section 4 of J.Feldman, but I will add more information about it when I will have 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 opportunityelementary 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 betweenFermionic 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
show/hide this revision's text 4 edited body

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$ 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, 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.
show/hide this revision's text 3 added 2 characters in body; edited tags

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 (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, 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 ${-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.
show/hide this revision's text 2 added 87 characters in body; added 1 characters in body
show/hide this revision's text 1