HPC. El impacto de la patente US 8266089: lo que parecía imposible antes, ahora al alcance de la mano, sin esfuerzo.

Disclaimer. Esta entrada es la rerepublicación de una publicada en este mismo blog hace unos meses. Hemos eliminado algunas partes que ahora son irrelevantes.

1. Introducción.

Debido al retraso en la (eterna) tramitación de la segunda solicitud de patente (también la primera fue eterna) que por motivos completamente injustificados (como venimos demostrando en las anteriores entradas) finalmente se ha denegado (aunque como tenemos la razón de nuestra parte, insistiremos), hacía tiempo que no  miraba las publicaciones más actuales sobre el problema al que nuestro método proporciona una solución teórica y práctica general: la determinación de la existencia y búsqueda constructiva de recorridos hamiltonianos en Dígrafos de Cayley bigenerados.

Y con (grata, creo) sorpresa he visto que varios autores (en la entrada publico dos ejemplos, los dos de autores canadienses creo), utilizando técnicas de la patente, están resolviendo problemas que antes de nuestra publicación parecían imposibles. 

2. Los dos ejemplos:

Antes contestamos a una pregunta que seguramente se harán los lectores. ¿ Que demuestran estos  dos resultados ? Que pasos aislados de mi algoritmo son de utilidad para éste problema (que como vamos a ver tiene importantes aplicaciones industriales), por si solos, sin combinarlos con los demás y por lo tanto que tiene todo el sentido su inclusión en una solicitud de patente como reclamación independiente y que por ello, de acuerdo con la legislación vigente (incluso en un contexto post Alice Corp v. CLS Bank) ésta solicitud se debería de haber concedido. La no concesión ha sido completamente ilegitima.

Está muy claro en que consisten algunos de estos pasos para los que estoy pidiendo protección en la segunda solicitud de patente y yo no veo abstracción por ninguna parte:

–son partes (digamos subdigrafos). Nótese que éstas partes están perfectamente definidas, son tan concretas que se le puede dar instrucciones a un computador para que las maneje). Nótese que hay muchos otras partes de éstos mismos dígrafos, para las cuales no pedimos protección, pues son irrelevantes para el problema que nos interesa. s

–de una clase muy concreta de dígrafos. Hay muchas otras clases de dígrafos, incluso algunas bastante relacionadas y en las cuales se pueden definir los mismas partes, para las que no pedimos protección. 

–dígrafos que se utilizan para modelar determinadas aplicaciones industriales que se pueden incluir en el término redes. Hablamos de redes técnicas, redes dónde haya una participación de máquinas, de aparatos. 

–estas partes muy concretas de una clase muy concreta de dígrafos con unas aplicaciones muy concretas en el campo de las redes, pueden ser un IAS regular (claim 1 de la segunda solicitud de patente), uno o varios IASes del entorno de la identidad con disposición lisa o smooth (claim 3 de la segunda solicitud de patente), que pueden ser dos IASes regulares entrelazados (claim 4 de la segunda solicitud de patente), pueden ser dos o varios IASes regulares con entrelazamiento de ciclos (claim 5). Nótese que las claims 2 y 6 son algo diferentes, pues son más procedimentales que estructurales, no se refieren a partes sino a cosas que se hacen con esas partes.   

–se usan como piezas de una máquina para resolver un problema muy concreto: el problema de recorridos hamiltonianos. Este uso se puede ser de varias formas: bien para tomar varias decisiones sobre como resolver un problema muy concreto como es el (en cuyo caso se hace un uso de ellos como tests), bien directamente como piezas para resolver éste mismo problema. En esta entrada hemos mostrado a dos investigadores que han utilizado a algunas de ellas.  Nótese que muy posiblemente estas partes se puedan utilizar para resolver otros problemas (por ejemplo, sin duda ninguna, y nosotros ya lo hemos utilizado para ello, para resolver el problema de isomorfismo, también para resolver el problema del camino más corto etc…) en esta misma clase de dígrafos, pero no estamos reclamando su protección para ello. Nos estamos refiriendo a un problema muy concreto.    

En definitiva, estamos definiendo muy concretamente la materia prima (las partes de los dígrafos), estamos definiendo muy concretamente sus usos (como tests, como componentes, para resolver un problema muy concreto) y estamos definiendo  muy concretamente su campo de aplicaciones industriales (redes). ¿ Se puede ser más concreto ?

