12
$\begingroup$

An N-subset $\{x_1,\dots,x_N\}$ of a compact set $X\subset \mathbb R^d$ is called a set of Fekete points (named after Michael Fekete) if it maximizes the product $$\prod_{1\le k<j\le N}|x_k-x_j|\qquad (1)$$ among all such $N$-tuples. When $X\subset \mathbb C$, one can express this product in terms of the Vandermonde determinant. In this case Fekete points are of particular interest in approximation theory (as interpolation nodes). Generally, they have no explicit form and must be found numerically. But there are exceptions.

When $X$ is a circle, Fekete points are equally spaced. This is well-known and can be proved like this: we may assume $x_k=\exp(i\theta_k)$ with $0=\theta_1<\theta_2<\dots <\theta_N<2\pi$. For a fixed integer $m$, $1\le m\le \lfloor N/2 \rfloor$, consider the product $\Pi(m)=\prod_{k=1}^N|x_{k+m}-x_{k}|$ with indices taken mod $N$. Since each point $x_k$ appears in just two terms of this product, it is not hard to see that $\Pi(m)$ is maximal when $x_k$ are equally spaced. (Indeed, $\log \sin$ is a concave function.)

Now let $X$ be the union of two concentric circles of radii $r$ and $R$. Assume that $N=2n$ is even and that exactly $n$ of the points lie on each circle. With this additional assumption we are not quite in the Fekete problem anymore, but we have an obvious candidate for the maximum -

Under the assumptions of the preceding paragraph, is the product (1) maximized by equally spaced, interlaced points? E.g., by $$x_k=\begin{cases} r\exp(2\pi i k/n), \quad k=1,\dots,n \\ R\exp(\pi i (2k-1)/n), \quad k=n+1,\dots,2n \end{cases} \qquad (2)$$

Presumably, a solution would consist of two steps.

  1. Show that the maximum is attained by interlaced points, i.e., when ordered by the argument, the points alternate between the two circles.
  2. Show that for interlaced points, maximum of (1) is attained when they are equally spaced.

One can hope that step 2 is doable with standard calculus tools, since there should be no other local maxima for interlaced points. But Step 1 seems to require a more imaginative approach.

Why do I find this question interesting? There is a natural way to distribute N points on a circle (i.e., at equal distances), and this configuration is known to give the solution for many extremal problems, such as the Fekete problem, isoperimetric N-gon problem, etc. There is also a natural way to distribute two sets of N points -- namely, by formula (2), but I don't know of any nontrivial problem for which the optimality of such configuration has been established.

$\endgroup$
3
  • $\begingroup$ Another idea would be to consider the process where we replace all points with the midpoints of the arcs between them. If one can prove that such a process increases the value of the product of the pairwise distances then the result follows, because the points converge to respective equidistributions. (This is how I visualize the proof for the circle case) $\endgroup$ Apr 14, 2010 at 9:09
  • $\begingroup$ Perhaps you could start by seeing whether the arguments of a locally optimal configuration change much when varying R/r, then reducing to the large R/r limit. $\endgroup$
    – S. Carnahan
    Apr 17, 2010 at 17:14
  • 3
    $\begingroup$ Were you able to finish it with Damiano's method? $\endgroup$
    – Will Jagy
    Apr 18, 2010 at 1:37

1 Answer 1

2
$\begingroup$

(This was too long to fit in a comment.)

For subsets of the complex plane, a slightly different perspective is that the square of the quantity you want to maximize is the absolute value of the discriminant of the monic polynomial whose roots are precisely the points. Up to a factor depending only on the degree, the discriminant of a monic polynomial is the product of the values of the polynomial at the roots of the derivative. Also note that in the configuration you suggested, the derivative of the polynomial is almost the optimal polynomial for points on a circle: maybe you can prove that the derivative of an optimal polynomial is close to an optimal polynomial?

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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