The no-three-in-line problem on a torus Joint work with Andrew Groot, Deven Pandya, Bart Snapp

For a group G , let T(G) denote the cardinality of the largest subset S \subset G so that no three elements of S are in the same coset of a cyclic subgroup. Undergraduates Andrew Groot and Deven Pandya, advised by myself and my colleague Bart Snapp, considered the case G = \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} , and showed that \begin{aligned} T(\mathbb{Z}_p \times \mathbb{Z}_{p^2}) &= 2p, \\ T(\mathbb{Z}_p \times \mathbb{Z}_{pq}) &= p+1. \end{aligned} This problem can also be formulated as a Gröbner basis question; after doing so, we computed T(\mathbb{Z}_m \times \mathbb{Z}_n) for 2 \leq m \leq 7 and 2 \leq n \leq 19 .

Thinking of a coset of a cyclic subgroup as a “line,” there is then connection with the usual “no three in line problem.” Paul Erdős proved that for a prime p , one can place p points on the p\times p lattice in the plane [1]; the construction goes via a parabola modulo p . Other more complicated constructions manage to place more points [2].

My interest lately has been considering the question for other groups. Although the no-three-in-line problem for G = (\mathbb{Z}/p\mathbb{Z})^2 can be considered as the k -arc problem from projective geometry [3], the question is interesting for, say, G = S_n or G = A_n where, say, Bezout’s theorem doesn’t make sense anymore.

[1] K.F. Roth, On a problem of Heilbronn, J. London Math. Soc. 26 (1951) 198–204. https://doi.org/10.1112/jlms/s1-26.3.198.

[2] R.R. Hall, T.H. Jackson, A. Sudbery, K. Wild, Some advances in the no-three-in-line problem, J. Combinatorial Theory Ser. A. 18 (1975) 336–341. https://doi.org/10.1016/0097-3165(75)90043-6.

[3] J.W.P. Hirschfeld, Projective geometries over finite fields, The Clarendon Press, Oxford University Press, New York, 1979.

Download from the ArXiv

 Download