From: bruck@math.usc.edu (Ronald Bruck)
Newsgroups: sci.math,rec.puzzles
Subject: Re: Russian 44 puzzle
Date: 30 Sep 1998 22:41:11 -0700
In article <6utulj$ke4$1@news1.rmi.net>,
Kurt Foster wrote:
>In sci.math John Scholes wrote:
>. Given n odd and a set of integers a_1, a_2, ... , a_n, derive a new set
>. (a_1+a_2)/2, (a_2+a_3)/2, ... , (a_(n-1)+a_n)/2, (a_n+a_1)/2. However
>. many times we repeat this process for a particular starting set we
>. always get integers. Prove that all the numbers in the starting set are
>. equal. [SPOILER after about 30 lines]
[solution omitted]
I'm not going to give the "spoiler" lineage, because my solution is more than
30 lines away!! Of course, it's not the simplest, but:
This problem has interesting generalizations and interpretations. The
matrix which maps (a1,...,aN) to ((a1+a2)/2, (a2+a3)/2, ..., (aN+a1)/2) is
called a "circulant", as I recall. When you apply it to points ai in the
plane, after a finite number of iterations the path joining each coordinate
to the next forms a convex polygon.
It's amusing to program this and watch it. The original points may have
a VERY complicated and self-intersecting path a1 -> a2 -> a3 ... -> aN ->a1,
but as you iterate, it slowly unravels itself until it's convex.
Now the transformation reduces the area of the polygon in the plane, but
leaves the center of mass fixed. Thus unless you want to see the iterates
quickly shrink to a point, you'd better rescale the polygon (relative to its
COM) to have area 1 (although these are signed areas, and the apparent size may
grow as the curve unravels itself--and switches negative areas to positive
areas). You might expect that this normalized figure will converge, but it
doesn't; for example, start with a square: alternately you get the square
and the diamond (after normalizing the areas).
To understand the convergence another way, let S be the mapping which does
a "rotate left": (x1,...,xn) -> (x2,x3,...,xn,x1). The desired
transformation T is (I+S)/2 (which is to be iterated on the original vertices).
Now S is an isometry, so ||S|| = 1 in the Euclidean norm. I claim that
||T^(n+1) - T^n|| <= cst/sqrt{n}.
The sharpest way to see this is to expand both (I+S)^(n+1) and (I+S)^n by the
binomial theorem, obtaining
T^(n+1) - T^n = \sum_p (C(n+1,p)/2^(n+1) - C(n,p)/2^n) S^p
= \sum_p (C(n,p) + C(n,p-1) - 2C(n,p)) S^p/2^(n+1)
so that
||T^(n+1) - T^n|| <= \sum_p |C(n,p) - C(n,p-1)| / 2^(n+1).
But the binomial coefficients increase from p = 0 up to p = n/2; so the first
part of the sum telescopes to C(n,n/2)/2^(n+1). And the second part also
telescopes, also to C(n,n/2)/2^(n+1). (When n is odd, you can take the
floor or ceiling of n/2, it doesn't matter.)
Thus ||T^(n+1) - T^n|| <= C(n,n/2)/2^n. The estimate that this is (mumble)
I think it's < sqrt{2/(pi n)) is a standard exercise in approximating
factorials.
HOWEVER, the convergence of ||T^(n+1) - T^n|| to zero does NOT, by itself,
prove that {T^nx} converges. Fortunately, for this kind of T it DOES: for T
acts in a compact set (the closed unit ball of R^N), so that {T^nx}
has a convergent subsequence. If z is a subsequential limit, say
T^n(i)x --> z,
then we simultaneously have
T^(n(i)+1)x --> Tz (by applying T to both sides), and
T^n(i)x --> z (since T^(n+1)-T^n --> 0)
and thus z = Tz. But hold on: if Tz = z, then the sequence
{||T^nx - z||} must be decreasing: for since ||T|| <= 1 we have
||T^(n+1)x - z|| = ||T^(n+1)x - Tz|| <= ||T^nx - z||.
But if {||T^nx - z||} is decreasing and a subsequence goes to zero, then the
WHOLE sequence goes to zero; i.e. T^n x converges to a fixed-point of T.
A fixed point of T := (I+S)/2 is obviously a fixed-point of S, and the only
fixed-points of S are vectors of the form (x1,x2,...,xN) where x1 = x2 =
... = xN.
There's another way to see the convergence of T^(n+1) - T^n; it's to prove
the UNIFORM convergence of ((1+z)/2)^(n+1) - ((1+z)/2)^n to zero for complex
|z| <= 1. That's curious in itself, because ((1+z)/2)^n DOESN'T
converge uniformly (problem near z = 1). Anyway, when you apply the maximum
modulus principle to ((1+z)/2)^(n+1) - ((1+z)/2)^n you get another proof of
the uniform convergence (which is then extended to the operator T by the
usual functional-calculus considerations).
Indeed, in ANY Banach space, if S is a NONLINEAR mapping of a bounded
closed convex set C back into itself, and S has Lipschitz constant 1, it
follows (for T = (I+S)/2) that
diam C
||T^(n+1)x - T^nx|| <= -----------
sqrt(pi * n)
This result was proved by Jean-Bernard Baillon and myself around 1995,
and can be found in the volume 178 of Lecture Notes in Pure and Applied
Mathematics, Marcel Dekker. The proof for the nonlinear case is VERY
difficult.
In the finite-dimensional linear case, the one needed by this problem, the
convergence of T^nx is of course exponential. To see this, mod-out by the
kernel of I-T, and note that the induced map T0 satisfies T0^n --> 0. (There
IS an induced map because Ker(I-T) = Ker(I-T*).)
Thus all the eigenvalues of T0 are < 1 in absolute value, and hence its
spectral radius is < 1 (= max of abs values of eigenvalues, since this is a
finite-dimensional space). Thus in fact T0^n --> 0 like k^n, where k is the
absolute value of the largest eigenvalue; from which it follows that also
T^nx --> z linearly.
In the infinite-dimensional case, even the LINEAR infinite-dimensional case,
the cst/sqrt(n) is sharp. (Look at the right-hand shift in little-ell-
infinity.) And I suppose that if you join INFINITELY many points in the
plane together (whatever that means), it takes infinitely long for the
polygonal line to straighten itself out into a convex set.
--Ron Bruck
From: bruck@math.usc.edu (Ronald Bruck)
Newsgroups: sci.math,rec.puzzles
Subject: Re: Russian 44 puzzle
Date: 1 Oct 1998 00:15:32 -0700
In article <6uv4ln$pgp$1@math.usc.edu>,
Ronald Bruck wrote:
:
:There's another way to see the convergence of T^(n+1) - T^n; it's to prove
:the UNIFORM convergence of ((1+z)/2)^(n+1) - ((1+z)/2)^n to zero for complex
:|z| <= 1. That's curious in itself, because ((1+z)/2)^n DOESN'T
:converge uniformly (problem near z = 1). Anyway, when you apply the maximum
:modulus principle to ((1+z)/2)^(n+1) - ((1+z)/2)^n you get another proof of
:the uniform convergence (which is then extended to the operator T by the
:usual functional-calculus considerations).
When I posted this, I couldn't remember the details of the proof. It's
funny that ((1+z)/2)^n doesn't converge uniformly, but the difference does; is
there a general result which would yield this?
Anyway, simplify fn(z) = ((1+z)/2)^(n+1) - ((1+z)/2)^n to
fn(z) = ((1+z)/2)^n * (z-1)/2.
Since this is analytic on |z| <=1 (it's a polynomial!), the maximum value
on |z| <= 1 is taken on |z| = 1. Thus we can set z = exp(i t), and
|fn(z)| = |(1+exp(it))|^n |(exp(i t)-1)/2|
= cos^n (t/2) |sin(t/2)|.
To maximize this, we set the derivative equal to zero; this can't happen
where sin(t/2) = 0, so WLOG we can take our function to be
cos^n(t/2) sin(t/2). Setting the derivative equal to zero and solving, we
get (if I'm not mistaken)
cos^2 (t/2) = n sin^2 (t/2),
thus cos^2 (t/2) = n/(n+1), sin^2(t/2) = 1/(n+1);
hence the max is |fn|_max = [n/(n+1)]^(n/2) /sqrt(n+1).
And the [n/(n+1)]^(n/2) converges to exp(-1/2), thus our estimate is something
like
1
|f_n(z)| < ---------
sqrt(e*n)
This is a shade better than the sqrt(2/(pi*n)) that we get in the infinite-
dimensional case.
--Ron Bruck