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.
The logarithmic density of a set of integers from 1 to can be defined by setting the weight of each integer to be , and dividing the total weight of the set by the th partial sum of the harmonic series (or, equivalently for the purposes of asymptotic analysis, dividing by ). The resulting number is 1 or close to 1 when the set includes all of the integers in that range, but smaller when many integers are missing, and particularly when the missing integers are themselves small. [1]
A subset of is called primitive if it has the property that no subset element is a multiple of any other element. Behrend's theorem states that the logarithmic density of any primitive subset must be small. More precisely, the logarithmic density of such a set must be . [1]
For infinite primitive sequences, the maximum possible density is smaller, . [2]
There exist large primitive subsets of . However, these sets still have small logarithmic density.
Both of these subsets have significantly smaller logarithmic density than the bound given by Behrend's theorem. Resolving a conjecture of G. H. Hardy, both Paul Erdős and Subbayya Sivasankaranarayana Pillai showed that, for , the set of numbers with exactly prime factors (counted with multiplicity) has logarithmic density
exactly matching the form of Behrend's theorem. [3] This example is best possible, in the sense that no other primitive subset has logarithmic density with the same form and a larger leading constant. [4]
This theorem is known as Behrend's theorem because Felix Behrend proved it in 1934, [1] and published it in 1935. [5] Paul Erdős proved the same result, on a 1934 train trip from Hungary to Cambridge to escape the growing anti-semitism in Europe, but on his arrival he discovered that Behrend's proof was already known. [1]
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.
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 number theory, natural density is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the desired subset when combing through the interval [1, n] as n grows large.
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.
In number theory, the Erdős–Kac theorem, named after Paul Erdős and Mark Kac, and also known as the fundamental theorem of probabilistic number theory, states that if ω(n) is the number of distinct prime factors of n, then, loosely speaking, the probability distribution of
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 .
In number theory, the Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. In other words, for every natural number k, there exist arithmetic progressions of primes with k terms. The proof is an extension of Szemerédi's theorem. The problem can be traced back to investigations of Lagrange and Waring from around 1770.
In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.
In number theory, a Sidon sequence is a sequence of natural numbers in which all pairwise sums are different. Sidon sequences are also called Sidon sets; they are named after the Hungarian mathematician Simon Sidon, who introduced the concept in his investigations of Fourier series.
The Erdős–Szemerédi theorem in arithmetic combinatorics states that for every finite set of integers, at least one of , the set of pairwise sums or , the set of pairwise products form a significantly larger set. More precisely, the Erdős–Szemerédi theorem states that there exist positive constants c and such that for any non-empty set
In mathematics, a square-difference-free set is a set of natural numbers, no two of which differ by a square number. Hillel Furstenberg and András Sárközy proved in the late 1970s the Furstenberg–Sárközy theorem of additive number theory showing that, in a certain sense, these sets cannot be very large. In the game of subtract a square, the positions where the next player loses form a square-difference-free set. Another square-difference-free set is obtained by doubling the Moser–de Bruijn sequence.
In combinatorial mathematics and extremal graph theory, the Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in a graph in which every edge belongs to a unique triangle. Equivalently it asks for the maximum number of edges in a balanced bipartite graph whose edges can be partitioned into a linear number of induced matchings, or the maximum number of triples one can choose from points so that every six points contain at most two triples. The problem is named after Imre Z. Ruzsa and Endre Szemerédi, who first proved that its answer is smaller than by a slowly-growing factor.
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.
Felix Adalbert Behrend was a German mathematician of Jewish descent who escaped Nazi Germany and settled in Australia. His research interests included combinatorics, number theory, and topology. Behrend's theorem and Behrend sequences are named after him.
In number theory, a Behrend sequence is an integer sequence whose multiples include almost all integers. The sequences are named after Felix Behrend.
In number theory, the Davenport–Erdős theorem states that, for sets of multiples of integers, several different notions of density are equivalent.
In mathematics, a Stanley sequence is an integer sequence generated by a greedy algorithm that chooses the sequence members to avoid arithmetic progressions. If is a finite set of non-negative integers on which no three elements form an arithmetic progression, then the Stanley sequence generated from starts from the elements of , in sorted order, and then repeatedly chooses each successive element of the sequence to be a number that is larger than the already-chosen numbers and does not form any three-term arithmetic progression with them. These sequences are named after Richard P. Stanley.
Roth's theorem on arithmetic progressions is a result in additive combinatorics concerning the existence of arithmetic progressions in subsets of the natural numbers. It was first proven by Klaus Roth in 1953. Roth's Theorem is a special case of Szemerédi's Theorem for the case .
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. Although planned to be part of a two-volume set, the second volume was never published.
