FACULTAD DE CIENCIAS Departamento de An´alisis Matem´atico TESIS DE LICENCIATURA

´ M´INIMO NUMERO DE DISTANCIAS ´ DISTINTAS ENTRE UN NUMERO FINITO DE PUNTOS

Alma Luisa Albujer Brotons 2004

´ M´INIMO NUMERO DE DISTANCIAS DISTINTAS ´ ENTRE UN NUMERO FINITO DE PUNTOS por Alma Luisa Albujer Brotons

Alicante, 30 de Septiembre de 2004

Memoria realizada en el Departamento de An´alisis Matem´atico de la Universidad de Alicante durante el curso acad´emico 2003/04 bajo la direcci´on y supervisi´on de Salvador Segura Gomis, Profesor Titular de Universidad de la Universidad de Alicante, por Alma Luisa Albujer Brotons, para optar al Grado de Licenciada.

VB El Director de la Tesina

Fdo.: Salvador Segura Gomis

VB El Director del Departamento

Fdo.: Gaspar Mora Mart´ınez

AGRADECIMIENTOS A Salvador, por tus ense˜ nanzas, tus consejos, y por estar siempre ah´ı cuando he necesitado ayuda. Gracias por todo. A M.a Angeles, a Ana y a Cinzia, por vuestro apoyo inform´atico y todos vuestros consejos. A mis compa˜ neros de la carrera, por esos cinco maravillosos a˜ nos, por su amistad. En especial a Esther, muchas gracias. A mi familia, por apoyarme y entenderme en todo momento. Gracias por estar siempre a mi lado. Al Ministerio de Educaci´on, Cultura y Deporte por concederme una beca de colaboraci´on gracias a la cual he conocido el mundo de la investigaci´on y he podido realizar esta Tesis de Licenciatura.

A mi hermana, Alicia.

´Indice general Introducci´ on

III

1. Resultados cl´ asicos y conjeturas

1

1.1. Puntos en el plano . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2. Puntos en el plano en posici´on general . . . . . . . . . . . . . . . . . 10 1.3. Puntos en el plano en posici´on convexa . . . . . . . . . . . . . . . . . 12 2. Extensiones del problema

15 2

2.1. Extensiones al ret´ıculo entero Z . . . . . . . . . . . . . . . . . . . . . 15 2.2. Extensiones a otros espacios topol´ogicos . . . . . . . . . . . . . . . . 17 2.2.1. Puntos en la esfera . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2. Puntos en el cilindro y en el toro llano . . . . . . . . . . . . . 20 2.3. Extensiones a otros espacios m´etricos . . . . . . . . . . . . . . . . . . 22 2.3.1. Espacios de Minkowski . . . . . . . . . . . . . . . . . . . . . . 22 2.3.2. Espacios m´etricos discretos . . . . . . . . . . . . . . . . . . . . 39 3. Otros problemas relacionados

45

3.1. Distancias repetidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2. Conjuntos de 2-distancias . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3. ¿Puede cada distancia darse un n´ umero distinto de veces? . . . . . . 51 A. Estimaciones asint´ oticas

55

B. Ejemplos de distancias

61

C. Ret´ıculos

69

Bibliograf´ıa

73 i

ii

´INDICE GENERAL

Introducci´ on El nombre de Erd¨os est´a particularmente asociado con el a´rea de la geometr´ıa discreta que considera propiedades geom´etricas de conjuntos finitos de puntos, ya sea en el plano, en Rd , o incluso en otros espacios topol´ogicos, como puede ser la esfera. Por ejemplo, dado un conjunto de n puntos, ¿qu´e se puede decir sobre el conjunto de distancias determinadas por los distintos pares de puntos?, o, ¿qu´e podemos decir sobre el conjunto de a´ngulos o a´reas determinadas por las diferentes tripletas de puntos? La mayor´ıa de los problemas en este campo han sido propuestos por Erd¨os, quien ha llegado a ofrecer sustanciales sumas de dinero por soluciones a algunos de estos problemas. As´ı, fue en 1946 cuando Paul Erd¨os propus´o los siguientes problemas: n puntos   en el plano siempre determinan n2 distancias. Sin embargo, muchas de estas distancias pueden ser iguales. Consideremos f (n) como el m´ınimo n´ umero de distancias diferentes determinadas por n puntos en el plano y g(n) como el m´aximo n´ umero de veces que la distancia uno (o cualquier otra distancia si consideramos las escalas adecuadas) puede darse entre n puntos en el plano. En este caso, ¿qu´e podemos decir sobre f (n) y g(n)? Resulta relativamente sencillo evaluar las dos funciones anteriores para valores peque˜ nos de n. Consideremos en primer lugar el caso m´as sencillo, n = 3. Normalmente, tres puntos en el plano determinan un tri´angulo (excepto en el caso en que los tres puntos est´en alineados), para ello s´olo hemos de considerar los tres puntos como los v´ertices del correspondiente tri´angulo. La distancia entre cada par de puntos vendr´a determinada por la longitud del lado correspondiente. As´ı, en general, tendremos tres situaciones distintas: si el tri´angulo es escaleno, sus tres lados son distintos por lo que tendremos tres distancias diferentes, si el tri´angulo es is´osceles dos de los lados del tri´angulo ser´an iguales, con lo que tendremos s´olo dos distancias, pero s´olo en el caso de que los tres puntos formen los v´ertices de un tri´angulo iii

iv

Introducci´on

equil´atero las tres distancias ser´an iguales. Concluyendo, podemos conseguir que todas las distancias determinadas por un conjunto de tres puntos coincidan y tomen cualquier valor (por ejemplo uno), luego f (3) = 1 y g(3) = 3.

Escaleno

Equil´atero

Is´osceles

Con un razonamiento similar, podemos calcular los valores f (n) y g(n) para otros valores de n. Sin embargo, el n´ umero de distancias determinadas por n puntos aumenta considerablemente al aumentar n con lo que la complejidad del problema cada vez es mayor. Por esta raz´on, en la mayor´ıa de las ocasiones, en vistas a simplificar el problema se buscan estimaciones asint´oticas para ambas funciones. Una estimaci´on asint´otica es una cota v´alida para valores grandes de n. Es decir una estimaci´on asint´otica de una funci´on h es una cota de h (superior o inferior) que se verifica ∀n ≥ n0 , n ∈ N para un cierto valor n0 . Erd¨os prob´o las siguientes respuestas parciales a los problemas anteriores: i) El m´ınimo n´ umero de distancias distintas determinadas por n puntos en el plano es a lo sumo n c1 √ log n (para alguna constante c1 > 0). ii) El m´aximo n´ umero de veces que la distancia uno se puede dar entre n puntos en el plano es al menos 1

n1+c2 log log n (para alguna constante c2 > 0). Adem´as, conjetur´o que los resultados anteriores eran las estimaciones asint´oticas exactas para las funciones f (n) y g(n) respectivamente.

v

Introducci´on Ambas cotas se alcanzan para el conjunto {(x, y) : 0 ≤ x, y <

√

n; x, y enteros}

es decir, para un subconjunto de al menos n puntos del ret´ıculo entero. El ret´ıculo entero es una de las pocas configuraciones sim´etricas conocidas en el plano, y por tanto tiene un especial inter´es como podemos ver a continuaci´on. En la mayor´ıa de los problemas de geometr´ıa discreta y combinat´orica las configuraciones, empaquetamientos, teselaciones... o´ptimos son sim´etricos en alg´ un sentido. De hecho, uno de los principales obst´aculos en el proceso de la investigaci´on en este campo es que se conocen muy pocos patrones sim´etricos compuestos por un n´ umero grande de objetos. Posiblemente, ´esta sea una de las razones por las que las configuraciones reticulares hayan atra´ıdo tanto la atenci´on en los u ´ltimos a˜ nos. Es sorprendente la falta de otro tipo de construcciones sim´etricas puesto que las aplicaciones modernas en cristalograf´ıa y teor´ıa de c´odigos exigen extensivas b´ usquedas inform´aticas de este tipo de configuraciones. Volviendo al problema de estimar las funciones f (n) y g(n), ¿qu´e ocurre si, en vez de considerar sistemas de puntos en el plano, consideramos sistemas de puntos sobre la esfera unidad? La situaci´on aqu´ı difiere del caso del plano principalmente en el siguiente aspecto: no hay ninguna configuraci´on an´aloga al ret´ıculo entero sobre la superficie esf´erica, y por tanto, no hay candidatos obvios que proporcionen estimaciones para las funciones anteriores. Sin embargo, existen otros espacios topol´ogicos, tales como el cilindro o el toro llano que pueden identificarse con regiones planas, y que permiten por tanto considerar configuraciones an´alogas a las ya conocidas en el plano. Otros espacios topol´ogicos donde es posible utilizar t´ecnicas similares a las utilizadas en el plano, es la familia formada por los espacios eucl´ıdeos de dimensi´on arbitraria, es decir, podemos considerar las mismas funciones f (n) y g(n) en Rd con d ≥ 2. Sin embargo, el problema se simplifica bastante al aumentar la dimensi´on y aunque se desconoce el valor de f (n) asint´oticamente, la diferencia entre la mejor estimaci´on superior y la mejor estimaci´on inferior conocidas es considerablemente m´as peque˜ na que en el caso de R2 ([27]). Por otro lado, para d ≥ 4 el problema de determinar g(n) esta resuelto, no s´olo asint´oticamente, sino que Braß([9]) determin´o recientemente el valor exacto de esta funci´on utilizando t´ecnicas referentes a teor´ıa de grafos.

vi

Introducci´on

Aunque en esta tesina se presta un especial inter´es a la funci´on f (n) antes introducida, no hay que olvidar que hay numerosos problemas abiertos sobre distintas propiedades que pueden satisfacer las distancias que determinan todo conjunto finito de puntos. Esta tesina est´a organizada en tres cap´ıtulos que se completan con una serie de ap´endices con el fin de facilitar la comprensi´on de aquellos conceptos necesarios que no est´an directamente relacionados con el tema principal. En el primer cap´ıtulo se presenta el problema de calcular el m´ınimo n´ umero de distancias distintas entre un conjunto de n puntos en el plano y se realiza un estudio de los resultados conocidos. Adem´as, en varias ocasiones, se ha considerado el mismo problema imponiendo determinadas condiciones a los conjuntos de puntos a considerar, cabe destacar el caso en que los puntos se encuentran en posici´on general (es decir, no existen tres puntos alineados ni cuatro sobre una circunferencia) y el caso en que se encuentran en posici´on convexa (los n puntos determinan los v´ertices de un pol´ıgono convexo). El segundo cap´ıtulo estudia varias extensiones del problema anterior. En primer lugar en una primera secci´on se impone a los puntos la restricci´on de pertenecer al ret´ıculo entero, es decir, se trata u ´nicamente con puntos de coordenadas enteras. A continuaci´on, en una segunda secci´on se estudia el problema sobre otros espacios topol´ogicos: en primer lugar se realiza un estudio de los resultados ya conocidos de conjuntos finitos de puntos sobre una superficie esf´erica para considerar despu´es el problema sobre las superficies de un cilindro y de un toro llano. De este modo, las dos primeras secciones del segundo cap´ıtulo tratan variaciones en la topolog´ıa del problema original. Sin embargo, en la u ´ltima secci´on del cap´ıtulo, se estudia el problema modificando la m´etrica. Se realiza en primer lugar un estudio sobre los resultados obtenidos por Swanepoel en espacios de Minkowski y se presenta una prueba alternativa de los resultados obtenidos en dimensi´on 2 y se considera al final el mismo problema sobre determinados espacios m´etricos discretos de especial inter´es. Podemos observar como para cada una de las extensiones tratadas, los valores obtenidos para la funci´on f (n) difieren de los obtenidos en el caso del plano. En el u ´ltimo cap´ıtulo se tratan tres problemas relacionados con el anterior: el problema de hallar el m´aximo n´ umero de veces que la distancia unidad se puede dar entre un conjunto de n puntos, el problema de hallar la cardinalidad de los conjuntos de 2−distancias, y la posibilidad de proporcionar configuraciones de puntos en el

Introducci´on

vii

plano para las cuales cada distancia se de un n´ umero distinto de veces. Para cada uno de estos problemas se resumen los principales resultados obtenidos hasta el momento. Para finalizar se incluyen tres ap´endices. El ap´endice A versa sobre estimaciones asint´oticas, definiendo las distintas comparaciones asint´oticas que se pueden dar entre dos funciones y algunas relaciones entre ellas. El ap´endice B proporciona diversos ejemplos de distancias que ir´an surgiendo a lo largo de esta tesina. Adem´as, proporciona un modo de construir m´etricas a partir de conjuntos cerrados, convexos y centralmente sim´etricos. Para finalizar en el ap´endice C se da la definici´on de ret´ıculo y se presentan algunos ejemplos de ret´ıculos de especial inter´es para el tema que se trata.

viii

Introducci´on

Cap´ıtulo 1 Resultados cl´ asicos y conjeturas 1.1.

Puntos en el plano

  n puntos en el plano determinan siempre n2 distancias. Sin embargo muchas de estas distancias pueden ser iguales. El objetivo de este primer cap´ıtulo es estimar el menor n´ umero de distancias distintas determinadas. Se va a representar este m´ınimo por la funci´on f (n). Claramente, se ve que f (3) = 1 como se comprueba colocando los tres puntos de modo que formen los v´ertices de un tri´angulo equil´atero. ...... .. ... .... ...... ... ......... ....... .... .. ..

n=3 ...... . . .... ... ... .... .............. ...... ...... . ................ n=5

... . ..... ................... . . . . . . .... .... n=4 ....... ...... ..... . ........ ............. .. .. ..... .......... ........... ......... . .. . .. .... ................. ... .. .. .............. .. .... n=6

Figura 1.1. Configuraciones para las que se alcanza el valor f (n).

Tambi´en se ve que f (4) = 2, pero en este caso -y a diferencia de f (3)- no existe una u ´nica configuraci´on que determine el m´ınimo n´ umero de distancias posibles (v´ease la figura 1.1). Por eso interesa tambi´en definir ahora la funci´on r(n) como el n´ umero de configuraciones esencialmente distintas para las cuales se alcanza este m´ınimo. 1

´ CAP´ITULO 1. RESULTADOS CLASICOS Y CONJETURAS

2

Como muestra tambi´en la figura 1.1, f (5) = 2 y f (6) = 3, y por otra parte r(3) = 1, r(4) = 3, r(5) = 1 y r(6) = 3. Para valores peque˜ nos de n resulta relativamente f´acil evaluar estas funciones. Pero, ¿podemos generalizarlo? A pesar de que no se conozca el valor de estas funciones m´as que para unos pocos valores de n, s´ı se conocen estimaciones asint´oticas de ellas. Estos problemas fueron introducidos por Erd¨os en 1946 ([14]) y a ´el se deben tambi´en muchas conjeturas y resultados sobre estimaciones asint´oticas. La primera de ellas se debi´o a Erd¨os que demostr´o que: 1

Teorema 1. n 2  f (n) 

n

1

*

(ln n) 2

Demostraci´ on. Para la cota inferior sea x cualquiera de los n puntos. Veamos enton1 ces que, o bien ocurren al menos (n − 1) 2 distancias distintas entre x y el resto de 1 puntos, o bien hay un circunferencia centrada en x que contiene al menos (n − 1) 2 de los puntos. Para ello supongamos que no se da ninguna de las dos situaciones. Designemos por k(d) al n´ umero de puntos a distancia d de x, y por k¯ al m´aximo de todos 1 estos n´ umeros, es decir, k¯ = m´ax k(d). Entonces, como tenemos menos de (n − 1) 2 d distancias distintas que se repiten a lo sumo k¯ veces, y entre x y el resto de puntos ocurren n − 1 distancias, tendremos que 1 n − 1 < (n − 1) 2 k¯ 1

Por no existir ning´ un c´ırculo centrado en x con (n − 1) 2 puntos, 1

k(d) < (n − 1) 2 para cualquier distancia d, luego como hay un n´ umero finito de puntos al tomar m´aximos 1 k¯ < (n − 1) 2 y por tanto 1

1

