This volume mainly deals with the dynamics of finitely valued sequences, and more specifically, of sequences generated by substitutions and automata. Those sequences demonstrate fairly simple combinatorical and arithmetical properties and naturally appear in various domains. As the title suggests, the aim of the initial version of this book was the spectral study of the associated dynamical systems: the first chapters consisted in a detailed introduction to the mathematical notions involved, and the description of the spectral invariants followed in the closing chapters.

This approach, combined with new material added to the new edition, results in a nearly self-contained book on the subject. New tools - which have also proven helpful in other contexts - had to be developed for this study. Moreover, its findings can be concretely applied, the method providing an algorithm to exhibit the spectral measures and the spectral multiplicity, as is demonstrated in several examples. Beyond this advanced analysis, many readers will benefit from the introductory chapters on the spectral theory of dynamical systems; others will find complements on the spectral study of bounded sequences; finally, a very basic presentation of substitutions, together with some recent findings and questions, rounds out the book.

[Hilbert's] style has not the terseness of many of our modem authors in mathematics, which is based on the assumption that printer's labor and paper are costly but the reader's effort and time are not. H. Weyl [143] The purpose of this book is to describe the classical problems in additive number theory and to introduce the circle method and the sieve method, which are the basic analytical and combinatorial tools used to attack these problems. This book is intended for students who want to lel?Ill additive number theory, not for experts who already know it. For this reason, proofs include many "unnecessary" and "obvious" steps; this is by design. The archetypical theorem in additive number theory is due to Lagrange: Every nonnegative integer is the sum of four squares. In general, the set A of nonnegative integers is called an additive basis of order h if every nonnegative integer can be written as the sum of h not necessarily distinct elements of A. Lagrange 's theorem is the statement that the squares are a basis of order four. The set A is called a basis offinite order if A is a basis of order h for some positive integer h. Additive number theory is in large part the study of bases of finite order. The classical bases are the squares, cubes, and higher powers; the polygonal numbers; and the prime numbers. The classical questions associated with these bases are Waring's problem and the Goldbach conjecture.

Quantum computers will break today's most popular public-key cryptographic systems, including RSA, DSA, and ECDSA. This book introduces the reader to the next generation of cryptographic algorithms, the systems that resist quantum-computer attacks: in particular, post-quantum public-key encryption systems and post-quantum public-key signature systems.

Leading experts have joined forces for the first time to explain the state of the art in quantum computing, hash-based cryptography, code-based cryptography, lattice-based cryptography, and multivariate cryptography. Mathematical foundations and implementation issues are included.

This book is an essential resource for students and researchers who want to contribute to the field of post-quantum cryptography.

Since its publication, C.F. Gauss's Disquisitiones Arithmeticae (1801) has acquired an almost mythical reputation, standing as an ideal of exposition in notation, problems and methods; as a model of organisation and theory building; and as a source of mathematical inspiration. Eighteen authors - mathematicians, historians, philosophers - have collaborated in this volume to assess the impact of the Disquisitiones, in the two centuries since its publication.

The relation between mathematics and physics has a long history, in which the role of number theory and of other more abstract parts of mathematics has recently become more prominent.

More than ten years after a first meeting in 1989 between number theorists and physicists at the Centre de Physique des Houches, a second 2-week event focused on the broader interface of number theory, geometry, and physics.

This book is the result of that exciting meeting, and collects, in 2 volumes, extended versions of the lecture courses, followed by shorter texts on special topics, of eminent mathematicians and physicists.

The present volume has three parts: Conformal Field Theories, Discrete Groups, Renomalization.

The companion volume is subtitled: On Random Matrices, Zeta Functions and Dynamical Systems (Springer, 3-540-23189-7).

Als mehrbandiges Nachschlagewerk ist das Springer-Handbuch der Mathematik in erster Linie fur wissenschaftliche Bibliotheken, akademische Institutionen und Firmen sowie interessierte Individualkunden in Forschung und Lehregedacht. Es erganzt das einbandige themenumfassende Springer-Taschenbuch der Mathematik (ehemaliger Titel Teubner-Taschenbuch der Mathematik), das sich in seiner begrenzten Stoffauswahl besonders an Studierende richtet. Teil I des Springer-Handbuchs enthalt neben dem einfuhrenden Kapitel und dem Kapitel 1 des Springer-Taschenbuchs zusatzliches Material zur hoheren komplexen Funktionentheorie und zur allgemeinen Theorie der partiellen Differentialgleichungen.

In today's extensively wired world, cryptology is vital for guarding communication channels, databases, and software from intruders. Increased processing and communications speed, rapidly broadening access and multiplying storage capacity tend to make systems less secure over time, and security becomes a race against the relentless creativity of the unscrupulous. The revised and extended third edition of this classic reference work on cryptology offers a wealth of new technical and biographical details. The book presupposes only elementary mathematical knowledge. Spiced with exciting, amusing, and sometimes personal accounts from the history of cryptology, it will interest general a broad readership.

What is the "most uniform" way of distributing n points in the unit square? How big is the "irregularity" necessarily present in any such distribution? This book is an accessible and lively introduction to the area of geometric discrepancy theory, with numerous exercises and illustrations. In separate, more specialized parts, it also provides a comprehensive guide to recent research.

In the last ?fteen years two seemingly unrelated problems, one in computer science and the other in measure theory, were solved by amazingly similar techniques from representation theory and from analytic number theory. One problem is the - plicit construction of expanding graphs (-expanders-). These are highly connected sparse graphs whose existence can be easily demonstrated but whose explicit c- struction turns out to be a dif?cult task. Since expanders serve as basic building blocks for various distributed networks, an explicit construction is highly des- able. The other problem is one posed by Ruziewicz about seventy years ago and studied by Banach Ba]. It asks whether the Lebesgue measure is the only ?nitely additive measure of total measure one, de?ned on the Lebesgue subsets of the n-dimensional sphere and invariant under all rotations. The two problems seem, at ?rst glance, totally unrelated. It is therefore so- what surprising that both problems were solved using similar methods: initially, Kazhdan s property (T) from representation theory of semi-simple Lie groups was applied in both cases to achieve partial results, and later on, both problems were solved using the (proved) Ramanujan conjecture from the theory of automorphic forms. The fact that representation theory and automorphic forms have anything to do with these problems is a surprise and a hint as well that the two questions are strongly related."

