gpt 6 astra ultra attempt on Math-478

Polynomial-Time Quasioptimal Logarithmic-Energy Points on the 2-Sphere

Definitions and mathematical statement

For distinct points $x_1,\ldots,x_N$ on the unit sphere $S^2\subset{\mathbb{R}}^3$, define logarithmic energy, using Smale's pair-counting convention, by \[ E(x_1,\ldots,x_N)=\sum_{1\le i<j\le N} \log\frac1{\|x_i-x_j\|},\qquad E_N^{\min}=\inf E. \] Seek a uniform real-number algorithm and an absolute constant $c$ such that, for every $N\ge2$, it produces $N$ points in time polynomial in $N$ and \[ E(x_1,\ldots,x_N)\le E_N^{\min}+c\log N. \] The real-number computation model and admissible operations are those in Smale's Problem 7. This does not silently impose a bit-complexity bound for exact transcendental coordinates. The required error is additive and logarithmic, much smaller than a fixed relative error in the leading-order energy.

Formulation and concept references: [S1].

Short English statement

Can a polynomial-time real-number algorithm place points on the sphere with logarithmic energy within a constant times log N of optimal?

Research attempt

Scope and source audit (27 September 2026).

This attempt keeps the unordered-pair convention in the statement. A paper summing over $i\ne j$ uses twice this energy, including twice every additive error. The requested algorithm is uniform in $N$, and its error must be compared with the global minimum, not with the best configuration found in a numerical run. Polynomial time for a local optimization step does not bound the number of steps or certify the global energy gap.

The original hosted PDF in [S1] was not retrievable during this audit. The primary paper [E1], Problem 1.1, explicitly restates the logarithmic additive target and develops lower bounds; [E2] computes expected energies for a family of random constructions. Neither inspected result supplies the requested algorithm. The discussion below does not treat a random expectation or an asymptotic leading coefficient as that guarantee. It also does not impose exact transcendental output in a bit model that is absent from the catalogue statement.

The approach is deliberately elementary: derive exact small cases and a global separation estimate, then discretize the continuous optimization. The discretization reaches a constant additive error using rational coordinates of moderate description length. Its search has exponentially many candidates. This isolates a selection problem rather than an obstruction from coordinate precision.

Existence of a minimizer and the product formulation.

Put $m=\binom N2$. Every pair distance is at most two, so every summand is at least $-\log2$. There is at least one distinct configuration of finite energy. Along a sequence in which any two points collide, the corresponding summand tends to $+\infty$, while the other summands have the fixed lower bound just noted. Thus a bounded-energy minimizing sequence cannot converge to a collision. Compactness of $(S^2)^N$ and continuity away from collisions prove that $E_N^{\min}$ is attained.

Equivalently, maximize \begin{equation}\label{wsref-0-61-34-37-34-3a-70-72-6f-64-75-63-74} D(X)=\prod_{i<j}\|x_i-x_j\|^2,\qquad E(X)=-\tfrac12\log D(X). \end{equation} For rational sphere points, $D(X)$ is a positive rational number. Comparing two such energies therefore requires only exact rational multiplication and comparison, not exact evaluation of logarithms. The requested gap is equivalent to \[ D(X)\ge D(X_{\min})N^{-2c}. \] This is a multiplicative approximation to the entire distance product; approximating each individual distance to a fixed relative tolerance would accumulate an error over $m$ pairs.

Lemma 474.1: a centroid bound and three exact optima.

For every $N$-point configuration, \begin{equation}\label{wsref-0-61-34-37-34-3a-6a-65-6e-73-65-6e} E(X)\ge-\frac m2\log\frac{2N}{N-1}. \end{equation} Equality holds precisely when the centroid is zero and all pair distances are equal. Consequently the bound is attained for $N=2,3,4$ by the antipodal pair, equilateral equatorial triangle, and regular tetrahedron.

Proof. Expanding scalar products gives \[ \sum_{i<j}\|x_i-x_j\|^2 =N\sum_i\|x_i\|^2-\left\|\sum_i x_i\right\|^2 =N^2-\left\|\sum_i x_i\right\|^2\le N^2. \] Concavity of the logarithm yields \[ \frac1m\sum_{i<j}\log\|x_i-x_j\|^2 \le\log\left(\frac1m\sum_{i<j}\|x_i-x_j\|^2\right) \le\log\frac{2N}{N-1}. \] Strict concavity gives the stated equality conditions. If the points form an equal-distance, zero-centroid configuration, their Gram matrix has diagonal one and off-diagonal $-1/(N-1)$. Its rank is $N-1$; because the vectors lie in $\mathbb R^3$, this requires $N\le4$. The three listed configurations have exactly that Gram matrix. $\square$

