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{align*} T(\mathbb{Z}_p \times \mathbb{Z}_{p^2}) &= 2p, \\ T(\mathbb{Z}_p \times \mathbb{Z}_{pq}) &= p+1. \end{align*} 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 [MR41889]; the construction goes via a parabola modulo $p$. Other more complicated constructions manage to place more points [MR366817].

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 [MR554919], the question is interesting for, say, $G = S_n$ or $G = A_n$ where, say, Bezout's theorem doesn't make sense anymore.

Download from the ArXiv