¿Puede un conjunto discreto del plano de densidad uniforme intersecar todos los triángulos grandes?

Question

Sea S un subconjunto discreto del plano euclidiano tal que el número de puntos de un disco grande es aproximadamente igual al área del disco. ¿El complemento de S contiene necesariamente triángulos de área arbitrariamente grande?

(Añadido en julio de 2021:) Recientemente me he enterado de que esto es El problema de Danzer . Un conjunto Danzer ( https://en.wikipedia.org/wiki/Danzer_set ) es un contraejemplo. Aparentemente no es tan conocido, aunque el comienzo de la respuesta de Gowers sugiere que ha oído hablar de él.

Answer 1

Creo que se ha investigado bastante sobre cuestiones relacionadas, prestando mucha atención al cuadrado unitario (y aún más, al cubo unitario en dimensiones superiores). Algunas referencias clave son:

[1] H.Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods (SIAM, 1992)

[2] J.Beck y W.Chen, Irregularidades de la distribución (CUP, 1987)

[3] B.Chazelle, El método de la discrepancia: Randomness and Complexity (CUP, 2000).

Todo lo que puedo hacer es citarle varios resultados de estos. (Algunos de ellos se tratan en Wikipedia-discrepancia .) Los resultados suelen expresarse en términos de "discrepancia": para N puntos del cuadrado unitario, la discrepancia D _N puede definirse como

sup _J |A(J,N) - N λ(J)|

donde J son todos los subintervalos de rectángulos alineados con los ejes, A(J,N) es la función de recuento (es decir, el número de puntos dentro de J), y λ(J) es la medida de Lebesgue. Esta definición tiene un factor extra de N en comparación con [1], pero creo que es útil cuando se escala el cuadrado unitario a un área N: un rectángulo de área λ entonces "debería" contener λ puntos; y la discrepancia es la diferencia entre eso y el número que realmente contiene.

Existen resultados para el mejor comportamiento posible de D _N en función de N. Para los rectángulos orientados al eje, es Ω(log N), y esto se puede conseguir mediante la Halton-Hammersley secuencia. Cuando J se cambia a rectángulos con cualquier rotación, la discrepancia es Ω(N 1/4 ), y O(N 1/4 √log N) puede lograrse mediante un muestreo jittered. Cuando J son todos los subconjuntos convexos del cuadrado unitario, se ha pasado a la "discrepancia isotrópica" J _N -- más difícil de estudiar, pero D _N ≤ J _N ≤ 8√(N D _N ). Además, J _N es Ω(N 1/4 ).

Todo esto está relacionado con la discrepancia de las formas que pueden contener algunos puntos, y la cuestión es si contienen el número "correcto". Si se empieza con una forma j ₁ con n ₁ puntos, y añadir una región vacía (permaneciendo en el conjunto J), se puede demostrar que la región vacía debe tener un área O(2D _N ), pero no veo una garantía de que una forma vacía obedezca al límite Ω.

No estoy seguro de que esto se acerque a una respuesta. Ciertamente estoy de acuerdo en que es un área agradable, y recomiendo esas referencias -- todas ellas pueden ser leídas, si no completamente entendidas, por alguien con educación matemática limitada, como yo.

Answer 2

Aquí hay algunos detalles para demostrar que la construcción de David Speyer no funciona:

Considere una "ventana" arbitrariamente grande, digamos $$W=\lbrace(x,y)|A-100\leq x\leq A+100,B-100\leq x \leq B+100]\rbrace$$ (hay que sustituir 100 por números arbitrariamente grandes más adelante) centrado en algún punto $(A,B)$ del avión. Si $(A,B)$ está lejos del origen, la intersección de $W$ con el conjunto $S$ de todos los puntos de la forma $(\sqrt{k}\cos(2k\pi),\sqrt{k}\sin(2k\pi)), k\in\mathbb N$ se parece (genéricamente, pero se puede descuidar el caso no genérico ya que también encaja en la imagen genérica) "casi" a una traducción $\Lambda$ de un entramado con un dominio fundamental de área $\pi$ . Esta traducción $\Lambda$ de una red depende, por supuesto, de la ubicación precisa de $(A,B)$ pero la "convergencia" de $W\cap S$ a tal $\Lambda$ depende sólo de la norma de (A,B) y del tamaño de W. Más precisamente, la convergencia significa que para cualquier épsilon estrictamente positivo existe un número real $R=R(epsilon,100)$ dependiendo sólo de epsilon y del tamaño (aquí 100) de la ventana con la propiedad de que si $(A,B)$ tiene norma al menos $R$ entonces existe una traducción $\Lambda$ (dependiendo de $(A,B)$ ) de una red euclidiana con dominio fundamental $\pi$ y un mapa de $S\cap W$ (los puntos de $S$ en la ventana $W$ ) en $\Lambda$ que desplaza los puntos como máximo en $\epsilon$ . Para $\epsilon$ lo suficientemente pequeño (dependiendo de nada) hay triángulos arbitrariamente grandes que no se cruzan con un $\epsilon-$ vecindad de dicho conjunto $\Lambda$ . Para $\epsilon$ suficientemente pequeño, el diámetro de tales triángulos de área $\alpha$ puede estar acotado por encima de algún número real que dependa sólo del área \alfa del triángulo pero no de la traslación $\Lambda$ de una red euclidiana con dominio fundamental $\pi$ . Dado un número real $\alpha$ podemos, por tanto, elegir la ventana $W$ lo suficientemente grande como para que contenga triángulos de área $\alpha$ que evitan un $\epsilon-$ barrio de $\Lambda$ . Dicho triángulo evita así $S$ .