In particular \[ E_2^{\min}=-\log2,\qquad E_3^{\min}=-\tfrac32\log3, \qquad E_4^{\min}=-3\log(8/3). \] The rank restriction explains why simply imposing the equality conditions does not solve larger instances. Zero centroid alone is far weaker than equality: many very poorly distributed configurations have zero centroid.

An exact average potential, with its algorithmic limitation.

Let $\sigma$ be normalized surface area measure. Rotational invariance makes $I=\int_{S^2}\log(1/\|x-y\|)\,d\sigma(x)$ independent of $y$. Taking $y$ to be the north pole, the height $u=x\cdot y$ is uniform on $[-1,1]$. Direct integration, including the integrable endpoint singularity, gives \begin{equation}\label{wsref-0-61-34-37-34-3a-61-76-65-72-61-67-65} I=-\frac14\int_{-1}^1\log(2-2u)\,du =\frac12-\log2<0. \end{equation} For independent uniform points, collisions have probability zero and linearity of expectation gives $\mathbb E E=mI$. Therefore \begin{equation}\label{wsref-0-61-34-37-34-3a-75-70-70-65-72} E_N^{\min}\le mI. \end{equation}

There is also an existence-only greedy version. Given $n-1$ distinct points, the potential $V(x)=\sum_{j<n}\log(1/\|x-x_j\|)$ has integral $(n-1)I$, so some noncolliding point satisfies $V(x)\le(n-1)I$. Choosing such a point at each stage yields energy at most $mI$. This observation neither tells us how to find that point efficiently in the allowed real-number model nor narrows the error to $O(\log N)$. The proven upper and lower bounds themselves leave an order-$N^2$ interval.

A useful failed construction is the regular equatorial $N$-gon. If $z_1,\ldots,z_N$ are the roots of $z^N-1$, differentiation at each root gives $\prod_{j\ne i}|z_i-z_j|=N$. Multiplying over $i$ shows $\prod_{i<j}|z_i-z_j|^2=N^N$, hence \[ E(\text{regular equatorial }N\text{-gon})=-\tfrac N2\log N. \] Combining with (a474:upper), its gap is at least $-\tfrac N2\log N-mI$, which grows quadratically. Exact symmetry and an exact distance product do not imply near-optimality on the sphere.

Lemma 474.2: an elementary separation bound at a minimizer.

Every minimizing configuration has pairwise separation at least \begin{equation}\label{wsref-0-61-34-37-34-3a-73-65-70-61-72-61-74-69-6f-6e} \delta_N=2\exp(-(N-1)/2). \end{equation} This bound is intentionally weak, but sufficient for the discretization.

Proof. Fix point $x_i$ of a minimizer. Replacing just this point cannot lower the total energy, so its potential is at most the spherical average of that same potential: \[ \sum_{j\ne i}\log(1/\|x_i-x_j\|)\le(N-1)I. \] Equivalently $\prod_{j\ne i}\|x_i-x_j\|\ge e^{-(N-1)I}$. All but any selected factor are at most two. Thus, for every $j\ne i$, \[ \|x_i-x_j\|\ge 2^{-(N-2)}e^{-(N-1)I} =2e^{-(N-1)/2}. \] The averaging argument is legitimate despite the finitely many infinite values at the other points: the potential is integrable and its global minimum lies away from those singularities.$\square$

No claim is made that this is the sharp scale. In particular, using this exponentially small bound in a covering construction will produce a very large grid. A polynomial separation estimate would improve the grid size, but would still leave the selection of $N$ points from that grid.

Lemma 474.3: perturbation cost at a separated configuration.

Suppose $X=(x_i)$ has separation at least $\delta>0$, and $Y=(y_i)$ satisfies $\|x_i-y_i\|\le\varepsilon$ for every $i$, with $2\varepsilon\le\delta/2$. Then the $y_i$ are distinct and \begin{equation}\label{wsref-0-61-34-37-34-3a-70-65-72-74-75-72-62} E(Y)-E(X)\le4m\varepsilon/\delta. \end{equation}

Proof. The reverse triangle inequality gives $\|y_i-y_j\|\ge\|x_i-x_j\|-2\varepsilon>0$. The increase for that pair is at most $-\log(1-2\varepsilon/\|x_i-x_j\|)$. For $0\le u\le1/2$, integration of $1/(1-u)\le2$ gives $-\log(1-u)\le2u$. Sum over the $m$ pairs.$\square$

Taking $\varepsilon\le\delta_N/(4N^2)$ makes the increase less than $1/2$. Thus a sufficiently fine rational approximation of a minimizing configuration already meets a stronger energy tolerance than requested. The issue is obtaining such an approximation without knowing a minimizer.

