October 2019 - mathfun@mailman.xmission.com

[math-fun] Quasirandomness question
by James Propp 04 Oct '19

04 Oct '19

Define a bit-guessing algorithm to be any algorithm that, given a finite string of bits as input, predict what the next bit will be; define the bit-guessing game as an adversarial game in which Player A chooses a bit-guessing algorithm, Player B chooses an infinite sequence of bits, and the score is the asymptotic density (maybe I should say upper density or lower density?) of the set of n’s for which A’s algorithm correctly predicts B’s nth bit. Question: If Player B is given complete knowledge of the innards of a million bit-guessing algorithms, can B construct an infinite sequence of bits whose score lies between .49 and .51 for *all* of those algorithms? Of course by “a million” I mean “n”, and by .49 and .51 I mean one-half plus epsilon and one-half minus epsilon, with suitable quantifiers. I want a (nonrandom) construction, not an existence proof. We’ll allow B to consult an oracle that will answer questions about those million bit-guessing algorithms (e.g., the oracle will reveal the truth-status of the Riemann Hypothesis if that’s germane). This is probably an old problem, but I’m not sure how to search for it. Jim Propp

6 9

[math-fun] Adversary B: "Okay, Let's Play!"
by Brad Klee 04 Oct '19

04 Oct '19

Here are 100 terms from three related binary sequences: S1R: 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 . . . S1X: 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 . . . S2: 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1 . . . Quick search suggests not in the OEIS. Obviously there are more ones than zeros (Hint 1: asymptotically the ratio should be 2:1). The win condition for any Adversary A is one next-term algorithm, which correctly predicts any one of the three sequences up to 10^6 terms, with at least 95% accuracy. Though, a stronger win would be to predict all future terms with 100% accuracy. Hint 2 : https://0x0.st/zwP2.png Hint 3 : Hilbert Kurve + Lebesgue Courbe = ? ? ? ? Cheers --Brad

1 1

Re: [math-fun] Quasirandomness question
by Keith F. Lynch 04 Oct '19

04 Oct '19

James Propp <jamespropp(a)gmail.com> wrote: > Question: If Player B is given complete knowledge of the innards > of a million bit-guessing algorithms, can B construct an infinite > sequence of bits whose score lies between .49 and .51 for *all* of > those algorithms? Certainly. I assume that the square roots of the primes, in binary, to the right of the radix point, are normal ("random") and uncorrelated. If so, consider some subset of the first k primes. B hashes (exclusive-ors) the digit sequences (to the right of the radix point) of the square roots of those primes together to generate the bit sequence. If k is 20, there will be about a million possible algorithms, so A can probably find the correct one (asuming A only tries algorithms in this set). But if k is much more than 20, A doesn't stand a chance. > Of course by ?a million? I mean ?n?, and by .49 and .51 I mean > one-half plus epsilon and one-half minus epsilon, with suitable > quantifiers. How large can n be? If k is more than a thousand, converting all mass in the universe into computers and running them all in parallel until the heat death of the universe wouldn't suffice to find B's algorithm. Of course there will be a chance just slightly less than 1/2 that two completely uncorrelated finite bit strings (e.g. A's and B's, if A is clueless) will match slightly more than half the time, but in the long run the proportion of matches will bounce between slightly more than 1/2 and slightly less than 1/2. Regardless of B's algorithm, so long as it produces the same number of 0s and 1s on average, I think it very unlikely that the asymptotic proportion of matches could be anything but 1/2 or 1. > We?ll allow B to consult an oracle that will answer questions about > those million bit-guessing algorithms (e.g., the oracle will reveal > the truth-status of the Riemann Hypothesis if that?s germane). If I understand you correctly, B comes up with an algorithm to generate an unending sequence of bits, and A tries to guess the algorithm so as to generate the same sequence (the same other than some finite number of mismatched bits at the beginning before A guesses the correct algorithm, I mean). As such, I don't understand the point in the oracle. If B simply asks the oracle for a complete list of every algorithm A will try, that would make B's already easy task even easier.

1 0

[math-fun] The Burning Ship fractal
by Allan Wechsler 03 Oct '19

03 Oct '19

There is a relatively famous fractal, called the Burning Ship fractal, which is usually presented as an analogue of some sort to the Mandelbrot set. The Mandelbrot set has two definitions. Both define a parameterized function f[c](z) = z^2 + c (over the complex numbers). One definition is that M is the set of all c such that the Julia set J(f[c]) is connected. The other is that it is the set of all c such that the sequence of iterates of f[c] starting with 0 does not converge to infinity. It is a theorem, and not a super easy theorem, that both definitions produce the same set. That is, that J(f[c]) is connected precisely when the 0-origin iteration sequence of f[c] converges to infinity. Call these the "connectedness definition" and the "convergence definition". The Burning Ship fractal is defined by substituting a different parameterized function, g[c](z), which doesn't have a simple formula because it isn't even analytic -- that is, it takes z apart into its real and imaginary parts, does some stuff to them, and then puts them back together. You can look up the rule on Wikipedia. The Burning Ship fractal is defined using convergence only, with no attention paid, apparently, to the question of whether the connectedness definition yields the same fractal -- that is, whether the theorem linking connectedness and convergence is even true of g, as it is of f. I have a strong intuition that it's not. Has anybody investigated what the connectedness-analog fractal generated by g looks like?

1 0

[math-fun] "Win Stephen Wolfram's Money"
by James Propp 02 Oct '19

02 Oct '19

https://rule30prize.org https://writings.stephenwolfram.com/2019/10/announcing-the-rule-30-prizes

5 10

[math-fun] Fwd: the Rule 30 Prizes are launched!
by Bill Gosper 02 Oct '19

02 Oct '19

---------- Forwarded message --------- From: Stephen Wolfram <s.wolfram(a)wolfram.com> Date: Tue, Oct 1, 2019 at 11:03 AM Subject: the Rule 30 Prizes are launched! To: Bill Gosper <billgosper(a)gmail.com> https://rule30prize.org https://writings.stephenwolfram.com/2019/10/announcing-the-rule-30-prizes Thank you for being part of the Prize Committee. Now let’s see if we have to wait for months, years or decades for anything to happen :) Thanks again. --- Stephen P.S. Please let me know if there are people / mailing lists / etc. who should be told about the prizes ... or (even better) let them yourself!

1 0

Re: [math-fun] Who has written a clear summary of what research mathematicians do?
by Steve Witham 01 Oct '19

01 Oct '19

Scott Kim wrote-- > I think it's an occupational hazard of being an > expert in any field, not just math, that it can be hard to explain what you > do to an outsider. Nonetheless I think it's important to do, and not just > for outsiders, but also for people inside the field. At least it's > important to me Â— the dearth of mathematicians talking about what > mathematics is I find intolerable, and makes me distrustful of mathematics > as a field. Ted Nelson's _Computer Lib_ (1974) for me was a taste of what the good thing can be: An enthusiastic insider in a field who is also a skeptical outsider without missing a beat. There's the public-facing importance of that (especially with something commercial like computers), but also I like the way I oriented myself after reading that book. Stewart Brand, Martin Gardner, Aubrey de Grey, Vi Hart. https://youtu.be/v-pyuaThp-c "Doodling in Math Class: Connecting Dots" (talk about not missing beats) --Steve

3 2

[math-fun] Happy 103rd birthday!
by ed pegg 01 Oct '19

01 Oct '19

One of our subscribers turns 103 today.

3 2