Proof. Fix an instance of \(\mathcal{C}\)-Binary ILP feasibility specified by \(A \in \Z^{m \times n}\) and \(b \in \Z^m\), with the column set \(\mathcal{A}\) satisfying \(|\mathcal{A} + \mathcal{A}| \leq \mathcal{C}|\mathcal{A}|\).

Let \(L \mathrel{\vcenter{:}}= \Sigma(2^{\mathcal{A}})\) denote the list of all (vector) sums that can be attained by adding together any subset of the columns of \(A\). Equivalently, this is the set of possible outputs \(Ax\) for any \(x \in \{0,1\}^n\). Our first goal is to bound \(|L|\).

First, we observe that there exists a GAP \(P\) with dimension \(d(\mathcal{C})\) and volume \(v(\mathcal{C}) n\) such that \[\mathcal{A} \subseteq P = \{x_1k_1 + x_2k_2 + \dots + x_{d(\mathcal{C})}k_{d(\mathcal{C})} \; : \; \forall i, k_i \in [K_i] \},\] where \(x_i \in \Z^m\) for all \(i \in [d(\mathcal{C})]\). This is true even though \(\mathcal{A}\) is a set of integer vectors, as Freiman’s Theorem holds for torsion-free⁶ commutative groups ([34], Theorem 8.1).

Thus \(L\) is contained in the GAP \[P' = \{x_1k_1 + x_2k_2 + \dots + x_{d(\mathcal{C})}k_{d(\mathcal{C})} \; : \; \forall i, k_i \in [n \cdot K_i] \},\] which implies \[\label{eq:LA-bound} |L| \leq |P'| \leq n^{d(\mathcal{C})} |P| = n^{d(\mathcal{C})} v(\mathcal{C}) n = n^{O_\mathcal{C}(1)}.\tag{2}\]

To complete the proof, we claim that we can enumerate \(L\) efficiently via dynamic programming, using the following procedure: Initially, we set \(L_1 = A[1,\cdot]\). Then, we iterate \(i = 2,3,\ldots,n\). In the \(i\)th iteration, we construct the sorted list \(L_i\), defined as:

\[L_i \mathrel{\vcenter{:}}= L_{i-1} \cup \{a+A[i,\cdot] \mid a \in L_{i-1}\}.\]

Finally, we return list \(L = L_n\). Correctness of the above algorithm follows immediately by a construction. For the running time, observe that \(L_i\) can be constructed in \(O(|L_i|)\) time. Because each of the \(n\) iterations of the subprocedure takes time \(O(|L_i|) = O(|L|)\), the total runtime is, by 2 , at most \(n \cdot O(|L|) = n^{O_\mathcal{C}(1)}\). ◻

Proof. Modify the proof of by considering the list \(L'\) of all possible outputs \(Ax\) for each valid assignment of variables \(x\), using the variable bounds \(x_i \in [\ell_i : u_i]\) for \(i \in [n]\) instead of \(x \in \{0,1\}^n\). As before, we bound \(|L'|\).

