# Can we find a function that finds the number of points inside a square centred on the origin?

This question was inspired from this problem.

For this problem, the radius of a square will be the distance from its centre to any of its four vertices. A lattice point is a point $$(a, b)$$ in the plane where $$a$$ and $$b$$ are both integers.

Find a function $$f$$ on the positive real numbers so that $$f(r)$$ is the largest possible number of lattice points inside any square of radius $$r$$ centred at the origin. A point on the perimeter is considered to be inside the square.

I misread the problem linked above and was trying to solve this question. I tried writing down the values of $$f(r)$$ depending on the value of $$r$$. For example, when $$1 \le r <\sqrt 2, f(r)=5$$ and when $$\sqrt 2 \le r < 2, f(r)=9$$. Next, I tried to focus only on the lower bounds, where the square's corners fall on boundary points. I could see that $$r$$ was of the form $$\sqrt {a^2+b^2}$$ so maybe I could try a function involving a lower bound. When the square's vertices fall on lattice points, we can use Pick's theorem to calculate the area. Here, $$i$$ means the number of interior points and $$b$$ means the number of boundary points.

According to Pick's theorem,
$$A=\frac 12b + i-1$$
However, as it is a square with diagonal $$2r$$,
$$A=2r^2$$
$$2r^2=\frac 12b + i-1$$

We know that $$f(r)=b+i$$ when $$r$$ is such that the square has lattice points as vertices. So:

$$f(r)=4r^2+1-i$$ or $$f(r)=4r^2+b+1$$

I could not progress any further. I thought I could form a relationship between the current square and the next largest square because $$f\left(r_{\text{Current Square}}\right)=4r^2+1-f\left(r_{\text{Next Largest Square}}\right)$$ but I am finding it difficult to define how we can get from a square to the next largest/smallest one. How should I progress? Is it even possible to find $$f(r)$$?

• Pick's theorem is an isolated result. You should look take into consideration the huge domain called geometry of numbers (initiated by Minkovski) : en.wikipedia.org/wiki/Geometry_of_numbers Commented May 26, 2020 at 21:24
• I should have been more precise : your issue look to be connected to Ehrhart polynomials : see for example the little paragraph " Examples of Ehrhart quasi-polynomials" in and the deep presentation here Commented May 27, 2020 at 18:17
• @JeanMarie Thank you very much. Commented May 27, 2020 at 19:45

Full version.

$$\color{brown}{\textbf{A model with rotational parameter.}}$$

