11
$\begingroup$

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.

Sample pictures showing some examples

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

$\endgroup$
4
+100
$\begingroup$

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

Squares

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).

Square 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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Does this mean that $f(r) = \max f(r, \varphi)$? $\endgroup$ – Varun Vejalla Jun 1 at 17:49
  • $\begingroup$ @VVejalla Thank you for a question! I've missed this task. Will be continued. $\endgroup$ – Yuri Negometyanov Jun 1 at 20:25
  • $\begingroup$ @VVejalla Full version is posted. $\endgroup$ – Yuri Negometyanov Jun 2 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.