WFL> 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!
Here is an ancient Lisp algorithm, invoked from Macsyma, telephoned ca. 1970 by Rich to Robert Maas, finding quartics for pi. It works mod 1, so there's no pi^0 term. The left column is the matrix row being printed, the 2nd column is the error, the third is the vector, the 4th is its norm, and the fifth is a figure of merit approximating the number of excess digits of agreement. (c147) round(2^105*makelist(%pi^k,k,1,4)) (d147)[127438138015862315638027235646471, 400358718177795200392018112753682, 1257764007827987814231061425713179, 3951382166942061712360453895340836] (c148) load("c:\\rwg\\climax\\munlsp.lsp")$ (c149) ?lsp("(user::precinit 105)") (d149) 72.7804 (c150) ?lsp("(user::linrel (cdr $d147))") Init of numrel has finished okay [0, 0.40909, [0, 0, 0, 1], 1, -1.77018285868794d0] [0, 0.00628, [0, 0, 1, 0], 1, 0.04390718722343d0] [0, 0.00136, [-1, -1, 2, 0], 6, 0.40674400805398d0] [0, 4.30503e-4, [-1, 2, -1, 1], 7, 0.85547926831103d0] [0, 7.30684e-5, [3, 5, 0, 3], 43, 0.67148385803703d0] [0, 9.54798e-6, [-6, 0, 5, 2], 65, 1.25846167486465d0] [0, 1.27879e-6, [-7, -12, 10, -4], 309, 0.88290059041933d0] [0, 3.62128e-7, [-18, -16, -6, -11], 737, 0.69333326841885d0] [0, 1.82782e-8, [-22, 13, -23, -5], 1207, 1.56677297182571d0] [0, 1.92441e-9, [33, 12, 48, -1], 3538, 1.61548864677868d0] This is Jim's monic quartic. But we can easily make monics by rubbing together pairs from the hereinafter. [0, 5.50442e-10, [68, 51, -11, 76], 13122, 1.02256306683229d0] [0, 1.3231e-11, [58, -28, 29, -159], 30270, 1.9160654198039d0] [0, 8.25957e-13, [-102, 154, -18, -84], 41500, 2.84671402663485d0] [0, 2.38296e-13, [-530, 10, -647, -131], 716770, 0.91211003918297d0] [0, 2.69997e-14, [741, 497, -525, -838], 1773959, 1.07075195229049d0] [0, 8.85595e-16, [-568, -561, -2006, 645], 5077406, 1.64147564053187d0] ... (c160) (makelist(%pi^k,k,1,4),[ [58, -28, 29, -159].%%,%%. [68, 51, -11, 76]])$ (c161) bfloat(%,33) (d161) [ - 1.46829999999999867690017321923245b4, 7.77900000000055043781524460966016b3] (c162) cfexpand(cf(159/76)) 159 23 (d162) ( ) 76 11 (c163) expand(d160.[11,23]) (d163) - pi^4 + 66 * pi^3 + 865 * pi^2 + 2202 * pi (c164) dfloat(%) (d164) 17404.0000000128d0
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
Sure, that's how I find those valuations of eta'(e^-(pi n/d)). And I think it's how Simon found his nth-bit-of-pi series. And although they're not new, it's the easiest way to simplify products of gammas of rationals. (Look for relations among the logs.) And here's a neat anecdote: Maas was doing adaptive data compression and needed to solve y-2 3-2y 1-y y 1-x x x-3 (1-x) x (1-y) y = 1 = (1-x) x (1-y) y . Curious whether the roots were algebraically independent, we fed them to Rich's recognizer and they turned out to be independently algebraic! Cubics, in fact, which we were then able to exhibit by rubbing the transcendentals together. I need also to nag that the powerseries analog of this process is a great way to uncover functional relationships. E.g., to find the ODE for Bessel_J[3], (c165) sqfr(tlinrel(makelist(('diff(bessel_j[3](z),z,k), %%=taylor(apply_nouns(%%),z,0,17)),k,0,2))) (d165) 2 2 d d 5971968000 (z (--- (bessel_j (z))) + z (-- (bessel_j (z))) 2 3 dz 3 dz 2 13 + (z - 9) bessel_j (z))/z = 0 3 where 17 is any sufficiently large degree, whose size does not affect the answer. (Not even that z^13.) With a little more trouble, one can find the ODE for Bessel_J[n].
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun