Characterization of Logarithmic Fekete Critical Configurations of at Most Six Points in All Dimensions Diego Armentano, Leandro Bentancur, Federico Carrasco, Marcelo Fiori, Matías Valdés, Mauricio Velasco Abstract We consider the logarithmic Fekete problem, which consists of placing a fixed number of points on the unit sphere in ℝ d \mathbb{R}^{d} , in such a way that the product of all pairs of mutual Euclidean distances is maximized or, equivalently, so that their logarithmic energy is minimized. Using tools from Computational Algebraic Geometry, we find and classify all critical configurations for this problem when considering at most six points in every dimension d d . In particular, our approach gives new proofs of several key results appearing in the literature, with the benefit of using a unified approach. Furthermore, for seven points in S 2 S^{2} , we characterize the global minimizer among critical configurations having at least one pair of antipodal points, and give numerical evidence to support the conjecture that this configuration is also the unrestricted global minimizer. Keywords: Fekete, logarithmic energy, critical points, Gröbner basis, msolve. 1 Introduction Consider the problem of placing n different points on the unit sphere S^{d-1}\subset\mathbb{R}^{d} , in such a way that the product of their mutual Euclidean distances is maximized: \argmax_{w=(w_{1},\dots,w_{n})\in(S^{d-1})^{n}}\prod_{i=1}^{n}\prod_{j=i+1}^{n}\|w_{i}-w_{j}\|^{2}. (1) Taking logarithm in the objective function, we obtain an equivalent problem, known as the logarithmic Fekete problem: \argmin_{w\in(S^{d-1})^{n}}-\sum_{i=1}^{n}\sum_{j=i+1}^{n}\log\left(\|w_{i}-w_{j}\|^{2}\right). (2) This is considered a highly non-trivial optimization problem, with exact solutions known only for a few values of n . Indeed, Smale’s 7th problem, listed among the key open problems for the 21st century by Steve Smale, asks whether it is possible to find n points on the sphere S^{2} in polynomial time in n , so that its logarithmic energy differs from the optimal value by at most c\ln n , for a universal constant c [ 29 ] . A key difficulty of this problem is that the optimal value remains unknown to logarithmic precision [ 10 , 6 ] . There are several lines of research related to this problem. Among them, we highlight two. One focuses on constructing random or deterministic configurations with “good” energy values for an arbitrary number of points, usually large or asymptotic [ 3 , 1 , 5 ] . The other aims to characterize optimal configurations for specific values of n , typically small ones. Our work falls within this latter setting. While the solution to this problem is known only for a few values of n , namely, n\leq 6 and n=12 , even less is understood about the critical configurations. For example, even for some values of n where the solution is known, the complete set of critical configurations is unknown. In this work, using a unified methodology, we find and classify all the critical configurations of the logarithmic Fekete problem, for the case of at most six points, and for spheres of all possible dimensions. In this setting, we recover the previously reported solutions, and we show that there are no spurious local minima in S^{2} . Our strategy for determining all critical configurations of Problem ( 2 ) proceeds as follows. First we define a system of polynomial equations, associated to the critical configurations. Then we count the number of complex solutions of the polynomial system, by computing a Gröbner basis for its ideal. We call this quantity the “expected number of solutions”. Observe that regardless of whether the ideal is radical, this is an upper bound on the number of real solutions of the problem. Simultaneously, we find as many solutions of the polynomial system as we can, and compare the number of found solutions with the upper bound. The proof of the Theorem is achieved because we are able to find enough solutions so as to exactly match the upper bound, guaranteeing that our list of critical configurations is exhaustive. The construction of solutions is done using different approaches. In the case of four and five points, we are able to find all solutions by considering natural symmetric configurations. For six points, imagination is not enough, and we use Gröbner bases to find additional solutions. The only problem with the above strategy is that the locus of critical points in (S^{d-1})^{n} does not form a zero-dimensional variety because it is invariant under the action of the orthogonal group. In order to recover finiteness, we reformulate the problem modulo the orthogonal group action. Doing so recovers finiteness and leads to a simpler formulation, which allows us to carry out the desired classification. The source code for reproducing our results is available at: www.github.com/matiasvd . 2 Related work For S^{1} , the solution of Problem ( 2 ) is known for any number of points, and is given by n equidistributed points [ 11 , Theorem 2.3.3] . We denote this configuration as n -gon or “Equator”. For S^{2} , the solutions are known only for up to six points [ 2 , 26 , 15 ] , and for twelve points [ 2 ] . For S^{3}\subset\mathbb{R}^{4} and six points, the solution is given by two equilateral triangles, inscribed in two great circles S^{1} , orthogonal to each other [ 17 , Theorem 1.9] . We denote this configuration as 3_{S^{1}}\times 3_{S^{1}} . Table 1 lists the known solutions for up to six points, for all possible dimensions of the sphere. We use the term (n-1) -simplex for the configuration that has n points on the sphere S^{d-1} , all at the same distance from each other. The (n-1) -simplex is the optimal configuration for n points on S^{d-1} , whenever d+1\geq n\geq 3 [ 26 ] . Note that the 3-simplex is the regular Tetrahedron. Table 1: Known optimal configurations of the logarithmic Fekete problem for at most six points. n S^{1} S^{2} S^{3} S^{4} 3 2-simplex N/A N/A N/A 4 4-gon Tetrahedron [ 26 ] N/A N/A 5 5-gon Bipyramid [ 15 ] 4-simplex [ 26 ] N/A 6 6-gon Octahedron [ 26 ] 3_{S^{1}}\times 3_{S^{1}} [ 17 ] 5-simplex [ 26 ] Regarding critical configurations of Problem ( 2 ), little is known about them, even for the cases where the solutions are known. One thing that is known is that the problem has no local maxima [ 7 , Corollary 1.3] , and that critical configurations always have center of mass zero [ 15 , Proposition 2] . It is also known that the global minima is not always unique. In particular, if q=p^{l} , with p>2 prime and l\geq 1 , taking n=(q+1)(q^{3}+1) points on S^{d-1} , d=q\frac{q^{3}+1}{q+1} , there are \lfloor(l-1)/2\rfloor essentially different global minima [ 4 , Section 1] . On the other hand, in [ 17 , 16 ] , the authors study the critical configurations for d+2 points on S^{d-1} , and give a method to classify all critical configurations, and to characterize the non-degenerate ones. Moreover, for six points in S^{3} , they find the global minimum and give the first known case of a spurious local minima. Also, the only saddle points that are explicitly mentioned in the literature are the Equator [ 28 , Section 2] , and two configurations for six points in S^{3} [ 17 , 16 ] . Another natural question is whether every saddle may be classified using the Hessian. This is particularly important for numerical optimization [ 21 , 25 ] . For 7 points on S^{2} , there is a critical configuration that the Hessian does not classify [ 13 , Remark 6.3] , although it is believed that it is a global minimum [ 8 ] [Conjecture 11.1]. Finally, based on numerical experiments, it is conjectured that the number of spurious local minima in S^{2} increases “dramatically” with the number of points [ 27 , Section 4] , although no spurious local minima are known in this dimension. Contributions We introduce an approach that transforms the real optimization problem of Fekete points into a novel problem amenable to the methods of Computational Algebraic Geometry (over the complex numbers). In principle, this methodology allows us to find and classify all critical configurations of n points in S^{d-1} , without assuming any relation between n and d , modulo sufficient computational resources. We apply this method successfully for up to six points in all dimensions, recovering previously known results in a unified framework. Although the optimal configuration for six points in S^{2} was already reported, our method obtains the first exhaustive list of all critical configurations and their classification. For six points in S^{3} , since our method obtains all critical configurations, including the degenerate ones, this complements the results of [ 17 , 16 ] , giving an exhaustive list of all critical configurations in this case. Finally, for seven points in S^{2} , we prove that if a solution to the Fekete problem has a dipole, then it is given by configuration 1:5:1, which is the solution conjectured via numerical experiments. If 1:5:1 is indeed the global minimum, our theorem reduces the problem of proving that it is optimal to verifying that some minimizer of the Fekete problem must have a dipole. We also provide numerical evidence in favor of the optimality of 1:5:1. 3 Formulation and computational algebraic tools 3.1 System of critical configurations The Lagrangian of Problem ( 2 ) is: L(w,\lambda):=-\sum_{i=1}^{n}\sum_{j=i+1}^{n}\log\left(\|w_{i}-w_{j}\|^{2}\right)+\sum_{i=1}^{n}\lambda_{i}\left(\|w_{i}\|^{2}-1\right). A critical configuration is a sequence (w_{1},\ldots,w_{n}) on the product of spheres, for which there exist multipliers (\lambda_{1},\ldots,\lambda_{n}) , such that the Lagrangian has null gradient with respect to w : \frac{\partial L(w,\lambda)}{\partial w_{k}}=-\sum_{j=1,j\neq k}^{n}\frac{2\left(w_{k}-w_{j}\right)}{\|w_{k}-w_{j}\|^{2}}+2\lambda_{k}w_{k}=\vec{0},\quad\forall\ k=1,\ldots,n. Taking dot product with w_{k} , and using that \|w_{k}-w_{j}\|^{2}=2-2w_{k}^{T}w_{j} on the sphere, we obtain the values of the multipliers, which happen to be all equal and constant: \lambda_{k}=\frac{n-1}{2},\quad\forall\ k=1,\ldots,n. Thus, the critical configurations are those points on the sphere \|w_{k}\|^{2}=1,\quad\forall\ k=1,\ldots,n, (3) which also satisfy the null gradient condition: \frac{n-1}{2}w_{k}-\sum_{j=1,j\neq k}^{n}\frac{w_{k}-w_{j}}{\|w_{k}-w_{j}\|^{2}}=\vec{0},\quad\forall\ k=1,\ldots,n.\\ (4) An interesting property of the critical configurations of Problem ( 2 ), is that their center of mass must be null: \sum_{k=1}^{n}w_{k}=\vec{0}. (5) This is obtained by summing the equations ( 4 ) and noting that: \sum_{k=1}^{n}\sum_{j=1,j\neq k}^{n}\frac{w_{k}-w_{j}}{\|w_{k}-w_{j}\|^{2}}=\vec{0}, because for every term w_{k}-w_{j} , the summation includes a corresponding w_{j}-w_{k} term. Searching for critical configurations of the Fekete problem means finding solutions to the system of polynomial equations defined by ( 3 ) and ( 4 ), to which we will add ( 5 ), which follows from the previous ones and does not modify the set of solutions. 3.2 Removing orthogonal symmetry An important property of the system of equations defined in the preceding section is that the system is invariant under isometries of the sphere. More precisely, if Q\in\mathbb{R}^{d\times d} is an orthogonal matrix, and (w_{1},\ldots,w_{n}) is a critical configuration, then (Qw_{1},\ldots,Qw_{n}) is also a critical configuration. Thus, given a critical configuration, we obtain an infinite number of them by applying rotations. As our method relies on counting solutions, we need a system with a finite number of solutions. For this, we consider another system of equations, where variables are the dot products of pairs of points: x_{ij}:=w_{i}^{T}w_{j},\quad i\neq j. Note that these variables represent the cosine of the angles between pairs of points. To obtain the new system of equations, we first take dot product in equation ( 4 ), with respect to each point w_{i} : \sum_{j=1,j\neq k}^{n}\frac{w_{i}^{T}w_{k}-w_{i}^{T}w_{j}}{\|w_{k}-w_{j}\|^{2}}=\frac{n-1}{2}w_{i}^{T}w_{k},\quad\forall\ k,i=1,\ldots,n. As w_{l}^{T}w_{l}=1,\forall\ l=1,\ldots,n , we have: \|w_{k}-w_{j}\|^{2}=2(1-w_{k}^{T}w_{j}) . Using this, the equations may be written in the new variables as: \sum_{j=1,j\neq k}^{n}\frac{x_{ik}-x_{ij}}{1-x_{kj}}=(n-1)x_{ik},\quad\forall\ k\neq i. (6) Note that for k=i the equation is trivial. We then consider Equation ( 5 ), were we also take dot product with respect to each point w_{j} : \sum_{k=1}^{n}w_{j}^{T}w_{k}=0,\quad\forall\ j=1,\ldots,n. Using w_{j}^{T}w_{j}=1 , the equations in the new variables are: 1+\sum_{k=1,k\neq j}^{n}x_{jk}=0,\quad\forall\ j=1,\ldots,n. (7) Equations ( 6 ) and ( 7 ) determine the new system of equations in the variables x_{ij} . The condition w_{i}\in S^{d-1} of equation ( 3 ) is now implicit, and we will not define variables x_{ii} . 3.3 Relation between solutions of both systems Any solution in the variables w_{i} has an associated solution x_{ij}=w_{i}^{T}w_{j} . The reciprocal is also true, provided that we consider complex solutions. That is: given a solution x_{ij}\in\mathbb{C} , there is a solution w_{i}\in\mathbb{C}^{d} , with x_{ij}=w_{i}^{T}w_{j} . To see this, we first define two matrices. Definition 1 (Dot product matrix) . Let x_{ij}\in\mathbb{C},\ 1\leq i0 , \tau>0 , \alpha_{0}>0 , maxIters. Retraction and Projection operators R_{w} and P_{w} , respectively. Output: configuration w^{k} with \|P_{w^{k}}\left(\nabla E_{\log}(w^{k})\right)\|\leq\text{gradTol} . 1: k\leftarrow 0 , \alpha\leftarrow\alpha_{0} 2: \nabla_{T}E_{\log}\leftarrow P_{w^{k}}\left(\nabla E_{\log}(w^{k})\right) \triangleright Project gradient to tangent space at w^{k} . 3: while k<\text{maxIters and }\|\nabla_{T}E_{\log}\|>\text{gradTol} do 4: 5: while E_{\log}\left(R_{w^{k}}\left(-\alpha\nabla_{T}E_{\log}\right)\right)>E_{\log}(w^{k})-r\alpha\|\nabla_{T}E_{\log}\|^{2} do 6: \alpha\leftarrow\tau\alpha \triangleright Update stepsize with Armijo rule. 7: end while 8: 9: w^{k+1}\leftarrow R_{w^{k}}\left(-\alpha\nabla_{T}E_{\log}\right) \triangleright Update configuration using stepsize \alpha . 10: 11: \alpha\leftarrow\frac{\alpha}{\tau} \triangleright Initial Armijo stepsize for next iteration. 12: 13: \nabla_{T}E_{\log}\leftarrow P_{w^{k+1}}\left(\nabla E_{\log}(w^{k+1})\right) \triangleright Projected gradient for next iteration. 14: 15: k\leftarrow k+1 16: end while For S^{2} we perform 1000 tests, and in all cases we obtain a configuration with energy value: E_{\log}=-16.3649557 , when rounding up to seven digits. For each test, we also check that the estimated solution has a dipole. This, together with Theorem 2 and the termination criteria of the algorithm, implies that each estimated configuration is of the kind 1:5:1. These results suggest the following conjecture, which already appears in the bibliography, although without the details of the numerical experiments in which it is based [ 8 ] [Conjecture 11.1], [ 13 ] [Table 1.1]. Conjecture 1 . Configuration 1:5:1 is the unique kind of solution of the Fekete problem for n=7 points in S^{2} . For S^{3} we perform 5000 tests, and in all cases we obtain a configuration with the following energy, when rounding up to seven digits: E_{\log}=-17.1587805 . For each test, we check that the estimated configuration has the following dot product matrix (or a permutation of it): WW^{T}=\begin{pmatrix}1&-1&0&0&0&0&0\\ -1&1&0&0&0&0&0\\ 0&0&1&-1&0&0&0\\ 0&0&-1&1&0&0&0\\ 0&0&0&0&1&-\frac{1}{2}&-\frac{1}{2}\\ 0&0&0&0&-\frac{1}{2}&1&-\frac{1}{2}\\ 0&0&0&0&-\frac{1}{2}&-\frac{1}{2}&1\\ \end{pmatrix}. This configuration has two dipoles, formed by the pairs (w_{1},w_{2}) , (w_{3},w_{4}) , and a regular simplex given by three points w_{5} , w_{6} and w_{7} . Also, the dipoles are orthogonal to each other and to the regular simplex. Based on the Föpl notation, we denote this configuration as 4_{S^{1}}\times 3_{S^{1}} , where we use \times since the configuration lies in S^{1}\times S^{1} . These experimental results suggest the following conjecture. Conjecture 2 . Configuration 4_{S^{1}}\times 3_{S^{1}} is the unique kind of solution of the Fekete problem for n=7 points in S^{3} . For S^{4} it is known that the Fekete problem has exactly two local minima, with one of them being a spurious local minima [ 16 ] [Theorem 1.1]. In particular, the global minima is given by “two orthogonal simplexes, an equilateral triangle and a regular tetrahedron, inscribed in a great circle and a great 3-D hypersphere” [ 17 ] [Theorem 1.9]. The spurious local minima is given by a dipole and a regular simplex of five points, orthogonal to each other. Our numerical experiments recover both local minima. For this we perform 10.000 tests, and we obtain configurations with two different energy values, as shown in Table 13 in the row of S^{4} . For each energy value, E_{\log}^{(1)} and E_{\log}^{(2)} , we obtain configurations with respective Cartesian coordinate matrices W_{1} and W_{2} , which correspond to the known local minima, as can be seen in the associated dot product matrices: W_{1}W_{1}^{T}=\begin{pmatrix}1&-\frac{1}{3}&-\frac{1}{3}&-\frac{1}{3}&0&0&1\\ -\frac{1}{3}&1&-\frac{1}{3}&-\frac{1}{3}&0&0&0\\ -\frac{1}{3}&-\frac{1}{3}&1&-\frac{1}{3}&0&0&0\\ -\frac{1}{3}&-\frac{1}{3}&-\frac{1}{3}&1&0&0&0\\ 0&0&0&0&1&-\frac{1}{2}&-\frac{1}{2}\\ 0&0&0&0&-\frac{1}{2}&1&-\frac{1}{2}\\ 0&0&0&0&-\frac{1}{2}&-\frac{1}{2}&1\\ \end{pmatrix},\ W_{2}W_{2}^{T}=\begin{pmatrix}1&-1&0&0&0&0&0\\ -1&1&0&0&0&0&0\\ 0&0&1&-\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}\\ 0&0&-\frac{1}{4}&1&-\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}\\ 0&0&-\frac{1}{4}&-\frac{1}{4}&1&-\frac{1}{4}&-\frac{1}{4}\\ 0&0&-\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}&1&-\frac{1}{4}\\ 0&0&-\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}&1\\ \end{pmatrix}. Table 13: RGD for n=7 points in S^{d-1}\subset\mathbb{R}^{d} . Iterations and final energy, with the number of times RGD converges to that value (in percentage). # RGD Iterations Energy values S^{d-1} # RGD tests min. mean max. E_{\log}^{(1)} E_{\log}^{(2)} S^{2} 1.000 20 2921 3073 -16.3649557 (100%) N/A S^{3} 5.000 50 72.6 145 -17.1587805 (100%) N/A S^{4} 10.000 60 98.0 253 -17.4985786 (84.2%) -17.4806735 (15.8%) S^{5} 50.000 18 24.1 58 -17.7932551 (100%) N/A Finally, for seven points in S^{k} , with k\geq 5 , it is known that the problem has a unique global minima, given by the 6-simplex [ 26 ] . We did 50.000 tests for k=5 , and the algorithm always converged to a configuration with the energy of the simplex: \simeq-17.7932551 . This suggests that there are no spurious local minima in this case. 4.5.2 Dipole implies conjectured minima in S^{2} We now prove our main result of this section. Theorem 2 . For the Fekete problem with n=7 points in S^{2} , the only critical configuration having a dipole is the 1:5:1. To prove our result, we work with the system of critical configurations in Cartesian coordinates, as obtained in Section 3.1 , and before taking dot products. This is useful as we want to work in S^{2} , while the dot product formulation gives critical configurations in any sphere dimension. Specifically, we use the following system of equations, with variables w_{i}\in\mathbb{R}^{3} and z_{ij}\in\mathbb{R} : w_{i}^{T}w_{i}=1,\ (n-1)w_{i}-\sum_{j=1,j\neq i}^{n}\left(w_{i}-w_{j}\right)z_{ij}=\vec{0},\ \forall\ i;\quad z_{ij}\left(1-w_{i}^{T}w_{j}\right)=1,\ \forall\ i