Fact-checked by Grok 2 weeks ago

No-three-in-line problem

The no-three-in-line problem is a classic question in discrete geometry that seeks the maximum number of points that can be placed on an n × n integer lattice grid such that no three points are collinear.^[1] Posed by the English mathematician and puzzle designer Henry Ernest Dudeney in 1917, the problem requires avoiding collinear triples not only in horizontal, vertical, or diagonal directions but along any straight line in the plane.^[2]^[3] A straightforward upper bound on the maximum number t(n) of such points is 2n, as no row or column can contain more than two points without forming a collinear triple.^[4] Constructions achieving exactly 2n points exist for all n up to 58, including computational solutions using branch-and-bound algorithms and constraint satisfaction methods.^[2] However, it remains an open question whether t(n) = 2n for every positive integer n, with the challenge intensifying for larger n due to the increasing complexity of avoiding all possible lines.^[1]^[5] Asymptotic lower bounds guarantee at least (3/2 - ε)n points for any ε > 0 and sufficiently large n, building on early results by Paul Erdős and later improvements.^[3] The problem has inspired extensive research, including generalizations to higher dimensions—where up to Θ(n²) points are possible in 3D without three collinear—and connections to combinatorial geometry, such as Roth's theorem on arithmetic progressions.^[3] Despite over a century of study, no counterexample to the 2n conjecture has been found, making it one of the oldest unsolved problems in combinatorial geometry.^[2]

Problem statement

Definition

The no-three-in-line problem asks for the maximum number t(n) of points that can be placed on the n \times n integer grid \{1, 2, \dots, n\} \times \{1, 2, \dots, n\} such that no three points are collinear.^[6] This grid consists of n^2 lattice points with integer coordinates in the first quadrant, bounded by the lines x = 1, x = n, y = 1, and y = n.^[7] Three points (x_i, y_i), (x_j, y_j), and (x_k, y_k) on this grid are collinear if they lie on the same straight line in the Euclidean plane, meaning any slope is possible—not just horizontal, vertical, or grid-aligned directions. Mathematically, this occurs precisely when the following equation holds:

x_i (y_j - y_k) + x_j (y_k - y_i) + x_k (y_i - y_j) = 0.

This condition arises from the vanishing of the signed area of the triangle formed by the three points, equivalent to the determinant criterion for collinearity in the plane. The problem requires selecting a subset of the grid points that avoids any such triple, maximizing the subset size while preserving this general position property. Trivially, t(n) \leq n^2, as this is the total number of grid points, but a tighter bound follows from the pigeonhole principle: since any three points in the same row or column are collinear, at most two points can be chosen per row (or per column), yielding t(n) \leq 2n.^[6] The no-three-in-line problem is a classic question in discrete geometry concerning the maximum size of a set in general position within a finite lattice.^[7]

Conjecture

The central conjecture of the no-three-in-line problem, attributed to Henry Dudeney, states that the maximum number of points t(n) that can be placed on an n \times n grid with no three collinear is exactly $2nfor every positive [integer](/page/Integer)n. This would imply both that t(n) \geq 2n

is achievable via suitable constructions and that &#36;2n

is the tight upper bound. The upper bound t(n) \leq 2n follows immediately from the pigeonhole principle applied to the rows (or columns) of the grid: with n rows available, placing more than $2n

points would force at least three points into some single row by the [pigeonhole principle](/page/Pigeonhole_principle), and points in the same row are collinear. Achieving exactly &#36;2n

points thus requires distributing precisely two points per row (and per column) while ensuring no three points are collinear in any other direction. Supporting evidence for the lower bound t(n) \geq 2n includes explicit constructions that place $2npoints with no three collinear for everynup to 58 as of 2025,[2] with ongoing computational verifications.[22] For primen = p, an algebraic construction places ppoints at coordinates(i, 2^i \mod p)fori = 0, 1, \dots, p-1, ensuring no three are collinear due to properties of exponential functions modulo p

; later generalizations of such algebraic methods, often combining multiple curves or permutations, extend this to achieve &#36;2n

points for general n.^[8] If the conjecture holds, it provides the exact solution to the problem and highlights deep connections to finite geometry, where sets of $2npoints with no three collinear correspond to maximum [cap set](/page/Cap_set)s in the affine plane over\mathbb{Z}/n\mathbb{Z}$, analogous to cap set problems in higher-dimensional vector spaces over finite fields.

