Number of regions formed by translations of a hyperplane arrangement

112 Views Asked by At

Let $\mathcal{A}$ be a hyperplane arrangement (a collection of hyperplanes) in $\mathbb{R}^d$. The number of regions $r(\mathcal{A})$ determined by $\mathcal{A}$ is defined as the number of connected components of $$\mathbb{R}^d\setminus\bigcup_{h\in\mathcal{A}}h.$$ It is well known and easy to see that $r(\mathcal{A})\le |\mathcal{A}|^d.$

Now, let $\mathcal{A}_1,\ldots,\mathcal{A}_M$ be translates of $\mathcal{A}$, that is, if $\mathcal{A} = \{h_1,\ldots, h_n\}$, then $\mathcal{A}_m = \{h_1^m,\ldots, h_n^m\}$, where $h_i^m$ and $h_i$ are parallel. Obviously, as before, $r(\bigcup A_m)\le (M|\mathcal{A}|)^d.$ I'm wondering if something stronger can be said here by exploiting the fact that the arrangement consists of translations of a smaller arrangement. For example, no two hyperplanes from $\{h_i^1,\ldots, h_i^M\}$ can contribute to the same region, for each $i$ (since they are translates of one another). Most work in this area starts by assuming the arrangement is in general position, so I'd appreciate any help here!

1

There are 1 best solutions below

0
On BEST ANSWER

If $d=1$, then worst-case answer is $M|A|+1$, so no improvement here.

If $d=2$, then you get the bound $\frac{|A|M(|A|M+1)}{2}-|A|\frac{(M-1)M}{2}$, so if you want to view $|A|$ as fixed and have $M \to \infty$, this yields an improvement of $\frac{|A|^2M^2}{2}$ to $\frac{(|A|^2-|A|)M^2}{2}$ roughly.

The way you get that $d=2$ bound is simply by going through the proof that $r(A) \le \frac{|A|(|A|+1)}{2}+1$ (which is obtained by starting with $r(1) = 2$ and then noting $r(m+1) \le r(m)+m$, which follows from the creation of at most $m$ new regions when you "add" the $(m+1)^{st}$ line). Indeed, you start with $r(A) \le \frac{|A|(|A|+1)}{2}+1$ and note that when you add $h_1^2$, you create new regions only possibly by intersecting with $h_2^1,\dots,h_n^1$ (not with $h_1^1$), and when you add $h_2^2$, you intersect with $h_1^1,h_3^1,\dots,h_n^1$ but not with $h_2^1$. Etc until you add $h_n^2$. Then $h_3^1$ misses $h_1^1,h_2^1$. Etc. etc.

I assume the same argument gives an improvement for $d \ge 3$ when $|A|$ is fixed and $M \to \infty$.

The argument given is tight, at least for $d=2$, in that the addition of $h_j^m$ will create new regions via intersection with $h_i^{m'}$ for $m' < m$ and $i \not = j$, provided $h_1,\dots,h_n$ start off in general position, so you can't get a better improvement than the bound obtained above. [It's probably tight for $d \ge 3$; I just can't visualize].