mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Analysis & Analytic Number Theory

Reply
 
Thread Tools
Old 2020-02-13, 04:47   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

133468 Posts
Default Parity barrier

Silverman suggested talking about some real mathematics, maybe the parity problem. I don't know if we have enough expertise here for a good discussion, but I thought I'd give it a go.

Tao has some great expository articles:
https://terrytao.wordpress.com/2007/...-sieve-theory/
https://terrytao.wordpress.com/2014/...m-obstruction/
https://terrytao.wordpress.com/2015/...-sieve-theory/
https://terrytao.wordpress.com/2014/...bounded-error/
https://terrytao.wordpress.com/2016/...mptotic-sieve/

Here are some papers showing real results breaking the parity barrier: Friedlander & Iwaniec, Heath-Brown, Helfgott, Heath-Brown & Moroz, Ramaré & Walker, Tao, and Zhang.

It's hard,and there are still no general techniques, but it's doable. Bilinear forms seem to be a recurring theme.
CRGreathouse is offline   Reply With Quote
Old 2020-02-13, 05:09   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Silverman suggested talking about some real mathematics, maybe the parity problem. I don't know if we have enough expertise here for a good discussion, but I thought I'd give it a go.

Tao has some great expository articles:
https://terrytao.wordpress.com/2007/...-sieve-theory/
https://terrytao.wordpress.com/2014/...m-obstruction/
https://terrytao.wordpress.com/2015/...-sieve-theory/
https://terrytao.wordpress.com/2014/...bounded-error/
https://terrytao.wordpress.com/2016/...mptotic-sieve/

Here are some papers showing real results breaking the parity barrier: Friedlander & Iwaniec, Heath-Brown, Helfgott, Heath-Brown & Moroz, Ramaré & Walker, Tao, and Zhang.

It's hard,and there are still no general techniques, but it's doable. Bilinear forms seem to be a recurring theme.
The basic problem, even for weighted sieves is that each time one adds an (additional)
element to the sieve a tiny bit of error creeps in. With enough elements the error
term overtakes the main term. Typically, when sieving integers up to B is that one can
use up to [log(B)]^m for some m elements in the sieve or under some conditions
B^epsilon for small epsilon before the errors become too large. This is known sometimes
as the "fundamental lemma of the sieve".

Example: How many integers in [1,101] are divisible by 3. Answer is trivially 33.
But it is also 33 for [1,99], and [1,100]. We estimate the number in [1,N] as N/3
but this is seen to be a "little bit wrong". If we want to sieve all the primes up to
K without error we need to take B >> 2*3*5*...K ~ exp(K). Thus we only are allowed
to have log(B) primes in the sieve if we want to avoid accumulating errors. When
we bound the error (depending on the weighting scheme) we can take up to log^m (B)
sieve elements.
R.D. Silverman is offline   Reply With Quote
Old 2020-02-13, 05:49   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
The basic problem, even for weighted sieves is that each time one adds an (additional)
element to the sieve a tiny bit of error creeps in. With enough elements the error
term overtakes the main term. Typically, when sieving integers up to B is that one can
use up to [log(B)]^m for some m elements in the sieve or under some conditions
B^epsilon for small epsilon before the errors become too large. This is known sometimes
as the "fundamental lemma of the sieve".

Example: How many integers in [1,101] are divisible by 3. Answer is trivially 33.
But it is also 33 for [1,99], and [1,100]. We estimate the number in [1,N] as N/3
but this is seen to be a "little bit wrong". If we want to sieve all the primes up to
K without error we need to take B >> 2*3*5*...K ~ exp(K). Thus we only are allowed
to have log(B) primes in the sieve if we want to avoid accumulating errors. When
we bound the error (depending on the weighting scheme) we can take up to log^m (B)
sieve elements.
With regard to the bilinear forms: The successes have come because the range sets
for these forms have "sufficient density". When one considers (say) X^2 + 1, there
are ~sqrt(B). such integers up to B. But if we take a bilinear form such as x^2 + y^4
there are ~B^(3/4) such integers less than B. This is "just enough more"
so that sieve methods can succeed; the range sets are just a little bit denser.

BTW, I have read Halberstam & Richert's "Sieve Methods" a couple of times. I have
it on good authority from an expert (my ex) that it is a great reference, but not a
great textbook to learn from. I found it frustrating to read and understand. I still
can't claim to understand it, but it is a good starting point.
R.D. Silverman is offline   Reply With Quote
Old 2020-02-13, 05:52   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
With regard to the bilinear forms: The successes have come because the range sets
for these forms have "sufficient density". When one considers (say) X^2 + 1, there
are ~sqrt(B). such integers up to B. But if we take a bilinear form such as x^2 + y^4
there are ~B^(3/4) such integers less than B. This is "just enough more"
so that sieve methods can succeed; the range sets are just a little bit denser.

BTW, I have read Halberstam & Richert's "Sieve Methods" a couple of times. I have
it on good authority from an expert (my ex) that it is a great reference, but not a
great textbook to learn from. I found it frustrating to read and understand. I still
can't claim to understand it, but it is a good starting point.
Does anyone know if Murty's book is a better tutorial?
R.D. Silverman is offline   Reply With Quote
Old 2020-02-15, 03:07   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10110111001102 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Does anyone know if Murty's book is a better tutorial?
I was curious as to how that compared to the Halberstam-Richert book.
CRGreathouse is offline   Reply With Quote
Old 2020-02-17, 03:38   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I was curious as to how that compared to the Halberstam-Richert book.
Indeed. That is why I asked. Halberstam & Richert is also somewhat dated.
R.D. Silverman is offline   Reply With Quote
Old 2020-02-22, 00:43   #7
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111710 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Does anyone know if Murty's book is a better tutorial?
Do you mean the book by Cojocaru and Ram Murty? I have recently begun studying it and have been enjoying it. I did bog down a couple years ago in Halberstam and Richert.
philmoore is offline   Reply With Quote
Old 2020-02-25, 16:20   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by philmoore View Post
Do you mean the book by Cojocaru and Ram Murty? I have recently begun studying it and have been enjoying it. I did bog down a couple years ago in Halberstam and Richert.
Yes. Comments are welcome.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Did that guy actually break the the sound barrier? davieddy Puzzles 47 2012-10-19 21:12

All times are UTC. The time now is 14:26.

Wed Aug 5 14:26:27 UTC 2020 up 19 days, 10:13, 1 user, load averages: 1.87, 1.81, 1.74

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.