The 8th International Conference on Cryptology and Network Security (CANS 2009) was held at the Ishikawa Prefectural Museum of Art in Kanazawa, Japan, during December 12-14, 2009. The conference was jointly co-organized by the NationalInstituteofAdvancedIndustrialScienceandTechnology(AIST), Japan, and the Japan Advanced Institute of Science and Technology (JAIST). In ad- tion, the event was supported by the Special Interest Group on Computer Se- rity (CSEC), IPSJ, Japan, the Japan Technical Group on Information Security (ISEC), IEICE, the Japan Technical Committee on Information and Com- nication System Security(ICSS), IEICE, and the Society of Information Theory and its Applications (SITA), Japan, and co-sponsored by the National Ins- tute of Information and Communications Technology, Japan, ComWorth Co., LTD, Japan, Hitachi, Ltd., Hokuriku Telecommunication Network Co., Inc., and Internet Initiative Japan Inc. The conference received 109 submissions from 24 countries, out of which 32 were accepted for publication in these proceedings. At least three Program Committee (PC) members reviewed each submitted paper, while submissions co-authored by a PC member were submitted to the more stringent evaluation of ?ve PC members. In addition to the PC members, many external reviewers joinedthereviewprocessintheirparticularareasofexpertise. Wewerefortunate to have this energetic team of experts, and are deeply grateful to all of them for their hard work, which included a very active discussion phase-almost as long as the initial individual reviewing period. The paper submission, review and discussion processes were e?ectively and e?ciently made possible by the Web-based system iChair.

In the Riemann zeta function ?(s), the non-real zeros or Riemann zeros, denoted ?, play an essential role mainly in number theory, and thereby g- erate considerable interest. However, they are very elusive objects. Thus, no individual zero has an analytically known location; and the Riemann - pothesis, which states that all those zeros should lie on the critical line, i.e., 1 haverealpart, haschallengedmathematicianssince1859(exactly150years 2 ago). For analogous symmetric sets of numbers{v}, such as the roots of a k polynomial, the eigenvalues of a ?nite or in?nite matrix, etc., it is well known that symmetric functions of the{v} tend to have more accessible properties k than the individual elements v . And, we ?nd the largest wealth of explicit k properties to occur in the (generalized) zeta functions of the generic form 's Zeta(s, a)= (v ]a) k k (with the extra option of replacing v here by selected functions f(v )). k k Not surprisingly, then, zeta functions over the Riemann zeros have been considered, some as early as 1917.What is surprising is how small the lite- ture on those zeta functions has remained overall.We were able to spot them in barely a dozen research articles over the whole twentieth century and in none ofthebooks featuring the Riemannzeta function. So the domainexists, but it has remained largely con?dential and sporadically covered, in spite of a recent surge of interest. Could it then be that those zeta functions have few or uninteresting pr- erties?Inactualfact, theirstudyyieldsanabundanceofquiteexplicitresu

