MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Update based on Michael's answer (thanks again!) - Can the LLL or PSLQ algorithms provide a (knowably - i.e. not just incidental) unique solution for the set of integer multiplicative factors? Are there other algorithms (perhaps with worse run-time complexities) that can?

Imagine that one has a set of 'n' finite-precision real numbers - (r_1, r_2, ..., r_n), each with an associated positive integer multiplicative factor, (i_1, i_2, ..., i_n). Here, one only has access to the values in the set of real numbers, as well as the sum of the real numbers multiplied by their corresponding multiplicative factors, 'S', i.e. - Sum(i_1*n_1, i_2*n_2, ..., i_n*r_n).

What's the most efficient way to test that the sum of a particular set of real numbers will (or, obviously, will not) always allow us to extract a unique solution for the set of integer multiplicative factors? Or to find/do this with fewest restrictions on the values of the integer multiplicative factors?

In the case that this has a very simple answer, apologies.

(Edit - Changed "each with an associated "set of" positive integer multiplicative factors" --> "each with an associated positive integer multiplicative factor". One finite-precision real number 'r_k' has one integer multiplicative factor 'i_k'.)

share|cite|improve this question
up vote 2 down vote accepted

You want integer relation algorithms, such as the LLL algorithm.

share|cite|improve this answer
Michael - thank you! However, from reading the description, I am not sure that the LLL or PSLQ algorithm will provide a solution that is unique? Can we insure that there is no 'lost information' for integer multiplicative factors from the summation operation? – Richard Dec 30 '09 at 2:04
I don't know; I just know the names of the algorithms, I haven't actually used them. Sorry I can't be of more help. – Michael Lugo Dec 30 '09 at 2:11

Your Answer


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.