wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Product of distances
        
(Message started by: Eigenray on Jun 4^th, 2005, 12:28pm)

Title: Product of distances
Post by Eigenray on Jun 4^th, 2005, 12:28pm

Given n points on the unit circle, let M denote the maximum, over all z on the unit circle, of the product of the distances from z to the other n points, i.e.,
M = max_|z|=1 [prod] |z-z_i|.
What is the best lower bound for M?
When is it obtained?

Title: Re: Product of distances
Post by Grimbal on Jun 4^th, 2005, 1:17pm

Intuitively, I would say the points must be equally spaced on the circle.

Title: Re: Product of distances
Post by Deedlit on Jun 4^th, 2005, 11:22pm

And it looks like [hide]the answer is 2[/hide], although I haven't come up with an argument yet.

Another nifty fact is that the product of the distances from one of the vertices to the other n-1 is n. (when they're equally spaced)

Title: Re: Product of distances
Post by Aryabhatta on Jun 5^th, 2005, 1:04pm

Deedlit is right: the minimum possible value of the maximum is [hide]2[/hide]

Here is why:
[hideb]
Let the n points be z_i i = 1 to n.

We can rotate the circle so that (-1)ⁿ[prod]z_i = 1.

Now consider
P(z) = (z-z₁)(z-z₂)...(z-z_n)

We are interested in |P(z)| for various z on the unit circle.

Let w_i be the n^th roots of unity.

Consider [sum] P(w_i)

Since [sum]_i w_i^k = 0, 1 [le] k [le] n-1, we have that [sum] P(w_i) = 2n.

Thus [sum] |P(w_i)| [ge] |[sum] P(w_i)| = 2n.

Hence, for some i, |P(w_i)| [ge] 2.

It can be shown that for the n points which are equally spaced, the maximum value of |P(z)| is 2.

[/hideb]

Title: Re: Product of distances
Post by Deedlit on Jun 5^th, 2005, 8:56pm

Sweet! As for proving the bound strict,

[hideb]
We can use the fact that sin(x) sin(c - x), with 0 <= x <= c, is maximized when x = c / 2. Assuming that the z_i are equally spaced, choose z so that it bisects the arc between z₁ and z₂. The length |z - z_i| = 2 sin (theta/2), where theta is the difference between the arguments of z and z_i. So, we divide the z_i into pairs for which the angles are the same. (when n is odd, there is one z_i that is diametrically opposed to z.) For each such pair z_m and z_n, the value of |z - z_m| |z - z_n| is maximized by the current value of z, by the lemma from the beginning. And, of course, |z - z_i| for the diametrically opposite z_i as at its maximum value. So the product of all the |z - z_i| is certainly maximized.

All that's left is to show that the above product is 2. However, I haven't been able to come up with a slick proof of that. It does follow from the fact I mentioned earlier (that the product of the distances from one of the z_i to the others is n.)
[/hideb]

Title: Re: Product of distances
Post by Aryabhatta on Jun 6^th, 2005, 1:20am

There is a simpler proof in case of the equally spaced version:

[hideb]

The given points are w_i, the n^th roots of unity.

P(z) = Prod (z-w_i) = zⁿ - 1. (as they are the roots of unity)

|P(z)| = |zⁿ - 1| [le] |zⁿ| + 1 = 2.

Any root of zⁿ + 1 = 0 will suffice to achieve the maximum of 2.

[/hideb]

Title: Re: Product of distances
Post by Deedlit on Jun 6^th, 2005, 9:51pm

Yeah, that's a little slicker, although the idea of maximizing pairs of distances is pretty immediate conceptually - it just takes a little longer to write down.

And now I see the same method works for the other problem:

[hideb]
The product of the distances to all nth roots of unity except 1 is

P(z) = (zⁿ - 1) / (z - 1) = z^n-1 + z^n-2 + ... + z + 1.

and P(1) = 1 + 1 + ... + 1 = n.

[/hideb]

Title: Re: Product of distances
Post by Eigenray on Jun 11^th, 2005, 10:46am

Nice job. It just remains to be shown that if M=2, then the points are equally spaced.

Title: Re: Product of distances
Post by Aryabhatta on Jun 12^th, 2005, 1:27pm

Ahh.. there seemed to be something missing..

Here is a demonstration that if M=2, then the points are equally spaced:
[hideb]

Assume points are z₁,z₂,...,z_n such that their product is (-1)ⁿ.

Consider P(z) = (z-z₁)(z-z₂)...(z-z_n) = zⁿ + 1 + Q(z)

We would like to show that Q(z) = 0 for all z.
As before consider the values at w₁, w₂,...,w_n the n^th roots of unity.

Since M = 2,
We have that |P(w_i)| = 2 exactly.
(because [sum]|P(w_i)| = 2n and M=2.)

i.e |2 + Q(w_i)| = 2 for each i. -- (1)

We also have that [sum] Q(w_i) = 0.

(1) says that each Q(w_i) lies on the circle of radius 2 centred at (-2,0). Sum of any points on that circle can never be zero, unless they all are zero. (as all points have non-positive x co-ordinates.)

Thus we must have that Q(w_i) = 0 for each i. Since Q(z) is a polynomial of degree n-1 we have that it is identically zero.

[/hideb]

Title: Re: Product of distances
Post by Deedlit on Jun 14^th, 2005, 1:12am

Well done.

[hideb]
In fact, since [sum] P(w_i) = 2n, we have immediately that P(w_i) = 2 for all i if M = 2.
[/hideb]

Title: Re: Product of distances
Post by Aryabhatta on Jun 14^th, 2005, 10:17am

on 06/14/05 at 01:12:33, Deedlit wrote:

Well done.

[hideb]
In fact, since [sum] P(w_i) = 2n, we have immediately that P(w_i) = 2 for all i if M = 2.
[/hideb]

Aah.. if P(w_j) = x_j + iy_j then [sum] x_j = 2n. We must also have that |x_j| [le] 2. It follows that each must be 2. From which it follows that y_j = 0.