Does every big polyomino contain a big arithmetic progression?

Question

Define a $k$-AP (arithmetic progression) as $k$ vertices whose $x$- and $y$-coordinates both from an arithmetic progression, for example, (1,0), (2,2), (3,4) is a 3-AP.

Is it true that for every $k$ every long enough path in the grid graph (which is a 4-regular infinite graph) contains a $k$-AP?

The statement holds for $k=4$: https://arxiv.org/abs/2004.12801
and it feels that it should have an easy proof for all $k$, but I don't see it.

Update. As pointed out by Renan in his answer, this problem was already posed and solved by him; the statement fails already for $k=5$: https://sarcasticresonance.wordpress.com/2018/11/21/arithmetic-progressions-in-space-2/

Answer 1

The answer is no. I will construct a connected subset $S\subset \Bbb{Z}^2$ without arbitrarily long arithmetic progressions. Since the grid is locally finite, $S$ must contain an infinite path $P\subset S$ (see: Konig's lemma), which also will not contain arbitrarily long progressions.

By a result of Cassaigne, Currie, Schaeffer, and Shallit (https://arxiv.org/abs/1106.5204), there exists an injective "Lipschitz function" $f:\Bbb{Z} \to \Bbb{Z}^2$ so that the image of $f$ that lacks arithmetic progressions of length $4$ (this is perhaps not immediately obvious from the language in their paper, but I will explain in a moment).

Given $f$, with Lipschitz constant $L$, the set $S:= \{(x,y): |(x,y)-f(n)|\le L \text{ for some }n\}$ is a connected subset of $\Bbb{Z}^2$. Moreover, $S$ can be covered by finitely many translates of the image of $f$, meaning it has a finite coloring lacking $4$-APs, meaning $S$ cannot contain arbitrarily long progressions (by van der Waerden's theorem). This completes the proof, modulo justifying the existence of $f$.

Existence of $f$: In the language of Cassaigne et al. they show there exists some function $F:\Bbb{Z}\to \{0,1,3,4\}$, so that for any three consecutive intervals $I_1 = \{i_0,\dots,i_1\},I_2 = \{i_1+1,\dots,i_2\},I_3=\{i_2+1,\dots,i_3\}$, we either have $$|I_x|\neq |I_y|\text{ or }\sum_{i\in I_x} F(i)\neq \sum_{i'\in I_y}F(i')$$ for some $x,y$. We then take $f(n) := (n,\sum_{i=1}^nF(n))$ to get our $f$.

Answer 2

Alternative proof to Zachs, with best bound: The answer is no, and the largest $k$ possible is $k=4$.

The proof is due to a theorem by Dekking from 1978: There exists a sequence on two symbols in which no four blocks occur consecutively that are permutations of each other.

If one symbol is interpreted as "increase $x$ by 1" and the other symbol as "increase $y$ by 1", the sequence then describes an infinite monotone polynomino. If this polynomino had an arithmetic progression of length 5, then the 4 blocks between two consecutive points in the progression would be permutations of each other, contradicting the theorem.

See also this blog post: https://sarcasticresonance.wordpress.com/2018/11/21/arithmetic-progressions-in-space-2/