home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 13102 < prev    next >
Encoding:
Internet Message Format  |  1992-10-13  |  1.6 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!husc-news.harvard.edu!ramanujan!elkies
  2. From: elkies@ramanujan.harvard.edu (Noam Elkies)
  3. Newsgroups: sci.math
  4. Subject: Re: real exponential sums
  5. Message-ID: <1992Oct13.113705.16330@husc3.harvard.edu>
  6. Date: 13 Oct 92 15:37:04 GMT
  7. Article-I.D.: husc3.1992Oct13.113705.16330
  8. References: <1behulINNm4e@uwm.edu>
  9. Distribution: world
  10. Organization: Harvard Math Department
  11. Lines: 24
  12. Nntp-Posting-Host: ramanujan.harvard.edu
  13.  
  14. In article <1behulINNm4e@uwm.edu> litow@csd4.csd.uwm.edu
  15. (bruce e litow) writes:
  16. >Let a_k = exp(k/N) where 0 <= k < N and let S1 and S2 be two sums
  17. >over two disjoint subsets of the a_k. By Lindemann's Thm, 
  18. >S1 - S2 can never vanish but is there a decent lower bound on
  19. >|S1 - S2| ? In particular, 1/N^O(1) ?
  20.  
  21. That's too much to hope for.  There are 2^N subsums in all, each of
  22. absolute value <=N.  However you put 2^N points in a radius-N circle,
  23. some pair must be at distance at most O(N/2^(N/2)), which decreases
  24. faster than 1/N^O(1).  [If all distances had been >=2r, you'd have
  25. a packing of 2^N circles of radius r in a circle of radius N+r, whence
  26. 2^N*r^2 >= (N+r)^2;  now solve for r.]  Now eliminate the roots of
  27. unity occurring in both sums to get two disjoint subsums S1, S2 at
  28. the same small distance.
  29.  
  30. This bound can be reduced a bit further (by a factor of sqrt(N)) by
  31. noting that a positive proportion of the 2^N sums must have absolute
  32. value O(sqrt(N)) [Central Limit Theorem and all that].  Actually
  33. finding such S1 and S2 when N is at all large (say N=100) is of
  34. course a much harder problem...
  35.  
  36. --Noam D. Elkies (elkies@zariski.harvard.edu)
  37.   Dept. of Mathematics, Harvard University
  38.