CS Paper Radar

Optimal Configurations for Mordell's Problem

Xiang Ji, Tiancheng Xu, Wensheng Yu

cs.SC math.COmath.OC ·submitted 2026-11-02 13:09 UTC · v1
theoryunusual

Abstract

Mordell's problem asks for the largest product of squared pairwise distances among $n$ points in the complex plane with a prescribed sum of squared distances from the origin. When this sum equals $n$, the maximum for $2\le n\le5$ is known to be $n^n$, attained precisely by the $n$th roots of unity up to rotation and relabeling. For $n\ge6$, Chalk showed that a regular polygon together with its center gives a larger product than the regular $n$-gon. We prove that for $6\le n\le9$ the maximum is $(n-1)^{n-1}r_n^{n(n-1)}$, where $r_n=\sqrt{n/(n-1)}$. Up to the same symmetries, the unique maximizer consists of the origin and the vertices of a regular $(n-1)$-gon of radius $r_n$. For six points, algebraic elimination reduces the proof to an exact comparison of stationary values. For seven points, we compare all twelve classes in a published classification of equilibria. For eight and nine points, rigorous interval arithmetic establishes an inequality for every admissible pair. Summing over pairs gives the sharp global bound, and the equality conditions determine the configuration. An explicit ten-point comparison and a known instability result together exclude Chalk's configuration for every $n\ge10$. For each $n$ from two through eight, Mordell's problem and the minimum-diameter problem studied by Bateman and Erdős have a common optimal configuration.

Closest papers

Nearest neighbours by meaning across the whole index.

Non-simple Arrangements of Lines and Pseudolines with Many Triangles

cs.CG math.CO ·2026-11-02 ·Roman Parpalak, Denis Utkin
code/data similarity 0.57
Abstract · 72 pages, 19 figures, 8 tables. Code, enumeration outputs and certificates: https://github.com/parpalak/nonsimple-arrangements

We study affine arrangements of an even number $n$ of lines and pseudolines with many triangles. For simple ones, Blanc's bound limits the number of triangular faces to $\lfloor n(n-5/2)/3\rfloor$. Adapting the Bartholdi-Blanc-Loisel doubling to the even case, we construct an infinite series of arrangements of $n=6\cdot2^t+2$ ($8,14,26,50,\ldots$) straight lines with two triple points and $(n(n-5/2)+1)/3$ triangles, one more than the simple bound allows. We obtain exhaustive enumerations of triangle-maximal pseudoline arrangements, simple or not, for even $n\le12$. For $n=6,8,10,12,14$ the maximum number of triangles, for both lines and pseudolines, is $7,15,25,38,54$; for $n=8,12,14$ every optimal arrangement has multiple points. All optimal arrangements for even $n\le12$ are realizable by straight lines, except two arrangements of 10 pseudolines, which are not stretchable. For the odd value $n=11$, no arrangement with $33$ triangles exists even with multiple points. We also obtain even arrangements by adding a line to odd ones. For $n\equiv2\pmod 6$ this again gives one triangle more than the simple bound, in pseudolines up to $n=44$ and in straight lines for $n=20$ and $n=32$. Doubling these pseudoline arrangements gives members of the series $18\cdot2^t+2$ and $30\cdot2^t+2$ with the same excess, up to $n=146$ and $n=242$, respectively; those with $n=38$ and $n=74$ are realizable by straight lines. These results lead us to conjecture that an arrangement of an even number $n$ of pseudolines has at most $\lfloor n(n-2)/3\rfloor-\lfloor n/6\rfloor$ triangles.

0.34

An upper bound on the number of edges of a Gomory corner polyhedron

cs.CG math.COcs.DMmath.OC ·2026-11-12 ·A. Yu. Chirkov, S. I. Veselov, D. V. Gribanov, D. S. Malyshev, N. Yu. Zolotykh
theory similarity 0.56
Abstract

We establish the first nontrivial upper bound on the number of edges of a Gomory corner polyhedron, resolving a long-standing open question. For an $n$-dimensional corner polyhedron associated with an integer lattice of determinant $δ$, the number of edges is at most $$ O\left(n6^n \cdot \bigl(1+\log_2(2δ)\bigr)^{2n-3}\right). $$ This improves the standard bound obtained by counting pairs of vertices, reducing the logarithmic exponent from $(2n-2)$ to $(2n-3)$.

