Mixing
Heuristics behind the Circle problem?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Is there a heuristic argument behind the exponent in the circle problem? The problem that I am referring to is the following: Consider a circle of radius $R$ centered at the origin in the plane and let $N(R)$ denote the number of integer lattice points contained in the circle. Then it easy to show that $N(r)/ pi R^2 to 1$ as $R to infty$. The circle problem asks what is the optimal exponent for the error term.
analytic-number-theory
asked 11 hours ago
Mustafa Said
1,0171522
add a comment |Â
up vote
1
down vote
favorite
Is there a heuristic argument behind the exponent in the circle problem? The problem that I am referring to is the following: Consider a circle of radius $R$ centered at the origin in the plane and let $N(R)$ denote the number of integer lattice points contained in the circle. Then it easy to show that $N(r)/ pi R^2 to 1$ as $R to infty$. The circle problem asks what is the optimal exponent for the error term.
analytic-number-theory
asked 11 hours ago
Mustafa Said
1,0171522
1
There is a wikipedia article, en.wikipedia.org/wiki/Gauss_circle_problem . See also mathoverflow.net/questions/19079/… for more info.
– none
11 hours ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Is there a heuristic argument behind the exponent in the circle problem? The problem that I am referring to is the following: Consider a circle of radius $R$ centered at the origin in the plane and let $N(R)$ denote the number of integer lattice points contained in the circle. Then it easy to show that $N(r)/ pi R^2 to 1$ as $R to infty$. The circle problem asks what is the optimal exponent for the error term.
analytic-number-theory
asked 11 hours ago
Mustafa Said
1,0171522
Is there a heuristic argument behind the exponent in the circle problem? The problem that I am referring to is the following: Consider a circle of radius $R$ centered at the origin in the plane and let $N(R)$ denote the number of integer lattice points contained in the circle. Then it easy to show that $N(r)/ pi R^2 to 1$ as $R to infty$. The circle problem asks what is the optimal exponent for the error term.
analytic-number-theory
analytic-number-theory
asked 11 hours ago
Mustafa Said
1,0171522
asked 11 hours ago
Mustafa Said
1,0171522
asked 11 hours ago
Mustafa Said
1,0171522
asked 11 hours ago
Mustafa Said
1,0171522
asked 11 hours ago
Mustafa Said
1,0171522
1,0171522
1
There is a wikipedia article, en.wikipedia.org/wiki/Gauss_circle_problem . See also mathoverflow.net/questions/19079/… for more info.
– none
11 hours ago
add a comment |Â
1
There is a wikipedia article, en.wikipedia.org/wiki/Gauss_circle_problem . See also mathoverflow.net/questions/19079/… for more info.
– none
11 hours ago
1
1
There is a wikipedia article, en.wikipedia.org/wiki/Gauss_circle_problem . See also mathoverflow.net/questions/19079/… for more info.
– none
11 hours ago
There is a wikipedia article, en.wikipedia.org/wiki/Gauss_circle_problem . See also mathoverflow.net/questions/19079/… for more info.
– none
11 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
5
down vote
accepted
The heuristics for this problem is due to Gauss: the error term $delta N(R)=N(R)-pi R^2$ must scale with the circumference $2pi R$ of the circle, because it is along the circumference that the ambiguity of lattice points just inside or just outside the circle appears; Gauss' estimate $delta N(R)propto R$ is an overestimate, the configuration of lattice points is such that the excess and deficit of points just inside and just outside partially cancels each other, so that the exponent is closer to $1/2$. Intuitively, this cancellation is obvious from a figure, but to obtain the correct exponent is not something that I think is accessible by any heuristics.
UPDATE: This could be an intuitive argument ("heuristics") for $delta N(R)propto R^1/2$: The number $M$ of lattice points along the perimeter is of order $R$. If each lattice point contributes $pm 1$ to $delta N(R)$, and these $M$ contributions are statistically independent, the total contribution would be of order $sqrt Mproptosqrt R$.
Source: The Circle Problem of Gauss and the Divisor Problem of Dirichlet—Still Unsolved.
Each lattice point is associated with a unit cell, chosen such that the lattice point is in the lower-left corner of the cell. Lattice points inside the circle correspond to a cell shown in red. The number of red cells that extends outside the circle cancels approximately with the number of white cells that extend inside, producing a sub-linear scaling of $delta N$ with the radius $R$ of the circle.
answered 7 hours ago
Carlo Beenakker
70.6k9156263
add a comment |Â
up vote
2
down vote
A formula, due to Hardy, expresses the error term $P(x) := N(sqrtx)-pi x$ in terms of values of a Bessel function:
$$(*), P(x) = x^1/2sum_n ge 1fracr(n)n^1/2J_1(2pi sqrtnx),$$
where $r(n):=# (a,b)in mathbbZ^2: a^2+b^2=n$ (this should be modified slightly for integer $x$). As $J_1(t)=O(1/sqrtt)$ as $tto infty$, any truncation of the RHS of $(*)$ is $O(x^1/4)$. Unfortunately, this does not yield such a bound for $P(x)$, since $sum r(n)/n^3/4$ obviously diverges.
There are also various results studying $P(x)$ in mean, usually using $(*)$ or variations thereof. The first such result seems to be Cramér's, who in 1921 showed that
$$int_1^x P^2(t), dt sim C x^2/3$$
for an explicit $C>0$. This is one good reason to suspect that $P(t) = O(t^1/4+epsilon)$ (and it certainly shows that $P(t) = O(t^1/4-epsilon)$ is impossible, which was proven before by Hardy). Subsequent works include computing the 3rd and 4th moments of $P$ (Tsang), and proving that $P(t)/t^1/4$ has a limiting distribution (Heath-Brown).
answered 1 hour ago
Ofir Gorodetsky
5,43212236
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
The heuristics for this problem is due to Gauss: the error term $delta N(R)=N(R)-pi R^2$ must scale with the circumference $2pi R$ of the circle, because it is along the circumference that the ambiguity of lattice points just inside or just outside the circle appears; Gauss' estimate $delta N(R)propto R$ is an overestimate, the configuration of lattice points is such that the excess and deficit of points just inside and just outside partially cancels each other, so that the exponent is closer to $1/2$. Intuitively, this cancellation is obvious from a figure, but to obtain the correct exponent is not something that I think is accessible by any heuristics.
UPDATE: This could be an intuitive argument ("heuristics") for $delta N(R)propto R^1/2$: The number $M$ of lattice points along the perimeter is of order $R$. If each lattice point contributes $pm 1$ to $delta N(R)$, and these $M$ contributions are statistically independent, the total contribution would be of order $sqrt Mproptosqrt R$.
Source: The Circle Problem of Gauss and the Divisor Problem of Dirichlet—Still Unsolved.
Each lattice point is associated with a unit cell, chosen such that the lattice point is in the lower-left corner of the cell. Lattice points inside the circle correspond to a cell shown in red. The number of red cells that extends outside the circle cancels approximately with the number of white cells that extend inside, producing a sub-linear scaling of $delta N$ with the radius $R$ of the circle.
answered 7 hours ago
Carlo Beenakker
70.6k9156263
add a comment |Â
up vote
5
down vote
accepted
The heuristics for this problem is due to Gauss: the error term $delta N(R)=N(R)-pi R^2$ must scale with the circumference $2pi R$ of the circle, because it is along the circumference that the ambiguity of lattice points just inside or just outside the circle appears; Gauss' estimate $delta N(R)propto R$ is an overestimate, the configuration of lattice points is such that the excess and deficit of points just inside and just outside partially cancels each other, so that the exponent is closer to $1/2$. Intuitively, this cancellation is obvious from a figure, but to obtain the correct exponent is not something that I think is accessible by any heuristics.
UPDATE: This could be an intuitive argument ("heuristics") for $delta N(R)propto R^1/2$: The number $M$ of lattice points along the perimeter is of order $R$. If each lattice point contributes $pm 1$ to $delta N(R)$, and these $M$ contributions are statistically independent, the total contribution would be of order $sqrt Mproptosqrt R$.
Source: The Circle Problem of Gauss and the Divisor Problem of Dirichlet—Still Unsolved.
Each lattice point is associated with a unit cell, chosen such that the lattice point is in the lower-left corner of the cell. Lattice points inside the circle correspond to a cell shown in red. The number of red cells that extends outside the circle cancels approximately with the number of white cells that extend inside, producing a sub-linear scaling of $delta N$ with the radius $R$ of the circle.
answered 7 hours ago
Carlo Beenakker
70.6k9156263
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
The heuristics for this problem is due to Gauss: the error term $delta N(R)=N(R)-pi R^2$ must scale with the circumference $2pi R$ of the circle, because it is along the circumference that the ambiguity of lattice points just inside or just outside the circle appears; Gauss' estimate $delta N(R)propto R$ is an overestimate, the configuration of lattice points is such that the excess and deficit of points just inside and just outside partially cancels each other, so that the exponent is closer to $1/2$. Intuitively, this cancellation is obvious from a figure, but to obtain the correct exponent is not something that I think is accessible by any heuristics.
UPDATE: This could be an intuitive argument ("heuristics") for $delta N(R)propto R^1/2$: The number $M$ of lattice points along the perimeter is of order $R$. If each lattice point contributes $pm 1$ to $delta N(R)$, and these $M$ contributions are statistically independent, the total contribution would be of order $sqrt Mproptosqrt R$.
Source: The Circle Problem of Gauss and the Divisor Problem of Dirichlet—Still Unsolved.
Each lattice point is associated with a unit cell, chosen such that the lattice point is in the lower-left corner of the cell. Lattice points inside the circle correspond to a cell shown in red. The number of red cells that extends outside the circle cancels approximately with the number of white cells that extend inside, producing a sub-linear scaling of $delta N$ with the radius $R$ of the circle.
answered 7 hours ago
Carlo Beenakker
70.6k9156263
The heuristics for this problem is due to Gauss: the error term $delta N(R)=N(R)-pi R^2$ must scale with the circumference $2pi R$ of the circle, because it is along the circumference that the ambiguity of lattice points just inside or just outside the circle appears; Gauss' estimate $delta N(R)propto R$ is an overestimate, the configuration of lattice points is such that the excess and deficit of points just inside and just outside partially cancels each other, so that the exponent is closer to $1/2$. Intuitively, this cancellation is obvious from a figure, but to obtain the correct exponent is not something that I think is accessible by any heuristics.
UPDATE: This could be an intuitive argument ("heuristics") for $delta N(R)propto R^1/2$: The number $M$ of lattice points along the perimeter is of order $R$. If each lattice point contributes $pm 1$ to $delta N(R)$, and these $M$ contributions are statistically independent, the total contribution would be of order $sqrt Mproptosqrt R$.
Source: The Circle Problem of Gauss and the Divisor Problem of Dirichlet—Still Unsolved.
Each lattice point is associated with a unit cell, chosen such that the lattice point is in the lower-left corner of the cell. Lattice points inside the circle correspond to a cell shown in red. The number of red cells that extends outside the circle cancels approximately with the number of white cells that extend inside, producing a sub-linear scaling of $delta N$ with the radius $R$ of the circle.
answered 7 hours ago
Carlo Beenakker
70.6k9156263
edited 3 hours ago
answered 7 hours ago
Carlo Beenakker
70.6k9156263
answered 7 hours ago
Carlo Beenakker
70.6k9156263
answered 7 hours ago
Carlo Beenakker
70.6k9156263
70.6k9156263
add a comment |Â
add a comment |Â
up vote
2
down vote
A formula, due to Hardy, expresses the error term $P(x) := N(sqrtx)-pi x$ in terms of values of a Bessel function:
$$(*), P(x) = x^1/2sum_n ge 1fracr(n)n^1/2J_1(2pi sqrtnx),$$
where $r(n):=# (a,b)in mathbbZ^2: a^2+b^2=n$ (this should be modified slightly for integer $x$). As $J_1(t)=O(1/sqrtt)$ as $tto infty$, any truncation of the RHS of $(*)$ is $O(x^1/4)$. Unfortunately, this does not yield such a bound for $P(x)$, since $sum r(n)/n^3/4$ obviously diverges.
There are also various results studying $P(x)$ in mean, usually using $(*)$ or variations thereof. The first such result seems to be Cramér's, who in 1921 showed that
$$int_1^x P^2(t), dt sim C x^2/3$$
for an explicit $C>0$. This is one good reason to suspect that $P(t) = O(t^1/4+epsilon)$ (and it certainly shows that $P(t) = O(t^1/4-epsilon)$ is impossible, which was proven before by Hardy). Subsequent works include computing the 3rd and 4th moments of $P$ (Tsang), and proving that $P(t)/t^1/4$ has a limiting distribution (Heath-Brown).
answered 1 hour ago
Ofir Gorodetsky
5,43212236
add a comment |Â
up vote
2
down vote
A formula, due to Hardy, expresses the error term $P(x) := N(sqrtx)-pi x$ in terms of values of a Bessel function:
$$(*), P(x) = x^1/2sum_n ge 1fracr(n)n^1/2J_1(2pi sqrtnx),$$
where $r(n):=# (a,b)in mathbbZ^2: a^2+b^2=n$ (this should be modified slightly for integer $x$). As $J_1(t)=O(1/sqrtt)$ as $tto infty$, any truncation of the RHS of $(*)$ is $O(x^1/4)$. Unfortunately, this does not yield such a bound for $P(x)$, since $sum r(n)/n^3/4$ obviously diverges.
There are also various results studying $P(x)$ in mean, usually using $(*)$ or variations thereof. The first such result seems to be Cramér's, who in 1921 showed that
$$int_1^x P^2(t), dt sim C x^2/3$$
for an explicit $C>0$. This is one good reason to suspect that $P(t) = O(t^1/4+epsilon)$ (and it certainly shows that $P(t) = O(t^1/4-epsilon)$ is impossible, which was proven before by Hardy). Subsequent works include computing the 3rd and 4th moments of $P$ (Tsang), and proving that $P(t)/t^1/4$ has a limiting distribution (Heath-Brown).
answered 1 hour ago
Ofir Gorodetsky
5,43212236
add a comment |Â
up vote
2
down vote
up vote
2
down vote
A formula, due to Hardy, expresses the error term $P(x) := N(sqrtx)-pi x$ in terms of values of a Bessel function:
$$(*), P(x) = x^1/2sum_n ge 1fracr(n)n^1/2J_1(2pi sqrtnx),$$
where $r(n):=# (a,b)in mathbbZ^2: a^2+b^2=n$ (this should be modified slightly for integer $x$). As $J_1(t)=O(1/sqrtt)$ as $tto infty$, any truncation of the RHS of $(*)$ is $O(x^1/4)$. Unfortunately, this does not yield such a bound for $P(x)$, since $sum r(n)/n^3/4$ obviously diverges.
There are also various results studying $P(x)$ in mean, usually using $(*)$ or variations thereof. The first such result seems to be Cramér's, who in 1921 showed that
$$int_1^x P^2(t), dt sim C x^2/3$$
for an explicit $C>0$. This is one good reason to suspect that $P(t) = O(t^1/4+epsilon)$ (and it certainly shows that $P(t) = O(t^1/4-epsilon)$ is impossible, which was proven before by Hardy). Subsequent works include computing the 3rd and 4th moments of $P$ (Tsang), and proving that $P(t)/t^1/4$ has a limiting distribution (Heath-Brown).
answered 1 hour ago
Ofir Gorodetsky
5,43212236
A formula, due to Hardy, expresses the error term $P(x) := N(sqrtx)-pi x$ in terms of values of a Bessel function:
$$(*), P(x) = x^1/2sum_n ge 1fracr(n)n^1/2J_1(2pi sqrtnx),$$
where $r(n):=# (a,b)in mathbbZ^2: a^2+b^2=n$ (this should be modified slightly for integer $x$). As $J_1(t)=O(1/sqrtt)$ as $tto infty$, any truncation of the RHS of $(*)$ is $O(x^1/4)$. Unfortunately, this does not yield such a bound for $P(x)$, since $sum r(n)/n^3/4$ obviously diverges.
There are also various results studying $P(x)$ in mean, usually using $(*)$ or variations thereof. The first such result seems to be Cramér's, who in 1921 showed that
$$int_1^x P^2(t), dt sim C x^2/3$$
for an explicit $C>0$. This is one good reason to suspect that $P(t) = O(t^1/4+epsilon)$ (and it certainly shows that $P(t) = O(t^1/4-epsilon)$ is impossible, which was proven before by Hardy). Subsequent works include computing the 3rd and 4th moments of $P$ (Tsang), and proving that $P(t)/t^1/4$ has a limiting distribution (Heath-Brown).
answered 1 hour ago
Ofir Gorodetsky
5,43212236
edited 40 mins ago
answered 1 hour ago
Ofir Gorodetsky
5,43212236
answered 1 hour ago
Ofir Gorodetsky
5,43212236
answered 1 hour ago
Ofir Gorodetsky
5,43212236
5,43212236
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f313978%2fheuristics-behind-the-circle-problem%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
There is a wikipedia article, en.wikipedia.org/wiki/Gauss_circle_problem . See also mathoverflow.net/questions/19079/… for more info.
– none
11 hours ago