16
$\begingroup$

The problem is to find the asymptotics (as $n\to\infty$) of the maximum (say $M_n$) of the Vandermonde determinant $$V_n:=\prod_{0\le i<j\le n-1}(a_j-a_i) $$ over all $a_0,\dots,a_{n-1}$ such that $0=a_0<\dots<a_{n-1}=1$ (or, better, an upper bound on $M_n$ which is asymptotic to $M_n$; or, at least, the asymptotics of $\ln M_n$). It is clear that the maximum is attained.

These questions can be obviously restated in terms of the minimization of the logarithmic energy $$\sum_{0\le i<j\le n-1}\ln\frac1{a_j-a_i}. $$

I have encountered this problem working on a matter involving higher-order divided differences. It is known that the $n$-tuple $(a_0,\dots,a_{n-1})$ maximizing $V_n$ is given by the formula $a_i=(1+x_i)/2$, where the $x_i$'s are the roots of the polynomial $(1-x^2)P'_{n-1}(x)$ (taken in the ascending order) and $P_{n-1}$ is the Legendre polynomial of degree $n-1$; these points $x_0,\dots,x_{n-1}$ are also known as the Fekete points; see e.g. SE Mathematics. The picture below suggests that $\ln M_n\sim-(a+bn)^2$ as $n\to\infty$, for some real constants $a<0$ and $b>0$.

graph

$\endgroup$
2
  • $\begingroup$ The AGM inequality gives an upper bound with sum instead of the product. Are there a close form for this sum? By all means many terms in this sum are cancelled, is not it possible to find the close form for the rest? $\endgroup$ – Sergei Jun 28 '15 at 9:05
  • $\begingroup$ Sergei: I don't see how the AGM inequality could be useful here. It works well when the terms are close to one another. But this is not the (extremal) case here, even if you rewrite the differences $a_j-a_i$ as the sums of some of the $h_k$'s, where $h_k:=a_k-a_{k-1}$. $\endgroup$ – Iosif Pinelis Jun 28 '15 at 18:43
11
$\begingroup$

Write $V(a)$ for the determinant $\prod_{0\leq i<j\leq n-1} |a_i-a_j|$. Selberg's formula tells you that

$$\int_0^1 \cdots \int_0^1 V(a)^{2\beta} \prod_{i=0}^{n-1} da_i= n! \prod_{j=0}^{n-1} \frac{(\Gamma(1+j\beta))^2 \cdot \Gamma((j+1)\beta)} {\Gamma(2+(n+j-1)\beta)\cdot \Gamma(\beta)}=:A(n,\beta)$$

Thus the asymptotics you seek are given by $\lim_{\beta\to\infty} A(n,\beta)^{1/2\beta}$, which can be read from known asymptotics for the Gamma function. I did not try to perform the actual computation.

Remark: The constant $-2b^2$ is the maximum of the logarithmic energy $$\int \log |x-y| \mu(dx) \mu(dy) $$ over all probability measures supported on $[0,1]$. I am sure that this maximizer has been computed somewhere; Maybe it appears in Saff and Totik's book, which I do not have access to at the moment.

$\endgroup$
4
  • $\begingroup$ may be a trivial AGM inequality is enough? $\endgroup$ – Sergei Jun 26 '15 at 18:45
  • $\begingroup$ Thank you! Selberg's formula (of which I did not know) looks promising. I also expect to find Saff and Totik's book (of which I did not know either) useful. (Concerning "The constant $b$", did you mean $-2b^2$?) $\endgroup$ – Iosif Pinelis Jun 26 '15 at 20:30
  • $\begingroup$ I still think there should be a minus before $2b^2$ (for one reason, $\log|x-y|\le0$ for $x$ and $y$ in $[0,1]$). $\endgroup$ – Iosif Pinelis Jun 26 '15 at 20:37
  • $\begingroup$ You are right of course. $\endgroup$ – ofer zeitouni Jun 26 '15 at 21:01
