Return to Answer

Not an answer, just too long for a comment: Set $a_i=b_i^2$, and let $E_n=E_n(b_1,\dots,b_n)$ be the left hand side minus the right hand side (and multiplied by $n!$). The assertion can be verified for $n=3, 4, 5$ by squares of polynomials. It is easy to see that $E_3$ is not a sum of squares, however \begin{align*} (1+b_3^2)E_3 &= (-b_1b_2b_3^2 - b_1b_3 - b_2b_3 + b_3^2 + 2)^2 + 2(b_1b_2b_3 - b_3)^2\\ &\quad + 2(b_1 - b_2)^2 + (b_1b_2b_3^2 - b_1b_3 - b_2b_3 + b_3^2)^2. \end{align*} Similarly \begin{align*} E_4 &= (b_4b_1 + b_2b_3 - 2)^2 + (b_4b_2 + b_1b_3 - 2)^2 + (b_1b_2 - b_4b_3)^2\\ &\quad + 2(b_3 - b_4)^2 + 2(b_1 - b_2)^2 + (1 - b_1b_2b_3b_4)^2 \end{align*} For $E_5$ there is also such an SOS representation over the rationals. However, the ones I found are very messy. (And for $E_6$ I only found a real approximation.) The problem is that already for $n=4$ such representations are far from unique, so they do not tend to have rational coefficients.

