Variante de progresión aritmética multidimensional

Para , deje que sea el conjunto de vértices del cubo dimensional escalado en la dirección de la coordenada por , es decir, . $\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 el siguiente problema:

Dado un conjunto de puntos en número , ¿el conjunto contiene una progresión aritmética -dimensional de longitud ? $\mathbb{N}^n$ $k$ $n$ $k$

Más formalmente,

Entrada:
dado un conjunto finito y un entero positivo . $X \subseteq \mathbb{N}^n$ $k \in \mathbb{N}^+$

Pregunta:
¿hay y tal que para todos los enteros ? $\vec{o}\in \mathbb{N}^n$ $\vec{d} \in (\mathbb{N}^+)^n$ $\vec{o}+ Q(i\vec{d})\subseteq X$ $0 \leq i \leq k$

Informalmente, estamos viendo la contención de los vértices de cubos alineados en ejes -dimensionales escalados centrados en . $n$ $\vec{o}$

¿Este problema tiene un nombre? ¿Cuál es su complejidad? ¿Podemos resolverlo usando programación dinámica?

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

Tenemos a este experto para demostrar la integridad de NP aquí en cstheory. SE: debe preguntarle. Se llama Marzio ... oh, espera.

Suresh Venkat

@SureshVenkat: ya le pregunté, pero parece que está un poco "fuera de servicio" en estas semanas :-)

Marzio De Biasi

¿Por qué no funciona el siguiente algoritmo trivial: enumerar sobre todas las opciones , y para cada enumerar sobre todos y todos los puntos en , dejar de fumar y pasar al siguiente tan pronto como algunos se encontró que no pertenece a . Hayopciones para , y para cada uno enumeramos como máximo puntos, por lo que este es un algoritmo de tiempo cuadrático. ¿Quizás tenga en mente alguna que se especifica implícitamente?

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: tienes razón, si se da explícitamente (y los lados de la caja están alineados en el eje) la solución es trivial. ¡Puedes convertir tu comentario en una respuesta y lo aceptaré!

X

$X$

Marzio De Biasi

@ Sasho: es suficiente verificar cada distancia entre dos vértices de , por lo tanto, como máximo , polinomio en la entrada. a Marzio: si es sucinto, ¿cuál es la situación para ? Tal vez eso sería hacernos comprender lo que está pidiendo ...

X

$X$

| X |^{2}

$|X|^2$

X

$X$

n = 1

$n=1$

domotorp

Respuestas:

El libro Additive Combinatorics de Terence Tao y Van Vu discuten en profundidad las secuencias aritméticas desde un punto de vista matemático. Ellos establecen la existencia de secuencias aritméticas en diversas condiciones de su aparato de . $X$

Ejemplo : Teorema de Szemeredi

Si un subconjunto de "densidad" positiva en su red tiene infinitas progresiones aritméticas de longitud arbitraria.

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$

Sea un conjunto de densidad superior positiva, entonces tiene una progresión aritmética -term no trivial . $E \subseteq \mathbb{N}$ $E$ $k$

Podrías imaginar totalmente buscando vectores dispuestos en varios patrones en lugar de restringir tu atención a . $\mathbb{Z}$

El libro simplifica el análisis y la probabilidad muy técnicos de Fourier y lo reemplaza con una teoría y probabilidad menos técnicas de Fourier. 😐 Desglosan las matemáticas pesadas en lemas y teoremas que son útiles para problemas más específicos. 😃

Ejemplo Considere un conjunto aleatoriocon probabilidad. Cualquier 3 espaciados uniformemente números elementosserá elegido dentro decon una probabilidad, así que podemos esperar muchos progresiones aritméticas en el conjunto aleatorio. $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$

En el otro extremo está usando la función de piso . Esto es lo más "ordenado" que puede obtener, y también tendrá muchas progresiones aritméticas de longitud arbitraria. $\{[n \sqrt{7}] : n \in \mathbb{Z}\} = \{ [ 0, 2, 5, 7, 10, 13, 15, 18, 21, 23,\dots \}$

Entonces dependería de usted considerar los aspectos de tiempo de ejecución de los algoritmos que implican. Puede que no sea necesariamente fácil encontrar secuencias aritméticas en los números libres primos o cuadrados, incluso si sabemos que existen.

john mangual
fuente