Long Lattice Paths with No Three Collinear Vertices

Abstract

For $d\ge 1$, let $L(d)\in \mathbb{N}\cup \{\infty \}$ be the supremum of the lengths of paths in ${\mathbb{Z}}^d$ whose steps are standard basis vectors and whose vertex sets contain no collinear triple. We prove that \[ \log_2\log_2 L(d)\ge \frac{2}{5}d-O(1) \] for all sufficiently large $d$.