Пусть $V_N(x)=\sum _{1⩽i⩽j⩽N}\log \frac{1}{\Vert x_i-x_j\Vert }$, где $x=(x_1,\dots ,x_N),x_i$ — различные точки на двумерной сфере $S^2\subset {\mathbb{R}}^3$, а $\Vert x_i-x_j\Vert$ — расстояние в ${\mathbb{R}}^3$. Обозначим $\underset{x}{min}{V}_N(x)$ через $V_N$.
Найти $(x_1,\dots ,x_N)$ такие, что
$$V_N(x)-V_N⩽c\log N,\text{ где }c-\text{ универсальная постоянная. }$$
«Найти» означает дать алгоритм, который по заданному $N$ выдает различные $x_1,\dots ,x_N$ на двумерной сфере, удовлетворяющие неравенству (2).

Чтобы быть более точным, необходимо рассматривать алгоритм для вещественных чисел в смысле, указанном в [5] (связанным с вычислением квадратного корня), с временем остановки алгоритма, полиномиальным по $N$.

Эта задача возникла в теории сложности и предложена мной совместно с Майком Шубом (см. [55]). Она возникла при отыскании хорошего начального многочлена для алгоритма гомотопии, реализующего основную теорему алгебры ${}^2$.

Точка $x=(x_1,\dots ,x_N)$ в которой $V_N(x)=V_N$ называется $N$-кратной эллиптической точкой Факетэ (см. [69]).
Сумма $V_N$, как функция $N$, удовлетворяет равенству
$$V_N=-\frac{1}{4}\log \left(\frac{4}{e}\right)N^2-\frac{1}{4}N\log N+O(N).$$

Естественно также рассмотреть функции
$$V_N(x,s)=\sum _{i<j}\frac{1}{{\Vert x_i-x_j\Vert }^s},V_N=\underset{x}{min}{V}_N(x,s),$$

где $x$ — такое же как прежде, а $0<s<2$. Исходные функции $V_N(x)$ и $V_N$ соответствуют естественным образом случаю $s=0$. В случае $s=1$ функция $V_N(x,1)$ — кулоновский потенциал, а $V_{N,1}$ соответствует состоянию равновесия $N$ электронов, лежащих на двумерной сфере.
${}^2$ Также данная задача имеет отношение к вихревой динамике. Так, $V_N(x)$ является гамильтонианом системы $N$ одинаковых точечных вихрей на сфере, а $V_N$ — значение энергии системы вихрей в положении равновесия. Подробности см. в книге Борисов А. В., Мамаев И.С. Пуассоновы структуры и алгебры Ли в гамильтоновой механике. Ижевск, 1999, Изд-во РХД, 466 с. — Прим. ред.

При разрешении указанной проблемы я попросил помощи у Эда Сафа. Впоследствии он и его коллеги написали по этой теме и ее ответвлениям ряд замечательных статей. Основную информацию и дальнейшие ссылки по этому вопросу можно найти в [29] и [50]. В работе [47] можно найти численное подтверждение ( $N=12000$ ), обосновывающее изложенные выше задачи.

На рассматриваемую проблему можно также взглянуть с точки зрения оптимизации функции
$$W_N(x)={(\exp V_N(x))}^{-1}=\prod _{i<j}\Vert x_i-x_j\Vert .$$

Однако, как было написано в [55], «…это не может быть таким легким, поскольку существуют седловые точки индекса $N$ (на большой окружности в $S^2$, равноотстоящие $N$ точек $x_1,\dots ,x_N$ ). Кроме того, различные симметрии, которыми обладает $W_N$, также запутывают картину».