Archive for the ‘MATEMATICAS’ Category

IBM Q. ¿ Cuánta sombra hace ?

marzo 6, 2017

Hace años publicamos  una entrada sobre las promesas de  la computación cuántica. Leyendo la prensa parecería que estas promesas se están cumpliendo ya.

Pero leyendo artículos sólo un poco más técnicos, de prensa técnica, parece que no es así. No veo nada realmente nuevo sino futuribles, como siempre que se habla de esta tecnología. No es la única: la energía de fusión nuclear le gana en esto.

Realmente no hay mucha información al respecto pero parece más bien una operación de marketing más, orquestada ahora por motivos que desconozco. Posiblemente lo que realmente IBM quiera publicitar es el simulador de 5 qubits accesible en modo cloud y útil para aprender a programar algoritmos cuánticos. Lo han incrementado a 20 qubits, lo cual es interesante. Pero esto no es más que  una hipótesis.

Quedamos a la espera de que el influencer más famoso que opina sobre estos temas se manifieste, si es que lo hace. Esperamos que no nos deje mal…:-).

Aquellos interesados en profundizar (no es mi caso ahora mismo) pueden buscar publicaciones de los responsables de las criaturas cuánticas.

IBM’s work is based on research done at Yale through professor Robert Schoelkopf (the IBM team is mostly his Ph.D. and post-grad students).

The other prominent US school working on this is the University of California at Santa Barbara under professor John Martinis in an effort that was backed and absorbed by Google in 2014.

P.s.1. Explicamos el título. No tiene nada que ver con la sombra que pueda proyectar una eventual nube (cloud). Simplemente hace años también publicamos una entrada sobre estos temas cuyo título contenía la frase Cuánto sol hace (de  cuyo contenido no me acuerdo), título que recogía el chascarrillo que circuló en España sobre el título de la (floja) película Quantum Solace.

P.s 2. No se por qué no aparece en el cuadro de herramientas de tratamiento de texto de WordPress la herramienta para cuadrar el texto de la entrada.

Actualización 20 de marzo de 2017. Ya se han manifestado dos blogueros a los que se les puede conceder la máxima confianza cuando opinan sobre estos temas.  El lector los puede leer aquí y aquí.   Se centran más en un nuevo resultado de D-Wave que en el proyecto de IBM (o el similar Google).  Pero creo que mi calificación de futurible se sostiene. En el primer enlace se recomienda leer también los comentarios: suelen ser informativos. Cuando terminemos con la entrada sobre la historia alto medieval de Borgoña/Provenza, tema mucho más complejo  que este de computación cuántica, seguramente haremos una entrada sobre los grafos implicados en la máquina de D-Wave.

Actualización 3 de marzo 2017.

Una entrada de otro bloguero, que como los dos anteriores ofrece la máxima confianza. En este caso conviene aclarar que se trata de investigador escéptico sobre las posibilidad de construir un computador cuántico.

Ya adelanto que es una entrada con una elevada densidad de enlaces. Este bloguero además de como investigador en matemáticas, campo en el que ya no tiene nada que demostrar (entiéndase esto sólo en uno de los dos sentidos de la frase; esperamos que su trabajo siga dando grandes frutos) tendría un buen futuro como periodista de investigación :-).

Extracto.

List of companies involved in quantum computers. A few webpages:  1Qbit ; D-wave ;Quantum circuits (Yale group) ; Rigetti ; Monroe’s blog; Station Q (Microsoft); GoogleIBM-Q;

Sobre Microsoft  y la computación cuántica.

Un extracto de otro blog de un investigador y empresario en computación cuántica:

 Alibaba, Google, IBM, Intel, and Microsoft (alphabetical order) , not to mention the govs. of Australia, Canada, China, EU, Holland, UK and USA are each spending tens of millions of dollars per year to achieve the same goal as Rigetti, to build an elusive gate model quantum computer.

Decenas de millones no parece demasiado teniendo en cuenta los nombres que aparecen.

Una muy breve historia de la organización industrial del sector de computación cuántica. Nos centramos en proyectos empresariales y dejamos de lado a la academia o instituciones públicas. La fuente es el mismo blog de la última cita, Quantum Bayesian Networks. y la revista MIT Technology Review.

1999. Se funda D-Wave. Since it was founded in 1999, D-Wave has obtained more than $100 million in funding from sources such as: the venture capital firm Harris & Harris, the Canadian government, and Goldmann Sachs.

Mayo 2011. La única empresa dedicada públicamente a estas actividades sigue siendo D-Wave. Este año firma un contrato con Lockheed Martin. En 2017 D-Wave sigue desarrollando actividades.

¿ 200? Microsoft e IBMGoogle will be competing not only with whatever improvements D-Wave can make, but also with Microsoft and IBM, which have substantial quantum computing projects of their own (see“Microsoft’s Quantum Mechanics” andIBM Shows Off a Quantum Computing Chip).

Junio 2014. Google contrata a Martinis. He was hired by Google in June 2014 after persuading the company that his team’s technology could mature rapidly with the right support. With his new Google lab up and running, Martinis guesses that he can demonstrate a small but useful quantum computer in two or three years. “We often say to each other that we’re in the process of giving birth to the quantum computer industry,” he says.

Terminamos la breve historia aquí. Hasta 2011 las incumbents seguían viendo la corrida desde la barrera y en 2014 Google ¿ da el primer paso o hubo otro anterior de alguna otra multinacional ?. No Microsoft e IBM ya se habían implicado antes. Más adelante en esta  entrada nos planteamos una serie de preguntas más detalladas sobre todo esto.

Se me ha ocurrido un par de reflexiones adicionales sobre la teología cuántica (1) computación cuántica:

Primera reflexión, que se me ha ocurrido pq desde hace poco tiempo dispongo de una información de la que no disponía: ¿ pq de repente empresas (no hablo de ahora sino de hace pocos años) con una trayectoria seria y dilatada en sus estrategias de I+D e incluso de Marketing (que yo conozca hay al menos dos en la lista anterior que cumplan con estos rasgos; y se puede excluir al menos a otra, Google, que ni es seria ni tiene trayectoria acreditada: tuvo suerte en una ocasión pero no la han vuelto a repetir) están apostando fuerte por ésta, aparentemente incierta, tendencia ?. ¿ Hay alguna novedad científica o tecnológica que no conocemos el resto de los mortales, que lo explique ?. Tengo una posible explicación, pero me la reservo. Creo que es un tema digno de investigar.

Lo primero que habría que ver es si el fenómeno es real: de verdad están apostando fuerte. ¿ Constituyen estos esfuerzos una proporción importante de sus inversiones en I+D ?. Y lo segundo, si se confirmase que la apuesta es fuerte, ¿ desde cuando exactamente ha aparecido ?, ¿ a partir de que momento ha tenido lugar este cambio de actitud, de mirar la corrida académica y científica desde la barrera, como hacían desde hace décadas o al menos quinquenios, a bajar a la plaza y coger el toro por los cuernos ?. Y tercero el pq. ¿ Que gran descubrimiento ha habido en este campo, campo que como decimos ya lleva unas décadas sobre la mesa,  como para que estas empresas apuesten fuerte ahora ? ¿ O ha sido una acumulación gradual de pequeñas causas ?. Ahora invertir tiempo en esto es imposible para nosotros. Esperamos que lo hagan otros. Sí señalamos que aunque un computador cuántico es una máquina, las tres multinacionales implicadas son de software. Uno esperaría ver implicados a otros actores en este drama.

Nota. Se puede poner como momento de comienzo de este sector principios de los 80 con Benioff, Manin, Feynman o Deutsch y otros o principios de los 90, con Deutsch–Jozsa, Simon, Shor, Grover y otros. 

The field of quantum computing was initiated by the work of Paul Benioff[2] and Yuri Manin in 1980,[3] Richard Feynman in 1982,[4] and David Deutsch in 1985.[5] A quantum computer with spins as quantum bits was also formulated for use as a quantum space–time in 1968. Fin de nota.

Segunda reflexión: todos  los expertos saben que la mecánica cuántica es correcta. Pero también que es incompleta como teoría física.

El pilar de todos estos esfuerzos de I+D es un teoría incompleta. Supongamos que tras una inmensa inversión se consigue la computación cuántica práctica, pero lo que se obtiene es una especie rueda de cuadrada, en relación a lo que podría conseguirse si la tecnología estuviese basada en una teoría completa, un rueda redonda, que son las que ruedan bien de verdad. ¿ No sería mejor invertir todo este dinero en desarrollar la teoría completa antes ?. Lo que queremos decir es que quizás con la teoría completa se podría conseguir lo mismo pero con mucho menos esfuerzo.

Ok, anticipo el contra-argumento correcto pero quizás incompleto y sin duda fácil: la mecánica de Newton también es incompleta, pero se sigue utilizando por igual en muchas aplicaciones, pese a disponer de otras más completas. Por lo tanto quizás para el campo de aplicaciones de la computación cuántica, la mecánica cuántica sea suficiente. Quizás.

En cuanto a lo de invertir para obtener la teoría correcta y completa, quizás algún lector pensará ¿ todavía más ?.  Y algún otro, en que,  ¿ en teoría de cuerdas ?.

(1) Que no se lea esto como como una ironía que intenta minimizar o ridiculizar estos proyectos. Sólo me hizo gracia descubrir el otro día que la disciplina de la teología cuántica…¡¡ existe !!.

 

Algorítmica y complejidad computacional. Un nuevo estilo / problema en matemáticas.

enero 26, 2017

Lo hemos comentado muy recientemente en una entrada anterior (perdón por la autocita).

Es el nuevo estilo de publicación: sin estar seguro de que lo que se tiene entre manos y publica es 100% correcto. Al igual que los problemas que se intentan resolver, las demostraciones son cada vez más complejas y necesitan múltiples mentes para la comprobación de su corrección.

Se ha publicado una interesante entrada en el blog GLL en la que hablan sobre este  mismo tema

The issue is simple:

Someone writes up a paper that “proves” that X is true, where X is some hard open problem. How do we check that X is proved?

The proof in question is almost always long and complex. So the checking is not a simple matter. In some cases the proof might even use nonstandard methods and make it even harder to understand.

y comentan sobre las posibles reacciones a este nuevo estilo de matemáticas.  Recomendamos su lectura.

(more…)

Caso de S5 2-4 generado retorcido o twisted.

junio 21, 2016

Actualización 18 de julio: he detectado un error en el punto 1. En breve lo modificaré, incluyendo seguramente las imágenes (ahora tengo el ordenador con algún problema en el modulo de electricidad). Fin de actualización.

Actualización 20 de julio. ¡¡ Corregido !!. Esta corrección nos ha obligado a borrar parte del texto que habíamos escrito, redundante. Y he cambiado la imagen. Fin de actualización.

En la entrada anterior hemos analizado un caso de S5 2-4 generado entrelazado o entangled que no sólo tenía RHs en dos de los VFs posibles (y eran 7) y hemos determinado el mecanismo que hace que los que no tienen RH no puedan tenerlo y lo que es más importante hemos demostrado que el que este mecanismo sea posible es debido a que el caso es entrelazado. Y también hemos comentado que este mecanismo no podría ser el motivo de que los casos twisted no tengan recorridos hamiltonianos.

¿ Podemos encontrar un mecanismo similar para los casos twisted, mecanismo en el que se vea claramente que puede intervenir por ser twisted ? Esto es lo que vamos a intentar contestar en esta entrada.

Para ello en esta entrada analizamos dos casos. Aunque los dos casos son twisted lo son de manera diferente: el primer caso es más cerrado, los IASes que lo hacen twisted están más cercanos el uno del otro, que en el segundo. Esto tiene consecuencias: si bien, como veremos, en los casos twisted más cerrados el método de activar el ciclo de C4 de todas las maneras posibles y concluir que todas llevan a contradicción funciona de manera bastante directa en los otros casos, los más abiertos, no parece ser así (es lo que queremos determinar).

En los casos twisted del segundo tipo, más abiertos, al aplicar el algoritmo de la patente, ocurre lo que explicamos a continuación. Primero una muestra gráfica, ya que lo hemos dibujado completamente. Sus parámetros son S5, G5, C2C4, IAS5, Circunferencia 6. Figura en la imagen siguiente (de nuevo bastante confusa, pido disculpas por ello):

s5 c2 c2 ias 6 twisted para blog

Sus VFs (excluimos los que sabemos, por el teorema de Rankin, que no pueden tener RHs). Son 23541 y 54123. Al aplicar el algoritmo que hemos implementado (el reflejado en la primera patente) determina que no tiene RHs en ninguno de estos dos vértices, pero dato importante, necesita respectivamente 27 opcions (y 11 llamadas de backtraking) y 42 opciones (y 18 llamadas de backtraking).

Creo relevante señalar a este respecto que en los otros dos casos en los que hemos encontrado demostraciones cortas o más directas de que no podían existir RHs (todos los 2-3 generados; algunos de los 2-4 generados entangled), el algoritmo identificaba que no existían sin opciones…

Otra de las preguntas que nos hacemos en esta entrada es si, en estos casos, hay una demostración más directa, más rápida, más económica, más corta, más comprensible, de que no tienen RHs en los VFs o sólo podemos determinar esto ejecutando todas estas llamadas de backtraking.

En cualquier caso queda claro lo que buscamos: identificar un mecanismo que esté relacionado con la propiedad de ser twisted y que  haga imposible la existencia de un RH en todos o algunos de los VFs. Y es muy posible que el hecho de que los ciclos de orden 4 se deban de activar de una determinada manera (que haya restricciones al respecto) forme parte del mecanismo. Y esto explica también por que el algoritmo necesita tanto backtraking en estos casos: esta propiedad no está incorporada en la implementación.

1.Twisted cerrados. A estos efectos comenzamos analizando un caso twisted cerrado que como veremos admite una demostración de que no contiene RHs sin necesidad de utilizar el algoritmo. Es aplicando aplicando el método que ya describíamos en la descripción de la patente, que consiste en activar de todas las maneras posibles el ciclo de C4 que sale de la identidad.

Es un caso 2-4 generado e IAS de orden 6 y circunferencia de orden 3 (¿ 6 IASes ?), en el que se detectaba que no podía tener recorridos hamiltonianos de manera más rápida que aplicando el algoritmo.

En un segundo punto aplicaremos este método (que ya hemos comentado que no nos satisface del todo, estamos convencidos de que debe de haber un método todavía más directo) al caso abierto, el que ha motivado la entrada para ver si funciona también. Por cierto, en breve aplicaré a este caso el algoritmo para ver tras cuantas opciones determina que no contiene RHs.  

Actualización 27 de junio de 2016. Ya lo he aplicado: salvo en el VF 31425, en el que determina que no hay VF tras 3 opciones y una llamada a backtraking en los otros lo encuentra de manera directa tras entre 1 opción (en el otro ciclo potencial y 3 op). De ciclo a ciclo el número de opciones es 3, 3,2,2,2,1. Fin de actualización.  

El caso aparece en la imagen siguiente (no está completo).

caso c2 c4 circ 3 twisted

El método es como sigue:

–el ciclo de orden 4 que sale de la identidad se puede activar de 16 maneras posibles diferentes. Algunas son equivalentes.

primera manera de activarlo: todos inactivados. Como se puede ver se genera contradicción (aparecerían necesariamente ciclos de orden 2). Esto es independiente de la propiedad de twistedness. Esta clase de equivalencia contiene solo un representante.

segunda manera de activarlo: sólo 1 activado (y por lo tanto los otros tres inactivados). En esta clase de equivalencia hay 4 representantes o maneras posibles de activar.  Y es fácil ver que se genera también necesariamente contradicción, de manera independiente a la propiedad de twistedness.

tercera manera de activarlo: tres arcos activados, también con cuatro representantes.  En la imagen siguiente (que representa el último digrafo mostrado anteriormente pero de manera más clara, sin confusión de colores) mostramos la situación cuando se activa el IAS de la identidad tomando como VF la permutación 13254. Esto hace que el ciclo de orden 4 que sale de la identidad se active por dos arcos. En esta situación todavía no se genera ninguna contradicción.

c2c4 ias 6 nuevo para blog

En la imagen se aprecia claramente que al ser twisted, el IAS marcado con A1 conecta con el IAS marcado con A2 y con el marcado como A3 y que también A2 y A3 están conectados. Lo  mismo sucede con los IASes marcados B1, B2 y B3 o los IASes marcados C1,C2 y C3. Y falta un último “cluster” o grupo de IASes que no hemos dibujado de momento para no añadir más confusión. En un caso smooth estas conexiones entre estos IASes no existirían. Es importante que el lector recuerde esto ya que estas conexiones que sólo existen por ser twisted son clave, como veremos.  

En la imagen siguiente vemos  que pasa al activar el tercer arco del ciclo de orden 4. Nótese que si activasemos estos tres arcos del ciclo de orden 4 directamente, llegaríamos a la misma situación que aparece en la imagen.

cntradiccion 200

El marcar el tercer arco tiene consecuencias:

–aparece un posible ciclo de orden 4 (marcado en la figura cómo Contradicción 1) en el que hay tres arcos ya marcados, posible ciclo que hay que corregir.

–aparece otro posible ciclo de orden 4, marcado como contradicción 2.

Si dibujamos el IAS rojo, y extraemos las correspondientes consecuencias aparece otro ciclo de orden 4, en este caso ya inevitable. Se concluye que no puede existir un RH si marcamos los 3 arcos del ciclo de orden 4 de la identidad.

