3
$\begingroup$

Let $\lambda$ be Lebesgue measure on $[0,1]$. For $\mathbf{x}=(x_1,x_2,..,x_k)\in[0,1]^k$, define $$A(\mathbf{x}):=\{(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 it true that the maximum number $n$ such that there exists $\mathbf{x}_1,..,\mathbf{x}_n\in[0,1]^k$ that satisfy $A(\mathbf{x}_1),..,A(\mathbf{x}_n)$ are mutually exclusive has at most exponentially growth speed in $k$?

That is if we denote $$n^*=\max\{n\in\mathbb{N}:\exists \text{ $\mathbf{x}_1,..,\mathbf{x}_n\in[0,1]^k$ that $A(\mathbf{x}_1),..,A(\mathbf{x}_n)$ are mutually exclusive }\} ,$$ can we prove $$n^*\leq C^k$$for some constant $C>1$?


First I tried a simple volume argument. I guessed for any $\mathbf{x}\in[0,1]^k$ we have $\text{vol}(A(\mathbf{x}))\geq c^k$ for some constant $c<1$. But it turns out not true. See the answer here lower bound volume of a set.

Any thoughts and comments are welcome!

Thanks for your help!

$\endgroup$
2
  • $\begingroup$ There will be no such constant if we replace $1/2$ by any smaller number --- but I assume you already know that? $\endgroup$ Commented Sep 13, 2017 at 12:37
  • $\begingroup$ @ IIya Bogdanov No, I don't know that. Really? How do you prove that? Actually I thought the constant doesn't affect the result except the choice of C. I am also interested if you can prove that for the constant very close to 1 $\endgroup$
    – Cuize Han
    Commented Sep 13, 2017 at 14:12

1 Answer 1

1
$\begingroup$

[EDIT] This is an affirmative answer to the original question, with $C=2$. The negative answer to the version where $1/2$ is replaced by a smaller constant is kept below.

For every $\mathbf x\in[0,1]^k$, we define $\mathbf a(\mathbf x)\in\{0,1\}^k$ by $a(x)_i=0\iff x_i\leq 1/2$. Now, assume that $A(\mathbf x^1),\dots,A(\mathbf x^n)$ are disjoint and $N>2^k$; then there are $\mathbf x=\mathbf x^i$ and $\mathbf z=\mathbf x^j$ with $i\neq j$ but $\mathbf a(\mathbf x)=\mathbf a(\mathbf z)=\mathbf a$.

Now define $\mathbf y\in[0,1]^k$ as follows: If $a_i=0$ then $y_i=x_i(\leq 1/2)$, otherwise $y_i=z_i(>1/2)$. Then $\mathbf y\in A(\mathbf x)$ due to the following system of segments: $I_i=[x_i,x_i]$ if $a_i=0$, and $I_i=[1/2,1]$ otherwise. Similarly, $\mathbf y\in A(\mathbf z)$ due to the following system of segments: $I_i=[0,1/2]$ if $a_i=0$, and $I_i=[z_i,z_i]$ otherwise. Thus $A(\mathbf x)\cap A(\mathbf z)\neq\varnothing$ --- a contradiction.

Thus $C=2$ fits.


[ORIGINAL] The rest of the text shows what happens if we replace $1/2$ by a smaller constant.

For $\mathbf x,\mathbf y\in[0,1]^k$, denote by $d(\mathbf x,\mathbf y)$ the minimal total length of a system of (disjoint) segments such that for every $i$, the numbers $x_i$ and $y_i$ lie in one of the segments. Clearly, $d$ is a metric. If we replace $1/2$ by some $\alpha<1/2$, then we are interested in finding many mutually disjoint balls $B_\alpha(\mathbf x)$ of radius $\alpha$ one can find in $[0.1]^k$.

For that purpose, it suffices to find many points $\mathbf x^i$ with pairwise distance $>2\alpha$. We will seek for such points of the form $$ \mathbf x^\sigma=\left(\frac{\sigma(0)}{k-1},\dots,\frac{\sigma(k-1)}{k-1}\right), $$ where $\sigma$ is a permutation of $\{0,1,\dots,k-1\}$.

Let $V$ be the number of points having the form $\mathbf x^\sigma$ and lying in a ball $B_{2\alpha}(\mathbf x^\tau)$ for some fixed $\tau$; the number $V$ does not depend on $\tau$, since all our points are equivalent via permutation of coordinates. Then we may choose the ``distant'' set of at least $k!/V$ such points, choosing one by one (since each chosen point prohibits at most $V$ points, including itself). So we are to estimate $V$ now, asssuming that $\tau=\mathrm{id}$ and denoting $\mathbf x=\mathbf x^\tau$.

Set $\ell=[2\alpha(k-1)]$. Then $d(\mathbf x,\mathbf x^\sigma)\leq 2\alpha$ iff there exists a set of (disjoint) segments of the form $[a/(k-1),b/(k-1)]$ with total length exactly $\ell/(k-1)$ such that $i/(k-1)$ and $x^\sigma_i$ are always in the same segment (we allow $a=b$, in which case the length of the segment is $0$).

Such a set of segments can be chosen in ${k-1\choose \ell}$ ways (choosing which elementary segments are covered). Consider any such set with lengths $m_1,\dots,m_s$; then there are exactly $(m_1+1)!(m_2+1)!\dots(m_s+1)!$ points $\mathbf x^\sigma$ ``compatible'' with this set.

Finally, notice that for any $m,n\geq 1$ we have $m!n!=m!\cdot 2\cdots n\leq (m+n-1)!$. Thus $$ (m_1+1)!\dots(m_s+1)!\leq (m_1+\dots+m_s+1)!=(\ell+1)!. $$ This means that $V\leq{k-1\choose \ell}(\ell+1)!=\frac{(k-1)!}{(k-\ell-1)!}(\ell+1)$.

Therefore, we can choose at least $$ \frac{k!}V\geq \frac{k(k-\ell-1)!}{\ell+1}\geq (k-\ell-1)! $$ points with pairwise distances $>2\alpha$; this number is superexponential in $k$ (since $k-\ell-1\approx[k(1-2\alpha)]$).

$\endgroup$
3
  • $\begingroup$ Thanks for your answer! Now I see that it won't work for length smaller than half. Your negative answer suggest it is not true for any constant smaller than 1? $\endgroup$
    – Cuize Han
    Commented Sep 13, 2017 at 17:21
  • $\begingroup$ I'm sorry; now I'm convinced that the answer for $\alpha=1/2$ is in the affirmative; see the new part of the answer (at the top of it). $\endgroup$ Commented Sep 13, 2017 at 23:23
  • $\begingroup$ Nice short argument! $\endgroup$
    – Cuize Han
    Commented Sep 14, 2017 at 2:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .