North-East Lattice Paths with Few Collinear Vertices

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) bounded $A(k)$ by $$\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 to $$\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\left(\left(\tfrac{2}{e}+o(1)\right)(k-1)^2\right)$.

Both bounds move, and the gap stays enormous: the lower bound rises from $\exp(\Omega(\log^2 k))$ to $\exp(\Omega(k^{1/3}))$ and the upper falls from $\exp(O(k^4))$ to $\exp(O(k^2))$, so $A(k)$ is still undetermined between an exponent of $k^{1/3}$ and one of $k^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.