A new, improved bound on the density

The main result of this note is an improvement in the maximum density of subset sum problems which can ``almost always'' be solved:

Theorem.   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$ be arbitrary, and let $s = \sum_{i=1}^n e_ia_i$. If the density $d < 0.9408\ldots{}$, then the subset sum problem defined by $a_1,\ldots{},a_n$ and s may ``almost always'' be solved in polynomial time with a single call to a lattice oracle.

Proof. We need to make only minor changes to the proof presented in Section 2. As above, A is a fixed positive integer and $a_1,\ldots{},a_n$ are 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$ be fixed, let $s = \sum_{i=1}^n e_ia_i$, and let $t= \sum_{i=1}^n a_i$. Vectors $\mathbf{b_1},\ldots{},\mathbf{b_n}$ are defined as in Section 2. Vector b_n+1 is replaced, however, by

$$\mathbf{b_{n+1}'} = (\tfrac{1}{2},\tfrac{1}{2},\ldots{},\tfrac{1}{2},Ns).$$

Let L' be the lattice spanned by the vectors $\mathbf{b_1},\ldots{},\mathbf{b_n},\mathbf{b_{n+1}'}$.

In Section 2, we knew that the vector $\mathbf{\hat{e}}=(e_1,\ldots{},e_n,0)$ was in the lattice L. Notice that the new lattice L' does not contain $\mathbf{\hat{e}}$ but instead contains the vector $\mathbf{\hat{e}'}$:

$$\mathbf{\hat{e}'} = (e_1',\ldots{},e_n',0), \quad\text{where } e_i' = e_i-\tfrac{1}{2}~.$$

Since $e_i \in \{0,1\}$ for $1 \leq i \leq n$, we know that $e_i' \in \{-\tfrac{1}{2},\tfrac{1}{2}\}$ for $1 \leq i \leq n$. Notice that $\Vert\mathbf{\hat{e}'}\Vert^2 \leq \tfrac{1}{4}n$ independent of the number of e_i's which are equal to 1.

Again, we are interested in the number of vectors $\mathbf{\hat{x}}$ which satisfy conditions similar to Equation 4:

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

Setting $N > \tfrac{1}{2}\sqrt{n}$ implies that x_n+1 = 0 for any $\mathbf{\hat{x}}$ which satisfies Equation 12. Suppose that $\mathbf{\hat{x}} = \sum_{i=1}^n y_i\mathbf{b_i} + y\mathbf{b_{n+1}'}$ satisfies Equation 12, then we can express x_i in terms of y_i and y in the following way
$$\begin{align*}x_i & = y_i + \tfrac{1}{2}y, \quad\text{for } 1\leq i \leq n, \\ 0 = x_{n+1} & = N \cdot \left\{\sum_{i=1}^n a_iy_i + ys\right\}. \end{align*}$$
This implies that

$$\sum_{i=1}^n a_iy_i = -ys.$$

Therefore, Equation 6 can be replaced by:

$$\sum_{i=1}^n x_ia_i = \tfrac{1}{2}y(t-2s),$$ (11)

since $(\sum_{i=1}^n \mathbf{b_i}) - 2\mathbf{b_{n+1}'} = (0,0,\ldots{},0,N(t-2s))$.

We now establish a bound on the size of |y|. From above,
 $$\begin{align}\vert y(t-2s)\vert & = 2 \left\vert \sum_{i=1}^n x_ia_i \right\vert... ...ha \sqrt{n}, \quad\text{where } \alpha = \max_{1 \leq i \leq n} a_i. \end{align}$$
If $\vert t-2s\vert \geq \tfrac{1}{2}\alpha$, then $\vert y\vert\vert t-2s\vert \geq \vert y\vert\alpha$, and

$$\vert y\vert \leq 2n\sqrt{n},$$ (12)

by Equation 14. If $\vert t-2s\vert < \tfrac{1}{2}\alpha$, then we can solve two problems: one where $\alpha$ is assumed to be part of the subset which sums to s, and one where $\alpha$ is assumed to be part of the subset which sums to t-s. In the first case, the new problem has $s' = s-\alpha, t'=t-\alpha$, and

$$\vert t'-2s'\vert = \vert t-\alpha-2s+2\alpha\vert = \vert t-2s+\alpha\vert \geq \tfrac{1}{2}\alpha.$$ (13)

For the second case, the new problem has $s' = s, t'=t-\alpha$, and

$$\vert t'-2s'\vert = \vert t-2s-\alpha\vert \geq \tfrac{1}{2}\alpha.$$ (14)

Thus we may always assume $\vert t-2s\vert \geq \tfrac{1}{2}\alpha$ and that the bound in Equation 15 holds.

We may now calculate the bound on probability P that there exists a vector $\mathbf{\hat{x}}$ which satisfies Equation 12. We now let $\mathbf{x} = (x_1,\ldots{},x_n)$ be any vector such that $2 \; \mathbf{x} \in {\mathbb Z}^n$. We obtain the following bound, similar to Equation 10:

$$P \leq \Pr\left(\sum_{i=1}^n a_ix_i = \tfrac{1}{2}y(t-2s)\rig... ...\sqrt{n}\right\}\right\vert \cdot n \left(4n\sqrt{n}+1\right).$$ (15)

As in Section 2, $\Pr(\sum_{i=1}^n a_ix_i = \tfrac{1}{2}y(t-2s)) \leq 1/A$. To estimate the number of vectors x with $\Vert\mathbf{x}\Vert \leq \tfrac{1}{2}\sqrt{n}$, we again use the technique in [12,15], but in a more complicated way. The number of x with $\Vert\mathbf{x}\Vert \leq \sqrt{n}/2$ is bounded above by
 $$\begin{multline}\left\vert\left\{\mathbf{w} = \left( w_1,\ldots{},w_n \right) \c... ...tfrac{1}{2})\Vert \leq \tfrac{1}{2} \sqrt{n} \right\}\right\vert. \end{multline}$$
In [15] it is shown that for n sufficiently large, the second summand in Equation 19 above is smaller than the first summand by a factor that is exponential in n. In any case, the second summand equals 2ⁿ. By the method of [12,15], the first summand is bounded, for every u > 0, by

$$2^{(\log_2 e)\delta(u)n},$$

where

$$\delta(u) = \tfrac{1}{4}u + \ln \theta(e^{-u}), \quad\text{for } \theta(z)= 1+ 2\sum_{k=1}^\infty z^{k^2}.$$

Numerically, we may calculate the minimum value of $\delta(u)$, and obtain

Thus, any subset sum problem with density $d < 1/c_0' = 0.9408\ldots{}$may be solved in polynomial time, given the existence of a lattice oracle.    $\blacksquare$