Nota. Según recuerdo el primer digrafo de este caso, el que realizamos hace años y publicamos hace un par de días un poco más arriba en esta misma entrada, contiene exactamente el numero de IASes necesario para demostrar que surge contradicción en cualquiera de las activaciones posibles del ciclo de orden 4 de la identidad. En este caso contiene casi tantos IASes como el total de IASes del digrafo, lo cual no parece una gran ventaja: pero ¿ y si en los casos twisted, a medida que n crece el la contradicción se puede seguir encontrando activando un número de IASes limitado del entorno de la identidad ? . En este caso nadie diría que el método no es ventajoso…Por eso me interesa determinar si también en los casos twisted pero más abiertos, el test es local.

Fin de nota.

De la misma manera que hemos demostrado con todo detalle que emerge contradicción al marcar los 3 arcos del ciclo de orden 4 de la identidad, se podría demostrar que pasa lo mismo con cualquier otra activación de tres arcos de este ciclo (y de cualquier otro), así como al activar sólo dos arcos opuestos en el ciclo de orden 4.

Y es fácil ver de que la causa de todo esto es que el caso sea twisted.

Continuará…

Nota.

Aprovecho para hacer un apunte rápido sobre una pregunta que hicimos en una entrada anterior, a la que asociamos una figura que volvemos a publicar:

smoothes twisted

Cuando construimos el entorno de la identidad puede, en teoría suceder dos cosas: quedan todos los vértices del entorno saturados (es decir de todos ellos entran y salen 2 arcos) o no quedan saturados. En el caso de que queden saturados es fácil demostrar que casos como el de la figura no pueden suceder: supongamos que un IAS de la circunferencia que se encuentre fuera del entorno de la identidad enlaza con un IAS que se encuentre al otro lado del entorno y que en su mismo lado podemos añadir más IASes a la circunferencia. Entonces por simetria debería de entrar en el entorno de la identidad un arco de alguno de estos IASes, lo cual es contradictorio con el hecho de que está saturado. Por lo tanto cuando el entorno de la identidad queda saturado podemos afirmar que el caso será smooth.

Queda por determinar:

–si es posible construir el entorno de la identidad sin que quede saturado;

–si esto fuese posible, que formas posibles pueden adoptar estos casos;

–y si estas formas tienen consecuencias de cara al problema  de recorridos hamiltonianos.

Haremos una entrada específica para comentar sobre todo esto en detalle.

Fin de nota.

2. Twisted más abierto (realizada a partir de 27 de julio de 2016).

Ya hemos comentado que si bien en el caso twisted más cerrado estudiado en el punto 1, cuando se le aplica el algoritmo, se puede determinar que no tiene RHs en pocas opciones (entre 3 y 1) y con pocas llamadas a backtraking (en general ninguna, lo determina directamente) en el caso twisted más abierto que estamos estudiando ahora, cuando se le aplica el algoritmo, tarda bastante más en determinar que no tiene RHs: más de 20 opciones y más de 11 llamadas a backtraking.

Luego es mucho más interesante encontrar una demostración lo más directa posible en estos casos. Diría que la vía de ataque tiene que implicar el IAS de la identidad y el IAS opuesto al de la identidad en la circunferencia.

A continuación dos imágenes que muestran el caso que estudiamos. La primera ya está publicada en esta misma entrada. La segunda es un nuevo dibujo que realmente tampoco mejora mucho en términos de claridad pero al  menos nos da otra perspectiva.

s5 c2 c2 ias 6 twisted para blog

c2c4 IAS5 para blog 22

 Ver entrada con mismo título, nº2.

Historia de la teoría de la complejidad computacional: nuevos primeros pasos.

mayo 31, 2016

A raíz de la entrada anterior, en la que hablábamos de Yves Lecerf, y su contribución a las ciencias computacionales, he encontrado este enlace a un capítulo de un libro en el que hablan sobre temas que hoy se incluirían dentro de la teoría de complejidad computacional, pero en realidad antes de que ésta disciplina existiese.

Curiosamente el capítulo del libro (de 1968, año complejo en Francia en otros aspectos), se titula Complexité y el contenido, como ya hemos comentado, es sobre los problemas de complejidad computacional: explosión combinatoria etc…Como veremos el artículo que de alguna manera creó la disciplina como un ente autónomo es de 1965 lo cual explica el uso de estos nombres.

La lista de nombres que aparecen en una historia de la complejidad computacional en el ámbito anglosajón (es decir EEUU; el enlace lo es a un artículo sobre la historia de la teoría de la complejidad computacional, fundamentalmente en EEUU, escrita por uno de sus protagonistas, que además es uno de los editores del primer blog que empezó a publicar sobre estos temas, bien conocido) suelen comenzar con Hartmanis y Stearns (1965), Cobham (1964), Edmonds (1965) y ya, cuando la disciplina madura y toma plena forma, Levin, Cook (la visión de Cook, escrita en 1983; habla de un artículo de Bennett de 1962: Bennett, J. H. On Spectra. Doctoral dissertation, Department of Mathematics, Princeton University, 1962) y Karp con sus bien conocidos respectivos resultados. También se suele / puede incluir a Rabin (1959) como precursor.

Tanto Hartmanis (Hartmanis, J. January 1981. Observations about the development of theoretical computer science. Annals of the History of Computing, Volume 3, Number 1, pp. 42-51. ) como Stearns han escrito sus respectivas versiones del periodo en el que fueron protagonistas.

En otras tradiciones como la soviética, como mucho se remontan a los 50 (Trakhtenbrot, de este mismo autor es la historia de la teoría de la complejidad computacional en la Unión Soviética que aparece en el enlace anterior, titulada A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms ). Por cierto Levin pertenece a esta otra tradición, sobre la que hablaremos luego de nuevo.

Nota. Cabe preguntarse en que medida el interés que surgió en paralelo en estos temas a uno y otro lado del telón de acero fueron producto de la Guerra Fría. Llama por ejemplo la casi total ausencia de europeos occidentales entre los pioneros. También por su diferente recepción a uno y otro lado.

Extracto.

It is not surprising that we were attracted by the same problems as our colleagues in the West (of course, we were working independently and in parallel), and we worked out almost the same techniques: complexity measures, crossing sequences, diagonalization, gaps, etc. All of these ideas arose quite naturally; we became most excited, and they evoked in us enthusiasm similar to that described by Hartmanis in his historical account (1981).