n − 1 < (n − 1) 2 (n − 1) 2 = n − 1 lo cual es una contradicci´on con lo que la primera afirmaci´on es v´alida. *

Dadas dos funciones f y g, la notaci´ on f  g significa que existe un n´ umero natural n0 de modo aa que ∀n ≥ n0 , f (n) ≤ g(n). Es decir, para valores suficientemente grandes de n, g(n) superar´ f (n). Para m´ as informaci´on sobre estimaciones asint´oticas, v´ease el Ap´endice A.

1.1. PUNTOS EN EL PLANO

3

y ... ... ... .. ... ... ... ... .

x

Figura 1.2.

Examinemos ahora cada una de las dos posibilidades por separado. En el primer 1 caso tenemos al menos (n − 1) 2 distancias distintas entre los n puntos. En el segundo caso consideremos un punto cualquiera y situado en la circun1 ferencia que contiene al menos (n − 1) 2 de los puntos. Sea el di´ametro que pasa 1 2

por y, entonces existir´a una semicircunferencia que contenga al menos (n−1) de los 2 puntos, y considerando las distancias de y a cada uno de estos puntos, obtendremos al menos dicho n´ umero de distancias distintas. 1 2

En cualquier caso concluimos que se dan al menos (n−1) distancias distintas 2 entre los n puntos. Para terminar, basta tener en cuenta que las funciones 1

g(x) = (x − 1) 2 y 1

h(x) = x 2 tienen el mismo comportamiento asint´otico, con lo que queda probado el resultado deseado. Para la cota superior consideremos en primer lugar n = k 2 , y el conjunto de n puntos P = conv((0, 0), (k − 1, 0), (0, k − 1), (k − 1, k − 1)) ∩ Z2 Hallar todas las posibles distancias entre los n puntos equivale a hallar todas las distancias entre el origen y el resto de puntos situados bajo la diagonal que pasa por el origen, con lo cual obtendremos a lo sumo cn distancias distintas. Sin embargo, alguna de estas distancias puede repetirse, se sabe que el n´ umero de enteros cn diferentes que no exceden 2n y que son de la forma u2 + v 2 es menor que (logn) 1/2

´ CAP´ITULO 1. RESULTADOS CLASICOS Y CONJETURAS

4

([21]); y esto nos permite concluir el resultado deseado. Para n cualquiera, basta con considerar el m´ınimo n´ umero k de modo que n < k 2 . Veamos con un ejemplo como pueden repetirse las distancias consideradas en la u ´ltima parte de la demostraci´on anterior. Consideremos los puntos de Z2 a = (7, 4) y b = (8, 1), entonces a = b, ambos puntos se encuentran bajo la diagonal y sin embargo √ √ d(0, a) = 72 + 42 = 65 √ √ d(0, b) = 82 + 12 = 65 Aqu´ı tenemos un ejemplo de una distancia repetida. ¿C´omo hemos llegado a estos n´ umeros? En general, dos puntos x = (m, n) e y = (p, q) de Z2 equidistar´an del origen si d(0, x) = d(0, y) o bien m 2 + n2 = p 2 + q 2 Operando obtenemos m 2 − p 2 = q 2 − n2 es decir, (m + p)(m − p) = (q + n)(q − n) que se trata de una ecuaci´on diof´antica sencilla. Para resolver hemos de tomar n´ umeros que se puedan descomponer de al menos dos formas distintas como producto de factores. Por ejemplo, 15 = 15 · 1 = 5 · 3 si ahora tomamos m + p = 15, m − p = 1, q + n = 5 y q − n = 3 y resolvemos el sistema obtenemos m = 8, p = 7, q = 4 y n = 1. Por tanto hemos obtenido los puntos x = (8, 1) e y = (7, 1) que son los puntos antes considerados. Erd¨os tambi´en conjetur´o que f (n) n1−ε para todo ε > 0 y quiz´a incluso que f (n) = (1 + o(1))

cn 1

**

(ln n) 2

A partir de la primera estimaci´on asint´otica de Erd¨os se han realizado m´ ultiples 2 mejoras. As´ı, Leo Moser ([23]) prob´o que f (n) n 3 resultado que fue mejorado **

La notaci´ on o(·) se explica en el Ap´endice A.

1.1. PUNTOS EN EL PLANO

5 58

5

por Chung ([10]) a f (n) n 7 y posteriormente a f (n) n 81−ε por Beck ([4]) y a 4 f (n) n 5 por Szemer´edi ([11]). Probaremos el primero de estos resultados. M´as concretamente, el teorema de Leo Moser afirma que 2 n3 f (n) > √ −1 239 Para llegar a este resultado son necesarios dos lemas. Lema 1. Sea r un entero positivo y ε un n´ umero real tal que 0 < ε ≤ 1. Sea P el punto (r + ε, 0) y Q y R dos puntos del primer cuadrante equidistantes de P y con distancias al origen comprendidas entre r y r + 1. Entonces QR < 2. Demostraci´ on. Q

R

R1

Q1

(r, 0) (1, 0) B

0

(r + 1, 0) P

A

Figura 1.3.

Consideremos el c´ırculo centrado en P y que pasa por Q y R que corta a los c´ırculos x2 +y 2 = r2 y x2 +y 2 = (r +1)2 en los puntos Q1 (x, y) y R1 (x+Δx, y +Δy), respectivamente. Por construcci´on Q1 R1 ≥ QR por lo que como queremos demostrar que QR < 2, bastar´a con probar que Q1 R1 < 2, es decir (Q1 R1 )2 = Δx2 + Δy 2 < 4. Por definici´on de Q1 y R1 tenemos x2 + y 2 = r 2 (x + Δx)2 + (y + Δy)2 = (r + 1)2 Como por hip´otesis P Q1 = P R1 y P = (r + ε, 0) tenemos (x − (r + ε))2 + y 2 = ((x + Δx) − (r + ε))2 + (y + Δy)2

´ CAP´ITULO 1. RESULTADOS CLASICOS Y CONJETURAS

6

Desarrollando esta expresi´on obtenemos x2 + (r + ε)2 − 2x(r + ε) + y 2 = (x + Δx)2 + (r + ε)2 − 2x(r + ε) − 2Δx(r + ε) + (y + Δy)2 luego r2 = (r + 1)2 − 2Δx(r + ε) Si despejamos Δx y simplificamos: Δx =

1 − 2ε 2r + 1 =1+ 2r + 2ε 2r + 2ε

Podemos considerar la u ´ltima expresi´on como una funci´on en ε decreciente y como 0 < ε ≤ 1 la funci´on alcanzar´a supremo e ´ınfimo en 0 y 1 respectivamente y por tanto teniendo en cuenta que r ≥ 1 1−

1 1 1 3 3, ya que en otro caso el lema est´a probado. Sustituyendo en la u ´ltima expresi´on 2xΔx + 2yΔy + 3 < 2r + 1 es decir xΔx + yΔy < r − 1 Tengamos ahora en cuenta que x ≤ r entonces utilizando la cota inferior de Δx y despejando Δy tenemos Δy <

r − 1 − x(1 − r − 1 − xΔx < y y

1 ) 2r

≤

r − 1 − x + 1/2 r−x < y y

Despejando y de x2 + y 2 = r2 podemos continuar con la cadena anterior de desigualdades:  r−x r−x ≤1 Δy < √ = r+x r 2 − x2

1.1. PUNTOS EN EL PLANO Tenemos entonces Δx < queda probado el lema.

3 2

7

y Δy < 1 luego Δx2 + Δy 2 <

9 4

+ 1 < 4 con lo que

Lema 2. Sean dos puntos A y B y n puntos m´as P1 , P2 , . . . , Pn situados todos a un lado de la l´ınea AB o sobre ella. De las distancias AP1 , AP2 , . . . , APn , BP1 , BP2 , √ . . . , BPn , al menos n distintas. Demostraci´ on.

B

A

Figura 1.4.

Consid´erense todos los semic´ırculos del mismo lado de la l´ınea AB con centros en A y B que pasan por los puntos P1 , P2 , . . . , Pn . Sean a y b el n´ umero de distintos semic´ırculos con centros en A y en B respectivamente. √ Si m´ax{a, b} ≥ n ya tenemos probado el lema, puesto que cada c´ırculo contiene √ √ al menos uno de los puntos. Si, por el contrario, a < n y b < n entonces el n´ umero √ √ de los puntos de intersecci´on es a lo sumo ab < n n = n ya que cada semic´ırculo centrado en A intersectar´a a lo sumo una vez a cada uno de los semic´ırculos centrados en B y viceversa. Esto contradice el hecho de que los n puntos distintos P1 , P2 , . . . , Pn son puntos de intersecci´on de estos semic´ırculos (sin embargo, si pueden haber m´as de n puntos de intersecci´on). Teorema 2. Para cada n´ umero natural n, 2

n3 f (n) > √ −1 239 Demostraci´ on. Sea P un conjunto de n puntos y sean A y B dos puntos de P de modo que d(A, B) = m´ın{d(x, y) : x, y ∈ P}

8

´ CAP´ITULO 1. RESULTADOS CLASICOS Y CONJETURAS

Para simplificar consideremos d(A, B) = 2. La recta que pasa por A y B determina dos semiplanos, y uno de ellos contendr´a al menos n−2 puntos si excluimos A y B. 2 Trabajaremos s´olo con los puntos de este semiplano. Sea 0 el punto medio del intervalo [A, B] y construyamos semic´ırculos de radios 1, 2, 3, . . . obteniendo una partici´on del semiplano con cajas en forma de medias coronas circulares. Sea s ∈ R de modo que 1 ≤ s ≤ n. Distinguiremos dos casos: CASO 1.- Alguna caja contiene al menos s puntos Consideremos esta caja y la dividimos por la mitad seg´ un la mediatriz del segmento [A, B] como indica la figura 1.3. Como la caja inicial conten´ıa al menos s puntos, al dividirla, una de las dos mitades contendr´a al menos 2s puntos (ya sea en el interior o en la frontera de la caja), sea este conjunto K. Supongamos sin p´erdida de generalidad que nos quedamos con la mitad “m´as pr´oxima” a A, entonces sea Q  sea m´ınimo (es posible hallar Q por ser un punto de K de modo que el a´ngulo AOQ P un conjunto finito de puntos). Supongamos que existen R, S de K equidistantes de Q. Entonces debido a la elecci´on de Q y K, nos encontramos bajo las hip´otesis del lema 1 al considerar como eje X a la recta que pasa por 0 y Q. Aplicando dicho lema concluimos que d(R, S) < 2, lo que contradice que d(A, B) = 2 sea la m´ınima distancia. Por tanto todos los puntos de K distan de Q distancias distintas, con lo que en este caso f (n) ≥

s −1 2

CASO 2.- Ninguna caja contiene s puntos Dividamos las cajas en tres clases del siguiente modo; una caja estar´a en la clase i si, y s´olo si, su radio exterior es r ≡ i(mod 3), i = 1, 2, 3. Entonces, excluyendo A puntos, existir´a una clase con y B, como en el semiplano escogido hay al menos n−2 2 n−2 1 n−2 al menos 2 3 = 6 puntos. Nos quedaremos u ´nicamente con A, B y los puntos de dicha clase. Sea una caja de nuestra clase con radio exterior r. Como d(A, 0) = d(B, 0) = 1, al considerar las distancias d de los puntos de esta caja a A y B, tendremos que r−2 ni i = 1, . . . , t. Como estamos tratando con conjuntos arbitrarios de n puntos, la cota inferior para f (n) ha de ser v´alida para cualesquiera que sean los valores n1 , n2 ,. . . , nt siempre que se verifiquen las desigualdades anteriores. Entonces, para acotar f (n) trataremos de ponernos en la peor “situaci´on”; es decir, buscamos entre todos los √ √ √ posibles valores n1 , n2 ,. . . , nt aquellos que maximicen la suma n1 + n2 +· · ·+ nt . En primer lugar, es muy sencillo demostrar la conocida desigualdad,  √ ni + nj √ ni + nj ≤ 2 2 Para ello basta tener en cuenta que la media aritm´etica de dos n´ umeros es siempre mayor que la media geom´etrica. Esta desigualdad se puede extender f´acilmente a  √ √ √ n1 + n2 + · · · + n t n1 + n2 + · · · + nt ≤ t t Adem´as, la desigualdad se convierte en igualdad si y s´olo si n1 = n2 = · · · = n t Por tanto, como debemos tomar

n−2 6

≤ n1 + · · · + nt , para buscar una cota inferior de f (n) n1 = n2 = · · · = n t =

n−2 6t

´ CAP´ITULO 1. RESULTADOS CLASICOS Y CONJETURAS

10

√ √ √ Sustituyendo estos valores en f (n) ≥ n1 + n2 + · · · + nt y en s > ni , obtenemos dos nuevas desigualdades:   n−2 (n − 2)t f (n) ≥ t = 6t 6 y

n−2 6s Si ahora combinamos ambas desigualdades tenemos t>

f (n) >

n−2 n √ > √ −1 6 s 6 s

Resumiendo, ten´ıamos dos posibles casos y para cada uno de ellos hemos obtenido una cota inferior para f (n). Si tomamos conjuntamente ambos resultados obtenemos: s n f (n) ≥ m´ın{ − 1, √ − 1} 2 6 s donde s era un n´ umero cualquiera de modo que 1 ≤ s ≤ n. El mejor valor de s ser´a el que maximice la cota anterior. Como se trata del m´ınimo entre dos n´ umeros, s n n el m´aximo se obtendr´a cuando tengamos la igualdad 2 −1 = 6√s −1, es decir 2s = 6√ s 2/3

de donde s = n√ . Luego finalmente, sustituyendo el valor de s en cualquiera de los 3 9 argumentos del m´ınimo obtenemos la cota inferior n2/3 f (n) ≥ √ −1 239 Hay numerosas conjeturas concernientes a este tema, por ejemplo: ¿Existen valores de n > 5 para los cuales r(n) = 1? El conjunto de puntos sobre el que se alcanza el m´ınimo, ¿tiene siempre una estructura reticular? ¿Existe siempre una l´ınea que 1 1 contenga cn 2 , o incluso cnε de los puntos para todo ε > 0? ¿Existen cn 2 l´ıneas, o incluso cn1−ε l´ıneas que contengan todos los puntos? En una configuraci´on para la cual se alcance f (n), ¿existen siempre cuatro puntos que determinen s´olo dos distancias, o incluso cuatro puntos que determinen tres distancias distintas? ...

1.2.

Puntos en el plano en posici´ on general

Sea ahora f1 (n) el m´ınimo n´ umero de distancias que pueden darse entre n puntos situados en posici´on general (es decir, que ni se encuentren tres alineados, ni cuatro

´ GENERAL 1.2. PUNTOS EN EL PLANO EN POSICION

11

sobre una circunferencia). En este caso, Erd¨os ([16]) conjetur´o que f1n(n) → ∞ y f1 (n) → 0 cuando n → ∞ y junto con Hickerson y Pach respondi´o afirmativamente n2 a la segunda de estas conjeturas con el siguiente resultado: Teorema 3. Para cada n´ umero natural n, 3 ln 3 3 f1 (n) < n ln 2 < n1,585... 2 2 Demostraci´ on. Consideremos en primer lugar el caso n = 2k y sea P el conjunto de todos los v´ertices del cubo unidad en Rk . Dicho de otra manera, P es el conjunto de todas las (0, 1)-sucesiones finitas x = (x1 , x2 , . . . , xk ) de longitud k. Dados dos puntos cualesquiera de P , x y x se verificar´a entonces que x − x es siempre una (0, 1, −1)-sucesi´on finita. Por tanto, los pares de puntos distintos de P determinan 3k − 1 vectores distintos ya que son todas las posibles (0, 1, −1)-sucesiones finitas k excluyendo el vector nulo. Es m´as, cada uno de estos vectores se da entre 3 2−1 pares de puntos opuestos. Como el conjunto de puntos es finito, siempre podemos elegir un plano 2-dimensional Π ⊆ Rk de modo que la proyecci´on ortogonal de P en Π est´e en posici´on k general. Denotemos por P  a la proyecci´on. P  tambi´en determinar´a a lo sumo 3 2−1 pares de vectores opuestos y, por tanto, el mismo n´ umero de distancias distintas, luego 3k − 1 3k f1 (2k ) < < 2 2 Sea ahora n arbitrario y tomemos k de modo que 2k−1 < n ≤ 2k . Como f1 (·) es claramente no decreciente, tendremos que 3k 2 < n, se tiene (k − 1) log 2 < log n lo cual implica que log n , k 0 de modo que: i) Para cualquier valor 0 < α < 2, g(n, α) ≤ c1 log∗ n √ ii) Para el caso particular en que α = 2 se tiene √ g(n, 2) ≤ c2 n1/3

