Orientador: Sueli Irene Rodrigues Costa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-10T10:56:09Z (GMT). No. of bitstreams: 1 Strapasson_JoaoEloir_D.pdf: 1100322 bytes, checksum: 054aeab4b36f30144155ce6b1668659a (MD5) Previous issue date: 2007 / Resumo: Este trabalho está dividido em duas partes. A primeira e dedicada ao problema de encontrar o menor vetor não nulo de um reticulado. Este é um problema de alta complexidade computacional e que tem grande interesse tanto para a Teoria dos Códigos, como para diversas outras áreas. Esse mínimo está associado a performance do reticulado em termos da codificação: quanto maior for a razão entre este mínimo e o determinante do reticulado, melhor e a distribuição dos pontos no espaço (alta densidade de empacotamento). Nesta tese demos ênfase ao caso especial dos reticulados obtidos por uma projeção ortogonal do reticulado n-dimensional dos inteiros na direção de seus elementos. Tais reticulados estão associados ao problema de codificação contínua fonte/canal. Mostramos nos casos tri e quadridimensionais em que condições podemos garantir reticulados bons, ou seja, com alta densidade de empacotamento. Neste processo foram também construídos dois novos algoritmos, um para cálculo da base de Minkowski de um reticulado e outro específico para a busca da norma mínima do reticulado-projeção. Na segunda parte trabalhamos com grafos em toros planares que são quocientes de reticulados, os quais são isomorfos a grafos circulantes. Estabelecemos a conexão entre estes códigos esféricos rotulados por grupos cíclicos e códigos perfeitos na métrica de Lee. A partir de tal associação foram também obtidos resultados sobre o gênero 1 e a determinação do dos gênero de uma classe especial de grafos circulantes que tem número arbitrariamente grande de conexões (grau) / Abstract: The research developed here is related and inspired by problems in coding theory. It is presented in two parts. In the first we focus on the search for the minimum nonvanishing vector of a lattice, specially in the case of a projection of the ndimensional integer lattice in the direction of one of its vectors. This is a problem of high computational complexity which is related to the search for efficient joint sourcechannel continuous coding. In the second part we deal with flat torus graphs generated by a quotient of lattices and which are labeled by a a cyclic group of isometries. We show that any circulant graph is isomorphic to one of these graphs and hence associated to a spherical code. Through these isomorphism a complete classification of circulant graphs of genus one and the genus of an arbitrarily high order class of circulant graphs is obtained. / Doutorado / Geometria Topologia / Doutor em Matemática

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work we study the critical properties of the spin-1 Blume-Capel model in two dimensions on Voronoi- Delaunay random lattices with quenched connectivity disorder. The system is treated by applying Monte Carlo simulations using the heat-bath update algorithm together with single histograms re-weighting tech- niques. We calculate the critical temperature as well as the critical exponents as a function of the crystal field -. It is found that this disordered system exhibits phase transitions of first- and second-order types that de- pend on the value of the crystal field. For values of - ≤ 3, where the nearest-neighbor exchange interaction J has been set to unity, the disordered system presents a second-order phase transition. The results suggest that the corresponding exponents ratio belong to the same universality class as the regular two-dimensional ferromagnetic model. There exists a tricritical point close to -t = 3:05(4) with different critical exponents. For -t ≤ - < 3:4 this model undergoes a first-order phase transition. Finally, for - ≥ 3:4 the system is always in the paramagnetic phase. / Neste trabalho estudamos as propriedades críticas do modelo Blume-Capel spin-1 em redes aleatórias de Voronoi-Delaunay em duas dimensões com desordem temperada nas conectividades. O sistema é tratado pela aplicação de simulações de Monte Carlo usando o algoritmo de banho térmico de atualização em con- junto com a técnica de repesagem do histograma simples. Nós calculamos a temperatura crítica bem como os expoentes críticos como função do campo cristalino -. Verificou-se que este sistema desordenado exibe transições de fases do tipo primeira e segunda ordem que dependem do valor do campo cristalino. Para valores de - ≤ 3, onde a interação de troca de primeiros vizinhos J foi definida como unidade, o sistema desordenado apresenta uma transição de fase de segunda ordem. Os resultados sugerem que a correspon- dente relação dos expoentes pertencem à mesma classe de universalidade como o modelo ferromagnético bidimensional regular. Existe um ponto tricrítico próximo de -t = 3:05(4) com diferentes expoentes críti- cos . Para -t ≤ - < 3:4 este modelo mostra uma transição de fase de primeira ordem. Finalmente, para - ≥ 3:4 o sistema é sempre na fase paramagnética. / São Cristóvão, SE

