Previous results

In [12], Lagarias and Odlyzko show that if the density is bounded by $0.6463\ldots{}$, the lattice oracle is guaranteed to find the solution vector with high probability. This section derives the $0.6463\ldots{}$ bound using simpler techniques due to Frieze [7]. Our presentation differs from that of [7] in a few technical details.

Let A be a positive integer and let $a_1,\ldots{},a_n$ be random integers with $0 < a_i \leq A$ for $1 \leq i \leq n$. Let $\mathbf{e}=(e_1,\ldots{},e_n) \in \{0,1\}^n$, $\mathbf{e} \neq (0,0,\ldots{},0)$depending only on n, be fixed and let

We may assume that $s \geq t/n$, since if s < t/n any $a_i \geq t/n$cannot be in the subset, and may be removed from consideration. Similarly, $s \leq (1-(1/n))t$, otherwise any $a_i \leq (1-(1/n)) t$ may be removed from consideration. Thus,

$$\frac{1}{n} t \leq s \leq \frac{n-1}{n} t.$$ (3)

We recall the Lagarias-Odlyzko attack on low-density subset sum problems. Define the vectors $\mathbf{b_1},\ldots{},\mathbf{b_{n+1}}$ as follows:
$$\begin{align*}\mathbf{b_1} & = (1,0,\ldots{},0,Na_1), \\ \mathbf{b_2} & = (0,1,... ...0,0,\ldots{},1,Na_n), \\ \mathbf{b_{n+1}} & = (0,0,\ldots{},0,Ns), \end{align*}$$
where N is a positive integer which will be chosen later. Let L be the lattice spanned by the vectors $\mathbf{b_1},\ldots{},\mathbf{b_{n+1}}$(i.e. $L = \{ \sum_{i=1}^{n+1} z_i\mathbf{b_i} \colon z_i \in {\mathbb Z} \quad\text{for } 1 \leq i \leq n+1 \}$).

Notice that the solution vector $\mathbf{\hat{e}}=(e_1,\ldots{},e_n,0)$ is in L. Following the proof in [7] we are interested in vectors $\mathbf{\hat{x}} = (x_1,x_2,\ldots{},x_{n+1})$ which satisfy:

$$\begin{split} \Vert\mathbf{\hat{x}}\Vert & \leq \Vert\mathbf{... ... \{\mathbf{0},\mathbf{\hat{e}},\mathbf{-\hat{e}}\}. \end{split}$$ (4)

We may assume that

$$\sum_{i=1}^n e_i \leq \tfrac{1}{2}n,$$ (5)

(i.e. the subset contains at most one-half of the a_i's). If $\sum_{i=1}^n e_i > \tfrac{1}{2}n$, we may replace s by t-s, b_n+1by $\mathbf{b_{n+1}'} = (0,\ldots{},0,N(t-s))$, and $\mathbf{\hat{e}}$ by $\mathbf{\hat{e}'}=(1-e_1,1-e_2,\ldots{},1-e_n,0)$. Solving this problem is equivalent to solving the given problem, $\sum_{i=1}^n (1-e_i) \leq \tfrac{1}{2}n$, and $s' = t-s \geq t/n$. (To be fully rigorous, we actually apply the basic method to two problems, at least one of which is covered by the condition $\sum_{i=1}^n e_i \leq \tfrac{1}{2}n$, and our analysis below applies to this case.)

Choose $N > \sqrt{n}$. It is clear that $\mathbf{\hat{x}}$satisfies Equation 4 only if x_n+1 = 0. (Otherwise, $\Vert\mathbf{\hat{x}}\Vert\geq \vert x_{n+1}\vert \geq N > \sqrt{n} \geq \Vert\mathbf{\hat{e}}\Vert$, which contradicts Equation 4.) Let y be defined by

$$ys = \sum_{i=1}^n x_ia_i,$$ (6)

and deduce that

$$\vert y\vert s = \left\vert \sum_{i=1}^n x_ia_i \right\vert \... ...\vert \sum_{i=1}^n a_i \right\vert \leq t\sqrt{\tfrac{1}{2}n}.$$ (7)

Hence, using Equation 3 above,

$$\vert y\vert \leq n\sqrt{\tfrac{1}{2}n}.$$ (8)

Note that since -y is the coefficient of b_n+1 in the expansion of $\mathbf{\hat{x}}$ in terms of the basis vectors, $y \in {\mathbb Z}$.

We will show that the probability P -- that a lattice L contains a short vector which satisfies Equation 4 -- is:
 $$\begin{align}% latex2html id marker 198 P &= \Pr(\exists\ \mathbf{\hat{x}} \text... ...}+1\right)\frac{2^{c_0n}}{A}, \quad\text{for } c_0 = 1.54724\ldots{} \end{align}$$
This implies that, if A = 2^cn with c > c₀, ${\displaystyle \lim_{n\rightarrow \infty} P = 0}$. If the density of a subset sum problem is less than $0.6463\ldots{}$, then
$$\begin{align*}\frac{n}{{\displaystyle \log_2\max\begin{substack}1 \leq i \leq n\... ...ack} a_i > 2^{n/0.6463\ldots{}} \\ & \Longrightarrow A > 2^{c_0n}. \end{align*}$$
Thus, all subset sum problems with density $< 0.6463\ldots{}$ could be solved in polynomial time, given the existence of a lattice oracle.

We will now prove Equation 9. Let $\mathbf{x} = (x_1,\ldots{},x_n)$ denote an element of ${\mathbb Z}^n$. (Note that if $\mathbf{\hat{x}} = (x_1,\ldots{},x_n,0)$, then $\Vert\mathbf{\hat{x}}\Vert = \Vert\mathbf{x}\Vert$ and as a special case we have $\Vert\mathbf{\hat{e}}\Vert = \Vert\mathbf{e}\Vert.)$ First we estimate the probability P by
 $$\begin{align}P & \leq \Pr(\exists\ \mathbf{x},y \text{ s.t. } \Vert\mathbf{x}\Ve... ...rt y\vert \leq n\sqrt{\tfrac{1}{2}n} \right\}\right\vert. \end{split}\end{align}$$

We have to estimate three factors in the right side of Equation 10. For the first factor of Equation 10 we may rewrite $\sum_{i=1}^n a_ix_i = ys$ as:

$$\sum_{i=1}^n a_iz_i = 0, \quad\text{where } z_i=x_i-ye_i.$$

Since x is non-zero and $\Vert\mathbf{x}\Vert \leq \Vert \mathbf{e} \Vert$, we have $\mathbf{z}=(z_1,\ldots{},z_n) \neq \mathbf{0}$, and so we may assume without loss of generality (by increasing the bound for the probability by a factor of at most n) that $z_1 \neq 0$. If z' is defined as $-(\sum_{i=2}^n a_iz_i/z_1)$, then
$$\begin{align*}\Pr\left(\sum_{i=1}^n a_iz_i = 0\right) & = \Pr(a_1 = z'), \\ &= ... ...\\ &= \sum_{j=1}^A \frac{1}{A} \Pr(z' = j), \\ &\leq \frac{1}{A}. \end{align*}$$

Now we consider the second factor of Equation 10. From [12] (which borrowed the technique from [15]) we know that

$$\left\vert\left\{\mathbf{x} \colon \Vert\mathbf{x}\Vert \leq ... ...t\vert \leq 2^{c_0n}, \quad\text{where } c_0 = 1.54724\ldots{}$$ (9)

It is clear that the last factor of Equation 10 can be estimated by $2n\sqrt{\tfrac{1}{2}n}+1$. This proves Equation 9.