Fin de nota.

En el artículo sobre el que hablamos desde el principio nos hablan de otras épocas y otros nombre que no había visto asociados a esta disciplina:

(more…)

¿ Una generalización del “teorema” de Milnor para dígrafos de Cayley (2-3) generados ?

mayo 25, 2016

1.En una nota de una entrada anterior hemos profundizado sobre el “teorema” de Milnor, cuyo enunciado y alcance en un principio no comprendíamos muy bien (su resultado no se publicó, se cita en otras fuentes de manera muy incompleta como si su demostración fuese evidente; aunque todavía tengo alguna duda sobre la constante, una vez que se comprende la idea efectivamente no es complicado comprenderla).

Tras darle unas cuantas vueltas y aunque , ya tengo más o menos claro su contenido, idea de demostración que esbozamos a continuación.

En los casos (2-3) generados, cuando un path recorre el digrafo fuera del IAS de la identidad, lo recorre necesariamente con el patrón abb o ab^2. Obviamente en cualquier caso, este patrón sólo se puede repetir un cierto número de veces hasta obtener de nuevo la identidad, que variará según los generadores.

El teorema de Milnor afirma:

Proposition 2 (attributed to Milnor [2, p. 201]). Assume the finite group is generated by two elements a and b, such that a^2=b^3=1 (o la identidad). If |G|>9|ab^2|, then the Cayley digraph does not have a hamiltonian path.

Y lo que no me queda claro es de dónde sale este n=9, ya que entiendo que en general puede haber casos en los que (ab^2)^n=1 no quede acotada por esta constante. Por ello entiendo que el resultado de Milnor se refiere a un caso específico de dígrafos.

2. En cualquier caso, las tres variables clave para que funcione el teorema son:

el tamaño del IAS,

el tamaño del dígrafo y,

el n de la relación (ab^2)^n=1.

Si el tamaño del IAS es pequeño y el tamaño del n son pequeños en relación al tamaño del dígrafo completo entonces no podrá haber RHs, dado que gran parte del recorrido se haría fuera del IAS y el n aplicado a la relación repetitiva no llegaría a cubrir todo el dígrafo.

Es decir (una primera versión,  que variará cuando tenga todo más claro) si |G|-|IAS| > |ab^2|^n=1, entonces no puede haber RHs.

Por lo tanto en aquellos casos (2-3) generados en los que el IAS suponga una parte significativa del dígrafo (y existen) habrá más posibilidades de que existan RHs. Y en aquellos en los que el IAS sea pequeño en relación al dígrafo, habrá menos posibilidades.

Más que una generalización se trataría de un test que permitiría identificar los casos (2-3) generados que no tengan RHS en ninguno de los VFs posibles. Realmente una vez se comprende el sentido del teorema de Milnor y nuestros resultados con unas minimas comprobaciones se puede llegar a la generalización.

¿ No supondrían estos últimos casos, si existiesen (todo esto que estamos contando es abstracto, al margen de momento de casos reales), una excepción a nuestro test de smoothness / twistedness?. No, dado que en general son igualmente twisted, pero si son casos que permiten una expresión más concreta, de tipo aritmético, de un obstáculo a la hamiltonicidad (similar al expresado por el teorema de Rankin y que por cierto, hemos generalizado también, apareciendo esta generalización como contenido de dos de las reclamaciones), obstáculo que se podría expresar de manera más farragosa con el test indicado.

Estudiaremos todos esto con más detalle en próximas actualizaciones a esta entrada o en entradas posteriores. Concretamente quiero ver la forma general de los generadores (2-3) de An y Sn.

Actualización 26 mayo 2016.

Con lo que estamos comentado,  en abstracto, y a la espera de posteriores comprobaciones, más concretas, me queda claro que es muy posible que haya infinitos casos / familias infinitas de tipo (2-3) con RHs en alguno de los VFs posibles. Esto me aclara una duda que tenñia. Al igual que también los hay (y posiblemente más frecuentes sin RHs en ningún VF posible; en algunos artículos algunos). Incluso no veo imposible poder determinar de antemano, sin necesidad de aplicar el algoritmo cuales de los VFs finales posibles tendrán RH. Posiblemente sólo uno en cada VF.

Por otra parte comentar que pienso entiendo que esta generalización posiblemente ya debía de estar en la mente o comentario de Milnor o de cualquier otro que se haya interesado por su resultado, a poco  que hayan intentado profundizar. Para mi, con la información de que disponía el fogonazo fue casi inmediato una vez que comprendí el resultado de Milnor he hice unas cuantas comprobaciones. Antes de las comprobaciones me rondaba en la cabeza la generalización peor no la tenía para nada aterrizada. También es posible que este y otros investigadores o no profundizasen o no dispusiesen de la misma información que yo, o que considerasen que no era necesario hacer la idea mucho más explícita…

Fin de actualización. 

3. ¿ No podría generalizarse esta técnica a otros casos (2-n) generalizados ?. Entiendo que como mucho a los (2-4) generados.  A partir de aquí, el tema está tan abierto que determinar los paths posibles cuando se recorres la zona en la que no se encuentra el IAS identidad, puede empezar a ser complejo. Estudiaremos los casos (2-4) generados.

4. Otros resultados similares. Es posible que este resultado, sobre el que ya hemos hablado en otras ocasiones, de alguna manera utilice esta misma idea. Lo tengo que comprobar.

Entrelazamiento y orden de circunferencia, ¿ dos propiedades / parámetros no independientes ?

mayo 24, 2016

Estudiando los casos de la entrada anterior, he detectado un tema que no  había visto antes.

Cuando calculamos el orden de la circunferencia en un caso de IAS par, y obtenemos que esta es de orden 2, pueden darse tres casos:

–cuando la circunferencia es de orden 2 y el caso es 1/2 entangled, y entonces la circunferencia contiene dos IASes, el IAS y el DAS de la identidad, y entonces al parecer la permutación (con la que se calcula el orden de la circunferencia comparandola con la identidad) es del tipo 123…(n)(n-1) o 21….(n-1)n, es decir con todos lospuntos fijos menos 2, es decir  una transposición. Recordemos que estos casos incluyen a los cycle-entangled.

–Cuando la circunferencia es de orden 2 y el caso es n-entangled (y por lo tanto ni 1/2 entangled ni 2-entangled), entonces esta contiene 3 IASes y la permutación es del tipo 123456->456123. Es decir sin puntos fijos. Esta es la primera anotación sobre este asunto.

–cuando la circunferencia es de orden 2 y el caso es 2-entangled, en cuyo caso la circunferencia contendrá 4 IASes y la permutación es del tipo 123456->132465, es decir con 2 o más puntos fijos.

Y seguramente este mismo fenómeno (adaptado a las nuevas condiciones; por ejemplo aquí no tendrá sentido hablar de casos 2-entangled), se dará en circunferencias de otros órdenes.

Tema a investigar con más casuística.

Dígrafos de Cayley (2,3)-generados (y otros similares): sus propiedades de hamiltonicidad.

mayo 18, 2016

Entrada en construcción. Estará terminada cuando desaparezca este mensaje.

Actualizado 18 de agosto 2016: se han añadido datos a los C2C4 generados. A falta de los de S6, la información está completa (todos los casos dibujados; no he añadido de momento los dibujos). Fin de actualización.

Actualización 8 de mayo de 2016.

Añadida información relativa a casos C2C4 de S4 (3 casos) y un dibujo más (que ya tenía realizados de hace años y he encontrado ayer revisando mis archivos) de 1 caso de S5.

Fin actualización.

http://www.famnit.upr.si/files/zakljucna_dela_repo/48

https://books.google.es/books?id=d5PLBQAAQBAJ&pg=PA224&lpg=PA224&dq=solvable+groups+permutation+generators&source=bl&ots=CGTnfchuwD&sig=i16JVQOO-SlCyuJMv0HgTVqVFpY&hl=es&sa=X&ved=0ahUKEwiP07-asfHMAhWJ2RoKHRUvAUM4FBDoAQgzMAM#v=onepage&q=solvable%20groups%20permutation%20generators&f=false

 

En base a las entradas anteriores en esta entrada quiero analizar las propiedades de hamiltonicidad de todos los casos de que dispongo (2-3) generados.

También analizaremos otros casos (2-n) generados de S5 cuyas propiedades estructurales no analicé en detalle en su momento. El factor común de todos ellos es,

–primero, que uno de los generadores es una involución y por ello en la base de datos que elaboré aparecían como entrelazados o entangled. Pero algunos de ellos o incluso que no haya recorridos en ninguno es posible

–segundo que el tamaño del IAS es “grande” en relación con el número de vértices o bien el orden del generador que no es de orden 2 es grande también.

–tercero, son casos problemáticos, en el sentido de que tienen algunos vértices finales posibles sin recorridos hamiltonianos, o incluso ninguno de ellos los tiene.

La motivación de esta entrada es la siguiente:

quiero averiguar si, como pienso, las propiedades estructurales que hemos reflejado en la patente (2º solicitud de patente) explican todos los casos complicados. Si no he analizado mal el caso de la entrada anterior (el PSL(2,7), que tengo pendiente de reanalizar) podría ser smooth y no tener recorridos hamiltonianos en ninguno de los vértices finales posibles. Realmente no hace falta analizarlo con mayor profundidad: es twisted, como todos aquellos cuya circunferencia es de orden 2 (4 IASES) si el IAS es par o de orden 4 (4 IASES) si el IAS es impar.

No obstante sí me interesa analizar varios otros de estos casos y similares, dado que es posible que tengan propiedades estructurales que nos permitan predecir mejor sus propiedades de hamiltonicidad.

Nota. El lector que haya seguido estas entradas a lo mejor se habrá realizado algunas preguntas sobre la propiedad smooth/twisted. Por ejemplo:

(more…)

PSL(2,7).

mayo 8, 2016

psl(2,7) (2)

El digrafo de Cayley que aparece en la imagen anterior, de PSL(2,7) isomorfo a GL (3,2) es muy interesante para  mi. En la  imagen aparece con generadores de orden 2 y 3.

(more…)

Algoritmica y complejidad computacional. Algunos resultados sobre permutaciones.

marzo 13, 2016

Disclaimer. Esta entrada se ha escrito en los días 13 y 14 de marzo de 2016. La parte dónde comentamos sobre resultados de otros autores, más  el día 13; la parte más de “investigación” propia o en la que comentamos sobre nuestra propia investigación más el día 14. Recordamos una vez, con una imagen más lo que dijo Donald Knuth, uno de los padres de la informática sobre el problema que hemos estudiado y algunos de cuyos resultados estamos intentando patentar en EEUU desde hace años, con grandes dificultades en la concesión, que se deben a motivos que desconocemos, pues incluso en un mundo post Alice Corp, se deberían de poder patentar.        

Ignacio Reneses. Knuth TAOCP.

Y recordamos lo que ha comentado un investigador recientemente al respecto, investigador que utilizando uno de los pasos que quiero patentar ha dado respuesta a uno de los problemas “abiertos” en digrafos de Cayley Bigenerados:

The Hamiltonicity of G(n) was first considered by Nijenhuis and Wilf (Exercise 6 in [5]). A general condition by Rankin [7] forbids Hamilton cycles in G(n) for even n ≥ 4 (see Swan for a simplified proof [11]). Determining if Hamilton cycles exist for odd n was given a difficulty rating of 48/50 by Knuth, making it one of the hardest in The Art of Computer Programming (Problem 71 in Section 7.2.1.2 [4]).

.  

Si mis resultados aportan tanta luz a todos los casos posibles (todos los pares posibles) del problema de recorridos hamiltonianos (ciclos y caminos) en Digrafos de Cayley bigenerados, siendo un problema con una de reputación de ser tan complicado, incluso si hablamos de un solo caso, de un solo par, ¿ por que no se ha concedido la patente para los pasos solicitados directamente y está costando 8 años de tramitaciones ?. ¿ Por qué tengo, a lo mejor (esta semana saldremos de dudas)  que volver a explicar esto una vez más oficialmente al examinador pagando, seguramente, otra importante cantidad a mi agente de patentes en EEUU (no me quejo por ello; hacen bien su trabajo) ?. ¿ Por qué un problema que es tan complicado para uno de los padres de la informática (y para cualquiera que intente abordarlo sin las técnicas de la patente) no lo es para la USPTO ? ¿ Sólo porque la solución es sencilla de programar ? 

Fin de disclaimer.

Quería reflejar en esta entrada, muy brevemente,

–en el primer punto algunos resultados sobre la teoría estadística de permutaciones (propiedades de una sola permutación elegida aleatoriamente en un grupo dado, en general Sn) y algunos problemas de la teoría estadística de permutaciones (propiedades de dos permutaciones, relacionados con la segunda patente, con nuestra propia investigación) que nos gustaría ver resueltos (en algunos puntos esbozamos soluciones). En esta parte seguramente nos repetimos, pues a medida que la voy escribiendo voy acordándome que igual hay una entrada anterior de contenido similar (en cuanto a algunas preguntas; la novedad de esta entrada serían las respuestas): 8 años, que es lo que están tardando en tramitar la USPTO mis solicitudes dan para olvidar.

–en el segundo punto, la importancia de la representación de grupos de permutaciones y en el tercero una simple curiosidad, la relación del problema del Sudoku generalizado con el problema de encontrar ciclos hamiltonianos en grafos generales.

1.Teoría estadística de permutaciones: propiedades de una sola permutación.

En general la teoría estadística de permutaciones se refiere a las propiedades que podemos esperar que tenga una sola permutaciónen general elegida de manera aleatoria.

Como el lector sabe, en el resultado de la patente nos hemos interesado más en identificar determinadas propiedades que puedan tener pares de permutaciones, y sus consecuencias de cara a la solución del problema de recorridos hamiltonianos. Como veremos ya se ha trabajado bastante también en problemas relativos a pares de permutaciones (por ejemplo el resultado de Dixon, sobre el que hablaremos más adelante).

Empezamos con el artículo relevante de wikipedia que

(more…)

Collineation groups of finite projective planes and Graph Isomorphism.

noviembre 4, 2015

Disclaimer. Esta es la re-publicación de una entrada anterior (de 2009 o 2010) que hemos reeditado para la ocasión, por el reciente breaktrough en relación al problema de isomorfismo de grafos, sobre el que todavía no se conocen detalles. Seguramente el método por el que Babai ha mejorado la cota superior para este problema no tiene nada que ver con el contenido de la entrada. 

Hubo un tiempo en que uno leía sobre estos temas  y era como leer el periódico: me entraban con total facilidad. Me interesaban mucho y les dedicaba tiempo. Eso era antes de recibir golpe tras golpe en las tramitaciones de las patentes.

Ya se sabe que el sistema de patentes está diseñado para estimular la publicación de nuevos resultados, no para estimular la investigación en sí: es un señuelo en el que sólo se pica una vez, salvo que te vaya bien, cosa que ocurre en la  minoría de los casos. En general, y salvo casos extremos, el que ha probado una vez no repite por esta vía (esta tortura) y lo normal es  que se dedique  a otras cosas que no tengan nada que ver con la invención / investigación.  Esta es la experiencia de un toro que salió con mucha fuerza a la plaza (es decir con mucho entusiasmo,  con mucha ilusión, con muchas ganas, sobre todo por partir con un buen resultado, una invención genuina, con potenciales aplicaciones) y al que, tras tercios de  Bilski varas y Alice Corp banderillas brutales, sobre todo el segundo, ya solo le queda que le den la puntilla

¿ Son más satisfactorias las  otras vías del investigador, como  la academica con financiación pública ? ¿ Hay alguna diferencia entre preparar solicitudes de patente que nadie se va a leer, ni siquiera el examinador, y preparar solicitudes de financiación de proyectos de investigación ? ¿ Se leen los funcionarios que conceden las subvenciones las propuestas ? ¿ Es menos arbitraria la concesión de las segundas que la  de las primeras ? Desconozco las respuestas a estas preguntas, pero de una manera o de otra, la mayor parte del tiempo se invierte en redactar documentos que nos son de investigación dirigidos a individuos que no  los van a comprender.

Luego seguramente no hay mucha diferencia. Ok, hay una gran diferencia: el que va por la vía de la patente paga por rellenar impresos mientras que al que va por la vía de la academia le pagan por hacer lo mismo. Yo me refiero a que ninguno de los dos,  salvo el que obtiene rendimientos por la vía de la patente o el que consigue una subvención (también hay investigadores estrella que consiguen cuantiosos premios que les permite  una independencia financiera y una investigación libre), tiene al  final tiempo para investigar que es lo que se supone que le gustaría hacer. 

Quiero recordar que considero que la respuesta a mi  segunda solicitud de patente es una auténtica tomadura de pelo, un impresentable pitorreo a mi costa y altamente ofensivo teniendo en cuenta los recursos invertidos, y una falta de respeto al inventor en general, indigno de una institución de un país avanzado como es EEUU y demuestra que el examinador, tras más de seis años de tramitación,  o bien no se ha leído la solicitud y no conoce la innovación en detalle o está actuando de mala fe. Se mire por dónde se mire, con las reglas en la mano (Interim Guidances y Examples), incluso después del caso Alice corp, la segunda solicitud se debe de conceder. Ya hemos señalado a tres responsables: examinador, supervisor y dirección de la USPTO (la directora). Y ya hemos comentado que esperamos que con la respuesta que ya tenemos  preparada (estamos dándole la última revisión) la decisión sea otra.   

Ahora no es que aborrezca estos temas pero he perdido grandemente el interés, les dedico mucho menos tiempo y realmente me cuesta enterarme, incluso de lo que escribí yo. Ya no es como leer un periódico, sino más bien como leer un ensayo de un filósofo post-moderno. Por lo tanto advierto que la entrada puede contener errores.  

