Is every finite descending sequence in [0,1] in convex hull of certain points?

257 Views Asked by At

Fix a natural number $n\in\mathbb{N}$ and a real number $s\in[0,n]$.

Consider the set $A_s\subset [0,1]^n$ of those sequences $(x_1 \geq\dots\geq x_n)$ in $[0,1]$ with $\sum_{i=1}^n x_i=s$.

Given positive integers $p,q$ there is at most one point $x_s(p,q)\in A_s$ of form $(1\geq\cdots\geq 1\geq a\geq \cdots\geq a\geq 0\geq \cdots \geq 0)$ with $p$ many ones and $q$ many $a$'s ($a$ has to be equal to $\frac{s-p}{q}$)

Now the question is: For which $s$ is it true that $A_s$ is the convex hull of the points $x_s(p,q)$, where $p,q$ range over all positive integers such that $x_s(p,q)$ is well defined.

Examples:

  1. If $n=1$, then $A_s=\{(s)\}$ consists of a single point (if $s\in[0,1]$ and is empty otherwise), this point is $x_s(0,0)$ (if $s=1$, then x_s(0,0)=x_s(1,0) but this does not change anything).
  2. If $n=2$, then $A_s=\{(x,s-x)\mid \frac s2\leq x\leq \min(s,1)\}$. On the other hand we have the points $x_s(0,0)=(\frac s2,\frac s2)$ (as long as $s\in[0,2]$) and $x_s(1,0)=(1,s-1)$ (as long as $s\in[1,2]$) and $x_s(0,1)=(s,0)$ (as long as $s\in[0,1]$). So the claim is true for all $s\in[0,2]$
1

There are 1 best solutions below

2
On BEST ANSWER

There is a result of L. Dubins ("On extreme points of convex sets", see also) to the effect that if $K$ is a polytope and $L$ is a co-dimension $m$ affine space, then each extreme point of $K\cap L$ is a convex combination of at most $m+1$ extreme points of $K$. (The actual result is for general convex compact sets, but polytopes is all that's needed here.)

In the case at hand $K$ is the polytope whose vertices are all of the form $x_{k,l}=(1,1,\dots,0,0,\dots)$, with the first $k$ coordinates equal to $1$ and the last $l$ coordinates equal to $0$, where $k,l\ge0$ and $k+l=n$. The affine space $L$ is determined by the single condition that the sum of the coordinates is $s$; it has codimension $m=1$. Each extreme point of $A_s=K\cap L$ is thus a convex combination of $m+1=2$ extreme points of $K$. It is easy to check that the OP's sought extreme points are indeed convex combinations of pairs of $x_{k,l}$.