Bringing the material up to date to reflect modern applications, Algebraic Number Theory, Second Edition has been completely rewritten and reorganized to incorporate a new style, methodology, and presentation. This edition focuses on integral domains, ideals, and unique factorization in the first chapter; field extensions in the second chapter; and class groups in the third chapter. Applications are now collected in chapter four and at the end of chapter five, where primality testing is highlighted as an application of the Kronecker-Weber theorem. In chapter five, the sections on ideal decomposition in number fields have been more evenly distributed. The final chapter continues to cover reciprocity laws. New to the Second Edition * Reorganization of all chapters * More complete and involved treatment of Galois theory * A study of binary quadratic forms and a comparison of the ideal and form class groups * More comprehensive section on Pollard's cubic factoring algorithm * More detailed explanations of proofs, with less reliance on exercises, to provide a sound understanding of challenging material The book includes mini-biographies of notable mathematicians, convenient cross-referencing, a comprehensive index, and numerous exercises. The appendices present an overview of all the concepts used in the main text, an overview of sequences and series, the Greek alphabet with English transliteration, and a table of Latin phrases and their English equivalents. Suitable for a one-semester course, this accessible, self-contained text offers broad, in-depth coverage of numerous applications. Readers are lead at a measured pace through the topics to enable a clear understanding of the pinnacles of algebraic number theory.

Number Theory is more than a comprehensive treatment of the subject. It is an introduction to topics in higher level mathematics, and unique in its scope; topics from analysis, modern algebra, and discrete mathematics are all included.

The book is divided into two parts. Part A covers key concepts of number theory and could serve as a first course on the subject. Part B delves into more advanced topics and an exploration of related mathematics. The prerequisites for this self-contained text are elements from linear algebra. Valuable references for the reader are collected at the end of each chapter. It is suitable as an introduction to higher level mathematics for undergraduates, or for self-study.

Geometry and the theory of numbers are as old as some of the oldest historical records of humanity. Ever since antiquity, mathematicians have discovered many beautiful interactions between the two subjects and recorded them in such classical texts as Euclid's Elements and Diophantus's Arithmetica. Nowadays, the field of mathematics that studies the interactions between number theory and algebraic geometry is known as arithmetic geometry. This book is an introduction to number theory and arithmetic geometry, and the goal of the text is to use geometry as the motivation to prove the main theorems in the book. For example, the fundamental theorem of arithmetic is a consequence of the tools we develop in order to find all the integral points on a line in the plane. Similarly, Gauss's law of quadratic reciprocity and the theory of continued fractions naturally arise when we attempt to determine the integral points on a curve in the plane given by a quadratic polynomial equation. After an introduction to the theory of diophantine equations, the rest of the book is structured in three acts that correspond to the study of the integral and rational solutions of linear, quadratic, and cubic curves, respectively. This book describes many applications including modern applications in cryptography; it also presents some recent results in arithmetic geometry. With many exercises, this book can be used as a text for a first course in number theory or for a subsequent course on arithmetic (or diophantine) geometry at the junior-senior level.

The relation between mathematics and physics has a long history, in which the role of number theory and of other more abstract parts of mathematics has recently become more prominent.

More than ten years after a first meeting in 1989 between number theorists and physicists at the Centre de Physique des Houches, a second 2-week event focused on the broader interface of number theory, geometry, and physics.

This book is the result of that exciting meeting, and collects, in 2 volumes, extended versions of the lecture courses, followed by shorter texts on special topics, of eminent mathematicians and physicists.

The present volume has three parts: Random matrices, Zeta functions, Dynamical systems.

The companion volume is subtitled: On Conformal Field Theories, Discrete Groups and Renormalization and will be published in 2006 (Springer, 3-540-30307-3).

Ce travail en deux volumes donne la preuve de la stabilisation de la formule des trace tordue. Stabiliser la formule des traces tordue est la methode la plus puissante connue actuellement pour comprendre l'action naturelle du groupe des points adeliques d'un groupe reductif, tordue par un automorphisme, sur les formes automorphes de carre integrable de ce groupe. Cette comprehension se fait en reduisant le probleme, suivant les idees de Langlands, a des groupes plus petits munis d'un certain nombre de donnees auxiliaires; c'est ce que l'on appelle les donnees endoscopiques. L'analogue non tordu a ete resolu par J. Arthur et dans ce livre on suit la strategie de celui-ci. Publier ce travail sous forme de livre permet de le rendre le plus complet possible. Les auteurs ont repris la theorie de l'endoscopie tordue developpee par R. Kottwitz et D. Shelstad et par J.-P. Labesse. Ils donnent tous les arguments des demonstrations meme si nombre d'entre eux se tr ouvent deja dans les travaux d'Arthur concernant le cas de la formule des traces non tordue. Ce travail permet de rendre inconditionnelle la classification que J. Arthur a donnee des formes automorphes de carre integrable pour les groupes classiques quasi-deployes, c'etait pour les auteurs une des principales motivations pour l'ecrire. Cette partie contient les preuves de la stabilisation geometrique et de la partie spectrale en particulier de la partie discrete de ce terme, ce qui est le point d'aboutissement de ce sujet.