Small instances

Configurations for n ≤ 10

For small values of n \leq 10, the maximum number t(n) of points that can be placed on an n \times n grid with no three collinear is t(1) = 1 and t(n) = 2n for $2 \leq n \leq 10. This value is achieved by constructions that place precisely two points per row (and typically per column as well), while ensuring no three points align on any line of other slopes. Moreover, $2n is maximal for these n (and 1 for n=1), since placing more than $2n points would force at least one row to contain three points by the pigeonhole principle, and any three points in the same row are collinear.^[1] The following table summarizes these exact values:

n	t(n)
1	1
2	4
3	6
4	8
5	10
6	12
7	14
8	16
9	18
10	20

These results follow from exhaustive enumeration and verification for small n.^[1] For n=3, a simple explicit configuration achieving 6 points is (1,1), (1,2), (2,1), (2,3), (3,2), (3,3). No three of these points are collinear: each row and column has exactly two points, the main diagonal passes through only (1,1) and (3,3) (missing the middle), the anti-diagonal passes through only (1,2) and (2,1) (with the third off-grid), and lines of other slopes (e.g., slope $1/2 or $2) intersect at most two grid points in this set. For n=3, adding a seventh point to any such 6-point configuration forces three collinear, confirming maximality.^[1] Configurations for n=4 to n=6 can be constructed similarly by selecting two positions per row in distinct columns, perturbing to avoid diagonal alignments; for example, for n=4, one valid set uses points at (1,1), (1,4), (2,2), (2,3), (3,1), (3,3), (4,2), (4,4), verifiable by checking all lines with rational slopes passing through at least two points. For n \leq 10, the existence of maximum configurations has been confirmed via computer-assisted enumeration of all possible placements, ruling out collinear triples.^[2]

Challenges for larger n

Determining whether constructions achieving t(n) = 2n exist becomes increasingly difficult for n > 10 due to the prohibitive computational cost of searches. Algorithms using backtracking or branch-and-bound to place 2n points while ensuring no three are collinear (beyond rows and columns) are feasible up to larger n, but the search space grows exponentially.^[1] For n = 11, constructions achieve 22 points with no three collinear, and since t(n) ≤ 2n always, this establishes t(11) = 22 exactly. Similar constructions exist for larger n.^[9]^[10] Constructions achieving t(n) = 2n have been computed for all n up to 58 as of October 2025, using optimized algorithmic searches that exploit symmetries to reduce the search space.^[2] Key obstacles include the explosion in the number of potential lines, with roughly n²/2 distinct slopes to monitor, exponentially increasing the complexity of avoiding collinear triples. Theoretical hurdles, such as links to blocking sets in projective planes, further impede progress toward general proofs of existence for all n.^[2]

Bounds and constructions

Lower bounds

The simplest lower bound of t(n) \geq n follows from selecting one point per row in distinct columns, forming a permutation matrix where no row or column has more than one point, thus avoiding three collinear points in horizontal or vertical lines; slanted lines are avoided by the permutation choice.^[1] A basic explicit construction achieving t(n) \geq 2n for small n places two points per row in a staggered manner to minimize alignments. For instance, attempting positions like (i, i \mod n) and (i, (i+1) \mod n) for rows i = 1 to n often requires adjustments to break potential diagonal or slanted lines, such as shifting columns for specific rows. This row-filling approach respects the upper bound of two points per row (to avoid horizontal triples) and can be verified computationally for n \leq 10.^[2] For prime n = p, algebraic constructions using the finite field \mathbb{F}_p yield t(p) \geq p via the set of points (i, i^2 \mod p) for i = 0, \dots, p-1. No three points are collinear because any line intersects this parabolic arc in at most two points, as the equation of a line through three such points would imply a quadratic equation over \mathbb{F}_p with three roots, which is impossible unless identical. This was observed by Erdős. Extending to $2p points for prime p involves union of two such quadratic sets with distinct leading coefficients, chosen to ensure no cross-alignments create three collinear points across sets.^[11] Hall, Jackson, Sudbery, and Wild generalized these algebraic methods in 1975 to achieve t(n) \geq n for all n, adapting modular constructions to composite cases without relying on primality. They further provided the best known general lower bound of t(n) \geq (3/2 - \epsilon)n for any \epsilon > 0 and sufficiently large n, using placements on hyperbolic curves like xy \equiv k \mod m over suitable moduli m \approx 2n/3, ensuring no line contains three points by bounding intersections. This asymptotic result remains the strongest proven for arbitrary n.^[11] Explicit constructions achieving the conjectured t(n) = 2n exist for all n \leq 58, obtained via computational searches or refined manual adjustments building on the staggered row placements and algebraic ideas. For example, configurations with 116 points on the $58 \times 58 grid have been verified to have no three collinear as of October 2025, using constraint satisfaction methods by Thomas Prellberg. These demonstrate that the bound is tight up to this scale, though no general proof exists for all n.^[2]