A finite rational search that attains a constant gap.

Here are explicit charts, avoiding an unmentioned transcendental-coordinate oracle. The rational parametrization \[ F(u,v)=\frac{(2u,2v,1-u^2-v^2)}{1+u^2+v^2} \] maps $\mathbb R^2$ into $S^2$. On $[-1,1]^2$ its differential has operator norm at most two. Use this chart with either pole and permute the three coordinate axes. These six charts cover the sphere: choose a coordinate of maximal absolute value and use the corresponding hemisphere; the inverse stereographic coordinates then have absolute values at most one.

Let $K=4N+10$ and take the grid $u,v\in2^{-K}\mathbb Z\cap[-1,1]$ in each chart. Rounding chart coordinates gives a covering radius at most $2\sqrt2\,2^{-K}$. For $N\ge2$ this is less than $\delta_N/(4N^2)$. One can check the inequality without an exponential oracle by using $e<4$ in (a474:separation); the deliberately generous choice of $K$ leaves ample slack. Every grid point has rational coordinates with $O(N)$ bits per numerator and denominator.

Enumerate all distinct $N$-subsets of the resulting finite point set and select one maximizing (a474:product). The grid contains a rounding of some minimizing configuration. Lemma 474.3 shows that its energy is less than $E_N^{\min}+1/2$, so the selected subset has at least this quality. In particular this proves existence of rational, moderate-length descriptions achieving the desired energy scale.

There are $2^{O(N)}$ grid points and at most $2^{O(N^2)}$ ordered candidate tuples. Exact products contain $O(N^3)$ bits, up to fixed constants, since there are $O(N^2)$ factors with $O(N)$-bit coordinates. Exhaustive search therefore gives an exponential-time construction with polynomial size output; it is not the requested polynomial-time real-number algorithm. The same conclusion holds if arithmetic operations themselves have unit cost: the number of subsets visited is still exponential.

Why the natural shortcuts do not remove the search.

The energy is not a convex function of the sphere-point coordinates on their nonconvex domain. A stationary configuration or a descent direction does not compare its value with the global minimum. Nor does the compactness argument give an efficient covering of the set of minimizers. The rational grid construction supplies a verifiable objective value, but its proof of quality uses the exhaustive maximum over all subsets.

One might instead compare a construction with an asymptotic expansion of $E_N^{\min}$. An error term $O(N)$, or even an unspecified $o(N)$ term, does not imply $O(\log N)$: for example $N^{1/2}=o(N)$ exceeds every constant multiple of $\log N$. Likewise the word "quasioptimal" in a different source may mean a bounded ratio or a linear additive error. The exact inequality in this catalogue is the criterion used throughout.

A sufficient missing lemma would select, in polynomial time, an $N$-subset of an explicitly generated sphere grid whose distance product is within a polynomial factor of the best continuous product. A grid with a polynomial number of points would not alone prove that lemma: optimizing over its $N$-subsets can still involve exponentially many choices. Neither such a selection theorem nor a rigorous global convergence bound is established.

Finite diagnostics and outcome.

The companion checks use exact rational sphere points from the charts, verify their norms and the distance-product comparison, and compare enumerated small-grid optima with the exact two-, three-, and four-point bounds. The tetrahedral Gram calculation is checked independently from its coordinate realization. The finite tests do not estimate an unknown large-$N$ optimum or certify a numerical local optimizer.

Outcome: UNRESOLVED. The attempt proves exact small subcases, a global separation estimate, a perturbation bound, and an explicit constant-gap rational search with exponential running time. It pinpoints efficient global selection as the first remaining algorithmic gap. Nothing here supplies the polynomial-time logarithmic-gap algorithm.

Sources

• S1 Stephen Smale, Mathematical Problems for the Next Century, Problem 7 $1998$. https://www.cityu.edu.hk/ma/doc/people/smales/pap104.pdf. Formulation source.
• E1 Carlos Beltrán and Fátima Lizarte, A Lower Bound for the Logarithmic Energy on $S^2$ and for the Green Energy on $S^n$, Constructive Approximation, published online 2023, Problem 1.1 and introduction. https://link.springer.com/article/10.1007/s00365-023-09642-4. Primary formulation and lower-bound comparison inspected 27 September 2026; the unavailable original link [S1] is preserved.
• E2 On the logarithmic energy of solutions to the polynomial eigenvalue problem, arXiv:2408.11148 $2024$. https://arxiv.org/abs/2408.11148. Primary abstract inspected 27 September 2026; used only for the scope of random expected-energy constructions, not a worst-case algorithm.