Quiero recordar que este problema (recorridos hamiltonianos) en éstos dígrafos (de Cayley; hay otros nombres) se llevan estudiando décadas, por  destacados investigadores (del campo de la matemática aplicada, pero sobre todo del campo de la ingeniería de redes) y nadie había detectado que éstas partes se podían utilizar de ésta manera para resolver éste problema. Estaban allí y nadie las había visto: por lo tanto hay novedad, no hay obviedad y hay inventiva, hay invención genuina.

También hay que recordar que no hablamos de objetos puramente matemáticos, abstractos: si los estudian ingenieros de redes, es por que es un objeto con importantes aplicaciones industriales. Ni siquiera  hablamos de meras propuestas técnicas, de prototipos: hablamos de objetos que se utilizan en sistemas reales comerciales.   

Finalmente, como ponen de manifiesto estos dos artículos, creo que está claro que antes de la existencia de estas técnicas que hemos inventado nosotros estos problemas eran prácticamente imposibles de resolver. Ahora, usándolas, los investigadores pueden resolver el problema para casos antes inaccesibles. Por lo tanto el uso de estas técnicas supone una mejora clara sobre el estado del arte.     

Todo esto se le ha explicado muy claramente al examinador en varias ocasiones, en conversación teléfonica y por escrito.  

Añadido. En el gráfico siguiente indicamos dónde se situarían los resultados de los que hablamos (por el nombre de los autores) de cuardo con nuestra teoría (ojo la asignación del resultado de Williams a la región indicada  es clara: a partir de un cierto n no muy grande sus casos son smooth; pero tengo pendiente de leer en detalle el artículo de Witte y por lo tanto la asignación de momento es hipotética). La estructura de la región twisted no está del todo clara todavía. Por ejemplo ¿ hay casos cycle-entangled con un número exponencial de IASes ?. Y hay otros interrogantes.

limite-supuesto-de-la-distribucin-1-7282

He modificado una figura que elaboré hace años, que ya hemos publicado en anteriores ocasiones y que tengo que revisar. Tampoco tengo claro que sea la más adecuada. Muestra, fijando Sn (una cantidad n!) la distribución de casos por grados (de las permutaciones). Si bien los casos de Williams sí generan Sn, no sucede lo  mismo con la familia infinita de Witte,  que muy posiblemente (no lo se todavía) serán de orden menor a n ! (tal y como veremos, incluye como subfamilia a metacíclicos, que son de orden bastante bajo).

Fin de añadido.

a) Primer resultado. 2013. David Witte. 

Título. On Cayley Digraphs That Do Not Have Hamiltonian Paths

Abstract.

We construct an infinite family of connected 2-generated Cayley digraphs that do not have hamiltonian paths, such that the orders of the generators and are unbounded. We also prove that if is any finite group with [[G,G]], then every connected Cayley digraph on has a hamiltonian path (but the conclusion does not always hold when or ). 

Extractos.

La primera familia (cuyo descubrimiento es seguramente anterior a mi resultado, pero se necesitó a todo un Milnor para obtenerlo…).

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=e. If |G|>= 9|ab^2|, then the Cayley digraph does not have a hamiltonian path.

La segunda familia, posterior a mi resultado.

The examples in the above proposition are very constrained, because the order of one generator must be exactly 2 and the order of the other generator must be exactly 3. In this note, we provide an infinite family of examples in which the orders of the generators are not restricted in this way. In fact, and can both be of arbitrarily large order.

Theorem 3. For any n elemento de N, there is a connected Cayley digraph, such that 

(1) The corresponding Cayley Digraph does not have a hamiltonian path,

(2) a and b both have order greater than n. Furthermore, if p is any prime number such p > 3 that and p es congruente con 3 (mod4), then we may construct the example so that the commutator subgroup of G has order p. More precisely, G=Zm*Zp is a semidirect product of two cyclic groups, so is metacyclic.

Remark 4. Here are some related open questions and other comments.

(1)The above results show that connected Cayley digraphs on solvable groups do not always have hamiltonian paths. On the other hand, it is an open question whether connected Cayley digraphs onnilpotent groups always have hamiltonian paths. (See [3] for recent results on the nilpotent case.)

(2)The above results always produce a digraph with an even number of vertices. Do there exist infinitely many connected Cayley digraphs of odd order that do not have hamiltonian paths?

(3)We conjecture that the assumption “p es congruente con 3 (mod 4)” can be eliminated from the statement of Theorem 3. On the other hand, it is necessary to require that p>3 (see Corollary 16).