´ 2.2. EXTENSIONES A OTROS ESPACIOS TOPOLOGICOS

19

Demostraci´ on. Debido a su complejidad, probaremos s´olo la segunda parte. Para ello, se necesita un resultado previo de Erd¨os que afirma la existencia de una constante c2 > 0 de modo que para todo n se pueden encontrar n/2 puntos y n/2 l´ıneas en el plano que verifiquen que cada punto pertenezca al menos a c2 n1/3 de las l´ıneas y cada l´ınea contenga al menos c2 n1/3 de los puntos ([13],teor. 6.18). Consideremos entonces la construcci´on anterior sobre un plano cualquiera y sea O un punto exterior a dicho plano. A cada punto P de la construcci´on anterior le asignamos el vector unidad con origen en O y en la direcci´on OP . An´alogamente, a cada una de las rectas L le asignamos uno de los dos vectores unitarios ortogonales al plano determinado por O y por L. Hemos obtenido as´ı n vectores unitarios con la propiedad que cada uno de ellos es ortogonal al menos a c2 n1/3 otros vectores. Demostremos esta u ´ltima afirmaci´on. Supongamos que v es un vector unitario asociado a un punto P  y sea L una recta cualquiera que contenga a dicho punto, entonces v pertenecer´a al plano determinado por O y L , con lo que v ser´a ortogonal al vector asociado a dicha recta. Como existen al menos c2 n1/3 rectas con esta propiedad, existir´an al menos el mismo n´ umero de vectores de la construcci´on or togonales a v. Y si consideramos v un vector unitario asociado a una recta L , por un razonamiento similar deducimos que v  es ortogonal a cualquiera de los vectores unitarios asociados a los puntos contenidos en L , con lo que llegamos a la misma conclusi´on. Consideremos finalmente el conjunto P de n puntos formado por los extremos de todos estos vectores. Como todos los vectores son unitarios, tendremos que P ⊂ S 2 . Si tomamos ahora un punto cualquiera P ∈ P, por el teorema de Pit´agoras, estar´a a √ distancia 2 de al menos c2 n1/3 de los otros puntos (de aquellos correspondientes a los vectores ortogonales al vector asociado al punto P ), con lo que habremos obtenido el resultado deseado. Como comentarios al teorema anterior, hay que decir que el resultado obtenido √ para α = 2 es m´as fuerte que el obtenido para el resto de distancias ya que asint´oticamente log ∗ n = o(n1/3 ) √ Pero, ¿es 2 especial, o existe una construcci´on similar para otros valores 0 < α < 2? √ Como 2 es la longitud del lado de un octaedro regular inscrito en la esfera unidad, ¿podr´ıamos obtener construcciones especiales para las longitudes de los lados de los otros s´olidos plat´onicos?

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

20

2.2.2.

Puntos en el cilindro y en el toro llano

Consideremos el cilindro como un cuadrado en el que se identifican un par de lados opuestos y el toro llano como un cuadrado en el que se identifican los dos pares de lados opuestos como indica la figura 2.3. -

6

6

6

6

-

Cilindro

Toro llano Figura 2.3.

De este modo podemos trabajar sobre ellos de igual modo que en el plano, pero teniendo en cuenta que las distancias se ven modificadas al existir pares de lados identificados. Para valores peque˜ nos de n es sencillo calcular los valores de f (n) sobre cada una de estas superficies. En la siguiente tabla podemos observar los primeros de estos valores y compararlos con los obtenidos en el caso del plano: f (n)

Plano

Cilindro

Toro llano

3

1

1

1

4

2

1

1

5

2

2

2

6

3

2

2

7

3

3

2

8

4

3

2

9

4

3

2

Cuadro 2.2. Algunos valores de f (n) en diferentes espacios topol´ogicos.

´ 2.2. EXTENSIONES A OTROS ESPACIOS TOPOLOGICOS

21

Estos valores de f (n) se alcanzan en las configuraciones que se muestran en la figura siguiente: Cilindro ................. ... ..... ...... ...... .. ... ... ... ... ................ ..... ..

......................... ... ... .... ... ... .. ...............................

.................................... ... ... ... ... .. ... . .... ..... ..... ......................... ...... ......... .......... . . . ......................................

n=4

n = 5, 6

n = 7, 8, 9

Toro llano .. .. .. ..................................... ... ... ... ................... . . ... . . ... ..... ..... ..... ... ......................... ... ... ... ... ... ... ... . . ... ... .. ................. ..... ................................... .. .. .. n = 5, 6, 7, 8, 9 n=4 Figura 2.4. Configuraciones para las que se alcanza f (n) en el cilindro y en el toro llano.

En general, se obtienen las siguientes cotas superiores para ambos espacios topol´ogicos: Teorema 7. En el cilindro √

f (n) ≤

( 

n  2

√

+ 3)(  2

n ) 2

√ √ √  n  n + (  + 1)( n −   + 1) 2 2

Teorema 8. En el toro llano √

f (n) ≤

( 

n  2

√

+ 3)(  2

n ) 2

Al igual que en la cota hallada en el apartado anterior cuando trat´abamos el problema restringido al ret´ıculo entero, las cotas anteriores no se tratan de cotas asint´oticas, verific´andose para cualquier valor de n y alcanz´andose la igualdad para determinados valores.

22

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

Demostraci´ on. La prueba de ambas cotas es similar a la prueba realizada en el apartado anterior para puntos en Z2 . Para obtener ambas cotas debemos considerar los conjuntos de puntos indicados en la Figura 2.5:

Toro llano

Cilindro Figura 2.5.

As´ı, dado n, sea P el conjunto de puntos resultante de la intersecci´on del ret´ıculo √ √ rectangular generado por {( n, 0), (0,  n)} con el cuadrado unidad I 2 = [0, 1]2 . El cardinal de P es √ √ √ √ |P| =  n n ≥ n n = n, luego f (n) ≤ f (|P|). Ahora bien, debido a las caracter´ısticas de los espacios topol´ogicos que estamos tratando, f (|P|) coincide con el n´ umero de todas las posibles distancias entre el punto se˜ nalado en ambas figuras como ◦ y el resto de puntos de P, que a su vez est´a acotado superiormente por el n´ umero de distancias entre dicho punto y el resto de puntos remarcados. Con un sencillo c´alculo aritm´etico es posible en cada caso contabilizar el n´ umero de dichos puntos.

2.3. 2.3.1.

Extensiones a otros espacios m´ etricos Espacios de Minkowski

El primer matem´atico en tratar este problema para distancias distintas de la eucl´ıdea ha sido Swanepoel ([28]) en 1999. Swanepoel trata el problema en espacios de Minkowski, es decir, espacios de Banach de dimensi´on finita. En realidad, no

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

23

halla estimaciones de f (n), sino que trata un problema equivalente: la cardinalidad de los conjuntos de k−distancias. Se dice que un subconjunto S de un espacio m´etrico es un conjunto de kdistancias si se dan exactamente k distancias no nulas entre puntos de S. Tambi´en se dice que un conjunto de 1−distancia es un conjunto equil´atero. Aunque ya se conoc´ıan resultados referentes a los conjuntos equil´ateros, los conjuntos de k−distancias con k ≥ 2 no se hab´ıan estudiado en espacios no eucl´ıdeos. As´ı, ya se conoc´ıa que para espacios de Minkowski d-dimensionales la m´axima cardinalidad de un conjunto equil´atero es 2d , d´andose la igualdad si y s´olo si la bola unidad del espacio es un paralelep´ıpedo. Adem´as, si d ≥ 3 siempre existe un conjunto equil´atero de al menos 4 puntos. Pero, ¿existe siempre un conjunto equil´atero de d + 1 puntos? Aunque esto sigue siendo una pregunta abierta, Braß ha probado que para cada n existe un n´ umero d = d(n) de modo que cualquier espacio de Minkowski d−dimensional tiene un conjunto equil´atero de al menos n puntos. Swanepoel ha hallado resultados para espacios de Minkowski de dimensi´on gen´erica d, pero u ´nicamente ha resuelto el problema por completo en el caso d = 2, conjeturando la soluci´on en el caso general. En los resultados siguientes consideraremos (Rd ,  · ) un espacio de Minkowski d−dimensional con norma  ·  y denotaremos a la bola cerrada de centro x y radio r > 0 como B(x, r). As´ı, B := B(0, 1) ser´a la bola unidad del espacio. Por el teorema de Mazur-Ulam hemos de tener en cuenta que dos espacios de Minkowski d−dimensionales son isom´etricos si y s´olo si sus bolas unidad son af´ınmente equivalentes. En particular, un espacio de Minkowski tendr´a un paralelep´ıpedo como bola unidad si y s´olo si es isom´etrico a (Rd ,  · ∞ ). Definimos un cono agudo P , aunque nos referiremos a ´el simplemente por cono, como un conjunto convexo en Rd tal que para todo x ∈ P y λ ≥ 0 se tiene λx ∈ P y que satisface P ∩ −P = {0}. Cualquier cono determina un orden parcial sobre Rd definido por x≤y ⇔ y−x∈P En general, denotaremos la cardinalidad de un conjunto S por S. Dado un conjunto medible S ⊆ Rd , denotamos su medida de Lebesgue como vol(S). Antes de comenzar con los principales resultados obtenidos por Swanepoel necesitamos el siguiente lema previo que es la versi´on de Lyusternik de la desigualdad de Brunn-Minkowski:

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

24

Lema 4. Si A, B ⊆ Rd son conjuntos compactos, entonces vol(A + B)1/d ≥ vol(A)1/d + vol(B)1/d Adem´ as, si la igualdad se verifica y vol(A), vol(B) > 0, entonces A y B son cuerpos convexos de modo que A = υ + λB para alg´ un λ > 0 y υ ∈ Rd . Veamos ya los principales resultados: Teorema 9. Si la bola unidad de un espacio de Minkowski d−dimensional X es un paralelep´ıpedo, entonces un conjunto de k−distancias en X tiene cardinalidad a lo as, esta cota se alcanza en determinados conjuntos. sumo (k + 1)d . Adem´ Demostraci´ on. Por las observaciones anteriores, podemos considerar, sin p´erdida de generalidad, que el espacio es (Rd ,  · ∞ ). Consideremos para cada i = 1, . . . , d el orden parcial ≤i determinado por el cono Pi = {(λ1 , . . . , λd ) ∈ Rd : m´ax |λj | = λi } j=1,...,d

Sea S un conjunto de k−distancias. Para cada x ∈ S sea hi (x) la longitud de la cadena descendiente m´as larga seg´ un el orden ≤i comenzando en x. Es decir, hi (x) es el mayor entero h de modo que exitan x1 , x2 , . . . , xh ∈ S tales que x >i x1 >i x2 >i . . . >i xh . d  Es directo comprobar que (Pi ∪ −Pi ) = Rd . Por tanto, para cualquier par de i=1

puntos distintos x, y existe un i ∈ {1, . . . , d} tal que x j x1 >j . . . >j xhj (x) , luego hj (y) ≥ hj (x) + 1 y por tanto son distintos, con lo que (h1 (x), . . . , hd (x)) = (h1 (y), . . . , hd (y)) y la aplicaci´on es inyectiva. Consecuentemente, si h :=

m´ax

x∈S, i=1,...,d

hi (x)

tendremos S ≤ (h + 1)d

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

25

Basta con probar ahora que h ≤ k. Ve´amoslo por reducci´on al absurdo. Supongamos que k < h, entonces para alg´ un x ∈ S e i ∈ {1, . . . , d} existen x1 , . . . , xk+1 ∈ S de modo que x >i x1 >i . . . >i xk+1 . Por ser S un conjunto de k−distancias, se tendr´a x − xm ∞ = x − xn ∞ para alg´ un 1 ≤ m < n ≤ k + 1. Por transitividad tenemos x >i xm y x >i xn , luego x − xm , x − xn ∈ Pi . Sin embargo, es inmediato observar que si a∞ = b∞ con a, b ∈ Pi , a = b entonces a − b ∈ / Pi . Por tanto (x − xn ) − (x − xm ) = xm − xn ∈ / Pi con xm >i xn , lo que es una contradicci´on. Veamos por u ´ltimo que la cota se alcanza para determinados conjuntos de kdistancias. S = {0, 1, . . . , k}d es un conjunto de k-distancias de cardinalidad (k +1)d . Es m´as, se puede probar que los u ´nicos conjuntos de k−distancias con cardinalidad (k + 1)d son de la forma S = a + λ{0, 1, . . . , k}d con a ∈ Rd y λ > 0. Teorema 10. Dado cualquier conjunto S de n puntos en un espacio de Minkowski d−dimensional con un paralelep´ıpedo como bola unidad, existe un punto en S desde el que se dan al menos n1/d  − 1 distancias distintas no nulas a puntos de S. Adem´ as, la cota se alcanza para determinados conjuntos. Demostraci´ on. Consideremos la misma aplicaci´on que en la prueba del teorema anterior: x → (h1 (x), . . . , hd (x)). Si de nuevo h es la longitud de la mayor cadena seg´ un el orden parcial ≤i para todo i, de un modo an´alogo al anterior concluimos un valor que n ≤ (h + 1)d , o equivalentemente h ≥ n1/d  − 1. Es decir, para alg´ i ∈ {1, . . . , d} existe una cadena x0 >i x1 >i . . . >i xh de longitud h ≥ n1/d  − 1. De la prueba anterior tambi´en deducimos que todas las distancias dist(x0 , xj ) con j ∈ {1, . . . , h} son distintas. As´ı existe un punto x0 desde el que se dan al menos h distancias no nulas distintas, y como h ≥ n1/d  − 1, obtenemos la cota buscada. Adem´as dado cualquier conjunto S ⊆ Rd de modo que {0, 1, . . . , n1/d  − 2}d  {0, 1, . . . , n1/d  − 1}d satisface que tiene exactamente n1/d −1 distancias distintas entre sus puntos seg´ un la norma  · ∞ Si observamos con detenimiento la prueba del Teorema 9 nos damos cuenta que podemos generalizar tanto la definici´on de los conos Pi como la elecci´on de la m´etrica siempre y cuando satisfagan unas propiedades m´ınimas. As´ı podemos generalizar el Teorema 9 obteniendo el siguiente corolario:

26

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

Corolario 1. Supongamos que {Pi : i ∈ I} es una familia de conos en un espacio de Minkowski (Rd ,  · ) que satisface  (Pi ∪ −Pi ) = Rd i∈I

y ∀i ∈ I ∀x = y x, y ∈ Pi , si x = y entonces ± (x − y) ∈ / Pi Entonces un conjunto de k−distancias en (Rd ,  · ) tiene cardinalidad a lo sumo (k + 1)I Para proseguir con los resultados de Swanepoel necesitamos una serie de lemas previos: Lema 5. Sea S un conjunto de k−distancias en un espacio m´etrico (X, ρ) con un valor i ∈ distancias ρ1 < ρ2 < . . . < ρk . Si ρk /ρ1 > 2k−1 , entonces para alg´ {1, . . . , k − 1}, la relaci´ on x ∼i y ⇔ ρ(x, y) ≤ ρi es una relaci´ on de equivalencia. Demostraci´ on. Para cualquier valor i la relaci´on ∼i es reflexiva y sim´etrica, por lo que s´olo tenemos que comprobar la transitividad. Supongamos que para un determinado valor i la relaci´on no es transitiva. Entonces existen x, y, z ∈ S de modo que ρ(x, y) ≤ ρi , ρ(y, z) ≤ ρi pero ρ(x, z) > ρi . Por ser S un conjunto de k−distancias con distancias ρ1 < ρ2 < . . . < ρk , ρ(x, z) > ρi implica ρ(x, z) ≥ ρi+1 y por la desigualdad triangular ρi+1 ≤ ρ(x, z) ≤ ρ(x, y) + ρ(y, z) ≤ 2ρi . Si esto es cierto para cualquier valor i ∈ {1, . . . , k − 1} tendremos ρk ≤ 2ρk−1 ≤ · · · ≤ 2k−2 ρ2 ≤ 2k−1 ρ1 , luego ρk /ρ1 ≤ 2k−1 lo que contradice las hip´otesis. Por tanto existe al menos un n´ umero i ∈ {1, . . . , k − 1} tal que la relaci´on ∼i es una relaci´on de equivalencia. Lema 6. La cardinalidad de un conjunto de k−distancias en un espacio de Minkowski d−dimensional es a lo sumo 2kd . Demostraci´ on. Sea S := {x1 , . . . , xm } un conjunto de k−distancias con distancias ρ1 < ρ2 < . . . < ρk y consideremos el conjunto V :=

