40
$\begingroup$

I am searching for the first proof of (or counterexample to) the following conjecture.

(The sum of squared logarithms conjecture) For all natural numbers $n$ and positive numbers $x_1,x_2, \ldots , x_n, y_1,y_2,\ldots, y_n>0$ such that for all $k\in\{1,\ldots, n-1\}$ it holds

$\sum_{i_1<\ldots<i_k} x_{i_1}\, x_{i_2}\ldots x_{i_k}\le \sum_{i_1<\ldots<i_k} y_{i_1}\, y_{i_2}\ldots y_{i_k}$

and $x_1\, x_2\, x_3 \ldots x_n=y_1\, y_2 \,y_3\ldots y_n$

it follows

$\sum_{i=1}^n (\log x_i)^2\le \sum_{i=1}^n (\log y_i)^2$

Replacing the assumption $x_1\, x_2\, x_3 \ldots x_n=y_1\, y_2\, y_3\ldots y_n$ by $x_1\, x_2\, x_3 \ldots x_n\le y_1\, y_2\, y_3\ldots y_n$ easily admits counterexamples.

Proofs are known for $n\in \{1,2,3,4\}$. More information can be found at

https://www.uni-due.de/mathematik/ag_neff/log_conjecture

Immediately after Lev Borisov's sketch of a proof idea below, Lev Borisov, Suvrit Sra, Christian Thiel and myself agreed to work out the details and to write together a complete and self-contained paper on the sum of squared logarithm conjecture and relations to other topics which can be found at: http://arxiv.org/abs/1508.04039 ${}{}{}$

As announced in my first post, the prize winner is Lev Borisov.

$\endgroup$
8
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because "proof this for me" (price money or not) isn't on topic for this site. $\endgroup$ May 28, 2015 at 15:30
  • 20
    $\begingroup$ @JohannesHahn: I'm surprised by your comment. The question clearly states a conjecture and asks for a proof -- what's not on topic about this? And, anyone who doesn't want the gold can pass it on to me! $\endgroup$
    – Lucia
    May 28, 2015 at 15:37
  • 1
    $\begingroup$ Algebraic-geometry? $\endgroup$
    – abx
    May 28, 2015 at 15:47
  • 3
    $\begingroup$ This conjecture is a really nice one; I saw it a couple of years ago, but did not yet get time to think about it! In particular, it states that if eigenvalues of a positive definite matrix $X$ are $E$-majorized (to be defined) by those of $Y$, then $d(X,I) \le d(Y,I)$, where $d(\cdot,\cdot)$ is the Riemannian distance on the manifold of positive definite matrices (E-majorization is just the majorization in terms of elementary symmetric functions as noted in the conjecture above) $\endgroup$
    – Suvrit
    May 28, 2015 at 15:59
  • 1
    $\begingroup$ @PraveenKumar It's LateX: en.wikipedia.org/wiki/LaTeX $\endgroup$
    – Ben Webster
    Jun 2, 2015 at 7:27

4 Answers 4

33
$\begingroup$

Is there anything wrong with the following argument?

First of all, by scaling all $x_i$ and all $y_i$ by a positive constant, we may safely assume that $\prod_i x_i = \prod_i y_i =1$.

The result would now follow from the following more general conjecture.

$\bf Conjecture:$ For ${\bf a}=(a_1,\ldots,a_{n-1})\in (\mathbb R_{>0})^{n-1}$ consider $h_{\bf a}(z) = z^n+a_{n-1}z^{n-1}+\cdots+a_1z+1$. Define the function $f:(\mathbb R_{>0})^{n-1}\to {\mathbb R}$ by $$ f(a_1,\ldots,a_{n-1}) = \sum_{z\vert h_{\bf a}(z)=0} (\log(-z))^2 $$ where the branch of $\log$ is picked as usual on the complement of ${\mathbb R}_{\leq 0}$ in $\mathbb C$. Then all partial derivatives $\frac{\partial f}{\partial a_k}$ are positive.

First, a few comments. The function $f$ is well-defined because none of the roots of $h_a(z)$ are positive reals. In addition, $f$ is real-valued, because roots of $h_a(z)$ come in complex conjugate pairs for which values of $\log(-z)$ are complex conjugates. The consequence of this conjecture is that if ${\bf a}\leq {\bf b}$ coordinate-wise, then $f({\bf a})\leq f({\bf b})$. Applied to the case when roots of $h_{\bf a}(z)$ and $h_{\bf b}(z)$ are real numbers $-x_i$ and $-y_i$, we get the original conjecture.

Now, let me describe what I think is the proof of this new conjecture.

