web analytics

Posts etiquetados con ‘Combinatoria’

Famosos matemáticos que nunca existieron III: G.W. Peck

Otros matemáticos fictios no han sido tan famosos como los que hemos comentado en entradas anteriores (Nicolas Bourbaki y Arthur L. Besse) , pero si gozaron de una cierta popularidad en su tiempo; este es el caso de G.W. Peck.

G.W. Peck

G. W. Peck es un seudónimo de un autor (y a veces coautor) de una serie de artículos en el ámbito de la combinatoria. Mantiene su propio perfil en Google Scholar en donde se encuentra un supuesto retrato que reproducimos. Aparecen 28 entradas (la primera de 1978, la última de 2002), que han recibido 357 citas, con un número h=11. También aparece en MathSciNet, con 16 publicaciones (la primera en 1979, la última en 2002), y ha sido citados 64 veces por 130 autores diferentes. Estos son sus coautores (por orden alfabético): Assmann, Susan F.; Du, Ding Zhu; Hsu, Derbiau Frank; Leibowitz, Rochelle; Ngo, Hung Quang; Paoli, Madeleine; Shastri, Aditya; Shor, Peter W.; Sysło, Maciej M.; Trotter, William T., Jr.; West, Douglas B.; Zak, Joshua.

En efecto, Peck apareció por primera vez como autor oficial de dos artículos:

Peck, G. W. Maximum antichains of rectangular arrays. J. Combin. Theory Ser. A 27 (1979), no. 3, 397–400.

Peck, G. W. Short proof of a general weight Burnside lemma. Stud. Appl. Math. 60 (1979), no. 2, 173–176.

El seudónimo “G. W. Peck” reúne las iniciales de los auténticos autores: Ronald Graham, Douglas West, George B. Purdy, Paul Erdős, Fan Chung y Daniel Kleitman. En un principio, el artículo indicaba que la afiliación de Peck era Xanadu, pero el editor de la revista se opuso, por lo que Ron Graham le dio un trabajo ficticio en los Laboratorios Bell. Pero Xanadu es la afiliación de Peck en Google Scholar.

 

Daniel Kleitman

Como comentamos, la investigación de G.W. Peck es en combinatoria, y hay algunos conceptos que llevan su nombre, por ejemplo, un poset de Peck (poset es el nombre de un conjunto parcialmente ordenado, partially ordered set) como un conjunto parcialmente ordenado graduado con cieretas propiedades.

Se podría decir que G.W. Peck es en gran medida el alter ego de Daniel Kleitman, quién por cierto reseñó para MathSciNet uno de los primeros artículos de Peck (G.W. Peck ha reseñado también algunos artículos en MathSciNet, para rizar el rizo).

El artículo

Peck, G. W. Kleitman and combinatorics: a celebration. Kleitman and combinatorics: a celebration (Cambridge, MA, 1999). Discrete Math. 257 (2002), no. 2-3, 193–224.

comienza con un subtítulo esclarecedor: Una discusión sobre la historia, las matemáticas y el encanto de Daniel J. Kleitman. La cosa no queda ahí porque en la afiliación del autor se indica: G.W. Peck is on leave from his usual residence. En el artículo, con ocasión de la celebración de los 65 años de Kleitman, Peck narra (de una manera muy divertida) la vida y trabajos de Kleitman, matemático que merece ser más conocido porque es una fuente de anécdotas (además de su gran trabajo matemático). Pero en este artículo, se cuenta el origen de Peck:

En un momento dado, Paul Erdos, en sus extensos viajes, trabajó en un problema con George Purdy; he olvidado de qué se trataba, y no estoy seguro de haberlo sabido nunca. Posteriormente, yo había hecho algo que simplificaba aún más la prueba. En ese momento, el resultado y su demostración podían exponerse en poco más espacio del que se necesitaría para enumerar a los autores, si todos nosotros tuviéramos que reconocer nuestras contribuciones.

Ron me llamó un día y me señaló la estupidez de presentar un artículo de ese tipo, pero pensó que la idea debía publicarse. Sugirió que cada colaborador recibiera una letra con un solo nombre de autor. Mientras jugaba con la idea, se le ocurrió que las letras pertinentes eran G(raham), P(urdy), E(rd ̋os),C(hung) y K(leitman), y que éstas formaban naturalmente la combinación “G. Peck”. Siendo Gregory Peck una famosa estrella de cine, éste parecía un nombre que tenía una existencia propia, lo que le daba un caché y una verosimilitud que apoyaba la idea.

El problema original había resultado ser un caso especial de algo que ya conocía. Una vez inventado G. Peck, se me ocurrió que el artículo sería mucho mejor si fuera algo más que el resultado que ya conocía. La cuestión era cómo obtener un resultado más general y nuevo que incluyera el anterior y dijera algo nuevo y no trivial.

Poco después, mencioné el problema a Doug West, que era entonces un estudiante de posgrado, y sugirió una extensión del resultado que suponía una clara mejora del mismo, y me pareció apropiado añadir también su inicial, si se iba a preparar un artículo al respecto. Y así, G.W. Peck envió su primer artículo, que fue publicado.

Daniel Kleitman

Y ahora Kleitman/Peck da una vuelta de tuerca y continúa:

Un día, unos años más tarde, mientras ojeaba un libro sobre destacadas personalidades de la década de 1880 que venía en un lote de libros que había comprado en una subasta, descubrí que realmente había un G.W. Peck, de hecho George Washington Peck, y que era un personaje bastante pintoresco. Escribió una columna de humor para varios periódicos y, posteriormente, varios libros sobre un chico extremadamente odioso que no dejaba de gastar horribles bromas a todos los que le rodeaban. Es posible que haya oído hablar de él. Su libro más famoso se titulaba Peck’s Bad Boy and HisPa (sigue siendo muy divertido).

En 1890 Peck fue elegido alcalde de Milwaukee por el margen más amplio de la historia de la ciudad. Ese mismo año, fue elegido Gobernador de Wisconsin por una amplia mayoría. Fue reelegido gobernador en 1894.

Y añade después un interesante debate: puesto que Erdös fue parte de Peck, ¿qué número de Erdös le podemos asignar? Esto merece otra entrada, por supuesto.

El artículo de Kleitman/Peck se cierra así:

He soñado con la idea de intentar conseguirle un trabajo, pero sus capacidades como orador son limitadas, y creo que Hacienda no ve con buenos ojos llevar esto hasta el punto de recibir pagos.Con todo, aunque no es una figura importante de ningún tipo, ha hecho un buen trabajo, ha hecho que el concepto de “Peck Poset” lleve su nombre, y no ha molestado a nadie por las cartas de recomendación: un tributo adecuado, creo, al histórico George Washington Peck.

Y terminamos con esta fotografía de “El indomable Will Hunting”, de la que Kleitman fue asesor y en la que aparece como extra en esa escena:

___________

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias, Real Academia Galega de Ciencias).

Etiquetas: , , ,
Categorias: General

El Premio Abel y las matemáticas discretas en España

El reciente Premio Abel concedido a László Lovász y Avi Wigderson, y del que dimos cuenta en Matemáticas y sus fronteras, nos lleva a una reflexión sobre la relación entre la llamada matemática discreta y la teoría de computación.

Uno de los nombres claves en la computación es, sin ninguna duda, el matemático Alan Turing, quien diseñó uno de los constructos mentales más relevantes del siglo XX, la máquina de Turing. Esos algoritmos son la esencia del software que subyace en nuestros ordenadores y es una clara muestra de cómo lo discreto es esencial para la computación.

Como es bien conocido, los ordenadores trabajan con un sistema binario de numeración, con unos y ceros (1 abierto, 0 cerrado), y en cantidades discretas. Lovász es un experto en teoría de grafos (recuerdo una excelente conferencia suya sobre grafos muy grandes), y los grafos son esenciales en muchas cuestiones de la computación. Sus primeros resultados los desarrolló con el propio Paul Erdös.

En su trabajo posteror, desarrolló algoritmos para tratar de resolver problemas. Uno de sus resultados más notables fue el llamado algoritmo LLL de reducción de bases de celosía Lenstra-Lenstra-Lovász, un algoritmo en tiempo polinómico que debe su nombre a las iniciales de sus creadores Arjen Lenstra, Hendrik Lenstra y László Lovász. Este algoritmo se usa para la factorización de polinomios con coeficientes racionales, para encontrar aproximaciones racionales simultáneas a los números reales, y para resolver problemas de programación lineal. Se usa además en criptografía.

