Interesting Esoterica

The no-three-in-line problem on a torus

Article by Jim Fowler and Andrew Groot and Deven Pandya and Bart Snapp
  • Published in 2012
  • Added on
In the collections
Let $T(\mathbb{Z}_m \times \mathbb{Z}_n)$ denote the maximal number of points that can be placed on an $m \times n$ discrete torus with "no three in a line," meaning no three in a coset of a cyclic subgroup of $\mathbb{Z}_m \times \mathbb{Z}_n$. By proving upper bounds and providing explicit constructions, for distinct primes $p$ and $q$, we show that $T(\mathbb{Z}_p \times \mathbb{Z}_{p^2}) = 2p$ and $T(\mathbb{Z}_p \times \mathbb{Z}_{pq}) = p+1$. Via Grobner bases, we compute $T(\mathbb{Z}_m \times \mathbb{Z}_n)$ for $2 \leq m \leq 7$ and $2 \leq n \leq 19$.

Links


BibTeX entry

@article{Thenothreeinlineproblemonatorus,
	title = {The no-three-in-line problem on a torus},
	author = {Jim Fowler and Andrew Groot and Deven Pandya and Bart Snapp},
	url = {http://arxiv.org/abs/1203.6604v1 http://arxiv.org/pdf/1203.6604v1},
	urldate = {2019-12-10},
	year = 2012,
	abstract = {Let {\$}T(\mathbb{\{}Z{\}}{\_}m \times \mathbb{\{}Z{\}}{\_}n){\$} denote the maximal number of points that can be
placed on an {\$}m \times n{\$} discrete torus with "no three in a line," meaning no
three in a coset of a cyclic subgroup of {\$}\mathbb{\{}Z{\}}{\_}m \times \mathbb{\{}Z{\}}{\_}n{\$}. By proving upper
bounds and providing explicit constructions, for distinct primes {\$}p{\$} and {\$}q{\$},
we show that {\$}T(\mathbb{\{}Z{\}}{\_}p \times \mathbb{\{}Z{\}}{\_}{\{}p^2{\}}) = 2p{\$} and {\$}T(\mathbb{\{}Z{\}}{\_}p \times \mathbb{\{}Z{\}}{\_}{\{}pq{\}}) = p+1{\$}.
Via Grobner bases, we compute {\$}T(\mathbb{\{}Z{\}}{\_}m \times \mathbb{\{}Z{\}}{\_}n){\$} for {\$}2 \leq m \leq 7{\$} and
{\$}2 \leq n \leq 19{\$}.},
	comment = {},
	archivePrefix = {arXiv},
	eprint = {1203.6604},
	primaryClass = {math.CO},
	collections = {Fun maths facts,Geometry,Puzzles}
}