Sobre el diámetro de los grupos de permutaciones.

Seguramente ya habrás oído hablar a estas alturas de los dos grandes (parece que cada vez más confirmados) avances en teoría de números, relacionados uno con dos conjeturas de dilatada solera, la conjetura de los números primos gemelos y la versión débil de la conjetura de Goldbach. En esta entrada, tras unos breves preliminares históricos sobre el segundo avance, vamos a hablar de otros resultados del autor del segundo avance.

I.

Primero , cómo curiosidad histórica señalemos que, con respecto a la segunda conjetura, en realidad Goldbach sólo expresó la versión débil, siendo Euler el que expresara la versión fuerte. Ambos eran matemáticos, amigos y residentes en Rusia, y mantuvieron un frecuente contacto epistolar  en el que intercambiaban problemas:

Otro de los vínculos que no se alteró por su salida de Rusia fue su amistad con Goldbach y la correspondencia entre ellos siguió fluyendo de manera continua. Una muestra del fruto de este ejercicio son dos importantes cartas para la historia de las matemáticas. En la del 7 de junio de 1742 Goldbach le escribe lo siguiente (a Euler):

[…]; de este modo quiero aventurar una conjetura: que todo número que está compuesto [como suma] de dos números primos es a la vez un agregado de tantos números primos como queramos (incluyendo la unidad), hasta alcanzar puras unidades. [que es lo más a lo que se puede extender].

Y luego, en el margen de la misma carta, aparece lo siguiente:

Después de leer esto otra vez, considero que pudiera ser demostrada con todo rigor para el caso n + 1, si sucede para el caso n, y si n+1 puede ser dividido en dos primos. [Entonces] la demostración es muy fácil. Parece por lo menos que todo número mayor que dos es la suma de tres números primos.” En estos dos párrafos que Goldbach le envía se puede ver, en el primero, una propuesta de representar a los números que son suma de dos primos como suma de tantos primos como se quiera, en tanto que el segundo párrafo es una especie de enmienda en la que ya sólo conjetura que todo número es una suma de tres primos.

Como se puede ver, en ningún lado aparece algo equivalente a lo que conocemos como la conjetura de Goldbach. El 30 de junio de 1742 Euler le responde lo siguiente (a Goldbach): 

que todo número que es resoluble como [suma] de dos primos, puede [a su vez] ser representado como [suma] de tantos primos como se quiera, puede ser ilustrado y confirmado por una observación, misma que usted me comunicó formalmente; en concreto, que todos los números pares son suma de dos primos. […] Sin embargo, que todo número par sea la suma de dos n´umeros primoslo que considero un teorema correcto, es algo que no puedo demostrar.

Aquí es donde se encuentra la primera mención a la conjetura que trata el caso con los pares, y la pregunta inmediata sería: ¿Es la conjetura que hoy conocemos como “de Goldbach” una propuesta de Goldbach? Lo que parece corresponder a la realidad es que el primero que plantea el famoso enunciado es Euler.

Las dos conjeturas, aunque se están mostrando difíciles de demostrar, casi intratables,  se entienden perfectamente y por ello no vamos a desarrollar el tema. Si te interesa hay información abundante sobre estos dos desarrollos en otros blogs.

El motivo de esta entrada es reseñar dos papers en los que el autor del segundo avance, Helfgott, un torero matemático peruano, ha participado cómo autor. Son sobre un tema que nos interesó mucho y sobre el que hablamos largo y tendido en su momento en este blog: el problema del diametro de los grupos de permutaciones.  A nosotros nos interesó este problema desde el punto de vista algorítmico y de complejidad computacional.

II.

Ignoro si estos dos temas en los que ha trabajado Helfgott (la conjetura débil de Goldbach y el estudio del diámetro de grupos) tienen alguna relación. Cómo anécdota y casualidad, y por supuesto sin ánimo de compararme con nadie puedo comentar que hace años, en un momento en el que me sentía muy potente en estos temas (al contrario que ahora), yo también trabajé un par de tardes en la conjetura (fuerte) de Goldbach, no porque  el tema tuviese ninguna relación con el de la patente (en la que estaba trabajando en esos momentos de manera muy intensiva), sino porque por  casualidad leí sobre esta conjetura. Pero por los siguientes motivos, enseguida lo dejé:

–primero, porque cuando pensaba que estaba avanzando a pasos de gigante, vi en la Web que la linea de ataque que estaba siguiendo ya había sido seguida por otros, era bastante obvia, y no llevaba a nada;

segundo, creo recordar que me despistó el  redescubrir en esos mismos días (posiblemente en relación con la investigación de la conjetura) una función aritmeticamultiplicativa, la “divisor function“, también llamada función Tau (a no confundir con la función del mismo nombre y relacionada con ella  debida a Ramanujan). Aunque en la nota propia que he consultado para comprobar que función Tau era la que efectivamente redescubrí indicaba que ya había sido descubierta por Lambert o Euler, y pese a que tras una infructuosa búsqueda histórica realizada hoy pensaba que no era más un resultado sin historia, folk y por lo tanto evidente o trivial, parece que finalmente sí que tiene algo de historia (Elementary Number Theory in Nine Chapters, apartado 3.2 Number Theoretic Functions, páginas 86 a 93; gran libro, y no porque hablen de mi sin citarme…:-)), aunque empieza antes de los dos autores citados, que además no aparecen vinculados a la función Tau, sino a la Omega (que permite computar la suma de los divisores):