Upper bounds

The trivial upper bound for the maximum number of points t(n) that can be placed on an n \times n grid with no three collinear is t(n) \leq 2n, as each of the n horizontal (or vertical) lines can contain at most 2 points from the set, or else three would be collinear on that line.^[2] Early non-trivial improvements came from K. F. Roth's 1951 work on a related combinatorial problem, which was adapted to show t(n) \leq 2n - c \sqrt{n} for some constant c > 0, using estimates on the distribution of points to force collinearities in certain configurations.^[12] The proof relies on counting the number of lines determined by pairs of points and bounding the possible alignments in the grid. Subsequent advances applied incidence geometry, particularly the Szemerédi–Trotter theorem, which bounds the number of incidences between points and lines in the plane. For a set of m points on the grid with no three collinear, the lines containing exactly 2 points from the set induce O(m^2) incidences, but considering all potential grid lines (there are O(n^2) lines containing at least 3 grid points), the theorem implies that if m > 2n - \Omega(n^{1/3}), then some line must contain at least 3 points from the set, yielding t(n) \leq 2n - \Omega(n^{1/3}). This approach counts incidences I between the points and candidate lines; since each line has at most 2 points, I \leq 2 \times O(n^2) = O(n^2), but the Szemerédi–Trotter bound I = O(m^{2/3} n^{4/3} + m + n^2) forces a contradiction for sufficiently large m unless collinearities occur. No major tightenings have occurred since the 2010s, with efforts focusing instead on explicit constructions approaching 2n for finite n.

General construction methods

One common approach to constructing no-three-in-line sets involves permutation-based methods, where points are placed using two permutations of the set {1, 2, ..., n} to ensure exactly two points per row and per column. Specifically, the points are given by (i, π(i)) and (i, σ(i)) for i = 1 to n, where π and σ are permutations chosen such that no three points are collinear. This can be achieved using pairs of mutually orthogonal Latin squares of order n, which define the permutations by superimposing the squares to guarantee that the resulting positions avoid collinear triples through orthogonality properties that ensure unique pair representations. Such constructions leverage the combinatorial structure of Latin squares to control the distribution of points, preventing alignments in rows, columns, or diagonals.^[13] Geometric methods focus on selecting points to avoid repeated slopes between pairs, thereby ensuring no three are collinear. A greedy algorithm in this vein adds points sequentially, at each step choosing a grid position that does not lie on any line determined by two existing points, effectively avoiding forbidden slopes from the current set. This approach prioritizes local avoidance of collinearities and can be refined by ordering the grid traversal to maximize the final set size, often achieving close to the conjectured 2n points for moderate n. The method's effectiveness stems from the finite number of possible lines through existing points, allowing incremental building while maintaining general position.^[14] Advanced constructions draw from finite geometry and block designs to produce larger sets for specific n, such as primes. For prime p, Erdős's original method places points at (k, k^2 \mod p) for k = 0, 1, ..., p-1, forming a parabolic arc in the finite field \mathbb{F}_p that avoids three collinear points because any line intersecting the parabola at three points would imply a quadratic equation with three roots, contradicting the degree unless the points coincide. This was extended by Pór and Woodall to all n using a similar quadratic construction over composites by decomposing into prime power blocks and adjusting for modular arithmetic, ensuring no three align by preserving the second-difference property of quadratics. Further refinements use projections from finite geometries or block designs, such as quadratic residues modulo p to select subsets with controlled collinearities. These algebraic techniques provide rigorous guarantees for certain n and inspire hybrid methods.^[15]

