Thirty years ago, Effros and Shen classified the simple dimension groups with rank two. Every such group is parametrized by an irrational number, and can be constructed as an inductive limit using that number's continued fraction expansion. There is a natural generalization of continued fractions to higher dimensions, and this invites the following question: What dimension groups correspond to multidimensional continued fractions? We describe this class of groups and show how some properties of a continued fraction are reflected in the structure of its dimension group. We also consider a related issue: an Effros-Shen group has been shown to arise in a natural way from the tail equivalence relation on a certain sequence space. We describe a more general class of sequence spaces to which this construction can be applied to obtain other dimension groups, including dimension groups corresponding to multidimensional continued fractions.

Thirty years ago, Effros and Shen classified the simple dimension groups with rank two. Every such group is parametrized by an irrational number, and can be constructed as an inductive limit using that number's continued fraction expansion. There is a natural generalization of continued fractions to higher dimensions, and this invites the following question: What dimension groups correspond to multidimensional continued fractions? We describe this class of groups and show how some properties of a continued fraction are reflected in the structure of its dimension group. We also consider a related issue: an Effros-Shen group has been shown to arise in a natural way from the tail equivalence relation on a certain sequence space. We describe a more general class of sequence spaces to which this construction can be applied to obtain other dimension groups, including dimension groups corresponding to multidimensional continued fractions.

Submitted by ANA KARLA PEREIRA RODRIGUES (anakarla_@hotmail.com) on 2017-08-29T14:23:53Z No. of bitstreams: 1 arquivototal.pdf: 1435272 bytes, checksum: c4761d1ead518c5fc147deba16a17059 (MD5) / Approved for entry into archive by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2017-08-29T15:43:00Z (GMT) No. of bitstreams: 1 arquivototal.pdf: 1435272 bytes, checksum: c4761d1ead518c5fc147deba16a17059 (MD5) / Made available in DSpace on 2017-08-29T15:43:01Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1435272 bytes, checksum: c4761d1ead518c5fc147deba16a17059 (MD5) Previous issue date: 2015-08-20 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The familyofmetallicmeanswasintroducedbytheArgentinemathematicsVera Spinadel, in1994.Themetallicmeansareunknown,exceptfortheGoldenMean. However,othermetallicmeansalsohavepropertiesandimportantapplications.The ContinuedFractionsenableanotherwaytorepresentthesenumbers,whichareir- rational. / A famíliadosnúmerosmetálicosfoiintroduzidapelamatemáticaargentinaVera de Spinadel,em 1994. OsNúmerosMetálicossãopoucoconhecidos,comexceçãodo Número deOuro.Porém,outrosnúmerosmetálicostambémpossuempropriedades e aplicaçõesimportantes.AsFraçõesContínuaspossibilitamumaoutramaneirade representaressesnúmeros,quesãoirracionais.

Actuellement, nous vivons dans une société numérique. L'avènement de l'Internet et l'arrivée du multimédia et des supports de stockage numériques, ont transformé profondément la façon dont nous communiquons. L'image en particulier occupe une place très importante dans la communication interpersonnelle moderne. Toutefois, elle présente l'inconvénient d'être représentée par une quantité d'information très importante. De ce fait, la transmission et le stockage des images soulèvent certains problèmes qui sont liés essentiellement à la sécurité et à la compression d'images. Ce sont ces considérations qui ont guidé cette thèse. En effet, la problématique que nous posons dans cette thèse est de proposer une solution conduisant à la crypto-compression d'images afin d'assurer un archivage et un transfert sécurisés tout en conservant les performances de la méthode de compression utilisée. En effet, nos travaux de recherche ont porté essentiellement sur la compression et le cryptage des images numériques. Concernant la compression, nous avons porté un intérêt particulier au codage arithmétique vu sont efficacité en terme de ta ux de compression et son utilisation par les nouvelles normes et standards de compression tel que JPEG2000, JBIG, JBIG2 et H.264/AVC. Quant au cryptage, nous avons opté pour l'utilisation du chaos combiné avec les fractions continues afin de générer des flux de clés ayant à la fois de bonnes propriétés cryptographiques et statistiques. Ainsi, nous avons proposé deux nouvelles méthodes de compression sans perte basées sur le codage arithmétique tout en introduisant de nouveaux paramètres de codage afin de réduire davantage la taille en bits des images compressées. Deux autres méthodes s'appuient sur l'utilisation du chaos et des fractions continues pour le développement d'un générateur de nombres pseudo-aléatoires et le cryptage par flot d'images. Enfin, nous proposons une nouvelle méthode qui emploie conjointement le cryptage avec la compression. Cette dernière méthode se base sur l'échange des sous-intervalles associés aux symboles d'un codeur arit hmétique binaire de façon aléatoire tout en exploitant notre générateur de nombres pseudo-aléatoire. Elle est efficace, sécurisée et conserve le taux de compression obtenu par le codage arithmétique et ceci quelque soit le modèle statistique employé : statique ou adaptatif. / Actually, we live in a digital society. The proliferation of the Internet and the rapid progress in information technology on multimedia, have profoundly transformed the way we communicate. An enormous amount of media can be easily exchanged through the Internet and other communication networks. Digital image in particular occupies an important place in modern interpersonal communication. However, image data have special features such as bulk capacity. Thus, image security and compression issues have became exceptionally acute. It is these considerations that have guided this thesis. Thus, we propose throw this thesis to incorporating security requirements in the data compression system to ensure reasonable security without downgrading the compression performance.For lossless image compression, we have paid most attention to the arithmetic coding (AC) which has been widely used as an efficient compression algorithm in the new standards including JBIG, JBIG2, JPEG2000 and H.264/AVC. For image encryption, we are based on the combination of a chaotic system and the Engel continued fraction map to generate key-stream with both good chaotic and statistical properties. First, we have proposed two new schemes for lossless image compression based on adding new pre-treatment steps and on proposing new modeling methods to estimate probabilities for AC. Experimental results demonstrate that the proposed schemes give mean compression ratios that are significantly higher than those by the conventional AC. In addition, we have proposed a new pseudo-random bit generator (PRBG). The detailed analysis done by NIST statistical test Suite demonstrates that the proposed PRGB is suitable for cryptography. The proposed PRBG is used to develop a new symmetr ic stream cipher for image encryption. Theoretic and numerical simulation analyses indicate that our image encryption algorithm is efficient and satisfies high security. Finally, we have proposed a new scheme which performs both lossless compression and encryption of image. The lossless compression is based on the binary AC (BAC) and the encryption is based on the proposed PRBG. The numerical simulation analysis indicates that the proposed compression and encryption scheme satisfies highly security with no loss of the BAC compression efficiency.

