[math-fun] An irrational number normal to every radix simultaneously
An irrational number normal to every radix simultaneously It seems to me it is possible to write down a computer program which will output the binary bits of such a number, one by one, with at most polynomial(N) time to output the Nth bit. Essentially, the program keeps track of the counts of digits in radix B (among digits "up to the present location") for all B=2,3,...,F(N), which is order F(N)^2 counts in all. (And note, radix 4 and 8 take care of 2- and 3-tuples in radix 2, etc.) The program chooses the pattern for the next lg(N) bits "greedily" from among the N possibilities to maximize some likelihood measure of "normality up to now." Here F(N) is a sufficiently-slow-growing monotonically-increasing-to-infinity continuous positive-valued function of N, for example lg(N)^(1/4) should be fine. Apparently Alan Turing claimed to have solved essentially this problem, using an approach which sounds vaguely similar, in an unpublished manuscript which was eventually printed in his collected works. He must have solved it before world war II. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
While I think that is very likely to work, I think it requires proof. Sometimes you'll find yourself "stuck"; in the next iteration, you can't improve normality for both base 47 and base 83. So you let one of these get slightly worse. It could happen so often that you have to do this that things stay bad forever in one base or another; fixing the base that's currently furthest from normal better makes two other bad ones worse. While this seems exceedingly unlikely, I think there's something that needs to be proved to show it doesn't happen. Of course the much simpler probabilistic computer program that outputs the binary digits at random produces a number that is normal in all bases with probability 1. Andy On Fri, Aug 14, 2015 at 2:03 PM, Warren D Smith <warren.wds@gmail.com> wrote:
An irrational number normal to every radix simultaneously
It seems to me it is possible to write down a computer program which will output the binary bits of such a number, one by one, with at most polynomial(N) time to output the Nth bit.
Essentially, the program keeps track of the counts of digits in radix B (among digits "up to the present location") for all B=2,3,...,F(N), which is order F(N)^2 counts in all. (And note, radix 4 and 8 take care of 2- and 3-tuples in radix 2, etc.) The program chooses the pattern for the next lg(N) bits "greedily" from among the N possibilities to maximize some likelihood measure of "normality up to now."
Here F(N) is a sufficiently-slow-growing monotonically-increasing-to-infinity continuous positive-valued function of N, for example lg(N)^(1/4) should be fine.
Apparently Alan Turing claimed to have solved essentially this problem, using an approach which sounds vaguely similar, in an unpublished manuscript which was eventually printed in his collected works. He must have solved it before world war II.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
participants (2)
-
Andy Latto -
Warren D Smith