# lower bound volume of a set

Let $\lambda$ be Lebesgue measure on [0,1]. For any $x_{1},\dots,x_{k}$ in $[0,1]$, define $$A(x_1,..,x_k):=\{(y_1,\dots,y_k)\in [0,1]^k: \text{there exist intervals }I_1,\dots,I_k \text{ in }[0,1]$$ $$\text{ such that } x_i,y_i\in I_i \text{ and } \lambda(\cup_iI_i)\leq\frac12\}$$

My question is: Is it true that there exists a constant $c\in(0,1)$ such that for any $x_{1},\dots,x_{k}$ in $[0,1]$ $$\lambda^{\otimes k}(A(x_1,..,x_k))\geq c^k$$

(Note that when $x_1,..,x_k$ can be covered by a interval of length not larger than 1/2, then $\lambda^{\otimes k}(A(x_1,..,x_k))\geq (\frac12)^k$. Thus the question is when $x_1,..,x_k$ is quite spread out on $[0,1]$, like for $x_i=\frac{i}{k+1}$ , is the volume still decay at most exponentially? For $x_i=\frac{i}{k+1},i=1,2,..,k$, we can construct interval $I_i=[x_i,x_i+\frac{1}{2k}]$, thus $\lambda^{\otimes k}(A(x_1,..,x_k))\geq (\frac{1}{2k})^k$. But of course we can construct other intervals and union all situations. )

• It appears that you can use the intervals $I_i=[x_i,x_i+\frac{1}{2k}]$ for any $x_i$'s, thus getting $\lambda^{\otimes k}(A(x_1,..,x_k))\geq (\frac{1}{2k})^k$. – Iosif Pinelis Sep 10 '17 at 21:47
• @losif Pinelis That's true. But I would like to know whether we can do better to prove the lower bound is actually $c^k$ for some $c\in [0,1]$ that doesn't depend on $k$ – Cuize Han Sep 10 '17 at 21:50
• @Nate Eldridge The previous description is confusing. Actually the set is a subset of $[0,1]^k$ (thanks for the editing) – Cuize Han Sep 10 '17 at 21:56
• Is this a question about the volume of an $\ell^1$ ball of radius $1/2$, intersected with $[0,1]^k$? If yes, then this goes to zero faster than $c^k$, namely, it is bounded above by the volume of the ball, which is equal to $2^k (1/2)^k / k! = 1/k!$. – Mateusz Kwaśnicki Sep 10 '17 at 22:05
• @Mateusz Thanks for the comment. Yes you are right. The set contains $l^1$ ball of radius 1/2 with center $(x_1,..,x_k)$. But there're more points to that in the set and that depends on how 'disperse' $x_1,..,x_k$ are on $[0,1]$. – Cuize Han Sep 10 '17 at 22:15

Such a constant $c$, not depending on $k$ and $x_1,\dots,x_k$, does not exist.

Indeed, suppose $k\ge2$. Let $x_i:=(i-1)h$ for $i=0,\dots,k+1$, where $h:=\frac1{k-1}$ -- so that $x_1=0$ and $x_k=1$.

Take any $(y_1,\dots,y_k)\in A(x_1,\dots,x_k)$. Then there exist intervals $I_1,\dots,I_k$ in $[0,1]$ such that $x_i,y_i\in I_i$ and $|\cup_iI_i|\leq\frac12$; here $|\cdot|$ denotes the Lebesgue measure in any dimensions. Without loss of generality (w.l.o.g.), we can replace here each $I_j$ by $[x_j\wedge y_j,x_j\vee y_j]$, so that w.l.o.g. each $I_j$ is closed. So, for some $m=1,\dots,k$, there exist disjoint nonempty closed subintervals $J_1,\dots,J_m$ of $[0,1]$ such that $I_1\cup\dots\cup I_k=J_1\cup\dots\cup J_m\supseteq\{x_1,\dots,x_k\}$. So, w.l.o.g. there are natural $n_1,\dots,n_m$ and real $a_1,b_1,\dots,a_m,b_m$ such that $a_1=0$, $b_m=1$, $n_1<\dots<n_m=k$, $J_i=[a_i,b_i]$ for all $i=1,\dots,m$, and $x_{n_i}\le b_i<a_{i+1}\le x_{n_i+1}$ for all $i=1,\dots,m-1$. So, $\{x_{n_{i-1}+1},\dots,x_{n_i}\}\subseteq J_i$ and hence $\{y_{n_{i-1}+1},\dots,y_{n_i}\}\subseteq J_i=[a_i,b_i]\subseteq[x_{n_{i-1}},x_{n_i+1}]$ for all $i=1,\dots,m$, with $n_0:=0$. For $i=1,\dots,m$, let $\ell_i:=n_i-n_{i-1}$, so that $\sum_1^m\ell_i=k$ and the length of the interval $[x_{n_{i-1}},x_{n_i+1}]$ is $(\ell_i+1)h\le2\ell_i h$. So, the Lebesgue measure of the set of all $(y_1,\dots,y_k)\in A(x_1,\dots,x_k)$ with given $n_1,\dots,n_m$ is no greater than $\prod_1^m(2\ell_i h)^{\ell_i}=(2h)^k\prod_1^m\ell_i^{\ell_i}$. On the other hand, the cardinality (say $N$) of the set of all $m$-tuples $(n_1,\dots,n_m)$ of natural numbers such that $m\in\{1,\dots,k\}$ and $n_1<\dots<n_m=k$ is no greater than $2^k$ (consider the indicators of the sets $\{n_1,\dots,n_m\}$).