Asymptotic and conjectured results

Asymptotic bounds

The asymptotic behavior of the no-three-in-line problem is captured by the limits of t(n)/n as n \to \infty, where t(n) denotes the maximum number of points that can be placed in the n \times n grid with no three collinear. Constructions achieving t(n) = 2n exist for all n up to at least 58, implying \liminf t(n)/n \ge 2.^[2] The trivial upper bound t(n) \le 2n, obtained by noting that each row can contain at most two points (as three would be collinear horizontally), yields \limsup t(n)/n \le 2.^[1] Although the best proven lower bound applicable to all n is t(n) \ge (3/2)n - o(n), the existence of $2n-point configurations for successively larger n supports the lower limit of 2.^[2] The problem implies that the maximum size of a set in general position in the ^2 grid is \Theta(n), corresponding to a density of \Theta(1/n) relative to the total n^2 points. This aligns with broader results in additive combinatorics, where the no-three-in-line condition avoids 3-term arithmetic progressions along lines; the Szemerédi density theorem guarantees that any subset of ^2 without 3-term arithmetic progressions has size o(n^2), consistent with the \Theta(n) bound here.^[16] The no-three-in-line problem serves as the 2-dimensional analog of avoiding combinatorial lines in higher dimensions, directly relating to the Hales-Jewett theorem, which asserts that sufficiently large grids in ^d contain unavoidable lines under any coloring.^[17] Recent work has explored related limit questions in competitions, such as a 2024 problem in the Ibero-American Inter-University Mathematical Competition examining the infimum of a normalized maximum over subsequences in a strip variant of the constraint, yielding a precise limit of $5/3.^[18]

Conjectured improvements

The Dudeney conjecture asserts that it is possible to place exactly 2n points in the n × n grid with no three collinear for every positive integer n. This remains open, though verified computationally for all n ≤ 58.^[2] Guy and Kelly proposed a conjectured improvement to this picture, arguing probabilistically that there are only finitely many such n, implying t(n) < 2n for all sufficiently large n.^[8] Initial algebraic constructions, such as placing points at (i, ai mod n) and (i, bi mod n) for suitable a and b, failed to avoid three collinear points when n ≡ 0 (mod 3), prompting speculation that t(n) < 2n might hold in those cases; however, this was disproved by alternative constructions achieving 2n points for all small n ≡ 0 (mod 3), with no verified exceptions to date.^[2] A central open question is whether t(n) = 2n holds for all n, or if there are infinitely many exceptions. In 2023, a new configuration achieving 2n points was discovered for n = 28, extending known examples. As of October 2025, additional solutions have been found for n up to 58, including new constructions for n = 47, 49, 51, 53, 54, 55, 56, and 58.^[2] Should the conjecture fail, the maximum is expected to satisfy t(n) = 2n - o(n), approaching the trivial upper bound asymptotically but falling short by a sublinear amount for infinitely many n.^[8]

Applications

In discrete geometry

In discrete geometry, sets arising from the no-three-in-line problem serve as exemplars of maximum-sized subsets in general position within the integer lattice \mathbb{Z}^2. A set of points is in general position if no three are collinear, and the n \times n grid provides a finite point set where the no-three-in-line construction yields subsets of size up to $2n, demonstrating that the general position number—the size of the largest such subset—is at least $2n for this lattice structure.^[19] These constructions highlight the challenges of selecting large general position subsets from structured point sets like lattices, where collinearities are prevalent due to the grid's alignment.^[20] The no-three-in-line problem also contributes to incidence geometry by providing explicit constructions of point sets with bounded point-line incidences, where each line contains at most two points from the set. Such sets offer lower bounds on the maximum size of configurations avoiding higher multiplicities, complementing upper bounds from the Szemerédi–Trotter theorem, which limits the total number of incidences I between n points and m lines to O((n^{2/3}m^{2/3} + n + m)). In the context of the n \times n grid, no-three-in-line sets achieve \Theta(n) points with at most two incidences per line, aiding in the study of extremal incidences and improvements to Szemerédi–Trotter variants in lattice settings.^[21]^[22] Connections to lattice point problems extend to additive combinatorics, where no-three-in-line sets relate to avoiding three-term arithmetic progressions in the coordinates of grid points. Collinear triples in the lattice often correspond to arithmetic relations in the x- and y-coordinates, linking the geometric avoidance of lines to additive structure without three points forming progressions along rational directions. This interplay informs bounds on progression-free subsets in \mathbb{Z}^2, drawing parallels between geometric general position and additive bases. In the 2020s, no-three-in-line constructions have been applied to variants of the Heilbronn triangle problem restricted to grid points, where the goal is to maximize the minimum area of triangles formed by the points. Scaling no-three-in-line sets from the n \times n grid to the unit square yields configurations where the smallest triangle area is \Omega(1/n^2), providing discrete analogues and lower bounds for Heilbronn-type questions on lattices while avoiding degenerate (zero-area) triangles via the no-collinearity condition. Recent work uses these sets to explore degeneracy avoidance in higher-dimensional lattice cubes, refining estimates for minimal areas in grid-based point configurations.^[23]

