Retsy Boss VIII's Star Fitting Homage

After 250 years, the nation has commissioned Retsy Boss VIII to design a new flag with one star for each of the nation’s current $58$ states. As an homage to the original flag design, Retsy wants to select $58$ stars from the square grid that are all at most some distance $R$ from a point on the plane. What is the minimum distance $R$ that Retsy can use?

Thankfully for Retsy Boss VIII, her namesake left her the Python code to run the optimization to find the number of stars given $h,$ $k$ and $R.$ Also, fortunately for Retsy Boss VIII she knew to look at OEIS to look up the integer sequence A000328, which captures the case of $h=k=0$ and $R \in \mathbb{N},$ to give her a decent idea of where to start. In particular, we see that $N(0,0,4) = 49$ and $N(0,0,5)=81,$ so let's start looking for $R \in [4,5].$ In particular, she wants to find $$R^* = \inf \left\{ R \in [4,5] \mid N^*(R) = \sup_{(h,k) \in [0,1]^2} N(h,k,R) \geq 58 \right\}.$$

Retsy didn't want to exhaustively search the entire phase space, so first she went about implementing a secant method update to arrive at some point $R$ for which $N^*(R) = 58.$ In particular, let's let $R_0 = 4,$ $R_1 = 5$ and $$R_{n+1} = \frac{R_{n-1} N^*(R_n) - R_n N^*(R_{n-1}) + 58 (R_n - R_{n-1})}{N^*(R_n) - N^*(R_{n-1})}.$$ Note that relatively quickly we arrive at some value with $N^*(R) = 58,$ that is,

$n$	$R_n$	$N^*(R_n)$
$0$	$4$	$49$
$1$	$5$	$81$
$2$	$4.20689655\dots$	$59$
$3$	$4.17084639\dots$	$58$

That is all well and good, but Retsy VIII wants the minimal such value of $R$ such that $N^*(R) = 58.$ Now she turns to a binary search of the interval $[a_0,b_0] = [4, 4.17084639],$ to within a tolerance of $\varepsilon = 10^{-6}.$ For each $n,$ she defines $c_n = \frac{a_n+b_n}{2}.$ If $N^*(c_n) \lt 58,$ then she defines $a_{n+1} = c_n$ and $b_{n+1} = b_n;$ however if $N^*(c_n) = 58,$ then she defines $a_{n+1} = a_n$ and $b_{n+1} = c_n.$ We can stop as soon as

$n$	$a_n$	$b_n$	$c_n$	$N^*(c_n)$
$0$	$4$	$4.17084639$	$4.08542320$	$56$
$1$	$4.08542320$	$4.17084639$	$4.12813480$	$57$
$2$	$4.12813480$	$4.17084639$	$4.14949060$	$57$
$3$	$4.14949060$	$4.17084639$	$4.16016850$	$58$
$4$	$4.14949060$	$4.16016850$	$4.15482955$	$57$
$5$	$4.15482955$	$4.16016850$	$4.15749902$	$58$
$6$	$4.15482955$	$4.15749902$	$4.15616428$	$58$
$7$	$4.15482955$	$4.15616428$	$4.15549691$	$58$
$8$	$4.15482955$	$4.15549691$	$4.15516323$	$57$
$9$	$4.15516323$	$4.15549691$	$4.15533007$	$58$
$10$	$4.15516323$	$4.15533007$	$4.15524665$	$58$
$11$	$4.15516323$	$4.15524665$	$4.15520494$	$58$
$12$	$4.15516323$	$4.15520494$	$4.15518409$	$57$
$13$	$4.15518409$	$4.15520494$	$4.15519451$	$58$
$14$	$4.15518409$	$4.15519451$	$4.15518930$	$57$
$15$	$4.15518930$	$4.15519451$	$4.15519191$	$57$
$16$	$4.15519191$	$4.15519451$	$4.15519321$	$58$
$17$	$4.15519191$	$4.15519321$	$4.15519256$	$58$

So we see that the optimal value of $R^*$ is about $4.15519256$ to within a tolerance of $\varepsilon = 10^{-6}.$ At this point, we can use map a contour plot, shown below, similar to what we did for the Classic problem. It is hard to discern, but the only place that the maximum is attained (up to the various symmetries of the $N$ function) when $R = 4.15519256$ is in a small neighborhood of the point $(h,k) = (1/2, 1/8)$ (seem familiar ... wink, wink?). If we were to graph the circle of radius $R = 4.15519256$ centered at $(1/2, 1/8),$ we see that it ever so slightly includes the lattice points $(-1,4),$ $(2,4),$ $(0,-4)$ and $(1,-4).$ In particular, since we see that the distance from $(1/2, 1/8)$ to any of these four lattices points is exactly the same, we can reduce the value of $R$ to precise that distance and maintain a value of $N^*(R) = 58,$ and hence the minimum distance that Retsy Boss VIII can use to honor her forebear's design is exactly $$R^* = \sqrt{0.5^2 + 4.125^2} = \sqrt{1.5^2 + 3.875^2} = \frac{\sqrt{1105}}{8} \approx 4.155192534648665\dots.$$

