On sums of roots of unity
Litow, B. (2010) On sums of roots of unity. Lecture Notes in Computer Science, 6198. pp. 420-425.
![[img]](https://researchonline.jcu.edu.au/style/images/fileicons/application_pdf.png) |
PDF (Published Version)
- Published Version
Restricted to Repository staff only |
Abstract
We make two remarks on linear forms over Z in complex roots of unity. First we show that a Liouville type lower bound on the absolute value of a nonvanishing form can be derived from the time complexity upper bound on Tarski algbera. Second we exhibit an efficient randomized algorithm for deciding whether a given form vanishes. In the special case where the periods of the roots of unity are mutually coprime, we can eliminate randomization. This efficiency is surprising given the doubly exponential smallness of the Liouville bound.
| Item ID: | 11687 |
|---|---|
| Item Type: | Article (Research - C1) |
| ISSN: | 1611-3349 |
| Additional Information: | From the proceedings of 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Part I |
| Date Deposited: | 18 Aug 2010 23:27 |
| FoR Codes: | 08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080201 Analysis of Algorithms and Complexity @ 100% |
| SEO Codes: | 89 INFORMATION AND COMMUNICATION SERVICES > 8999 Other Information and Communication Services > 899999 Information and Communication Services not elsewhere classified @ 100% |
| Downloads: |
Total: 3 |
| More Statistics |
Actions (Repository Staff Only)
 |
Item Control Page |