m  i=1

B(xi , ρ1 /2)

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

27

Por ser ρ1 la distancia m´as peque˜ na, V es una uni´on de m bolas disjuntas de igual radio, y por tanto de igual volumen. As´ı, vol(V ) = m(ρ1 /2)d vol(B) Por otra parte sean x, y ∈ V , por definici´on de V existir´an i y j de modo que x − xi  ≤ ρ1 /2 e y − xj  ≤ ρ1 /2. Por la desigualdad triangular tenemos x − y ≤ x − xi  + xi − xj  + y − xj  ≤

ρ1 ρ1 + ρk + = ρ1 + ρk 2 2

de donde V − V ⊆ B(0, ρ1 + ρk ) y por tanto vol(V − V ) ≤ (ρ1 + ρk )d vol(B) Si aplicamos la desigualdad de Brunn-Minkowski del lema 4 para A := V y B := −V tenemos vol(V − V )1/d ≥ vol(V )1/d + vol(−V )1/d Teniendo en cuenta las relaciones antes obtenidas para vol(V − V ) y vol(V ) y que vol(V ) = vol(−V ), la desigualdad anterior se traduce en ρ1 + ρk ≥ m1/d ρ1 o equivalentemente m ≤ (1 + ρk /ρ1 )d . Si 1 + ρk /ρ1 ≤ 2k ya est´a, puesto que S = m ≤ (1 + ρk /ρ1 )d ≤ 2kd . En otro caso ρk /ρ1 > 2k − 1 ≥ 2k−1 , luego por el lema anterior para alg´ un i ∈ {1, . . . , k − 1}, x ∼i y ⇔ ρ(x, y) ≤ ρi es una relaci´on de equivalencia. Deduciremos el resultado por inducci´on sobre k. Para k = 1 tenemos un conjunto equil´atero, y en este caso ya se sabe que su cardinalidad m´axima es 2d . Supongamos ahora que todo conjunto de i−distancias con i ∈ {1, . . . , k − 1} tiene a lo sumo 2id puntos, entonces cada clase umero total de equivalencia tambi´en tendr´a a lo sumo 2id puntos. Falta estimar el n´ de clases de equivalencia. Para ello tomemos un representante de cada una de las clases. Estos representantes forman un conjunto de (k − i)−distancias puesto que la distancia entre dos puntos de dos clases de equivalencia distintas ha de ser mayor que ρi . Como k − i ∈ {1, . . . , k − 1} tendremos a lo sumo 2(k−i)d representantes y el mismo n´ umero de clases de equivalencia. Como las clases de equivalencia forman una partici´on de S, tenemos a los sumo 2(k−i)d clases y cada una de ellas contiene a lo sumo 2id puntos tenemos finalmente S ≤ 2(k−i)d 2id = 2kd .

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

28

Lema 7. Sean B1 = conv(±1, 0), (0, ±1) y B∞ = [−1, 1]2 . Para cualquier disco C ⊂ R2 convexo y centralmente sim´etrico existe una transformaci´ on lineal inversible   que transforma C en C de modo que B1 ⊆ C ⊆ B∞ y tal que cualquier segmento de l´ınea recta contenido en la frontera de C  quede contenido completamente en uno de los cuatro cuadrantes coordenados. Demostraci´ on. Podemos suponer sin p´erdida de generalidad, que el origen 0 es un punto interior de C, ya que en otro caso, bastar´ıa con considerar un trasladado de C. Consideremos todos los tri´angulos con v´ertices 0, x, y, donde x e y est´an en la frontera de C. Por compacidad de C existen dos puntos de la frontera de C: x0 , y0 de modo que el a´rea del correspondiente tri´angulo es m´axima. {x0 + λy0 : λ ∈ R} es un hiperplano soporte de C en x0 ya que en otro caso podr´ıamos obtener un tri´angulo de mayor a´rea con v´ertices 0, y0 , x siendo x un punto de la frontera de C del otro ´ lado del hiperplano. Analogamente, {y0 + λx0 : λ ∈ R} es un hiperplano soporte de C en y0 . Por ser C centralmente sim´etrico, de los resultados anteriores se sigue que C est´a contenido en el paralelogramo {λx0 + μy0 : −1 ≤ λ ≤ 1, −1 ≤ μ ≤ 1} y por convexidad contiene al paralelogramo conv(x0 , 0), (−x0 , 0), (0, y0 , ), (0, y0 ).

y0 .. . . . . . . . . ............ . . . . . . . . . .... . . ... . .. . . .. .. .. ... .. ... . ... ..... ... . .. . . . . .. .. .. .. ... . ........... . . . . . . . .... . . . . . . . . ........ .. .. .. ... . . . 0... ... .. x0 .. .. ... ... .. .. ... .. ... ..... ... ... .. .. ... . . . . .. .. .. C .... . . . . . . . . . ............ . . . . . . . . ...

-

e2 .. .............. .. ... .................. . .. 6 . . ... . . . .. . ... ... ... . . . . . .. ... ... ... .. ... ... .. ..... ...... . ...... e1 ........ . . . .. ... . . ... ... .. .. ... ... . . ... .. ... .... ... ... ... C  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..

{x0 + λy0 : λ ∈ R}

Figura 2.6.

Si x0 es un punto interior de un segmento de l´ınea recta, podemos cambiarlo por un extremos de dicho segmento sin que se vea modificada el a´rea del tri´angulo y de modo que C siga contenido en el mismo paralelogramo. El mismo razonamiento es v´alido para y0 . Basta considerar ahora la transformaci´on lineal que transforma x0 e y0 en e1 y e2 respectivamente. Como hab´ıamos evitado que x0 e y0 fueran puntos interiores de segmentos de l´ınea recta, lo mismo ocurrir´a con e1 y e2 , y por tanto,

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

29

cualquier segmento de l´ınea recta en la frontera de C estar´a contenido ´ıntegramente en uno de los cuatro segmentos. Por u ´ltimo , el paralelogramo {λx0 + μy0 : −1 ≤ λ ≤ 1, −1 ≤ μ ≤ 1} se transforma en B∞ y conv(x0 , 0), (−x0 , 0), (0, y0 , ), (0, y0 ) en B1 , con lo que se verifican las relaciones de inclusi´on del lema, al ser la relaci´on de inclusi´on invariante mediante transformaciones lineales. Los siguientes teoremas son de particular inter´es ya que tratan el problema en espacios de Minkowski 2−dimensionales obteniendo resultados m´as fuertes. Teorema 11. La cardinalidad de un conjunto de k−distancias en un espacio de Minkowski 2−dimensional es a lo sumo (k + 1)2 , con igualdad si y s´olo si la bola unidad del espacio es un paralelogramo. Demostraci´ on. Para probar la primera afirmaci´on, aplicaremos el Corolario 1 para lo que hemos de hallar dos conos P1 y P2 que satisfagan las hip´otesis de este corolario. Por el lema 7, podemos considerar que el espacio m´etrico es (R2 ,  · ) de modo que la bola unidad B de  ·  satisfaga B1 ⊂ B ⊂ B∞ y de modo que cualquier segmento de l´ınea recta en la frontera de B est´e contenido en un u ´nico cuadrante del plano. Consideremos en primer lugar P1 el primer cuadrante cerrado, y P2 el segundo cuadrante cerrado. P1 y P2 satisfacen trivialmente la primera condici´on del corolario puesto que P1 ∪ −P1 ∪ P2 ∪ −P2 = R2 La segunda condici´on afirma que ∀i = 1, 2 ∀x = y x, y ∈ Pi , si x = y entonces ± (x − y) ∈ / Pi Debido a las propiedades de la bola unidad B expresadas antes y a su convexidad, la u ´nica manera de que se viole la segunda condici´on del corolario es que los dos puntos x, y ∈ Pi tales que x = y se encuentren en un segmento de l´ınea recta paralela a cualquiera de los dos ejes. As´ı, si existe un segmento en la frontera de B en P1 paralelo al eje X, basta con eliminar el semieje positivo X de P1 , es decir, tomar P1 := {(x1 , x2 ) ∈ R2 : x1 ≥ 0, x2 > 0}. Si existiera un segmento de l´ınea recta en la frontera de B contenido en P2 paralelo al eje X, habr´ıa un segmento de l´ınea recta en la frontera de B en los dos primeros cuadrantes, lo cual es una contradicci´on. Por tanto, no ser´ıa necesario eliminar el eje X tambi´en de P2 con lo que se seguir´ıa satisfaciendo la primera condici´on del corolario. Basta hacer ahora el mismo proceso para P2 y los segmentos de l´ınea recta paralelos al eje Y. Al final,

30

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

habremos encontrado dos conos que satisfacen las condiciones del corolario 1, de donde se deduce S ≤ (k + 1)2 . Supongamos ahora que se verifica la igualdad. Revisando la prueba del teorema 9 observamos que la aplicaci´on x → (h1 (x), h2 (x)) tiene que ser una biyecci´on de S en {0, . . . , k}2 . Denotemos cada punto x ∈ S por pi,j , donde (i, j) = (h1 (x), h2 (x)). Supongamos que dos de las distancias p0,i − p0,0  (i = 1, . . . , k) son iguales, es decir supongamos que p0,i −p0,0  = p0,j −p0,0  para determinados valores 0 < i < j. Puesto que P1 ∪ −P1 ∪ P2 ∪ −P2 = R2 , tendremos p0,i − p0,0 ∈ P1 ∪ −P1 ∪ P2 ∪ −P2 , es decir, los puntos p0,i y p0,0 tienen que estar relacionados, bien mediante el orden parcial >1 o mediante >2 . Como la primera componenete de ambos puntos es 0, esto indica que nos son >1 comparables, y por tanto ha de ser p0,i >2 p0,0 . De modo an´alogo con p0,j y p0,i se tiene p0,j >2 p0,i , luego p0,j >2 p0,i >2 p0,0 y por tanto p0,i − p0,0 , p0,j − p0,0 ∈ P2 , lo que contradice la segunda condici´on del corolario. Por tanto, las distancias p0,i − p0,0 , i = 1, . . . , k son todas distintas, y son exactamente las k distancias distintas en orden creciente: p0,i − p0,0  = ρi , i = 1, . . . , k. De un modo an´alogo se prueba que las distancias p0,i − p0,1 , i = 2, . . . , k son distintas en orden creciente. Supongamos que p0,k − p0,1  = ρk , entonces como antes se tendr´a p0,k − p0,1  = p0,k − p0,0  con p0,k >2 p0,1 >2 p0,0 , luego p0,k − p0,0 , p0,k − p0,1 ∈ P2 obteniendo de nuevo una contradici´on. Por tanto p0,i − p0,1  = ρi−1 , i = 2, . . . , k. Si proseguimos con el mismo proceso, llegamos a que p0,i+1 − p0,i  = ρ1 para todo i = 0, . . . , k − 1. Y aplicando la desigualdad triangular, ρk = p0,k − p0,0  ≤ p0,k − p0,k−1  + p0,k−1 − p0,k−2  + · · · + p0,1 − p0,0  = ρ1 + ρ1 + · · · + ρ1 = kρ1 , luego ρk ≤ kρ1 Si revisamos las desigualdades obtenidas en la prueba del lema 6, observamos que ρk ≤ kρ1 implica que la u ´ltima de estas desigualdades: m ≤ (1 + ρk /ρ1 )d (en este caso d = 2) se verifica con igualdad. Para verlo basta observar por un lado que como m es la cardinalidad del conjunto m = (k + 1)2 , y por otro lado (1 + ρk /ρ1 )2 ≤ (1 + kρ1 /ρ1 )2 = (k + 1)2 con lo que (k + 1)2 = m ≤ (1 + ρk /ρ1 )2 ≤ (k + 1)2 , y esto s´olo puede ser posible si la desigualdad se verifica con igualdad. Sin embargo, el ser esta u ´ltima desigualdad una igualdad, implica que todas las desigualdades anteriores tambi´en han de serlo, en particular: vol(V − V )1/2 = vol(V )1/2 + vol(−V )1/2

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

31

y vol(V − V ) = (ρ1 + ρk )2 vol(B) Por tanto V y V − V son homot´eticas y, adem´as, como ten´ıamos V :=

S 

B(xi , ρ1 /2)

y

V − V ⊆ B(0, ρk + ρ1 ),

i=1

ha de ser V − V = B(0, ρk + ρ1 ). Por tanto, V es una bola teselada por bolas m´as peque˜ nas. Por un conocido resultado de teselaciones ([18]), esto implica que la bola unidad es un paralelogramo, con lo que queda probado el teorema. Teorema 12. Dado cualquier conjunto de n puntos en un espacio de Minkows√ ki 2−dimensional, existe un punto en S desde el que se dan al menos  n − 1 distancias distintas no nulas al resto de puntos de S. Demostraci´ on. La prueba de este teorema se sigue de la del teorema anterior del mismo modo que la prueba del teorema 10 se sigue de la del teorema 9. Por u ´ltimo, el siguiente teorema establece una cota de la cardinalidad de los conjuntos de k−distancias para una dimensi´on d gen´erica: Teorema 13. La cardinalidad de un conjunto de k−distancias en un espacio de Minkowski d−dimensional es a lo sumo m´ın{2kd , (k + 1)(11

d −9d )/2

}.

Demostraci´ on. El lema 6 proporciona la primera parte de la prueba ya que afirma que la cardinalidad de un conjunto de k−distancias est´a acotada superiormente por 2kd . Para hallar la otra cota aplicaremos el corolario 1. Necesitamos una familia de conos {Pi : i ∈ I} que satisfagan  (Pi ∪ −Pi ) = Rd i∈I

y ∀i ∈ I ∀x = y x, y ∈ Pi , si x = y entonces ± (x − y) ∈ / Pi Veamos en primer lugar que para demostrar que un cono P satisface la segunda propiedad, es suficiente con que ∀a, b ∈ P : si a = b = 1, entonces a − b < 1

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

32

Para ello, supongamos que P no satisface la segunda condici´on del corolario y por tanto existen x, y ∈ P, x = y de modo que x = y y y − x ∈ P . Consideremos los vectores unitarios: a := y sea 0 < λ :=

x y−x + x

x , x

b :=

y y

y

c :=

y−x , y − x

< 1. Entonces,

(1 − λ)(a − c) + λb = x x y−x x y )( − )+ y − x + x x y − x y − x + x y x x y − x y−x y = (1 − ) − + y − x + x x y − x + x y − x y − x + x x x y−x y = − − + x y − x + x y − x + x y − x + x x = a, = x