Remark: Let $\chi(n)=\lfloor{\frac{n!}e+\frac{1}{2}}\rfloor$ be the number of derangements of $n$ letters. Using induction on $n$ and assuming that a global minimum of the left hand side minus the right hand side is a local minimum too, I can show (in the conjecture's notation) \begin{equation} \mathbb{E}_{\pi \in S_n} [w(\pi)] \ge \frac{\chi(n)}{n!}+(1-\frac{\chi(n)}{n!})\mathbb{E}_{\{i,j\} \in\binom{[n]}{2}} [\sqrt{a_i a_j}]. \end{equation} So this inequality is better for small $a_i$'s but worse by a factor $\sim 1-\frac{1}{e}$ for large $a_i$'s.

Not an answer, just too long for a comment: Set $a_i=b_i^2$, and let $E_n=E_n(b_1,\dots,b_n)$ be the left hand side minus the right hand side (and multiplied by $n!$). The assertion can be verified for $n=3, 4, 5$ by squares of polynomials. It is easy to see that $E_3$ is not a sum of squares, however \begin{align*} (1+b_1^2b_2^2)E_3 &= 2(1-b_1b_2)^2 + (b_1 + b_2 - b_3-b_1^2b_2^2b_3)^2 + (b_1b_2)^2(b_1 -b_2)^2. \end{align*} Similarly \begin{align*} E_4 &= (b_4b_1 + b_2b_3 - 2)^2 + (b_4b_2 + b_1b_3 - 2)^2 + (b_1b_2 - b_4b_3)^2\\ &\quad + 2(b_3 - b_4)^2 + 2(b_1 - b_2)^2 + (1 - b_1b_2b_3b_4)^2. \end{align*} For $E_5$ there is also such an SOS representation over the rationals. However, the ones I found are very messy. (And for $E_6$ I only found a real approximation.) The problem is that already for $n=4$ such representations are far from unique, so they do not tend to have rational coefficients.

Not an answer, just too long for a comment: Set $a_i=b_i^2$, and let $E_n=E_n(b_1,\dots,b_n)$ be the left hand side minus the right hand side (and multiplied by $n!$). The assertion can be verified for $n=3, 4, 5$ by squares of polynomials. It is easy to see that $E_3$ is not a sum of squares, however \begin{align*} (1+b_3^2)E_3 &= (-b_1b_2b_3^2 - b_1b_3 - b_2b_3 + b_3^2 + 2)^2 + 2(b_1b_2b_3 - b_3)^2\\ &\quad + 2(b_1 - b_2)^2 + (b_1b_2b_3^2 - b_1b_3 - b_2b_3 + b_3^2)^2. \end{align*} Similarly \begin{align*} E_4 &= (b_4b_1 + b_2b_3 - 2)^2 + (b_4b_2 + b_1b_3 - 2)^2 + (b_1b_2 - b_4b_3)^2\\ &\quad + 2(b_3 - b_4)^2 + 2(b_1 - b_2)^2 + (1 - b_1b_2b_3b_4)^2 \end{align*} For $E_5$ there is also such an SOS representation over the rationals. However, the ones I found are very messy. (And for $E_6$ I only found a real approximation.) The problem is that already for $n=4$ such representations are far from unique, so they do not tend to have rational coefficients.

Not an answer, just too long for a comment: Set $a_i=b_i^2$, and let $E_n=E_n(b_1,\dots,b_n)$ be the left hand side minus the right hand side (and multiplied by $n!$). The assertion can be verified for $n=3, 4, 5$ by squares of polynomials. It is easy to see that $E_3$ is not a sum of squares, however \begin{align*} (1+b_3^2)E_3 &= (-b_1b_2b_3^2 - b_1b_3 - b_2b_3 + b_3^2 + 2)^2 + 2(b_1b_2b_3 - b_3)^2\\ &\quad + 2(b_1 - b_2)^2 + (b_1b_2b_3^2 - b_1b_3 - b_2b_3 + b_3^2)^2. \end{align*} Similarly \begin{align*} E_4 &= (b_4b_1 + b_2b_3 - 2)^2 + (b_4b_2 + b_1b_3 - 2)^2 + (b_1b_2 - b_4b_3)^2\\ &\quad + 2(b_3 - b_4)^2 + 2(b_1 - b_2)^2 + (1 - b_1b_2b_3b_4)^2 \end{align*} For $E_5$ there is also such an SOS representation over the rationals. However, the ones I found are very messy. (And for $E_6$ I only found a real approximation.) The problem is that already for $n=4$ such representations are far from unique, so they do not tend to have rational coefficients.

Remark: Let $\chi(n)=\lfloor{\frac{n!}e+\frac{1}{2}}\rfloor$ be the number of derangements of $n$ letters. Using induction on $n$ and assuming that a global minimum of the left hand side minus the right hand side is a local minimum too, I can show (in the conjecture's notation) \begin{equation} \mathbb{E}_{\pi \in S_n} [w(\pi)] \ge \frac{\chi(n)}{n!}+(1-\frac{\chi(n)}{n!})\mathbb{E}_{\{i,j\} \in\binom{[n]}{2}} [\sqrt{a_i a_j}]. \end{equation} So this inequality is better for small $a_i$'s but worse by a factor $\sim 1-\frac{1}{e}$ for large $a_i$'s.

Not an answer, just too long for a comment: Set $a_i=b_i^2$, and let $E_n=E_n(b_1,\dots,b_n)$ be the left hand side minus the right hand side (and multiplied by $n!$). The assertion can be verified for $n=3, 4, 5$ by squares of polynomials. It is easy to see that $E_3$ is not a sum of squares, however \begin{align*} (1+b_3^2)E_3 &= \frac{1}{2}(-b_3^2b_1b_2 + b_3^2 - b_3b_1 - b_3b_2 + 2)^2\\ &\quad + (-b_1 + b_2)^2 + (-b_3b_1b_2 + b_3)^2\\ &\quad + \frac{1}{2}(-b_3^2b_1b_2 - b_3^2 + b_3b_1 + b_3b_2)^2. \end{align*} Similarly \begin{align*} E_4 &= (b_4b_1 + b_2b_3 - 2)^2 + (b_4b_2 + b_1b_3 - 2)^2\\ &\quad + (b_1b_2 - b_4b_3)^2 + 2(b_3 - b_4)^2\\ &\quad + 2(b_1 - b_2)^2 + (1 - b_1b_2b_3b_4)^2 \end{align*} For $E_5$ there is also such an SOS representation over the rationals. However, the ones I found are very messy. (And for $E_6$ I only found a real approximation.) The problem is that already for $n=4$ such representations are far from unique, so they do not tend to have rational coefficients.

Not an answer, just too long for a comment: Set $a_i=b_i^2$, and let $E_n=E_n(b_1,\dots,b_n)$ be the left hand side minus the right hand side (and multiplied by $n!$). The assertion can be verified for $n=3, 4, 5$ by squares of polynomials. It is easy to see that $E_3$ is not a sum of squares, however \begin{align*} (1+b_3^2)E_3 &= (-b_1b_2b_3^2 - b_1b_3 - b_2b_3 + b_3^2 + 2)^2 + 2(b_1b_2b_3 - b_3)^2\\ &\quad + 2(b_1 - b_2)^2 + (b_1b_2b_3^2 - b_1b_3 - b_2b_3 + b_3^2)^2. \end{align*} Similarly \begin{align*} E_4 &= (b_4b_1 + b_2b_3 - 2)^2 + (b_4b_2 + b_1b_3 - 2)^2 + (b_1b_2 - b_4b_3)^2\\ &\quad + 2(b_3 - b_4)^2 + 2(b_1 - b_2)^2 + (1 - b_1b_2b_3b_4)^2 \end{align*} For $E_5$ there is also such an SOS representation over the rationals. However, the ones I found are very messy. (And for $E_6$ I only found a real approximation.) The problem is that already for $n=4$ such representations are far from unique, so they do not tend to have rational coefficients.