Home /  Analytic Number Theory Seminar: The sieve of Eratosthenes in less space

Seminar

Analytic Number Theory Seminar: The sieve of Eratosthenes in less space February 16, 2017 (02:00 PM PST - 03:00 PM PST)
Parent Program:
Location: SLMath: Eisenbud Auditorium
Speaker(s) Harald Helfgott (Georg-August-Universität zu Göttingen)
Description No Description
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Video
No Video Uploaded
Abstract/Media

We will show how to carry out a sieve of Erastosthenes up to $N$ in space $O(N^{1/3})$ and essentially linear time. This improves over the usual versions, which take space about $O(\sqrt{N})$ and essentially linear time.  The algorithm -- which, like the one in (Galway, 2000), is ultimately related to diophantine approximation -- can also be used to factorize integers $n$, and thus to give the values of arithmetical functions such as the M\"obius function $\mu$ and the Liouville function $\lambda$ for all integers up to $N$.

No Notes/Supplements Uploaded No Video Files Uploaded