= (1 −

luego a = (1 − λ)(a − c) + λb y por la desigualdad triangular 1 = a = (1 − λ)(a − c) + λb ≤ (1 − λ)(a − c) + λb = (1 − λ)(a − c) + λ luego a − c ≥ 1 Con respecto a la primera hip´otesis del corolario, bastar´a con cubrir la semiesfera unidad por conjuntos tales que si consideramos los correspondientes conos positivos sean convexos. Para obtener estos conjuntos, consideremos C = {c1 , c2 , . . . , cm } un conjunto maximal de vectores unitarios de modo que ci − cj , ci + cj  ≥ 1/5 ∀1 ≤ i < j ≤ m. Dado C con estas caracter´ısticas, para cada vector unitario x ha de existir un i tal que ci − x < 1/5 o ci + x < 1/5, puesto que de otro modo, podr´ıamos considerar C  = C ∪ {x} y C ya no ser´ıa maximal.

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

33

Para i = 1, . . . , m, sea Pi el cono generado por Qi := {x ∈ Rd : x = 1, ci − x < 1/5} es decir

 Pi := { λj xj : λj ≥ 0, xj ∈ Qi } j

Es inmediato comprobar, por la desigualdad triangular, que los conjuntos Qi son convexos, y por tanto que tambi´en lo son los correspondientes conos Pi . Adem´as, por maximalidad de C,  (Pi ∪ −Pi ) = Rd i∈I

 S´olo falta comprobar que los conos verifican la segunda condici´on: sea λj xj ∈ j  Pi , con λj ≥ 0, xj  = 1, ci − xj  < 1/5 y  λj xj  = 1. Entonces por una parte j    1 =  λj xj  ≤ λj xj  = λj , y por tanto j

j

ci −

j



λj xj  = 

j



λj (ci − xj ) + (1 −

j

≤

 

λj )ci 

j

λj ci − xj  + |1 −

j

<



λj /5 − 1 +

j





λj |ci 

j

λj =

j

6 λj − 1 5 j

Tambi´en tenemos      1+ λj /5 >  λj xj  + λj xj − λj ci  ≥ λj ci  = λj de donde



j

j

j

j

j

λj < 5/4 y por tanto

j

ci −



λj xj  <

j

65 1 −1= 54 2

Sean por tanto x, y ∈ Pi tales que x = y = 1, entonces los elementos ser´an   de la forma x = λj xj , y = μj yj con λj ≥ 0, μj ≥ 0, xj  = yj  = 1, j j   ci − xj  < 1/5, ci − yj  < 1/5 y  λj xj  =  μj yj  = 1. Podemos aplicar los j

j

resultados anteriores, y as´ı: x − y ≤ ci − x + y − ci  = ci − x + ci − y < 1/2 + 1/2 = 1

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

34

con lo que se satisface la segunda hip´otesis del corolario 1 seg´ un la primera parte de la prueba. Aplicando el corolario 1, obtenemos que la cardinalidad de un conjunto de k−distancias es a lo sumo (k + 1)I donde I representa el conjunto de ´ındices de los conos Pi , luego I = C. Como C es un conjunto de vectores unitarios tales que para cualquier par ci , cj ∈ C, ci + cj  ≥ 1/5 y ci − cj  ≥ 1/5, es inmediato comprobar que las bolas 1 9 B(0, ), B(±ci , ), i = 1, . . . , m 10 10 tienen interiores disjuntos y est´an contenidas en la bola B(0, 11 ). Por tanto, 10   9 1 1 vol(B(0, )) + vol(B(ci , )) + vol(B(−ci , )) ≤ vol(B(0, 11/10)) 10 10 10 i=1 i=1 m

m

es decir, (

9 d 1 11 ) vol(B) + 2m( )d vol(B) ≤ ( )d vol(B) 10 10 10

y por tanto 1 C = m ≤ (11d − 9d ) 2 con lo que queda demostrado el resultado deseado. A partir de los teoremas 9 y 11, Swanepoel formula la siguiente conjetura: Conjetura 1. La cardinalidad de un conjunto de k−distancias en un espacio de Minkowski d−dimensional es a lo sumo (k + 1)d , con igualdad si y s´olo si la bola unidad del espacio es un paralelep´ıpedo. Por los resultados mencionados al principio, esta conjetura es cierta para conjuntos equil´ateros, es decir cuando k = 1. Por otra parte, el teorema 11 prueba que la conjetura es cierta para d = 2. Finalmente, el teorema 9 demuestra que la conjetura es cierta en el caso general cuando la bola unidad sea un paralelep´ıpedo. Presentaremos ahora una prueba alternativa al resultado obtenido por Swanepoel para el caso del plano. Es decir, probaremos que, para cualquier espacio de Minkowski 2-dimensional, la cardinalidad de un conjunto de k-distancias es a lo sumo (k + 1)2 con igualdad si y s´olo si la bola unidad es un paralelogramo, o equi√ valentemente, en un espacio de Minkowski 2−dimensional f (n) ≥  n − 1 con √ igualdad f (n) =  n − 1 si y s´olo si la bola unidad del espacio es un paralelogramo.

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

35

Una espacio m´etrico 2−dimensional de especial inter´es es aquel que tiene asociada la distancia del taxi. En este caso, la bola unidad del espacio es un cuadrado, luego un paralelogramo. Lema 8. En un espacio de Minkowski 2−dimensional cuya bola unidad es un paralelogramo, √ f (n) ≤  n − 1 Demostraci´ on. Supongamos que estamos trabajando con la distancia del taxi. Sea L el ret´ıculo generado por los vectores (1, 1) y (1, −1). Sea p un n´ umero entero y definimos Kp como el conjunto de puntos determinado por Kp = L ∩ (0, 0), (p − 1, −(p − 1)), (2(p − 1), 0), (p − 1, p − 1). Dado n, consideremos K√n . Este conjunto contiene al menos n puntos puesto √ √ √ √ que K√n =  n n ≥ n n = n y por tanto, siempre podemos seleccionar ´ltimo es inmediato comprobar que los puntos de n puntos del conjunto K√n . Por u √ K√n determinan  n − 1 distancias distintas no nulas entre ellos, lo que completa la prueba en el caso de la distancia del taxi. Esta prueba es generalizable a cualquier otro espacio de Minkowski cuya bola unidad sea un paralelogramo, para ello basta considerar el ret´ıculo determinado por dicho paralelogramo. En la Figura 2.7 podemos ver la configuraci´on o´ptima para la que se alcanza la cota en un caso gen´erico, es decir, K√n .

Figura 2.7.

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

36

Veamos ahora que en efecto el lema anterior no presenta u ´nicamente una cota superior, sino una determinaci´on precisa del m´ınimo n´ umero de distancias distintas. Lema 9. En un espacio de Minkowski 2−dimensional cuya bola unidad es un paralelogramo, √ f (n) ≥  n − 1 Demostraci´ on. Consideremos las circunferencias m´etricas, que en este caso tendr´an forma de paralelogramo, como el lugar geom´etrico de los puntos del plano que est´an a distancia r de un punto p ∈ R2 : S(p, r) = {x ∈ R2 : dist(p, x) = r} Para demostrar el lema, hallaremos el m´aximo n´ umero de puntos que determinan a lo sumo m distancias entre ellos. Es decir, pretendemos determinar la m´axima cardinalidad de un conjunto de m−distancias. Como siempre trabajamos con un n´ umero finito de puntos, habr´an al menos dos puntos a y b de modo que la distancia entre ellos sea la m´axima posible. El resto de puntos deben estar situados en la intersecci´on de m circunferencias m´etricas centradas en a y m circunferencias m´etricas centradas en b. Si no queremos aumentar el n´ umero de distancias distintas, los radios de las circunferencias m´etricas deben ser proporcionales a los n´ umeros naturales {1, . . . , m}, es decir, los radios ser´an

m dist(a, b) i . m i=1 Hay dos posibles situaciones: i) Todas las circunferencias m´etricas tienen intersecciones propias, es decir, los puntos de intersecci´on entre una circunferencia centrada en a y otra centrada en b son asilados. Adem´as, cada par de estas circunferencias m´etricas determinan un par de pseudodiscos* y se sabe para cada par de pseudodiscos se dan a lo sumo dos intersecciones propias entre sus fronteras ([6]). En este caso obtenemos que el n´ umero m´aximo de posibles puntos es (m + 1)2 y que est´an distribuidos en un trasladado del conjunto Km+1 . Esto proporciona la cota inferior buscada. Podemos observar esta configuraci´on en la Figura 2.8: *

Se dice que un par σ1 , σ2 de objetos planos son un par de pseudodiscos si satisfacen la siguiente propiedad: σ1 \σ2 y σ2 \σ1 son conjuntos conexos.

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

37

a

b

Figura 2.8.

ii) Hay alg´ un para de circunferencias m´etricas que no tienen intersecci´on propia pero son tangentes. En este caso, como indica la Figura 2.9, las circunferencias son tangentes a lo largo de un segmento de l´ınea recta. Si consideramos ahora los extremos de dichos segmentos y tomamos de nuevo las circunferencias m´etricas centradas en estos extremos, concluimos que de nuevo no hay m´as de (m + 1)2 posibles puntos, con lo que obtenemos de nuevo la misma cota inferior.

a

b

Figura 2.9.

Es f´acil ver que los argumentos empleados en la prueba del lema anterior tambi´en son v´alidos para cualquier espacio de Minkowski 2−dimensionales, ya que la bola unidad de cualquiera de estos espacios es un pseudodisco.

38

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

Sin embargo no ocurre lo mismo con el lema 8, ´este s´olo es v´alido en el caso en que la bola unidad del espacio sea un paralelogramo, por lo que la igualdad s´olo se alcanza en este caso: Corolario 2. En un espacio de Minkowski 2−dimensional √ f (n) ≥  n − 1 verific´ andose la igualdad si y s´ olo si la bola unidad del espacio es un paralelogramo. Sin embargo, el corolario anterior no es v´alido para m´etricas generales que no sean de Minkowski. Consideremos, por ejemplo, la conocida distancia de correos definida como d((x1 , y1 ), (x2 , y2 )) = d2 ((x1 , y1 ), (0, 0)) + d2 ((0, 0), (x2 , y2 )) donde d2 representa la distancia eucl´ıdea en el plano. En este caso, podemos determinar un conjunto S con cardinalidad infinita en el plano de modo que dado cualquier par de puntos, la distancia entre ellos es uno: d((x1 , y1 ), (x2 , y2 )) = 1 ∀(x1 , y1 ), (x2 , y2 ) ∈ S Para ello, basta tomar S la circunferencia de radio 1/2 centrada en (0, 0). Dados dos puntos (x1 , y1 ), (x2 , y2 ) ∈ S se tiene que d2 ((x1 , y1 ), (0, 0)) = d2 ((x2 , y2 ), (0, 0)) = 1/2, luego d((x1 , y1 ), (x2 , y2 )) = d2 ((x1 , y1 ), (0, 0)) + d2 ((0, 0), (x2 , y2 )) = 1/2 + 1/2 = 1. Concluyendo, f (n) = 1 ∀n ∈ N

(0, 0)

Figura 2.10. Configuraci´ on o´ptima con la m´etrica de correos.

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

2.3.2.

39

Espacios m´ etricos discretos

Consideremos ahora espacios m´etricos (X, d) discretos, es decir, espacios m´etricos donde el conjunto X contenga a lo sumo una cantidad numerable de puntos. Cualquier espacio m´etrico discreto puede interpretarse como un grafo ponderado donde el conjunto X coincide con el conjunto de nodos y de modo que el peso asignado a cada arco coincida con la distancia entre los dos nodos correspondientes. Cabe destacar, sin embargo, que no todo grafo ponderado con pesos positivos corresponder´a a un espacio m´etrico discreto, ya que habr´a que exigir que los pesos satisfagan la desigualdad triangular, para poder determinar una distancia. Trataremos con una familia especial de espacios m´etricos discretos. Consideraremos familias de grafos particulares y asignaremos a cada arco el peso 1. De este modo est´a bien definida la distancia entre dos nodos como el ´ınfimo de la suma de los pesos de los arcos que conectan los dos nodos. En estos grafos es especialmente interesante considerar una variante del problema: estudiaremos la cardinalidad de los conjuntos de k−distancias para los cuales las k distancias toman los valores {1, 2, . . . , k}. Consideraremos dos grafos particulares: el grafo con un conjunto infinito de nodos de modo que estos forman cuadrados iguales (los lados de los cuadrados se corresponden con los arcos del grafo), y el grafo con un n´ umero infinito de nodos formando tri´angulos equil´ateros iguales (de nuevo los arcos del grafo coinciden con los lados de los tri´angulos equil´ateros). Consideremos en primer lugar el grafo donde los arcos forman cuadrados. Para hallar la cardinalidad de los conjuntos de k-distancias hemos de distinguir casos seg´ un sea k par o impar. Se tiene el siguiente resultado: Teorema 14. En el grafo de la Figura 2.11 se tiene que: i) La cardinalidad m´ axima de un conjunto de (2k + 1)−distancias es 2(k + 1)2 ii) La cardinalidad m´ axima de un conjunto de 2k-distancias es 2k 2 + 2k + 1 Las cotas anteriores se alcanzan para las configuraciones representadas en la Figura 2.11.

40

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

Figura 2.11. Configuraciones o´ptimas para los conjuntos de k-distancias.

Demostraci´ on. Para demostrar el teorema, hemos de distinguir los casos par e impar. En primer lugar, hemos de considerar dos puntos a y b de modo que la distancia entre ellos sea m´axima, es decir d(a, b) = k (el conjunto de k−distancias tiene que contener dos puntos con estas caracter´ısticas por ser las k distancias distintas {1, . . . , k}). Consideremos la bola centrada en cada punto de radio k. Podemos ver en la Figura 2.12 la forma de estas bolas. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ................................................................................................................................................. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . . . . . . . . . . . . . . . ................................................................................................................................................. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . . . . . . . . . . . . . . . ................................................................................................................................................. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . . . . . . . . . . . . . . . ................................................................................................................................................. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ................................................................................................................................................. . . . . . . . . . . . . . . . . .. .. .. .. ..a .. .. .. .. .. .. .. .. ..a .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ................................................................................................................................................. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . . . . . . . . . . . . . . . . ................................................................................................................................................. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . . . . . . . . . . . . . . . ................................................................................................................................................. .. ... ... ... ... .. ... ... ... ... ... ... ... .. ... ... ... ................................................................................................................................................ ... . . . . .. . . . . . . . .. . . . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . . . . . . . . . . . . . . . . . k par k impar

Figura 2.12.

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

41

El resto de puntos se encontrar´an en la intersecci´on de las bolas centradas en a y b de radio k. Sin embargo, no todos los puntos de la intersecci´on de ambas bolas son v´alidos, puesto que podemos encontrar parejas de puntos a distancia mayor que k. Si eliminamos los nodos necesarios para no obtener distancias adicionales, obtenemos las cardinalidades deseadas. Para entender el procedimiento seguido, ilustraremos la prueba para un valor concreto de k. Consideraremos, por ejemplo, k impar, el caso par es an´alogo, pero no tienen porque salir los mismos casos. Si consideramos a un punto fijo cualquiera y b un punto a distancia k de a tenemos, en nuestro caso particular (Figura 2.13), que el punto b se puede encontrar en dos posiciones esencialmente distintas: .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . . .. . .. . .. . .. . .. . .. .. .. .. .. .. .. .. . .. . .. . .. . .. . .. . . . . . . ....... ................................................................................................................................................... . . . . . . . . . . . . . . . . . . .............................................................................................................................................................................................. . . . . .b . . . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ....... ................................................................................................................................................... . . .. . .. . .. . .. . .. . .. . b .. . .. .. .................................................................................................................................................................................... . .. .. .. .. ...a .. ... .. .. .. .. .. ..a .. .. .. ... ... ................................................................................................................................................... . . .. . .. . .. . .. . .. . .. . .. . .. .. ....... . . . . . . . . . . . . . . . . . . ......................................................................................................................................................................................... . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ................................................................................................................................................... . . .. . .. . .. . .. . .. . .. . .. . .. .. ....... . . . . . . . . . . . . . . . . . . . ........................................................................................................................................................................... .. .. . .. . .. . .. . .. . .. . .. . .. . . . . .. . .. . .. . .. . .. . .. . .. . .. .. ....... ................................................................................................................................................... .. .. . CASO . . . . . . . . . . .. 2 . .. . . .. .. .. ... .. 1... .. ... .. ... .. ... CASO .. .. .. .. .. .. Figura 2.13.

