WT Tutte

William Thomas Tutte OC FRS FRSC (14 de mayo de 1917 - 2 de mayo de 2002) fue un descifrador de códigos y matemático inglés y canadiense. Durante la Segunda Guerra Mundial, realizó un avance brillante y fundamental en el criptoanálisis del cifrado Lorenz, un importante sistema de cifrado alemán nazi que se utilizó para comunicaciones ultrasecretas dentro del Alto Mando de la Wehrmacht. La naturaleza estratégica de alto nivel de la inteligencia obtenida del avance crucial de Tutte, específicamente en el descifrado masivo de los mensajes cifrados de Lorenz, contribuyó en gran medida, y quizás incluso de manera decisiva, a la derrota de la Alemania nazi. También tuvo una serie de logros matemáticos significativos, incluido el trabajo de base en los campos de la teoría de grafos y la teoría de matroides.

La investigación de Tutte en el campo de la teoría de grafos demostró ser de notable importancia. En un momento en que la teoría de grafos era todavía un tema primitivo, Tutte comenzó el estudio de las matroides y las convirtió en una teoría ampliando el trabajo que Hassler Whitney había desarrollado por primera vez a mediados de la década de 1930. Aunque las contribuciones de Tutte a la teoría de grafos han influido en la teoría de grafos moderna y muchos de sus teoremas se han utilizado para seguir avanzando en el campo, la mayor parte de su terminología no estaba de acuerdo con su uso convencional y, por lo tanto, su terminología. no es utilizado por los teóricos de grafos en la actualidad. "Tutte avanzó la teoría de grafos desde un sujeto con un texto (D. Kőnig's) hacia su estado actual extremadamente activo."

Vida temprana y educación

Tutte nació en Newmarket en Suffolk. Era el hijo menor de William John Tutte (1873–1944), un jardinero de la finca, y Annie (de soltera Newell; 1881–1956), ama de llaves. Ambos padres trabajaron en los establos de Fitzroy House, donde nació Tutte. La familia pasó algún tiempo en Buckinghamshire, el condado de Durham y Yorkshire antes de regresar a Newmarket, donde Tutte asistió a la escuela primaria Cheveley Church of England en el pueblo cercano de Cheveley. En 1927, cuando tenía diez años, Tutte ganó una beca para la Escuela secundaria para niños de Cambridge y el condado. Ocupó su lugar allí en 1928.

En 1935 ganó una beca para estudiar ciencias naturales en el Trinity College de Cambridge, donde se especializó en química y se graduó con honores de primera clase en 1938. Continuó con la química física como estudiante graduado, pero se transfirió a matemáticas en la finales de 1940. Como estudiante, él (junto con tres de sus amigos) se convirtió en uno de los primeros en resolver el problema de elevar al cuadrado el cuadrado, y el primero en resolver el problema sin un subrectángulo cuadrado. Juntos, los cuatro crearon el seudónimo de Blanche Descartes, bajo el cual Tutte publicó ocasionalmente durante años.

Segunda Guerra Mundial

Las máquinas Lorenz SZ tenían 12 ruedas cada una con un número diferente de cámaras (o "pins").