In combinatorial designs

The no-three-in-line problem has connections to the construction of mutually orthogonal Latin squares (MOLS), where sets of such squares can be used to generate point placements on the grid that avoid collinear triples. Specifically, for an order n where a complete set of n-1 MOLS exists (such as when n is a prime power), one can superimpose the squares to select points (i, \sigma_k(i)) for permutations \sigma_k derived from the squares, ensuring no three points align due to the orthogonality property that distinguishes row-column pairs uniquely across squares. This approach yields a no-three-in-line set of size n, though extensions to larger sets often combine it with algebraic constructions over finite fields. In coding theory, no-three-in-line sets correspond to constant-weight binary codes with specific minimum distance properties that prevent three codewords from satisfying collinearity conditions in the grid embedding. For instance, viewing grid points as codewords of weight 1 in a higher-dimensional space, the requirement of no three collinear translates to a minimum Hamming distance that avoids linear dependencies in their supports, akin to constant-weight codes used in error detection for combinatorial search problems. Such codes have been applied to construct evasive sets in finite geometries, where the no-three-in-line configuration provides bounds on covering radii and subspace incidences, paralleling error-correcting code designs that tolerate geometric "errors" like unintended alignments. The problem also relates to block design theory, particularly pairwise balanced designs (PBDs) where the blocks represent potential lines in the grid, and the design ensures that every pair of points appears in at most one block with a third point, thereby limiting lines to at most two selected points. In this framework, a no-three-in-line set of size m on an n \times n grid induces a PBD with block sizes up to 2, and extremal sizes inform the existence of designs with restricted replication numbers for pairs.^[24] This connection highlights applications in scheduling and experimental design, where avoiding triple incidences models constraints on resource allocations without over-concentration.^[24] A recent reformulation links the no-three-in-line problem to parafermion models in quantum information theory, offering new insights into quantum error correction. By modeling points as parafermion particles \psi_v in an algebra A(S_n) over the symmetric group, the condition of no three collinear corresponds to commuting operators that preserve a statistical ground state, yielding a lower bound of approximately (3/2)n + O(\sqrt{n}) points for large n.^[22] This parafermion approach connects to \mathbb{Z}_3 parafermions and anyonic systems in topological quantum computing, where such grid placements facilitate fault-tolerant error correction by encoding logical qubits in non-local states immune to local noise, as parafermion braiding statistics protect against decoherence in parafermion-based codes.^[22]

Generalizations

Higher dimensions