Espero que estas explicaciones sean lo suficientemente explícitas. Todo esto es esencialmente sólo la teoría elemental de la red y nada es difícil de demostrar.

Answer 3

Esta respuesta se refiere a la búsqueda de cuadrículas en el modelo del girasol. Mi confianza se tambalea pero no se rompe.

Creo que he entendido lo que dice Roland. Consideremos un cuadrado de área A, a una distancia R del origen, con R muy grande. Será conveniente identificar nuestro plano con el plano complejo. Así que nuestros puntos son de la forma e^{(1/2) log k + 2 pi i tau k}.

Sea L(z) = R log z. En nuestro pequeño cuadrado, L es aproximadamente preservador del área y aproximadamente lineal, con error O(1/R). Así que nuestro cuadrado contendrá grandes triángulos libres de puntos de la red si y sólo si L de nuestro cuadrado lo hace.

Pues bien, L del patrón girasol son los puntos de la forma (1/2) R log k + 2 pi i tau R k. Sólo nos importa k entre (R- \sqrt {A})^2 y (R + \sqrt {A})^2 (aproximadamente), es decir, k de la forma R^2 +s para |s| < 2 \sqrt {A} R. Para tal k,

(1/2) R log k + 2 pi i tau R k = R log R + (1/2) s/R + 2 pi i tau R^3 + 2 pi i tau s R = c + (1/2) s/R + 2 pi i tau s R,

donde c no depende de s. Por supuesto, log es multivaluado, por lo que la respuesta correcta es en realidad

c + s (1/2R + 2 pi i tau R) + t (2 pi i R).

En resumen, el patrón del girasol, restringido a nuestro cuadrado, parece la intersección de un cuadrado similar con una traslación de la cuadrícula generada por (1/2R + 2 pi i tau R) y (2 pi i R). Me he dado cuenta de que esto tiene el dominio fundamental 2 pi, así que supongo que esta es la cuadrícula que Roland está discutiendo.

Entonces, ¿por qué no estoy convencido de que esto sea un problema? La forma de la cuadrícula está cambiando con R. Básicamente, estamos intersectando nuestro cuadrado (de área A) con una cuadrícula cuyas regiones fundamentales se están volviendo muy delgadas y altas. No me queda claro cómo podemos encontrar triángulos grandes DENTRO del cuadrado de área A.

De hecho, esa sería una gran pregunta para que alguien la respondiera. Tomemos un cuadrado de área 100. Interséctalo con la cuadrícula abarcada por (1/R, tau R) y (0, R). Sea f(R) el mayor triángulo dentro del cuadrado, faltando esta retícula. A medida que R pasa a infty, ¿se aproxima f(R) a 1, o se queda más cerca de 100? (He eliminado los factores de 2 y pi que espero que no sean esenciales).

