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

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Realz Slaw
    Sep 6, 2012 at 15:37
  • $\begingroup$ An interesting similar problem is the Merkle–Hellman knapsack cryptosystem, which can be solved with LLL as shown here. $\endgroup$
    – Realz Slaw
    Sep 6, 2012 at 15:42
  • $\begingroup$ I am beginning to think the question is equivalent to the knapsack problem. $\endgroup$
    – Realz Slaw
    Sep 6, 2012 at 17:00
0
$\begingroup$

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!

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .