Putterman 2026 infinite sets no line

../

---

Moe Putterman, Mehtaab Sawhney, Gregory Valiant, On infinite sets with no $3$ on a line. arXiv:2602.21275 (2026). The arXiv record (https://arxiv.org/abs/2602.21275, read 2026-10-02) names the Creative Commons CC0 1.0 Universal public domain dedication. The folder-name PDF is arXiv v1 of 24 February 2026.

Theorem 1.1 gives an infinite A in R^2 such that every n-point subset P of A contains a subset of size at least n/2 with no three points collinear, yet A admits no partition into finitely many pieces each free of collinear triples. The construction indexes points by the 2-element subsets {i,j} of N, i < j, via P_{i,j} = (t_i + t_j, t_i^2 + t_i t_j + t_j^2) for an algebraically independent sequence (t_i). Claim 2.1 classifies collinear triples: P_{i,j}, P_{j,k}, P_{i,k} are collinear and every other pattern is not, verified by showing that each of the other determinants has a monomial with nonzero coefficient, so that algebraic independence keeps it nonzero. The two properties then follow from graph theory: identifying a point set with a graph, a bipartite subgraph keeps at least half the edges (first property), while a finite partition would give a triangle-free m-coloring of K_N, contradicting Ramsey's theorem (second property). The finitary version yields a lower bound of Omega(log k/log log k) parts for k points against an O(log k) upper bound. This resolves the question of Erdos, Nesetril and Rodl behind Erdos problem 846 with a short proof, avoiding density Hales-Jewett; Rodl noted it also follows from Reiher-Rodl-Sales. On the use of AI the paper says (Section 1.1, p. 1): "The construction and proof were generated by a model internal to OpenAI." The human authors then worked through the proof and rewrote it for human readers.

Source: https://arxiv.org/abs/2602.21275.

Bears on. #846

Results to transcribe.

• Theorem 1.1: There is an infinite A in R^2 where every n-point subset has a subset of size at least n/2 with no 3 collinear, yet A is not a finite union of sets with no 3 collinear.
• Construction: A = { (t_i + t_j, t_i^2 + t_i t_j + t_j^2) : i < j in N } for an algebraically independent sequence (t_i).
• Claim 2.1: Among distinct indices, P_{i,j}, P_{j,k}, P_{i,k} are collinear and the four other index patterns are not, so collinear triples correspond exactly to triangles in K_N.
• Finitary bound: For k points the construction forces Omega(log k/log log k) parts in such a partition, with an O(log k) upper bound from iterating the first property.