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

  • $\begingroup$ 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$. $\endgroup$ – Iosif Pinelis Sep 10 '17 at 21:47
  • $\begingroup$ @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$ $\endgroup$ – Cuize Han Sep 10 '17 at 21:50
  • $\begingroup$ @Nate Eldridge The previous description is confusing. Actually the set is a subset of $[0,1]^k$ (thanks for the editing) $\endgroup$ – Cuize Han Sep 10 '17 at 21:56
  • $\begingroup$ 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!$. $\endgroup$ – Mateusz Kwaśnicki Sep 10 '17 at 22:05
  • $\begingroup$ @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]$. $\endgroup$ – 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 \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$.


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

  • $\begingroup$ How is your $J_i$ defined and why is it $[x_i,x_{i+1}]$? $\endgroup$ – Iosif Pinelis Sep 11 '17 at 17:18
  • $\begingroup$ 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? $\endgroup$ – Cuize Han Sep 11 '17 at 18:24
  • $\begingroup$ 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}}]$. $\endgroup$ – user112703 Sep 13 '17 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.