North-East Lattice Paths with Few Collinear Vertices

Abstract

Let $A(k)$ be the largest possible number of moves in a north-east lattice path whose visited vertices contain no $k$ collinear points. Gerver (1979) and Gerver and Ramsey (1979) gave lower and upper bounds on $A(k)$ of the form \[ \exp\left(Ω(\log(k)^2)\right)\le A(k)\le \exp\left(O(k^4)\right). \] Improving upon these results, we show that \[ \exp\left(Ω(k^{1/3})\right)\le A(k)\le \exp\left(\left(\frac{2}{e}+o(1)\right)(k-1)^2\right). \]

Disclosure

“r was assisted by GPT-5.5 Pro in the preparation of this paper. 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 were used to check computations, improve the upper-bound constant by suggesting the use of the mediant of the relevant Farey fractions, and assist in drafting and editing the manuscript. The author is responsible for all statements and pro”

PDF page 17

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-24T00:28:51.963Z

Structural counts