El grafo formado por los editores de Wikipedia (aristas) que contribuyen a las diferentes versiones lingüísticas de Wikipedia (vértices) durante un mes del verano de 2013

Por otra parte, Wigderson estudia los problemas computacionales para tratar de determinar la dificultad de los algoritmos para resolverlos, en lo que se conoce como teoría de la complejidad. El problema clave es en cuánto tiempo (o en cuántos pasos) el algoritmo resolvería el problema. La clase general de preguntas para las que algún algoritmo puede proporcionar una respuesta en tiempo polinómico se denomina “clase P”. Para algunas preguntas, no hay una forma conocida de encontrar una respuesta rápidamente, pero si se proporciona información que muestre cuál es la respuesta, es posible verificar la respuesta rápidamente. La clase de preguntas cuya respuesta puede verificarse en tiempo polinómico se denomina NP, que significa “tiempo polinómico no determinista”. Pues bien, uno de los siete problemas del milenio es precisamente probar si P es igual o no a NP.

Uno de los resultados más sorprendentes de Wigderson es que los problemas difíciles (hard) se pueden resolver si se usan algoritmos ales leatoriedad en los problemas computacionales. Muchos problemas difíciles pueden resolverse con mayor rapidez si se abordan con algoritmos que dependen de la aleatoriedad. Poco después fue capaz de probar que en realidad esos algoritmos se podían convertir en otros deterministas que eran tan eficaces como los aleatorios.

Solución de un problema de viajante de comercio: la línea negra muestra el bucle más corto posible que conecta cada punto rojo.

La citación del premio Abel dice que “Gracias al liderazgo de Lovász y Wigderson, la matemática discreta y el campo relativamente joven de la informática teórica se han establecido como áreas centrales de la matemática moderna”.

Las tres cuestiones que nos planteamos son las siguientes. Si tan importantes son las investigaciones en matemáticas discretas en relación con sus aplicaciones a la computación:

1. Cuál es el nivel de la investigación matemática española en combinatoria, teoría de grafos y en general en matemática discreta?

2. ¿Existen en España equipos interdisciplinares de matemáticos e informáticos que aborden estas cuestiones?

3. ¿Cuál es el impacto de estas investigaciones en la tecnología desarrollada en España?

En 2005 publicamos un estudio titulado La investigación matemática española de difusión internacional: estudio bibliométrico del período 1996-2001, elaborado por María Bordons, Isabel Gómez, María Teresa Fernández, Fernanda Morillo, David Martín de Diego y yo mismo, una colaboración con el entonces CINDOC, en el que examinamos la especialización de las matemáticas españolas en relación con Europa, Estados Unidos y el mundo, comparando la sproducciones relativas en los campos de la MSC. De ese estudio, concluíamos:

Resulta muy llamativa la alta actividad relativa de España en Análisis funcional (código46). Menos llamativo, pero también digno de resaltar es la actividad del país en Análisis de Fourier (código 42) y Teoría de juegos (código 91). Por el contrario, España muestra baja actividad relativa en algunos temas como Combinatoria (código 5), Teoría de números (código 11), Teoría de sistemas (código 93) y Mecánica de fluidos (código 76), temas a los que el mundo dedica cerca del 3% de la producción en cada caso, y en los que nuestro país muestra un IE<0,7.

Para comprobar si la situación había variado en estos últimos años, haciendo una consulta grosera en MathSciNet. Así, desde 2005 a 20020, se encuentran 1394 papers de autores españoles con la clasificación de “Combinatoria”, una media de 87 por año. La mayoría de la producción se centra en el ámbito de las universidades catalanas y andaluzas, con una más reducida presencia de la UC3M y la URJC de Madrid.

La producción, aunque parece haber aumentado (un 1,95% del total mundial), se mantiene por debajo de la de otras líneas de investigación en cuanto a cantidad que no en calidad, lo que indica que es una disciplina que precisa aumentar el número de investigadores.

En cuanto a las colaboraciones con la informática, me gustaría destacar las del grupo GAPCOMB (Geometric, Algebraic and Probabilistic Combinatorics), asentado en la Universidad Politécnica de Cataluña y apoyado por la Barcelona Graduate School of Mathematics. Pero es claro que necesitaríamos más grupos donde se produzca ese cruce de caminos entre ambas disciplinas

En cuanto al tercer tema, me temo que no soy capaz de identificar actividades en ese sentido (y agradecería recibir información sobre ellas si es que ya existen).

En conclusión, este Premio Abel nos llama la atención sobre la relevancia de la Combinatoria sino también sobre la necesidad de impulsarala más en España.

___________

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias, Real Academia Galega de Ciencias).

Etiquetas: , , ,
Categorias: General

El Premio Abel 2021, concedido a Laszló Lovász y Avi Wigderson

La Academia Noruega de Ciencias y Letras ha anunciado su decisión sobre el Premio Abel 2021, que ha recaído en los matemáticos László Lovász, del Instituto de Matemáticas Alfréd Rényi y de la Universidad Eötvös Loránd de Budapest, Hungría, y Avi Wigderson, del Instituto de Estudios Avanzados de Princeton (EE.UU.), “por sus contribuciones fundacionales a la informática teórica y a la matemática discreta, y por su papel destacado en la configuración de éstas como campos centrales de la matemática moderna”.

Trazaremos unas breve biografías de ambos matemáticos. László Lovász nació  en 1948 en Budapest, y es fruto de la excelente escuela matemática húngara, especialmente brillante en algunos temas como la matemática discreta. László Lovász fue un alumno superdotado, ganador de medallas de oro en tres Olimpiadas Matemáticas Internacionales (164, 1965 y 1966), en dos ocasiones con la puntuación máxima.

 

László Lovász

Lovász obtuvo su grado de Ph.D. en 1970 de la Universidad Eötvös Loránd, Budapest, donde trabajó hasta 1975. Sin abandonar Hungría, pasó a la Universidad de Szeged, hasta 1982, regresando entonces a Eötvös  y crear el Departamento de Ciencias de la Computación. Después fue profesor de la Universidad de Yale durante la década de 1990, colaborando como investigador en el Microsoft Research Center hasta 2006. Entonces volvió a Hungría para dirigir el Instituto de Matemáticas de la Academia de Ciencias.

Entre los premios que ha ganado, están el Premio Wolf de 1999, el Premio Knuth de 1999, el Premio Gödel de 2001, el Premio Bolyai en 2007 y el Premio Kyoto de 2010, todos ellos de un indudable prestigio.

Su trabajo de investigación se centra en la combinatoria y la teoría de grafos, y sus aplicaciones a la complejidad en computación, un ejemplo extraordinario de cómo una investigación básica incide en las aplicaciones de frontera. Su labor se traduce en más de 300 artículos y libros que han conseguido un impacto enorme.

Reunión del Comité Ejecutivo de IMU en Perth (Australia)

 

Tuve la oportunidad de trabajar 8 años con Laci Lovász, de 2007 a 2010 como Presidente de la Unión Matemática Internacional (IMU) y de 2011 a 2014 como exPresidente. Tras su labor en IMU, fue elegido presidente de la Academia de Ciencias de Hungría entre 2014 y 2020.

En 2007 lo invitamos a Madrid para participar en un Simposio de la Fundación Areces, Las fronteras de las Matemáticas, que coordiné con mi colega de la Real Academia de Ciencias, Manuel López Pellicer. En todos estos años, he podido apreciar no sólo su extraordinaria calidad matemática, pero también su calidad humana, su sencillez y su siempre bonhomía.

 

En cuanto al otro premiado, Avi Wigderson nació en Haifa (Israel) en 1956. Ingresó en el Technion en 1977, y se licenció en Ciencias de la Computación en 1980. Se trasladó a Princeton para realizar sus estudios de posgrado, y se doctoró en 1983. En 1986 Wigderson regresó a Israel para ocupar un puesto en la Universidad Hebrea de Jerusalén. Al año siguiente fue nombrado profesor titular en 1991. En 1999 también aceptó un puesto en el Instituto de Estudios Avanzados (IAS) de Princeton, y en 2003 renunció a su puesto en la Universidad Hebrea para residir a tiempo completo en el IAS.

Avi Widgerson

Además de la medalla Nevanlinna, concedido por la IMU en el Congreso Internacional de Matemáticos (ICM) en Zúrich en 1994, obtuvo como Lovasz los Premios Gödel (2009) y Knuth (2019).

