Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

# division of the simplex

49 views

Jul 9, 2002, 5:41:30 PM7/9/02
to
Let S be the n-dimensional simplex, i.e. the set of (n+1)-tuples of
nonnegative real numbers (x_0,...,x_n) such that x_0+...+x_n=1. Let F
be the map sending an (n+1)-tuple (x_0,...,x_n) of nonnegative real
numbers, not all zero, to F(x_0,...,x_n) = (x_0/x,...,x_n/x), where
x=x_0+...+x_n, so that F(x_0,...,x_n) is in S.

If (k_0,...,k_n) is an (n+1)-tuple of natural numbers, let
S(k_0,...,k_n) be the image by F of the cube (k_0+I)*...*(k_n+I)
(where I is the segment [0,1]) consisting of (n+1)-tuples of real
numbers of the form (k_0+t_0,...,k_n+t_n) where each t_i is between 0
and 1 (we possibly need to remove the vertex (0,...,0) from the cube
for the map F to be defined on it, namely when k_0=...=k_n=0; this is
unimportant). This defines a polytope S(k_0,...,k_n) in S.

Now fix k (a natural number) and consider all polytopes S(k_0,...,k_n)
with k_0+...+k_n=k. (There are binomial(k+n,n) such.) It is not too
hard to show that the S(k_0,...,k_n) form a division of S (in the
sense that their union is all of S and the intersection of two of them
is, at most, a face of dimension <n).

My question is: is it true that all S(k_0,...,k_n) (still with
k_0+...+k_n=k a constant) are of the same measure? Here, the measure
on S is the usual one: it is the unique probability measure on S which
is proportional to Lebesgue measure on the hyperplane of equation
x_0+...+x_n=1.

(Background: this division of the simplex corresponds to a classical
electoral system. Namely, if there are k seats in an assembly, n+1
political parties numbered 0 through n and each one receaves a share
x_i of the votes, with x_0+...+x_n=1, we want to distribute the seats
proportionally to the number of votes, as far as that can be arranged.
Then assign to the party i k_i seats in the assembly where k_0,...,k_n
are the (essentially unique) integers such that k_0+...+k_n=k and
(x_0,...,x_n) belongs to S(k_0,...,k_n).)

--
(david....@ens.fr,

### Robert Marmier

Jul 12, 2002, 6:58:45 PM7/12/02
to
Yes, all the projections have the same volume. Here is a proof (written
for n=2, I think it will be easier to read -for another n, replace
obviously cubes by hypercubes, triangles by simplexes and so on). s will
denote the sum of the coordinates of a point (what you called x).

First note that there is no real reason in the question (except the
background) to restrict oneself to cubes with integer vertices. Admit
vertices for your cube anywhere in (R+)^3 ; and note A(a,b,c) the area
of the projection of the cube of summits (a + epsilon_0, b + epsilon_1,
c + epsilon_2) (epsilon_i being 0 or 1).

A(a,b,c) can be computed in the following way : first note that F(cube)
is divided as the union of the three F(face) where face is a face of the
cube adjacent to (a,b,c). Now watch one of these faces, say the
horizontal one (fix the third variable x_2 to c) ; this can be in turn
be divided as the union of 2! triangles, one for each ordering of the
two variables x_0 and x_1 : the first triangle has summits (a,b,c)
(a+1,b,c) and (a+1,b+1,c) while the second triangle has summits (a,b,c)
(a,b+1,c) and (a+1,b+1,c). Watch the first of these triangles ; write
down the formulas for the image of each summit under F, note that the
area of the resulting triangle is proportional to the determinant of
these three points (by a factor \sqrt{3}\over 3!, with no guarantee),
write down this determinant, you'll see that this area is a rational
function of (a,b,c) whose denominator is s(s+1)(s+2). Now sum up all of
these on the (2+1)2! triangles ; now we know that A(a,b,c) is a rational
fraction with denominator s(s+1)(s+2).

Since we know by advance that the first factor is superfluous, we can
wonder whether we can chase it. You can do that thinking that the
projection of the cube is also the projection of the dark side of the
cube. So you can also prove that A(a,b,c) can also be written with
denominator (s+1)(s+2)(s+3), hence can be written with denominator
(s+1)(s+2) (but disappointingly this trick is not necessary to finish
the proof).

Now move the cube to infinity along the half-line leaving from zero
through its base vertex. Intuitively, the further you go, the more
linear F becomes ; or seen otherwise, this motion has the same result
than leaving the cube motionless while the pole of the perspective leave
to infinity on the other side, that is the perspective tends to a linear
projection (leaving haze around what happens to the image hyperplane) ;
alternately, you can also projectify by allowing the side of the cube to
move, and leave the base vertex of the cube and the pole motionless
while the side tends to zero. This informal argument is easy to shape ;
just compute s[F(a + epsilon_0, b + epsilon_1, c + epsilon_2) -
F(a,b,c)] when (a,b,c) tends to infinity along a half-line : you'll
check the limit position of this point exists (and is the linear
projection of (epsilon_0,epsilon_1,epsilon_2) on x_0+x_1+x_2 = 0 along
the direction of (a,b,c)). Henceforth s^2A(a,b,c) has a limit when
(a,b,c) tends to infinity along a fixed direction. Due to what we