Made available in DSpace on 2014-10-09T12:49:06Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T14:06:38Z (GMT). No. of bitstreams: 1 09670.pdf: 10232628 bytes, checksum: 1590f43108c1cbc7b2065202eea72fa8 (MD5) / Dissertacao (Mestrado) / IPEN/D / Instituto de Pesquisas Energeticas e Nucleares - IPEN/CNEN-SP

A Análise de Conceitos Formais (FCA) é uma teoria matemática que formaliza a noção de conceitos e hierarquias conceituais. De importância central a esta teoria é uma estrutura algébrica denominada reticulado de conceitos. Esta estrutura é definida em função de um conjunto de objetos, outro de atributos e uma relação que indica os atributos apresentados por cada objeto. Uma representação gráfica de um reticulado de conceitos, por meio de uma interface computacional, é capaz de expor regularidades presentes em dados a um usuário, e este pode então realizar tarefas de análise exploratória de dados. Este tipo de aplicação de FCA vem sendo empregado em dezenas de projetos pertencentes a áreas diversas, como medicina, serviços de inteligência, engenharia de software e bioinformática. Mostramos neste trabalho um sistema de análise exploratória de dados baseado em FCA, e sua utilização sobre dados reais. Também é mostrado como reticulados de conceitos podem ser empregados em interfaces de recuperação de informação. Do ponto de vista algorítmico, analisamos métodos computacionais para a determinação do reticulado de conceitos, e também de uma subestrutura simplificada, o conjunto de conceitos. O tamanho de um reticulado de conceitos pode ser exponencial em função dos tamanhos dos conjuntos de objetos e de atributos. Assim, é de vital interesse o estabelecimento de cotas superiores para o número de conceitos de um reticulado. Neste trabalho, apresentamos as cotas já conhecidas presentes na literatura. Também estabelecemos uma nova cota superior, e mostramos famílias de casos em que nossa cota superior é mais justa que as demais. Para algumas famílias particulares, nossa cota é polinomial, enquanto que as demais são exponenciais. / Formal Concept Analysis (FCA) is a mathematical theory that formalizes the notion of concepts and conceptual hierarchies. Of central importance to this theory is an algebraic structure termed concept lattice. Such structure becomes defined after being given one set of objects, one of attributes, and an incidence relation describing the attributes held by each object. A graphical representation of a concept lattice, by means of a computational interface, is capable of unfolding regularities present in data to an user, who is then able to conduct exploratory data analysis tasks. This sort of FCA application is currently deployed in tens of projects belonging to a wide range of areas, such as medicine, intelligence services, software engineering and bioinformatics. We show in this work an FCA-based system of exploratory data analysis, and its use over real data. Moreover, it is shown how concept lattices can be employed in information retrieval interfaces. From the algorithmic viewpoint, we analyse computational methods for the determination of a concept lattice, and also of a simplified substructure, the concept set. The size of a concept lattice can be exponential when compared to the size of the objects and the attributes sets. Therefore, it is of paramount interest the establishment of upper bounds for the number of concepts of a lattice. In this work, we present the upper bounds already known in the literature. We also establish a new upper bound, and show families of cases in which our bound is sharper than the others. For particular families, our bound is polynomial, whereas the other bounds are exponential.

