Sequences (book)

Last updated
H. Halberstam and K.F. Roth: Sequences
H. Halberstam and K.F. Roth - Sequences 2nd ed., Springer, New York, 1983 - front cover.jpg
H. Halberstam and K.F. Roth: Sequences 2nd ed., Springer, New York, Heidelberg, Berlin, 1983.
AuthorH. Halberstam and K.F. Roth
PublisherClarendon Press 1st edition; Springer, New York, 2nd edition.
Published in English
1966 1st edition; 1983 2nd edition.
ISBN 9781461382294 2nd edition.
OCLC 877577079 1st edition; 7330436683 2nd edition.

Sequences is a mathematical monograph on integer sequences. It was written by Heini Halberstam and Klaus Roth, published in 1966 by the Clarendon Press, and republished in 1983 with minor corrections by Springer-Verlag. [1] [2] Although planned to be part of a two-volume set, [3] [4] the second volume was never published.

Contents

Topics

The book has five chapters, [3] each largely self-contained [4] [5] and loosely organized around different techniques used to solve problems in this area, [4] with an appendix on the background material in number theory needed for reading the book. [3] Rather than being concerned with specific sequences such as the prime numbers or square numbers, its topic is the mathematical theory of sequences in general. [6] [7]

The first chapter considers the natural density of sequences, and related concepts such as the Schnirelmann density. It proves theorems on the density of sumsets of sequences, including Mann's theorem that the Schnirelmann density of a sumset is at least the sum of the Schnirelmann densities and Kneser's theorem on the structure of sequences whose lower asymptotic density is subadditive. It studies essential components, sequences that when added to another sequence of Schnirelmann density between zero and one, increase their density, proves that additive bases are essential components, and gives examples of essential components that are not additive bases. [3] [6] [7] [8]

The second chapter concerns the number of representations of the integers as sums of a given number of elements from a given sequence, and includes the Erdős–Fuchs theorem according to which this number of representations cannot be close to a linear function. The third chapter continues the study of numbers of representations, using the probabilistic method; it includes the theorem that there exists an additive basis of order two whose number of representations is logarithmic, later strengthened to all orders in the Erdős–Tetali theorem. [3] [6] [7] [8]