This book is a modern treatment of the theory of theta functions in the context of algebraic geometry. The novelty of its approach lies in the systematic use of the Fourier-Mukai transform. Alexander Polishchuk starts by discussing the classical theory of theta functions from the viewpoint of the representation theory of the Heisenberg group (in which the usual Fourier transform plays the prominent role). He then shows that in the algebraic approach to this theory (originally due to Mumford) the Fourier-Mukai transform can often be used to simplify the existing proofs or to provide completely new proofs of many important theorems. This incisive volume is for graduate students and researchers with strong interest in algebraic geometry.

Adrien-Marie Legendre (1752-1833), one of the great French mathematicians active in the Revolutionary period, made important contributions to number theory, statistics, mathematical analysis and algebra. He taught at the Ecole Militaire, where he was a colleague of Laplace, and made his name with a paper on the trajectory of projectiles which won a prize of the Berlin Academy in 1782, and brought him to the attention of Lagrange. In 1794 he published Elements de geometrie, which remained a textbook for over 100 years. The first edition of his Essai sur la theorie des nombres was published in 1798, and the much improved second edition, which is offered here, in 1808. In it Legendre had taken account of criticism by Gauss of the mathematical proofs in the first edition, though he was bitter at the manner in which his younger rival had claimed credit for some of his solutions.

In this volume one finds basic techniques from algebra and number theory (e.g. congruences, unique factorization domains, finite fields, quadratic residues, primality tests, continued fractions, etc.) which in recent years have proven to be extremely useful for applications to cryptography and coding theory. Both cryptography and codes have crucial applications in our daily lives, and they are described here, while the complexity problems that arise in implementing the related numerical algorithms are also taken into due account. Cryptography has been developed in great detail, both in its classical and more recent aspects. In particular public key cryptography is extensively discussed, the use of algebraic geometry, specifically of elliptic curves over finite fields, is illustrated, and a final chapter is devoted to quantum cryptography, which is the new frontier of the field. Coding theory is not discussed in full; however a chapter, sufficient for a good introduction to the subject, has been devoted to linear codes. Each chapter ends with several complements and with an extensive list of exercises, the solutions to most of which are included in the last chapter.

Though the book contains advanced material, such as cryptography on elliptic curves, Goppa codes using algebraic curves over finite fields, and the recent AKS polynomial primality test, the authors' objective has been to keep the exposition as self-contained and elementary as possible. Therefore the book will be useful to students and researchers, both in theoretical (e.g. mathematicians) and in applied sciences (e.g. physicists, engineers, computer scientists, etc.) seeking a friendly introduction to the important subjects treated here. The book will also be useful for teachers who intend to give courses on these topics.

Eugene Charles Catalan made his famous conjecture - that 8 and 9 are the only two consecutive perfect powers of natural numbers - in 1844 in a letter to the editor of Crelle's mathematical journal. One hundred and fifty-eight years later, Preda Mihailescu proved it.

Catalan's Conjecture presents this spectacular result in a way that is accessible to the advanced undergraduate. The author dissects both Mihailescu's proof and the earlier work it made use of, taking great care to select streamlined and transparent versions of the arguments and to keep the text self-contained. Only in the proof of Thaine's theorem is a little class field theory used; it is hoped that this application will motivate the interested reader to study the theory further.

Beautifully clear and concise, this book will appeal not only to specialists in number theory but to anyone interested in seeing the application of the ideas of algebraic number theory to a famous mathematical problem."

Many of the important and creative developments in modern mathematics resulted from attempts to solve questions that originate in number theory. The publication of Emil Grosswald's classic text presents an illuminating introduction to number theory. Combining the historical developments with the analytical approach, Topics from the Theory of Numbers offers the reader a diverse range of subjects to investigate.