0.28

Finding the Farthest in High Dimensions: Dynamic Diameter and Farthest-Neighbor Search

cs.DS ·2026-11-12 ·Mohammad Hajiaghayi, Morteza Monemizadeh
similarity 0.56
Abstract

We give algorithms for maintaining diameter in the dynamic model, and for answering farthest-neighbor queries on a fixed point set, in high-dimensional Euclidean space. For every fixed $1<c<\sqrt2$, update horizon $t$, and error probability $δ$, we maintain an actual factor-$c$ diameter pair with worst-case update time $n^{2/c^2-1}\text{poly}_c(d,\log(2nt/δ))$ and space $n^{2/c^2}\text{poly}_c(d,\log(2nt/δ))$. Here $n$ bounds the number of active point identities. The update exponent improves Indyk's SODA~2003 bound from $1/c^2$ to $2/c^2-1$, while the space exponent improves from $1+1/c^2$ to $2/c^2$. At $c=\sqrt{3/2}$, the update exponent decreases from $2/3$ to $1/3$. A separate construction achieves approximation exactly $\sqrt2$ with update time polynomial in $d$ and $\log(2nt/δ)$. With probability at least $1-δ$, every maintained answer during the first $t$ updates is correct, even when updates depend on all previous answers and random choices. A second construction improves the update exponent when the space exponent is close to one. On rational inputs, it has an always-correct variant with expected amortized update bounds over every fixed finite prefix of an adaptive execution, without an advance update horizon. The dynamic structures store a current answer, so reporting its two point identifiers takes constant time. The geometric method also gives static diameter algorithms and a farthest-neighbor structure for a fixed set that answers arbitrary adaptive queries. At approximation $\sqrt2-\varepsilon$, the diameter time is $n^{1+O(\varepsilon)}$, and the query time is $n^{O(\varepsilon)+o(1)}$ with near-linear preprocessing and space, up to polynomial input-parameter factors.

0.25

First Order Geometry of Equilateral Small Polygons

cs.CG math.MG ·2026-11-17 ·José Ayala Hoffmann, Tomás Ayala Coppola
theory similarity 0.55
Abstract · 16 pages

We develop a first order calculus based on the geometry of realised diameter graphs for perimeter maximisation among convex equilateral small polygons. Polygon side equalities and active diameter constraints define a linearised feasible cone and an associated equality space. We prove that an equilateral small polygon is a strict local maximiser of perimeter modulo Euclidean motions if a multiplier balance holds with strictly positive active diameter multipliers and the active equality space consists only of infinitesimal Euclidean motions. The proof uses a local Euclidean slice and a geometric limiting argument and requires neither independence of the active constraint gradients nor second order information. As an application, we combine our criterion with validated interval arithmetic to establish strict local maximality for Bingane and Audet's polygons $A_{16}$, $A_{32}$, $A_{64}$ and for reconstructions of their polygons $Z_{32}$ and $Z_{64}$. For each $n\in\{32,64\}$, the perimeter of $Z_n$ is strictly larger than that of $A_n$. Thus, strict local maximisers with different perimeters coexist in the space of convex equilateral small polygons with the same number of sides.

0.40

An Improved Upper Bound for the Turán Number of the Hexagon

cs.DM math.CO ·2026-09-09 ·Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
theory similarity 0.54
Abstract · 9 pages

For a graph $F$, the Turán number $\operatorname{ex}(n,F)$ is the maximum number of edges in an $n$-vertex graph containing no copy of $F$. Determining the Turán numbers of even cycles is a central problem in extremal graph theory and remains open in general. For $C_6$, the best previous upper bound was due to Füredi, Naor, and Verstraëte [Advances in Mathematics, 2006], who proved that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq λn^{4/3}+O(n)<0.6272 n^{4/3}, $$ where $λ$ is the real root of $ 16λ^3-4λ^2+λ-3=0$. We improve this bound by showing that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq αn^{4/3}+O(n)<0.6144 n^{4/3}, $$ where $α$ is the unique real root of $ 4 α^{3} (3/2)^{1-1/(2α)} =1$ in the interval $(1/2,2/3)$.

