Approximate calculation of the number of lattice points in a quadrant by applying the BHH theorem

0. References

[1]Yoshitsugu Yamamoto and Mikio Kubo (February 20, 1997, first edition, first printing) Invitation to the Traveling Salesman Problem, Asakura Publishing Co.

[2]https://manabitimes.jp/math/661 How to find Pythagorean numbers and their proof

1. What is the BHH Theorem?

The BHH theorem is a theorem named after the initial letters of three researchers, Beardwood, Halton, and Hammersley. The content of the theorem is as follows.

"In a rectangle of area S, there are n random points. The length of the shortest path through all the points, l, converges to β√(nS). That β would be about 0.72, or about 0.765." [1]

2. Number of grid points in a quadrant

The equation of a circle can be expressed as x^2+y^2=r^2. (x,y) is almost a rational number (from tightness) or a real number, and conversely, there are only a finite number of grid points, which can be approximated by r.

What is important here is that the equation of the circle is created by applying the Pythagorean theorem, and the Pythagorean number is the one that makes the Pythagorean theorem valid.

3. How to generate atomic Pythagorean numbers

When we consider a set of atomic Pythagorean numbers (a,b,c) satisfying a^2+b^2=c^2, the following properties hold.

There exist natural numbers m,n (m>n) and

a=m^2-n^2, b=2mn, c=m^2+n^2

This can be seen from the fact that if we actually substitute, we get a constant equation.

Application of atomic Pythagorean numbers to the problem of the number of grid points in a quadrant

First, consider r=c, c-b=t^2.

In this case, the relation between m and n is

m=n+t

is m=n+t.

Under this assumption, find (a,b,c).

a=t(2n+t), b=2n(n+t), c=2n^2+2nt+t^2

Now, because of symmetry, we can consider up to the range a<=b, so

t(2n+t)<=2n(n+t)

→t<=n・sqrt(2)

In other words, if you know the combination of (a, b, c) as you determine n and vary t from 1 to n・sqrt(2), you can easily count the number of grid points in the quadrant.

For example, in the case of r=2c=10

The radius is determined -> the endpoints are determined -> 2 are determined.

c=5→(n,t)=(1,1)

2a=6, 2b=8

In other words, (1+6)*(1+8)+(1+6) is now fixed.

Counting each of the cases 2b=7, 9 separately, we get

2b=7→8

2b=9→5

From the above, we have

2+(1+6)*(1+8)+(1+6)+8+5+5=90

In fact, kc=r, k=r, and k=k.

As a matter of fact, when kc=r, k=const., this method can be adapted for quite a few cases since c grows in the second order of n, t, but we still need to divide the cases.

5. Application of the BHH theorem to the problem of the number of grid points in a quadrant (Part 1: How to apply)

So, I would like to find a formula N=N(r) using the number N and the radius r. So, I would like to apply the BHH theorem.

First of all, the BHH theorem requires the area S, the number of grid points N, the radius r, and the length l of the shortest path. Fortunately, S and l can be expressed as follows

S=πr^2/4

l=a+b・sqrt(2), 0<=b<=2, a+b+1=N(*1)

(*1) Consider that all grid points except one have one hand. Consider starting from each of the two points farthest (only r away) from the origin, and touching the lattice points. At this point, most of them can be reached by extending the hand by distance 1.

However, due to the even-odd relationship, we will need to reach out diagonally to successfully connect the two routes.

In this case, we need to reach out by sqrt(2). Furthermore, due to the even-odd relationship, sometimes the shortest path is not from the two farthest points, but if one of them starts from the point next to it, in this case, we will need to reach out further diagonally to connect the one point that was not used.

From the above, we can take β in the BHH theorem as an unknown

2(N-1)=β・sqrt(N・πr^2), b=0

2(N-3+sqrt(2))=β・sqrt(N・πr^2), b=2

2(N-3+sqrt(2))=β・sqrt(N・πr^2), b=2 If you can show that this β is a function of r through numerical experiments using approximate curves, you will be able to understand the formula N=N(r).

By the way, let's try solving for β once.

b=0→β=2(N-1)/sqrt(N・πr^2)

b=2→β=2(N-3+sqrt(2))/sqrt(N・πr^2)

The difference between the two is

(2-sqrt(2))/sqrt(N・πr^2)

and becomes negligible as r increases.

For the approximation curve, let's express the mean β of the two as a function of r.

Application of the BHH theorem to the problem of the number of grid points in a quadrant (Part 2: Approximate curve of β)

The actual number of grid points up to r=12 and the calculated value of β are shown in the table, which is close to 1.

In fact, I made a graph with r on the horizontal axis and β on the vertical axis.

Looking at this, we can infer that it has the shape ar^(-b)+c. I did the following command in matlab

f=fit(r,β,'power2')

This gave us an approximation of 0.524r^(-1.068)+1.036.

We compared it with the approximation curve.

I have a good approximation there, but it seems to be off in some places. So I made a graph of β/(the value of the approximation curve).

Apparently, it looks like a periodic function. It is widely known that a periodic function can be represented by a Fourier series. (More generally, it is said that all functions can be represented by Fourier series.) So, we will consider approximation by Fourier series. (Let's call this value of y g_1.)

For now, let's consider a_0+b_0cos(t_0・r)+c_0sin(t_0・r) I did the following command in matlab.

f2=fit(r,g_1,'fourier1')

This gives us

1.1013+0.0389cos(0.8194・r)-0.04892sin(0.8194・r)

The result is an approximation to

I compared g_1 and f2.

I also compared it to the value of f*f2.

That's a good approximation. In the same way, I made a graph of β/(the value of approximation curve 2).

This is also a periodic function. Similarly, we consider approximation by Fourier series. By repeating the same procedure below, we can get a more accurate approximation. But this time, we will finish with the following. (Let this value of y be g_2.)

I did the following command as a_1+b_1cos(t_1・r)+c_1sin(t_1・r).

f3=fit(circle.VarName9,circle3.VarName20,'fourier1');

Result:

1.004-0.0336cos(1.76・r)-0.0336sin(1.76・r)

I made a comparison between g_2 and f3.