After a chapter on sieve theory and the large sieve (unfortunately missing significant developments that happened soon after the book's publication), [6] [7] the final chapter concerns primitive sequences of integers, sequences like the prime numbers in which no element is divisible by another. It includes Behrend's theorem that such a sequence must have logarithmic density zero, and the seemingly-contradictory construction by Abram Samoilovitch Besicovitch of primitive sequences with natural density close to 1/2. It also discusses the sequences that contain all integer multiples of their members, the Davenport–Erdős theorem according to which the lower natural and logarithmic density exist and are equal for such sequences, and a related construction of Besicovitch of a sequence of multiples that has no natural density. [3] [6] [7]

Audience and reception

This book is aimed at other mathematicians and students of mathematics; it is not suitable for a general audience. [4] However, reviewer J. W. S. Cassels suggests that it could be accessible to advanced undergraduates in mathematics. [6]

Reviewer E. M. Wright notes the book's "accurate scholarship", "most readable exposition", and "fascinating topics". [5] Reviewer Marvin Knopp describes the book as "masterly", and as the first book to overview additive combinatorics. [4] Similarly, although Cassels notes the existence of material on additive combinatorics in the books Additive Zahlentheorie (Ostmann, 1956) and Addition Theorems (Mann, 1965), he calls this "the first connected account" of the area, [6] and reviewer Harold Stark notes that much of material covered by the book is "unique in book form". [7] Knopp also praises the book for, in many cases, correcting errors or deficiencies in the original sources that it surveys. [4] Reviewer Harold Stark writes that the book "should be a standard reference in this area for years to come". [7]

Related Research Articles

In additive number theory, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician Lev Schnirelmann, who was the first to study it.

In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.

<span class="mw-page-title-main">Klaus Roth</span> British mathematician (1925–2015)

Klaus Friedrich Roth was a German-born British mathematician who won the Fields Medal for proving Roth's theorem on the Diophantine approximation of algebraic numbers. He was also a winner of the De Morgan Medal and the Sylvester Medal, and a Fellow of the Royal Society.

In additive combinatorics, the sumset of two subsets and of an abelian group is defined to be the set of all sums of an element from with an element from . That is,

In number theory, zero-sum problems are certain kinds of combinatorial problems about the structure of a finite abelian group. Concretely, given a finite abelian group G and a positive integer n, one asks for the smallest value of k such that every sequence of elements of G of size k contains n terms that sum to 0.

Erdős' conjecture on arithmetic progressions, often referred to as the Erdős–Turán conjecture, is a conjecture in arithmetic combinatorics. It states that if the sum of the reciprocals of the members of a set A of positive integers diverges, then A contains arbitrarily long arithmetic progressions.

Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigroups with an operation of addition. Additive number theory has close ties to combinatorial number theory and the geometry of numbers. Two principal objects of study are the sumset of two subsets A and B of elements from an abelian group G,

In additive number theory, an additive basis is a set of natural numbers with the property that, for some finite number , every natural number can be expressed as a sum of or fewer elements of . That is, the sumset of copies of consists of all natural numbers. The order or degree of an additive basis is the number . When the context of additive number theory is clear, an additive basis may simply be called a basis. An asymptotic additive basis is a set for which all but finitely many natural numbers can be expressed as a sum of or fewer elements of .

Combinatorial number theory deals with number theoretic problems which involve combinatorial ideas in their formulations or solutions. Paul Erdős is the main founder of this branch of number theory. Typical topics include covering system, zero-sum problems, various restricted sumsets, and arithmetic progressions in a set of integers. Algebraic or analytic methods are powerful in this field.

Ergodic Ramsey theory is a branch of mathematics where problems motivated by additive combinatorics are proven using ergodic theory.

In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.

Additive combinatorics is an area of combinatorics in mathematics. One major area of study in additive combinatorics are inverse problems: given the size of the sumset A + B is small, what can we say about the structures of and ? In the case of the integers, the classical Freiman's theorem provides a partial answer to this question in terms of multi-dimensional arithmetic progressions.

<span class="mw-page-title-main">Dyson's transform</span>

Dyson's transform is a fundamental technique in additive number theory. It was developed by Freeman Dyson as part of his proof of Mann's theorem, is used to prove such fundamental results of additive number theory as the Cauchy-Davenport theorem, and was used by Olivier Ramaré in his work on the Goldbach conjecture that proved that every even integer is the sum of at most 6 primes. The term Dyson's transform for this technique is used by Ramaré. Halberstam and Roth call it the τ-transformation.

The Erdős–Turán conjecture is an old unsolved problem in additive number theory posed by Paul Erdős and Pál Turán in 1941.

In additive number theory, an area of mathematics, the Erdős–Tetali theorem is an existence theorem concerning economical additive bases of every order. More specifically, it states that for every fixed integer , there exists a subset of the natural numbers satisfying

<span class="mw-page-title-main">Salem–Spencer set</span> Progression-free set of numbers

In mathematics, and in particular in arithmetic combinatorics, a Salem-Spencer set is a set of numbers no three of which form an arithmetic progression. Salem–Spencer sets are also called 3-AP-free sequences or progression-free sets. They have also been called non-averaging sets, but this term has also been used to denote a set of integers none of which can be obtained as the average of any subset of the other numbers. Salem-Spencer sets are named after Raphaël Salem and Donald C. Spencer, who showed in 1942 that Salem–Spencer sets can have nearly-linear size. However a later theorem of Klaus Roth shows that the size is always less than linear.

In arithmetic combinatorics, Behrend's theorem states that the subsets of the integers from 1 to in which no member of the set is a multiple of any other must have a logarithmic density that goes to zero as becomes large. The theorem is named after Felix Behrend, who published it in 1935.

In number theory, the Davenport–Erdős theorem states that, for sets of multiples of integers, several different notions of density are equivalent.

References

  1. Halberstam, H.; Roth, K.F. (1966). Sequences. Oxford: Clarendon Press. OCLC   877577079.
  2. Halberstam, H.; Roth, K.F. (1983). Sequences (2nd ed.). New York: Springer New York. doi:10.1007/978-1-4613-8227-0. ISBN   9781461382294. OCLC   7330436683.
  3. 1 2 3 4 5 6 Kubilius, J., "Review of Sequences", Mathematical Reviews , MR   0210679
  4. 1 2 3 4 5 6 Knopp, Marvin I. (January 1967), "Questions and methods in number theory", Science , 155 (3761): 442–443, Bibcode:1967Sci...155..442H, doi:10.1126/science.155.3761.442, JSTOR   1720189, S2CID   241017491
  5. 1 2 Wright, E. M. (1968), "Review of Sequences", Journal of the London Mathematical Society , s1-43 (1): 157, doi:10.1112/jlms/s1-43.1.157a
  6. 1 2 3 4 5 6 7 Cassels, J. W. S. (February 1968), "Review of Sequences", The Mathematical Gazette , 52 (379): 85–86, doi:10.2307/3614509, JSTOR   3614509, S2CID   126260926
  7. 1 2 3 4 5 6 7 Stark, H. M. (1971), "Review of Sequences", Bulletin of the American Mathematical Society , 77 (6): 943–957, doi: 10.1090/s0002-9904-1971-12812-4
  8. 1 2 Briggs, W. E., "Review of Sequences", zbMATH , Zbl   0141.04405