Número de rueda	1	2	3	4	5	6	7	8	9	10	11	12
Nombre de la rueda BP	${displaystyle psi _{1}$	${displaystyle psi _{2}$	${displaystyle psi _{3}$	${displaystyle psi _{4}$	${displaystyle psi _{5}$	${displaystyle mu }$37	${displaystyle mu }$61	${displaystyle chi _{1}}$	${displaystyle chi _{2}}$	${displaystyle chi ¿Qué?$	${displaystyle chi _{4}}$	${displaystyle chi _{5}}$
Número de cámaras (pins)	43	47	51	53	59	37	61	41	31	29	26	23

Poco después del estallido de la Segunda Guerra Mundial, el tutor de Tutte, Patrick Duff, lo sugirió para trabajar en la guerra en la Government Code and Cypher School en Bletchley Park (BP). Fue entrevistado y enviado a un curso de capacitación en Londres antes de ir a Bletchley Park, donde se unió a la Sección de Investigación. Al principio, trabajó en el cifrado Hagelin que estaba siendo utilizado por la Armada italiana. Esta era una máquina de cifrado de rotor que estaba disponible comercialmente, por lo que se conocía la mecánica del cifrado, y para descifrar los mensajes solo requería averiguar cómo estaba configurada la máquina.

En el verano de 1941, Tutte fue transferido para trabajar en un proyecto llamado Fish. La información de inteligencia había revelado que los alemanes llamaban a los sistemas de transmisión de teleimpresores inalámbricos "Sägefisch" (pez sierra). Esto llevó a los británicos a utilizar el código Fish para el sistema de cifrado de teleimpresor alemán. El apodo Tunny (tunafish) se usó para el primer enlace no Morse, y posteriormente se usó para las máquinas Lorenz SZ y el tráfico que cifraron.

La telegrafía utilizaba el Alfabeto telegráfico internacional n.º 2 (ITA2) de 5 bits. No se sabía nada sobre el mecanismo de cifrado, aparte de que los mensajes estaban precedidos por un indicador de 12 letras, lo que implicaba una máquina de cifrado de rotor de 12 ruedas. El primer paso, por tanto, tenía que ser diagnosticar la máquina estableciendo la estructura lógica y por tanto el funcionamiento de la máquina. Tutte desempeñó un papel fundamental para lograr esto, y no fue hasta poco antes de la victoria aliada en Europa en 1945, que Bletchley Park adquirió una máquina de cifrado Tunny Lorenz. Los avances de Tutte llevaron finalmente al descifrado masivo de mensajes cifrados por Tunny entre el Alto Mando Alemán (OKW) en Berlín y sus mandos militares en toda la Europa ocupada y contribuyeron, quizás de manera decisiva, a la derrota de Alemania.

Diagnóstico de la máquina de cifrado

El 31 de agosto de 1941, se enviaron dos versiones del mismo mensaje utilizando claves idénticas, lo que constituía una "profundidad". Esto permitió a John Tiltman, el veterano y notablemente talentoso criptoanalista de Bletchley Park, deducir que se trataba de un cifrado de Vernam que utiliza la función Exclusive Or (XOR) (simbolizada por "⊕"), y extraer los dos mensajes y por lo tanto obtener la clave de oscurecimiento. Después de un período infructuoso durante el cual los criptoanalistas de la Sección de Investigación trataron de averiguar cómo funcionaba la máquina Tunny, esta y algunas otras claves fueron entregadas a Tutte, a quien se le pidió que "viera qué puede hacer con estas".

La máquina Lorenz SZ42 con sus tapas removidas. Museo del Parque Bletchley

En su curso de capacitación, a Tutte se le había enseñado la técnica de examen Kasiski de escribir una clave en papel cuadriculado, comenzando una nueva fila después de un número definido de caracteres que se sospechaba era la frecuencia de repetición de la clave. Si este número fuera correcto, las columnas de la matriz mostrarían más repeticiones de secuencias de caracteres que el azar por sí solo. Tutte sabía que los indicadores Tunny usaban 25 letras (excluyendo la J) para 11 de las posiciones, pero solo 23 letras para la otra. Por lo tanto, probó la técnica de Kasiski en el primer impulso de los caracteres clave, utilizando una repetición de 25 × 23 = 575. No observó una gran cantidad de repeticiones de columna con este período, pero sí observó el fenómeno en un diagonal. Por lo tanto, volvió a intentarlo con 574, que mostró repeticiones en las columnas. Reconociendo que los factores primos de este número son 2, 7 y 41, lo intentó de nuevo con un período de 41 y "obtuvo un rectángulo de puntos y cruces que estaba repleto de repeticiones".

Sin embargo, estaba claro que el primer impulso de la llave era más complicado que el producido por una sola rueda de 41 impulsos clave. Tutte llamó a este componente de la clave ${displaystyle chi _{1}}$ ()Chi₁). Pensó que había otro componente, que era XOR-ed con esto, que no siempre cambió con cada nuevo personaje, y que éste era el producto de una rueda que él llamó ${displaystyle psi _{1}$ ()psi₁). Lo mismo se aplica para cada uno de los cinco impulsos ()${displaystyle chi _{1}chi _{2}chi _{3}chi ¿Qué?$ y ${displaystyle psi _{1}psi _{2}psi _{3}psi ¿Qué?$). Así que para un solo personaje, toda la llave K consistía en dos componentes:

$${displaystyle K=chi oplus psi }$$

En Bletchley Park, los impulsos de marca se representaban con x y los impulsos de espacio con •. Por ejemplo, la letra "H" se codificaría como ••x•x. La derivación de Tutte de los componentes chi y psi fue posible por el hecho de que era más probable que los puntos fueran seguidos por puntos, y que las cruces tenían más probabilidades que no debe ser seguido por cruces. Esto fue producto de una debilidad en la configuración de clave alemana, que luego eliminaron. Una vez que Tutte hizo este avance, el resto de la Sección de Investigación se unió para estudiar los otros impulsos, y se estableció que las cinco ruedas chi avanzaban todas con cada nuevo personaje y que las cinco ruedas psi todas movidas juntas bajo el control de dos mu o "motor" ruedas Durante los siguientes dos meses, Tutte y otros miembros de la Sección de Investigación trabajaron en la estructura lógica completa de la máquina, con su conjunto de ruedas con levas que podrían estar en una posición (elevada) que sumaba x al flujo de caracteres clave, o en la posición alternativa que se agregó en •.

Diagnosticar el funcionamiento de la máquina Tunny de esta manera fue un logro criptoanalítico verdaderamente notable que, en la mención de la inducción de Tutte como Oficial de la Orden de Canadá, se describió como 'uno de los grandes hazañas intelectuales de la Segunda Guerra Mundial.

Método estadístico de Tutte

Para descifrar un mensaje de Tunny se requería conocimiento no solo del funcionamiento lógico de la máquina, sino también de las posiciones de inicio de cada rotor para el mensaje en particular. Se estaba buscando un proceso que manipulara el texto cifrado o la clave para producir una distribución de frecuencia de caracteres que se apartara de la uniformidad que el proceso de cifrado pretendía lograr. Mientras estaba adscrito a la Sección de Investigación en julio de 1942, Alan Turing descubrió que la combinación XOR de los valores de caracteres sucesivos en un flujo de texto cifrado y clave enfatizaba cualquier desviación de una distribución uniforme. La corriente resultante (simbolizada por la letra griega "delta" Δ) se llamó la diferencia porque XOR es lo mismo que la resta de módulo 2.

La razón por la que esto proporcionó una manera en Tunny era que aunque la distribución de frecuencias de caracteres en el cifertexto no podía distinguirse de un flujo al azar, lo mismo no era cierto para una versión del cifertexto del cual el Chi se había eliminado el elemento clave. Este fue el caso porque donde el texto contenía un carácter repetido y el psi las ruedas no se movieron, la diferenciada psi carácter${displaystyle Delta psi }$Sería el personaje nulo ('/ En Bletchley Park. Cuando XOR-ed con cualquier personaje, este personaje no tiene efecto. Los caracteres repetidos en el texto fueron más frecuentes tanto por las características de alemán (EE, TT, LL y SS son relativamente comunes), como porque los telégrafos repitieron con frecuencia los personajes de cambio de figuras y letras como su pérdida en un mensaje telegráfico ordinario podría llevar a la ginebra.

Para citar el Informe General sobre Tunny:

Turingery introdujo el principio de que la clave se diferencia en uno, ahora llamado Δ, podría producir información inalcanzable de la clave común. Esto Δ El principio debía ser la base fundamental de casi todos los métodos estadísticos de ruptura y fijación de las ruedas.

Tutte explotó esta amplificación de la no-uniformidad en los valores diferenciados y para noviembre de 1942 había producido una manera de descubrir los puntos de inicio de la rueda de la máquina Tunny que se conocía como el "método estadístico". La esencia de este método era encontrar la configuración inicial de la Chi componente de la clave al tratar exhaustivamente todas las posiciones de su combinación con el cifertexto, y buscando evidencia de la no-uniformidad que refleja las características del texto original. Porque cualquier personaje repetido en el texto siempre generaría •, y de forma similar ${displaystyle Delta psi _{1}oplus Delta psi _{2}}$ generaría • cuando psi las ruedas no se movieron, y alrededor de la mitad del tiempo cuando lo hicieron – un 70% en general.

Además de aplicar la diferenciación a los caracteres completos de 5 bits del código ITA2, Tutte la aplicó a los impulsos individuales (bits). La configuración actual de la leva de la rueda chi debía haberse establecido para permitir que se generara la secuencia de caracteres relevante de las ruedas chi. Era totalmente impracticable generar los 22 millones de caracteres de las cinco ruedas chi, por lo que inicialmente se limitó a 41 × 31 = 1271 de las dos primeras. Después de explicar sus hallazgos a Max Newman, Newman recibió el trabajo de desarrollar un enfoque automatizado para comparar el texto cifrado y la clave para buscar desviaciones de la aleatoriedad. La primera máquina se denominó Heath Robinson, pero la computadora Colossus, mucho más rápida, desarrollada por Tommy Flowers y usando algoritmos escritos por Tutte y sus colegas, pronto se hizo cargo de descifrar códigos.

Doctorado y carrera

A fines de 1945, Tutte reanudó sus estudios en Cambridge, ahora como estudiante de posgrado en matemáticas. Publicó algunos trabajos que comenzaron antes, uno ahora famoso que caracteriza qué gráficos tienen una coincidencia perfecta y otro que construye un gráfico no hamiltoniano.

Tutte completó un doctorado en matemáticas de Cambridge en 1948 bajo la supervisión de Shaun Wylie, quien también había trabajado en Bletchley Park en Tunny. Su tesis Una teoría algebraica de grafos se consideró innovadora y trataba sobre el tema conocido más tarde como teoría matroide.

El mismo año, invitado por Harold Scott MacDonald Coxeter, aceptó un puesto en la Universidad de Toronto. En 1962, se trasladó a la Universidad de Waterloo en Waterloo, Ontario, donde permaneció el resto de su carrera académica. Se retiró oficialmente en 1985, pero permaneció activo como profesor emérito. Tutte fue fundamental para ayudar a fundar el Departamento de Combinatoria y Optimización de la Universidad de Waterloo.

Su carrera matemática se concentró en la combinatoria, especialmente en la teoría de grafos, a la que se le atribuye haber ayudado a crear en su forma moderna, y en la teoría de matroides, a la que hizo profundas contribuciones; un colega lo describió como "el matemático líder en combinatoria durante tres décadas". Fue editor en jefe del Journal of Combinatorial Theory hasta que se jubiló de Waterloo en 1985. También formó parte de los consejos editoriales de varias otras revistas de investigación matemática.

Contribuciones de investigación

El trabajo de Tutte en teoría de grafos incluye la estructura de espacios de ciclo y espacios de corte, el tamaño de coincidencias máximas y la existencia de factores k en gráficos y gráficos hamiltonianos y no hamiltonianos. Refutó la conjetura de Tait, sobre la hamiltonicidad de los gráficos poliédricos, utilizando la construcción conocida como fragmento de Tutte. La prueba final del teorema de los cuatro colores hizo uso de su trabajo anterior. El polinomio gráfico que llamó "dicromato" se ha vuelto famoso e influyente bajo el nombre de polinomio de Tutte y sirve como prototipo de invariantes combinatorios que son universales para todos los invariantes que satisfacen una ley de reducción específica.

Los primeros avances importantes en la teoría de las matroides fueron realizados por Tutte en su tesis doctoral de Cambridge de 1948, que formó la base de una importante secuencia de artículos publicados durante las siguientes dos décadas. El trabajo de Tutte en teoría de grafos y teoría de matroides ha tenido una gran influencia en el desarrollo tanto del contenido como de la dirección de estos dos campos. En la teoría de matroides, descubrió el altamente sofisticado teorema de la homotopía y fundó los estudios de grupos de cadenas y matroides regulares, sobre los cuales demostró profundos resultados.

Además, Tutte desarrolló un algoritmo para determinar si una matroide binaria determinada es una matroide gráfica. El algoritmo aprovecha el hecho de que un grafo plano es simplemente un grafo cuyo circuito-matroide, el dual de su enlace-matroide, es gráfico.

Tutte escribió un artículo titulado Cómo dibujar un gráfico en el que demostró que cualquier cara en un gráfico de 3 conexiones está encerrada por un ciclo periférico. Usando este hecho, Tutte desarrolló una prueba alternativa para mostrar que cada gráfico de Kuratowski no es plano al mostrar que K₅ y K _3,3 cada uno tiene tres ciclos periféricos distintos con un borde común. Además de usar ciclos periféricos para demostrar que los gráficos de Kuratowski no son planos, Tutte demostró que cada gráfico simple de 3 conexiones se puede dibujar con todas sus caras convexas e ideó un algoritmo que construye el dibujo del plano resolviendo un sistema lineal. El dibujo resultante se conoce como incrustación de Tutte. El algoritmo de Tutte hace uso de las asignaciones baricéntricas de los circuitos periféricos de un gráfico simple de 3 conexiones.

Los hallazgos publicados en este documento han demostrado ser de gran importancia porque los algoritmos que desarrolló Tutte se han convertido en métodos populares de dibujo de gráficos planos. Una de las razones por las que la incrustación de Tutte es popular es que los cálculos necesarios que realizan sus algoritmos son simples y garantizan una correspondencia uno a uno de un gráfico y su incrustación en el plano euclidiano, que es de importancia al parametrizar una malla tridimensional al plano en el modelado geométrico. "El teorema de Tutte es la base para las soluciones a otros problemas de gráficos por computadora, como el morphing."

Tutte fue el principal responsable de desarrollar la teoría de la enumeración de grafos planos, que tiene estrechos vínculos con los polinomios cromáticos y dicromáticos. Este trabajo involucró algunas técnicas altamente innovadoras de su propia invención, que requerían una considerable destreza de manipulación en el manejo de series de potencias (cuyos coeficientes cuentan tipos apropiados de gráficos) y las funciones que surgen como sus sumas, así como destreza geométrica para extraer estas series de potencias del gráfico. -situación teórica.

Tutte resumió su trabajo en Selected Papers of W.T. Tutte, 1979, y en Graph Theory as I have know it, 1998.

Cargos, honores y premios

El trabajo de Tutte en la Segunda Guerra Mundial y posteriormente en combinatoria le valió varios puestos, honores y premios:

• 1958, Fellow of the Royal Society of Canada (FRSC);
• 1971, Premio Jeffery-Williams de la Sociedad Matemática Canadiense;
• 1975, Henry Marshall Tory Medal by the Royal Society of Canada;
• 1977 Se celebró en la Universidad de Waterloo una conferencia sobre Teoría Gráfico y Temas Relacionados con ocasión de su 60o cumpleaños;
• 1982, Isaak-Walton-Killam Premio del Consejo del Canadá;
• 1987, Fellow of the Royal Society (FRS);
• 1990–1996, Primer Presidente del Instituto de Combinación y sus Aplicaciones;
• 1998, Nombrado director honorario del Centro de Investigación Críptográfica Aplicada de la Universidad de Waterloo;
• 2001, Oficial de la Orden del Canadá (OC);
• 2001, premio CRM-Fields-PIMS.
• 2016, Waterloo Region Hall of Fame
• 2017, Waterloo "William Tutte Way" nombre de carretera

Tutte se desempeñó como bibliotecario de la Royal Astronomical Society of Canada en 1959–1960, y el asteroide 14989 Tutte (1997 UB7) recibió su nombre.

Debido al trabajo de Tutte en Bletchley Park, el Establecimiento de Seguridad de las Comunicaciones de Canadá nombró una organización interna destinada a promover la investigación en criptología, el Instituto Tutte de Matemáticas y Computación (TIMC), en su honor en 2011.

En septiembre de 2014, Tutte se celebró en su ciudad natal de Newmarket, Inglaterra, con la inauguración de una escultura, después de que un periódico local iniciara una campaña para honrar su memoria.

Bletchley Park en Milton Keynes celebró el trabajo de Tutte con una exposición Bill Tutte: Mathematician + Codebreaker de mayo de 2017 a 2019, precedida el 14 de mayo de 2017 por conferencias sobre su vida y obra durante el Simposio del Centenario de Bill Tutte.

Vida y muerte personales

Además de los beneficios profesionales de trabajar en la nueva Universidad de Waterloo, el entorno más rural del condado de Waterloo atrajo a Bill y su esposa Dorothea. Compraron una casa en el pueblo cercano de West Montrose, Ontario, donde disfrutaron de caminatas, pasaron tiempo en su jardín en el Grand River y permitieron que otros disfrutaran del hermoso paisaje de su propiedad.

También tenían un amplio conocimiento de todas las aves de su jardín. Dorothea, una ávida alfarera, también era una gran excursionista y Bill organizaba excursiones de senderismo. Incluso cerca del final de su vida, Bill todavía era un ávido caminante. Después de la muerte de su esposa en 1994, se mudó de nuevo a Newmarket (Suffolk), pero luego regresó a Waterloo en 2000, donde murió dos años después. Está enterrado en el cementerio West Montrose United.

Seleccionar publicaciones

Libros

• Tutte, W. T. (1966), Conectividad en gráficos, Exposiciones matemáticas, vol. 15, Toronto, Ontario: University of Toronto Press, Zbl 0146.45603
• Tutte, W. T. (1966), Introducción a la teoría de los esteroides, Santa Monica, Calif.: RAND Corporation report R-446-PR. También Tutte, W. T. (1971), Introducción a la teoría de los esteroides, Métodos analíticos y computacionales modernos en ciencia y matemáticas, vol. 37, Nueva York: American Elsevier Publishing Company, ISBN 978-0-444-00096-5, Zbl 0231.05027
• Tutte, W. T., ed. (1969), Progresos recientes en la combinatoria. Proceedings of the third Waterloo conference on combinatorics, May 1968, Nueva York-Londres: Academic Press, pp. xiv+347, ISBN 978-0-12-705150-5, Zbl 0192.33101
• Tutte, W. T. (1979), McCarthy, D.; Stanton, R. G. (eds.), Documentos seleccionados de W.T. Tutte, Vols. I, II., Winnipeg, Manitoba: Charles Babbage Research Centre, St. Pierre, Manitoba, Canada, pp. xxi+879, Zbl 0403.05028
  • Volumen I: ISBN 978-0-969-07781-7
  • Volumen II: ISBN 978-0-969-07782-4
• Tutte, W. T. (1984), Teoría del Gráfico, Enciclopedia de matemáticas y sus aplicaciones, vol. 21, Menlo Park, California: Addison-Wesley Publishing Company, ISBN 978-0-201-13520-6, Zbl 0554.05001 Reimpreso de la Universidad de Cambridge Press 2001, ISBN 978-0-521-79489-3
• Tutte, W. T. (1998), Teoría de Gráficos como lo he sabido, Oxford conferencia serie en matemáticas y sus aplicaciones, vol. 11, Oxford: Clarendon Press, ISBN 978-0-19-850251-7, Zbl 0915.05041 Reimpresión de 2012, ISBN 978-0-19-966055-1

Artículos

• Brooks, R. L.; Smith, C. A. B.; Stone, A. H.; Tutte, W. T. (1940). "La disección de los rectángulos en cuadrados". Duke Math. J. 7: 312–340. doi:10.1215/s0012-7094-40-00718-9.