0.27

The Deepest Pairs of Points Are Not as Deep as Conjectured

cs.CG math.CO ·2026-11-14 ·Herbert Edelsbrunner, Alexey Garber, Morteza Saghafian, Emo Welzl
theory similarity 0.54
Abstract

Given any finite set of points in $\mathbb{R}^2$, Neumann-Lara and Urrutia \cite{NLUr88} proved in 1988 that there is always a pair such that every circle through the two points encloses a positive fraction of all points. While Edelsbrunner et al.\ \cite{EHSS89} showed that the fraction is at least $\sfrac{1}{2} - \sfrac{1}{\sqrt{12}} = 0.211\ldots$, Urrutia \cite{Urr02} conjectured that the constant $\sfrac{1}{4} = 0.25$ in the upper bound proved by Hayward, Rappaport and Wenger \cite{HRW89} is best possible. We disprove this conjecture by lowering the constant to $\sfrac{3}{14} = 0.214\ldots$. The new bound also disproves a related conjecture by Ramos and Viaña \cite{RaVi09} on finite sets in convex position in $\mathbb{R}^3$. Finally, we generalize the latter extremal question to finite sets in possibly non-convex position, for which we prove the first linear lower bound, with constant $\sfrac{(2-\sqrt{2})}{6} = 0.097\ldots$.

0.22

Minimum central circles: an effective characterization of the global asymptotic constant

cs.CG math.MG ·2026-09-12 ·Maurizio Falconi
theoryhot direction similarity 0.53
Abstract · 9 pages. Revised exposition and reproducibility documentation. Standalone proof supplements S1 and S2 are supplied as ancillary PDFs, with t…

Let $R^\ast(n)$ be the minimum radius of a central circle externally tangent to nonoverlapping circles of radii $1,\ldots,n$. We prove that $R^\ast(n)=C_\ast n^2+o(n^2)$ and give finite linear programs that enclose $C_\ast$ with prescribed error. An exact angular comparison reduces the problem to marked points on a line with separation at least the geometric mean of each pair of marks. Concatenation with bounded joining cost and reassignment to the prescribed normalized radii prove existence of the limit. Balanced finite-word programs give a bracket of width $(1/k+1/r)/π$, before directed arithmetic error, using $k$ types and words of length $r$. We also obtain explicit geometric bounds. For the upper bound, we recover finite and countable reflected-block constructions by actual permutations, retaining all pair constraints. A coupled terminal-subset argument gives an explicit lower bound strictly above $1/8$. Together these give $C_{\rm term}+η_{\rm width}\le C_\ast\le U_4$. The lower endpoint comes from the terminal-subset argument, and the upper endpoint from the four-block construction; neither is asserted sharp. The finite-word scheme establishes computability; efficient high-precision evaluation and the structure of global optimizers remain open.

0.29

Improved lower bounds for the kissing number in dimensions 49 to 61

cs.IT math.MGmath.CO ·2026-11-01 ·Dmitry Kamenetsky
theorycode/data similarity 0.53
Abstract · 9 pages, 4 tables, 1 figure. Code, data and exact certificates: https://github.com/dimkadimon/KissingNumbers

We give explicit kissing configurations in R^d for every d = 49, ..., 61. The lower bound is improved over the best previously published value in all thirteen dimensions, by margins from 232 to 159,220 points and by 506,461 points in total. The configurations are obtained from the antipodal block lift of Yang et al. applied to the 52,416,000-point minimal shell of the extremal even unimodular lattice P_48p, using a class of 7,193 minimal lines and, in each dimension, a kissing configuration of R^k (k <= 15) with the largest available number of antipodal pairs. Two ingredients are new. The published class of 7,077 lines is grown to 7,193 by local search in three stages, as a sequence of exchanges between candidate lines and class lines; and the point count, which equals 52,416,000 + 2S + 2t with t the number of antipodal pairs and S the size of the union of t isometric images of the class, is maximised as a maximum-coverage problem by greedy search with iterated local search over pools of 4,000 automorphic images, reaching 92-100% of the trivial bound 7,193t. All results are verified in exact integer arithmetic, and the certificates are distributed with the code. Code and data: https://github.com/dimkadimon/KissingNumbers

0.36