# Spreading points in the unit interval to maximize the product of pairwise distances

This is prompted by question 15312, but moved to the reals. It must be solved already. Pick n points $x_i \in [0,1]$ to maximize $\prod_{i < j} (x_i - x_j)$. A little playing shows you don't want them evenly distributed-they need to push out to the ends. With four points, Alpha says to use $\{0,\frac{1}{2}\pm\frac{1}{2\sqrt{5}},1\}$ and with five, $\{0,\frac{1}{2}-\frac{\sqrt{\frac{3}{7}}}{2},\frac{1}{2},\frac{1}{2}+\frac{\sqrt{\frac{3}{7}}}{2},1\}$

-
Looks like the title should read "maximize the product of pairwise distances", rather then "sum of pairwise products"? –  Alon Amit Dec 23 '10 at 19:40
Fixed the title. Not sure of the the tags, though. –  Aryabhata Dec 23 '10 at 20:02
You are right. Thanks. –  Ross Millikan Dec 23 '10 at 20:10
What does 'push out to the ends' mean? 1/2 + 1/(2 sqrt(7)) is less than 0.69, so in this case the points are pushing in to the centre. But +1 for the question –  TonyK Dec 23 '10 at 20:13
Physically, this corresponds to the equilibrium distribution of $n$ points under a pairwise repulsion potential $U(r) = -\log \lvert r \rvert$. People tend to study electrostatic potential instead, $U(r) = 1/r$, but in 1D it feels like there should be a closed-form solution for either case. I don't know what it is, though. –  Rahul Dec 23 '10 at 20:19

These points are known as Fekete points. A general Fekete problem is to maximize the product $$\max_{z_1,...,z_n\in E}\prod\limits_{\quad 1\leq i < j \leq n}|z_i-z_j|$$ where $E\subset \mathbb C$.

In case $E=[-1,1]$, there is a unique solution and the corresponding points coincide with the zeros of $(1-x^2)P'_{n-1}(x)$, where $P_{n-1}$ is the Legendre polynomial of degree $n-1$.

I cannot give a precise reference at the moment, but this can be probably found in Szegő's book on orthogonal polynomials.

-
Apparently, these are also called Gauss-Labatto points. –  Aryabhata Dec 23 '10 at 21:34
I think Gauss-Labatto is specific to the case of one real dimension. (Which, obviously, is what the OP asked about.) And I think (I maybe wrong on this count) their constructions/motivations are different. –  Willie Wong Dec 23 '10 at 22:01
@Willie: Yeah, I was trying to find a reference for Andrey when I came across this. Just thought it might be interesting and might help find a reference. –  Aryabhata Dec 23 '10 at 22:51
@Willie, Mo is correct, "Gauss-Lobatto nodes" does refer to the roots of the derivative of the Legendre polynomial (not counting the "fixed" nodes at $\pm 1$). Another keyword one could use apart from "Fekete" is "Leja sequence"... –  Ｊ. Ｍ. Dec 24 '10 at 0:43
Here's a good reference, I think: Saff & Totik books.google.com/… –  Hans Lundmark Dec 24 '10 at 15:34