A379299 a(n) is the maximum number k such that every permutation of the integers mod n admits at least k collinear triples.

0, 0, 1, 0, 2, 0, 3, 0, 5, 2, 5, 0, 6, 9, 6, 4, 8

Offset: 1

Author

Joshua Cooper, Dec 20 2024

Keywords

• nonn
• more

Comments

Three points (x_i,y_i), i=1,2,3, are collinear if x_1*(y_2-y_3) + x_2*(y_3-y_1) + x_3*(y_1-y_2) == 0 (mod n).

Exhaustive search in SageMath obtained the reported values from Cooper and Solymosi 2004, where the authors show that (n-1)/4 <= a(n) <= (n-1)/2 for every odd prime n. In Li 2008, the author shows that a(n) = (n-1)/2 for every odd prime n.

Examples

			a(5)=2 because the permutation (in one-line notation) 0,1,3,2,4 admits two collinear triples mod 5: {(0,0),(1,1),(4,4)} is on the line y=x and {(0,0),(3,2),(2,3)} is on the line y=4*x; and all other permutations admit at least 2 collinear triples.
		

Links

• Joshua Cooper and Jack Hyatt, Permutations minimizing the number of collinear triples, arXiv:2501.02331 [math.CO], 2025. See p. 7.
• Joshua N. Cooper and József Solymosi, Collinear points in permutations, Ann. Comb. 9 (2005), no. 2, 169-175; preprint, arXiv:math/0408396 [math.CO], 2004.
• Liangpan Li, Collinear triples in permutations, Innov. Incidence Geom. 8 (2008), 171--173; arXiv preprint, arXiv:0805.0410 [math.CO], 2008.

Crossrefs

Cf. A272651, A000769, A000755, A000938.

Formula

a(n) = (n-1)/2 for odd primes n.