Su investigación es muy amplia en intereses que incluyen la teoría de la complejidad, los algoritmos paralelos, la teoría de grafos, la criptografía, la computación distribuida y las redes neuronales.

Según la Academia Noruega, la teoría de la “complejidad computacional” -que se ocupa de la velocidad y la eficiencia de los algoritmos- surgió en la década de los 70 y ahora es un campo establecido tanto en las matemáticas como en la informática teórica. “Lovász y Wigderson han sido las principales fuerzas de este desarrollo en las últimas décadas. Sus trabajos se entrelazan de muchas maneras y, en particular, ambos han hecho contribuciones fundamentales para entender la aleatoriedad en la computación y para explorar los límites de la computación eficiente”, afirmó Hans Munthe-Kaas, presidente del Comité Abel.

Este es el vídeo del anuncio

Imagen de previsualización de YouTube

Un premio muy merecido por ambos científicos.

___________

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias, Real Academia Galega de Ciencias).

 

Etiquetas: , , , , ,
Categorias: General

Lecciones de la combinatoria de Strathclyde

Hace unos días leí la última entrada del magnífico blog de Timothy Gowers, titulada The fate of combinatorics at Strathclyde. Gowers, medallista Fields en, cuenta que ha recibido un email de Sergey Kitaev, uno de los tres matemáticos dedicados a la Combinatoria en la Universidad de Strathclyde, que trabajan en el Departamento de Informática, informándole que la universidad ha decidido eliminar esta especialidad. En su breve entrada, Gowers informa que el problema está perfectamente resumido en otra entrada del blog de Peter Cameron. En lo que sigue trataremos de explicar el problema.

 

En esta universidad escocesa de Glasgow trabaja un excelente grupo de Combinatoria, formado por los matemáticos David Bevan, Sergey Kitaev y Einar Steingrímsson. Este grupo está incluido en el Departmento de Ciencias de la Computación y la Información, departamento que ha emprendido un plan de futuro, estratégico, en el que la combinatoria parece no tener sitio.

De hecho, se refiere literalmente que este tema no tiene una influencia en las tareas de la universidad, y que este  campo puede ser cubierto por otros profesores de análisis de datos o ciberseguridad. Se aduce también que estos tres matemáticos no consiguen proyectos de los de un millón de libras, y por tanto, no son necesarios y la combinatoria debe desaparecer de la universidad.

El informe del director del departamento obvia que este grupo es el responsable de una gran parte de la producción científica de más calidad, que han conseguido casi un millón de libras en proyectos en los últimos cuatro años, y que han contribuido con cursos a que el resto del departamento haya adquirido la formación necesaria para ser más competitivos.

Este problema, comenta Cameron, está ocurriendo en otras universidades británicas, al pensar que las matemáticas básicas no son necesarias o pueden adquirirse por otros medios.

 

Decir que la combinatoria no es útil es una preocupante muestra de ignorancia, ya que es una de las disciplinas más útiles en informática y en análisis de datos. Se aplican además a los sistemas dinámicos, la física estadística, teoría de códigos, o problemas de investigación operativa.

La reflexión que podemos hacernos es si los matemáticos estamos haciendo llegar de manera eficiente la utilidad de las matemáticas al resto de los científicos y a los que deben tomar las decisiones de política científica. Vivimos en España unos momentos en los que las matemáticas están muy presentes, pero también llegan noticias de falta de aprecio en la toma de algunas decisiones. Que las matemáticas son fundamentales, lo sabemos los matemáticos, lo saben muchos o la mayoría de nuestros colegas científicos, pero quizás falta un punto de estrategia para convencer a los que toman las decisiones. Podemos estar asistiendo a una burbuja matemática y no sería de gente inteligente dejar que fuera así.

Tenemos foros donde se puede mostrar el valor de las matemáticas. Por ejemplo, la Alianza SOMMA es un foro muy desaprovechado. Si el ICMAT fue activo en las reuniones de centros Severo Ochoa y María de Maeztu, estos cuatro últimos años  su presencia es puramente testimonial ante la falta de compromiso de sus actuales responsables. Y el BGSM ya no será unidad María de Maztu, con lo que los efectivos disminuyen. Por otra parte, la Red Estratégica de Matemáticas afronta también problemas para su continuidad. Creo que toca reflexionar.

___

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias).

Etiquetas: ,
Categorias: General