home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9695 < prev    next >
Encoding:
Text File  |  1992-07-30  |  2.6 KB  |  59 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!sun-barr!ames!agate!linus!linus.mitre.org!faron!bs
  3. From: bs@faron.mitre.org (Robert D. Silverman)
  4. Subject: Re: Sieve  (Was Re; Re; prime quadruplets ... partial apology)
  5. Message-ID: <1992Jul30.234102.1645@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: faron.mitre.org
  8. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  9. References: <keRf_Ru00iUy02UVMt@andrew.cmu.edu> <1992Jul29.222749.18849@spool.cs.wisc.edu> <1992Jul30.171603.14329@husc3.harvard.edu>
  10. Date: Thu, 30 Jul 1992 23:41:02 GMT
  11. Lines: 46
  12.  
  13. In article <1992Jul30.171603.14329@husc3.harvard.edu> kubo@zariski.harvard.edu (Tal Kubo) writes:
  14.  
  15. stuff deleted....
  16.  
  17. :i.e. the conjectured density is the product of local densities 
  18. :[essentially  (1-4/p)]  taken over few enough primes less than N
  19. :to maintain the 'independence' of congruences modulo different
  20. :primes.  Some questions for the experts:
  21. :
  22. :>    This is based on probabilistic arguments, 
  23. :                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^        
  24. :   1)  Are there problems where the heuristic arguments fail?
  25. :
  26. Yes. Certainly. One very well known failure is the probabalistic argument
  27. for Fermat's Last Theorem. While it works for exponents greater than 3,
  28. it fails for exponent 3. That is to say the heuristic predicts that
  29. there should be an infinite number of solutions for exponent 3.
  30.  
  31. :   2)  Can one guess the prime number theorem from heuristics?
  32.  
  33. Yes, but only approximately (up to a constant factor). See, for example
  34. the derivation of Merten's Theorem in Hardy and Wright. Roughly speaking
  35. the probability that a large number is prime is the probability that it
  36. is NOT divisible by 2,3,5,....... . This probability is (1-1/2)*(1-1/3)*
  37. (1-1/5)*.....(1-1/sqrt(n)).  This product is O(n/log(n)). [the constants
  38. are known. see Merten's theorem]. There are other heuristics that suggest
  39. the constant is 1.
  40.  
  41. :>                                                 and agrees with
  42. :>    numerical data, as far as we know.  Using sieve methods, it can 
  43. :>    be shown that the number is O( N / (log N)^4 ).
  44. :
  45. :   3)  How convincing is the numerical data?  Is there reason
  46.  
  47. It is VERY convincing. In fact, in a loose sense it is overwhelming.
  48.  
  49. :       to believe that breakdown of heuristic hypotheses such as
  50. :       independence could be tested in the range of computations
  51. :       feasible today? 
  52.  
  53. Not really. If they do break down it is likely out of range.
  54. --
  55. Bob Silverman
  56. These are my opinions and not MITRE's.
  57. Mitre Corporation, Bedford, MA 01730
  58. "You can lead a horse's ass to knowledge, but you can't make him think"
  59.