<p>The book <em><a href="http://www.cambridge.org/us/academic/subjects/mathematics/real-and-complex-analysis/additive-combinatorics?format=HB" rel="nofollow">Additive Combinatorics</a></em> 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$. </p>

<hr>

<p><strong>Example</strong>: Szemeredi Theorem</p>

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

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

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

<hr>

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

<p>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. </p>

<hr>

<p><a href="http://arxiv.org/abs/1404.0775" rel="nofollow"><strong>Example</strong></a> 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$.</p>

<p>On the other extreme is using the <a href="https://en.wikipedia.org/wiki/Floor_and_ceiling_functions" rel="nofollow">floor function</a>  $\{[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.</p>

<hr>

<p>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. </p>

CC BY-SA 3.0
2014-05-01T16:36:35.493Z
2014-05-02T12:35:57.907Z
2014-05-02T12:35:57.907Z
john mangual
<p>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\}$.</p>

<p>Consider the following problem:</p>

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

<p>More formally,</p>

<blockquote>
  <p><strong>Input:</strong><br>
  given a finite set $X \subseteq \mathbb{N}^n$ and a positive integer $k \in \mathbb{N}^+$.  </p>
  
  <p><strong>Question:</strong><br>
  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$?</p>
</blockquote>

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

<p>Does this problem have a name?
What is its complexity? 
Can we solved it using dynamic programming?</p>

CC BY-SA 3.0
2014-04-30T18:31:52.600Z
The way I am reading your notation, it looks like you are just asking if there exist $a_0,d \in \mathbb{N}^n$ such that $\{a_0 + i d: -k \leq i \leq k\}\subseteq X$. But that is like looking for a line, and not a box, so I think I am misreading something?
Sasho Nikolov
CC BY-SA 3.0
2014-04-30T18:41:00.093Z
We have this expert on proving NP-completeness here at cstheory.SE: you should ask him. His name is Marzio... oh wait.
Suresh Venkat
CC BY-SA 3.0
2014-05-01T00:10:32.160Z
@SureshVenkat: I already asked him, but it seems that he is a little bit "out of order" in these weeks :-)
Marzio De Biasi
CC BY-SA 3.0
2014-05-01T00:15:37.170Z
@SashoNikolov: you're right I was reasoning with distinct $i_1,...,i_n$ (i.e. an expanding hyper-rectangle) but I wrongly wrote $i$ (a multidimensional line) which is solvable in polynomial time. I'll correct the question.
Marzio De Biasi
CC BY-SA 3.0
2014-05-01T07:42:08.273Z
@Kaveh: perhaps the reformulation is still wrong :-( I'm only interested in the vertices. Thinking in 2D I want the vertices of a "scaling" rectangle (i.e. 4 "expanding" vertices). In 3D the vertices of a "scaling" cuboid (i.e. 8 "expanding vertices"). Let me know if you think it is not correct. Yes  $N$ is $\mathbb{N}$
Marzio De Biasi
CC BY-SA 3.0
2014-05-01T13:56:09.413Z
This looks a lot like the multidimensional Van der Waerden theorem, where the set X is any fixed color in the VDW-coloring. (It would take a lot of time/energy for me to find a mapping between the two, but you should email Bill Gasarch if you really want to track an answer down.)
Daniel Apon
CC BY-SA 3.0
2014-05-01T14:08:29.513Z
See e.g. the final theorem in http://homepages.warwick.ac.uk/~masdbl/vdw.pdf
Daniel Apon
CC BY-SA 3.0
2014-05-01T19:16:06.273Z
Why does the following trivial algorithm not work: enumerate over all choicses $a_0 \in X$, and for each $a_0$ enumerate over all $i$ and all points in $Q_i(a_0)$, quitting and moving on to the next $a_0$ as soon as some $a \in Q_i(a_0)$ is found that does not belong to $X$. There are $|X|$ choices for $a_0$, and for each we enumerate over at most $|X|+1$ points, so this is a quadratic time algorithm. Maybe you have in mind some $X$ which is specified implicitly?
Sasho Nikolov
CC BY-SA 3.0
2014-05-01T20:18:20.167Z
@SashoNikolov: I have in mind an implicitly (succinct) $X$ :-); but for now assume that every point is given explicitely (as intended in the question). At every $a_0$ we must pick a "jump" $d_i$ for each dimension and check that for $i=0,...,k$ all vertices of the "expanding hyper-rectangle" are in $X$ (the sides of the axis-aligned box can be different). If a $d=d_1,...,d_n$ "fails", we must try another $d$, but it seems (to me) that we must scan all the combinations of $d_i$. Let me know if it is not clear.
Marzio De Biasi
CC BY-SA 3.0
2014-05-01T23:40:19.120Z
I edited the question, hopefully haven't messed it up. By the way, it might help to first look at just the positive set only, i.e. are there $\vec{o}$ and $\vec{d}$ such that $\vec{o} + i \vec{d} \in X$ for $0 \leq i \leq k$. Do you know the answer for that problem? (I would guess the answer to the cube version would be similar.) Also what is known about the $n=1$ and $n=2$ cases?
Kaveh
CC BY-SA 3.0
2014-05-02T00:29:01.933Z
@Kaveh: thanks, the edited question is OK. For fixed $n$ it can be easily solved by DP; for $n = 1$ it is smilar to the well known *longest arithmetic progression problem*, which is solvable using DP in $O(n^2)$ (where $n$ is the length of the 1-D input array). I'm checking the trivial solution by Sasho, which seems to work if $X$ is given explicitly.
Marzio De Biasi
CC BY-SA 3.0
2014-05-02T00:56:12.017Z
@SashoNikolov: you're right, if $X$ is given explicitely (and the sides of the box are axis-aligned) the solution is trivial. You can convert your comment into an answer and I'll accept it!
Marzio De Biasi
CC BY-SA 3.0
2014-05-02T04:02:02.187Z
Marzio, I am not sure anymore that it works. In my previous comment I ignored the fact that $d$ is part of the solution, not the input.  @Kaveh, in your edit, what is $\vec{d}Q$? I think you want $DQ$ for a diagonal positive integral matrix $D$.
Sasho Nikolov
CC BY-SA 3.0
2014-05-02T04:05:40.040Z
@Sasho, yes, or just point-wise multiplication.
Kaveh
CC BY-SA 3.0
2014-05-02T06:11:01.027Z
@Sasho: It is enough to check every distance between two vertices of $X$, so at most $|X|^2$, polynomial in the input. to Marzio: If $X$ is succinct, then what is the situation for $n=1$? Maybe that would make us understand what you are asking...
domotorp
CC BY-SA 3.0
2014-05-02T08:03:26.837Z
@domotorp: right, thanks! Actually I was asking for the explicitly given $X$ and it turned out that Sasho's trivial solution can work (it didn't come to my mind )-:. I'm working on a puzzle-like problem in which $X$ is given implicitly as differently sized boxes (3D case) and it will probably be more interesting, but I'm still searching stuff on the subject and to avoid confusion I leave this question as is and I'll post another one if I have more troubles.
Marzio De Biasi
CC BY-SA 3.0
2014-05-02T08:24:30.283Z
@SashoNikolov: it works: it is enough to scan all the possible endpoints (pairs of vertices $\vec{o}, \vec{v} \in X$) of the "half-hyper-diagonal". Once fixed the hyper-diagonal the "jumps" are also fixed: $(\vec{v} - \vec{o}) / k$ and we can check in $O(|X|)$ time that the inner vertices are themselves in $X$.
Marzio De Biasi
<cc.complexity-theory><reference-request><co.combinatorics><cg.comp-geom><time-complexity>
Multidimensional arithmetic progression variant
Marzio De Biasi
# Multidimensional arithmetic progression variant

