Combinatorial question on the arrangement of hyperplanes

54 Views Asked by At

Let $l,m\in\mathbb{N}_+$ and define $\Theta(l,m):=\mathbb{R}^{m\times l}\times \mathbb{R}^m$ to be the set of tuples of a $m\times l$ matrix and a vector of length $m$.

Definition of $v_\theta$ and $V_m$

For fixed $\theta\in\Theta(l,m)$, identify $\theta=(W,b)$ and let $w_1,\cdots,w_m$ be the rows of $W$. Now we have $m$ hyperplanes $H_1,\cdots,H_m$ in $\mathbb{R}^l$, given by $H_i:\{x\in\mathbb{R}^l\vert \langle x, w_i\rangle=b_i\}$ for $i\in\{1,\cdots,m\}$. For each $x\in\mathbb{R}^l$ we can define the signature $S_\theta(x)\in\{0,1\}^m$ that determines if $x$ lies on the positive side of the hyperplanes, i.e. $S_\theta(x)_i=1$ if and only if $\langle x,w_i\rangle >b_i$ for $i\in\{1,...,m\}$. We will denote the set of all attained signatures by $\mathcal{S}_\theta:=\{S_\theta(x)\vert x\in\mathbb{R}^l\}\subset\{0,1\}^m$. Now we define $v_\theta\in V_m:=\{ v:\{0,\cdots,m\}\to \mathbb{N}_0\}$ by $v_{\theta}(j):=\vert\{s\in\mathcal{S}_\theta\vert \sum_{i=1}^ms_i=j\}|$ for $j\in\{0,\cdots,m\}$. That means we are counting in each coordinate $j$ of $v_\theta$: "How many attained signatures are there that correspond to $x$ values in $\mathbb{R}^l$ lying in the positive side of exactly $j$ of the $m$ hyperplanes?"

Definition of a maximum on $V_m$

For $v\in V_m$, we write $v_i$ for $v(i)$, $i\in\{0,\cdots m\}$. Define a partial order $\preceq$ as follows: For $u,v\in V_m$, $u\preceq v$ if and only if $\forall K\in\{0,\cdots,m\}: \sum_{i=K}^{m}u_i\le\sum_{i=K}^mv_i$. Intuitively, this means that $u\preceq v$ "if $u$ can be transformed into $v$ by moving weights from smaller to larger indices and/or adding new weights". For $u,v\in V_m$, we can define a maximum $w\in V_m$ by the conditions $\forall K\in\{0,\cdots,m\}: \max(\sum_{i=K}^{m}u_i,\sum_{i=K}^{m}v_i)=\sum_{i=K}^mw_i$. We will denote this $w$ by $\max(u,v)$. It is the smallest element in $V$ that satisfies $u\preceq w$ and $v\preceq w$. Similarly (or recursively), we can define the maximum $\max(v_1,\cdots,v_L)$ of finitely many elements $v_1,\cdots,v_L\in V_m$, $L\in\mathbb{N}_+$.

Question

For fixed $l,m\in\mathbb{N}_+$, what is $\max\{v_\theta\vert \theta\in\Theta(l,m)\}$?

Note that this is well-defined because it is actually a maximum of finitely many elements.

Example

For $l=1$, we need to consider $m$ hyperplanes (points) on the real line. They partition it into at most $m+1$ bounded or half-open intervals. Only one such interval can have signature $s=(1,\cdots,1)$ with $\sum_{i=1}^{m}s=m$ because only one such interval can lie on the positive side of all $m$ hyperplanes. If there is such an interval, from there we can go to the left and right on the real line and each time we pass one of the $m$ points, the quantity $\sum_{i=1}^m s_i$ decreases by one, so in this case, at most two such intervals can have a signature $s$ with $\sum_{i=1}^m s_i=m-1$. Following this idea leads me to the hypothesis that the required maximum is obtained by filling a vector $v\in V_m$ with $m+1$ unit weights starting at index $m$ with "capacity" 1 and continuing with smaller indices with "capacity" 2, i.e. I think that for $m\in\mathbb{N}_+$, \begin{equation} \max\{v_\theta\vert\theta\in\Theta(1,m)\}= \begin{cases} e_m + \sum_{i=m-(m-1)/2}^{m-1}2e_i&\text{if $m$ is odd}\\ e_m + \sum_{i=m-(m-2)/2}^{m-1}2e_i+e_{m/2}&\text{if $m$ is even} \end{cases} \end{equation}with unit vectors $e_i(j)=\delta_{ij}$ for $i\in\{0,...,m\},j\in\mathbb{N}_0$. But this is just a hypothesis for a special case of the question.