(4)If is abelian, then it is easy to show that every connected Cayley digraph on has a hamiltonian path. However, some abelian Cayley digraphs do not have a hamiltonian cycle. See Section 5 for more discussion of this.

(5)The proof of Theorem 3 appears in Section 3, after some preliminaries in Section 2.

No recuerdo si reseñamos ya éste artículo en su momento o fue otro del mismo autor, y éste no lo conocía. Como se ha visto, en él que dan dos ejemplos de familias infinitas de Dígrafos de Cayley bigenerados que no tienen caminos hamiltonianos.

El autor utiliza el IAS regular y el resultado de los vértices finales posibles, dos técnicas que nosotros hemos intentado incluir como reclamaciones en la segunda solicitud de patente, pero que el examinador considera que son meras ideas abstractas, que se agotan en si mismas, sin ninguna consecuencia práctica de cara a las aplicaciones. ¿ No es el examinador consciente  del ahorro de trabajo computacional que se obtiene al poder determinar de antemano que un caso no tiene recorridos hamiltonianos ? Lo debería de ser porque se lo hemos intentado explicar por teléfono y en escritos (formales) en varias ocasiones. ¿ Entonces por qué rechaza éstas reclamaciones ? O no se ha enterado o se está haciendo el sueco, y ha denegado con una larga cambiada.

Alguien pensará que el resultado de los vértices finales posibles ya se había publicado, con otro método diferente al mio (más general y mucho más aparatoso cuando se trata de aplicarlo a los casos con IAS regular, de los que  no habla el autor, en mi modesta opinión;  y ojo soy admirador de éste investigador), por otro autor a principios de los 80. Es cierto, y ésto hace aceptable  la publicación de éste autor sin citarme incluso aunque conociese mi resultado, pero resulta que hasta después de mi publicación no lo había utilizado nadie para demostrar éste tipo de resultados. ¿ Por qué ? Resulta que sin mi teoría, y sin las definitivas pruebas que se obtienen al aplicarla a los (brillantes) resultados experimentales obtenidos por otroa autores (Effler y Ruskey) sin los otros pasos de la patente, el resultado de vértices finales posibles no va mucho más allá.

En fin tengo que mirar en detalle éste artículo. A priori interesante aunque conociendo mi método éste tipo de resultados ya no tiene mayor dificultad.  Ya se sabe dónde mirar para encontrar éste tipo de casos.

Actualización 1 de julio de 2015:

a) En éste artículo aparece la familia de Milnor. El resultado no está publicado, lo explica en un breve párrafo y no es mucho más informativo que lo que ya explica Witte. La motivación de Milnor fue encontrar un contra-ejemplo a una conjetura de Nijenhuis y Wilf.

b) Estoy leyendo el artículo de Witte. No puede ser más abstracto (en mi modesta opinión sin necesidad; cuando conoces el mecanismo, según la teoría de la patente, que en un caso es causa de no hamiltonicidad, sea de ciclos o de caminos, entiendo que no debe de ser difícil transformarlo en una condición algebraica cualquiera que se pueda expresar con el mumbo jumbo de la teoría de grupos; cierto, más difícil es identificar y demostrar que existe una familia infinita en la que se tiene que dar necesariamente éste mecanismo; entiendo que en este caso la familia consta de casos con IAS de orden pequeño y ordenes de los generadores grandes).  En la demostración del resultado principal utiliza la técnica de demostración de los IASes, distinguiendo 2 casos. Todavía no soy capaz de determinar a que tipo de digrafos pertenece su familia infinita (según la nomenclatura de la patente). Luego añade otros resultados también complicados de interpretar. En resumen un buen resultado.

Confirmado que lo reseñé en el blog en su momento (curiosamente lo encontré por casualidad nada más publicarse). Confirmado  también que se trata de una familia metacíclica (la otra ve lo capté antes; hace dos años estaba más entrenado; ahora había interpretado el enunciado de otra manera).  Ya no tengo tan claro que el orden del IAS se pequeño en relación al de los generadores.

Algunos datos que compilé hace días sobre los grupos metacíclicos (estaba preparando una entrada, pero lo publico aquí):

–Se llaman así porque su estructura es muy parecida a la de los cíclicos.

–su definición abstracta: A metacyclic group is a group G containing a normal cyclic subgroup A such that G/A is also cyclic.

–un ejemplo clásico: Perhaps the best known examples of metacyclic groups are the dihedral groups, D2n. In this case the cyclic subgroup has order n, and the quotient group has order 2.

–su presentación por generadores y relaciones.

In summary, the generators a and b of the metacyclic group G satisfy the following relations:

