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

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
    Ok, I understand what you are saying wrt to the gcd of the coefficients. I will restate my other question: Is it possible to force an+1 to be 1 (or equivalently −1) or use the algorithm to (eventually) spit out such a solution? What happens if all the vectors contain a zero in the $a_{n+1}$ place? I am still going through LLL to fully understand and see if it can be leveraged to accomplish a solution.2012-09-06
  • 0
    An interesting similar problem is the [Merkle–Hellman knapsack cryptosystem](http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem), which can be solved with LLL as shown [here](http://kutioo.blogspot.com/2011/12/liblll.html).2012-09-06
  • 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
    I think I have a counter example: if $x_1$ = $x_2$, then the assinment $[-1,1, 0, 0, 0, ... 0]$ would be satisfied. However, in the original, this vector would not result in $1$.2012-09-05
  • 0
    $x_1, \ldots, x_n$ are supposed to be given, $a_1, \ldots, a_n$ to be found. I think you mean solve $a_1 x_1 + \ldots + a_n x_n - a_{n+1} b = 0$ and take the solutions with $a_{n+1} = 1$. There's no reason to discriminate between rational and irrational $b$: multiply all of $x_1, \ldots, x_n, b$ by the same nonzero number and the solutions are unchanged.2012-09-05
  • 0
    @RobertIsrael yes, that is why I felt they were equivalent. Thank you for making this point.2012-09-05
  • 0
    Fixed the problems, thanks guys. I got my $a_i$s and $x_i$s mixed up :)2012-09-05
  • 0
    @CliveNewstead I think my counter example still applies, can you try plugging in those numbers?2012-09-05
  • 0
    Typically $LLL$, for example, will find several integer vectors $(a_1,\ldots, a_{n+1})$. You want to find a linear combination of them with $a_{n+1} = 1$. In order to do this, the gcd of the $a_{n+1}$ values needs to be $1$.2012-09-05
  • 0
    @RobertIsrael I don't yet fully understand $LLL$, I am reading up on it now. Is it possible to force $a_{n+1}$ to be $1$ (or equivalently $-1$) or use the algorithm to (eventually) spit out such a solution? Also, why does the gcd of "gcd of the $a_{n+1}$ values" have an effect? And by "gcd of the $a_{n+1}$ values", I assume you mean $gcd(a_{n+1},x_{n+1})$ ?2012-09-05
  • 0
    Ah, I think you mean the gcd of the vector $\mathbf a$, including the $a_{n+1}$ value. I still don't understand what effect this has.2012-09-05
  • 0
    That's not what I meant. Hopefully my answer will explain.2012-09-06