Neste trabalho, apresentamos estudos sobre o magnetotransporte em um sistema de bicamadas com uma rede de antipontos triangulares em campos magnéticos baixos sob a aplicação de campos elétricos externos, que são produzidos por voltagens de porta. A bicamada é feita em poços quânticos largos (wide quantum well) de alta densidade eletrônica, formado em heteroestruturas semicondutoras de AlxGa1xAs=GaAs. Oscila- ções magneto-inter-sub-banda (MIS) são observadas em poços quânticos largos de alta densidade eletrônica com duas sub-bandas ocupadas. Estas são originadas pelo espalhamento inter-sub-bandas e tem um máximo para campos magnéticos B que satisfazem a condição de alinhamento entre os leques dos níveis de Landau de cada sub-banda. Oscila- ções de comensurabilidade são observadas na magnetoresistência que é sensível ao arranjo do potencial dos antipontos. A aplicação de campos elétricos faz diminuir o número de oscilações na magnetoresistência para campos magnéticos compreendidos entre 0; 1T e 0; 4T, observando-se uma transição das oscilações MIS aos efeitos de comensurabilidade. Aplicando voltagens de porta podemos variar a amplitude do potencial dos antipontos. / In this work, we present studying about magnetotransport in a bilayer system with triangular antidot lattices in low magnetic elds under the application of external electric eld. The bilayer forms inside a wide quantum well of high electron density in semiconductor heterostructures formed by AlxGa1xAs=GaAs. Magneto-inter-subband (MIS) oscillations are observed in a wide quantum wells of high electron density with two subbands occupied, and they are caused by intersubband scattering and have a maximum for a magnetic eld B that satises the alignment condition between the staircase of Landau level. Commensurability oscillations are observed in magnetoresistance, which is sensitive to the potential of antidot arrangements. The application of electric elds decrease the number of oscillations in the magnetoresistance for magnetic elds between 0; 1T and 0:4T, showing a transition of MIS oscillations to commensurability oscillations. We varied the amplitude of the potential of the antidots applying dierent gate voltages.

We show that, for any tubular algebra, the lattice of pp-definable subgroups of the direct sum of all indecomposable pure-injective modules of slope r has m-dimension 2 if r is rational, and undefined breadth if r is irrational- and hence that there are no superdecomposable pure-injectives of rational slope, but there are superdecomposable pure-injectives of irrational slope, if the underlying field is countable.We determine the pure-injective hull of every direct sum string module over a string algebra. If A is a domestic string algebra such that the width of the lattice of pp-formulas has defined breadth, then classify "almost all" of the pure-injective indecomposable A-modules.

Dans cette thèse, nous étudions des problèmes de minimisation d'énergies discrètes et nous cherchons à comprendre pourquoi une structure périodique peut être un minimiseur pour une énergie d'interaction, c'est ce que l'on appelle un problème de cristallisation. Après avoir montré qu'un réseau de R^d soumis à un certain potentiel paramétré peut être vu comme un minimum local, nous démontrons des résultats d'optimalité du réseau triangulaire parmi les réseaux de Bravais du plan pour certaines énergies par point, avec ou sans densité fixée. Finalement, nous démontrons, à partir des travaux de Sandier et Serfaty sur les gaz de Coulomb bidimensionnels, la conjecture de Rakhmanov-Saff-Zhou, c'est-à-dire l'existence d'un terme d'ordre n dans le développement asymptotique de l'énergie logarithmique optimale pour n points sur la sphère unité de R^3. De plus, nous montrons l'équivalence entre la conjecture de Brauchart-Hardin-Saff portant sur la valeur de ce terme d'ordre n et celle de Sandier-Serfaty sur l'optimalité du réseau triangulaire pour une énergie coulombienne renormalisée / In this thesis, we study minimization problems for discrete energies and we search to understand why a periodic structure can be a minimizer for an interaction energy, that is called a crystallization problem. After showing that a given Bravais lattice of R^d submitted to some parametrized potential can be viewed as a local minimum, we prove that the triangular lattice is optimal, among Bravais lattices of R^2, for some energies per point, with or without a fixed density. Finally, we prove, from Sandier and Serfaty works about 2D Coulomb gases, Rakhmanov-Saff-Zhou conjecture, that is to say the existence of a term of order n in the asymptotic expansion of the optimal logarithmic energy for n points on the 2-sphere. Furthermore, we show the equivalence between Brauchart-Hardin-Saff conjecture about the value of this term of order n and Sandier-Serfaty conjecture about the optimality of triangular lattice for a coulombian renormalized energy

Deux méthodes de construction de représentations de groupes sont présentées. La première propose une stratégie essayant de déterminer les représentations de groupes libres de type fini à valeurs dans tout réseau de groupes de Lie réel. La seconde, après avoir revu une construction d'une surface hyperbolique complexe, c'est-à-dire le quotient du plan hyperbolique complexe par un réseau, et examiné soigneusement ses propriétés, produit une infinité de représentations non-conjuguées, à valeurs dans un réseau du groupe des isométries du plan hyperbolique complexe, de groupes fondamentaux de variétés hyperboliques fermées de dimension 3, obtenues comme des fibrés en surfaces sur le cercle. / Two construction methods of group representations are presented. The first one proposes a strategy to try to determine the representations of finitely generated free groups into any lattice in real Lie groups. The second, after reviewing a construction of a complex hyperbolic surface, that is the quotient of the complex hyperbolic plane by a lattice, and examining its properties carefully, yields infinitely many non-conjugate representations into a lattice in the group of isometries of the complex hyperbolic plane, of fundamental groups of closed hyperbolic 3-dimensional manifolds, obtained as surface bundles over the circle.

