Approximation of Complex Numbers by Cyclotomic Integers

TitleApproximation of Complex Numbers by Cyclotomic Integers
Publication TypeTechnical Report
Year of Publication1996
AuthorsM. Shokrollahi, A., & Stemann V.
Other Numbers1043
Keywordscomplex approximation, cyclotomic fields, cyclotomic units, Discrete Fourier tranform, integer linear programming

We present a new method of approximating complex numbers by cyclotomic integers in Z[e^{2?i/2^n}] whose coefficients with respect to the basis given by powers of e^{2?i/2^n} are bounded in absolute value by a given integer M. It has been suggested by Cozzens and Finkelstein that such approximations reduce the dynamic range requirements of the discrete Fourier transform. For fixed n our algorithm gives approximations with an error of O(1/M^{2^{n-2}-1}). This proves a heuristic formula of Cozzens and Finkelstein. We will also prove a matching lower bound for the worst case error of any approximation algorithm and hence show that our algorithm is essentially optimal. Further, we derive a slightly different and more efficient algorithm for approximation by 16th roots of unity. The basic ingredients of our algorithm are the explicit Galois theory of cyclotomic fields as well as cyclotomic units. We use a deep number theoretic property of these units related to the class number of the field. Various examples and running times for this case and that of approximation by 32nd roots of unity are included. Finally, we derive the algebraic and analytic foundations for the generalization of our results to arbitrary algebraic number fields.

Bibliographic Notes

ICSI Technical Report TR-96-033

Abbreviated Authors

M. A. Shokrollahi and V. Stemann

ICSI Publication Type

Technical Report