Si observamos el conjunto que queda en la intersecci´on de las dos bolas del CASO 1, observamos que es salvo una rotaci´on la configuraci´on que queremos hallar. Estudiemos el CASO 2. Si observamos el conjunto de puntos que tenemos, podemos comprobar a la izquierda de la figura 2.14 que si tomamos un punto de cada subconjunto marcado, la distancia entre ellos es mayor que k, luego uno de estos dos subconjuntos no puede formar parte del conjunto de k−distancias. Por simetr´ıa es indiferente que subconjunto eliminar.

42

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA ... ... ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ................................................................................................................................. .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ................................................................................................................................. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..............................................................b........................................................................b....................................................... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ................................................................................................................................. .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ............................................................................................................................................................................................. ... ... ... ...a ... ... ... ... ... a... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ................................................................................................................................. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ............................................................................................................................................................................................. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ................................................................................................................................. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . . . . . . . . . . . . . . ............................................................................................................................................................................................. .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..

Figura 2.14.

Nos hemos quedado con el dibujo de la derecha de la figura 2.14. Es sencillo comprobar que ocurre lo mismo con los dos nuevos subconjuntos se˜ nalados, si eliminamos cualquiera de ellos obtenemos de nuevo la configuraci´on deseada. Una vez obtenidas las configuraciones o´ptimas, es un c´alculo aritm´etico hallar sus cardinalidades como los t´erminos generales de sucesiones cuadr´aticas. Estudiemos ahora el grafo cuyos arcos forman tri´angulos equil´ateros. En este caso obtenemos resultados similares a los del caso anterior, de nuevo hemos de distinguir seg´ un sea k par o impar. Teorema 15. En el grafo de la Figura 2.15 se tiene que: i) La cardinalidad m´ axima de un conjunto de (2k + 1)−distancias es 3(k + 1)2 ii) La cardinalidad m´ axima de un conjunto de 2k-distancias es 3k 2 + 3k + 1 Las cotas anteriores se alcanzan para las configuraciones representadas en la Figura 2.15.

´ 2.3. EXTENSIONES A OTROS ESPACIOS METRICOS

43

Figura 2.15. Configuraciones o´ptimas para los conjuntos de k-distancias.

Demostraci´ on. La prueba es an´aloga a la del teorema anterior. La u ´nica variaci´on es que al tratarse de otro grafo, la forma de las bolas cambian, pero el procedimiento a seguir es el mismo.

44

CAP´ITULO 2. EXTENSIONES DEL PROBLEMA

Cap´ıtulo 3 Otros problemas relacionados 3.1.

Distancias repetidas

En los cap´ıtulos anteriores hemos tratado el problema de estimar la funci´on f (n): el m´ınimo n´ umero de distancias distintas determinadas entre n puntos en el plano y variaciones de este problema. Tratemos ahora un problema relacionado: tres puntos cualesquiera en el plano determinan tres distancias, posiblemente distintas, pero como ya hemos visto en el cap´ıtulo anterior, en el caso que situemos los tres puntos en los v´ertices de un tri´angulo equil´atero estas tres distancias coinciden. Por otro lado, cuatro puntos en el plano determinan seis distancias, y como ya se ha visto se tiene f (4) = 2, alcanz´andose este valor en tres configuraciones distintas. En una de estas tres configuraciones cada una de las distancias se da tres veces, en otra una de las distancias se da cuatro veces y la otra dos, y en la u ´ltima una distancia se da cinco veces, mientras que la otra s´olo se da una vez. Siempre podemos suponer, considerando la escala adecuada, que la distancia que se da un mayor n´ umero de veces es la distancia unidad. Definamos en general g(n) como el m´aximo n´ umero de veces que se puede dar la distancia 1 (o cualquier otra distancia, ya que podemos considerar la escala adecuada en cada caso) entre pares de puntos de un conjunto de n puntos en el plano. Por tanto, seg´ un el an´alisis anterior, se tendr´a g(3) = 3 y g(4) = 5. Se puede comprobar tambi´en que g(5) = 7, g(6) = 9 y g(7) = 12. Podemos comprobar que los valores anteriores se alcanzan para las configuraciones de la Figura 3.1. 45

CAP´ITULO 3. OTROS PROBLEMAS RELACIONADOS

46

n=3

n=4

n=5

n=6

n=7

Figura 3.1. Algunas configuraciones para las que se alcanza g(n).

El primer matem´atico en tratar este problema y hallar estimaciones asint´oticas para la funci´on g(n) fue, de nuevo, Paul Erd¨os ([14]). Erd¨os hall´o las siguientes cotas. Teorema 16. n1+1/ ln ln n  g(n)  n3/2 Adem´ as, la cota superior no se trata u ´nicamente de una cota asint´ otica, sino de una desigualdad v´ alida para cualquier valor de n, es decir, g(n) < n3/2 Demostraci´ on. Sea Pn la familia de todos los conjuntos de n puntos en el plano y sea umero de puntos del {P1 , . . . , Pn } un elemento arbitrario de esta familia. Sea xi el n´ conjunto a distancia uno de Pi . Como cada distancia se mide sobre un par de puntos, n  xi , y el n´ umero total de distancias unitarias en el conjunto {P1 , . . . , Pn } ser´a 12 i=1

por tanto

1 xi 2 i=1 n

g(n) = m´ax Pn

Podemos suponer sin p´erdida de generalidad que x1 ≥ x2 ≥ · · · ≥ xn . Los xi puntos a distancia 1 de Pi se encontrar´an en la circunferencia de radio 1 centrada en Pi . An´alogamente los xj puntos a distancia 1 de Pj estar´an sobre la circunferencia

3.1. DISTANCIAS REPETIDAS

47

unidad centrada en Pj . Como dos circunferencias con distinto centro son secantes a lo sumo en dos puntos, los xi puntos a distancia 1 de Pi contienen a lo sumo dos puntos que disten 1 de Pj . Las siguientes desigualdades son por tanto ciertas: x1 ≤ n Como de los x2 puntos a distancia 1 de P2 estar´an 2 a lo sumo a distancia 1 de P1 , x1 + (x2 − 2) ≤ n y an´alogamente x1 + (x2 − 2) + (x3 − 4) ≤ n x1 + (x2 − 2) + (x3 − 4) + (x4 − 6) ≤ n luego en general j 

(xi − 2i + 2) ≤ n ∀j = 1, 2, . . . , n

i=1

Sea a = [n1/2 ] y ε = n1/2 − a. Se tiene 0 ≤ ε < 1. De la desigualdad anterior se tiene: n≥

a 

(xi − 2i + 2) =

i=1

a  i=1

xi − 2

a  i=1

(i − 1) =

a 

xi − 2

i=1

a(a − 1) 2

y por tanto x1 + x2 + · · · + xa ≤ n + a(a − 1) Como a = n1/2 − ε, a(a − 1) = (n1/2 − ε)(n1/2 − ε − 1) = n − 2εn1/2 + ε2 − n1/2 + ε por lo que x1 + · · · + xa ≤ 2n − 2εn1/2 + ε2 + ε − n1/2 Adem´as, como 0 ≤ ε < 1, si n ≥ 4 se tiene ε2 + ε − n1/2 < 0, luego x1 + x2 + · · · + xa < 2n − 2εn1/2 De esta u ´ltima desigualdad y del hecho que x1 ≥ x2 ≥ · · · ≥ xa ≥ · · · ≥ xn se deduce: 1 2n1/2 1/2 (n − ε) = 2n1/2 xa < (2n − 2εn1/2 ) = a a

CAP´ITULO 3. OTROS PROBLEMAS RELACIONADOS

48 y

n  i=1

xi ≤

a 

xi + (n − a)xa < 2n − 2εn1/2 + (n − a)2n1/2 = 2n3/2

i=1

de donde se deduce finalmente que g(n) < n3/2 si n ≥ 4 Para n < 4, ya conocemos los valores correspondientes de g(n), con lo que podemos comprobar directamente que la desigualdad anterior es cierta. Falta por demostrar la cota inferior, para ello hemos de considerar el conjunto de puntos {(x, y) : 0 ≤ x, y ≤ a, x, y ∈ N}. Utilizando teoremas conocidos sobre el n´ umero de soluciones de la ecuaci´on u2 + v 2 = m ([20]) obtenemos el resultado deseado n1+1/ ln ln n  g(n) Erd¨os conjetur´o adem´as que g(n)  n1+ε para todo ε > 0 y aunque esta conjetura parece ser cierta, hasta el momento todav´ıa no se ha demostrado. Sin embargo, se han hecho varias mejoras con respecto a la cota original proporcionada por Erd¨os. As´ı, Beck y Spencer ([5]) demostraron que g(n)  n13/9 y Spencer, Szemer´edi y Trotter ([26]) mejoraron este resultado a g(n)  n4/3 . A´ un as´ı, todav´ıa hay un gran salto de este u ´ltimo resultado a la conjetura de Erd¨os. En el caso que los n puntos coincidan con los v´ertices de un pol´ıgono estrictamente convexo, Paul Erd¨os y Leo Moser conjeturaron que g(n)  n y demostraron que en este caso particular g(3m + 1) ≥ 5m para cualquier n´ umero natural m. M´as adelante, F¨ uredi ([17]) obtuvo g(n)  n ln n. Es interesante extender el problema a dimensiones superiores. Consideremos en primer lugar conjuntos de n puntos en el espacio R3 y sea entonces g(n) el m´aximo n´ umero de distancias unitarias que pueden darse entre n puntos de R3 . Las primeras estimaciones asint´oticas se deben de nuevo a Erd¨os que demostr´o: n4/3  g(n)  n5/3 Beck, Chung y Clarkson entre otros mejoraron las estimaciones anteriores. Hasta el momento se sabe que: n4/3 ln ln n  g(n)  n8/5

3.1. DISTANCIAS REPETIDAS

49

Sin embargo, en dimensi´on cuatro la situaci´on es muy distinta. H. Lenz di´o el siguiente razonamiento: si consideramos 1 P = {(ui , vi , 0, 0) : 1 ≤ i ≤  n} 2 y 1 Q = {(0, 0, uj , vj ) : 1 ≤ j ≤  n} 2 donde (ui , vi ) son distintas soluciones de la ecuaci´on u2 + v 2 = 1/2, entonces la distancia entre cualquier punto de P y otro de Q es siempre 1, puesto que  d((ui , vi , 0, 0), (0, 0, uj , vj )) = u2i + vi2 + (−uj )2 + (−vj )2 = 1/2 + 1/2 = 1. Por tanto como P = Q =  12 n * , el conjunto P ∪ Q est´a compuesto de al menos n puntos de R4 con m´as de 14 n2 distancias unitarias (ya que se dan al menos  12 n 12 n distancias unitarias y  12 n 12 n ≥ 12 n 12 n = 14 n2 ). Como n puntos distintos     cualesquiera determinan n2 distancias entre ellos y n2 = O(n2 ), el ejemplo anterior proporciona el orden correcto de magnitud en el caso 4−dimensional. Para espacios Rd con d > 4, un argumento similar al anterior proporciona el mismo resultado. La construcci´on anterior es muy sencilla y proporciona una estimaci´on asint´otica exacta para g(n) en Rd con d ≥ 4. Sin embargo, recientemente Braß ([9]) ha determinado con exactitud el m´aximo n´ umero de distancias unitarias entre n puntos en dimensi´on 4. El resultado de Braß es el siguiente: Teorema 17. El m´aximo n´ umero de veces que se puede dar la distancia uno entre 4 n ≥ 5 puntos en R es 1  n2  + n 4 si la ecuaci´on ν1 π ν2 π (sen n )−2 + (sen n )−2 = 4 2 2 tiene una soluci´on ν1 , ν2 ∈ N con ν1 , ν2 <  n2 , y 1  n2  + n − 1 4 en otro caso. Adem´ as, tal soluci´on de la ecuaci´ on existe por lo menos en el caso en que n sea m´ ultiplo de 8, en cuyo caso podemos tomar ν1 = ν2 = n8 *

Recordemos que dado un conjunto A, A denota su cardinal.

50

3.2.

CAP´ITULO 3. OTROS PROBLEMAS RELACIONADOS

Conjuntos de 2-distancias

En el cap´ıtulo anterior hemos hablado en general sobre conjuntos de k-distancias. Recordemos que un conjunto de k-distancias es un conjunto tal que se dan exactamente k distancias distintas entre sus puntos. Sin embargo, en el espacio eucl´ıdeo es de especial inter´es el caso k = 2, restringiendo por tanto el problema a conjuntos de 2−distancias. La pregunta que nos planteamos es: ¿Cu´antos puntos distintos podemos tener en Rd de modo que se den a lo sumo 2−distancias distintas entre ellos? La respuesta a la pregunta anterior depende de la dimensi´on d. As´ı, la respuesta es tres en R (considerando los extremos de un segmento y su punto medio), cinco en R2 (considerando los v´ertices de un pent´agono regular) y seis en R3 (los v´ertices de un octaedro regular, de un prisma regular o de una pir´amide que tenga como base un pent´agono regular y una altura adecuada). Para d ≥ 4 no se conoce una respuesta exacta. Sin embargo, si se conocen cotas superiores para la cardinalidad de los conjuntos de 2−distancias. El conjuntos de los 12 d(d + 1) puntos medios de los lados de un s´ımplice regular siempre forman un conjunto de 2−distancias. En el caso d = 3, los puntos medios de los lados de un tetraedro regular (un s´ımplice regular de dimensi´on tres) determinan los v´ertices de un octaedro regular, que como hemos dicho antes es un conjunto de 2−distancias. Delsarte, Goethals y Seidel ([12]) dieron ejemplos de conjuntos de 2-distancias con 12 d(d + 3) puntos para d = 2, 6 y 22. Sin embargo, la mejor cota superior general es debida a Blokhuis ([8]) quien ha probado que un conjunto de 2-distancias en Rd tiene a lo sumo 12 (d + 1)(d + 2) puntos. Otra restricci´on interesante del problema de hallar la cardinalidad de los conjuntos de k−distancias en Rd es considerar d = 3. As´ı, sea en general gd (n) el m´aximo n´ umero de puntos en Rd que determinan a lo sumo n distancias distintas. La pregunta es ¿Cu´anto vale g3 (n) para valores peque˜ nos de n. Y en particular, ¿es el conjunto formado por los v´ertices de un icosaedro regular el u ´nico conjunto de 3−distancias 3 en R con 12 puntos? Y, ¿es el conjunto de los v´ertices de un dodecaedro regular el u ´nico conjunto de 5−distancias con 20 puntos? En el caso general, Bannai, Bannai, Stanton y Blokhuis ([2], [3] y [7]) han de  mostrado que gd (n) ≤ d+n . Pero, ¿es gd (n) ∼ dn el orden correcto de magnitud n para valores grandes de n?

3.3. ¿PUEDE CADA DISTANCIA DARSE DISTINTAS VECES?

51

Podr´ıamos plantearnos el problema de hallar la cardinalidad de los conjuntos de 2−distancias para distintos espacios m´etricos. Como ya se ha visto en el cap´ıtulo anterior, Swanepoel ha resuelto parcialmente el problema para espacios de Minkowski. As´ı Swanepoel conjetura, considerando el caso k = 2, que la cardinalidad de un conjunto de 2−distancias en un espacio de Minkowski d−dimensional es al lo sumo 3d , con igualdad si y s´olo s´ı la bola unidad del espacio es un paralelep´ıpedo. Adem´as, se sabe que la conjetura es cierta para el caso 2−dimensional y cuando la bola unidad del espacio sea un paralelep´ıpedo. Un caso de especial inter´es, es el espacio de Minkowski (Rd , dT ) donde dT representa la conocida distancia del taxi definida como dT ((x1 , . . . , xn ), (y1 , . . . , yn )) = |x1 − y1 | + |x2 − y2 | + · · · + |xn − yn | En este caso la bola unidad es un paralelep´ıpedo regular, luego existen conjuntos de puntos para los que se alcanza la cota 3d . Dado d, una configuraci´on o´ptima es

Pd = conv±e1 , ±e2 , . . . , ±en  Zn

3.3.

¿Puede cada distancia darse un n´ umero distinto de veces?

Erd¨os ([15]) se pregunt´o si es posible tener n puntos en posici´on general en el plano (es decir, de modo que no se encuentren tres en una l´ınea ni cuatro en un c´ırculo) tales que para cada i (1 ≤ i ≤ n − 1) exista una distancia determinada por estos n puntos que se de exactamente i veces. En primer lugar, tiene sentido plantearse la cuesti´on anterior por la siguiente   raz´on. Entre n puntos se dan exactamente n2 distancias (no necesariamente distintas todas entre s´ı). Si exigimos las condiciones anteriores, tendremos una distancia que se de una vez, otra que se dos veces, . . . , hasta una distancia que se de exactamente n − 1 veces. Es decir, en total tendremos 1 + 2 + · · · + (n − 1) distancias entre los n puntos, la suma anterior se puede realizar como la suma de los n − 1 primeros t´erminos de una progr´esion aritm´etica obteniendo:   n(n − 1) n 1 + 2 + · · · + (n − 1) = = 2 2 luego los n´ umeros coinciden.

52

CAP´ITULO 3. OTROS PROBLEMAS RELACIONADOS

S´olo se conocen respuestas parciales a esta pregunta. Es decir, para valores de n peque˜ nos se conocen ejemplos para los cuales se verifica la condici´on. Sin embargo, es muy probable que no existan configuraciones de puntos con esta propiedad para valores de n superiores a un cierto n0 , pero se trata de un problema abierto. As´ı se han descubierto ejemplos u ´nicamente para valores de n de modo que 2 ≤ n ≤ 8. Para observar esto consideremos las siguientes configuraciones de puntos: Para n = 3 consideremos los puntos (0, 1), (0, 0) y (1, 0). Tenemos que la dis√ tancia 2 se da una vez, mientras que la distancia 1 ocurre dos veces. En realidad, podr´ıamos haber considerado cualquier tri´angulo is´osceles (Figura 3.2). Para n = 4 consideremos el conjunto formado por los puntos (−1, 0), (0, 0), (1, 0) √ √ y (0, 3). En este caso tenemos las distancias 3, 1 y 2 que se dan una, dos y tres veces respectivamente (Figura 3.2).

(0, 1) ..... .... .... .... ..(1, (1, 0) (0, 0) ... 0) (−1, 0)............................. (0, 0) n=3 n=4

Figura 3.2.

√ √ Para n = 5 consideremos los puntos del plano (0, 0), (6, 0), (3, 3 3), (3, 3) y √ √ √ √ √ (−2 6, 2 3), entonces las distancias 2 18 + 6 6, 2 9 + 3 6, 2 3 y 6 ocurren una, dos, tres y cuatro veces respectivamente (Figura 3.3). . ........ . . .. .... .......... ............ ... ... . . .... ....... .. ... ......... .... .... ... ........ ..... ... .... ... ........................................... n=5

Figura 3.3.

3.3. ¿PUEDE CADA DISTANCIA DARSE DISTINTAS VECES?

53

√ √ √ √ Para n = 6 consideremos los puntos (0, 0), (6, 0), (3, 3 3), (3, 3), (−2 6, 2 √3) √ √ √ √ y (3 − 6, − 3 − 3 2). En este caso, las distancias 2 15 + 6 6, 2 18 + 6 6, √ √ 2 3, 2 9 + 3 6 y 6 ocurren una, dos, tres, cuatro y cinco veces respectivamente (Figura 3.4). . ........... . . . .. . .......... ... .... ..... .... ....... . . ... .... ........ ... ... ......... .. . .... .... ... ............... ..... .... .. .. .............. .. ............. ..................... .. ... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... .... .. . n=6

Figura 3.4.

√ √ √ Para n = 7 hemos de considerar los puntos (0, 0), (2, 0), (2 + 6, 2), ( 6 + √ √ √ √ √ √ √ 1, 2 + 3), (1, 3 + 2 2), (0, 2 2) y (1, 2 2 − 3). En este ejemplo las distancias √ √ √ √ √ 2 5 − 6, 2 3 − 6, 2 2, 2, 2 3 y 2 3 + 6 se dan una, dos, tres, cuatro, cinco y seis veces respectivamente (Figura 3.5). ...... ......... ...... .. ... .... ..... .... ...... .... .. . ... .. .... .... ........... .... ...... . . ..... ................. ...... ....... ... ............ .... .. ........ ... ....... ..... ......... . . . . ... . . . . . . ..... . .... ............... .... ............. .. ...... ... ......... ................................. .. .... n=7

Figura 3.5.

54

CAP´ITULO 3. OTROS PROBLEMAS RELACIONADOS

√ √ √ Por u ´ltimo, si n = 8 consideremos los puntos (0, 2), (2 3, 0), (4 3, 0), (5 3, 5), √ √ √ √ √ √ √ (3 3, 9), ( 3, 7), (3 3, 7) y (2 3, 4). Entonces las distancias 2, 2 19, 2 21, 2 3, √ √ 4, 2 7 y 2 13 se dan una, dos, tres, cuatro, cinco, seis y siete veces respectivamente (Figura 3.6). ... ...... ...... . . . . . ... ..... ... ...... . . . . . . . . ...... . .. .. . . . . . . .. . ...... .. ............ .. ...... .. ...... .. ...... .. .. ...... .. .. ... .. ....... .. . . . . . . .. . . . ..... . .......... . . . . . . . . . . . . . . . .. .... . . ...... .. ...... ..................... . . . . . .. .......... .. . .. . . . . . ............. . . .. . . . . . . . .. ... .. . .. .............. .. .. .. ...... . .. ...... .. . . ...... .. ...... ...... .. ...... ... ...... .. n=8 Figura 3.6.

De los ejemplos anteriores, el ejemplo correspondiente a n = 5 se debe a Carl Pomerance ([15]), el correspondiente a n = 6 fue descubierto por un grupo de alumnos h´ ungaros, y Pal`asti ([24] y [25]) descubri´o los ejemplos correspondientes a n = 7 y n = 8. Como hemos dicho al principio, no se conoce nada m´as sobre este tema, pero las cuestiones m´as inmediatas son: ¿Puede construirse una configuraci´on para n = 9, o dicha configuraci´on no existe?, ¿Es posible resolver el mismo problema en R3 para n arbitrariamente grande?, o generalizando m´as a´ un, ¿Existe alg´ un d con d ≥ 2 de d modo que se pueda resolver el problema para cualquier n en R ?

Ap´ endice A Estimaciones asint´ oticas En matem´aticas e inform´atica se estudia a menudo el comportamiento de las funciones definidas sobre los n´ umeros naturales cuando n tiende a infinito, ignorando su comportamiento para valores de n peque˜ nos. Pongamos un ejemplo, consideremos las funciones f (n) = 5n y g(n) = n2 . En este caso ninguna de las desigualdades f (n) ≤ g(n) y g(n) ≤ f (n) son ciertas para todo n, ya que para n = 1, f (1) = 5 > g(1) = 1 mientras que para n = 6 f (6) = 30 < g(6) = 36. Sin embargo, a partir de un cierto valor n0 , g es siempre mayor que f . Diremos en este caso que g crece mucho m´as r´apido que f . Ante situaciones como las descritas en el ejemplo anterior, hablaremos de an´alisis asint´otico de las funciones consideradas. Hablamos tambi´en de comportamiento asint´otico de una funci´on cuando la comparamos con algunas funciones sencillas cuando n tiende a infinito. Para formalizar todo lo anterior precisamos de la siguiente notaci´on. Si f y g son funciones de una u ´nica variable n, diremos que f  g cuando exista un n´ umero n0 a partir del cual la desigualdad f (n) ≤ g(n) sea cierta para todo n ≥ n0 . Volviendo al primer ejemplo, podemos decir que 5n  n2 . La relaci´on  puede verse como una desigualdad “suave” entre las funciones consideradas. As´ı, si f  g es seguro que g superar´a a f para valores suficientemente grandes de n pero, ¿c´omo de grande tiene que ser n? La notaci´on  suprime por tanto cierta informaci´on. Por ello dadas dos funciones f y g suele ser m´as sencillo establecer la  desigualdad que probar la desigualdad fuerte ≤ (que debe verificarse para todo n). 55

56

´ ´ APENDICE A. ESTIMACIONES ASINTOTICAS

Sin embargo, esto puede llevar al enga˜ no. Supongamos que alguien vende una “caja negra” de modo que, para cada n´ umero introducido n, proporciona el correspondiente valor f (n). Adem´as, nos garantizan que f (n)  n. Nunca podremos probar la veracidad de esta garant´ıa. No importa con cu´antos n´ umeros n obtengamos f (n) > n, ya que el vendedor siempre puede afirmar que el n´ umero n0 es superior a cualquiera de los ejemplos introducidos. En la literatura encontramos otras notaciones referidas a estimaciones asint´oticas que todav´ıa suprimen m´as informaci´on, y por tanto proporcionan relaciones m´as sencillas de comprobar. La siguiente notaci´on es posiblemente la m´as com´ un, especialmente en el an´alisis de algoritmos. Definici´ on 1. Sean f , g dos funciones reales de una u ´nica variable definidas sobre el conjunto de los n´ umeros naturales. La notaci´on f (n) = O(g(n)) significa que existe una constante C tal que ∀n ∈ N |f (n)| ≤ C · g(n). f (n) = O(g(n)) se lee, f es del orden de g. Hay que fijarse que la informaci´on suprimida con esta notaci´on es el valor de C, ya que esta constante depende de las funciones f y g. As´ı podemos tener C = 0,1, C = 1 o´ C = 1010 , lo u ´nico que exige la definici´on es su existencia. Intuitivamente podemos entender f (n) = O(g(n)) como que f no crece m´as r´apido que g, es decir, (n) que fg(n) no tiende a infinito. Por ejemplo, 10n2 + 5n = O(n2 ) Podemos decir que si f es del orden de g, entonces f (n) no es demasiado grande desde el punto de vista que est´a “dominada” por g(n), pero no podemos decir nada acerca de como de peque˜ na sea f (n) en comparaci´on con g(n). As´ı, es verdad 5 ´til, que que n + 5 = O(n ) pero tambi´en es verdad, y posiblemente mucho m´as u n + 5 = O(n). Son ciertas las siguientes reglas: si f1 (n) = O(g1 (n)) y f2 (n) = O(g2 (n)) entonces f1 (n) + f2 (n) = O(g1 (n) + g2 (n))

y

f1 (n)f2 (n) = O(g1 (n)g2 (n)).

Estas sencillas reglas junto con el siguiente resultado son muy u ´tiles para simplificar determinadas expresiones.

57 Proposici´ on 1. Sean C, a, α, β > 0 n´ umeros reales fijos independientes de n. Entonces: i) nα = O(nβ ) si α ≤ β. ii) nC = O(an ) para cualquier a > 1. iii) (ln n)C = O(nα ) para cualquier α > 0 Veamos con un ejemplo como usar estas herramientas. Queremos estimar asint´oticamente (7n2 + 6n + 2)(n3 − 3n + 28 ). Por i) de la proposici´on anterior y la regla de la suma, 7n2 + 6n + 2 = O(n2 + n2 + n2 ) = O(3n2 ) = O(n2 ) y an´alogamente n3 −3n+28 = O(n3 ). Entonces, por la regla del producto (7n2 +6n+2)(n3 −3n+28 ) = O(n2 n3 ) = O(n5 ). Con la notaci´on O(·) tambi´en podemos expresar los errores que cometemos al √ aproximar funciones mediante otras m´as sencillas. Por ejemplo, f (n) = g(n)+O( n) √ significa que al aproximar f por g cometemos un error de orden n, es decir, que   √ = 12 n2 + O(n). f (n) − g(n) = O( n). Un ejemplo sencillo concreto es n2 = n(n−1) 2 La definici´on 1 se puede extender para funciones de varias variables. Diremos entonces que f (n1 , . . . , nk ) = O(g(n1 , . . . , nk )) si existe una constante C de modo que ∀n1 , . . . , nk tenemos que |f (n1 , . . . , nk )| ≤ C · g(n1 , . . . , nk ). Podemos relajar la definici´on 1 como sigue. En las estimaciones asint´oticas nos interesa el valor de la funci´on para valores grandes de n, por lo que no nos importa lo que ocurra para valores peque˜ nos de n. Consideremos entonces la siguiente definici´on alternativa: Definici´ on 2. Decimos que f (n) = O(g(n)) si existen n´ umeros C0 y n0 ∈ N tales que ∀n ≥ n0 |f (n)| ≤ C0 · g(n). En esta u ´ltima definici´on incluimos aquellas funciones no definidas para un n´ umero finito de puntos. Es inmediato comprobar que en caso de que las funciones f y g esten bien definidas para todo n natural, ambas definiciones son equivalentes. Hay otros s´ımbolos que relacionan los ordenes de magnitud de funciones, es decir, comparan funciones para valores elevados de n. Esto es precisamente lo que hace O(·), pero hay veces que se requiere m´as precisi´on, o interesan otras relaciones. Consideremos entonces la siguiente notaci´on:

´ ´ APENDICE A. ESTIMACIONES ASINTOTICAS

58 Definici´ on 3. Decimos que

f (n) = o(g(n)) f (n) n→∞ g(n)

si l´ım

= 0, es decir, si f crece mucho m´ as lento que g.

Decimos que f (n) = Ω(g(n)) si g(n) = O(f (n)), es decir, si f crece al menos tan r´ apido como g. Decimos que f (n) = Θ(g(n)) si f (n) = O(g(n)) y f (n) = Ω(g(n)), es decir, si f y g tienen el mismo orden de magnitud. Finalmente, decimos que f (n) ∼ g(n) f (n) n→∞ g(n)

si l´ım

= 1 l´ımn→∞

f (n) g(n)

= 1, es decir, si f (n) y g(n) son “casi” la misma.

De las distintas relaciones introducidas en la definici´on anterior, las relaciones o(·), Θ(·) y ∼ son refinamientos de la relaci´on O(·) en el sentido que: f (n) = o(g(n)) ⇒ f (n) = O(g(n)) f (n) = Θ(g(n)) ⇒ f (n) = O(g(n)) f (n) ∼ g(n) ⇒ f (n) = O(g(n)) Por el contrario, la relaci´on Ω(·) se puede considerar opuesta a la relaci´on O(·) en el sentido que: f (n) = Ω(g(n)) ⇔ g(n) = O(f (n)) Veamos unos sencillos contraejemplos para las implicaciones anteriores: 3n = O(n) pero 3n = o(n) y tampoco satisfacen la relaci´on ∼. Sin embargo, 3n = Θ(n). n = O(n2 ) pero n = Θ(n2 ). Es muy sencillo demostrar la siguiente equivalencia: f (n) = O(g(n)) ⇔ (f (n) = o(g(n)) o bien f (n) = Θ(g(n)))

59 Finalmente, tambi´en podr´ıamos preguntarnos para qu´e es buena una cota f (n) = O(g(n)). Como no sabemos nada acerca de la constante C, no podemos deducir una estimaci´on de f (n) para ning´ un valor espec´ıfico de n. Sin embargo, en determinados contextos no son importantes los valores particulares que pueda tomar n, basta saber que cierta funci´on no crece mucho m´as r´apido que otra determinada funci´on. Esto es u ´til, por ejemplo, para probar la existencia de un determinado objeto sin construirlo. De todos modos, en la mayor´ıa de los casos es posible hallar la constante C. Para ello, basta prestar atenci´on a los c´alculos realizados para hallar la estimaci´on asint´otica y tener en cuenta todas las constantes usadas en cada paso. Esto puede resultar tedioso, pero posible. Suele ocurrir en general que si hallamos una O(·) de un modo sencillo, la constante C no suele ser muy grande, sin embargo esto es muy poco fiable. Para m´as informaci´on sobre estimaciones asint´oticas v´ease ([22]).

60

´ ´ APENDICE A. ESTIMACIONES ASINTOTICAS

Ap´ endice B Ejemplos de distancias Cuando hablamos de la distancia entre dos puntos x e y sin realizar m´as comentarios, pensamos involuntariamente en la longitud del segmento con extremos x, y. Si estamos en Rn entonces x = (x1 , . . . , xn ), y = (y1 , . . . , yn ) y esta longitud tiene como expresi´on anal´ıtica d(x, y) =

(x1 − y1 )2 + · · · + (xn − yn )2 .

Sin embargo la definici´on de distancia es mucho m´as amplia y existen muchas funciones que verifican las propiedades de distancia. Definici´ on 4. Una distancia en un conjunto X es una funci´ on d:X ×X →R satisfaciendo las siguientes propiedades: i) d(x, y) ≥ 0 para todos x, y ∈ X; la igualdad se da si, y s´ olo si, x = y. ii) d(x, y) = d(y, x) para todos x, y ∈ X. iii) (Desigualdad triangular) d(x, y) + d(y, z) ≥ d(x, z) para todos x, y, z ∈ X. Dada una distancia d en X, el n´ umero d(x, y) se llama a menudo distancia entre x e y en la distancia d. Uno de los conceptos m´as importantes asociados a las distancias, es el concepto de bola: 61

62

´ APENDICE B. EJEMPLOS DE DISTANCIAS

Definici´ on 5. Definida una distancia d en X, x ∈ X y ε > 0 se tiene: La bola abierta de radio ε centrada en x es el conjunto Bd (x, ε) = {y ∈ X|d(x, y) < ε} de todos los puntos y cuya distancia a x es menor que ε. La bola cerrada de radio ε centrada en x es el conjunto B d (x, ε) = {y ∈ X|d(x, y) ≤ ε} de todos los puntos y cuya distancia a x es menor o igual que ε. La esfera de radio ε centrada en x es el conjunto Sd (x, ε) = {y ∈ X|d(x, y) = ε} de todos los puntos y cuya distancia a x es igual a ε. Algunas veces omitiremos la distancia d de la notaci´on y escribiremos simplemente B(x, ε), B(x, ε), S(x, ε), cuando no exista problema de confusi´on. Por otro lado, cuando trabajemos en el plano, usaremos a menudo el t´ermino circunferencia en lugar de esfera, aunque nos refiramos al mismo objeto. Veamos ya algunos ejemplos de distancias as´ı como la forma de sus respectivas bolas y esferas. S´olo calcularemos en cada caso las bolas abiertas, puesto que el resto se calculan de modo an´alogo. En todos los ejemplos que siguen, es f´acil comprobar que las distancias definidas verifican la definici´on 1. Ejemplo 1. Dado un conjunto X definimos  1 si x = y d(x, y) = 0 si x = y Dado x ∈ X, para calcular las bolas abiertas hemos de distinguir casos seg´ un el radio: Si ε ≤ 1 entonces B(x, ε) = {y|d(x, y) < ε} = {y|d(x, y) = 0} = {x} Si ε > 1 entonces B(x, ε) = {y|d(x, y) < ε} = {y|d(x, y) ≤ 1} = X

63 Si realizamos los c´ alculos correspondientes deduciremos que: ⎧ ⎨ {x} si ε < 1 B(x, ε) = ⎩ X si ε ≥ 1 ⎧ ⎪ ⎪ ⎪ ⎨ S(x, ε) =

⎪ ⎪ ⎪ ⎩

{x}

si

ε=0

X\{x} si

ε=1

∅

en otro caso

Omitiremos de aqu´ı en adelante las expresiones de las bolas cerradas y las esferas. Ejemplo 2. La distancia usual sobre los n´ umeros reales R est´ a definida por la ecuaci´ on d(x, y) = |x − y| En este caso, dado x ∈ X y ε > 0 B(x, ε) = {y||x − y| < ε} = {y| − ε < y − x < ε} = {y|x − ε < y < x + ε} =]x − ε, x + ε[, es decir el intervalo abierto de extremos x − ε, x + ε. El ejemplo anterior se puede generalizar a Rn obteniendo la distancia indicada en el ejemplo inicial. Ejemplo 3. La distancia eucl´ıdea sobre puntos de Rn se define como d(x, y) = (x1 − y1 )2 + · · · + (xn − yn )2 donde x = (x1 , . . . , xn ), y = (y1 , . . . , yn ). En este caso dado ε > 0 se tiene B(x, ε) = {y| (x1 − y1 )2 + · · · + (xn − yn )2 < ε} = {y|(x1 − y1 )2 + · · · + (xn − yn )2 < ε2 }, es decir un disco abierto de radio ε. Veamos a continuaci´on otras distancias no tan conocidas pero tambi´en interesantes. Para simplificar nos restringiremos a R2 , pero todas las distancias se pueden generalizar sin ning´ un problema.

64

´ APENDICE B. EJEMPLOS DE DISTANCIAS

Ejemplo 4. Dados x = (x1 , x2 ), y = (y1 , y2 ), se define la distancia del taxi o de Manhattan entre x e y como d(x, y) = |x1 − y1 | + |x2 − y2 | Las bolas abiertas en este caso tienen la expresi´ on B(x, ε) = {y||x1 − y1 | + |x2 − y2 | < ε} es decir, las bolas son cuadrados centrados en x cuyas diagonales de longitud 2ε son paralelas a los ejes de coordenadas, tal como indica la figura B.1.

x r -

Dist. eucl´ıdea

x r -

Dist. taxi

Figura B.1.

Ejemplo 5. Dados x = (x1 , x2 ), y = (y1 , y2 ), se define la distancia de correos entre x e y como  0 si x = y d(x, y) = d2 (p, (0, 0)) + d2 ((0, 0), q) si x = y donde d2 representa cualquier otra distancia. Usualmente, consideraremos d2 como la distancia eucl´ıdea. El nombre “distancia de correos” viene motivado por la siguiente situaci´ on. Supongamos que en una ciudad hay una u ´nica oficina de correos, entonces si queremos enviar una carta de un punto a hasta otro punto b, la carta tendr´ a que pasar previamente por la oficina de correos (representada por el origen). Por tanto, la distancia entre a y b se obtiene como la suma de la distancia entre a y el origen y la distancia entre el origen y b. Podemos comprobar de un modo an´ alogo a los ejemplos anteriores que en este caso ⎧ ⎨ {x} si ε ≤ d2 ((0, 0), x) B(x, ε) = ⎩ B ((0, 0), r)) ∪ {x} si ε > d ((0, 0), x) d2 2

65 donde r = ε − d2 ((0, 0), x)y Bd2 (x, r) representa la bola abierta con respecto a la distancia eucl´ıdea.

x

x

0

0

r < d(x, 0)

r > d(x, 0)

Figura B.2.

Ejemplo 6. Sea H := {(x, y) ∈ R2 : x ≥ 0} ⊂ R2 el semiplano superior. Sobre H se puede definir una distancia muy interesante como sigue: Dados dos puntos de H (x1 , x2 ) y (y1 , y2 ) se define la distancia del ascensor de la siguiente manera:  |x2 − y2 | si x1 = y1 d((x1 , x2 ), (y1 , y2 )) = |x2 | + |x1 − y1 | + |y2 | si x1 = y1

⎫ ⎪ ⎬

x  ε

}

⎪ ⎭

ε

x

ε < |x2 |

ε ≥ |x2 | Figura B.3.

En este caso, para hallar la expresi´ on de las bolas abiertas, tambi´en hemos de distinguir seg´ un el valor del radio, y as´ı, si x = (x1 , x2 ) se tiene:

´ APENDICE B. EJEMPLOS DE DISTANCIAS

66

 B(x, ε) =

](x1 , x2 + ε), (x1 , x2 − ε)[ si ε < |x2 | (](x1 , x2 + ε), (x1 , x2 − ε)[ ∪ BdT ((x1 , 0), r))) ∩ H si ε ≥ |x2 |

donde r = ε − |x2 | y BdT (x, r) representa la bola abierta con respecto a la distancia del taxi. En la figura B.4, podemos observar como act´ uan las anteriores distancias sobre dos puntos x, y ∈ H: x

x y

0 Dist. eucl´ıdea

y

0 Dist. taxi

x

x y

0 Dist. correos

y

0 Dist. ascensor

Figura B.4. Distancias distintas en R2 .

Un modo interesante de definir distancias en el plano es el siguiente ([19]). Se define la funci´on gauge g(K, x) de un conjunto K convexo y cerrado relativa a un origen 0 como g(K, x) = inf {λ : x ∈ λK, λ > 0} Es sencillo probar que si K es un cuerpo convexo propio y si 0 ∈ intK, entonces la funci´on m(x, y) = g(K, x − y) casi define una distancia en el plano. As´ı, la funci´on m satisface las propiedades i) y iii) de la definici´on de distancia violando u ´nicamente la condici´on de simetr´ıa

67 m(x, y) = m(y, x) que se verifica u ´nicamente en el caso en que K sea centralmente sim´etrico. Por tanto un conjunto K cerrado, convexo y centralmente sim´etrico con 0 ∈ intK define una m´etrica. Por ejemplo, la distancia del taxi definida en el ejemplo 4 se puede definir del modo explicado a partir de un cuadrado K, que verifica todas las condiciones anteriores. De igual modo, la distancia eucl´ıdea en el plano se puede definir a partir de un c´ırculo del mismo modo. Todas las distancias construidas de este modo generan la topolog´ıa eucl´ıdea y todos los espacios m´etricos resultantes son espacios de Minkowski, es decir, espacios de Banach de dimensi´on finita.

68

´ APENDICE B. EJEMPLOS DE DISTANCIAS

Ap´ endice C Ret´ıculos Definici´ on 6. Dados n puntos linealmente independientes b1 , ..., bn en el espacio Eucl´ıdeo n−dimensional Rn , se define el ret´ıculo L generado por ellos como L(b1 , ..., bn ) = {a1 b1 + ... + an bn : a1 , ...an ∈ Z} El conjunto {b1 , ..., bn } es una base de L. As´ı, un ret´ıculo est´a formado por todos los puntos que se puedan expresar como una combinaci´on lineal de los elementos de una base con coeficientes enteros. Desde luego, un mismo ret´ıculo puede estar generado de diferentes formas, es decir, un ret´ıculo L puede tener distintas bases. Veamos a continuaci´on algunos ejemplos de ret´ıculos especialmente relevantes: Ejemplo 7. El ret´ıculo entero Zn es el formado por todos los puntos de Rn con coordenadas enteras, es decir el ret´ıculo generado por el conjunto {b1 , ..., bn } con bi = ei = (0, ..., 1(i) , ..., 0). Ejemplo 8. Una generalizaci´ on del ret´ıculo entero es el llamado ret´ıculo rectangular. El ret´ıculo rectangular es el generado por el conjunto {b1 , ..., bn } con bi = (0, ..., ki , ..., 0) donde ki ∈ Z. Un caso particular de ret´ıculo rectangular de especial inter´es es aquel donde k1 = ... = kn = k. En este caso, el ret´ıculo se puede obtener como una dilataci´ on o contracci´ on del ret´ıculo entero.

69

´ APENDICE C. RET´ICULOS

70

6

b2 = (0, b)

b2 = (0, 1)

6 -

b1 = (a, 0)

-

b1 = (1, 0)

Ret´ıculo rectangular

Ret´ıculo entero

Figura C.1.

Ejemplo 9. El ret´ıculo hexagonal (en el plano) es el que tiene como base los vectores √ {(1, 0), (1/2, 3/2)}. El ret´ıculo hexagonal est´ a formado por tanto por los v´ertices de un conjunto de tri´ angulos equil´ ateros que teselan el plano.

√ b2 = (1/2, 3/2)

 -

b1 = (1, 0)

Ret´ıculo hexagonal

Figura C.2.

Ejemplo 10. Consideremos por u ´ltimo el ret´ıculo en el plano generado por los √ √ √ √ puntos {( 2/2, 2/2)), (− 2/2, 2/2)}.

71 Aunque este ret´ıculo se puede obtener mediante una rotaci´ on de 90o grados del ret´ıculo entero, tiene inter´es por s´ı mismo.

√ √ b2 = (− 2/2, 2/2)I



Figura C.3.

√ √ b1 = ( 2/2, 2/2)

72

´ APENDICE C. RET´ICULOS

Bibliograf´ıa [1] Albujer, A. y Segura Gomis, S.: Minimum number of different distances defined by a finite number of points, Contribution at the 20th European Workshop on Computational Geometry, Seville, March 2004. [2] Bannai, E. y Bannai, E.: An upper bound for the cardinality of an s−distance subset in real Euclidean space, Combinatorica 1 (1981), 99–102. [3] Bannai, E. , Bannai, E. y Stanton D.: An upper bound for the cardinality of an s−distance subset in real Euclidean space II, Combinatorica 3 (1983), 147–152. [4] Beck J.: Different distances, preprint. [5] Beck, J. y Spencer, J.: Unit distances, J. Combin. Theory Ser. A 37 (1984), 231–238. [6] Berg, M. de, Kreveld, M. van, Overmars, M. y Schwarzkopf, O.: Computational Geometry, Algorithms and Applications, Second Edition, Springer-Verlag Berlin Heidelberg 1997,2000. [7] Blokhuis, A.: An upper bound for the cardinality of s−distance sets in E d y H d , Eindhoven Univ. Tech. Mem. 68 (1982). [8] Blokhuis, A.: A new upper bound for the cardinality of 2−distance sets in Euclidean space, in Rosenfeld, M. y Zacks, J. (eds.): Proccedings of Jerusalem Conference, 10981, Ann. Discrete Math. 20, North-Holland, Amsterdam, 1984. [9] Braß, P.: On the maximum number of unit distances among n points in dimension four, Intuitive geometry (Budapest, 1995), 277–290, Bolyai Soc. Math. Stud., 6, J´anos Bolyai Math. Soc., Budapest, 1997. [10] Chung, F. R. K.: The number of different distances determined by n points in the plane, J. Combin. Theory Ser. A 36 (1984) 342–354 73

74

BIBLIOGRAF´IA

[11] Chung, F. R. K., Szemerdi, E. y Trotter, W. T.: The number of different distances determined by a set of points in the Euclidean plane, Discrete Comp. Geometry 7 (1992), 1–11. [12] Delsarte, P. , Goethals, J.M. y Seidel, J.J.: Spherical codes and designs, Geom. Dedicata 6 (1977), 363–388. [13] Edelsbrunner, H.: Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin, 1987. [14] Erd¨os, P.: On sets of distances of n points, Amer. Math. Monthly 53 (1946), 248–250. [15] Erd¨os, P.: Distances with specified multiplicities, Amer. Math. Monthly 96 (1989), 447. [16] Erd¨os, P. , Hickerson, D. y Pach J.: A problem of Leo Moser about repeated distances on the sphere, Amer. Math. Monthly 96 (1989), 569–575. [17] F¨ uredi, Z.: The maximum number of unit distances in a convex n−gon, J. Combin. Theory Ser. A 55 (1990) 316–320 [18] Groemer H.: Absch¨atzungen f¨ ur die Anzahl der konvexen K¨orper, die einen konvexen K¨orper ber¨ uhren, Monatsh. Math. 65 (1961), 74–81. [19] Guggenheimer, H. W.: Applicable geometry, Robert E. Krieger Publishing Co., Inc. , Huntington, New York, 1977. [20] Jahresbericht der Deutschen Math. Vereinigung, vol. 43, (1934), p. 114. [21] Landau, Verteilung der Primzahlen, vol. 2. [22] Matouˇsek, J. y Neˇsetˇril, J.: Invitation to Discrete Mathematics, 2002, SpringerVerlag, J´anos Bolyai Mathematical Society, Budapest. [23] Moser, L.: On different distances determined by n points, Amer. Math. Monthly 59 (1952), 85–91. [24] Pal´asti, I.: On the seven points problem of P. Erd¨os, Studia Sci. Math. Hungar. 22 (1987), 447–448.

BIBLIOGRAF´IA

75

[25] Pal´asti, I.: Lattice point examples for a question of Erd¨os, Period. Math. Hungar. 20 (1989), 231–235. [26] Spencer, J., Szemer´edi, E. y Trotter, W.: Unit distances in the Euclidean plane, Graph Theory and Combinatorics, Academic Press, London (1984), 293–303. [27] Sz´ekely, L. A.: Erd¨os on unit distances and the Szemer´edi-Trotter theorems, Paul Erd¨os and his Mathematics. II, Budapest, 2002, 649–666. [28] Swanepoel, K.J.: Cardinalities of k−distances sets in Minkowski spaces, Discrete Math. 197/198 (1999), 759–767.