(Asked by: username_0 on 2014-04-30)

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?

**Tags:** cc.complexity-theory, reference-request, co.combinatorics, cg.comp-geom, time-complexity

> **Comments:**
> **username_1**: The way I am reading your notation, it looks like you are just asking if there exist $a_0,d \in \mathbb{N}^n$ such that $\{a_0 + i d: -k \leq i \leq k\}\subseteq X$. But that is like looking for a line, and not a box, so I think I am misreading something?  
> **username_2**: We have this expert on proving NP-completeness here at cstheory.SE: you should ask him. His name is Marzio... oh wait.  
> **username_0**: @SureshVenkat: I already asked him, but it seems that he is a little bit "out of order" in these weeks :-)  
> **username_0**: @SashoNikolov: you're right I was reasoning with distinct $i_1,...,i_n$ (i.e. an expanding hyper-rectangle) but I wrongly wrote $i$ (a multidimensional line) which is solvable in polynomial time. I'll correct the question.  
> **username_0**: @username_4: perhaps the reformulation is still wrong :-( I'm only interested in the vertices. Thinking in 2D I want the vertices of a "scaling" rectangle (i.e. 4 "expanding" vertices). In 3D the vertices of a "scaling" cuboid (i.e. 8 "expanding vertices"). Let me know if you think it is not correct. Yes  $N$ is $\mathbb{N}$  
> **username_3**: This looks a lot like the multidimensional Van der Waerden theorem, where the set X is any fixed color in the VDW-coloring. (It would take a lot of time/energy for me to find a mapping between the two, but you should email Bill Gasarch if you really want to track an answer down.)  
> **username_3**: See e.g. the final theorem in http://homepages.warwick.ac.uk/~masdbl/vdw.pdf  
> **username_1**: Why does the following trivial algorithm not work: enumerate over all choicses $a_0 \in X$, and for each $a_0$ enumerate over all $i$ and all points in $Q_i(a_0)$, quitting and moving on to the next $a_0$ as soon as some $a \in Q_i(a_0)$ is found that does not belong to $X$. There are $|X|$ choices for $a_0$, and for each we enumerate over at most $|X|+1$ points, so this is a quadratic time algorithm. Maybe you have in mind some $X$ which is specified implicitly?  
> **username_0**: @SashoNikolov: I have in mind an implicitly (succinct) $X$ :-); but for now assume that every point is given explicitely (as intended in the question). At every $a_0$ we must pick a "jump" $d_i$ for each dimension and check that for $i=0,...,k$ all vertices of the "expanding hyper-rectangle" are in $X$ (the sides of the axis-aligned box can be different). If a $d=d_1,...,d_n$ "fails", we must try another $d$, but it seems (to me) that we must scan all the combinations of $d_i$. Let me know if it is not clear.  
> **username_4**: I edited the question, hopefully haven't messed it up. By the way, it might help to first look at just the positive set only, i.e. are there $\vec{o}$ and $\vec{d}$ such that $\vec{o} + i \vec{d} \in X$ for $0 \leq i \leq k$. Do you know the answer for that problem? (I would guess the answer to the cube version would be similar.) Also what is known about the $n=1$ and $n=2$ cases?  
> **username_0**: @username_4: thanks, the edited question is OK. For fixed $n$ it can be easily solved by DP; for $n = 1$ it is smilar to the well known *longest arithmetic progression problem*, which is solvable using DP in $O(n^2)$ (where $n$ is the length of the 1-D input array). I'm checking the trivial solution by Sasho, which seems to work if $X$ is given explicitly.  
> **username_0**: @SashoNikolov: you're right, if $X$ is given explicitely (and the sides of the box are axis-aligned) the solution is trivial. You can convert your comment into an answer and I'll accept it!  
> **username_1**: Marzio, I am not sure anymore that it works. In my previous comment I ignored the fact that $d$ is part of the solution, not the input.  @username_4, in your edit, what is $\vec{d}Q$? I think you want $DQ$ for a diagonal positive integral matrix $D$.  
> **username_4**: @Sasho, yes, or just point-wise multiplication.  
> **username_5**: @Sasho: It is enough to check every distance between two vertices of $X$, so at most $|X|^2$, polynomial in the input. to Marzio: If $X$ is succinct, then what is the situation for $n=1$? Maybe that would make us understand what you are asking...  
> **username_0**: @username_5: right, thanks! Actually I was asking for the explicitly given $X$ and it turned out that Sasho's trivial solution can work (it didn't come to my mind )-:. I'm working on a puzzle-like problem in which $X$ is given implicitly as differently sized boxes (3D case) and it will probably be more interesting, but I'm still searching stuff on the subject and to avoid confusion I leave this question as is and I'll post another one if I have more troubles.  
> **username_0**: @SashoNikolov: it works: it is enough to scan all the possible endpoints (pairs of vertices $\vec{o}, \vec{v} \in X$) of the "half-hyper-diagonal". Once fixed the hyper-diagonal the "jumps" are also fixed: $(\vec{v} - \vec{o}) / k$ and we can check in $O(|X|)$ time that the inner vertices are themselves in $X$.  

---

## 1 answers

### Answer by username_6 on 2014-05-01. Score: 3 | Accepted answer

The book *[Additive Combinatorics](http://www.cambridge.org/us/academic/subjects/mathematics/real-and-complex-analysis/additive-combinatorics?format=HB)* 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**](http://arxiv.org/abs/1404.0775) 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](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) $\{[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.


---

