8
$\begingroup$

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?

Improve this question
$\endgroup$
17
  • 4
    $\begingroup$ We have this expert on proving NP-completeness here at cstheory.SE: you should ask him. His name is Marzio... oh wait. $\endgroup$
    – Suresh Venkat
    Apr 30, 2014 at 18:41
  • 1
    $\begingroup$ @SureshVenkat: I already asked him, but it seems that he is a little bit "out of order" in these weeks :-) $\endgroup$
    – Marzio De Biasi
    May 1, 2014 at 0:10
  • 2
    $\begingroup$ 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? $\endgroup$
    – Sasho Nikolov
    May 1, 2014 at 19:16
  • 2
    $\begingroup$ @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! $\endgroup$
    – Marzio De Biasi
    May 2, 2014 at 0:56
  • 2
    $\begingroup$ @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... $\endgroup$
    – domotorp
    May 2, 2014 at 6:11

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.