gpt 6 astra ultra attempt on Math-535

The No-Three-in-Line Problem in a Square Grid

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

For $A\subseteq[N]^2\subset{\mathbb{R}}^2$, the condition is that no Euclidean straight line contains three distinct points of $A$. Let $g(N)$ be the maximum of $|A|$ over such sets. Every horizontal grid line contains at most two chosen points, so $g(N)\leq2N$. The highlighted question asks whether equality eventually becomes impossible. [S1] [S2]

Statement recorded in the supplied source.

What is the largest subset of the grid $[N]^2$ with no three points on a line? In particular, for $N$ sufficiently large, is it impossible to have a set of size $2N$ with this property? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove eventual strict inequality D(N)<2N, construct 2N examples for infinitely many N, or narrow the general 3N/2 versus 2N gap. [S1]

Short English statement

What is the largest selection of grid points with no three collinear, and can the elementary upper bound of twice the side length persist indefinitely?

Research attempt

Provenance and scope.

This individual attempt was generated by GPT-6 Astra Ultra on 1 October 2026. The method was to derive explicit partial results and test the first proposed extension adversarially. The original statement and sources below are retained. No claim of mathematical novelty or complete solution is made.

Formal target and current source check.

Let $g(N)$ be the largest subset of $[N]^2$ with no three distinct collinear points in the Euclidean plane. The question singles out whether $g(N)=2N$ can persist for arbitrarily large $N$. Prellberg's inspected 2026 manuscript reports constructions attaining $2N$ through $N=60$; this is finite evidence, not an asymptotic resolution. We analyse the rigid row-column structure forced by equality and test a natural attempt to double a modular parabola.

Equality forces two permutation graphs.

Every row contains at most two selected points, giving $g(N)\leq2N$. If equality holds, every row contains exactly two points. Applying the same argument to columns shows that every column also contains exactly two. Regard the selected points as edges of a bipartite graph with row vertices on one side and column vertices on the other. This graph is simple and every vertex has degree two. Each connected component is therefore a cycle, and bipartiteness makes its length even. Alternately colouring its edges gives two disjoint perfect matchings after the colours are combined over all components.

Consequently every equality example can be written \[ A=\{(i,\sigma(i)):1\leq i\leq N\} \cup\{(i,\tau(i)):1\leq i\leq N\}, \] where $\sigma,\tau$ are permutations and $\sigma(i)\ne\tau(i)$ for all $i$. Conversely such a pair automatically has exactly two points per row and column, but it need not avoid other collinear triples. Thus the representation is a necessary structural reduction, not a construction theorem. The remaining restrictions can be expressed exactly by requiring \[ (x_2-x_1)(y_3-y_1)\ne(x_3-x_1)(y_2-y_1) \] for every three distinct selected points. The determinant criterion avoids slope division and includes vertical lines correctly.

A modular parabola gives a verified baseline.

For an odd prime $p$, take the $p$ integer points \[ P_p=\{(x,r_x):0\leq x<p,\ r_x\equiv x^2\pmod p, \ 0\leq r_x<p\}. \] If three distinct points were collinear over the integers, their determinant would vanish modulo $p$. A nonvertical line over ${\mathbb{F}}_p$ intersects the parabola $y=x^2$ in at most two points, since substitution gives a nonzero quadratic polynomial. A vertical line contains at most one point of the graph. Since distinct selected integer $x$-coordinates remain distinct modulo $p$, three points cannot collapse to fewer points upon reduction. This proves that $P_p$ has no three collinear. Translation by $(1,1)$ embeds it in $[p]^2$.

The modular argument uses a one-way implication: an integer collinearity would imply a modular one. Modular collinearity need not imply integer collinearity, because the determinant may be a nonzero multiple of $p$. Thus modular exclusion is a sufficient certificate, sometimes stronger than necessary.

Doubling the parabola fails explicitly.

A tempting construction is to take the union of $y=x^2$ and $y=x^2+1$ modulo $p$, lifted to the same integer square. Each piece is individually certified by the previous argument, but mixed triples can occur. For $p=5$, the first graph contains $(0,0)$ and $(2,4)$, while the shifted graph contains $(1,2)$. Those three points are collinear on $y=2x$. The same displayed triple occurs for every prime $p>5$, because the relevant values zero, two, and four do not wrap modulo $p$. Hence this particular doubling proposal fails for every sufficiently large prime, not just in a small exceptional example.

This counterexample also explains why certifying each matching or each curve separately is insufficient. A union can create triples using points from both parts. In the equality representation by two permutations, both pure triples within one graph and mixed triples across the graphs must be excluded. The row-column constraints alone do not see this interaction.

Verification and the unresolved gap.

The companion script checks all triples in $P_p$ for $p=3,5,7,11$ using the integer determinant, with no violations. These checks accompany the general polynomial proof and are not its justification. The explicit bad triple in the doubled construction is checked directly before any modular reduction. For $N=1$, the grid has only one point, so the $2N$ equality discussion is conditional and does not assert existence. The two-matching decomposition remains valid for every actual equality example.

The established output is a complete necessary normal form for $2N$ examples, an elementary infinite family of size $p$, and an infinite obstruction to a natural doubling attempt. The first remaining gap is either constructing two permutations that avoid all mixed determinants for unbounded $N$, or proving that no such pairs exist beyond a fixed threshold. The finite computational record through sixty and the modular baseline do not decide that asymptotic question.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 133 (GREEN-045), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Thomas Prellberg, Constraint Satisfaction Programming for the No-three-in-line Problem, arXiv:2602.07751 $2026$. https://arxiv.org/abs/2602.07751. Bibliographic information from the supplied record.

• S3 Alexandr Grebennikov and Matthew Kwan, No-$k+1$-in-line problem for large constant k, arXiv:2510.17743 $2025$. https://arxiv.org/abs/2510.17743. Bibliographic information from the supplied record.

• S4 Ben Green, 100 Open Problems, current Problem 72. https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf. The author-hosted document was inspected on 27 September 2026; the archive’s local code is not a problem-number locator in this paper.

• E1 T. Prellberg, Constraint Satisfaction Programming for the No-three-in-line Problem, 2026. https://arxiv.org/abs/2602.07751. Inspected 1 October 2026.