8
$\begingroup$

Since you know already that the optimal $a_i$ have $2a_i + 1 = x_i = \pm 1$ and the roots of $P'_{n-1}$, the calculation of $V_n$ comes down to the discriminant of $P'_{n-1}$, its leading coefficient, and its values at $\pm 1$, all of which are available in closed form via formulas for Jacobia polynomials (since $P'_{n-1}$ is a multiple of $P^{(1,1)}_{n-2}$). For the asymptotic growth of $\log M_n$, as ofer zeitouni suggests it is enough to find the maximum of the logarithmic energy $\int\!\!\int \log|x-y| \, d\mu(dx) \, d\mu(dy)$ over probability measures supported on $[0,1]$, and it is known that the optimal $\mu$ is the measure $\pi^{-1} dx/\sqrt{x-x^2}$ obtained from the uniform measure $d\theta$ on ${\bf R} / \pi{\bf Z}$ via $x = \cos^2 \theta$. The leading term is $\log M_n \sim -b n^2$ with $b=\log 2$, because the optimal measure on an interval of length $4$ has logarithmic energy zero so the average of the $n \choose 2$ terms for $(0,1)$ approaches $-\log 4$.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer! I'll now take a break and come back to this hopefully on Sunday to look for these results in the literature. $\endgroup$ – Iosif Pinelis Jun 26 '15 at 22:48
5
$\begingroup$

I am amazed that nobody noticed that Iosif asks for the calculation of the transfinite diameter of the interval $[0,1]$. This notion applies to arbitrary compact domains $K$ in ${\mathbb R}^n$ : $$d(K)=\lim_{k\rightarrow+\infty}\sup_{x_1,\ldots,x_k\in K}\left(\prod_{\alpha<\beta}|x_\alpha-x_\beta|\right)^{2/k(k-1)}.$$ In the particular case where $K\subset{\mathbb C}$ is simply connected, then the inverse of $d(K)$ is the conformal radius of ${\mathbb C}\setminus K$.

$\endgroup$
2
  • $\begingroup$ Yes, I have to edit my post ! $\endgroup$ – Denis Serre Jun 29 '15 at 13:12
  • $\begingroup$ Thank you Denis for another interesting connection. However, as I wrote in my answer, it was very surprising to me to find that at least for large enough $n$ the quantity $M_n^{2/n^2}$ that I asked about cannot be approximated quite well by (let alone be written as) the logarithmic capacity $\exp\max_\mu E_\mu$, which latter coincides with the transfinite diameter, per goo.gl/SdOmVJ . One may also want to look at the question at goo.gl/vF6kNT . $\endgroup$ – Iosif Pinelis Jun 29 '15 at 13:58
3
$\begingroup$

I would like to provide some details on the answers by ofer zeitouni and Noam D. Elkies.
By Selberg's formula, as presented in the answer by ofer zeitouni, one easily finds
$$(1)\qquad M_n=\lim_{\beta\to\infty} A(n,\beta)^{1/(2\beta)}= \prod _{j=0}^{n-1} \frac{j^j (j+1)^{(j+1)/2}}{(j+n-1)^{(j+n-1)/2}} $$ (with $0^0:=1$), which follows immediately from the observation that for any real $a$ and any real $c>0$ $$\Gamma(a+c\beta)^{1/(2\beta)}\sim(c\beta/e)^{c/2} $$ as $\beta\to\infty$.

I asked for an upper bound on $M_n$, which would be asymptotic to $M_n$, thinking that an explicit expression for $M_n$ would not be possible. However, as is now clear from the answers by ofer zeitouni and Noam D. Elkies, such an expression is not so hard to obtain, and formula (1) presents this expression.

On the other hand, the relation between the logarithmic energy
$E_{n,a}:=2\sum_{0\le i<j\le n-1}\ln(a_j-a_i)$ and its ostensibly more general version $n^2E_\mu$ with $E_\mu:=\int\ln|x-y|\mu(dx) \mu(dy)$ for probability measures $\mu$ supported on $[0,1]$ seems unclear, I guess because of the singularities on the diagonal. Namely, one would expect that $$(2)\qquad 2\ln M_n=\max_{0=a_0<\dots<a_{n-1}=1}E_{n,a} \le n^2 \max_\mu E_\mu. $$ However, it is not clear if $2E_{n,a}=2\sum_{0\le i<j\le n-1}\ln(a_j-a_i)$ could be written as $n^2E_\mu=n^2\int\ln|x-y|\mu(dx) \mu(dy)$ for some probability measure $\mu$ on $[0,1]$.

In fact, quite surprisingly to me, the inequality in (2) is false, at least for large enough $n$. Indeed, it is not hard to show based on formula (1) that for some real $c\in(0,\infty)$ $$(3)\qquad M_n=(c+o(1))m_n,\quad\text{where}\quad m_n:=2^{-n^2} \sqrt{(n-1)!}\,(8e)^{n/2} n^{3/8} $$ $$(4)\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad >>2^{-n^2}=\text{(?)}=\exp\Big\{\frac{n^2}2\,\max_\mu E_\mu\Big\}. $$ The asymptotics $M_n=(c+o(1))m_n$ follows because $$\ln\frac{M_{n+1}}{M_n} =-n \ln2+\frac{n-1}{2}\,\ln (n-1)+\frac{n+1}{2}\,\ln (n+1)-\frac{2n-1}{2}\,\ln(2 n-1)$$ $$=d_n+O(1/n^2)$$ for large $n$, where $d_n:=\frac{3}{8 n}-2n\ln2+\frac{1}{2}\ln n+\frac12(1+\ln2)$.

A curious corollary to (3)--(4) is that for each large enough natural $n$ there is some $a=(a_0,\dots,a_{n-1})$ with $0=a_0<\dots<a_{n-1}=1$ such that $2E_{n,a}$ cannot be approximated by (let alone written as) $n^2E_{\mu_k}$ for any sequence $(\mu_k)$ of probability measures on $[0,1]$.

Yet, it also follows from (3)--(4) that the logarithmic asymptotics $\ln M_n\sim\frac{n^2}2 \max_\mu E_\mu$ holds.

One can also see that $\ln(M_{n+1}/M_n)<d_n$ for $n\ge4$, and hence for each $k\ge4$ and all $n>k$ one has the upper bound $M_k\exp\sum_{j=k}^{n-1}d_j$ on $M_n$, which is asymptotic to $M_n$ as $n>k\to\infty$. In particular, for $n\ge4$ one has $M_n<\tilde c_4 m_n$, where $m_n$ is as before and $\tilde c_4:=\frac{512}{25} \sqrt{\frac{2}{15}} e^{(6 \gamma -43)/16}=0.631\dots$ and $\gamma$ is the Euler constant.

$\endgroup$
3
  • $\begingroup$ Added a remark that in general the discrete logarithmic energy $2E_{n,a}$ cannot be approximated by its ostensibly more general counterpart $n^2 E_\mu$, for any probability measure $\mu$ on $[0,1]$. $\endgroup$ – Iosif Pinelis Jun 29 '15 at 3:58
  • 1
    $\begingroup$ The two forms of Selberg's formula are the same (the form I wrote is from Anderson's proof, which is reproduced in our RMT book with Guionnet; but with some effort, using the n!, you can check they are the same formula). There is a very nice review of Selberg's formula by Forrester, which is highly recommended and entertaining reading. See ams.org/journals/bull/2008-45-04/S0273-0979-08-01221-4/… $\endgroup$ – ofer zeitouni Jun 30 '15 at 18:45
  • $\begingroup$ Of course, they are the same; sorry for having been too hasty, and thank you for your comment. I have now edited my answer accordingly. $\endgroup$ – Iosif Pinelis Jun 30 '15 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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