Minimal number of points on a grid forming line segments of equal length
We consider the minimal number of points on a regular grid on the plane that generates $n$ line segments of points of exactly length $k$. We illustrate how this is related to the $n$-queens problem on the toroidal chessboard and show that this number is upper bounded by $kn/3$ and approaches $kn/4$ as $n\rightarrow\infty$ when $k+1$ is coprime with $6$ or when $k$ is large.
\section{Introduction}
We consider points on a regular grid on the plane which form horizontal, vertical or diagonal blocks of exactly  $k$ points (which we will call {\em patterns})\footnote{We use the convention that an isolated point corresponds to $4$ patterns of length $1$; a horizontal, a vertical and 2 diagonal patterns.}.   For example, the set of points in Fig. \ref{fig:one} shows 12 points forming 3 patterns of length $5$. Note that since a pattern of length $k$ has to have exactly $k$ points flanked by empty grid locations, the set of points in Fig. \ref{fig:one} contains 4 patterns of length 2 and does not contain any patterns of length $4$ or of length $3$.   Our motivation for studying this problem is the Bingo-4 problem proposed by Sun et al. and  described in OEIS\cite{OEIS} sequence \href{http://oeis.org/A273916}{A273916} where  the case $k=4$ is considered.   Let $a_k(n)$ denote the minimal number of points needed to form $n$ patterns of length $k$, i.e. Fig. \ref{fig:one} shows that $a_5(3) = 12$.  Finding the exact value of $a_k(n)$ appears to be difficult and not feasible for large $n$. The purpose of this note is to provide an analysis on the asymptotic behavior of $a_k(n)$. 


\begin{figure}[htbp]
\centerline{\includegraphics[width=3in]{figure1.pdf}}
\caption{12 points on a grid forming 3 patterns of length 5.}\label{fig:one}
\end{figure}

\section{Bounds and asymptotic behavior of $a_k(n)$}
It is easy to see that $a_k(1) = k$, $a_k(2) = 2k-1$ and $a_k(3) = 3(k-1)$. Next, consider Fekete's subadditive Lemma   \cite{fekete:subadditive:1923} which is applicable to subadditive sequences.
\begin{lemma}[Fekete's subadditive Lemma]
If the sequence $a(n)$ is subadditive, i.e. $a(n+m) \leq a(n)+a(m)$, then $\lim_{n\rightarrow\infty}\frac{a_n}{n}$ exists and is equal to $\inf \frac{a_n}{n}$.
\label{lem:fekete}
\end{lemma}

\begin{theorem}
For all $k$, $a_k(n)$ is subadditive, and $f(k) = \lim_{n\rightarrow\infty}\frac{a_k(n)}{n} $ exists and satisfies $\frac{k}{4}\leq f(k) \leq \frac{k}{3}$.
\label{thm:bound}
\end{theorem}
\begin{proof}
Since each pattern takes $k$ points and each point can be part of at most $4$ patterns, $a_k(n) \geq \frac{kn}{4}$.
It is clear that $a_k(n)$ is subadditive. Lemma \ref{lem:fekete} implies that $f(k)$ exists and is equal to $\inf_n \frac{a_k(n)}{n}$.
Consider a $k$ by $m$ rectangular array of points with $k\leq m$. It is easy to see that there are $3m-2k+2$ length $k$ patterns there. This shows that $a_k(3m-2k+2)\leq km$ which implies that
$\frac{k}{4}\leq f(k) \leq \frac{k}{3}$.
\end{proof}


\section{Constellations where each point is part of 4 different patterns}
The upper bound $\frac{k}{3}$ on $f(k)$ in Theorem \ref{thm:bound} shows that for large $n$ we can construct a constellation of $n$ points such that most points are part of $3$ different patterns. Is it possible to construct a constellation such that most points are part of $4$ different patterns (a horizontal, a vertical and two diagonal patterns) and thus achieve the lower bound $\frac{k}{4}$? The case $k=1$ is simple. Since $a_1(4n) = n$ as exhibited by the constellation of $n$ isolated points, this implies that $f(1) = \frac{1}{4}$. 


Let $\sigma$ be a permutation on the integers $\{0,1,\cdots , k\}$. Consider a $k+1$ by $k+1$ square grid and place a point on each position $(i,j)$ except when it is of the form $(i,\sigma(i))$. It is clear that tiling this grid on the plane results in a constellation that have horizontal and vertical patterns of length $k$.
In order for the diagonals to also have a block of exactly $k$ points, $\{i+\sigma(i) \mod k+1\}$ and $\{i-\sigma(i) \mod k+1\}$ need to be permutations of  $\{0,1,\cdots , k\}$ as well.  Consider a $N$ by $N$ subgrid of this tiling.  Except for points near the edges which is on the order of $kN \propto k\sqrt{n}$, all points belong to $4$ patterns of length $k$.  Thus we have proved the following:
\begin{theorem} \label{thm:perm}
If there is a  permutation $\sigma$ of the numbers $\{0,1,\cdots ,k\}$ such that
$\sigma_1 = \{i+\sigma(i) \mod k+1\}$ and $\sigma_2 = \{i-\sigma(i) \mod k+1\}$ are both permutations, then $f(k) = \frac{k}{4}$. In particular, $\frac{a_k(n)}{n}$ converges to $f(k)$ on the order of 
$O\left(\frac{1}{\sqrt{n}}\right)$. 
\end{theorem}


If $\sigma$ satisfies the conditions of Theorem \ref{thm:perm}, then so does $\sigma^{-1}$.  For a fixed integer $m$, the permutation
$\sigma(i) + m \mod k+1$ also satisfies these conditions. We will use this to partition the set of admissible permutations into equivalent classes. More specifically,
\begin{definition}
Let $S_{k+1}$ be the set of permutations on $\{0,1,\cdots , k\}$.  $T_{k+1}\subset S_{k+1}$ is defined as the set of permutations $\sigma$ such that  $\{i+\sigma(i)\mod k+1\}$ and $\{i-\sigma(i)\mod k+1\}$ are in $S_{k+1}$.  The equivalence relation $\sim$ is defined as follows. If $\sigma, \tau \in T_{k+1}$, then $\sigma \sim \tau$ if $\tau = \sigma^{-1}$ or
there exist an integer $m$ such that $\sigma(i) = \tau(i) + m \mod k+1$ for all $i$.
\end{definition}

Thus if $T_{k+1}\neq \emptyset$, then $f(k) = \frac{k}{4}$.

\section{Modular $n$-queens problem}
The $n$-queens problem asks whether $n$ nonattacking queens can be placed on an $n$ by $n$ chessboard.  The answer is yes and is first shown by Pauls \cite{pauls:nqueens:1874,bell:nqueens:2009}.
Next consider a toroidal $n$ by $n$ chessboard, where the top edge is connected to the bottom edge and the left edge is connected to the right edge.
Polya \cite{polya:nqueens:1918} showed that a solution to the corresponding modular $n$-queens problem exists if and only if $n$ is coprime with $6$. It is clear that
a permutation in $T_{k+1}$ corresponds to a solution of the modular $(k+1)$-queens problem.  Thus Polya's result is equivalent to the following result:
\begin{theorem}\label{thm:polyaT}
$T_{k+1} \neq \emptyset$ if and only if $k+1$ is coprime with $6$.
\end{theorem} 


\begin{corollary}\label{cor:one}
If $k+1$ is coprime with $6$, then $f(k) = \frac{k}{4}$.
\end{corollary}

Monsky \cite{monsky:nqueens:1989} shows that $n-2$ nonattacking queens can be placed on an $n$ by $n$ toroidal chess board and $n-1$ queens can be placed if
$n$ is not divisible by $3$ or $4$.
This implies the following which shows that for $k$ large, $f(k)$ approaches the lower bound $\frac{k}{4}$:

\begin{theorem}\label{cor:upperbound}
$f(k) \leq \frac{k(k+1)+2}{4(k-1)}$. If $k+1$ is not divisible by $3$ or $4$, then
$f(k) \leq \frac{k(k+1)+1}{4k}$.
\end{theorem}

\begin{proof}
Consider a $k+1$ by $k+1$ array with $k+1-r$ nonattacking queens. By placing a point on the location where there are no queens we obtain a constellation with $(k+1)^2-(k+1-r)$ points.
Each queen position corresponds to $4$ patterns.  Thus  when this array is tiled, we get for a large number of points a ratio $\frac{a_k(n)}{n}$ approaching
$\frac{(k+1)^2-(k+1-r)}{4(k+1-r)} = \frac{k(k+1)+r}{4(k+1-r)}$.  The conclusion follows by setting $r =1 $ or $r= 2$.
\end{proof}

\begin{corollary}
$\lim_{k\rightarrow \infty} \frac{f(k)}{k} = \frac{1}{4}$.
\end{corollary}

\subsection{Lattice construction}
As in the $n$-queens problem, we can construct permutations in $T_{k+1}$ via a lattice construction.
In particular, we construct a constellation of points by placing a point on the grid if and only if it is not a point on a lattice spanned by two vectors $v_1$ and $v_2$.
For instance with the lattice points generated by the vectors $(1,2)$ and $(2,-1)$, the set of points with $N=15$ is shown in Fig. \ref{fig:two}.
In particular, this configuration shows that $f(4) = 1$.

\begin{figure}[htbp]
\centerline{\includegraphics[width=6in]{figure2.pdf}}
\caption{A lattice constellation. Points in the center of the grid are part of $4$ different patterns, showing that $\frac{a_{4}(n)}{n} \rightarrow 1$ as $n\rightarrow \infty$.}\label{fig:two}
\end{figure}

The following result appears to be well-known \cite{bell:nqueens:2009}, but we include it here for completeness.
\begin{theorem} \label{thm:coprime}
If there exists $1 <m < k$ such that $m-1$, $m $ and $m+1$ are all coprime with $k+1$, then the lattice construction with $v_1 = (1,m)$ and $(k+1,0)$ generates a permutation $\sigma$ in $T_{k+1}$.
\end{theorem}

\begin{proof}
Consider the lattice generated with the vectors $(1,m)$ and $(0,k+1)$. Clearly, if $m$ is coprime with $k+1$, then we find in a $k+1$ by $k+1$ subarray
locations which do not have a point of the form $(i,\sigma(i))$ with $\sigma$ a permutation.  
The lattice points have coordinates $(a, ma+(k+1)b)$ which lie on the $2$ main diagonals if $a=ma+(k+1)b$ or $-a = ma+(k+1)b$.
In the first case $-(m-1)a=(k+1)b$. Since $m-1$ is coprime with $k+1$,  this means that $a$ is a multiple of $k+1$, i.e., a diagonal pattern must have length $k$.  In the second case $-(m+1)a = (k+1)b$.  Since $k+1$ is coprime with $m+1$, again this means that $a$ is a multiple of $k+1$.
\end{proof}

Theorem \ref{thm:coprime} also provides a proof of Corollary \ref{cor:one} since if $k+1$ is coprime with $6$, then $1$, $2$ and $3$ are all coprime with $k+1$.  In particular the lattice construction with $v_1 = (1,2)$ and $(k+1,0)$ generates a permutation $\sigma$ in $T_{k+1}$. 
Fig. \ref{fig:three} shows the construction for $k= 12$.

\begin{figure}[htbp]
\centerline{\includegraphics[width=6in]{figure3.pdf}}
\caption{A lattice constellation for $k=12$ generated by vectors $(1,2)$ and $(0,13)$.}\label{fig:three}
\end{figure}

For $k=4$,
there is only one equivalence class $(0,2,4,1,3)$ in $T_{k+1}$ that satisfies the conditions of Theorem \ref{thm:perm}.  For $k=6$, there are two equivalent classes
$(0,2,4,6,1,3,5)$ and $(0,3,6,2,5,1,4)$. For $k=10$, there are $4$ equivalent classes.
In particular, Theorem \ref{thm:coprime} shows that if $k+1 > 4$ is prime, then there are at least $\frac{k-2}{2}$ equivalent classes in $T_{k+1}$. This is because each $2\leq m \leq k-1$ is coprime with $k+1$ and the permutation generated by $m$ is the inverse of the permutation generated by $k-1-m$ which are equivalent\footnote{For general $k$, see \cite{burger:nqueens:2004} for a formula of the number of such permutations.}. It is possible to have more than  $\frac{k-2}{2}$ equivalent classes as there are permutations in $T_{k+1}$ not generated by a lattice.
For $k+1$ coprime with $6$, if $k = 4, 6$ and $10$, all permutations in $T_{k+1}$ are generated by a lattice.  For $k = 12$, there are permutations in $T_{k+1}$ that are not generated by a lattice.  One such example is shown in Fig. \ref{fig:k12}. Such solutions are referred to as {\em nonlinear} solutions \cite{bell:nqueens:2009}. 

\begin{figure}[htbp]
\centerline{\includegraphics[width=6in]{k12nonlattice.pdf}}
\caption{A constellation for $k=12$ not generated by a lattice corresponding to the permutation $(0,2,4,6,11,9,12,5,3,1,7,10,8)$.}\label{fig:k12}
\end{figure}


\section{Conclusions}
We studied the asymptotic behavior of the minimal number of points needed to generate $n$ patterns of length $k$ using a construction based on permutations of
$\{0,1,\cdots, k\}$ with certain properties.  We showed that this construction allows us to create patterns where asympotically most points are part of 4 patterns. This construction is equivalent to the modular $(k+1)$-queens problem and thus $f(k)=\frac{k}{4}$ for $k+1$ coprime with $6$. If $k+1$ is even or $k+1$ is divisible by $3$, this construction fails to provide such a constellation.
However, results in the modular $n$-queens problem can still provide an upper bound on $f(k)$ which shows that $\lim_{k\rightarrow\infty}\frac{f(k)}{k} = \frac{1}{4}$. Even though these constructions for the modular $n$-queens problem provide limiting value of $\frac{a_k(n)}{n}$ as $n\rightarrow \infty$, for a fixed $n$ the optimal constellation to achieve $a_k(n)$ can be quite different (see for example \url{https://oeis.org/A273916/a273916.png}) .


\section{Acknowledgements}
We are indebted to Don Coppersmith for stimulating discussions and for providing his many insights during the preparation of this note.


2017-07-20T02:01:08.000
1608
1608.07247
en
https://arxiv.org/abs/1608.07247
We consider the minimal number of points on a regular grid on the plane that generates $n$ line segments of points of exactly length $k$. We illustrate how this is related to the $n$-queens problem on the toroidal chessboard and show that this number is upper bounded by $kn/3$ and approaches $kn/4$ as $n\rightarrow\infty$ when $k+1$ is coprime with $6$ or when $k$ is large.
Combinatorics (math.CO)
Minimal number of points on a grid forming line segments of equal length
Qwen/Qwen-72B
1. YES
2. YES