Move Over Ed McMahon, It's Retsy Boss's Star Search

When designing her new nation’s flag, Retsy Boss wanted to compactly arrange some stars. These stars were positioned along a square grid, but she only wanted to include stars whose centers were at most two units away from some point on the plane.

For example, if she had centered the circle on a star itself, then she could have placed a total of 13 stars on the flag, as shown below:

What is the greatest number of stars Retsy could have placed on the flag?

Let's define the function $N(h,k,R)$ to be the number of integer lattice points within distance $R$ of the point $(h,k) \in \mathbb{R}^2,$ in particular, we have $$N(h,k,R) = \# \left\{ (m,n) \in \mathbb{Z}^2 \mid (m-h)^2 + (n-k)^2 \leq R^2 \right\}.$$ If we have a fixed value of $k,$ let's say, then we see will have $$\eta_n(h,k,R) = \left\lfloor \sqrt{R^2 - (n-k)^2} + h \right\rfloor + \left\lfloor \sqrt{R^2 - (n-k)^2} - h \right\rfloor + 1,$$ where for clarity $\lfloor x \rfloor = \max \{ n \in \mathbb{Z} \mid n \leq x \}$ and in particular $\lfloor x \rfloor = -1$ for $x \in [-1,0).$ So in particular, we have $$N(h,k,R) = \sum_{n=-\lfloor R - k \rfloor}^{\lfloor R + k \rfloor} \eta_n (h,k,R).$$ We see for instance, that when $h=k=0$ and $R=2,$ that we indeed recover $\eta_{-2}(0,0,2) = \eta_2(0,0,2) = 1, \eta_{-1}(0,0,2) = \eta_1(0,0,2) = 3,$ and $\eta_0 (0,0,2)= 5,$ so we have $$N(0,0,2) = \sum_{n=-2}^2 \eta_n(0,0,2) = 1 + 3 + 5 + 3 + 1 = 13.$$

Now, since we also see that everything is periodic and symmetric, in order to solve Retsy's problem we only need to find $$N^* = \max \left\{ N(h,k,2) \mid 0 \leq k \leq h \leq \frac{1}{2} \right\},$$ since everything else in the unit square will can be recovered from this region and everything else in the plane is periodic so $N(h,k,2) = N([h], [k],2),$ for all $(h,k) \in \mathbb{R}^2,$ where $[x] = x - \lfloor x \rfloor$ is the fractional part function.

We can code this up in the following Python code to explore the phase space and empirically determine $N^*$:

 

import math

import numpy as np

​

def _stars(h, k, R):

    num = 0

    lst_y = list(range(-math.floor(R-k), math.floor(R+k)+1))

    for y in lst_y:

        root = math.sqrt(R*R - (y-k)*(y-k))

        num += math.floor(root + h) + math.floor(root - h) + 1

    return num

​

def stars(h, k, R):

    tmph = h.copy()

    tmpk = k.copy()

    shape = h.shape

    if len(shape) == 1:

        shape = (shape[0],1)

    out = np.zeros(shape=shape)

    tmph.resize(shape)

    tmpk.resize(shape)

    for i in range(shape[0]):

        for j in range(shape[1]):

            out[i,j] = _stars(tmph[i,j], tmpk[i,j], R)

    return out

Using this Python code, we can plot the following contour plot, which shows that anywhere in the dark blue region produces the the largest possible number of stars that Retsy could place on the flag is $N^*=14.$ In particular, we can take the point $(h,k) = (0.5, 0.125)$ for foreshadowing purposes and explicitly compute that \begin{align*} \eta_{-1}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (-1-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (-1-0.125)^2 } - 0.5 \rfloor + 1 \\ &\quad = \lfloor 1.654\dots + 0.5 \rfloor + \lfloor 1.654\dots - 0.5 \rfloor + 1 = 4\\ \eta_{0}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (-0.125)^2 } - 0.5 \rfloor + 1\\ &\quad =\lfloor 1.996\dots + 0.5 \rfloor + \lfloor 1.996\dots - 0.5 \rfloor + 1 = 4\\ \eta_{1}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (1-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (1-0.125)^2 } - 0.5 \rfloor + 1\\ &\quad =\lfloor 1.798\dots + 0.5 \rfloor + \lfloor 1.798\dots - 0.5 \rfloor + 1 = 4\\ \eta_{2}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (2-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (2-0.125)^2 } - 0.5 \rfloor + 1\\ &\quad =\lfloor 0.696\dots + 0.5 \rfloor + \lfloor 0.696\dots - 0.5 \rfloor + 1 = 2\end{align*} so that $$N(0.5,0.125,2)=N^*=4+4+4+2=14.$$