4
$\begingroup$

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

$\endgroup$
7
  • $\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$ Sep 10, 2017 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, 2017 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, 2017 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$ Sep 10, 2017 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, 2017 at 22:15

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ How is your $J_i$ defined and why is it $[x_i,x_{i+1}]$? $\endgroup$ Sep 11, 2017 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, 2017 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, 2017 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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