Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 16 down vote favorite
2

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\}$

share|improve this question
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
2  
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 Narain Dec 23 '10 at 20:19
show 2 more comments

1 Answer

up vote 13 down vote accepted

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.

share|improve this answer
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
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. – 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"... – J. M. Dec 24 '10 at 0:43
1  
Here's a good reference, I think: Saff & Totik books.google.com/… – Hans Lundmark Dec 24 '10 at 15:34
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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