finite partitions of the square that separate all equipotent sets of points

29 Views Asked by At

This question asked whether there exists a finite partition of $[0, 1]^2$ and a finite set of points in $[0, 1]^2$ that can't be affinely transformed to fall into one part of the partition.

I would like to ask a related and simpler question: for every $k > 0$, is there a partition of $[0, 1]^2$ of size $k$ such that every $k$ points in $[0, 1]^2$ can be affinely transformed to fall in different parts of the partition? We may generalize to $[0, 1]^d$. I am interested both in answers to the full question and solutions for particular $k$ (and $d$).

1

There are 1 best solutions below

0
On BEST ANSWER

I will answer this question in the affirmative for all dimensions $d$ and numbers of points $k$.

First we reduce the $d$-dimensional case to the 1-dimensional case. For every $k$ points in $\mathbb{R}^d$, there is a line onto which the projections of the points are distinct. This is because there are finitely many directions through two points and any line with another direction suffices. Now we rotate the points about the origin so that this line is parallel to the $x$ axis. All $x$ coordinates of the rotated points are distinct. Given a solution to the 1-dimensional case for $k$ points, partition $[0, 1]$ along the $x$ axis accordingly and extend each part $P$ to $[0, 1]^d$ as $P \times [0, 1]^{d-1}$. This solution is independent of our $k$ points and thus is a $d$-dimensional solution.

Note that this reduction just needed to rotate the points and then possibly scale them to fit in $[0, 1]$.


Toward proving the 1-dimensional case, we state a trivial lemma: for any real numbers $x_1 < \ldots < x_k$, there are natural numbers $0 = n_0 < n_1 < \ldots < n_k$ such that $x_i \in (\frac{n_{i-1}}{n_k}, \frac{n_i}{n_k})$. This is because there is a $\frac{1}{n}$-width grid separating all $x_i$ and we may set $n_i$ to a number of grid cells containing $x_i$ but not $x_{i+1}$.

Now we enumerate all natural number $k$-tuples $0 = n_0 < n_1 < \ldots < n_k$ as $(N_i)_{i \in \mathbb{N}}$. We scale and translate $N_i$ to $(2^{-(i+1)}, 2^{-i})$. We then set each part of the partition $P_j$ to be the $j$th part of each $N_i$. As any $x_1 < \ldots < x_k$ can be separated by some $N_i$, the $x_j$ can be translated and scaled to $(2^{-(i+1)}, 2^{-i})$ to fall one point per part.


Note that for the 1-dimensional case we just needed to translate and scale the $x_j$. There is also a solution that just scales the $x_j$. Toward this end we choose a convergent series $t_i$ other than $2^{-i}$ such that $\frac{t_{i+1}}{t_i} \rightarrow 0$. We then scale each $N_i$ by $\frac{t_i}{n_k}$ so that it fits in the interval $(0, t_i]$ and remove the portion of $N_i$ in the interval $(0, t_{i+1}]$. The resulting $N_i$ then fill $(0, 1]$. As any $k$ positive numbers $x_j$ may be scaled by $t_i$ to fit in $(t_{i+1}, t_i]$ for all sufficiently large $i$, and because there is no maximum $i$ for which $N_i$ separates $x_j$, we may scale all $x_i$ by some $t_i$ to fall in all parts of the partition.

Combining everything, we see that the $d$-dimensional case can be solved with just rotations and scales.


As a final note, we may produce a single countable partition that accommodates every finite set of points by interleaving the $N_i$ for different $k$.