Solving a linear diophantine equation approximately

Question

Consider the following problem:

Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in standard binary representation.

Output: $\mathbf{x} \in \mathbb{Z}^n = \arg \min d( \mathbf{x}, H)$

In the above notation $d(\mathbf{x}, S)$ for $\mathbf{x} \in \mathbb{R}^n$ and $S \subseteq \mathbb{R}^n$ is defined as $d(\mathbf{x}, S) = \min_{\mathbf{y} \in S}{\|\mathbf{x} - \mathbf{y}}\|_2$, i.e. it's the natural euclidean distance between a set of points and a single point.

In words, we're given a hyperplane and we're looking for the point in the integer lattice that is closest to the hyperplane.

The question is:

What is the complexity of this problem?

Note that polynomial time here will mean polynomial in the bitsize of the input. As far as I can see the problem is interesting even in two dimensions. Then it's not hard to see that it's enough to consider only those solutions $(x_1, x_2)$ with $0\leq x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$ but that's superpolynomially many options.

A closely related problem is solving a linear diophantine equation, i.e. finding an $\mathbf{x} \in \mathbb{Z}^n$ such that $\mathbf{a}^T\mathbf{x} = b$ or determining that no such $\mathbf{x}$ exists. So, solving a linear diophantine equation is equivalent to determining whether there exists a solution of value 0 to the problem I defined above. A linear diophantine equation can be solved in polynomial time; in fact even systems of linear diophantine equations can be solved in polynomial time by computing the Smith normal form of the matrix $\mathbf{A}$ giving the system. There are polynomial time algorithms that compute the Smith normal form of an integer matrix, the first one given by Kannan and Bachem.

To get intuition about linear diophantine equations we can consider the two dimensional case again. Clearly, there is no exact solution if $\mathsf{gcd}(a_1, a_2)$ does not divide $b$. If it does divide $b$, then you can run the extended GCD algorithm to get two numbers $s$ and $t$ such that $a_1s + a_2t = \mathsf{gcd}(a_1, a_2)$ and set $x_1 = sb/\mathsf{gcd}(a_1, a_2)$ and $x_2 = tb/\mathsf{gcd}(a_1, a_2)$. Now you can see how the approximate version is different: when $\mathsf{gcd}(a_1, a_2)$ does not divide $b$, how do we find integers $x_1, x_2$ such that distance between $(x_1, x_2)$ and the line $a_1x_1 + a_2x_2 =b$ is minimized?

The problem to me sounds a little like the closest vector problem in lattices, but I do not see an obvious reduction from either problem to the other.

Answer 1

All right, having thought about it more I believe I have an explicit reduction from this problem to extended GCD; I'll explain it in the $n=2$ case, but I believe that it extends to arbitrary $n$. Note that this finds an $\mathbf{x}$ that minimizes the distance to the hyperplane, but not necessarily the smallest $\mathbf{x}$ (there are in fact infinitely many values that attain the same minimum distance) - I believe the latter problem is also feasible, but haven't given it any real thought yet. The algorithm is based on a few simple principles:

• If $g=\mathrm{GCD}(a_1, a_2)$, then the set of values taken on by $\mathbf{a}\cdot\mathbf{x} = a_1 x_1 + a_2 x_2$ is precisely $\left\{0, \pm g, \pm 2g, \pm 3g, \ldots\right\}$; furthermore, values $x_1$ and $x_2$ with $a_1 x_1 + a_2 x_2 = g$ can be found efficiently (this is exactly the extended Euclidean algorithm).
• The minimum distance from the hyperplane to a point on the lattice is the minimal distance from a point on the lattice to the hyperplane (obvious, but a useful inversion of the problem).
• The distance from a given point $\mathbf{x}$ to the hyperplane $\mathbf{a}\cdot\mathbf{y} = b$ is proportional to $\left|\mathbf{a}\cdot\mathbf{x}-b\right|$ (specifically, it's $1/|\mathbf{a}|$ times this value - but since multiplying all distances by this value has no effect on the location of the minimum, we can ignore the normalizing factor).

This suggests the following procedure:

• Compute $g=\mathrm{GCD}(a_1,a_2)$, along with $x^0_1, x^0_2$ such that $a_1x^0_1+a_2x^0_2 = g$.
• Compute $r = \left\lfloor{b\over g}\right\rfloor$ and calculate $d =\min(b-rg, (r+1)g-b)$; $d$ is the (scaled) minimal distance from the lattice to the hyperplane. Let $s$ be either $r$ or $r+1$ ($=\left\lceil{b\over g}\right\rceil$, unless $b$ is a multiple of $g$) depending on which one attains the minimal distance.
• Compute $x_1 = sx^0_1$ and $x_2 = s x^0_2$; then $\mathbf{a}\cdot\mathbf{x} = sg$ is the nearest multiple of $g$ to $b$, and thus $\left|\mathbf{a}\cdot\mathbf{x}-b\right|$ attains the minimum of this distance over all lattice points.

As far as I know, the exact same procedure should work correctly in arbitrary dimensions; the key is that the $n$-dimensional GCD still satisfies Bezout's identity, and so to find the minimum distance to a lattice point you only have to find the nearest multiple of $g$ to $b$.