Ramanujan Sums in the Context of Signal Processing—Part I: Fundamentals

The famous mathematician S. Ramanujan introduced a summation in 1918, now known as the Ramanujan sum c_q(n). For any fixed integer q, this is a sequence in n with periodicity q. Ramanujan showed that many standard arithmetic functions in the theory of numbers, such as Euler´s totient function φ(n) and the Möbius function μ(n), can be expressed as linear combinations of c_q(n), 1 ≤ q ≤ ∞. In the last ten years, Ramanujan sums have aroused some interest in signal processing. There is evidence that these sums can be used to extract periodic components in discrete-time signals. The purpose of this paper and the companion paper (Part II) is to develop this theory in detail. After a brief review of the properties of Ramanujan sums, the paper introduces a subspace called the Ramanujan subspace Sq and studies its properties in detail. For fixed q, the subspace Sq includes an entire family of signals with properties similar to c_q(n). These subspaces have a simple integer basis defined in terms of the Ramanujan sum c_q(n) and its circular shifts. The projection of arbitrary signals onto these subspaces can be calculated using only integer operations. Linear combinations of signals belonging to two or more such subspaces follows certain specific periodicity patterns, which makes it easy to identify periods. In the companion paper (Part II), it is shown that arbitrary finite duration signals can be decomposed into a finite sum of orthogonal projections onto Ramanujan subspaces.