Le chiffrement à base de réseaux euclidiens a connu un grand essor durant les vingt dernières années. Autant grâce à l’apparition de nouvelles primitives telles que le chiffrement complètement homomorphe, que grâce à l’amélioration des primitives existantes, comme le chiffrement á clef publique ou les signatures digitales, qui commencent désormais à rivaliser avec leurs homologues fondés sur la théorie des nombres. Cela dit les preuves à divulgation nulle de connaissance, bien qu’elles représentent un des piliers des protocols de confidentialité, n’ont pas autant progressé, que ce soit au niveau de leur expressivité que de leur efficacité. Cette thèse s’attelle dans un premier temps à améliorer l’état de l’art en matière de preuves à divulgation nulle de connaissance. Nous construisons une preuve d’appartenance à un sous ensemble dont la taille est indépendante de l’ensemble en question. Nous construisons de même une preuve de connaissance amortie qui est plus efficace et plus simple que toutes les constructions qui la précèdent. Notre second propos est d’utiliser ces preuves à divulgation nulle de connaissance pour construire de nouvelles primitives cryptographiques. Nous concevons une signature de groupe dont la taille est indépendante du groupe en question, ainsi qu’un schéma de vote électronique hautement efficace, y compris pour des élections à grand échelle. / Lattice based cryptography has developed greatly in the last two decades, both with new and stimulating results such as fully-homomorphic encryption, and with great progress in the efficiency of existing cryptographic primitives like encryption and signatures which are becoming competitive with their number theoretic counterparts. On the other hand, even though they are a crucial part of many privacy-based protocols, zero-knowledge proofs of knowledge are still lagging behind in expressiveness and efficiency. The first goal of this thesis is to improve the quality of lattice-based proofs of knowledge. We construct new zero-knowledge proofs of knowledge such as a subset membership proof with size independent of the subset. We also work towards making zero-knowledge proofs more practical, by introducing a new amortized proof of knowledge that subsumes all previous results. Our second objective will be to use the proofs of knowledge we designed to construct novel and efficient cryptographic primitives. We build a group signature whose size does not depend on the size of the group, as well as a practical and highly scalable lattice-based e-voting scheme.

The work presented in this dissertation concerns dynamics of Rydberg atom lattices in the presence of noise and dissipation. Rydberg atoms possess a number of exaggerated properties, such as a strong van der Waals interaction. The interplay of that interaction, coherent driving and decoherence leads to intriguing non-equilibrium phenomena. Here, we study the non-equilibrium physics of driven atom lattices in the presence of decoherence caused by either laser phase noise or strong decay. In the first case, we compare between global and local noise and explore their effect on the number of excitations and the full counting statistics. We find that both types of noise give rise to a characteristic distribution of the Rydberg excitation number. The main method employed is the Langevin equation but for the sake of efficiency in certain regimes, we use a Markovian master equation and Monte Carlo rate equations, respectively. In the second case, we consider dissipative systems with more general power-law interactions. We determine the phase diagram in the steady state and analyse its generation dynamics using Monte Carlo rate equations. In contrast to nearest-neighbour models, there is no transition to long-range-ordered phases for realistic interactions and resonant driving. Yet, for finite laser detunings, we show that Rydberg atom lattices can undergo a dissipative phase transition to a long-range-ordered antiferromagnetic phase. We identify the advantages of Monte Carlo rate equations over mean field predictions. Having studied the dynamics of Rydberg atom lattices, we study an application of the strong interactions in such systems for quantum information processing. We investigate the coherent exchange of a single photon between a superconducting microwave cavity and a lattice of strongly interacting Rydberg atoms in the presence of local electric field fluctuations plaguing the cavity surface. We show that despite the increased sensitivity of Rydberg states to electric fields, as compared to ground state atoms, the Rydberg dipole-dipole interaction can be used to protect the system against the dephasing induced by the local noise. Using $1/f$ and laser phase noise models, we show that compared to the case with non-interacting atoms, our system exhibits longer coherence lifetimes and larger retrieval efficiency of the photon after storing into the atoms.