[PAPER] "Pi is in Log Space" by Chee Yap

[abetusk]

Paper

"Pi is in Log Space" by Chee Yap (link)

Overview

Bailey, Borwein and Plouffe (BBP) discovered a "spigot algorithm" [1] for the digits of Pi. The spigot algorithm computes the n'th digit of Pi in time poly(log(n)) (that is, the n'th digit of Pi can be computed in something like O(log^k(n)) time, for some integer k) but in the BBP paper, they did not adequately bound some rounding issues to guarantee polynomial time complexity.

Yap closes this issue and proves that any number that has some "BBP-like" series and that have bounded irrationality measure can have it's n'th digits be computed in O(log|n|) time.

[1] "On the rapid computation of various polylogarithmic constants" By David Baily, Peter Borwein, and Simon Plouffe (link)

When to Meet

Anytime, though after 7pm EST on weekdays is preferable for me.

Preconditions for participation

None, though a background in algorithms, number theory and analysis is probably going to be helpful.

Goals

• Understand the main argument of the proof and gain familiarity with the tools used

Stretch Goals

• Implement a spigot algorithm that provably converges to Pi as proposed by Yap

Communication Channels

IRC is preferred but I'm open to suggestions.

Tools to Communicate

Overleaf I guess? I've never used it but some collaborative environment where we can write Latex.

[zx9w]

I've never read a paper like this but it's interesting! I can do after 7pm EST tomorrow and the day after as well as Thursday next week.

[abetusk]

Can we try for Thursday 7pm EST next week (2020-05-21)?

Maybe we can create an IRC channel, maybe something that's logged as well?

It's probably good to try and get a shared Latex pad to work on. Do you have any suggestions on that?

[zx9w]

Can we try for Thursday 7pm EST next week (2020-05-21)?

Sure, I made this PR with a skeleton of a skeleton of a meeting format as a starting point:

https://github.com/zx9w/read-together/pull/5

Maybe we can create an IRC channel, maybe something that's logged as well?

Sounds good, it's easy to make a channel on freenode. We can follow pie_'s example and just name the channel as the acronym of the paper.

If you want a log then the simplest solution is just to keep using github as a forum (unless freenode offers that as well? idk).

It's probably good to try and get a shared Latex pad to work on. Do you have any suggestions on that?

CodiMD is a pretty nice platform, I included a link in the readme I added.

[abetusk]

hm, I'm not sure I did this as intended. There was a branch which I edited on a fork and issued a PR with some additions.

At any rate, I'm on the #readtogether channel on IRC with a logging bot attached. If we need voice we can figure it out. The CoMID seems like a good platform for math notes so I kept that (and just cleaned up the link) which we can export after we're done.

[abetusk]

PR sent with logs and scratch space we used for investigation.

If you want to continue with reading this paper, let me know what a good time is for you.

If anyone is lurking, feel free to jump in.