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\}$
Spreading points in the unit interval to maximize the product of pairwise distances
20
$\begingroup$
real-analysis
analysis
-
1Looks like the title should read "maximize the product of pairwise distances", rather then "sum of pairwise products"? – 2010-12-23
-
0Fixed the title. Not sure of the the tags, though. – 2010-12-23
-
0You are right. Thanks. – 2010-12-23
-
2What 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 – 2010-12-23
-
0Physically, 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. – 2010-12-23
-
0@Tony K: You are right. I found an error in what I fed Alpha. Now the second point of 5 is at .17267, which is pushed out. – 2010-12-23
-
0@Rahul: Logarithmic potentials are well studied. See the book by Saff & Totik in my comment to Andrey's answer. – 2010-12-24
1 Answers
17
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.
-
0Apparently, these are also called Gauss-Labatto points. – 2010-12-23
-
0I 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. – 2010-12-23
-
1@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. – 2010-12-23
-
0@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"... – 2010-12-24
-
0[...and here's a quick way of generating them from Wolfram Alpha](http://tinyurl.com/395oobb). – 2010-12-24
-
0@J.M.: my point is that I don't think Fekete points are defined to be the roots of the derivative of the Legendre polynomial, at least not according to the definition that Andrey gave. So while the Gauss-Labatto points coincide with the Fekete points for $[-1,1]$, they are not defined from the same starting points. – 2010-12-24
-
1Here's a good reference, I think: Saff & Totik http://books.google.com/books?id=0-pJz_ntKH4C&printsec=frontcover&dq=saff+totik&source=bl&ots=0d3H8YKQ1x&sig=ybUpwFUiK4fAiWXv0ybdx-6Tesg&hl=en&ei=Ab0UTdioNIik8QPZkqGDBw&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBIQ6AEwAA#v=onepage&q&f=false – 2010-12-24
-
0@Willie: Yes, there is an ambiguity in what "these" in "these are also called Gauss-Labatto.." refers to. I intended to refer to the roots of the derivative of Legendre, while you interpreted them to refer to the points of the question. – 2010-12-24
-
0@Hans since you added the "I think": do you mean that is a reasonable reference from your search, or is that actually a recommendation for the book? I can't get to the library right now, but if it is the latter, I should go check it out when I get back. Thanks. – 2010-12-27
-
1@Willie: What I meant is that I'm under the impression that it's one of the standard references on the subject, but I haven't read it myself (unfortunately). I read a tiny bit about this in Percy Deift's *Orthogonal Polynomials and Random Matrices* years ago, and the book by Saff & Totik was recommended there, along with *Foundations of Modern Potential Theory* by N. S. Landkof (which I haven't read either). – 2010-12-27