20
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Looks like the title should read "maximize the product of pairwise distances", rather then "sum of pairwise products"? $\endgroup$ – Alon Amit Dec 23 '10 at 19:40
  • $\begingroup$ Fixed the title. Not sure of the the tags, though. $\endgroup$ – Aryabhata Dec 23 '10 at 20:02
  • $\begingroup$ You are right. Thanks. $\endgroup$ – Ross Millikan Dec 23 '10 at 20:10
  • 2
    $\begingroup$ 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 $\endgroup$ – TonyK Dec 23 '10 at 20:13
  • $\begingroup$ 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. $\endgroup$ – Rahul Dec 23 '10 at 20:19
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Apparently, these are also called Gauss-Labatto points. $\endgroup$ – Aryabhata Dec 23 '10 at 21:34
  • $\begingroup$ 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. $\endgroup$ – Willie Wong Dec 23 '10 at 22:01
  • 1
    $\begingroup$ @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. $\endgroup$ – Aryabhata Dec 23 '10 at 22:51
  • 1
    $\begingroup$ Here's a good reference, I think: Saff & Totik books.google.com/… $\endgroup$ – Hans Lundmark Dec 24 '10 at 15:34
  • 1
    $\begingroup$ @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). $\endgroup$ – Hans Lundmark Dec 27 '10 at 15:02

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.