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