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

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?

• What is the meaning of the notation $P_i P_j^2$? Do you mean $|P_i P_j|^2$, the square of the Euclidean length of the segment from $P_i$ to $P_j$? Or are you implying some type of multiplication between $P_i$ and $P_j$? – Joseph O'Rourke Jul 14 '13 at 14:58
• Voting to close pending clarification of what $P_iP_j^2$ means. – Steven Landsburg Jul 14 '13 at 15:32
• @Joseph O'Rourke: Thank you very much for pointing it out. In this problem, ${P_{i}P_{j}}^2$ means the square of the Euclidean length of the segment from $P_i$ to $P_j$. – mathlove Jul 14 '13 at 15:38
• I edited the question to make the notation more explicit and standard. – Ricardo Andrade Jul 14 '13 at 16:48
• @Ricardo Andrade: Thank you very much. – mathlove Jul 14 '13 at 17:24

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.

• Wow! Beautiful argument! – Joseph O'Rourke Jul 21 '13 at 0:10
• @Sergei Ivanov: Many thanks! $$x_{i+1}=-x_{i-1}-(\frac{n}{\lambda}-2)x_i$$ isn't it? – mathlove Jul 24 '13 at 14:57
• Yes the sign was wrong, but it does not matter for the argument. – Sergei Ivanov Jul 24 '13 at 23:13