<p>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 <em>an</em> $\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:</p>

<ul>
<li>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).</li>
<li>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).</li>
<li>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).</li>
</ul>

<p>This suggests the following procedure:</p>

<ul>
<li>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$.</li>
<li>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.</li>
<li>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.</li>
</ul>

<p>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$.</p>

CC BY-SA 3.0
2012-02-02T05:43:40.403Z
2012-02-02T05:51:03.530Z
2012-02-02T05:51:03.530Z
Steven Stadnicki
<p>Consider the following problem:</p>

<p><strong>Input</strong>: 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.</p>

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

<p>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. </p>

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

<p>The question is:</p>

<blockquote>
  <p>What is the complexity of this problem?</p>
</blockquote>

<p>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.</p>

<p>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 <a href="http://planetmath.org/?method=l2h&amp;from=objects&amp;name=GausssAlgorithmForPrincipalIdealDomains&amp;op=getobj" rel="nofollow">Smith normal form</a> 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 <a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v8/i4/p499_s1?isAuthorized=no" rel="nofollow">Kannan and Bachem</a>.</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2011-12-30T08:06:52.510Z
Does [*Approximating Good Simultaneous Diophantine Approximations Is Almost NP-Hard*, C Rössner and J-P Seiffert, MFCS 96](http://dl.acm.org/citation.cfm?id=645725.667037) answer your question?
Kai
CC BY-SA 3.0
2011-12-30T10:04:39.593Z
no it does not: diophantine approximation is a different problem from solving a diophantine equation. in a diophantine approximation problem you're given $n$ real numbers and you want to multiply them *all by a single* integer $Q$ so that all of them are within $\epsilon$ from some integer. the issue there is finding the optimal tradeoff between the size of $Q$ and $\epsilon$. I do not see a relation between my problem and this one.
Sasho Nikolov
CC BY-SA 3.0
2012-02-01T19:47:05.437Z
What's your input format?  It seems as though if any two coordinate values of $\mathbf{a}$ are incommensurate then the minimum in question is zero (intersect with the appropriate 2-dimensional plane to get an equation of the form $sx+ty=w$ with $s$ and $t$ incommensurate, i.e. $\alpha \equiv \frac{s}{t}$ irrational, and then use the standard results on $\left\{n\alpha\right\}\pmod 1$ to show that the line passes arbitrarily close to lattice points.
Steven Stadnicki
CC BY-SA 3.0
2012-02-01T19:52:35.320Z
In particular, this means that your 'min' should be an 'inf' (sine you're taking it over infinitely many points), and the problem of whether $\mathrm{inf}\ d(\mathbf{x},H)=0$ is distinct from the question of whether there exists some $\mathbf{x}$ with $d(\mathbf{x},H)=0$.  This means the coefficients of $\mathbf{a}$ have to be rational numbers for the problem to have nontrivial solution, and then the problem seems to take on a very Euclidean form, closely coupled to multidimensional GCD algorithms.  Am I missing something?
Steven Stadnicki
CC BY-SA 3.0
2012-02-01T20:15:14.200Z
@StevenStadnicki right. you can assume $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ (I will add that to the question, I must have missed it). the input is given in standard binary representation. the question is interesting even when $n = 2$. then it's enough to consider all possible solutions $(x_1, x_2)$ with $x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$, but the bruteforce search will be superpolynomial in the binary representation of $a_1, a_2$.
Sasho Nikolov
CC BY-SA 3.0
2012-02-01T20:24:41.850Z
It seems like when $n=2$ the problem is precisely the extended GCD problem (i.e., finding $x_1,x_2$ with $x_1a_1+x_2a_2 = \mathrm{gcd}(a_1,a_2)$ ), but I haven't dug deeply enough to find the specific mapping there.  Regardless, that would be the first place I'd start looking...
Steven Stadnicki
CC BY-SA 3.0
2012-02-01T22:49:05.273Z
@StevenStadnicki  
the problem whether $d(\mathbf{x},H)=0$ in two dimensions is exactly extended GCD  (since there is no solution if $\mathsf{gcd}(a_1,a_2)$ doesn't divide $b$ - added that to the question). you can see the Smith normal form as a higher-dimensional generalization of this. however, when $\mathsf{gcd}(a_1,a_2)$ doesn't divide $b$, I don't see how GCD helps you minimize $d(\mathbf{x},H)$?
Sasho Nikolov
<cc.complexity-theory><optimization><linear-algebra><integer-lattice>
Solving a linear diophantine equation approximately
Sasho Nikolov
# Solving a linear diophantine equation approximately

(Asked by: username_0 on 2011-12-29)

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](http://planetmath.org/?method=l2h&from=objects&name=GausssAlgorithmForPrincipalIdealDomains&op=getobj) 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](http://epubs.siam.org/sicomp/resource/1/smjcat/v8/i4/p499_s1?isAuthorized=no).

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.

**Tags:** cc.complexity-theory, optimization, linear-algebra, integer-lattice

> **Comments:**
> **username_1**: Does [*Approximating Good Simultaneous Diophantine Approximations Is Almost NP-Hard*, C Rössner and J-P Seiffert, MFCS 96](http://dl.acm.org/citation.cfm?id=645725.667037) answer your question?  
> **username_0**: no it does not: diophantine approximation is a different problem from solving a diophantine equation. in a diophantine approximation problem you're given $n$ real numbers and you want to multiply them *all by a single* integer $Q$ so that all of them are within $\epsilon$ from some integer. the issue there is finding the optimal tradeoff between the size of $Q$ and $\epsilon$. I do not see a relation between my problem and this one.  
> **username_2**: What's your input format?  It seems as though if any two coordinate values of $\mathbf{a}$ are incommensurate then the minimum in question is zero (intersect with the appropriate 2-dimensional plane to get an equation of the form $sx+ty=w$ with $s$ and $t$ incommensurate, i.e. $\alpha \equiv \frac{s}{t}$ irrational, and then use the standard results on $\left\{n\alpha\right\}\pmod 1$ to show that the line passes arbitrarily close to lattice points.  
> **username_2**: In particular, this means that your 'min' should be an 'inf' (sine you're taking it over infinitely many points), and the problem of whether $\mathrm{inf}\ d(\mathbf{x},H)=0$ is distinct from the question of whether there exists some $\mathbf{x}$ with $d(\mathbf{x},H)=0$.  This means the coefficients of $\mathbf{a}$ have to be rational numbers for the problem to have nontrivial solution, and then the problem seems to take on a very Euclidean form, closely coupled to multidimensional GCD algorithms.  Am I missing something?  
> **username_0**: @StevenStadnicki right. you can assume $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ (I will add that to the question, I must have missed it). the input is given in standard binary representation. the question is interesting even when $n = 2$. then it's enough to consider all possible solutions $(x_1, x_2)$ with $x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$, but the bruteforce search will be superpolynomial in the binary representation of $a_1, a_2$.  
> **username_2**: It seems like when $n=2$ the problem is precisely the extended GCD problem (i.e., finding $x_1,x_2$ with $x_1a_1+x_2a_2 = \mathrm{gcd}(a_1,a_2)$ ), but I haven't dug deeply enough to find the specific mapping there.  Regardless, that would be the first place I'd start looking...  
> **username_0**: @StevenStadnicki   the problem whether $d(\mathbf{x},H)=0$ in two dimensions is exactly extended GCD  (since there is no solution if $\mathsf{gcd}(a_1,a_2)$ doesn't divide $b$ - added that to the question). you can see the Smith normal form as a higher-dimensional generalization of this. however, when $\mathsf{gcd}(a_1,a_2)$ doesn't divide $b$, I don't see how GCD helps you minimize $d(\mathbf{x},H)$?  

---

## 1 answers

### Answer by username_2 on 2012-02-02. Score: 5 | Accepted answer

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$.


---

