I too spent time in the 70's tinkering with a naive algorithm for this problem --- just around the time that LLL came along and blew my pedestrian notions clean out of the water! I didn't know about the 1989 paper --- has it proposals less artificial to apply than LLL, which was in an essential sense discrete (for lattice basis minimisation, in the course of factoring polynomials over a finite field)? Despite trying the idea many times, I have to confess I have never actually discovered a new relation in this manner. Has anybody else out there had better luck? WFL On 9/16/08, victor miller <victorsmiller@gmail.com> wrote:
On Tue, Sep 16, 2008 at 12:13 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Christian writes:
<< Let f(x , x , ..., x ) = k x + k x + ... + k x 1 2 n 1 1 2 2 n n
where k , k , ..., k are n REAL constants 1 2 n
and x , x , ..., x are n INTEGERS (positive or negative) 1 2 n
If we try to have the best possible approximations of
f(x , x , ... x ) = 0 1 2 n
do you know good algorithms giving best values of (x , x , ..., x )?
Assume x_j = 0 for all j is not true.
Let K and X be the n-dim vectors of real constants and unknown integers, respectively. Then we want to find X so that <K,X> = 0 as near as possible.
The set of all values G := {<K,X> : X in Z^n}
is a subgroup of the reals, so it's either discrete or dense. The discrete case is easy to handle, and only occurs for measure 0 among possible vectors K in R^n. Otherwise the set
G* := {<K,X> : X in Z^n - {0}}
contains elements arbitrarily close to 0, so there is no "best" value of X.
That's true, but one can ask for what the best value of X is given that all elements of X are bounded in absolute value by H. There is an algorithm due to Hastad, Just, Lagarias and Schnorr that is designed to answer the posed question. When looked at the right way it's very close to the L^3 lattice reduction algorithm.
Victor
Here's the reference:
# Polynomial time algorithms for finding integer relations among real numbers , J. Hastad, B. Just, J. C. Lagarias and C. P. Schnorr, SIAM J. Computing 18 (1989), pp. 859-881. [Preliminary version in: STACS '86 , Lecture Notes in Computer Science No. 210, Springer-Verlag: New York 1986, pp. 105-118.]
I'll leave finding "good" values of X to the number theorists, once "good" is defined.
--Dan
_____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun