5
$\begingroup$

One round of Fourier-Motzkin elimination may yield $n^2/4$ inequalities where $n$ is the original number of linear inequalities, whence an upper bound of $n^{2^d}/2^{2^{d+1}-2}$ for $d$ rounds of elimination without removal of redundant constraints.

I'm wondering whether it is possible to meet this upper bound.

(Note: this is a distinct question from that of counting the number of true faces in a projection, that is, after removal of redundant constraints, for which McMullen's upper bound provides a tighter bound.)

$\endgroup$
4
$\begingroup$

I think this upper bound is tight. As an example, consider the following system

\begin{align*} +x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le 0 \\ +x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le 0 \\ +x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le 0 \\ +x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le 0 \\ -x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le 0 \\ -x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le 0 \\ -x_0 & -\frac{3}{2} x_1 +\frac{1}{4} x_2 \le 0 \\ -x_0 & -\frac{3}{2} x_1 -\frac{7}{4} x_2 \le 0 \\ \end{align*}

It has 8 inequalities. Though some of them are identical, it is not a problem since we do not remove redundant constraints. One can also add dummy variables to make them different. Reducing $x_0$, we obtain system with 16 inequalities. Then, reducing $x_1$, we obtain system with $64$ inequalities.

More generally, let $S_{n}^k$ denote the following system of inequalities over $x_0, x_1, \ldots, x_{k - 1}$. Here we assume that $k \le n, n\ge 2$. There will be $2^n$ inequalities in $S_{n}^ k$. Take any $m \in\{1, 2, \ldots, 2^n\}$. Let $m^{th}$ inequality of $S_{n}^ k$ be $$\alpha^m_0 x_0 + \ldots + \alpha^m_{k - 1} x_{k - 1} \le 0,$$ where $$\alpha^m_i = \begin{cases} 2^{-i} & \mbox{if $m \le 2^n - 2^{n - i - 1}$}, \\ -2 + 2^{-i} & \mbox{otherwise.} \end{cases}$$

Here we use a restriction mentioned above : provided $k\le n$, we have that $2^{n - i - 1}$ is an integer.

For example, system above is $S_{3}^3$. It is easy to verify that if we eliminate $x_0$ from $S_{n} ^k$, we obtain $S_{2n - 2} ^{k - 1}$. Indeed, when we eliminate $x_0$, we add up all the inequalities from the first half with all the inequalities from the second half. Thus we get $2^{n - 1} \cdot 2^{n - 1} = 2^{2n - 2}$ inequalities. What happens with $x_i$ for $i > 0$? In the first $$2^{n - 1} \cdot (2^{n - 1} - 2^{n - i - 1}) = 2^{2n - 2} - 2^{2n - 2 - i} = 2^{2n - 2} - 2^{(2n - 2) - (i - 1) - 1}$$ inequalities a coefficient before $x_i$ will be $2^{-i} + 2^{-i} = 2^{-(i - 1)}$. In the last $2^{-i} + (-2 + 2^{-i}) = 2^{(2n - 2) - (i - 1) - 1}$ inequalities a coefficient before $x_i$ will be $2^{-i} + (-2 + 2^{-i}) = -2 + 2^{-(i - 1)}$. This is $S_{2n - 2}^{k - 1}$, but over variables $x_1, \ldots, x_{k - 1}$. Since, $2n - 2 \ge n - 1 \ge k - 1$, a restriction on the number of variables is also preserved.

Further, if we eliminate $x_1$, we obtain $S_{4n - 6}^{k - 2}$, and so on. After $d$ steps we will have $S^{k - d}_{2^d n - (2^{d + 1} - 2)}$. The latter has exactly $$2^{2^d n - (2^{d + 1} - 2)} = N^{2^d}/ 2^{2^{d + 1} - 2}$$ inequalities, where $N = 2^n$ is the number of inequalities of the initial system.

$\endgroup$
  • $\begingroup$ Thank you very much. However, when I iterated Fourier-Motzkin 3 times from this original system of inequalities, I ended up with a system containing 1024 (the right number) inequalities all with a positive coefficient in column 3, thus the next step of elimination yields an empty set. Maybe I implemented it wrong. $\endgroup$ – David Monniaux Apr 5 '18 at 20:56
  • $\begingroup$ Sorry, but do you mean a system from the beginning of my answer? Applying Fourier-Motzkin 3 times elimininates all the variables in it; maybe I'm missing something? $\endgroup$ – Sasha Kozachinskiy Apr 6 '18 at 21:46
  • $\begingroup$ I created a system with 8 inequalities and 10 variables according to these formulas and projected it 3 times. The last system I get has 1024 inequalities, but they all have a positive component on the next variable so the next system has 0 inequalities. Maybe I implemented something wrong. $\endgroup$ – David Monniaux Apr 8 '18 at 6:34
  • $\begingroup$ As it turns out, my answer works only when the number of variables is at most logarithm of the number of inequalities, i.e., $k\le n$. This is because in my argument I use a fact that $2^{n - i - 1}$ is an integer. Modified my answer to make it explicit. $\endgroup$ – Sasha Kozachinskiy Apr 8 '18 at 8:56

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.