VibeMathedMath problems solved with AI
Sign in

North-East Lattice Paths with Few Collinear Vertices

Let A(k)A(k) be the largest possible number of moves in a north-east lattice path whose visited vertices contain no kk collinear points. Gerver (1979) and Gerver and Ramsey (1979) bounded A(k)A(k) byexp⁡(Ω(log⁡(k)2))≤A(k)≤exp⁡(O(k4)),\exp\left(\Omega\left(\log(k)^2\right)\right) \le A(k) \le \exp\left(O\left(k^4\right)\right),and determining the true growth rate has been open since. Both bounds are improved toexp⁡(Ω(k1/3))≤A(k)≤exp⁡(O(k2)),\exp\left(\Omega\left(k^{1/3}\right)\right) \le A(k) \le \exp\left(O\left(k^2\right)\right),with the upper bound proved in the sharper form exp⁡((2e+o(1))(k−1)2)\exp\left(\left(\tfrac{2}{e}+o(1)\right)(k-1)^2\right).

Result
Proved(see note)
Status
Partial result
AI contribution
AI-assisted
Method
Argument
Field
Discrete geometry - lattice paths
Posed by
Joseph L. Gerver, L. Thomas Ramsey
Year posed
1979
Years open
47y
Solved
2026-07-02
Model
GPT-5.5 Pro
Vendor
OpenAI
Collaborators
Samuel Korsky
Verification
Unreviewed
Publication
Preprint
Significance
15 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Both bounds move, and the gap stays enormous: the lower bound rises from exp⁡(Ω(log⁡2k))\exp(\Omega(\log^2 k)) to exp⁡(Ω(k1/3))\exp(\Omega(k^{1/3})) and the upper falls from exp⁡(O(k4))\exp(O(k^4)) to exp⁡(O(k2))\exp(O(k^2)), so A(k)A(k) is still undetermined between an exponent of k1/3k^{1/3} and one of k2k^2. The paper's own closing discussion argues its lower-bound construction is near the limit of the method and that beating it needs additional randomness, a sharper line-counting step, or a different model entirely.

What the AI did

The acknowledgement in full: the author was assisted by GPT-5.5 Pro in preparing the paper, but "the main construction ideas, including the dyadic-interval random variables in the lower bound and the density-increment framework in the upper bound, were due to the author". AI tools checked computations, assisted with drafting, and improved the upper-bound constant by suggesting the use of the mediant of the relevant Farey fractions. That last contribution is traceable in the text: it lifts the density increment from (1/8−o(1))(k−1)−2(1/8-o(1))(k-1)^{-2} to (1/4−o(1))(k−1)−2(1/4-o(1))(k-1)^{-2}, which is what produces the 2/e2/e constant. So the model sharpened the constant inside the new upper bound rather than the exponent, which is the lower tier by this site's definition.

Verification

Checked by this site on 17 August 2026 against the paper's LaTeX (arXiv:2607.02832, Korsky, 2 July 2026). The abstract matches this entry, and the acknowledgement is verbatim as the AI-role note now quotes it - including the sentence attributing the main construction ideas to the author, which the submission's quote had omitted. The model's named contribution was traced through the text to the density-increment step it actually improves. The prior bounds attribute correctly: Gerver, Pacific J. Math. 83 (1979) 349-355, and Gerver-Ramsey, same volume, 357-363. The proofs themselves - a dyadic slope-field random construction and a Farey-mediant density increment - were not checked here and need a discrete geometer. Unrefereed preprint, no independent review.

Sources

Submitted by GoldenMongoose827 on

Changelog4 changes
  • Rasmus Lindahlchanged Statement from “Let $A(k)$ be the largest possible number of moves in a north-east lattice path whose visi…” to “Let $A(k)$ be the largest possible number of moves in a north-east lattice path whose visi…”, also Significance, Significance note
  • Rasmus Lindahlapproved this entry
  • Rasmus Lindahlset Field detail to “Discrete geometry - lattice paths”, also What the AI did, Verification note, Posed by, Source name, What was actually shown, Age note
  • GoldenMongoose827submitted this entry

Discussion