Está en inglés (y puede contener erratas o errores gramaticales) y debido a la elevada erosión que  sufre la web con el paso del tiempo, muchos enlaces fallarán.

Añadido posterior. Al  inicio de la entrada había un párrafo relacionado con mi propia investigación que he eliminado pues luego concluí que lo que describía en él era incorrecto.

No recuerdo qué es lo que me llevó a la hipótesis del primer párrafo que he dejado. Lo dejo tal cual ya que si lo elimino ya tendría que empezar a modificar el resto de la entrada.

Posiblemente la siguiente proposición:

Proposition 4. Testing isomorphism of graphs with bounded valence is polynomialtime reducible to the problem of determining generators for Aute (X ), where X is a connected graph with the same valence, and e is a distinguished edge.

Una presentación reciente (2014) del método de Babai para los diseños de Steiner (que eran algunos de los casos que habían identificado como más complicados para este problema). Diría que la situación es muy parecida a la que hemos descubierto en el problema de recorridos hamiltonianos en los Dígrafos de Cayley bigenerados (versión decisión):  los casos más difíciles tienen menos grados de libertad (el tamaño del grupo de automorfismos no llega a explotar exponencialmente) y por ello la complejidad queda controlada (cuasipolinómica de momento). ¿ Llegará a polinómica ?, se pregunta todo el mundo…En cuanto a los casos fáciles, no tengo claro la situación: o bien los casos fáciles son los que teniendo más grados de libertad es sencillo encontrar la diferencia entre los dos grafos o aunque tengan un grupo de automorfismos exponencial no hace falta explorar todo el grupo para determinar que son iguales. Ya digo que esto último no lo tengo claro.

Fin añadido. 

Some considerations has led us to stablish the following working hypothesis: the hard cases for the isomorphism problem over combinatorial structures represented in normal form are also those for which the automorphism group is two-generated.

And the desire to check this hypothesis has led us to study if the collineation groups of finite (desarguian) projective planes are two generated (this search has been inspired by the content of this thesis). In this post we plan to clarify or at least to collect links about this research.

Añadido posterior. El enlace anterior falla. La tesis citada es: Efficient algorithms for graph isomorphism testing (esperamos que este enlace supere la fuerte erosión de los próximos años) en la que el autor nos comenta sobre cuales son las familias de grafos más complicadas para cualquier algoritmo de GI. Fin añadido.

Projective planes.

Let´s first recall that the theory of projective planes is a subtheory of the theory of combinatorial designs. Also of interest. As we can see in the previous link there are many of those (although most if not all can be described by the triple SET, SUBSET, RESTRICTIONS OVER SUSETS), and in this post we will focus almost exclusively on the theory of finite projective spaces.

Good introductory preliminaries in the introduction of this, where they inform that standard references for finite geometries are:

–Dembowski´s Finite geometries,

–Beth, Jungnickel and Lenz´s Design Theory and,

–for projective planes Hughes and Piper´s  Design Theory.

In Projective planes PG(2, n), n is the order of the plane which has a number of points / planes shown to be equal to: n^2+n+1. In the Desarguian planes PG(2, q), which are the classical examples, q is a prime power and points and lines are the 1-and 2-dimensional subspaces of the vector space GF(q)^3, respectively and a point is incident with a line iff it is a subset of the line (a well known example is the Fano plane, the unique Desarguian plane of order 2, up to isomorphism). Though I´m looking for introductory papers, this kind of groups seems quite general so that most papers are quite specialized.

As every other field of mathematics, this one has central conjectures and theorems:

–A first important theorem, which situates projective spaces within the more general setting of combinatorial designs is the Dembowski-Wagner theorem (see this paper).

–When restricted to projective spaces, a first important negative theorem is the Bruck-Ryser theorem and,

–for construction purposes the theorem that relates latin squares with projective planes (see this paper).

Automorphism groups  of projective planes.

Of more interest for our purpose is the conjecture par excellence in this field,  the prime power order conjecture. Since all known projective planes with transitive collineation group are Desarguesian (that is of prime power order) it has been conjectured that all such planes are Desarguesian.

The most celebrated theorem, related with this conjecture, is the Ostrom-Wagner (see their conjoint paper “On projective and affine planes with transitive collineation groups”), theorem that asserts that the conjecture is true for projective planes with 2-transitive collineation groups (see the very interesting introduction in  this paper) if a finite projective plane admits a collineation group acting doubly transitively on points, then the plane is Desarguesian and the group contains the Projective Special Linear group (some kind of PSL groups where of interest for us in previous posts).

On the other hand, as far as I know, there is not yet any equivalent to Frucht theorem for projective planes, unfortunately: see this paper.

Other links / papers of interest I have found so far are:

The entry of Springer Encyclopediae of Mathematics about projective planes with information about the finite and desarguian cases.

A paper about projective spaces in general including finite projective spaces, with a proof of the fundamental theorem of projective spaces, and about projective planes (see also this other paper  by an author which has published intensively in the field of permutations groups).  These papers comes from a lecture notes book (see the presentation chapter  ) that can be accessed through this link.

–The web page of an active author in the field, Professor William M. Kantor which also has published in the field of GI, as coauthor of Babai. A clear signal that the thread of research we are following has been already explored. Some papers of this author: one, two, three, four, five, six, seven and eight.

 —Ho, Chat Yin(1-FL). On the order of a finite projective plane and its collineation group.
Finite geometries and combinatorial designs (Lincoln, NE, 1987), 299–301, Contemp. Math., 111, Amer. Math. Soc., Providence, RI, 1990. 51E15 (20B25)

http://www.uwyo.edu/moorhouse/pub/psl3q.pdf and from the same author http://www.uwyo.edu/moorhouse/pub/psl2q.pdf.

http://www.combinatorics.org/Volume_13/PDF/v13i1r94.pdf

After reading in diagonal all this papers I have not clear if the hypothesis stands or not (possibly not). So, to be continued.