Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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!

share|improve this answer
    
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$. –  Realz Slaw Sep 5 '12 at 17:19
    
$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. –  Robert Israel Sep 5 '12 at 17:22
    
@RobertIsrael yes, that is why I felt they were equivalent. Thank you for making this point. –  Realz Slaw Sep 5 '12 at 17:23
    
Fixed the problems, thanks guys. I got my $a_i$s and $x_i$s mixed up :) –  Clive Newstead Sep 5 '12 at 17:24
    
@CliveNewstead I think my counter example still applies, can you try plugging in those numbers? –  Realz Slaw Sep 5 '12 at 17:26

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

share|improve this answer
    
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. –  Realz Slaw Sep 6 '12 at 15:37
    
An interesting similar problem is the Merkle–Hellman knapsack cryptosystem, which can be solved with LLL as shown here. –  Realz Slaw Sep 6 '12 at 15:42
    
I am beginning to think the question is equivalent to the knapsack problem. –  Realz Slaw Sep 6 '12 at 17:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.