What is the shape of the $n$-gon which gives the maximum of a function?

Question

What is the shape of the $n$-gon $P_1P_2\cdots P_n$ which gives the maximum of $A_n$? The quantity $A_n$ is defined by $$ A_n = \frac{{\sum_{i\lt{j}\le{n}}{\lvert P_i P_j\rvert}^2}-{\sum_{i=1}^{n}{\lvert P_i P_{i+1}\rvert}^2}}{{\sum_{i=1}^{n}{\lvert P_i P_{i+1}\rvert}^2}} $$ Here, $\lvert P_i P_j \rvert$ is the Euclidean length of the line segment from $P_i$ to $P_j$. Note that $P_{n+1}=P_1$ and that the $n$-gon can be either convex or concave.

I'm interested in $A_n$ because I knew the fact that the maximum of $A_4$ is $1$ only if $P_1P_2P_3P_4$ is a parallelogram. I've already proved the case $n=4$, but I don't have any good idea for $n\ge5$.

Could you tell me how to solve this problem?

Answer 1

The optimal shape is the regular $n$-gon and all its affine images.

I am going to optimize the ratio $$ \frac{\sum_{i<j} |P_iP_j|^2}{\sum_i|P_iP_{i+1}|^2} $$ which differs from $A_n$ by 1. For the regular $n$-gon this ratio equals $$ \frac{n}{2(1-\cos\frac{2\pi}n)} . $$ Let us prove that this is the maximum.

The maximum ratio equals the maximum $\lambda\in\mathbb R$ such that the quadratic form $$ P\mapsto Q_\lambda(P) := \sum |P_iP_j|^2-\lambda\sum|P_iP_{i+1}|^2 $$ is nonnegative definite. Here $P$ denotes a polygon $P_1\dots P_n$ regarded as a point in $\mathbb R^{2n}$, so $Q_\lambda$ is a quadratic form in $\mathbb R^{2n}$. If $\lambda$ is the maximum and $P$ is an optimal polygon, then $Q_\lambda(P)=0$.

By the Pythagorean theorem, the coordinate expression for $Q_\lambda(P)$ splits into 2 independent summands: one for $x$-coordinates of the vertices and a similar one for $y$-coordinates. Since the form is nonnegative on all configurations of points, it is also nonnegative on the projections to $x$- and $y$-lines, and both summands must be zero separately.

Thus we have reduced the problem to the 1-dimensional case. It remains to solve the similar problem for the from $Q_\lambda$ in $\mathbb R^n$: $$ Q_\lambda(x) = \sum (x_i-x_j)^2-\lambda\sum(x_i-x_{i+1})^2 $$ where $x=(x_1,\dots,x_n)\in\mathbb R^n$. By the way, this reduction also shows that, whatever the optimal shape is, it comes with all its affine images.

Now assume that $\lambda$ is the maximum ratio and $x=(x_i)$ is an optimal configuration on the line. Differentiating $Q_\lambda(x)$ with respect to $x_i$ yields $$ 2n(x_i-a) -2\lambda(2x_i-x_{i-1}-x_{i+1}) $$ where $a$ is the arithmetic mean of $x_1,\dots,x_n$. The derivative must be zero, and by translation we may assume that $a=0$. This gives us a linear recurrence equation $$ x_{i+1}=-x_{i-1}+(\tfrac{n}{\lambda}-2)x_i . $$ The solution must be $n$-periodic, so it is a linear combination of two geometric progressions whose ratios are two conjugate $n$th roots of unity. In other words, we have $$ x_k = A \cos k\varphi + B\sin k\varphi $$ for some real constants $A$ and $B$, where $\varphi$ is a multiple of $\frac{2\pi}n$. (Notation $i$ is changed to $k$ to prevent confusion with complex numbers.) Then $$ \lambda = \frac{n}{2(1-\cos\varphi)} . $$ Checking the condition $Q_\lambda(x)=0$ leaves the only possibility $\varphi=\frac{2\pi}n$ (for larger multiples, the quantity is strictly positive).

Thus the maximum ratio equals $\frac{n}{2(1-\cos\frac{2\pi}n)}$ and the optimal polygons are those whose $x$- and $y$-coordinates are sequences of the above form. These are precisely affine images of a regular $n$-gon. The solution is the same in all dimensions, not only in the plane.