       Re: Re: Re: algebraic numbers

• To: mathgroup at smc.vnet.net
• Subject: [mg106077] Re: [mg106054] Re: [mg106011] Re: [mg105989] algebraic numbers
• From: danl at wolfram.com
• Date: Fri, 1 Jan 2010 05:32:25 -0500 (EST)
• References: <200912290620.BAA02732@smc.vnet.net>

```> "If so, you will indeed have recognized the number x as algebraic, from
> its first N figures."
>
> No... you will have identified an algebraic number that agrees with x, to
> N figures.
>
> OTOH, every computer Real is rational, so they're all algebraic.
>
> Bobby

I'm not intending to argue with anyone here, but I wanted to elaborate a
bit on what had been a quick remark. To some people this may well be
familiar.

There is a long history of studying integer relations amongst approximate
reals. It is regarded as a generalization of continued fractions, among
other things. Anyway, based on the question posed, I'm pretty sure this
type of relation finding is what the original poster was seeking.

The fact that approximate numbers are arbitrarily close to, well, anything
nearby (all of which, except a measure zero set, being transcendental), is
sorta obvious, and also largely irrelevant. What matters is that there are
good number-theoretic (and really also measure theoretic) bounds that show
"random" numbers cannot be too close to algebraic numbers once one places
bounds on degree and coefficient size. Recognizing "good' algebraic number
approximants has its uses. I would say that lattice reduction is to
computational math what NSAIDs (aspirin et al) are to pain relief.

For reference, check fork by Helaman Ferguson. Look for his older work, on
an algorithm called PSLQ; his more recent work is in sculpture. Also see
the Lenstra, Lenstra, Lovasz paper that introduced lattice reduction
(known as LLL, for obvious reasons).

Daniel Lichtblau
Wolfram Research

> On Thu, 31 Dec 2009 02:17:22 -0600, Robert Coquereaux
> <robert.coquereaux at gmail.com> wrote:
>
>> "Impossible....Not at all"
>> I think that one should be more precise:
>> Assume that x algebraic, and suppose you know (only) its first 50
>> digits. Then consider y = x +  Pi/10^100.
>> Clearly x and y have the same first 50 digits , though y is not
>> algebraic.
>> Therefore you cannot recognize y as algebraic from its first 50 digits !
>> The quoted comment was in relation with the question first asked by
>> hautot.
>> Now, it is clear that, while looking for a solution x of  some
>> equation (or definite integral or...), one can use the answer obtained
>> by applying  RootApproximant (or another function based on similar
>> algorithms) to numerical approximations of x, and then show that the
>> suggested algebraic number indeed solves exactly the initial problem.
>> If so, you will indeed have recognized the number x as algebraic, from
>> its first N figures.
>> But this does not seem to be the question first asked by hautot.
>> Also, if one is able to obtain information, for any N, on the first N
>> digits of a real number x, this is a different story... and a
>> different question.
>>
>> Le 30 d=E9c. 2009 =E0 18:11, Daniel Lichtblau a =E9crit :
>>
>>>
>>>> To recognize a number x as algebraic, from its N first figures, is
>>>> impossible.
>>>
>>> Not at all. There are polynomial factorization algorithms based on
>>> this notion (maybe you knew that).
>>>
>>> Daniel Lichtblau
>>> Wolfram Research
>>
>>
>
>
> --
> DrMajorBob at yahoo.com
>

```

• Prev by Date: Re: sampling a spline
• Next by Date: Re: Re: Replace and ReplaceAll -- simple application
• Previous by thread: Re: algebraic numbers
• Next by thread: Re: Re: algebraic numbers