2
$\begingroup$

Given a positive constant $0<\gamma<1$, does there exists integer $k_0>0$ such that for any integer $k\geq k_0$ the following holds?:

For any $A\subseteq\left[0,1\right]^k$ with the measure of $A$ satisfied $\mu(A)\geq\gamma$, there exists integer $k_1\geq\sqrt{k}$ such that $A$ can be approximated by a product space (Cartesian product) formed by a subset in $\mathbb{R}^{k-k_1}$ and a hypersquare in $\mathbb{R}^{k_1}$?

i.e. there exist $K_1\subseteq[k],|K_1|=k_1$ and $A_0\subseteq\mathbb{R}^{[k]-K_1}$ and for any $i\in[K_1]$ there exist $U_i\subseteq[0,1]$, such that $A\triangle (A_0\cdot\prod U_i)=(A_0\cdot\prod U_i-A)\cup(A-A_0\cdot\prod U_i)\leq\varepsilon$ for some $\varepsilon\ll\gamma$.

$${}$$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Apparently not. Let $\gamma=1/3$ and choose some $\varepsilon<\frac{1}{4}$.

For any $k\in\mathbb{N}$ we can consider the set

$$A=\left\{(x_1,\dots,x_k)\in[0,1]^k;\;\sum_{i=1}^k\lfloor2x_i\rfloor\equiv0\text{mod}2\right\}.$$ (So, $A$ is the `white squares' in a $k$-dimensional chess board of side $2$)

Then for any subset $U\subseteq[0,1]$ and any measurable $B\subseteq\mathbb{R}^{k-1}$, we will have $\mu(A\Delta(U\times B))\geq\frac{1}{4}$. This follows from the proof of the claim below and the fact that $A$ can be expressed (up to measure $0$) as $([0,1/2)\times C_1)\cup([1/2,1)\times C_2)$, where $C_1,C_2\subseteq[0,1]^{k-1}$ are disjoint and have measure $1/2$.

Claim: Let $A:=[0,1/2)^2\cup[1/2,1)^2\subseteq[0,1]^2$. For any subsets $X_1,X_2$ of $[0,1]$, $\mu((X_1\times X_2)\Delta A)\geq\frac{1}{4}$.

Proof:

Let $x:=\mu([0,1/2)\cap X_1),y:=\mu([1/2,1)\cap X_1)$, $z:=\mu([0,1/2)\cap X_2),w:=\mu([1/2,1)\cap X_2)$.

Clearly $\mu((X_1\times X_2)\Delta A)$ only depends on $x,y,z,w$, and in fact (as shown in the picture, where $(X_1\times X_2)\Delta A$ is shaded) we have $\mu((X_1\times X_2)\Delta A)=\frac{1}{2}+xw+yz-xz-yw$. 1

Thus, the problem is reduced to minimizing the function $xw+yz-xz-yw$ for $x,y,z,w\in[0,1/2]$, and one checks that the minimum is $-\frac{1}{4}$, concluding the proof.

Similar examples should work for $\gamma=1-\frac{1}{n}$, by letting $\varepsilon=\frac{1}{100n}$ and $$A=\left\{(x_1,\dots,x_k)\in[0,1]^k;\quad\sum_{i=1}^k\lfloor100(n+1)x_i\rfloor\not\equiv0\text{ mod }n+1\right\}.$$

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your answer, however, $U_i$ needn't to be an interval--it is just a subset of [0,1]. $\endgroup$
    – tom jerry
    Commented May 9 at 14:13
  • $\begingroup$ Oh sorry, when I read `hypersquare' I had thought it would be a product of intervals. The construction will still work I think, I will write why $\endgroup$
    – Saúl RM
    Commented May 9 at 14:45
  • $\begingroup$ I am sure there is a much more elegant way to write my answer, for now I just wrote the first thing that came to mind. I will surely try to write something nicer later if noone does it first $\endgroup$
    – Saúl RM
    Commented May 9 at 15:30
  • $\begingroup$ Thank you! And moreover, could this implies that when k_1 larger than √k (but not let k_1=1) , the question is negative? $\endgroup$
    – tom jerry
    Commented May 9 at 15:56
  • $\begingroup$ Of course, what I prove is more general (if $k_1>1$, that just means that the set $B$ of my answer can be expressed as a product) $\endgroup$
    – Saúl RM
    Commented May 9 at 16:08

You must log in to answer this question.

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