Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.