baez@x.ucr.edu (john baez) (02/10/90)
In article <1990Feb7.002735.8746@cadence.com> holsz@cadence.com (Wlodzimierz Holsztynski) writes: > >Just an example. Can we compress strings of bits (0-s and 1-s) of >length 100, so that on average we get less than a 1000 bits? Many >mathematicians will have a knee-jerk reaction. My knee-jerk reaction is that you made a typo and mean 100 in both cases. It's not surprising that you can map the set of 100-bit sequences 1-1 into the set of 100-or-fewer-bit sequences, since there are about twice as many of the latter. When dealing with binary expansions of arbitrary reals, things are fairly different since there are uncountably many. I really wouldn't want to say one number is more complicated than another, I would prefer to say its decimal or binary expansion is more complicated, because this is only one of many possible descriptions of the number. It has the advantage of working for all real numbers (though most are "inaccessible" since not computable), but it's certainly not the best for many purposes, like telling if they're rational. "What?" you say, "The rationals repeat and the irrationals don't". True, but one can never decide this from examination of a finite-information piece (e.g. intial segment) of a decimal expansion. If one specifies a number as the solution of an equation - which takes a finite string - one can "often" decide whether the number is rational. I say "often" with misgivings, because I don't know, for example: 1) is there a decision procedure for rationality of algebraic numbers (i.e., given a polynomial with integer coefficients, can one tell which roots are rational and which not? I flunked Galois theory :-)). If not, is there one that works for some positive density of cases??? 2) how about other presentations of numbers?
gsmith@garnet.berkeley.edu (Gene W. Smith) (02/13/90)
In article <3981@ucrmath.UCR.EDU>, baez@x.ucr (john baez) writes: >1) is there a decision procedure for rationality of >algebraic numbers (i.e., given a polynomial with >integer coefficients, can one tell which roots are >rational and which not? This is actually pretty easy. For one thing, there are good algorithms for factoring over Q(x), and for another, one can clear denominators and consider a related *monic* polynomial with integer coefficients. The roots of this will be algebraic integers, and hence rational only if rational integers. -- ucbvax!garnet!gsmith Gene Ward Smith/Brahms Gang/Berkeley CA 94720 "I am quite prepared to prove in court that I am neither stupid nor insane." quoted from ONE FOR THE BOOKS, the authorized biography of Captain Carnage.