Varian variasi aritmatika multidimensi

Untuk $\vec{d} \in \mathbb{N}^n$ , misalkan $Q(\vec{d}) \subset \mathbb{N}^n$ adalah himpunan simpul dari kubus dimensi- $n$ diskalakan ke arah koordinat ke- $i$ oleh $d_i$ , yaitu $Q(\vec{d} = \{\langle \pm d_1, \ldots, \pm d_n\rangle\}$ .

Pertimbangkan masalah berikut:

Diberikan satu set titik dalam $\mathbb{N}^n$ dan angka $k$ , apakah himpunan tersebut berisi suatu perkembangan aritmatika $n$ dimensi panjang $k$ ?

Lebih formal,

Input:
diberi himpunan terbatas $X \subseteq \mathbb{N}^n$ dan bilangan bulat positif $k \in \mathbb{N}^+$ .

Pertanyaan:
adakah $\vec{o}\in \mathbb{N}^n$ dan $\vec{d} \in (\mathbb{N}^+)^n$ sehingga $\vec{o}+ Q(i\vec{d})\subseteq X$ untuk semua bilangan bulat $0 \leq i \leq k$ ?

Secara tidak resmi kita sedang melihat penahanan simpul-simpul yang disejajarkan dengan sumbu $n$ dimensi yang dipusatkan pada $\vec{o}$ .

Apakah masalah ini memiliki nama? Apa kerumitannya? Bisakah kita menyelesaikannya menggunakan pemrograman dinamis?

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

Kami memiliki pakar dalam membuktikan kelengkapan NP di sini di cstheory.SE: Anda harus bertanya kepadanya. Namanya Marzio ... oh, tunggu.

Suresh Venkat

@ SureshVenkat: Saya sudah bertanya kepadanya, tetapi sepertinya dia sedikit "rusak" dalam minggu-minggu ini :-)

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$

Jawaban:

$X$

Contoh : Teorema Szemeredi

Jika subset positif "kepadatan" dalam kisi Anda itu memiliki tak terhingga banyak perkembangan aritmatika dengan panjang sewenang-wenang.

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$

Biarkan disetel dari kepadatan atas positif, maka memiliki perkembangan aritmatika -term non-sepele . $E \subseteq \mathbb{N}$ $E$ $k$

Anda benar-benar bisa membayangkan mencari vektor yang tersusun dalam berbagai pola daripada membatasi perhatian Anda pada . $\mathbb{Z}$

Buku ini menyederhanakan analisis Fourier yang sangat teknis dan probabilitas untuk menggantinya dengan teori dan probabilitas Fourier yang kurang teknis. 😐 Mereka memecah matematika tugas berat menjadi lemma dan teorema yang berguna untuk masalah yang lebih spesifik. 😃

Contoh Pertimbangkan himpunan acakdengan probabilitas. Apa saja 3 merata spasi nomor elemenakan dipilih dalamdengan probabilitas, sehingga kita dapat berharap banyak deret aritmetika di set acak. $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$

Di sisi lain ekstrim menggunakan fungsi lantai . Ini adalah tentang "memerintahkan" yang Anda bisa dapatkan, dan itu juga akan memiliki banyak perkembangan aritmatika dengan panjang sewenang-wenang. $\{[n \sqrt{7}] : n \in \mathbb{Z}\} = \{ [ 0, 2, 5, 7, 10, 13, 15, 18, 21, 23,\dots \}$

Maka terserah Anda untuk mempertimbangkan aspek run-time dari algoritma yang mereka maksudkan. Mungkin tidak selalu mudah untuk menemukan urutan aritmatika dalam bilangan prima atau kuadrat bahkan jika kita tahu mereka ada.

John Mangual
sumber