algebraic numbers
in [Mathematica]
|
Prev: FindInstance Problem
Next: Persistent assumption
From: danl on 1 Jan 2010 05:32 > "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(a)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(a)yahoo.com >
From: Noqsi on 1 Jan 2010 05:32 On Dec 31, 1:16 am, DrMajorBob <btre...(a)austin.rr.com> wrote: > This is a little like those idiotic SAT and GRE questions that ask "What's > the next number in the following series?"... where any number will do. > Test writers don't seem to know there's an interpolating polynomial (for > instance) to fit the given series with ANY next element. Explanations in terms of epicycles may be mathematically adequate in a narrow sense, but an explanation in terms of a single principle applied repeatedly is to be preferred in science. The ability to recognize such a principle is important. And my mathematical logician son (who's looking over my shoulder) directed me to http://www.research.att.com/~njas/sequences/ for research on this topic. When he encounters such a sequence in his research, he finds that knowledge of a simple genesis for the sequence can lead to further insight.
From: DrMajorBob on 1 Jan 2010 05:36 "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 On Thu, 31 Dec 2009 02:17:22 -0600, Robert Coquereaux <robert.coquereaux(a)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(a)yahoo.com
From: DrMajorBob on 2 Jan 2010 05:05 When I clicked on the link below, the search field was already filled with the sequence target = {1, 2, 3, 6, 11, 23, 47, 106, 235}; Searching yielded "A000055 Number of trees with n unlabeled nodes." I tried a few Mathematica functions on it: FindLinearRecurrence(a)target FindLinearRecurrence[{1, 2, 3, 6, 11, 23, 47, 106, 235}] (fail) FindSequenceFunction(a)target FindSequenceFunction[{1, 2, 3, 6, 11, 23, 47, 106, 235}] (fail) f[x_] = InterpolatingPolynomial[target, x] 1 + (1 + (1/ 3 + (-(1/ 12) + (7/ 120 + (-(1/ 60) + (1/144 - (41 (-8 + x))/20160) (-7 + x)) (-6 + x)) (-5 + x)) (-4 + x)) (-3 + x) (-2 + x)) (-1 + x) and now the next term: Array[f, 1 + Length(a)target] {1, 2, 3, 6, 11, 23, 47, 106, 235, 322} But, unsurprisingly, the next term in A000055 is 551, not 322. A000055 actually starts with another three 1s, but that doesn't change things much: target = {1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235}; FindLinearRecurrence(a)target FindLinearRecurrence[{1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235}] (fail) FindSequenceFunction(a)target FindSequenceFunction[{1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235}] (fail) f[x_] = InterpolatingPolynomial[target, x] 1 + (1/24 + (-(1/ 40) + (1/ 90 + (-(1/ 280) + (1/ 1008 + (-(43/ 181440) + (191/3628800 - (437 (-11 + x))/ 39916800) (-10 + x)) (-9 + x)) (-8 + x)) (-7 + x)) (-6 + x)) (-5 + x)) (-4 + x) (-3 + x) (-2 + x) (-1 + x) Array[f, 1 + Length(a)target] {1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, -502} So I ask you, from the data alone: what's the next term? If one had the Encyclopedia of Integer Sequences handy, those SAT questions could be interesting. But they'd still be nonsense. Bobby On Fri, 01 Jan 2010 04:32:58 -0600, Noqsi <jpd(a)noqsi.com> wrote: > On Dec 31, 1:16 am, DrMajorBob <btre...(a)austin.rr.com> wrote: > >> This is a little like those idiotic SAT and GRE questions that ask >> "What's >> the next number in the following series?"... where any number will do. >> Test writers don't seem to know there's an interpolating polynomial (for >> instance) to fit the given series with ANY next element. > > Explanations in terms of epicycles may be mathematically adequate in a > narrow sense, but an explanation in terms of a single principle > applied repeatedly is to be preferred in science. The ability to > recognize such a principle is important. > > And my mathematical logician son (who's looking over my shoulder) > directed me to http://www.research.att.com/~njas/sequences/ for > research on this topic. When he encounters such a sequence in his > research, he finds that knowledge of a simple genesis for the sequence > can lead to further insight. > -- DrMajorBob(a)yahoo.com
From: Andrzej Kozlowski on 2 Jan 2010 05:07
On 1 Jan 2010, at 20:41, Andrzej Kozlowski wrote: > > On 1 Jan 2010, at 19:36, DrMajorBob wrote: > >> "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 > > Well, actually Mathematica does not agree with your last assertion: > > Head[1.12] > > Real > > Element[1.12, Rationals] > > False > > Element[1.12, Reals] > > True > > In fact it seems clear that the designers of Mathematica have decided to interpret all approximate numbers (with head Real) as approximations to irrationals rather than as finite expansions of rationals. The only rationals in Mathematica are indeed the ones that have the head Rational, i.e. fractions. > > Andrzej Kozlowski > > I forgot to add why I think this is justified. Note that the function RandomReal[] 0.691808 Returns an approximate number between 0 and 1. This is supposed to represent a real number from the interval between 0 and 1 returned by a random variable with uniform distribution. But clearly as the rationals are a set of measure 0, such a number ought always to be an irrational. Thus it is natural to regard all approximate reals as (approximations to) irrationals. I don't think this is an issue of any real importance but I think the seemingly strange looking behaviour of Element is mathematically well justified. Andrzej Kozlowski |