Variante de progressão aritmética multidimensional

Para , seja o conjunto de vértices do cubo dimensional dimensionado na direção de a ésima coordenada por , ou seja, . $\vec{d} \in \mathbb{N}^n$ $Q(\vec{d}) \subset \mathbb{N}^n$ $n$ $i$ $d_i$ $Q(\vec{d} = \{\langle \pm d_1, \ldots, \pm d_n\rangle\}$

Considere o seguinte problema:

Dado um conjunto de pontos em número , o conjunto contém uma progressão aritmética dimensional do comprimento ? $\mathbb{N}^n$ $k$ $n$ $k$

Mais formalmente,

Entrada:
dado um conjunto finito $X \subseteq \mathbb{N}^n$ e um número inteiro positivo $k \in \mathbb{N}^+$ .

Pergunta:
existem $\vec{o}\in \mathbb{N}^n$ e $\vec{d} \in (\mathbb{N}^+)^n$ tal que $\vec{o}+ Q(i\vec{d})\subseteq X$ para todos os números inteiros $0 \leq i \leq k$ ?

Informalmente, estamos analisando a contenção dos vértices dos cubos alinhados ao eixo dimensionados em $n$ dimensões, centrados em $\vec{o}$ .

Esse problema tem um nome? Qual é a sua complexidade? Podemos resolvê-lo usando programação dinâmica?

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

Temos esse especialista em provar a completude da PN aqui em cstheory.SE: você deve perguntar a ele. O nome dele é Marzio ... oh espera.

Suresh Venkat

@SureshVenkat: Eu já perguntei a ele, mas parece que ele é um pouco "fora de ordem" nestas semanas :-)

Marzio De Biasi

Por que o seguinte algoritmo trivial não funciona: enumere sobre todas as opções e para cada enumere sobre todos os e todos os pontos em , e passando para o próximo assim que alguns é encontrado que não pertence a . Existemopções para e para cada uma delas enumeramos no máximo pontos, portanto esse é um algoritmo de tempo quadrático. Talvez você tenha em mente algum que é especificado implicitamente?

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$

Sasho Nikolov

@ SashoNikolov: você está certo, se é dado explicitamente (e os lados da caixa estão alinhados ao eixo), a solução é trivial. Você pode converter seu comentário em resposta e eu aceito!

X

$X$

Marzio De Biasi

@ Sasho: Basta verificar todas as distâncias entre dois vértices de , portanto, no máximo , polinômio na entrada. para Marzio: se é sucinto, então qual é a situação para ? Talvez isso nos faria entender o que você está pedindo ...

X

$X$

| X |^{2}

$|X|^2$

X

$X$

n = 1

$n=1$

domotorp

Respostas:

O livro Additive Combinatorics de Terence Tao e Van Vu discute sequências aritméticas em profundidade de um ponto de vista matemático. Eles estabelecem a existência de seqüências aritméticas sob várias condições de seu conjunto de . $X$

Exemplo : Teorema de Szemeredi

Se um subconjunto "densidade" positiva em sua rede possui infinitas progressões aritméticas de comprimento arbitrário.

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

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

Seja um conjunto de densidade superior positiva, então tem uma progressão aritmética não trivial em term. $E \subseteq \mathbb{N}$ $E$ $k$

Você pode imaginar totalmente procurando vetores organizados em vários padrões, em vez de restringir sua atenção a . $\mathbb{Z}$

O livro simplifica a análise e a probabilidade de Fourier muito técnicas, substituindo-as por menos teoria e probabilidade de Fourier. 😐 Eles dividem a matemática pesada em lema e teorema que são úteis para problemas mais específicos. 😃

Exemplo Considere um conjunto aleatóriocom probabilidade. Quaisquer 3 uniformemente espaçados números elementosserá escolhido dentrocom probabilidade, portanto, pode esperar muitos progressões aritméticas no conjunto aleatório. $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$

Por outro lado, está usando a função floor . Isso é o mais "ordenado" possível, e também terá muitas progressões aritméticas de comprimento arbitrário. $\{[n \sqrt{7}] : n \in \mathbb{Z}\} = \{ [ 0, 2, 5, 7, 10, 13, 15, 18, 21, 23,\dots \}$

Cabe a você considerar os aspectos em tempo de execução dos algoritmos que eles estão implicando. Pode não ser necessariamente fácil encontrar seqüências aritméticas nos números livres primos ou quadrados, mesmo se sabemos que eles existem.

john mangual
fonte