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$ 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
    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
    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$ Sep 13, 2017 at 23:23
  • $\begingroup$ Nice short argument! $\endgroup$
    – Cuize Han
    Sep 14, 2017 at 2:09

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.