Mehrdimensionale arithmetische Progressionsvariante

Für $\vec{d} \in \mathbb{N}^n$ sei $Q(\vec{d}) \subset \mathbb{N}^n$ die Menge der Eckpunkte des $n$ dimensionalen Würfels, skaliert in Richtung der $i$ ten Koordinate durch $d_i$ , dh $Q(\vec{d} = \{\langle \pm d_1, \ldots, \pm d_n\rangle\}$ .

Betrachten Sie das folgende Problem:

Enthält die Menge bei einer Menge von Punkten in $\mathbb{N}^n$ und der Zahl $k$ eine $n$ dimensionale arithmetische Folge der Länge $k$ ?

Formeller,

Eingabe:
gegeben eine endliche Menge $X \subseteq \mathbb{N}^n$ und eine positive ganze Zahl $k \in \mathbb{N}^+$ .

Frage:
Gibt es $\vec{o}\in \mathbb{N}^n$ und $\vec{d} \in (\mathbb{N}^+)^n$ so dass $\vec{o}+ Q(i\vec{d})\subseteq X$ für alle ganzen Zahlen $0 \leq i \leq k$ ?

Informell betrachten wir die Eindämmung der Eckpunkte von skalierten $n$ dimensionalen achsenausgerichteten Würfeln, die bei zentriert sind $\vec{o}$ .

Hat dieses Problem einen Namen? Was ist ihre Komplexität? Können wir es mit dynamischer Programmierung lösen?

cc.complexity-theory reference-request co.combinatorics cg.comp-geom time-complexity Marzio De Biasi
quelle

Wir haben diesen Experten für den Nachweis der NP-Vollständigkeit hier bei cstheory.SE: Sie sollten ihn fragen. Er heißt Marzio ... oh warte.

Suresh Venkat

@SureshVenkat: Ich habe ihn bereits gefragt, aber es scheint, dass er in diesen Wochen ein bisschen "außer Betrieb" ist :-)

Marzio De Biasi

a_{0} \in X

$a_0 \in X$

a_{0}

$a_0$

i

$i$

Q_{i} (a_{0})

$Q_i(a_0)$

a_{0}

$a_0$

a \in Q_{i} (a_{0})

$a \in Q_i(a_0)$

X

$X$

| X |

$|X|$

a_{0}

$a_0$

| X | + 1

$|X|+1$

X

$X$

X

$X$

X

$X$

| X |^{2}

$|X|^2$

X

$X$

n = 1

$n=1$

Antworten:

$X$

Beispiel : Satz von Szemeredi

Wenn eine Teilmenge eine positive "Dichte" in Ihrem Gitter hat, hat sie unendlich viele arithmetische Progressionen beliebiger Länge.

d e n s i t y (E) = \underset{N \to \infty}{lim sup} \frac{| E \cap [1, N] |}{N} \geq 0

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

Sei eine positive obere Dichte, dann hat eine nicht triviale terminale arithmetische Progression. $E \subseteq \mathbb{N}$ $E$ $k$

Sie können sich durchaus vorstellen, nach Vektoren zu suchen, die in verschiedenen Mustern angeordnet sind, anstatt Ihre Aufmerksamkeit auf . $\mathbb{Z}$

Das Buch vereinfacht die sehr technische Fourier-Analyse und Wahrscheinlichkeit und ersetzt sie durch weniger technische Fourier-Theorie und Wahrscheinlichkeit. 😐 Sie zerlegen die Hochleistungsmathematik in Lemma und Theorem, die für spezifischere Probleme nützlich sind. 😃

Beispiel Betrachten Sie eine Zufallsmengemit der Wahrscheinlichkeit. Alle 3 gleichmäßig verteilten Zahlenelementewerden inmit der Wahrscheinlichkeit, sodass wir in der Zufallsmengeviele arithmetische Progressionen erwarten können. $E \subset [1,N]$ $\mathbb{P}[k \in E] = \frac{1}{2}$ $a, a+d, a+2d \in \mathbb{N}$ $E$ $\frac{1}{8}$ $E$

Das andere Extrem ist die Verwendung der Bodenfunktion . Dies ist ungefähr so "geordnet" wie möglich und es wird auch viele arithmetische Abläufe beliebiger Länge geben. $\{[n \sqrt{7}] : n \in \mathbb{Z}\} = \{ [ 0, 2, 5, 7, 10, 13, 15, 18, 21, 23,\dots \}$

Dann liegt es an Ihnen, die Laufzeitaspekte der Algorithmen zu berücksichtigen, die sie implizieren. Es muss nicht unbedingt einfach sein, arithmetische Folgen in den Primzahlen oder quadratfreien Zahlen zu finden, selbst wenn wir wissen, dass sie existieren.

John Mangual
quelle