The higher-dimensional no-three-in-line problem generalizes the two-dimensional case to the d-dimensional grid ^d = \{1, \dots, n\}^d for d \geq 2, where t_d(n) denotes the maximum number of points that can be selected such that no three are collinear along any straight line in \mathbb{R}^d.^[25] A simple upper bound follows from considering lines parallel to one coordinate axis, say the d-th axis: there are n^{d-1} such lines (one for each fixed choice of the first d-1 coordinates), and each can contain at most two points to avoid three collinear, yielding t_d(n) \leq 2n^{d-1}. This bound holds analogously for lines parallel to any other axis. For the lower bound, a probabilistic compression construction places \gg \frac{n^{d-1}}{2^d \sqrt{d}} points with no three collinear, improving on prior algebraic methods and implying t_d(n) = \Theta(n^{d-1}).^[25] In three dimensions (d=3), the problem is particularly well-studied, with t_3(n) = \Theta(n^2). The upper bound t_3(n) \leq 2n^2 arises from the n^2 lines parallel to the z-axis, each allowing at most two points. Constructions achieve at least n^2/4 points, and more refined methods yield (1 - \epsilon)n^2 points for any \epsilon > 0 and sufficiently large n, using sets like V_p = \{(x, y, (x^2 + y^2) \mod p)\} over primes p \not\equiv 1 \pmod{4}.^[25]^[26] The compression approach gives a specific lower bound of \gg n^2 C_2 / (6 \sqrt{3}) for some constant C_2 > 0.^[25] No general conjecture for the optimal constant in t_d(n) \sim c_d n^{d-1} has been established beyond d=2, though the bounds suggest c_d \leq 2 from the axis-parallel argument.

Toroidal grids

The toroidal variant of the no-three-in-line problem is defined on the discrete torus modeled by the abelian group \mathbb{Z}_n \times \mathbb{Z}_n, where the goal is to place the maximum number of points such that no three lie on a common line. A line on the torus is a coset of a proper cyclic subgroup of \mathbb{Z}_n \times \mathbb{Z}_n of order at least 3, corresponding to periodic lines that wrap around the grid boundaries. This setup introduces additional collinearity constraints compared to the standard Euclidean grid, as directions can wrap modulo n.^[27] The maximum number t(n) of points satisfiable this condition obeys the upper bound t(n) \leq 2n, since the n horizontal rows form lines (each a coset of \langle (1,0) \rangle), allowing at most 2 points per row to avoid three collinear, and similarly for the n vertical columns. For the rectangular case on \mathbb{Z}_m \times \mathbb{Z}_n, the bound generalizes to t(m,n) \leq 2 \gcd(m,n). These periodic lines make the problem more restrictive than the plane grid version, often yielding stricter effective bounds for specific n.^[28] Constructions achieving large sets on toroidal grids leverage algebraic structures, particularly properties of finite abelian groups and commutative algebra techniques like Gröbner bases for verification. For instance, when n = p is prime, an explicit construction places p + 1 points on \mathbb{Z}_p \times \mathbb{Z}_p with no three collinear, using rotated configurations or elements from finite fields, achieving t(p) \geq p + 1. In rectangular cases like \mathbb{Z}_p \times \mathbb{Z}_{p^2} for prime p, algebraic placements based on quadratic forms achieve the bound t(p, p^2) = 2p. Such group-theoretic methods simplify constructions relative to the standard grid, as they exploit the modular arithmetic inherent to the torus.^[27] For composite n with \gcd(m,n) = p an odd prime and certain divisibility conditions (e.g., \gcd(pm, n) = p^2), constructions yield $2p points, as in sets formed by unions of scaled quadratic curves modulo n.^[28] Representative small values illustrate the variability: t(2) = 4 = 2 \cdot 2 (the full grid), t(3) = 4 < 2 \cdot 3, and t(4) = 6 < 2 \cdot 4, computed via exhaustive algebraic methods. Further analysis shows periodicity in the sequence t(kn, n) for fixed k, aiding predictions for larger n.^[27]^[29]

Extensible and k-in-line variants

The extensible variant of the no-three-in-line problem seeks a set S \subseteq \mathbb{Z}^2 in general position (no three points collinear) such that |S \cap [1,n]^2| is maximized for every n, ensuring the set remains viable across increasingly large finite grids without removal of prior points. This addresses a question posed by Joshua Erde on the asymptotic density \liminf_{n \to \infty} |S \cap [1,n]^2| / n. In a 2023 study, Nagy, Nagy, and Woodroofe constructed such a set achieving |S \cap [1,n]^2| = \Theta(n / \log^{1+\varepsilon} n) for any \varepsilon > 0, using separated copies of modular parabolas placed along curves like x / \log^\varepsilon x to limit collinear intersections. They employed a dynamic probabilistic method, akin to Rödl's nibble, adding points incrementally while deleting those forming triples, bounding deletions via double counting and concavity properties of the placements. Additionally, the authors provided an explicit construction yielding at least n/2 points in [1,n]^2 for infinitely many n, and proved that no such set can exceed $3n/2 points for infinitely many n, via pigeonhole arguments on line distributions.^[19] A related dynamic perspective involves building sets by adding points one by one to an n \times n grid without forming a collinear triple at any intermediate stage, often via greedy strategies that select the next viable point in a fixed ordering (e.g., lexicographic). The 2023 study connects this to extensible constructions, noting that greedy approaches, such as the lexicographically earliest sequence avoiding collinearities (OEIS A236335), produce sets in general position but with sizes growing sublinearly in practice for finite n; computational explorations suggest limits around $0.8n for column-wise greedy placements. Since any static no-three-in-line set of size $2n (known to exist) has all subsets in general position, adding its points in arbitrary order trivially achieves $2n dynamically without intermediate triples. However, the challenge intensifies under constrained orders or extensible requirements, where probabilistic dynamic methods ensure near-optimal growth.^[19] The k-in-line variant generalizes the problem to selecting the maximum number t_k(n) of points in an n \times n grid with no k collinear. Trivial constructions yield t_k(n) \geq (k-1)n by placing k-1 points per row, and upper bounds follow from averaging arguments over lines. For k=4, the bound is t_4(n) \leq 3n + o(n), reflecting the general t_k(n) \leq (k-1)n + o(n) via extremal graph theory on line-point incidences. A 2025 preprint by Kovács, Nagy, and Szabó settles the problem for large k, proving that for k \geq C \sqrt{n \log n} with C > (5/2)\sqrt{35} \approx 14.79, t_k(n) = kn exactly, using random bipartite graphs and concentration inequalities to construct full-row fillings without k+1 on any line; for k \geq (2/3)n, an explicit diagonal construction achieves this. These results highlight how the maximum transitions from sublinear to linear as k grows relative to n. In higher dimensions, subsets in general position extend the variant, such as no four coplanar points in ^4. A 2024 seminar at the University of California, Irvine, by Ji Zeng established a non-trivial upper bound on the maximum size of such a set, characterizing its asymptotic behavior through incidence geometry and providing the first sublinear constraint beyond the trivial $3n^3 + o(n^3). This builds on the no-three-in-line framework by replacing collinearity with coplanarity avoidance in 4D grids.^[30]

References