The history of the Tau-function can be traced back to Girolamo Cardano, an Italian mathematician-physician, who noted in 1537 that the product of any k distinct primes has 2^k divisors. Cardano played a major role in popularizing the solution to cubic equations and wrote the text devoted to the study of probability. Cardano’s result was reestablished in 1544 by Michael Stifel and again in 1657 by the Dutch mathematician Frans van Schooten. In 1659 Van Schooten published an influential Latin translation of Descartes “La Geometrie” that was highly regarded by Isaac Newton. The canonical formula for Tau(n), in Theorem 3.5, is found in the 1719 edition of John Kersey‘s Elements of that Mathematical Art Commonly Called Algebra. Kersey was a London surveyor and highly respected teacher of mathematics. His book was very popular, went through several editions, and was recommended to students at Cambridge. An equivalent representation for Tau(n), based on the canonical representation for n, appeared in the 1732 edition of Newton’s Universal Arithmetic. The canonical formula for Tau(n), in Theorem 3.5, also appeared in the 1770 edition of Edward Waring’s Meditationes algebraicae without justification, as was Waring’s nature. Waring, Lucasian Professor of Mathematics at Cambridge University, succeeded Isaac Barrow, Isaac Newton, William Whiston, Nicholas Saunderson, and John Colson in that position. In 1919, Leonard Eugene Dickson, a number theorist at the University of Chicago, introduced the notation Tau(n) to represent the number of divisors of the positive integer n and the notation Tau(n) to represent the sum of divisors of n. On the decade of 2000 an unknown researcher rediscovered again this formula, beeing, probably, the last rediscoverer😉.  

Hasta el último eslabón el pedigree del resultado es bastante notable…A partir de Newton o Waring, que lo recogen en sus libros se debe de dejar de hablar de redescubrimiento. Por otra parte parece el típico resultado que cualquiera que lo ataque durante un mínimo tiempo lo coinsigue. Otra historia son las cotas asíntoticas de esta función.  También señalar que una primera fórmula (no general) para la suma de los divisores, Omega (n) la dio Descartes en 1638. Euler dio la fórmula general en 1750. Lambert no aparece por ninguna parte.

–tercero, porque en general los problemas puramente matemáticos, sin otra motivación, no  consiguen engancharme fuertemente nunca (no quiero decir  con esto que no considere que sea importante dedicarles tiempo, ni mucho menos); y

–cuarto, la razón fundamental, porque tenía cosas más urgentes que hacer, relacionadas con la patente.

Por todos estos motivos no se ha demostrado todavía la conjetura de Goldbach🙂.

III.

En fin, batallitas aparte, las publicaciones de Helfgott sobre el diametro de grupos,  tema principal de esta entrada, son las que siguen:

1. Título. BOUNDS ON THE DIAMETER OF CAYLEY GRAPHS OF THE SYMMETRIC GROUP

Autores. JOHN BAMBERG, NICK GILL, THOMAS P. HAYES, HARALD A. HELFGOTT, AKOS SERESS, AND PABLO SPIGA ´

Abstract. In this paper we are concerned with the conjecture that, for any set of generators S of the symmetric group Sym(n), the word length in terms of S of every permutation is bounded above by a polynomial of n. We prove this conjecture for sets of generators containing a permutation fixing at least 37% of the points.

La fecha de publicación es de mayo 2012 y puedes ver el paper completo aquí.

1. Título: ON THE DIAMETER OF PERMUTATION GROUPS

Autores: HARALD A. HELFGOTT AND AKOS SERESS ´

Abstract. Given a finite group G and a set A of generators, the diameter
diam(Γ(G, A)) of the Cayley graph Γ(G, A) is the smallest ℓ such that every
element of G can be expressed as a word of length at most ℓ in A∪A^−1
.

We are concerned with bounding diam(G) := maxA diam(Γ(G, A)).
It has long been conjectured that the diameter of the symmetric group of degree n is polynomially bounded in n, but the best previously known upper bound was exponential in √nlogn. We give a quasipolynomial upper bound, namely, diam(G) = exp O((logn) ^4 log log n) = exp (log log |G|)^O(1)
for G = Sym(n) or G = Alt(n), where the implied constants are absolute. This
addresses a key open case of Babai’s conjecture on diameters of simple groups.

By a result of Babai and Seress (1992), our bound also implies a   quasipolynomial upper bound on the diameter of all transitive permutation groups of degree n.

La fecha de publicación de este segundo paper, más general que el anterior  es de febrero de 2013. Puedes ver el paper completo aquí. Ojo, parece que hablan del diametro de grafos y no de dígrafos, que creo recordar es el problema que nos interesó (hace ya tan to tiempo que de todo esto tengo sólo recuerdos vaporosos).

Cómo imagino muchos otros resultados, estos dos no habían sido captados por mi radar. Cuando los lea quizás añada más comentarios.

Addenda: Hay un tercer paper, muy reciente también, que me parece interesante. Growth in groups: ideas and perspectives.

 

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: