An arc in \(\mathbb Z^2_n\) is defined to be a set of points no three of which are collinear. We describe some properties of arcs and determine the maximum size of arcs for some small n.
1 Introduction
The no-three-in-line problem is an old question (see Dudeney 1917) which asks for the maximum number of points that can be placed in the \(n \times n\) grid with no three points collinear. This question has been widely studied (see Erdös 1951; Flammenkamp 1992, 1998; Guy and Kelly 1968; Hall et al. 1975), but is still not resolved.
In this paper we consider the no-three-in-line problem over the \(\mathbb Z_n^2\). This modified problem is still interesting and was investigated in Huizenga (2006), Kurz (2009) and Misiak et al. (2016). Many authors considered arcs in the context of projective geometry, see e.g. Bose (1947), Segre (1955) and Hirschfeld (1979) for further reference, and in a context of Hjelmslev geometry, see e.g. Honold and Landjev (2001), Honold and Landjev (2005), Kiermaier et al. (2011) and Kleinfeld (1959) for definition of abstract Hjelmslev plane.
Advertisement
Four integers a, b, u, v with \(\gcd (u,v)\!=\!1\) correspond to the line \(\{(a+u k, b+v k):k\in \mathbb Z\}\) on \(\mathbb Z^2\). We define lines in \(\mathbb Z^2_n\) to be images, by natural projection, of lines in the \(\mathbb Z^2\) (see Misiak et al. 2016). We say that points \(a_1,\ldots ,a_k\) are in line on \(\mathbb Z^2_n\) (or collinear) if there exists a line l in \(\mathbb Z^2_n\) such that \(a_1,\ldots ,a_n\in l\). We would like to remark that one could also define a line as a coset of a (maximal) cyclic subgroup of \(\mathbb Z^2_n\) (see Huizenga 2006; Kurz 2009).
If \(n=p\) is a prime the resulting space is just \(\mathrm {AG}(2,p)\) where every two distinct lines intersect in either 0 or 1 point. In contrast, for arbitrary n it may happen that two distinct lines meet each other in more than a single point.
We call \(X\subset \mathbb Z^2_n\) an arc if it does not contain any three collinear points, and we call X complete if it is maximal with respect to the set-theoretical inclusion. We denote by \(\uptau (\mathbb Z^2_n)\) the maximum possible size of an arc in \(\mathbb Z^2_n\).
Kurz (2009) uses the integer linear programming to determine numbers \(\uptau (\mathbb Z^2_n)\). He identifies values of \(\uptau (\mathbb Z^2_n)\) for \(n \le 21\) and, after transformations, the value of \(\uptau (\mathbb Z^2_{25})\) (see also Kiermaier et al. 2011 for this case). We were interested in finding the lacking values of \(\uptau (\mathbb Z^2_{22})\) and \(\uptau (\mathbb Z^2_{24})\). Our first try was using the mathematical programming solver Gurobi. We succeed with computing \(\uptau (\mathbb Z^2_{24})\) but were not able to determine \(\uptau (\mathbb Z^2_{22})\) in this way. Therefore, we investigated some properties of arcs in \(\mathbb Z^2_{2p}\) for p prime, which allowed us to compute \(\uptau (\mathbb Z^2_{22})\).
Advertisement
We will use the following notation. Denote by \(\pi _n\) the natural projection from \(\mathbb Z\) to \(\mathbb Z_n\). If the context is clear, we omit the index n. For \(u=(u_x,u_y)\) we write \(\pi (u)\) for \((\pi (u_x), \pi (u_y))\). If p|n then by \(\phi _p\), we denote the projection \(\phi _p:\mathbb Z_n \rightarrow \mathbb Z_p\) defined by \(\phi _p \circ \pi _n = \pi _p\). Similarly, we write \(\phi _p(u)\) for \((\phi _p(u_x), \phi _p(u_y))\).
By automorphism of \(\mathbb Z_{n}^{2}\) we mean mapping from \(\mathbb Z_{n}^{2}\) to \(\mathbb Z_{n}^{2}\) which preserves arcs. The group formed by these elements is denoted by \(\mathcal G_{n}.\) Let \(GL_{2}(\mathbb Z_{2p})\) denote the group of invertible \(2\times 2\) matrices with coefficients in \(\mathbb Z_{2p}\). We denote by \(f_{A}\) the automorphism of \(\mathbb Z^{2}_{2p}\) corresponding to the matrix A. Another class of automorphisms are translations. In this paper \(t_{v}\) denotes the translation by a vector v. More explicitly, \(t_{(v_x,v_y)}(u_x,u_y)=(u_x+v_x, u_y+v_y)\).
It is easy to see that m(2, q) is an upper bound for \(\tau (\mathbb {Z}_p^2)\) in the case of a prime \(q=p\). To establish the lower bound for \(\tau (\mathbb {Z}_p^2)\), recall that there are arcs of \(\mathbb {Z}_p^2\) of cardinality \(p+1\) (see for instance Misiak et al. 2016 for more details). Therefore, the following lemma is true.
Lemma 2.2
Let p be an odd prime, then \(\uptau \left( \mathbb Z^{2}_{p}\right) =p+1.\)
Recall the well-known test to check whether three points are collinear or not.
Lemma 2.4
Points \(a, b, c \in \mathbb Z^2_p\) for p prime are in a line if and only if \(D(a,b,c)=0\).
The following lemma is adapted from Huizenga (2006).
Lemma 2.5
Let \(N = m\cdot n\) with coprime m and n. Then any three points in \(\mathbb Z^{2}_{N}\) are collinear if and only if both projections onto \(\mathbb Z^2_m\) and \(\mathbb Z^2_n\) give a collinear point set.
Theorem 2.6
Let \(p_1, p_2\) be primes such that \(p_1 \ne p_2\). Then points \(a, b, c \in \mathbb Z^2_{p_1 \cdot p_2}\) are in a line if and only if \(D(a,b,c)=0\).
Proof
Assume that \(D(a,b,c)=0\in \mathbb Z_{p_1 \cdot p_2}\). Consequently, \(D(\phi _{p_i}(a), \phi _{p_i}(b), \phi _{p_i}(c))=0\in \mathbb Z_{p_i}\) and by Lemma 2.4\(\phi _{p_i}(a), \phi _{p_i}(b), \phi _{p_i}(c)\) are in a line on \(\mathbb Z^2_{p_i}\) for \(i=1,2\). By Lemma 2.5a, b, c are in a line on \(Z^2_{p_1 \cdot p_2}\).
Conversely, assume that \(a,b,c\in \mathbb Z^2_{p_1 \cdot p_2}\) are in a line. There exists \(A,B,C\in \mathbb Z^2\) in a line such that \(\pi (A)=a\), \(\pi (B)=b\) and \(\pi (C)=c\). Hence, \(D(A,B,C)=0\in \mathbb Z\) and consequently \(D(a,b,c)=0\in \mathbb Z_{p_1 \cdot p_2}\). \(\square \)
Remark 2.7
Generally, zeroing of determinant is necessary but not sufficient for three points to be collinear. Let \(p^2|m\) for some prime p. Then for the points (0, 0), (p, 0), (0, p) we have
Let X be a complete arc of \(\mathbb Z^{2}_{p}\). Then \(\alpha _2(X)\) is the complete arc of \(\mathbb Z^{2}_{2p}\).
Proof
Let X be a complete arc of \(\mathbb Z^2_p\). Then \(\alpha _2(X)\) is obviously the arc of \(\mathbb Z^2_{2p}\). Let \(c\in \mathbb Z^{2}_{2p}\). We will show that there are \(a,b\in \alpha _2(X)\) such that a, b, c are collinear.
Assume first that \(c\in \phi ^{-1}_2(0,0).\) Then there is \(c'\in Z^{2}_{p}\) such that \(\alpha _2(c')=c.\) Since X is a complete arc then there exist \(a', b' \in X\) such that \(a',b',c'\) are collinear. By Theorem 2.4, \(D(a',b',c')=0\in \mathbb Z_{p}.\) Then \(D(\alpha _2(a'),\alpha _2(b'),c)=0\in \mathbb Z_{2p}.\) By Theorem 2.6, \(a=\alpha _2(a'),\)\(b=\alpha _2(b'),\)c are collinear.
Now assume that \(c\notin \phi ^{-1}_2(0,0).\) Then there is \(v\in \left\{ \left[ 0,p\right] ,\left[ p,0\right] ,\left[ p,p\right] \right\} \) such that \(t_{v}(c)\in \phi ^{-1}_2(0,0).\) Hence the first part of the proof shows that there are \(a,b\in \alpha _2(X)\) such that a, b, \(t_{v}(c)\) are collinear (i.e. \(D(a,b,t_{v}(c))=0\)). Because \(\alpha _{2}(X)\subset \phi ^{-1}_{2}(0,0),\) a straightforward calculation shows that \(D(a,b,c)=D(a,b,t_{v}(c))\) for \(a,b\in \alpha _{2}(X).\) Hence \(D(a,b,c)=0\) and a, b, c are collinear, by Theorem 2.6. This completes the proof. \(\square \)
Lemma 3.4
Let X be a complete arc of \(\mathbb Z^{2}_{2}\). Then \(\alpha _{p}(X)\) is the complete arc of \(\mathbb Z^{2}_{2p}\).
Proof
Let X be a complete arc in \(\mathbb Z^{2}_{2}.\) Then \(X=\mathbb Z^{2}_{2}\) and \(\alpha _p(X)\) is obviously the arc of \(\mathbb Z^2_{2p}\). It is easy to check that for every \(c \in Z^{2}_{2p}\) there is \(b\in \alpha _{p}(X)\backslash {(0,0)}\) such that \(D((0,0),b,c)=0.\) By Theorem 2.6, (0, 0), b, c are collinear. \(\square \)
The proof of the Theorem 3.9 takes up the rest of this section. We prepare for the proof by collecting together some useful technical results.
Lemma 3.5
Let \(\sigma \) be an arbitrary permutation of the set \(\mathbb Z^{2}_{2}\). Then there is \(f\in \mathcal G_{2p}\) such that \(\phi _{2}\circ f =\sigma \circ \phi _{2}.\)
Proof
Let \(f_{A},\)\(f_{B}\) be linear transformations determined by matrices \(A=\begin{pmatrix} 1 &{} 0\\ 1 &{} 1\\ \end{pmatrix}\), \(B=\begin{pmatrix} 0 &{} 1\\ 1 &{} 0\\ \end{pmatrix}\), respectively. Note that the group of permutations of the set \(\mathbb Z^{2}_{2}\) is generated by transpositions \(\sigma _{1}=\left( {\scriptstyle (0,0), (0,1)}\right) \), \(\sigma _{2}=\left( {\scriptstyle (0,1), (1,0)}\right) \), \(\sigma _{3}=\left( {\scriptstyle (1,0), (1,1)}\right) \).
One can verify by a straightforward calculation that \(\phi _{2}\circ f_{A}\circ t_{\left[ 1,1\right] }=\sigma _{1}\circ \phi _{2}\), \(\phi _{2}\circ f_{B}=\sigma _{2}\circ \phi _{2} \) and \(\phi _{2}\circ f_{A}=\sigma _{3}\circ \phi _{2}\). \(\square \)
Lemma 3.6
Let \(X\subset \mathbb Z^{2}_{2p}\) be an arc. If \(\left| \phi _2\left( X\right) \right| \le 2\), then \(|X|\le p+1.\)
Proof
The condition \(\left| \phi _2\left( X\right) \right| \le 2\) means that \(\phi _2\left( X\right) \) is collinear in \(\mathbb Z^{2}_{2}.\) Since X is an arc then, by Lemma 2.5, \(\phi _p\left( X\right) \subset \mathbb Z^{2}_{p}\) is an arc and \(|\phi _p\left( X\right) |=|X|\). By Lemma 2.2, \(|X|\le p+1.\)\(\square \)
Lemma 3.7
Let \(X\subset \mathbb Z^{2}_{2p}\) be an arc and \(a\in X\). If \(t_{v}(a)\in X\) for some \(v\in \left\{ \left[ 0,p\right] ,\left[ p,0\right] ,\left[ p,p\right] \right\} ,\) then \(|X|\le p+3.\)
Proof
Consider first the case that \(v=[0,p].\) Let \(l_0=\pi (L_{0})\) and \(l_1=\pi (L_{1})\) denote the lines in \(\mathbb Z^{2}_{2}\), where \(L_0\) and \(L_1\) are given by the equations \(x=0\), \(x=1\), respectively. Assume without loss of generality that \(a\in \phi _2^{-1}\left( l_{0}\right) .\) A straightforward calculation shows that \(D(a,t_{[0,p]}(a),b)=0\) for all \(b\in \phi _2^{-1}\left( l_{0}\right) .\) Hence, by Theorem 2.6, \(X\subseteq \left( \phi _2^{-1}\left( l_{1}\right) \cup \left\{ a,t_{[0,p]}(a)\right\} \right) .\) The same argument as in Lemma 3.6 shows that \(\left| X\cap \phi _2^{-1}\left( l_{1}\right) \right| \le p+1.\) The remaining two cases are dealt with similarly. \(\square \)
Lemma 3.8
Let \((a_{x},a_{y})\in \mathbb Z^{2}_{2p}\) and \(a_{y}\) is invertible in \(\mathbb Z_{2p}.\) If \(a_{y}b_{x}^{1}-b_{y}^{1}a_{x}=a_{y}b_{x}^{2}-b_{y}^{1}a_{x}=a_{y}b_{x}^{3}-b_{y}^{1}a_{x}=A\) then \(b^{1},\)\(b^{2},\)\(b^{3}\) are on line.
The result now follows from Theorem 2.6. \(\square \)
Theorem 3.9
Let \(p\ge 5\) and \(X\subset \mathbb Z^{2}_{2p}\) be an arc. If \(|X|>p+3\), then there is \(f\in \mathcal G_{2p}\) such that (0, 0), (1, 0), \((0,1)\in f(X).\)
Proof
By Lemmas 3.6 and 3.5 we may assume that \(\phi _2^{-1}\left( 0,0\right) \cap X \ne \emptyset ,\)\(\phi _2^{-1}\left( 0,1\right) \cap X \ne \emptyset \) and \(\phi _2^{-1}\left( 1,0\right) \cap X\ne \emptyset .\) Since \(|X|>8\) we may assume that \(|\phi _2^{-1}\left( 1,0\right) \cap X|\ge 3,\) by Lemma 3.5. We may also assume that \((0,0)\in X\). For if not, then we may translate X by a vector \([-u,-v]\) for some \((u,v)\in \phi _2^{-1}\left( 0,0\right) \cap X\). Let \((a_{x},a_{y}) \in \phi _2^{-1}\left( 0,1\right) \cap X.\) Then possibilities for \(a_{y}\) are: (i) \(a_{y}=p,\) (ii) \(a_{y}\) is invertible in \(\mathbb Z_{2p}.\)
Fig. 3
A complete arc of cardinality 20 over \(\mathbb Z^2_{24}\)
Fig. 4
Backtracking search
×
×
In the case (i), the assumption that \(|X|>p+3\) and by Lemma 3.7 imply that \(a_{x}\ne 0.\) Hence \(a_{x}b_{y}-b_{x} a_{y}\ne p\) for all \((b_{x},b_{y}) \in \phi _2^{-1}\left( 1,0\right) \cap X.\)
In the case (ii), the assumption that \(|\phi _2^{-1}\left( 1,0\right) \cap X|\ge 3\) and Lemma 3.8 imply that there is \((b_{x},b_{y}) \in \phi _2^{-1}\left( 1,0\right) \cap X\) such that \(a_{x}b_{y}-b_{x} a_{y}\ne p.\)
In both cases, there is \((b_{x},b_{y})\in \phi _2^{-1}\left( 1,0\right) \cap X\) such that \(a_{x}b_{y}-b_{x} a_{y}\) is invertible in \(\mathbb Z_{2p}.\) Then the map \(f_{A}\) with matrix \(A=\frac{1}{a_{x}\cdot b_{y}-b_{x}\cdot a_{y}}\begin{pmatrix} b_{y} &{} -b_{x}\\ -a_{y} &{} a_{x} \\ \end{pmatrix}\) maps
Computing \(\uptau (\mathbb Z^2_{24})\) was quite easy. We used the mathematical programming solver Gurobi. After expanding 12946227 nodes (602109089 simplex iterations) the solver found the solution depicted in Fig. 3. On the other hand, using the solver to compute \(\uptau (\mathbb Z^2_{22})\) was not successful.
Fig. 5
A complete arc of cardinality 12 over \(\mathbb Z^2_{14}\)
Fig. 6
A complete arc of cardinality 18 over \(\mathbb Z^2_{22}\)
×
×
Consequently, we used a more direct approach. For finding the value of \(\uptau (\mathbb Z^2_{2p})\) we implemented backtracking search algorithm depicted in Fig. 4. Figures 2, 5 and 6 show results of our search. Note that it is easy to find these complete arcs. The difficult part is showing that there are no bigger ones.
To limit searching space we made some optimizations. Thanks to Theorem 3.9 we start with the set (0, 0), (1, 0), (0, 1) (lines 29–31). Since the initial set is symmetric, after checking the fourth point (x, y) (line 34) we can exclude (y, x) from further search (line 35 and 36). After choosing a point (x, y) (line 3 and 4) we can also exclude points \(t_{[p,0]}(a)\), \(t_{[0,p]}(a)\) and \(t_{[p,p]}(a)\) from further search (lines 8–11 and Lemma 3.7). The program presented here is simplified, the real computations were performed in parallel.
For reference we present in Table 1 all known values of \(\uptau (\mathbb Z^2_m)\) for nonprime m (bold numbers are computed by us). Recall that \(\uptau (\mathbb Z^2_2)=4\) and \(\uptau (\mathbb Z^2_p)=p+1\) for primes \(p>2\). We also attach a table with some lower and upper bounds for non-prime \( 26\le n\le 40\) found by computer search or application of Lemma 2.3 (Table 2). Note that with the exception of \(n = 3^3\) and \(n = 2^5\), upper bounds are derived from Lemma 2.3. We were not able to improve them using numerical computations. The corresponding examples for the lower bounds can be found in Table 3.
Acknowledgements
The authors are grateful to the reviewer whose valuable suggestions resulted in a better organized and improved paper.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