Like the intriguing Fibonacci and Lucas numbers, Catalan numbers are also ubiquitous. "They have the same delightful propensity for popping up unexpectedly, particularly in combinatorial problems," Martin Gardner wrote in Scientific American. "Indeed, the Catalan sequence is probably the most frequently encountered sequence that is still obscure enough to cause mathematicians lacking access to Sloane's Handbook of Integer Sequences to expend inordinate amounts of energy re-discovering formulas that were worked out long ago," he continued. As Gardner noted, many mathematicians may know the abc's of Catalan sequence, but not many are familiar with the myriad of their unexpected occurrences, applications, and properties; they crop up in chess boards, computer programming, and even train tracks. This book presents a clear and comprehensive introduction to one of the truly fascinating topics in mathematics. Catalan numbers are named after the Belgian mathematician Eugene Charles Catalan (1814-1894), who "discovered" them in 1838, though he was not the first person to discover them. The great Swiss mathematician Leonhard Euler (1707-1763) "discovered" them around 1756, but even before then and though his work was not known to the outside world, Chinese mathematician Antu Ming (1692?-1763) first discovered Catalan numbers about 1730. A great source of fun for both amateurs and mathematicians, they can be used by teachers and professors to generate excitement among students for exploration and intellectual curiosity and to sharpen a variety of mathematical skills and tools, such as pattern recognition, conjecturing, proof-techniques, and problem-solving techniques. This book is not intended for mathematicians only but for a much larger audience, including high school students, math and science teachers, computer scientists, and those amateurs with a modicum of mathematical curiosity. An invaluable resource book, it contains an intriguing array of applications to computer science, abstract algebra, combinatorics, geometry, graph theory, chess, and world series.

In this volume the author further develops his philosophy of quantum interpolation between the real numbers and the p-adic numbers. The p-adic numbers contain the p-adic integers Zp which are the inverse limit of the finite rings Z/pn. This gives rise to a tree, and probability measures w on Zp correspond to Markov chains on this tree. From the tree structure one obtains special basis for the Hilbert space L2(Zp, w). The real analogue of the p-adic integers is the interval -1,1], and a probability measure w on it gives rise to a special basis for L2( -1,1], w) - the orthogonal polynomials, and to a Markov chain on "finite approximations" of -1,1]. For special (gamma and beta) measures there is a "quantum" or "q-analogue" Markov chain, and a special basis, that within certain limits yield the real and the p-adic theories. This idea can be generalized variously. In representation theory, it is the quantum general linear group GLn(q)that interpolates between the p-adic group GLn(Zp), and between its real (and complex) analogue -the orthogonal On (and unitary Un )groups. There is a similar quantum interpolation between the real and p-adic Fourier transform and between the real and p-adic (local unramified part of) Tate thesis, and Weil explicit sums.

The ?rst Algorithmic Number Theory Symposium took place in May 1994 at Cornell University. The preface to its proceedings has the organizers expressing the hope that the meeting would be "the ?rst in a long series of international conferencesonthe algorithmic, computational, andcomplexity theoreticaspects of number theory." ANTS VIII was held May 17-22, 2008 at the Ban? Centre in Ban?, Alberta, Canada. It was the eighth in this lengthening series. The conference included four invited talks, by Johannes Buchmann (TU Darmstadt), AndrewGranville(UniversitedeMontr eal), Fran, coisMorain(Ecole Polytechnique), andHughWilliams(UniversityofCalgary), apostersession, and 28 contributed talks in appropriate areas of number theory. Each submitted paper was reviewed by at least two experts external to the Program Committee; the selection was made by the committee on the basis of thoserecommendations.TheSelfridgePrizeincomputationalnumbertheorywas awardedtotheauthorsofthebestcontributedpaperpresentedattheconference. The participants in the conference gratefully acknowledge the contribution made by the sponsors of the meeting. May 2008 Alf van der Poorten and Andreas Stein (Editors) Renate Scheidler (Organizing Committee Chair) Igor Shparlinski (Program Committee Chair) Conference Website The names of the winners of the Selfridge Prize, material supplementing the contributed papers, and errata for the proceedings, as well as the abstracts of the posters and the posters presented at ANTS VIII, can be found at: http: //ants.math.ucalgary.ca."

This book grew out of three series of lectures given at the summer school on "Modular Forms and their Applications" at the Sophus Lie Conference Center in Nordfjordeid in June 2004. The first series treats the classical one-variable theory of elliptic modular forms. The second series presents the theory of Hilbert modular forms in two variables and Hilbert modular surfaces. The third series gives an introduction to Siegel modular forms and discusses a conjecture by Harder. It also contains Harder's original manuscript with the conjecture.

Each part treats a number of beautiful applications.