Let $$\ {\scriptsize\Box} ABCD\$$ has the vertices $$A(x\!^\,_A,y\!^\,_A),\ B(x^\,_B,y^\,_B),\ C(x^\,_C,y^\,_C),\ D(x^\,_D,y^\,_D),\$$ where \left\{\begin{align} &z\!^\,_A=x\!^\,_A+iy\!^\,_A = re^{i\,(\,\varphi+{\Large^\pi\!/\large_4})},\\[4pt] &z^\,_B=x^\,_B+iy^\,_B = re^{i\,(\,\varphi+{\Large^{3\pi}\!/\large_4})},\\[4pt] &z^\,_C=x^\,_C+iy^\,_C = re^{i\,(\,\varphi-{\Large^{3\pi}\!/\large_4})},\\[4pt] &z^\,_D=x^\,_D+iy^\,_D = re^{i\,(\,\varphi-{\Large^{\pi}\!/\large_4})}, \end{align}\right.\tag1 $$r\$$ is the radius of $$\ {\scriptsize\Box} ABCD\$$ and
$$\varphi\in\left[0,\frac\pi2\right)\$$ is the angle between the diagonal of the first quadrant and the segment $$OA.$$

Denote the inner lattice points quantity as $$f(r,\varphi).$$

If $$\color{blue}{\mathbf{\ \varphi=0}},\$$ then $$\ {\scriptsize\Box} ABCD\$$ has the horizontal orientation, and $$\color{blue}{\mathbf{f(r,0) = \left(2\left\lfloor \dfrac r{\sqrt2}\,\right\rfloor+1\right)^2 = 2\left(\sqrt2\left\lfloor \dfrac r{\sqrt2}\,\right\rfloor+\dfrac1{\sqrt2}\right)^2}}.\tag{2}$$

If $$\color{blue}{\mathbf{\ \varphi=\dfrac\pi4}},\$$ then $$\ {\scriptsize\Box} ABCD\$$ has the diagonal orientation, and $$f\left(r,\dfrac\pi4\right) = \left(2\left\lfloor r\,\right\rfloor+1\right) +2\sum\limits_{k=0}^{\lfloor r \rfloor - 1}(2k+1),$$ $$\color{blue}{\mathbf{f\left(r,\dfrac\pi4\right) = 2\left\lfloor r\,\right\rfloor^2 + 2\left\lfloor r\,\right\rfloor+1 = 2\left(\lfloor r\rfloor+\dfrac12\,\right)^2+\dfrac12}}.\tag3$$

If $$\color{blue}{\mathbf{\ \varphi \in \left(\dfrac\pi4,\dfrac\pi2\right)}},\$$ then by symmetry $$\color{blue}{\mathbf{f(r,\varphi) = f\left(r,\dfrac\pi2-\varphi\right)}}.\tag4$$

If $$\color{blue}{\mathbf{\ \varphi \in \left(0,\dfrac\pi4\right)}}\$$ (the TeX plot for $$\ r=7,\ \varphi=\dfrac\pi{12}\$$ see above), then $$\begin{cases} \dbinom{x\!^\,_A}{y\!^\,_A} = \dfrac r{\sqrt2}\dbinom{\cos\varphi-\sin\varphi}{\cos\varphi+\sin\varphi}\\[8pt] \dbinom{x^\,_B}{y^\,_B} = \dfrac r{\sqrt2}\dbinom{-\cos\varphi-\sin\varphi}{\cos\varphi-\sin\varphi}\\[8pt] \dbinom{x^\,_C}{y^\,_C} = \dfrac r{\sqrt2}\dbinom{-\cos\varphi+\sin\varphi}{-\cos\varphi-\sin\varphi}\\[8pt] \dbinom{x^\,_D}{y^\,_D} = \dfrac r{\sqrt2}\dbinom{\cos\varphi+\sin\varphi}{-\cos\varphi+\sin\varphi},\tag5 \end{cases}$$

• side $$\ BC:\ y=y^\,_B - \cot \varphi\cdot (x-x^\,_B),\quad x=x\!^\,_B - \tan\varphi\cdot(y-y^\,_B),\\ x(0)=-\dfrac r{\sqrt2}\cos\varphi\left(1+\tan\varphi-\tan\varphi+\tan^2\varphi\right) =-\xi,\quad\text{where}\quad\xi=\dfrac r{\sqrt2 \cos\varphi},\\ x=-\xi-y\tan\varphi;$$

• side $$\ BA:\ y=y^\,_B + \tan \varphi\cdot (x-x^\,_B),\quad x=x\!^\,_B + \cot\varphi\cdot(y-y^\,_B),\\ x(0)=-\dfrac r{\sqrt2}\sin\varphi(1+\cot\varphi-\cot\varphi+\cot^2\varphi)=-\xi \cot\varphi, \quad x=-(\xi-y)\cot\varphi;$$

• side $$\ AD:\ y=y\!^\,_A - \cot \varphi\cdot (x-x\!^\,_A),\quad x=x\!^\,_A - \tan\varphi\cdot(y-y\!^\,_A),\\ \quad x(0) = \dfrac r{\sqrt2}\cos\varphi(1-\tan\varphi+\tan\varphi=\tan^2\varphi) = \xi, \quad x=\xi-y\tan\varphi.$$

If $$\ y=0,\$$ then $$\ x\in[-\xi,\xi].$$
If $$\ y\in(0,y^\,_B],\$$ then $$\ x\in[-\xi-y\tan\varphi,\xi-y\tan\varphi].$$
If $$\ y\in(y^\,_B,y\!^\,_A],\$$ then $$\ x\in[-(\xi-y)\cot\varphi,\xi-y\tan\varphi].$$

Therefore, $$f(r,\varphi) = 1+2\lfloor\xi\rfloor +2\sum\limits_{k=1}^{\lfloor y^\,_A\rfloor}\lfloor\xi-k\tan\varphi\rfloor +2\sum\limits_{k=1}^{\lfloor y^\,_B\rfloor}\lfloor1+\xi+k\tan\varphi\rfloor\\ +2\sum\limits_{k=1+\lfloor y^\,_B\rfloor}^{\lfloor\xi\rfloor}\lfloor1+(\xi-k)\cot\varphi\rfloor -2\sum\limits_{k=1+\lfloor\xi\rfloor}^{\lfloor y^\,_A\rfloor}\lfloor(k-\xi)\cot\varphi \rfloor,$$

\color{blue}{\mathbf{\begin{align} &f(r,\varphi) = 1+4\lfloor\xi\rfloor +2\sum\limits_{k=1}^{\lfloor y^\,_A\rfloor}\lfloor\xi-k\tan\varphi\rfloor +2\sum\limits_{k=1}^{\lfloor y^\,_B\rfloor}\lfloor\xi+k\tan\varphi\rfloor\\[4pt] &+2\sum\limits_{k=1+\lfloor y^\,_B\rfloor}^{\lfloor\xi\rfloor}\lfloor(\xi-k) \cot\varphi\rfloor -2\sum\limits_{k=1+\lfloor\xi\rfloor}^{\lfloor y^\,_A\rfloor}\lfloor(k-\xi)\cot\varphi \rfloor,\\[4pt] &\text{where}\quad\xi=\dfrac r{\sqrt2 \cos\varphi}. \end{align}}}\tag6

If $$\ r=7,\ \varphi = \dfrac\pi{12},\$$ then $$\ \xi=\dfrac7{\sqrt2 \cos\frac\pi{12}}\approx5.124356,\ \cot\frac\pi{12}\approx 3.732051,$$ $$A=\dfrac72(1,\sqrt3)\approx(3.5,6.062),\quad B=\dfrac72(-\sqrt3,1),\quad C=\dfrac72(-1,\sqrt3),\quad D=\dfrac72(\sqrt3,1)$$ (see also Wolfram Alpha plot).

From $$(6)$$ should $$f\left(7,\dfrac\pi{12}\right) = 1+4\cdot5 + 2\sum\limits_{k=1}^6\left\lfloor 5.124356-\dfrac k{3.732051}\right\rfloor +2\sum\limits_{k=1}^3\left\lfloor 5.124356+\dfrac k{3.732051}\right\rfloor\\ +2\sum\limits_{k=4}^5\lfloor(5.124356-k)\cdot 3.732051\rfloor -2\sum\limits_{k=6}^6\lfloor(k-5.124356)\cdot3.732051\rfloor=97$$ (see also Wolfram Alpha calculations), in accordance with the TeX plot.

These calculations confirm expression $$(6).$$

Therefore, formulas $$(2),(3),(4),(6)$$ give the required result in the all possible cases.

$$\color{brown}{\textbf{Optimization.}}$$

Expressions in the round braces in $$(2),(3)$$ correlate with the round function. If $$\varphi=0,$$ then unit of the scale is $$\sqrt2.$$
If $$\varphi = \dfrac\pi4,$$ then the unit of the scale equals to $$1.$$

This means that the discretization is the single significant factor.
In particular,

$$f(7,0)= \left(2\lfloor4.950\rfloor+1\right)^2 = 98,\quad f\left(7,\dfrac\pi4\right) = 2\left(\dfrac{15}2\right)^2+\dfrac12 = 113,$$ $$f(5\sqrt2,0) = \left(2\lfloor5\rfloor+1\right)^2 = 121,\quad f\left(5\sqrt2,\dfrac\pi4\right) = 2\left(\lfloor 7.071\rfloor + \dfrac12 \right)^2 +\dfrac12 = 113.$$

Applying this approach to $$(6),\$$ can be assumed $$\begin{cases} \cot\varphi = n\in\mathbb N\\ \xi=\dfrac{r}{\sqrt2\cos\varphi} = m\in\mathbb N \end{cases}\Rightarrow \begin{cases} \cot\varphi = n\\ r=\dfrac{mn\sqrt2}{\sqrt{n^2+1}} \end{cases}$$ If $$\ \cot\varphi = n=2,\ \xi=m=11,\$$ then $$\ r=\sqrt{\dfrac{968}5}\approx13.914022,\ y^\,_B = r\sin\left(\varphi+\dfrac34\pi\right)=4.4,\ y^\,_A = r\sin\left(\varphi+\dfrac\pi4\right)=13.2,$$

\begin{align} &f(r,0)= \left(2\left\lfloor\dfrac{r}{\sqrt2}\right\rfloor+1\right)^2 =(2\cdot9+1)^2 = 361,\\[4pt] &f\left(r,\dfrac\pi4\right) = 2\left(\lfloor r\rfloor+\dfrac12\right)^2 +\dfrac12 = 365,\\[4pt] &f(r,\arctan 0.5) = 1+4\lfloor11\rfloor +2\sum\limits_{k=1}^{\lfloor 13.2\rfloor}\lfloor11-\,^k\!/_2\rfloor +2\sum\limits_{k=1}^{\lfloor 4.4\rfloor}\lfloor11+\,^k\!/_2\rfloor\\[4pt] &+2\sum\limits_{k=1+\lfloor 4.4\rfloor}^{\lfloor11\rfloor}\lfloor(11-k)\cdot2 \rfloor -2\sum\limits_{k=1+\lfloor11\rfloor}^{\lfloor 13.2\rfloor}\lfloor(k-11)\cdot2 \rfloor = 401. \end{align}

Therefore, the bounds of $$f(r)$$ can be defined as the global minimum and the global maximum of the all cases described by the formulas $$(2),(4),(6).$$

From $$(2)$$ should $$\left(2\left(\dfrac r{\sqrt2}-1\right)+1\right)^2 \le f(r,0) \le \left(2\left(\dfrac r{\sqrt2}-1\right)+1\right)^2,$$

$$2r^2-2\sqrt2\,r+1 \le f(r,0) \le 2r^2+2\sqrt2\,r+1.\tag{7a}$$

From $$(3)$$ should $$2\left(r-\dfrac12\right)^2+\dfrac12 \le f\left(r,\dfrac\pi4\right)\le 2\left(r+\dfrac12\right)^2+\dfrac12,$$

$$2r^2-2r+1 \le f\left(r,\dfrac\pi4\right)\le 2r^2+2r+1.\tag{7b}$$

Formulas $$(7a),(7b)$$ satisfy the condidion $$\color{brown}{\mathbf{2r^2-2\sqrt2\,r+1 \le f(r) \le 2r^2+2\sqrt2\,r+1}}.\tag{7}$$

There are some reasons why the inequalities $$(7)$$ look common.

• RHS is correct for $$\ r=n\sqrt2,\$$ where $$\ n\in\mathbb N;$$

• LHS is correct for $$\ r where $$\ n\in\mathbb N;$$

• There are confirmed by the tests.

However, I have not a proof.

• Does this mean that $f(r) = \max f(r, \varphi)$? Commented Jun 1, 2020 at 17:49
• @VVejalla Thank you for a question! I've missed this task. Will be continued. Commented Jun 1, 2020 at 20:25
• @VVejalla Full version is posted. Commented Jun 2, 2020 at 14:05