How to best distribute points on two concentric circles? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T14:46:50Z http://mathoverflow.net/feeds/question/21298 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21298/how-to-best-distribute-points-on-two-concentric-circles How to best distribute points on two concentric circles? 002 2010-04-14T03:56:17Z 2010-04-17T16:45:59Z <p>An N-subset <code>$\{x_1,\dots,x_N\}$</code> of a compact set $X\subset \mathbb R^d$ is called a set of <em>Fekete points</em> (named after <a href="http://en.wikipedia.org/wiki/Michael_Fekete" rel="nofollow">Michael Fekete</a>) if it maximizes the product <code>$$\prod_{1\le k&lt;j\le N}|x_k-x_j|\qquad (1)$$</code> 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.</p> <p>When $X$ is a circle, Fekete points are equally spaced. This is well-known and can be proved like this: we may assume <code>$x_k=\exp(i\theta_k)$</code> with <code>$0=\theta_1&lt;\theta_2&lt;\dots &lt;\theta_N&lt;2\pi$</code>. For a fixed integer $m$, $1\le m\le \lfloor N/2 \rfloor$, consider the product <code>$\Pi(m)=\prod_{k=1}^N|x_{k+m}-x_{k}|$</code> with indices taken mod $N$. Since each point <code>$x_k$</code> 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.)</p> <p>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 -</p> <blockquote> <p>Under the assumptions of the preceding paragraph, is the product (1) maximized by equally spaced, interlaced points? E.g., by <code>$$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)$$</code></p> </blockquote> <p>Presumably, a solution would consist of two steps. </p> <ol> <li>Show that the maximum is attained by interlaced points, i.e., when ordered by the argument, the points alternate between the two circles. </li> <li>Show that for interlaced points, maximum of (1) is attained when they are equally spaced. </li> </ol> <p>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. </p> <p>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 <strong>two</strong> 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. </p> http://mathoverflow.net/questions/21298/how-to-best-distribute-points-on-two-concentric-circles/21325#21325 Answer by damiano for How to best distribute points on two concentric circles? damiano 2010-04-14T11:31:55Z 2010-04-14T11:31:55Z <p>(This was too long to fit in a comment.)</p> <p>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?</p>