2
$\begingroup$

My question is related to the Integer Relation Detection Problem which can be formulated as:

$a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$

Where $\forall_{a_i} a_i\in\mathbb{Z},a_i and $\exists_{a_i} a_i\neq 0$, and $\forall_{x_i} x\in \mathbb{R}$. $c$ and vector $\mathbf{x}$ are given, and the problem is to find a valid vector $\mathbf{a}$ that satisfies these constraints.

There are a few algorithms to solve this problem, listed on the wikipedia page linked.

My question: are there algorithms for a solution to the same problem with the modification that:

$a_1x_1 + a_2x_2 + \cdots + a_nx_n = 1$

Or equivalently (I believe):

$a_1x_1 + a_2x_2 + \cdots + a_nx_n = b$

$b\in \mathbb R$ is a given.

I would love to see some reduction to an existing problem with a polynomial-time algorithm, such as Integer Relation Detection, or Simultaneous Integer Relation Detection. Another possibility is that this is a hard problem.

2 Answers 2

3

Here's an example of what I meant. Suppose you want to solve (approximately) $a_1 x_1 + a_2 x_2 + a_3 x_3 = 1$ where $x_1 = .234532$, $x_2 = .876834$, $x_3 = .917409$. You take $x_4 = -1$ and give LLL the vectors $[1,0,0,0,234532], [0,1,0,0,876834], [0,0,1,0,917409], [0,0,0,1,-1000000]$. The result (in Maple 16) is $[[6, 8, -7, 2, 1], [-1, -6, -6, -11, 10], [-28, 17, -8, 1, 10], [-30, -11, -93, -102, -171]]$. The third vector $[-28, 17, -8, 1, 10]$ tells you that $-28 x_1 + 17 x_2 - 8 x_3 + x_4$ is very near $0$ (in fact is $.000010$), so $-28 x_1 + 17 x_2 - 8 x_3$ is nearly $-x_4 = 1$. However, you could also use the first and second vectors, which have $a_4 = 2$ and $-11$ respectively. Since $1 = 6 \times 2 - 11$, we take $6 [6, 8, -7, 2, 1] + [-1, -6, -6, -11, 10] = [35, 42, -48, 1, 16]$ and find that $35 x_1 + 42 x_2 - 48 x_3$ is very nearly $1$. In order to write $1$ as an integer linear combination of $2$ and $-11$, we needed the fact that $\gcd(2,-11) = 1$.

  • 0
    I am beginning to think the question is equivalent to the knapsack problem.2012-09-06
0

If $b=\dfrac{p}{q}$ with $p,q \in \mathbb{Z}$ (and $q \ne 0$) then you could solve $x_1(qa_1) + \cdots + x_n(qa_n) - a_{n+1}p = 0$ and then take the solutions of the form $(a_1, \cdots, a_n, 1)$.

If $b \in \mathbb{R}$ then you run into problems if you can only use integers; but if $b \in \mathbb{R}$ then I doubt somewhat that such an algorithm would work anyway!

  • 0
    That's not what I meant. Hopefully my answer will explain.2012-09-06