The crucial observation is that $a_{i+1}-b_i\le x_{n_i+1}-x_{n_i}=h$ for all $i=1,\dots,m-1$ and hence $\frac12\le|[0,1]\setminus(J_1\cup\dots\cup J_m)|=\sum_1^{m-1}(a_{i+1}-b_i)\le(m-1)h$, so that $$m-1\ge\frac1{2h}=\frac{k-1}2.$$ Therefore and because $\sum_1^m\ell_i=k$, for $L:=\max_i\ell_i$ we have $k\ge L+(m-1)\ge L+\frac{k-1}2$, whence $L\le\frac{k+1}2\le\frac{3k}4$.

Thus, $$|A(x_1,\dots,x_k)|\le N(2h)^k\max\Big\{\prod_1^k\ell_i^{\ell_i}\colon \sum_1^k\ell_i=k,0\le\ell_i\le\tfrac{3k}4\ \forall i\Big\},$$ with $0^0:=1$. Since $\ln(u^u)=u\ln u$ is convex in $u>0$, it follows that $\prod_1^k\ell_i^{\ell_i}$ is Schur-convex in the $\ell_i$'s, so that for any fixed real $c>0$ $$|A(x_1,\dots,x_k)|\le N(2h)^k(\tfrac{3k}4)^{3k/4} \le \frac{4^k}{(k-1)^k}\,k^{3k/4}=o(c^k)$$ as $k\to\infty$.

We show it is wrong for $x_i=\frac{i}{k}$. And we note $J_i=[x_i,x_{i+1}]$

First note that because $\forall i,\lambda(J_i)=\frac{1}{k}$, there is no more than $\frac{k}{2}$ such intervals included in a set $\cup I_i$. Therefore, for any set $\cup I_i$ with $\lambda(\cup I_i)\leq 1/2$ there exist at least $\frac{k}{2}$ split in $J_{i_1},J_{i_2},...J_{i_{\frac{k}{2}}}$ we have then

$$A(x_1,\dots ,x_k)\subset \cup_{J_{i_1},\dots ,J_{i_{k/2}}}[(y_1,\dots , y_k),sup J_{i_l}<x_i<inf J_{i_{l+1}}\Rightarrow inf J_{i_l}<y_i<sup J_{i_{l+1}}]$$ Indeed otherwise $J_{i_l}\subset[y_i,x_i]$ or $J_{i_{l+1}}\subset[x_i,y_i]$.

Finally, because there are $k/2$ split, there is at least $k/4$ split such that $i_{l+1}-i_l\leq 4$ and there is then $k/4$ index $i$ such that $y_i$ is trapped inside a interval of length $6/k$. We can then conclude : $$\lambda^{\otimes k}(A(x_1 \dots x_k))\leq \begin{pmatrix}k \\ k/2 \end{pmatrix} (\frac{6}{k})^{k/4}\leq 2^k(\frac{6}{k})^{k/4}$$

• How is your $J_i$ defined and why is it $[x_i,x_{i+1}]$? – Iosif Pinelis Sep 11 '17 at 17:18
• Thanks for your answer. But I have some trouble understanding the long equation in the middle.could you please explain more that why A is contained in that set and what is that set? – Cuize Han Sep 11 '17 at 18:24
• The idea is to ask which $(x_i,x_j)$ are in the connected subset of $\cup I$. $(x_i,x_{i+1})$ are in the same one iff $J_i=[x_i,x_{i+1}]\subset \cup I$. For the large equation. because there exists $z_l\in J_{i_l}$ $z\notin \cup I$, then the interval $I$, with $x\in I$ is $I \subset [z_l,z_{l+1}]\subset [inf J_{i_l} ,max J_{i_{l+1}}]=[x_{i_l},x_{i_{l+2}}]$. – user112703 Sep 13 '17 at 7:16