Observe that \(L'\) is contained in the GAP \(P''\) obtained by scaling each range bound \(L_i\) of \(P\) by a factor of \(n^{O(1)}\), where the hidden constant is determined by the bounds on the variables. It follows that \(|L'| = n^{O_\mathcal{C}(1)}\). We can enumerate \(L'\) by modifying the procedure given above so that Step 2 merges a polynomial number of lists, one for each variable assignment. ◻

Proof. Fix an instance of \(\mathcal{C}\)-Subset Sum given by an integer set \(Z\) satisfying \(|Z + Z| \leq \mathcal{C}|Z|\) and an integer target \(t\). Apply , which fails with probability \(n^{-\gamma}\) and otherwise produces a GAP \[P = \{y_1\ell_1 + y_2\ell_2 + \cdots + y_d\ell_d \; : \; \forall i, \ell_i \in [L_i]\}\] of dimension \(d \mathrel{\vcenter{:}}= d(\mathcal{C})\) and volume \(v(\mathcal{C})n\) containing \(Z\).

For each \(z_i \in Z\), let \(v(z_i) = (v_1, v_2, \dots, v_d)\) be an arbitrary \(d(\mathcal{C})\)-dimensional integer vector satisfying \[\begin{align} y_1v_1 + y_2v_2 + \dots y_dv_d &= z_i \text{ and } \\ \forall i \in [d], v_i &\in [L_i]. \end{align}\] We can think of \(v(z_i)\) as the \(d\)-dimensional “GAP coordinates” of the input element \(z_i\). \(v(z_i)\) is guaranteed to exist by Freiman’s theorem, and we can recover it in time \(O(|P|) = O_\mathcal{C}(n)\) via exhaustive search of \(P\). (However, \(v(z_i)\) is not guaranteed to be unique.)

To complete the reduction, set \[\begin{align} A &\in \Z^{d(\mathcal{C}) \times n} \text{ with } \forall j \in [n], A[\cdot, j] = v(z_j), \end{align}\] set \(s \mathrel{\vcenter{:}}= (y_1, y_2, \dots, y_d)\) and preserve the same target \(t\). Note that \(\lVert A \rVert_\infty \leq n^{2 / d(\mathcal{C})}\) without loss of generality by .

We claim that for any binary vector \(x = (x_1, x_2, \dots, x_n) \in \{0, 1\}^n\), \[\label{eq:equivalence-SS-HBILP} \langle Ax, s \rangle = \sum_{i \; : \; x_i = 1} z_i.\tag{3}\] To see this, observe that \[\begin{align} \langle Ax, s \rangle &= \sum_{i \in [d]} y_i \sum_{x_j = 1 } A[i, j] \\ &= \sum_{x_j = 1} y_1A[1, j] + y_2 A[2, j] + \dots y_d A[d,j] \\ &= \sum_{x_j = 1} \langle y, v(z_j) \rangle \\ &= \sum_{j \; : \; x_j = 1} z_j. \end{align}\] Thus \(\langle Ax, s \rangle = t\) if and only if \(\sum_{i \; : \; x_i = 1} z_i = t\), and there is a one-to-one correspondence between solutions to our \(\mathcal{C}\)-Subset Sum instance and our HBILP feasibility instance. ◻

Proof. In polynomial time (in the size of the input), we can preprocess an instance of Subset Sum and produce an equivalent one such that all integers are bounded by \(2^{\poly(n)}\) (see, e.g.,  [35], [36]).⁷ Next, we use the reduction given in , which takes time \(\tilde{O}_\mathcal{C}(n)\) and succeeds with probability \(1 - n^{-\gamma}\), and solve the resulting HBILP instance in time \[\Delta^{O(m)} \cdot O_m(\poly(n)) = (n^{2/d(\mathcal{C})})^{O(d(\mathcal{C}))} \cdot O_\mathcal{C}(\poly(n)) = O_\mathcal{C}(\poly(n)). \qedhere\] ◻

Proof. Fix an instance of HBILP Feasibility given by the matrix \(A \in \Z^{m \times n}\), the vector \(s \in \Z^m\), and the integer target \(t\). Let \(\Delta \mathrel{\vcenter{:}}= \lVert A \rVert_\infty\).

We perform the reduction in two steps. First, we self-reduce our HBILP instance to another HBILP instance \(A', s', t'\) with the property that every column \(A'[\cdot, j]\) of \(A'\) has a unique dot product \(\langle A'[\cdot, j], s' \rangle\). We then reduce \(A', s', t'\) to \(\mathcal{C}\)-Subset Sum.

If \(A\) contains any column with only zeroes, then the value of the corresponding entry of \(x\) does not matter, and we can safely delete it. Thus we can assume without loss of generality that each column of \(A\) has at least one nonzero entry. Moreover, by , proved in , we can assume that each entry of \(A\) is non-negative and that any solution vector \(x\) has fixed support exactly \(q\) for some \(q = \Theta(n)\).

Step 1: Self-reduction. In order to construct the instance \(A', s', t'\), define \(M \mathrel{\vcenter{:}}= nm\Delta \lVert s \rVert_\infty + 1\), which satisfies \[\label{eq:M-lb} M > \langle Ax, s \rangle\tag{4}\] for any \(x \in \{0, 1\}^n\) by construction. Moreover, let \(k \mathrel{\vcenter{:}}= \lceil \log_\Delta(n) \rceil\).

Let \(R \in [\Delta]^{k \times n}\) be the matrix whose columns are vectors in \([0:\Delta-1]^k\) in lexicographically increasing order. Because the number of such vectors is at least \(n\), every column of \(R\) is different. Recall that \(J_{k\times n}\) denotes the \(k \times n\) matrix containing only 1’s and let \(\bar{R}\) be \(\Delta \cdot J_{k\times n}- R\).

Create the block matrix \(A' \in \Z_{\ge 0}^{ (m+k) \times 2n}\) as follows. The top-left block is \(A\), the bottom-left block is \(R\), the bottom-right block is \(\bar{R}\) and each entry in the top-right block is \(0\). Observe that every column in \(\tilde{A}\) is distinct because each column in \(R\) is distinct and no column in \(A\) is all 0’s.

Create \(s' \in \Z_{\ge 0}^{m + k}\) as follows. The first \(m\) entries of \(s'\) are \(s\), and the remaining \(k\) entries are the vector \(v = (M\Delta^0, M \Delta^1, \dots, M \Delta^{k-1})\). Finally, set \(t' \mathrel{\vcenter{:}}= t + q \Delta \lVert v \rVert_1\) to complete the reduction. \[A' \mathrel{\vcenter{:}}= \begin{pmatrix} \makebox(1.5cm,1.5cm){ A} & \vline& \makebox(1.5cm,1.5cm){\normalfont\Large\bfseries 0} \\ \hline \makebox(1.5cm,0.5cm){R} & \vline& \makebox(1.5cm,0.5cm){\bar{R}} \end{pmatrix} \smallskip \,\,\, s' \mathrel{\vcenter{:}}= \begin{pmatrix} \makebox(1.5cm,1.5cm){ s } \\ \hline \makebox(1.7cm,0.5cm){v} \\ \end{pmatrix}\]

Proof:Begin with the first \(n\) columns. For all \(i \in [n]\), we can break down the relevant dot product into two pieces corresponding to the top and bottom portions of \(A'\): \[\langle A'[\cdot, i], s' \rangle = \langle A[\cdot, i], s \rangle + \langle R[\cdot, i] \cdot v \rangle.\]

First, observe that \(\langle R[\cdot, i], v \rangle\) is distinct for every \(i \in [n]\) by construction, due to the fact that each component of \(R[\cdot, i]\) is less than \(\Delta\), and the components of \(v\) increase by factors of \(\Delta\).

Second, because \[0 < \langle A[\cdot, i], s\rangle \leq M,\] the \(\langle A[\cdot, i], s\rangle\) term of the dot product \(\langle A'[\cdot, i], s'\rangle\) is not large enough to interfere with the \(\langle R[\cdot, i], v \rangle\) term, and thus the first \(n\) columns of \(A'\) have distinct dot products with \(s'\).

Because \(\bar{R} = \Delta \cdot J_{k \times n} - R\), and because no column of \(A\) consists of all \(0\)’s by assumption, similar arguments show that the value \(\langle A'[\cdot, i], s' \rangle\) is distinct for every column \(i \in [2n]\). \(\blacksquare\)

Proof:Suppose \(x\) satisfies \(\langle Ax, s \rangle = t\). Recall that \(x\) has support exactly \(q\) by without loss of generality. Thus the vector \(x'\) created by concatenating two copies of \(x\) satisfies \[\langle A'x', s' \rangle = t + q \Delta \lVert v \rVert_1 = t'.\] Moreover, any vector \(y' \in \{0,1\}^{2n}\) that satisfies \(\langle A'y', s' \rangle = t'\) must satisfy \[\langle A(y'_1, y'_2, \dots, y'_n), s \rangle = t\] by construction. This is because the \([R \mid \bar{R}]\) submatrix of \(A'\) can contribute to \(t'\) only in multiples of \(M\), so because \(\langle A(y'_1, y'_2, \dots, y'_n), s \rangle < M\) by 4 , this product must evaluate to \(t\). \(\blacksquare\)

Step 2: Reduction to \(\mathcal{C}\)-Subset Sum. Consider the integer vector \[\label{eq:z-def} z \mathrel{\vcenter{:}}= (\langle s', A'[\cdot, 1] \rangle, \langle s', A'[\cdot, 2] \rangle, \dots, \langle s', A'[\cdot, 2n] \rangle)\tag{5}\] and let \[Z = \{ z_1, z_2, \dots, z_{2n} \}\] denote the set containing the components of \(z\). (Note that \(Z\) is a proper set and contains no duplicates, by .) We proceed to consider \(Z, t\) as an instance of Subset Sum.

Because \(\langle A'x, s' \rangle = t'\) if and only if \(\langle x, z \rangle = t'\) by construction 5 , we have a one-to-one correspondence between solutions to our Subset Sum and HBILP Feasibility instances: any subset of \(Z\) that adds to \(t'\) corresponds to a binary vector \(x \in \{0, 1\}^{2n}\) such that \(\langle A'x, s' \rangle = t'\), which can be used to recover a solution for the original instance \(A\), \(s\), \(t\) by . It remains to show that an \(O_\mathcal{C}(\poly(n))\) algorithm for \(\mathcal{C}\)-Subset Sum will allow us to solve the problem in the claimed time.

We begin by bounding the doubling constant \(\mathcal{C}\) of \(Z\). By the definition of \(z\), we have that \(z_j = \langle s, A'[\cdot, j] \rangle\) for all \(j \in [n]\), and thus \(Z\) is a subset of the GAP \[Y \mathrel{\vcenter{:}}= \{y_1s_1 + y_2s_2 + \dots + y_ms_m + y_{m+1}M\; : \; -\Delta \leq y_i \leq \Delta, \forall i \in [m]; 0 < y_{m+1} < \Delta^{k-1} \}.\] Note here that the dimension of \(Y\) is \(m+1\) instead of \(m+k\), as we have chosen to represent the component of each \(z_j \in Z\) divisible by \(M\) into a single large dimension.

We claim that we can assume \[\label{eq:Z-Omega-Y} |Z| = \Omega(|Y|)\tag{6}\] without loss of generality. To see this, observe that we can inflate \(|Z|\) by adding up to \(|Y|\) dummy elements from the translated GAP \(t + Y\). Because every such element is greater than \(t\), and each is contained in a translation of \(Y\), we create no additional solutions and increase \(|Y+Y|\) by at most a factor of 2.

We have that \[\begin{align} |Z + Z| &\leq |Y + Y| \\ &\leq 2^{m+1} \cdot |Y| \\ &= O_m(1) \cdot |Z|, \end{align}\] where the first line follows from the fact that \(Z \subseteq Y\), the second line follows from the fact that \(|Y|\) has dimension \(m+1\), and the third follows from 6 .

Thus \(Z, t\) is an instance of \(O_m(1)\)-Subset Sum whose solutions correspond directly to solutions of our original HBILP feasibility instance. Also, \(|Z| = O(|Y|) = \Delta^{O(m) + k}\). Because \(\Delta^k = O(n)\) by the definition of \(k\), an algorithm for Subset Sum that runs in time \(O_\mathcal{C}(\poly(n))\) solves \(Z, t\) in time \(O_m(\poly(\Delta^m \cdot n)) = \Delta^{O(m)} \cdot O_m(\poly(n))\) as claimed. ◻

Proof. We begin with a bound on the support of lexicographically minimal solutions that follows standard arguments.

Proof:Assume for contradiction that \[2^{|\supp(y)|} > (2 n \Delta+1)^m.\] Because \(Ax \leq (2n\Delta + 1)^m\) for any \(x \in \{0,1\}^n\), there must exist two different vectors \(v,w \in \{0,1\}^n\) such that (i) \(\supp(v),\supp(w) \subseteq \supp(y)\), and (ii) \(A v = A w\), by the pigeonhole principle.

Let \(y_1 = y - w + v\) and \(y_2 = y + w - v\). Observe that \(A y_1 = A y_2\) and \(y_1,y_2 \in \Z_{\geq 0}^n\) because \(\supp(v),\supp(w) \subseteq \supp(y)\). Moreover, because \(v \neq w\) we have that one of \(y_1\) or \(y_2\) is lexicographically smaller than \(y\), which contradicts the assumption that \(y\) is lexicographically minimal. \(\blacksquare\)

Let \(\mathcal{X} \subseteq \{0,1\}^n\) be the set of lexicographically minimal solutions to \(Ax = b\) for every \(b \in \Z_{\geq 0}^n\) with \(\lVert b \rVert_\infty < n\Delta\). Clearly, \(|\mathcal{X}| \le (2n\Delta + 1)^m\) as this is the number of suitable \(b\)’s. To construct \(\mathcal{X}\) it remains to iterate over every \(b \in \Z_{\geq 0}^n\) with \(\lVert b \rVert_\infty < n\Delta\) and solve the following Integer Linear Program: \[\max \left\{ \sum_{i=1}^n x_i \cdot M^i \mid Ax = b, x \in \Z_{\geq 0}^n\right\},\] where \(M = 4n\Delta\). Note that this can be solved in \((n\Delta)^{O(m)}\) time by [6] for each \(b\). Hence, the set \(\mathcal{X}\) can be constructed in the claimed time. Finally, it remains to show that for any feasible \(b\), there exists a solution \(y\) with small support in \(\mathcal{X}\).

Proof:Let \(z \in \Z_{\geq 0}^n\) be the lexicographically minimum vector such that \(Az = b\). Let \(\hat{z} \in \{0,1\}^n\) be such that \(\hat{z}_i = 1\) iff \(z_i \neq 0\) and \(\hat{z}_i=0\) otherwise. Let \(\hat{b}\) be such that \(A\hat{z} = \hat{b}\). Observe that \(\lVert \hat{b} \rVert_\infty < n\Delta\).

Hence it remains to show that \(\hat{z}\) is the lexicographically minimal vector for which \(A\hat{z} = \hat{b}\). Assume for contradiction that there exists \(\hat{y} \in \Z_{\geq 0}^n\) such that \(A \hat{y} = \hat{b}\) and \(\hat{y}\) is lexicographically smaller than \(\hat{z}\). Consider a vector \(y = z - \hat{z} + \hat{y}\). Note, that \(\supp(\hat{z}) \subseteq \supp(z)\) so \(y \in \Z_{\geq 0}^n\). Clearly \(Ay = Az = b\). Moreover, because \(\hat{y}\) is lexicographically smaller than \(\hat{z}\), it follows that \(y\) is lexicographically smaller than \(z\). This contradicts our assumption that \(z\) is lexicographically minimal. \(\blacksquare\) Thus the set \(\mathcal{X}\) satisfies the property stated in , concluding the proof. ◻

Proof. Following the steps of our reduction from \(\mathcal{C}\)-Subset Sum to HBILP feasibility (), we can use the constructive Freiman’s theorem⁸ () to encode the \(\mathcal{C}\)-Unbounded Subset Sum instance as an Unbounded Hyperplane-Constrained ILP Feasibility instance given by \(A \in \Z_{\geq 0}^{d(\mathcal{C}) \times n}\) with \(\Delta = \lVert A \rVert_\infty = n^{O(1 / d(\mathcal{C}))}\), step vector \(\ell\), and target \(t\).

We then use  to construct a set \(\mathcal{X}\) of candidate supports in \((n\Delta)^{O(m)} = n^{O_\mathcal{C}(1)}\) time. For each support vector \(x^* \in \mathcal{X}\), we reduce the ILP to variables in \(x^*\). This gives us a program with \(|x^*| = O(m \log_2(n\Delta)) = O_{\mathcal{C}}(\log(n))\) variables. Now, we encode this problem as the ILP \[\left\{x \in \Z_{\geq 0}^n \; \middle| \; \sum_{j=1}^d \ell_j \sum_{i \in x^*} a_{i,j} x_i = t \right\}.\]

Observe that this is equivalent to an instance of Unbounded Subset Sum with \(O_\mathcal{C}(\log(n))\) items. Thus any algorithm for Unbounded Subset Sum (or, more generally, any algorithm for unbounded ILP) that runs in time \(2^{O(v)}\) on instances with \(v\) variables would automatically yield an \(n^{O_\mathcal{C}(1)}\) time algorithm for \(\mathcal{C}\)-Unbounded Subset Sum. Using the best-known algorithm for unbounded ILPs, which runs in time \((\log{v})^{O(v)}\) [3], we get an \(n^{O_\mathcal{C}(1) \log\log\log(n)}\)-time algorithm. ◻

Proof. Let \(X\) be an integer set of size \(n\), and let \(\{x_1,\ldots,x_k\} \subseteq X\) denote a set of \(k\) integers that sum to \(t\). We commence by constructing the family \(\mathcal{P}\) from  and guessing a partition \((X_1,\ldots,X_k) \in \mathcal{P}\) of \(X\) such that \(x_i \in X_i\) for all \(i \in [k]\). Observe that by  this incurs only an additional \(2^{O(k)} \log(n)\) factor in the running time.

Now, we use the sparse convolution algorithm of Bringmann et al. [31].

We use  to enumerate two sets: \[\begin{align} \mathcal{L} \mathrel{\vcenter{:}}= X_1 + \ldots + X_{ \lfloor k/2 \rfloor} &&\text{ and } && \mathcal{R} \mathrel{\vcenter{:}}= X_{ \lfloor k/2 \rfloor+1} + \ldots + X_k. \end{align}\]

Both \(\mathcal{L}\) and \(\mathcal{R}\) can be computed deterministically in \(\tilde{O}(k \cdot (|\mathcal{L}| + |\mathcal{R}|))\) time by repeatedly applying . Next, with both \(\mathcal{L}\) and \(\mathcal{R}\) in hand, we apply the meet-in-the-middle approach to recover a solution if one exists. This can be implemented in \(\tilde{O}(|\mathcal{L}| + |\mathcal{R}|)\) time by first sorting \(\mathcal{L}\) and \(\mathcal{R}\), and then for every element \(a \in \mathcal{L}\) using binary search to decide if \(t-a \in \mathcal{R}\). Finally, if for at least one \(a \in \mathcal{L}\) we find an accompanying element in \(\mathcal{R}\), we know that the instance has a solution.

As stated, the algorithm decides \(k\)-SUM without recovering a solution. However, given that a solution exists we can recover a solution via binary search at the cost of an additional \(O_k(\log(n))\) factor. This concludes the description of the algorithm.

Correctness of the algorithm follows from the fact that  returns a valid partition, and from the definition of the sets \(\mathcal{L}\) and \(\mathcal{R}\). It remains to bound the runtime. Since the other steps of the algorithm take time \(\tilde{O}_k(n)\), the bottleneck occurs in the meet-in-the-middle step, which takes time \(\tilde{O}_k(|\mathcal{L}| + |\mathcal{R}|)\). Therefore it remains to bound the sizes of \(\mathcal{L}\) and \(\mathcal{R}\). Without loss of generality, consider \(|\mathcal{R}|\), and observe \[|\mathcal{R}| = |X_1 + \ldots + X_{ \lceil k/2 \rceil}| \leq | \lceil k/2 \rceil X| = \mathcal{C}^{ \lceil k/2 \rceil} |X|,\] where the final step applies Plünnecke-Ruzsa (). This concludes the proof of . ◻

Proof. The upper bound follows by analysis of the proof of . Recall that the bottleneck is \(|\mathcal{R}|\), which in the case when \(k=4\) is \(|X+X| \le \mathcal{C}\cdot |X|\).

For the lower bound, observe that \(|X+X| \le |X|^2\) and therefore \(\mathcal{C}\le |X|\). Thus, any algorithm for \((\mathcal{C}, 4)\)-SUM with runtime \(O( \mathcal{C}^{1-\epsilon} n)\) would yield an algorithm for \(4\)-SUM that runs in \(O(n^{2 - \epsilon})\) time. ◻

Proof. Fix any prime \(q > \max(sA - sA)\). As \(|\max(sA - sA)| \leq s\Delta\), we can find a prime of this size with high probability in time \(O_s(\polylog(\Delta))\) by repeatedly guessing and testing primality [45].

For each value \(\lambda \in [q]\), let \(\phi_\lambda\) denote the map \(\phi_\lambda: \Z \rightarrow \Z_q \rightarrow \Z_q \rightarrow \Z\) that

1. first maps \(a \in \Z\) to \(a' = a \pmod{q} \in \Z_q\),

2. computes \(a'' = \lambda a'\) in \(\Z_q\),

3. then maps \(a''\) back to \([0:q-1] \subset \Z\) via the identity map.

Choose \(\boldsymbol{\lambda} \in [q - 1]\) uniformly at random. Since \(q\) is prime, any element \(r \in [q-1]\) is a generator for \(\Z_q\), and thus for any \(r \in [q-1]\), \(\phi_{\boldsymbol{\lambda}}(r)\) is uniformly distributed over \([q-1]\). Since \(q > \max(sA - sA)\), for any nonzero integer \(c \in sA - sA\), \(c \in [q-1]\) and thus \(\phi_{\boldsymbol{\lambda}}(c)\) is uniformly random over \([q-1]\).

Thus for any nonzero \(c \in sA - sA\) the probability that \(\phi_{\boldsymbol{\lambda}}(c)\) is divisible by \(m\) is less than \(2/m\). As \(m = 4\mathcal{C}^{2s} n \geq 4|sA - sA|\) by , \(|sA - sA| \leq m/4\) and the probability that \(m\) evenly divides any nonzero element in \(sA - sA\) is less than \(1/2\) by a union bound. Compute \(\phi_{\boldsymbol{\lambda}}(A)\) in time \(O(n)\) and output “failure” if \(m\) divides any element in this set. Otherwise, continue.

Let \(A'\) be a subset of \(A\) such that \(|A'| \geq n / s\) and \(\mathrm{diam}(\phi_{\boldsymbol{\lambda}}(A')) \leq q / s\). Note that the existence of \(A'\) is guaranteed by the pigeonhole principle. We can compute \(A'\) in time \(O(n)\) by partitioning \([q]\) into evenly-sized intervals and computing \(\phi_{\boldsymbol{\lambda}}(A)\).

Finally, we define \(\psi_{\boldsymbol{\lambda}}: \Z \rightarrow \Z_m\) by \(\psi_{\boldsymbol{\lambda}}(x) = \phi_{\boldsymbol{\lambda}}(x) \pmod{m}\) and observe that \(\psi_{\boldsymbol{\lambda}}\) is a \(s\)-isomorphism from \(A'\) to \(\psi_{\boldsymbol{\lambda}}(A')\) as \(m\) does not divide any nonzero element in \(sA - sA\). This follows from the final two paragraphs of the proof of Theorem 7.7.3 in [33], with the argument unchanged. ◻

Proof. To make Bogolyubov’s lemma in \(\Z_m\) [33] constructive, it suffices to observe that \(R\) is defined explicitly as \[R = \{ r \in \Z_m \setminus \{0\} \; : \; |\hat{\mathbb{1}_B}(r)| > \alpha^{3/2}\}.\] Here \(\hat{\mathbb{1}_B}\) is the finite group Fourier transform of \(\mathbb{1}_B\), the membership function of \(B\): \[\hat{\mathbb{1}_B}(r) = \frac{1}{m} \sum_{x \in \Z_m} \mathbb{1}_B(x) e^{-\frac{2\pi i r x}{m}}.\] Computing \(R\) directly using the Fast Fourier Transform takes time \(O(m \log m)\). ◻

Proof. Let \(R = \{r_1, r_2, \dots, r_d\}\) be a subset of \(\Z_m\) (recall that \(m\) is a prime). We can directly compute the vector \(v = (\frac{r_1}{m}, \dots, \frac{r_d}{m}) \in \mathbb{R}^d\) to define the lattice \[\Lambda = \Z^d + \Z v \subseteq \mathbb{R}^d.\] Note that the lattice vectors are not necessarily integral, and we have not yet computed a lattice basis; letting \(e_i\) denote the standard basis vector in dimension \(i\), the set \(\{e_1, e_2, \dots, e_d, v\}\) spans the lattice but is not linearly independent.

Let \(r'\) be any nonzero element of \(R\). Since \(\Z_m\) is a cyclic group of prime order, \(r'\) generates \(\Z_m\). Thus, because one component of \(v\) is \(r' / m\), the translations of the integer lattice \(\{\Z^d + \gamma v\}_{\gamma \in [m]}\) are all disjoint. Since \[\Lambda = \Z^d + \Z v \subseteq \bigcup_{\gamma \in [m]} \Z^d + \gamma v,\] we have that \(\Lambda\) is the disjoint union of \(m\) translates of the integer lattice. This implies that there are exactly \(m\) lattice points of \(\Lambda\) within each translation of the unit cube, and, equivalently, that \(\det(\Lambda) = 1/m\).

As a result, we can enumerate the set \[C \mathrel{\vcenter{:}}= \{ \lVert \gamma r / m \rVert_{\R \setminus \Z} \; : \; \gamma \in [m]\} - \{0,1\}^d,\] the set of all \(2^d \cdot m\) lattice points in the cube \(\Lambda \cap [-1, 1)^d\), in time \(O(2^d \cdot m) = O_d(m)\).

Next, we sort the set \(C\) according to the \(L_\infty\) metric, which takes time \(\tilde{O}_d(m)\). This coincides with our definition of the successive minima of a cube centered on the origin with respect to \(\Lambda\): if \(\lambda_i\) is the \(i\)th successive minima of \([-\epsilon, \epsilon]^d\) with respect to \(\Lambda\), then the \(i\)th directional basis vector satisfies \(\lVert b_i \rVert_\infty \leq \lambda_i [-\epsilon, \epsilon]^d\).

Construct the successive minima \(\lambda_1, \dots, \lambda_d\) and the directional basis \(b_1, \dots, b_d\) of \([-\epsilon, \epsilon]^d\) with respect to \(\Lambda\) by greedily adding independent lattice vectors to our basis from short to long according to the \(L_\infty\) metric. Checking whether each subsequent lattice vector is independent from the previous set takes time \(O_d(1)\) using Gaussian elimination. Because \([-1, 1)^d\) contains \(d\) linearly independent lattice vectors (consider the standard basis), our directional basis is guaranteed to be contained in \(\Lambda \cap [-1, 1)^d = C\).

To complete the construction of the GAP in [33], we observe that the proper GAP \(P\) is defined explicitly in terms of the directional basis of \([-\epsilon, \epsilon]^d\) with respect to \(\Lambda\) that we have just constructed. Specifically, we have \[P = \{ \ell_1 x_1 + \cdots + \ell_d x_d \; | \; \forall i \in [d], \ell_i \in [L_i] \},\] where each \(x_i\) is the unique element in \([0:m-1]\) such that \(b_i \in x_i v + \Z^d\) and \(L_i \mathrel{\vcenter{:}}= \lceil 1/(\lambda_i d)\rceil\). Each \(L_i\) can be computed directly, and each \(x_i\) can be computed in time \(O(m)\). ◻

Proof. Combining the ingredients from the previous subsections allows us to prove . Let \(A\) be a finite integer set with \(|A+A| \leq \mathcal{C}|A| = \mathcal{C}n\). By , \(|8A - 8A| \leq \mathcal{C}^{16} |A|\).

Choose a prime \(m = O_\mathcal{C}(n)\) satisfying \(4 \mathcal{C}^{16} n < m < 16 \mathcal{C}^{16} n\), which can be accomplished in time \(O_\mathcal{C}(\polylog(n))\) with high probability by guessing and testing primality [45]. Then, apply with \(s = 8\) to compute a set \(A' \subseteq A\) with \(|A'| \geq |A| / 8\) and a mapping \(\psi\) such that \(\psi\) is a Freiman 8-isomorphism from \(A'\) to \(B \mathrel{\vcenter{:}}= \psi(A') \subseteq \Z_m\) with probability at least \(1/2\) in time \(\tilde{O}(n)\). We can increase the success probability of this step by repetition: for any integer constant \(\gamma > 0\), running the algorithm \(\gamma \log(n)\) times lowers the failure probability to \(n^{-\gamma}\).

Apply to \(B\) with \[\alpha = \frac{|B|}{m} = \frac{|A'|}{m} \geq \frac{|A|}{8m} = 1 / O_\mathcal{C}(1).\] This gives us \(R \subseteq \Z_m\) of size \(1 / \alpha^2 = O_\mathcal{C}(1)\) such that \(Bohr(R, 1/4) \subseteq 2B - 2B\) in time \(\tilde{O}(m) = \tilde{O}(n)\). Then, apply to \(R\) to compute the proper GAP \(P \subset Bohr(R, \epsilon) \subseteq 2B-2B\) with dimension at most \(|R| = O_\mathcal{C}(1)\) and volume at least \((1/4|R|)^{|R|} m = m / O_\mathcal{C}(1)\).

Following the proof of Theorem 7.11.1 (Freiman’s Theorem) in [33], we have that \(Q \mathrel{\vcenter{:}}= \psi^{-1}(P)\) is a GAP of the same dimension and volume satisfying \[\label{eq:QA1} Q \subseteq 2A' - 2A' \subseteq 2A - 2A.\tag{7}\] Thus \[|Q + A| \leq |2A - 2A + A| = |3A - 2A| \leq \mathcal{C}^5 |A| = O_\mathcal{C}(1) \cdot |Q|,\] where the second inequality uses . Using the fact that \(|Q+A| = O_\mathcal{C}(1) \cdot |Q|\), we apply to \(Q\) and \(A\) to get a set \(X\) of size \(|X| = O_\mathcal{C}(1)\) satisfying \(A \subseteq Q - Q + X\) in time \[\tilde{O}(\mathcal{C}|Q - Q + A|) = \tilde{O}(\mathcal{C}|2A - 2A - (2A - 2A) + A|) = \tilde{O}(\mathcal{C}|5A - 4A|) = \tilde{O}(\mathcal{C}^9|A|),\] where the final equality uses . We conclude with the observation that \(Q - Q + X\) is a GAP of dimension \(O_\mathcal{C}(1)\) and volume \(O_\mathcal{C}(1) \cdot |Q| = O_\mathcal{C}(1) \cdot |A|\), containing \(A\). Note that each step in the proof takes \(\tilde{O}_\mathcal{C}(n)\) time. ◻

Proof. Suppose \(L_i > n^{1/d(\mathcal{C})}\) for some \(i \in [d(\mathcal{C})]\), and let \(\alpha_i \mathrel{\vcenter{:}}= \alpha_i(\mathcal{C})\) be the solution to \(L_i \leq n^{\alpha_i/d(\mathcal{C})}\). (Note that \(\alpha_i = O_\mathcal{C}(1)\), as \(|A| = O_\mathcal{C}(n)\).)

Let \(\hat{\alpha}_i \mathrel{\vcenter{:}}= \alpha_i - \lfloor \alpha_i \rfloor\) denote the decimal part of \(\alpha_i\), and observe that \[\begin{align} &\{y_i\ell_i : \ell_i \in [L_i]\} \subseteq \\ &\{y_{i,1}\ell_{i, 1} + \dots +y_{i,\lfloor \alpha_i \rfloor}\ell_{i, \lfloor \alpha_i \rfloor} + y_{i,\lceil \alpha_i \rceil}\ell_{i, \lceil \alpha_i \rceil} \; : \; \forall j \in [\lfloor \alpha_i \rfloor], \ell_{i, j} \in [\lceil L_i^{1/d(\mathcal{C})} \rceil], \ell_{i, \lceil \alpha_i \rceil} \in [n^{\hat{\alpha}_i/d(\mathcal{C})}]\}, \end{align}\] where \(y_{i, j} = y_i \lceil L_i^{1/d(\mathcal{C})} \rceil^{j-1}\) for \(j \in [\lceil \alpha_i \rceil]\); that is, we can replace one dimension of our arithmetic progression with \(\lceil\alpha_i\rceil\) new dimensions, each bounded by \(n^{1/d(\mathcal{C})}\). As \[vol(P) = \prod_{i \in [d]} L_i = O_\mathcal{C}(n)\] by , performing this operation for each \(L_i > n^{1/d(\mathcal{C})}\) results in a new gap \(P'\) with dimension \(d'(\mathcal{C}) \leq 2d(\mathcal{C})\) and volume \(O_\mathcal{C}(n)\). ◻

Proof. Construct a new constraint matrix \(\tilde{A}\) as follows: Recall that \(J_{m\times n}\) denotes the \(m\) by \(n\) matrix of 1’s, and add \(\Delta \cdot J_{m\times n}\) to the matrix \(A\). Then we append an additional \(n\) columns to \(A\), where each column consists only of \(\Delta\) entries only. Finally, we append a row of 1’s.

To create \(\tilde{b}\), add \(n\Delta \cdot J_{m \times 1}\) to \(b\) and append a single entry with the value \(n\). \[\tilde{A} \mathrel{\vcenter{:}}= \begin{pmatrix} \makebox(2.5cm,1.5cm){ A + \Delta \cdot J_{m \times n}} & \vline& \makebox(2.5cm,1.5cm){\Delta \cdot J_{m \times n}} \\ \hline \makebox(1.5cm,0.5cm){ J_{1 \times n}} & \vline& \makebox(1.5cm,0.5cm){ J_{1 \times n}} \end{pmatrix} \smallskip \,\,\, \tilde{b} \mathrel{\vcenter{:}}= \begin{pmatrix} \makebox(2.3cm,1.5cm){ b + n\Delta \cdot J_{m \times 1}} \\ \hline \makebox(1cm,0.5cm){n} \\ \end{pmatrix}\]

Observe that every entry in \(\tilde{A}\) is positive and that the maximum entry in \(\tilde{A}\) is at most \(2\Delta = O(\Delta)\). For correctness, note that the last row ensures that any solution to \(\tilde{A} x = \tilde{b}\) with \(x \in \{0,1\}^{2n}\) has support exactly \(n\). This implies that the additional \(\Delta\) factors added to every component in each of the first \(m\) rows add a total of \(n\Delta\) to each component of \(Ax\). Thus \(\tilde{A}x = \tilde{b}\) if and only if \(Ax = b\). ◻

Proof. Given \(A, s, t\), we create a new HBILP feasibility instance \(\tilde{A}, \tilde{s}, \tilde{t}\) as follows. Recall that \(J_{m \times n}\) denotes the \(m\) by \(n\) matrix of 1’s and add \(\Delta \cdot J_{m \times n}\) to \(A\). Then append the matrix \(\Delta \cdot J_{m\times n}\) to the right-hand side \(A\). Finally, add a row of 1’s to the bottom of the matrix.

Define \[M \mathrel{\vcenter{:}}= \lVert s \rVert_\infty \cdot 3n\Delta m,\] and note that, by construction, we have \[\label{eq:M-lb-HBILP} \langle (A + 2 \Delta J_{m \times n})x, s \rangle \leq 3n\Delta \langle J_{m \times 1}, s \rangle < M.\tag{8}\] Create \(\tilde{s} \in \Z^{m+1}\) by appending \(M\) to \(s\), and set \(\tilde{t} = t + n\Delta \lVert s \rVert_1 + nM\). Written as block matrices, we have:

\[\tilde{A} \mathrel{\vcenter{:}}= \begin{pmatrix} \makebox(2.5cm,1.5cm){ A + \Delta \cdot J_{m \times n}} & \vline& \makebox(2.5cm,1.5cm){\Delta \cdot J_{m \times n}} \\ \hline \makebox(1.5cm,0.5cm){ J_{1 \times n}} & \vline& \makebox(1.5cm,0.5cm){ J_{1 \times n}} \end{pmatrix} \smallskip \,\,\, \tilde{s} \mathrel{\vcenter{:}}= \begin{pmatrix} \makebox(2.3cm,1.5cm){ s } \\ \hline \makebox(1cm,0.5cm){M} \\ \end{pmatrix}\]

Observe that every entry in \(\tilde{A}\) is positive and that the maximum entry in \(\tilde{A}\) is at most \(2\Delta = O(\Delta)\). Because the top \(m\) rows of \(\tilde{A}\) contribute a total value less than \(M\) to the dot product \(\langle \tilde{A}x, \tilde{s} \rangle\) by 8 , any solution to \(\tilde{A}, \tilde{s}, \tilde{t}\) must have support exactly \(n\) so that the resulting dot product contains the term \(nM\).

It remains to prove correctness:

Proof:Suppose some vector \(y' \in \{0, 1\}^n\) satisfies \(\langle Ay', s \rangle = t\). Then the vector \(y\) created by adding an arbitrary \(n\)-bit string with support \(n - \supp(y')\) satisfies \[\langle \tilde{A}x', \tilde{s} \rangle = \tilde{t}\] and is a valid solution to \(\tilde{A}, \tilde{s}, \tilde{t}\).

Now suppose some vector \(y \in \{0, 1\}^{2n}\) satisfies \(\langle \tilde{A}y, \tilde{s} \rangle = \tilde{t}\). As previously noted, we must have \(\supp(y) = n\) to create the \(nM\) term in the product \(\langle \tilde{A}y, \tilde{s} \rangle\). The additional \(\Delta\) factors added to every component in each of the first \(m\) rows of \(\tilde{A}\) create the \(n \Delta ||s||_1\) term in the product. If we remove these two terms, the remainder of the equation \(\langle \tilde{A}y, \tilde{s} \rangle = \tilde{t}\) is \(\langle A(y'_1, y'_2, \dots, y'_n), s \rangle = t\). \(\blacksquare\)

This concludes the proof of . ◻

Proof of . Fix an instance \(A \in \Z^{m \times n}, b \in \Z^n\) of Binary ILP Feasibility with \(\Delta \mathrel{\vcenter{:}}= \lVert A \rVert_\infty\). By , we can assume without loss of generality that the entries of \(A\) are non-negative.

Define \(q \mathrel{\vcenter{:}}= q(n, \Delta) = n\Delta + 1\) and create a new instance \(A, s, t'\) of HBILP feasibility by setting \[\begin{align} s &\mathrel{\vcenter{:}}= (q^0, q^1, \dots, q^{m-1}) \text{ and } \\ t' &\mathrel{\vcenter{:}}= \langle b, s \rangle = b_1 \cdot q^0 + b_2 \cdot q^1 + \dots + b_m \cdot q^{m-1}, \end{align}\] effectively using \(t'\) to store \(m\) registers of \(\log_2(q) = \log_2(n\Delta+1)\) bits each.

We claim \(x \in \{0,1\}^n\) solves \(A, b\) if and only if it solves \(A, s, t'\). If \(Ax = b\), \(\langle Ax, s \rangle = t'\) follows immediately from the definition of \(t'\).

Now suppose \(\langle Ax, s \rangle = t'\). Because \(q > A[i, \cdot]x\) for any row \(i \in [m]\) by construction, the only way to achieve \(t'\) is if \(A[i, \cdot]x = b_i\) for each \(i \in [m]\). ◻