In this dissertation we study graph directed Markov systems (GDMS) and limit sets associated with these systems. Given a GDMS S, by the Hausdorff dimension spectrum of S we mean the set of all positive real numbers which are the Hausdorff dimension of the limit set generated by a subsystem of S. We say that S has full Hausdorff dimension spectrum (full HD spectrum), if the dimension spectrum is the interval [0, h], where h is the Hausdorff dimension of the limit set of S. We give necessary conditions for a finitely primitive conformal GDMS to have full HD spectrum. A GDMS is said to be regular if the Hausdorff dimension of its limit set is also the zero of the topological pressure function. We show that every number in the Hausdorff dimension spectrum is the Hausdorff dimension of a regular subsystem. In the particular case of a conformal iterated function system we show that the Hausdorff dimension spectrum is compact. We introduce several new systems: the nearest integer GDMS, the Gauss-like continued fraction system, and the Renyi-like continued fraction system. We prove that these systems have full HD spectrum. A special attention is given to the backward continued fraction system that we introduce and we prove that it has full HD spectrum. This system turns out to be a parabolic iterated function system and this makes the analysis more involved. Several examples have been constructed in the past of systems not having full HD spectrum. We give an example of such a system whose limit set has positive Lebesgue measure.

In this thesis we present and solve selected problems arising from digital geometry and combinatorics on words. We consider digital straight lines and, equivalently, upper mechanical words with positive irrational slopes a<1 and intercept 0. We formulate a continued fraction (CF) based description of their run-hierarchical structure. Paper I gives a theoretical basis for the CF-description of digital lines. We define for each irrational positive slope less than 1 a sequence of digitization parameters which fully specifies the run-hierarchical construction. In Paper II we use the digitization parameters in order to get a description of runs using only integers. We show that the CF-elements of the slopes contain the complete information about the run-hierarchical structure of the line. The index jump function introduced by the author indicates for each positive integer k the index of the CF-element which determines the shape of the digitization runs on level k. In Paper III we present the results for upper mechanical words and compare our CF-based formula with two well-known methods, one of which was formulated by Johann III Bernoulli and proven by Markov, while the second one is known as the standard sequences method. Due to the special treatment of some CF-elements equal to 1 (essential 1's in Paper IV), our method is currently the only one which reflects the run-hierarchical structure of upper mechanical words by analogy to digital lines. In Paper IV we define two equivalence relations on the set of all digital lines with positive irrational slopes a<1. One of them groups into classes all the lines with the same run length on all digitization levels, the second one groups the lines according to the run construction in terms of long and short runs on all levels. We analyse the equivalence classes with respect to minimal and maximal elements. In Paper V we take another look at the equivalence relation defined by run construction, this time independently of the context, which makes the results more general. In Paper VI we define a run-construction encoding operator, by analogy with the well-known run-length encoding operator. We formulate and present a proof of a fixed-point theorem for Sturmian words. We show that in each equivalence class under the relation based on run length on all digitization levels (as defined in Paper IV), there exists exactly one fixed point of the run-construction encoding operator.

This report explores the effect of interactive visualizations on the advancement of mathematics understanding. Not only do interactive visualizations aid mathematicians to expand the body of knowledge of mathematics but it also allows students an efficient way to process the information taught in schools. There are many concepts in mathematics that utilize interactive visualizations and examples of such concepts are illustrated within this report. / text

Abstract This dissertation consists of four articles on irrationality measures. In the first paper we derive explicit irrationality measures by using the simple continued fraction expansions in a completely new way. In the second and third articles we use Padé approximations to construct irrationality measures. In the second paper we obtain an explicit irrationality measure for the values of q-exponential series, for which the earlier corresponding results are not as explicit. Furthermore, we construct a restricted irrationality measure for the values of q-exponential series, which is an improvement on the earlier results in the restricted case. In the third article we derive the best possible asymptotic restricted irrationality exponent for the values of Jacobi's triple product. In the last paper we consider Cantor series. We generalize the earlier results by deriving Sondow's irrationality measure for some Cantor series. / Tiivistelmä Tämä väitöskirja koostuu neljästä artikkelista, jotka kaikki käsittelevät irrationaalisuusmittoja. Ensimmäisessä artikkelissa irrationaalisuusmittoja johdetaan uudella tavalla irrationaalilukujen yksinkertaisista ketjumurtolukuesityksistä. Toisessa ja kolmannessa artikkelissa irrationaalisuusmitat konstruoidaan Padé-approksimaatioiden avulla. Toisessa artikkelissa saadaan eksplisiittinen irrationaalisuusmitta q-eksponenttisarjan arvoille, joiden vastaavat aikaisemmat irrationaalisuusmitat eivät ole näin eksplisiittisiä. Lisäksi samassa artikkelissa konstruoidaan q-eksponenttisarjan arvoille rajoitettu eksplisiittinen irrationaalisuusmitta, mikä parantaa aikaisempia tuloksia rajoitetussa tapauksessa. Kolmannessa artikkelissa johdetaan paras mahdollinen asymptoottinen irrationaalisuuseksponentti Jacobin kolmitulon arvoille. Viimeisessä artikkelissa käsitellään Cantorin sarjoja. Siinä yleistetään aikaisempia tuloksia johtamalla Sondowin irrationaalisuusmitta tietylle joukolle Cantorin sarjoja.

There has been a rapid increase interest in computational number theory ever since the invention of public-key cryptography. Various attempts to solve the underlying hard problems behind public-key cryptosystems has led to interesting problems in computational number theory. One such problem, called the cubic sieve congruence problem, arises in the context of the cubic sieve method for solving the discrete logarithm problem in prime fields. The cubic sieve method requires a nontrivial solution to the Cubic Sieve Congruence (CSC)x3 y2z (mod p), where p is a given prime. A nontrivial solution must satisfy x3 y2z (mod p), x3 ≠ y2z, 1≤ x, y, z < pα , where α is a given real number ⅓ < α ≤ ½. The CSC problem is to find an efficient algorithm to obtain a nontrivial solution to CSC. This thesis is concerned with the CSC problem. Recently, the parametrization x y2z (mod p) and y υ3z (mod p) of CSC was introduced. We give a deterministic polynomial-time (O(ln3p) bit-operations) algorithm to determine, for a given υ, a nontrivial solution to CSC, if one exists. Previously it took Õ(pα) time to do this. We relate the CSC problem to the gap problem of fractional part sequences. We also show in the α = ½ case that for a certain class of primes the CSC problem can be solved deterministically Õ(p⅓) time compared to the previous best of Õ(p½). It is empirically observed that about one out of three primes are covered by this class, up to 109

Nous étudions les semi-groupes de matrices avec des points de vue variés qui se re-coupent. Le point de vue de la croissance s’avère relié à un point de vue géométrique : nous avons partiellement généralisé aux semi-groupes un théorème de Patterson-Sullivan-Paulin sur les groupes, qui donne l’égalité entre exposant critique et dimension de Hausdorff de l’ensemble limite. Nous obtenons cela dans le cadre général des semi-groupes d’isométries d’un espace Gromov-hyperbolique, et notre preuve nous a permis d’obtenir également d’autres résultats nouveaux. Le point de vue informatique s’avère également relié à la croissance, puisque la notion de semi-groupe fortement automatique, que nous avons introduit, permet de calculer les exposants critiques exactes de semi-groupes de développement en base β. Et ce point de vue donne également beaucoup d’autres informations sur ces semi-groupes. Cette notion de croissance s’avère aussi reliée à des conjectures sur les fractions continues telles que celle de Zaremba. Et c’est en étudiant certains semi-groupes de matrices que nous avons pu démontrer des résultats sur les fractions continues périodiques bornées qui permettent de petites avancées dans la résolution d'une conjecture de McMullen. / We study matrix semigroups with different point of view that overlaps. The growth point of view seems to be related with the geometric point of view : we partially generalize to the semigroups a theorem on groups of Patterson-Sullivan-Paulin, that give the equality between the critical exponent and the Hausdorff dimension of the limit set. We obtain this in the general framework of isometries of a Gromov-hyperbolic space, and our proof give also others new results. The computer science point of view is also related to the growth, since we obtain a way to calculate exact values of critical exponents of somes β-adic development semigroups, from a notion of automatic semigroups that we introduce. Furthermore this point of view give a lot of information on these semigroups. This notion of growth shows to be also related to conjectures on continued fractions like Zaremba’s one. And by studing some matrix semigroups we were able to prove some results on bounded periodic continued fractions, doing a little step in the resolution of a conjecture of McMullen.