Por supuesto, puede que haya interpretado mal a Roland. Roland, ¿qué rejilla se acerca al modelo de girasol?

Answer 4

No sé si estoy tan enganchado a este problema como David S., pero es realmente adictivo. Mi corazonada es también que la respuesta debería ser "no", y realmente quiero que esto se pueda resolver con argumentos simples (aunque inteligentes) de geometría combinatoria. Aquí hay algunos argumentos de esa naturaleza que no creo que se puedan hacer pasar por sí mismos, pero que descartan algunos enfoques. Estoy haciendo el post wiki de la comunidad, para que la gente pueda añadir o corregir los errores estúpidos que casi seguro he cometido.

Así que usaremos la formulación del rectángulo. Supongamos que S es un conjunto de puntos que sí interseca a todo triángulo suficientemente grande. Entonces, si proyectamos S sobre cualquier línea, la imagen tiene que ser densa. Esto es factible; creo que la construcción tau de David tiene esta propiedad. Pero no se puede construir un conjunto de este tipo a partir de celosías de forma sencilla.

Pero podemos hacerlo un poco mejor, aunque es más difícil de afirmar. También es necesario que las proyecciones de S intersecten una franja paralela a una línea L en L estén muy bien distribuidas. En particular, la distancia máxima entre dos puntos consecutivos tiene que ser O(1/x) para una franja de anchura x, que es la mejor posible hasta una constante. (Para ver esto, observe que hay O(Lx) puntos en la franja, y que tienen que cubrir un intervalo de longitud L).

Por cierto, esto subsume las apelaciones a la "incrustación de grandes casi-látex". Me interesaría (harrison) ver un conjunto que tenga esta propiedad de proyección más fuerte pero que contenga probadamente rectángulos grandes. ETA: Tras una nueva reflexión, si la constante implícita es uniforme para todas las líneas L, entonces esta propiedad es necesaria y suficiente, ya que la propiedad de proyección limita el tamaño de un rectángulo en el complemento de S que es paralelo a L.

Es importante señalar que esto descarta la mayoría de las construcciones aleatorias directas. Si colocamos N puntos al azar en un segmento de línea de longitud 1, prevemos un hueco de longitud log N/N en alguna parte. Tenemos que hacerlo mejor, consiguiendo huecos de tamaño O(1/N). Prueba: Dividir el segmento en N cubos. Para cualquier k cubos consecutivos, la probabilidad de que se pierda todo es (1-k/n)^n ~ e^{-k}. Por lo tanto, si k es log N + O(1), la probabilidad de que un determinado k cubos se pierda será de orden 1/N. Como hay del orden de N bloques de k cubos consecutivos, el número esperado de tales bloques que se pierden será positivo. Por tanto, existe una probabilidad positiva de que se pierda un segmento de longitud log N/N.

Answer 5

David, considerar el logaritmo es una buena idea. Un pequeño error: el dominio fundamental tiene el área pi: Hay un factor de 2 en el denominador de la parte real.

Por supuesto, tienes razón: El área de todos los triángulos (que no se cruzan con puntos de girasol) contenidos en cuadrados (o ventanas) de área fija A está acotada. Sin embargo, hay que considerar el límite cuando A llega al infinito. Entonces tu argumento ya no es válido y obtienes efectivamente triángulos arbitrariamente grandes que no intersecan los puntos girasol en cuadrados suficientemente grandes y suficientemente alejados del origen.

Tu interpretación es correcta: (Hasta el logaritmo,) esto es efectivamente la retícula (prefiero hablar de una traslación de una red euclidiana).

Conclusión: Una solución al problema (si existe) no debería tener regiones arbitrariamente grandes en las que se parezca mucho a un entramado euclidiano (que es el caso del conjunto de puntos del girasol).

Otra bonita idea que desgraciadamente no funciona es tomar el conjunto S de todos los vértices (o baricentros o ???) de todos los triángulos que intervienen en un mosaico de Penrose (dando esas bonitas imágenes cuasiperiódicas con casi simetrías de orden cinco). De hecho, tales mosaicos contienen líneas rectas arbitrariamente largas. Esto implica la existencia de triángulos con un área arbitrariamente grande que no intersecan a S.