[1]
No-Three-in-a-Line-Problem -- from Wolfram MathWorld
It is possible to select 2n lattice points with x,y in [1,n] such that no three are in a straight line (where "straight line" means any line in the plane--not ...
[2]
No Three in Line Problem - Universität Bielefeld
The task is to mark as many of the intersection points of the n 2 grid points as possible under the condition that no three of them lie in a straight line.Introduction · Superficial Explanation · Sub No-3-in-line Solutions
[3]
https://arxiv.org/pdf/2106.15621.pdf
[4]
[PDF] Extensions of the No-Three-In-Line Problem? - TU Chemnitz
The No-Three-in-Line problem, which has been raised originally by Dudeney [7] ... upper bounds on fd(k +2, k, T) for integers k ≥ 1, in particular fd(k ...
[5]
Dudeney's No-Three-In-Line Problem - ACO Center @ UCI
What is the maximum number of points in an n x n grid such that no 3 points lie on a line? Here we mean not just vertical, horizontal, and diagonal lines, but ...
[6]
https://doi.org/10.4153/CMB-1968-062-3
[7]
[PDF] Variations on the No-Three-in-a-Line Problem arXiv:2311.13183v1 ...
Nov 22, 2023 · 1 Introduction. The no-three-in-a-line problem is an open problem first proposed by Henry. Dudeney in the early 20th century. It asks, what is ...
[8]
[PDF] No-three-in-line problem and parafermions - HAL
The no-three-in-line problem is to find the maximum number of points that can be placed in the n × n grid so that no three points lie on a line. This ...
[9]
The No-Three-In-Line Problem | Canadian Mathematical Bulletin
Nov 20, 2018 · We give a probabilistic argument to support the conjecture that there is only a finite number of solutions to the no-three-in-line problem.
[10]
Progress in the no-three-in-line-problem - ScienceDirect
Progress in the no-three-in-line-problem. Author links open overlay panel ... 10. R.R Hall, T.H Jackson, A Sudbery, K Wild. Some advances in the no-three ...
[11]
[PDF] Martin Gardner's minimum no-3-in-a-line problem
These included placements of queens on chessboards 3 × 3 through 12 × 12, which provided upper bounds on this number. ... Kelly, The no-three-in-line problem.
[12]
Progress in the No-Three-in-Line Problem, II - ScienceDirect.com
First solutions to the no-three-in-line problem forn=33, 37, 39, 41, 43, 45, 48, 50, 52 and for certain symmetry classes forn=26, 42, 44 are presented.
[13]
Some advances in the no-three-in-line problem - ScienceDirect
It is shown that for any n there exist subsets of an n × n square array containing n points, of which no three lie in a line.
[14]
https://arxiv.org/pdf/2209.01447.pdf
[15]
https://www.sciencedirect.com/science/article/abs/pii/S0195669823001130
[16]
https://arxiv.org/pdf/1208.5289
[17]
https://www.semanticscholar.org/paper/Extensions-of-the-No-Three-In-Line-Problem-Lefmann/f3b47d1a2bbdeb7e429cb4d7d2e03ffef5c4ebe0
[18]
The extensible No-Three-In-Line problem - ScienceDirect.com
The classical No-Three-In-Line problem seeks the maximum number of points that may be selected from an grid while avoiding a collinear triple.
[19]
[PDF] On the general position subset selection problem
to that of Lemma 1 in its use of the Szemeredi–Trotter theorem. ... vances in the no-three-in-line problem. J ... [25] Endre Szemerédi and William T. Trotter, Jr ...
[20]
[PDF] Extensions of the No-Three-In-Line Problem - Semantic Scholar
In this thesis we study various combinatorial problems relating to the geometry of point sets in the Euclidean plane. ... No-Three-in-Line-in-3D · A. PórD. Wood.
[21]
A limit problem involving the no-three-in-line constraint
Jul 9, 2025 · Therefore, 11 tiles in 6 consecutive blocks is not possible, so 10 must be the maximum since it is achievable by construction. So, there is a ...
[22]
[2209.01447] The extensible No-Three-In-Line problem - arXiv
Sep 3, 2022 · The classical No-Three-In-Line problem seeks the maximum number of points that may be selected from an n\times n grid while avoiding a collinear triple.
[23]
[PDF] The general position number of integer lattices - UNI-Lj
... general position set in G. This concept and terminology was introduced in [10], in part motivated by the cen- tury old Dudeney's No-three-in-line problem [3].
[24]
On the General Position Subset Selection Problem
Wild, Some advances in the no-three-in-line problem, J. Combin. Theory Ser ... The Szemerédi–Trotter theorem [Combinatorica, 3 (1983), pp. 381–392] ...<|control11|><|separator|>
[25]
Permutations minimizing the number of collinear triples
Apr 23, 2025 · We discuss a connection with complete sets of mutually orthogonal latin squares and state a few open problems primarily about general finite ...Missing: construction | Show results with:construction
[26]
Combinatorial Mathematics | SpringerLink
Some thoughts oh the no-three-in-line problem. Michael A. Adena, Derek A ... A class of block designs having the same parameters as the design of points ...
[27]
[2106.15621] On the general no-three-in-line problem - arXiv
Jun 29, 2021 · In this paper we show that the number of points that can be placed in the grid n\times n\times \cdots \times n~(d~times)=n^d for all d\in \mathbb{N} withMissing: proven | Show results with:proven
[28]
[1203.6604] The no-three-in-line problem on a torus - arXiv
Mar 29, 2012 · ... no three in a line," meaning no three in a coset of a cyclic subgroup of \Z_m \times \Z_n. By proving upper bounds and providing explicit ...Missing: definition | Show results with:definition
[29]
A note on the no-three-in-line problem on a torus
### Summary of arXiv:1406.6713
[30]
[1901.09012] No-three-in-line problem on a torus: periodicity - arXiv
Jan 25, 2019 · Title:No-three-in-line problem on a torus: periodicity ; Comments: Version 2: 19 pages, 4 figures; typos and computational mistakes corrected.Missing: toroidal | Show results with:toroidal
[31]
Variation of no-three-in-line problem | UCI Mathematics
Mar 6, 2024 · First, we give a non-trivial upper bound for the maximum size of a set in [n]4 such that no four are coplanar. Second, we characterize the ...