Volumes of polytopes in hypercubes

[Roland Bacher]

Dear Seqfans,

The computation of the diagonal resistance in an n-dimensional
hypercube suggest the following geometric analogy:

The n-dimensional hypercube [0,1]^n of volume 1 can be sliced into 
n polytopes having integral vertices by considering 
the floor function (which forgets the fractional part of a real number) 
on the coordinate sum

(x_1,...x_n) |--> F(x_1,\dots,x_n)=floor(x_1+...+x_n)

By taking the adherence of F^{-1}(k)\cap [0,1]^n, one gets an integral 
polytope $P_k=\overline{F^{-1}(k)\cap[0,1]^n}  \subset [0,1]^n
with vertices all points {0,1}^n having coordinate sum
$k$ or $k+1$.

The "normalised" volumes n! Vol(P(0)),\dots,n! Vol(P(n-1))$ are of course
integers, sum up to $n!$ and  and Vol(P_k)=Vol(P_{n-1-k}).

It would be interesting to know them:
The first value $n! Vol(P(0))=n! Vol(P(n-1))$ is always one.
The triangle of these Volumes starts thus

 1:               1
 2:            1     1
 3:         1     4     1
 4:      1    11    11     1
 5:   1     x     y     x     1

where 2+2x+y=120 and y/120 is the volume of the convex hull
P(2)=P(2)_5 of the 20 integral points with coordinates in {0,1}^5 and 
coordinate sum either 2 or 3. (Remark that this polytope is symmetric
with respect to central symmetry in its barycenter 1/5(1,1,1,1,1),
this holds of course for all "middle" polytopes P(n)_{2n+1}
in odd dimension 2n+1).

Related interesting objects are:
  
The (n-1) dimensional volumes (which are of the form 
sqrt(n)/(n-1)! times integers) obtained by
intersecting [0,1]^n with the affine hyperplane
 
x_1+x_2+..+x_n=k for k=1,...,n-1   

(there is of course again an
obvious symmetry coming from the central symmetry of [0,1]^n).

More generally, the volume function k-> Vol_{(n-1)-dimensional}
([0,1]^n\cap {x_1+..+x_n=k}) is a continuous (for real k\in[0,n]), 
piecewise-polynomial function of degree
\leq n-1 in $k$ with changes of the polynomial definition at 
integral values. It would be nice to know these polynomials
(they have rational coefficients, after division or 
multiplication by sqrt(n)).

Does someone have any suggestion or idea on how to compute 
these quantities?

Roland Bacher


On Thu, Aug 17, 2006 at 01:01:07PM -0400, Henry Gould wrote:
> If I am not mistaken the number
> 
> sum(1/binomial(n,k),k=1..n-1)  is the diagonal resistance in ohms of an 
> n-dimensional cube, each edge of which is a 1 ohm resistor. I had to 
> figure this out using Kirchhoff's laws back in 1948.
> Can someone concur with this????
> 
> Henry Gould
> 
> Brendan McKay wrote:
> >The average is  sum(1/binomial(n,k),k=1..n-1).  I don't know
> >if this has a closed form or a name.
> >
> >Proof:  There are clearly k! (n-k)! permutations that have a 
> >break after the k-th value, so the probability of a break in
> >that place is 1/binomial(n,k).
> >
> >Asymptotically, the values k=1 and k=n-1 dominate, so the
> >expectation is 2/n + O(1/n^2).
> >
> >Brendan.
> >
> >
> >* Hugo Pfoertner <all at abouthugo.de> [060817 22:30]:
> >  
> >>SeqFans,
> >>
> >>today Hauke Reddmann started a new thread in the NG sci.math
> >>
> >>http://groups.google.com/group/sci.math/msg/b1c1164b936c6dca
> >>
> >><<
> >>For easyness, I use the data of my lest chess tournament :-)
> >>The finish in terms of the starting numbers was
> >>7 1 6 4 3 8 5 2|9|10|14 15 20 13 18 16 23 22 12 26 11 17 19 27 25 21
> >>24|28
> >>
> >>A | marks boundaries between consecutive number subsets that permute
> >>to themselves. Note that I (the 16) also permute to myself, but there
> >>are number crossing from both sides and so this is no boundary.
> >>
> >>Obvious question: How many boundaries occur in a random permutation?
> >>Clearly a tournament is about the opposite of random, as the swap
> >>numbers will be low.
> >>
> >>Example n=3
> >>
> >>1|2|3
> >>1|3 2
> >>2 1|3
> >>2 3 1
> >>3 1 2
> >>3 2 1
> >>-- 
> >>Hauke Reddmann <:-EX8    fc3a501 at uni-hamburg.de
> >>His-Ala-Sec-Lys-Glu Arg-Glu-Asp-Asp-Met-Ala-Asn-Asn
> >>    
> >>Is there anything in the OEIS that can answer his question? Any other
> >>ideas?
> >>
> >>Can you please CC answers also to Hauke; AFAIK he is not member of the
> >>Seqfan community.
> >>
> >>Hugo Pfoertner
> >>    
> >
> >  
>