lower bound volume of a set

Question

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. )

Answer 1

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 \begin{equation} m-1\ge\frac1{2h}=\frac{k-1}2. \end{equation} 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, \begin{equation} |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\}, \end{equation} 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$ \begin{equation} |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) \end{equation} as $k\to\infty$.

Answer 2

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}$$