# Reaching the double exponential upper bound in Fourier-Motzkin elimination

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.)

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.

• 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. – David Monniaux Apr 5 '18 at 20:56
• 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? – Sasha Kozachinskiy Apr 6 '18 at 21:46
• 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. – David Monniaux Apr 8 '18 at 6:34
• 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. – Sasha Kozachinskiy Apr 8 '18 at 8:56