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)$?

Solution 1:

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<n\sqrt2,\ $ where $\ n\in\mathbb N;$

• There are confirmed by the tests.

However, I have not a proof.