First of all, as standard, I can write the function $f(\bf a)$ by a contour integral. In a neighborhood of fixed ${\bf a}$ for any large enough $R$ and small enough $\epsilon>0$ there holds $$ f({\bf a}) = \frac 1{2\pi i}\int_{C} (\log(-z))^2 \frac {h_{\bf a}'(z)}{h_{\bf a}(z)}\,dz $$ over the contour $C$ on the union of $\mathbb C$ with two copies of $\mathbb R_{>0}$ which I will call "north" and "south" shores (so that $\log(-t)=\log t -\pi i$ on the north shore and $\log(-t)=\log t +\pi i$ on the south shore). The contour $C$ is the union of the following four pieces $C_\epsilon$, $C_R$, $C_+$, $C_-$.

$C_\epsilon$ is a circle of radius $\epsilon$ around $z=0$ traveled from $\epsilon$-south to $\epsilon$-north clockwise.

$C_R$ is a circle of radius $R$ around $z=0$ traveled from $R$-north to $R$-south counterclockwise.

$C_+$ is the line segment $[\epsilon,R]$-north.

$C_-$ is the line segment $[R,\epsilon]$-south.

The derivative $\frac{\partial f({\bf a})}{\partial a_k}$ is the integral of the derivative, so we get: $$ \frac{\partial f({\bf a})}{\partial a_k}= \frac 1{2\pi i}\int_{C} (\log(-z))^2 \frac \partial{\partial a_k}\frac {h_{\bf a}'(z)}{h_{\bf a}(z)}\,dz $$ $$ = \frac 1{2\pi i}\int_{C} (\log(-z))^2 \Big(\frac {z^k} {h_{\bf a}(z)} \Big)'\,dz = -\frac 1{2\pi i}\int_{C} \Big((\log(-z))^2 \Big)'\frac {z^k} {h_{\bf a}(z)} \,dz $$ $$ =-\frac 1{\pi i}\int_{C} \log(-z)\frac {z^{k-1}} {h_{\bf a}(z)}\,dz = -\frac 1\pi {\rm Im}\Big(\int_{C} \log(-z)\frac {z^{k-1}} {h_{\bf a}(z)}\,dz\Big) $$ We can take a limit as $R\to +\infty$ and $\epsilon\to 0$. Since $k\leq {n-1}$ the integral over $C_R$ goes to zero (the length is $2\pi R$ and the size of the function is $O(R^{-2}\log R)$). The integral over $C_\epsilon$ also goes to zero, because the $k>=1$, so the function is $O(\log \epsilon)$ and the length is $2\pi\epsilon$.

So we get $$ \frac{\partial f({\bf a})}{\partial a_k} = -\lim_{\epsilon\to 0^+}\frac 1\pi {\rm Im}\Big( \int_{[\epsilon,+\infty]-{\rm north}\cup [+\infty,\epsilon]-{\rm south}} \log(-z)\frac {z^{k-1}} {h_{\bf a}(z)}\,dz\Big) $$ $$ =-\lim_{\epsilon\to 0^+}\frac 1\pi \int_{\epsilon}^{+\infty}{\rm Im}\Big( (\log(t)-\pi i)\frac {t^{k-1}} {h_{\bf a}(t)} -(\log(t)+\pi i)\frac {t^{k-1}} {h_{\bf a}(t)}\Big)\,dt $$ $$ =2\lim_{\epsilon \to 0^+} \int_{\epsilon}^{+\infty} \frac {t^{k-1}}{h_{\bf a}(t)}\,dt >0.$$ This finishes the proof of the new conjecture, and consequently of the old conjecture.

Remark: I am guessing that there is a simpler argument for $$ \frac{\partial f({\bf a})}{\partial a_k} = 2\int_{0}^{+\infty} \frac {t^{k-1}}{h_{\bf a}(t)}\,dt $$ but I am just writing the first thing that came to my mind.

$\endgroup$
5
  • 1
    $\begingroup$ If this solution turns out to be correct I will consider it the first proof of my conjecture and it will have priority as if it was an ArXive submission (see my announcement above) $\endgroup$ May 29, 2015 at 16:28
  • $\begingroup$ I think this solution has given me a hint on how to prove the result without complex analysis and using elementary methods; great work Lev! I will type out my solution as a corollary of existing results shortly! $\endgroup$
    – Suvrit
    May 29, 2015 at 16:40
  • $\begingroup$ I have an argument now that avoids the contour integration tricks (but does use an analytic continuation). I will type it up and send to Patrizio shortly. $\endgroup$ May 29, 2015 at 17:51
  • 6
    $\begingroup$ I hope it works out. Given the poster's original offer, I would like Lev to update this post to hear if things concluded satisfactorily. (The detail of whether he was compensated in precious metal is less important to me than knowing that the proof withstood vetting and that the poster made good on the offer. I think others on MO would like to know the same.) $\endgroup$ May 29, 2015 at 21:02
  • 5
    $\begingroup$ It's all good :) $\endgroup$ May 29, 2015 at 22:02
17
$\begingroup$

Lev's proof reminded me of two papers, and unless I'm doing something silly, the said conjecture follows as a corollary of those papers. The answer below is just meant to supplement Lev's result, and he deserves the credit for coming up with an independent proof.


Consider the function \begin{equation*} D(x) := \sum\nolimits_j (\log x_j)^2. \end{equation*}

Let $e_k$ be the elementary symmetric polynomials in $x_i$, so that \begin{equation*} e_1 = \sum_i x_i,\quad e_k=\sum_{|I|=k}\prod_{i\in I}x_i,\quad e_n=\prod_{i}x_i. \end{equation*} Since $D(x)$ is symmetric, without loss of generality, we assume that the $x_i$ are arranged in increasing order, so that $0 < x_1\cdots < x_n$. Also, we assume wlog that $e_n(x)=1$.

Lemma.

\begin{equation*} \frac{\partial D}{\partial e_k} = (-1)^{k+1}\sum_{j=1}^n \frac{x_j^{n-k-1}\log x_j}{\prod_{i \neq j}(x_j-x_i)},\quad\text{for}\ 1\le k < n. \end{equation*} Proof: The $x_j$ are roots of the polynomial \begin{equation*} p(x) = x^d - e_1x^{n-1}+e_2x^{n-2}\cdots+(-1)^ne_n. \end{equation*} Implicitly differentiating the roots $x_j$'s as a function of the $e_k$ we have \begin{equation*} \frac{\partial x_j}{\partial e_k} = \frac{(-1)^{k+1}x_j^{n-k}}{\prod_{i\neq j}(x_j-x_i)}\qquad 1\le k < n. \end{equation*} Now use the chain rule \begin{equation*} \frac{\partial D}{\partial e_k} = \sum_{j=1}^n\frac{\partial D}{\partial x_j}\frac{\partial x_j}{\partial e_k}, \end{equation*} to obtain the identity \begin{equation*} \frac{\partial D}{\partial e_k} = (-1)^{k+1}2\sum_{j=1}^n\frac{x_j^{n-k-1}\log x_j}{\prod_{i\neq j}(x_j-x_i)}. \end{equation*} Writing $q = k+1$, we obtain for $2\le q < n$, \begin{equation*} \frac{\partial D}{\partial e_{k}} = 2(-1)^{q}\sum_{j=1}^n\frac{x_j^{n-q}\log x_j}{\prod_{i\neq j}(x_j-x_i)}, \end{equation*} which is known to be nonnegative (and $q\ge 2$ is important there)---see: Josza & Mitchison (2013); or even the older paper: Mitchison & Josza; (2003).


Using the above Lemma, we see that $D$ is monotonic in the $e_k$, which establishes the original conjecture under the hypothesis on $e_k(x) \le e_k(y)$ for all $x$ and $y$.

Moreover, using the cited 2013 paper we can probably prove much more, including multivariate complete monotonicity of $D$ of the form \begin{equation*} (-1)^{m}\frac{\partial^m D}{\partial e_{i_1}\partial e_{i_2}\ldots\partial e_{i_m}} \ge 0,\qquad m \ge 1. \end{equation*}

$\endgroup$
1
  • 1
    $\begingroup$ Wow, this is almost exactly what I was trying (see my answer). I haven't read the Josza and Mitchison papers yet, but the problem I ran into is that I could only prove the inequalities on $\partial D/\partial e_k$ when the roots were real, and I couldn't show that I could move from one real rooted polynomial to another while keeping the roots real and decreasing the coefficients. Looking now to see whether or not Josza and Mitchison address this. $\endgroup$ May 29, 2015 at 19:04
6
$\begingroup$

Lev Borisov having put up a complete solution; I'll put up how far I got. In his notation, I was able to show $\frac{\partial f(a)}{\partial a_k} > 0$ when $z^n + a_{n-1} z^{n-1} + \cdots + a_0$ has all real roots but couldn't figure out how to descend from one real rooted polynomial to another while keeping the roots real. I'm feeling annoyed with myself for not thinking harder about what would happen if I allowed complex roots. Just for the fun of it, here is how far I had gotten.

$\endgroup$
2
  • $\begingroup$ Wow indeed! Thanks for linking your PDF. $\endgroup$
    – Suvrit
    May 29, 2015 at 21:07
  • 2
    $\begingroup$ My thought was actually is that if it doesn't work for all complex roots, then I am not going to bother with it, as it seems too subtle :) I was encouraged by $n=2$ though. $\endgroup$ May 29, 2015 at 22:17
6
$\begingroup$

The article http://arxiv.org/abs/1410.2706 by Neff and Pompe gives a criterion, for which functions the partial derivative with respect to the elementary symmetric polynomials is nonnegative (and checks it for log^2).

The difficult part here is not to show that the partial derivatives are nonnegative, but to show that this already implies the conjecture. The reason is that the function, whose partial derivatives then are checked, is defined on a not-so-nice set, namely

S={(e_1(x_1,...,x_n),e_2(x_1,...,x_n),...,e_n(x_1,...,x_n)); x_i>0},

which is, e.g., non-convex. (And it is not difficult to find functions with nonnegative partial derivatives and sufficiently "strange" domain, which are not monotone.) Maybe S has some structure that can be used, but I do not see it.

A large part of the article mentioned (probably for this reason) is concerned with the construction of curves, along which the nonnegativity of partial derivatives can be utilized in order to obtain monotonicity.

Difficulties with the "only real"-approach appear at the boundary of the set S - there, invoking the implicit function theorem becomes impossible.

Of course, by his clever idea to consider the question over the complex numbers, the function in Lev Borisov's solution is defined on a much larger (and convex) set and thereby this problem is avoided entirely. Congratulations.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.