Multidimensional arithmetic progression variant For $\vec{d} \in \mathbb{N}^n$, let $Q(\vec{d}) \subset \mathbb{N}^n$ be the set of vertices of the $n$-dimensional cube scaled in the direction of the $i$-th coordinate by $d_i$, i.e. 
$Q(\vec{d} = \{\langle \pm d_1, \ldots, \pm d_n\rangle\}$.

Consider the following problem:


  Given a set of points in $\mathbb{N}^n$ and number $k$, 
  does the set contains an $n$-dimentional arithmetic progression of length $k$?


More formally,


  Input:
  given a finite set $X \subseteq \mathbb{N}^n$ and a positive integer $k \in \mathbb{N}^+$.  
  
  Question:
  are there $\vec{o}\in \mathbb{N}^n$ and $ \vec{d} \in (\mathbb{N}^+)^n$ such that 
  $\vec{o}+ Q(i\vec{d})\subseteq X$ for all integers $0 \leq i \leq k$?


Informally we are looking at the containment of 
the vertices of scaled $n$-dimensional axis-aligned cubes centered at $\vec{o}$.

Does this problem have a name?
What is its complexity? 
Can we solved it using dynamic programming?
The book Additive Combinatorics by Terence Tao and Van Vu discuss arithmetic sequences in depth from a mathematical point of view.  They establish the existence of arithmetic sequences under various conditions of your set $X$. 



Example: Szemeredi Theorem

If a subset positive "density"  in your lattice it has infinitely many arithmetic progressions of arbitrary length. 

$$\displaystyle \mathrm{density}(E) =  \limsup_{N \to \infty}  \frac{|E \cap [1,N]| }{N} \geq 0$$ 

Let $E \subseteq \mathbb{N}$ be set of positive upper density, then $E$ has a non-trivial $k$-term arithmetic progression. 



You could totally imagine looking for vectors arranged in various patterns rather than restrict your attention to $\mathbb{Z}$. 

The book simplifies very technical Fourier analysis and probability replacing it with less technical Fourier theory and probability.   They break down the heavy duty math into lemma and theorem that are useful for more specific problems. 



Example Consider a random set $E \subset [1,N]$ with probability $\mathbb{P}[k \in E] = \frac{1}{2}$.  Any  3 evenly spaced numbers elements $a, a+d, a+2d \in \mathbb{N}$ will chosen inside $E$ with probability $\frac{1}{8}$, so we can expect many arithmetic progressions in the random set $E$.

On the other extreme is using the floor function  $\{[n \sqrt{7}] : n \in \mathbb{Z}\} = \{ [  0,   2,   5,   7,  10,  13,  15,  18,  21,  23,\dots \}$.  This is about as "ordered" as you can get, and it will also have many arithmetic progressions of arbitrary length.



Then it would be up to you to consider the run-time aspects of the algorithms they are implying.  It may not necessarily be easy to find arithmetic sequences in the prime or square free numbers even if we know they exist.