I'm reading a scientific paper on integer linear programming and trying to understand a specific part of it.
There is a point $ b \in \mathbb Z^m $ and a set $\mathcal S$ that consist of all points $x \in \mathbb Z^m$ for which there exists some $\alpha \in \mathbb R, \alpha \geq 0, \alpha \leq 1$ with
$\|x - \alpha \cdot b\|_{\infty} \leq 2m \cdot \Delta$
($\Delta \in \mathbb Z,$ so $2m \cdot \Delta $ is some constant integer value)
So in short, the set $\mathcal S$ contains integer points which are at some distance $d$ from the line segment connecting $0$ and $b$.
The paper says (right in the middle of pg 5) the following:
We now argue that $\mathcal |S| \leq (4m · \Delta + 1)^m ·\|b\|_1$ .
Let $ f \in \mathbb R^m$ be any point. Since $2m \cdot \Delta $ is an integer, the integer points at distance at most $2m \cdot \Delta $ from $f$ are contained in the set of integer points at distance at most $2m \cdot \Delta $ from $\lfloor f \rfloor $. Therefore, an upper bound on $\mathcal |S|$ is the number of different integer vectors that can be obtained by rounding a point on the line-segment $(0, b)$ times $ (4m · \Delta + 1)^m $ . The number of rounded integer points is at most $\|b\|_1$.
I've been trying to understand where the $ (4m · \Delta + 1)^m $ and $\|b\|_1$ come from, but to no avail.
Could you please give me any tips or suggestions about this particular variables or the problem in general?
The key point here is the observation that the integer points at distance at most $k=2m\cdot\Delta$ from $f$ are contained in the set of integer points at distance at most $k$ from $\lfloor f \rfloor$. We can see this by noting that $|x_i-f_i| \le k$ is equivalent to $-k\le x_i-f_i \le k$. Since $x_i,k$ are integers, the inequality $x_i-f_i\le k \leftrightarrow x_i-k\le f_i$ is just the same as $x_i-k\le \lfloor f_i \rfloor$ (and similarly to the other inequality). With this key observation, to bound the number of integral points in the set $\|x - \alpha \cdot b\|_{\infty} \leq 2m \cdot \Delta$, we only need to bound the total number of integral points obtained from the sets $\|x - c\|_{\infty} \leq 2m \cdot \Delta$ where $c$ is an integral point on the line segment between $0$ and $b$. And how many such integral points $c$? There are at most $\|b\|_1$ such points.
Now, let's think about the set of points $x$ that $\|x - 0\|_{\infty} \leq k $. This is just the hypercube with length $k$ in $\mathbb{R}^m$ and it has exactly $(2k+1)^m$ integral points (for each integral point $(x_1,\ldots ,x_m)$ there are $2k+1$ ways to choose an integral value for each $x_i$).
Now for any integral point $b$, the set of points $x$ that $\|x - b\|_{\infty} \leq k $ is just the translation of hypercube with length $k$ in $\mathbb{R}^m$ by $b$ so it has exactly the same number of integral points in it, which is $(2k+1)^m$. This is the reason why they have $(4m · \Delta + 1)^m$ in their estimation.