a^m = 1, b^−1ab = a^r , (r, m) = 1, b^s = a^t , m|t(r − 1), m|r^s − 1.

con m y s el orden de los generadores, y (r,m) mínimo divisor común. Para más detalles ver ésta tesis. He visto presentaciones más claras.

–Todos son bigenerables.

–Todos se pueden construir como producto semidirecto mxn (con m el orden de un generador y n el orden de otro.

Todos son de orden pequeño: <= n (n-1) con n el grado de la permutación.

–Algunos grupos conocidos que son metacíclicos son los dihédricos y los cuaternionicos generalizados. Nuestra entrada sobre los cuaternionicos.

Creo que hay un motivo que hace que los metacíclicos hayan sido de los Dígrafos de Cayley más estudiados: procedimiento de construcción al margen de tener generadores de tipo permutaciones, orden pequeño y estructura parecida a los abelianos. Todo esto hace que sus casos más pequeños sean más manejables manualmente (ya hemos comentado que se necesita un poco de información; y antes del estudio experimental Effler-Ruskey, no había mucha. Sin embargo diría que para el problema de recorridos hamiltonianos son de los complicados  ya que todos deben de ser bastante entrelazados. Todo esto les añade más mérito a todas éstas investigaciones. Pero por ello también es posible que los investigadores se llevasen una falsa impresión sobre la dificultad del problema. Ahora sabemos…¡¡ que la mayoría son sencillos !!.

c) Un libro dónde aparecen algunos generadores de tipo permutación para grupos pequeños (aunque no comprendo muy bien su descripción): An introduction to groups. A  computer illuestrated text.

Fin de actualización.

b) Segundo resultado. 2013. Aaron Williams.

Título.  HAMILTONICITY OF THE CAYLEY DIGRAPH ON THE SYMMETRIC GROUP GENERATED BY σ = (1 2 ··· n) AND τ = (1 2)

Abstract. The symmetric group is generated by σ = (1 2 ··· n) and τ = (1 2). We answer an open problem of Nijenhuis and Wilf by constructing a Hamilton path in the directed Cayley graph for all n, and a Hamilton cycle for odd n.

Aunque todavía lo tengo que leer en detalle, para obtener éste resultado utiliza (conjuntamente con otras técnicas) cuando menos lo que nosotros hemos llamado el IAS regular (él lo llama de otra manera: alternating-cycle) y que hemos intentado proteger en una reclamación de la solicitud, rechazada ya que el examinador de la USPTO considera que éste método, a todas luces práctico y con consecuencias, es una idea abstracta sin mayor incidencia práctica en las aplicaciones. 

Si algún lector considera que las aplicaciones en matemáticas no dejan de ser ideas abstractas hay más. Además de las aplicaciones que éste artículo demuestra, éste tipo de dígrafos y dentro de ellos el enrutamiento mediante recorridos hamiltonianos, tiene importantes aplicaciones industriales. Entran dentro de lo que se llaman Rotator Graphs que se utilizan como  modelos de redes de interconexión, modelos que ha desarrollado un investigador de IBM. ¿ Por qué el examinador no ha querido valorar ésto si en la redacción de  las reclamaciones hacíamos referencia explícita a las redes de interconexión modeladas por Dígrafos de Cayley ? ¿ Se puede ser más concreto ?. Y eso que como estamos viendo en las últimas entradas nuestro método va más allá de los Dígrafos de Cayley. 

El citado no es el único investigador industrial  que ha investigado sobre Grafos de Cayley, ni mucho menos. Podría citar a cientos. Un caso reciente, Alexander Holroyd, de Microsoft research, coautor del autor sobre el que hablamos de un artículo titulado: Efficient generation of hamilton cycles in restricted and generalized Rotator Graphs, es decir una clase de Dígrafos de Cayley.  O podríamos citar a otro ¿ investigador ? de IBM, Ian Shields que ha publicado una destacad tesis sobre el problema (previa a la publicación de nuestro resultado. Y podriamos citar a otros cientos.

Extracto.

3.1. Basic Cycles. We first show that walks associated with σ n and (τσ−1 ) n−1 are (directed) cycles, which we refer to as σ-cycles and alternating-cycles, respectively.

Lemma 1. If p = p1···pn ∈ Pn , then walk(pσ n) and walk(p(τσ−1 ) n−1 ) are cycles.

Luego continua con la demostración. La tengo que leer pero en principio entiendo que está demostrando matemáticamente uno de los pasos de mi método (no sé si específicamente para el tipo de dígrafos; en realidad se puede demostrar que ésto es así para todos los no  commutativos). Seguramente habrá más de ésto en el futuro. Por ejemplo estoy a la  espera de ver al primero que publique, sin citarme, una demostración de la generalización del famoso teorema de Rankin que yo he publicado en mi patente, con demostración completa. Otras demostraciones no las he publicado por no estar relacionadas con métodos constructivos y por lo tanto no  tener sentido en una patente. También estoy a la espera de la publicación del importantísimo test de lisura o smoothness y sus consecuencias de cara a la propiedad de hamiltonicidad.

En nuestra descripción del método incluido en la solicitud ya decíamos que nuestro método se podía utilizar para resolver determinados problemas abiertos en relación a éste problema y entre otros nos referíamos a éste. Aplicando nuestra teoría es fácil ver que a partir de un cierto tamaño, por ser smooth, todos los Dígrafos de Cayley Bigenerados de tipo Sigma Tau tiene recorridos hamiltonianos en todos los vértices finales posibles.  Con nuestro método se pueden construir demanera eficiente todos los recorridos posibles en todos éstos vértices finales posibles (añadido 30 de junio. obviamente teniendo en cuenta el teorema de Rankin para ciclos y caminos cuando éste sea aplicable. fin de añadido).

Éste es el estado del arte hoy, tras la publicación de nuestro resultado, y éste era hace años. Se puede ver también éste otro artículo (en el que atacan  un problema de una clase similar):

Doubly adjacent gray codes for the symmetric group

ABSTRACT Let x 1 x 2…xi xi+1 …xn be a permutation of {1,2,…,n} written in one line notation. An “i-adjacent interchange” applied to this permutation produces the permutation x 1 x 2…xi+1 xi …xn obtained from the first permutation by interchanging the symbols in positions i and i+1. We denote such an interchange by (i,i+1), where i=1,…,n−1. The permutation x 1 x 2…xi+1 xi …xn results from x 1 x 2…xi xi+1 …xn by right multiplication by the transposition (i,i+1) in the symmetric group Sn . Two adjacent transpositions (i,i+1) and (j,j+1) are themselves adjacent if either i=j+1 or j=i+1. In this paper, we show that that for every n≥3, there is an n long sequence (f(1),f(1)+1),…,(f(n!),f(n!)+1) of adjacent transpositions, each except the first adjacent to its predecessor, the first adjacent to the last, and such that the set of products of transpositions {πt:πt=(f(1),f(1)+1)…(f(t),f(t)+1)t=1,…,n!} is Sn , with the final product πn equal to the identity. We call such a sequence of transpositions a doubly adjacent Gray code for the symmetric group Sn . We give a procedure for constructing such a Gray code. The existence of such a code (Theorem 6.2) seems to be a very nontrivial problem. As a consequence of the existence of this code we resolve an open problem in the theory of Cayley graphs of the symmetric group by showing that the Cayley graph of Sn with generators {(l,2),(l,…,n),(n,…,l)} has a Hamiltonian cyclen≥3 (Corollary 6.5). Our procedure shows how to braid n strands.

50  páginas de demostración para obtener lo que con nuestro método se puede obtener dándole a una tecla.

2. No se que pensar de todo ésto.

Aunque por determinados motivos que no vamos a detallar nos sorprendería que fuese así, no tenemos pruebas de que ninguno de éstos dos autores conozcan nuestro resultado y por ello dejamos el tema aquí.

Pero queremos pensar que la ética académica obliga a todo académico, sea del país que sea, a informarse primero de todo lo publicado en su campo y reseñarlo si tiene conocimiento, independientemente de quién y cómo se haya publicado.  ¿ Somos científicos o sólo un grupo de vanidosos y elitistas amiguetes ?. ¿ Somos civilizados o preferimos que el sector de conocimiento, la academia global que está emergiendo sea una jungla ?

No es complicado llegar al texto de  mi patente: aparece en cualquier búsqueda Google y está en inglés. Yo me la encuentro continuamente cuando busco sobre éstos temas. Por mi parte puedo admitir que haya partes no del todo claras y quedo a la disposición de cualquier autor para aclarar dudas.

De cualquier manera, sin acritud (tampoco es ésta mi guerra), les felicitamos por sus resultados. Nos alegra ver que hay avances en éste difícil campo.

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

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

Logo de WordPress.com

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

Imagen de Twitter

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

Foto de Facebook

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

Google+ photo

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

Conectando a %s


A %d blogueros les gusta esto: