Pi, the Primes, Periodicities, and Probability

Abstract

The theory of numbers has repeatedly shown itself to be both practical and beautiful. This paper gives an example of this duality. We present a very efficient (and practical) algorithm for extracting the fundamental period from a set of sparse and noisy observations of a periodic process. The procedure is computationally straightforward, stable with respect to noise, and converges quickly. Its use is justified by a theorem, which shows that for a set of randomly chosen positive integers, the probability that they do not all share a common prime factor approaches one quickly as the cardinality of the set increases. The proof of this theorem rests on a (beautiful) probabilistic interpretation of the Riemann zeta function.

Additional information

Notes on contributors

Stephen D. Casey

STEPHEN D. CASEY received his B.A. from Drew University and his Ph.D. from the University of Maryland-College Park. He currently teaches at American University in Washington, DC. He is active in the classroom, and has won five teaching awards. His research interests are in complex and harmonic analysis with applications to signal and image processing, and he serves on the editorial boards of Sampling Theory in Signal and Image Processing and the Journal of Signal and Image Processing. Steve and his wife Becky have seven children. With what little free time they have, they enjoy hiking, boating, and playing tennis.

Brian M. Sadler

BRIAN M. SADLER received his B.S. and M.S. from the University of Maryland-College Park and his Ph.D. from the University of Virginia-Charlottesville, all in electrical engineering. He is currently a fellow of the Army Research Laboratory in Adelphi, MD. His research interests are in signal and information processing. He is a Fellow of the IEEE and he has served on the editorial board of several journals. Brian and his wife Laurel have two daughters. With what little free time they have, they enjoy cooking and watching their girls dance.