|
Sumset
In additive combinatorics, the sumset (also called the Minkowski sum) of two subsets A and B of an abelian group G (written additively) is defined to be the set of all sums of an element from A with an element from B. That is, :A + B = \. The n-fold iterated sumset of A is :nA = A + \cdots + A, where there are n summands. Many of the questions and results of additive combinatorics and additive number theory can be phrased in terms of sumsets. For example, Lagrange's four-square theorem can be written succinctly in the form :4\Box = \mathbb, where \Box is the set of square numbers. A subject that has received a fair amount of study is that of sets with ''small doubling'', where the size of the set A+A is small (compared to the size of A); see for example Freiman's theorem. See also *Restricted sumset * Sidon set *Sum-free set *Schnirelmann density *Shapley–Folkman lemma *X + Y sorting References * * * *Terence Tao and Van Vu, ''Additive Combinatorics'', Cambridge Universit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Minkowski Addition
In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors ''A'' and ''B'' in Euclidean space is formed by adding each vector in ''A'' to each vector in ''B'', i.e., the set : A + B = \. Analogously, the Minkowski difference (or geometric difference) is defined using the complement operation as : A - B = \left(A^c + (-B)\right)^c In general A - B \ne A + (-B). For instance, in a one-dimensional case A = 2, 2/math> and B = 1, 1/math> the Minkowski difference A - B = 1, 1/math>, whereas A + (-B) = A + B = 3, 3 In a two-dimensional case, Minkowski difference is closely related to erosion (morphology) in image processing. The concept is named for Hermann Minkowski. Example For example, if we have two sets ''A'' and ''B'', each consisting of three position vectors (informally, three points), representing the vertices of two triangles in \mathbb^2, with coordinates :A = \ and :B = \ then their Minkowski sum is :A + B = \ which comp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Restricted Sumset
In additive number theory and combinatorics, a restricted sumset has the form :S=\, where A_1,\ldots,A_n are finite nonempty subsets of a field ''F'' and P(x_1,\ldots,x_n) is a polynomial over ''F''. If P is a constant non-zero function, for example P(x_1,\ldots,x_n)=1 for any x_1,\ldots,x_n, then S is the usual sumset A_1+\cdots+A_n which is denoted by nA if A_1=\cdots=A_n=A. When :P(x_1,\ldots,x_n) = \prod_ (x_j-x_i), ''S'' is written as A_1\dotplus\cdots\dotplus A_n which is denoted by n^ A if A_1=\cdots=A_n=A. Note that , ''S'', > 0 if and only if there exist a_1\in A_1,\ldots,a_n\in A_n with P(a_1,\ldots,a_n)\not=0. Cauchy–Davenport theorem The Cauchy–Davenport theorem, named after Augustin Louis Cauchy and Harold Davenport, asserts that for any prime ''p'' and nonempty subsets ''A'' and ''B'' of the prime order cyclic group \mathbb/p\mathbb we have the inequalityGeroldinger & Ruzsa (2009) pp.141–142 :, A+B, \ge \min\ where A+B := \, i.e. we're using modu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Freiman's Theorem
In additive combinatorics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if , A+A, /, A, is small, then A can be contained in a small generalized arithmetic progression. Statement If A is a finite subset of \mathbb with , A+A, \le K, A, , then A is contained in a generalized arithmetic progression of dimension at most d(K) and size at most f(K), A, , where d(K) and f(K) are constants depending only on K. Examples For a finite set A of integers, it is always true that :, A + A, \ge 2, A, -1, with equality precisely when A is an arithmetic progression. More generally, suppose A is a subset of a finite proper generalized arithmetic progression P of dimension d such that , P, \le C, A, for some real C \ge 1. Then , P+P, \le 2^d , P, , so that :, A+A, \le , P+P, \le 2^d , P, \le C2^d, A, . History of Freiman's theorem This result is due to Gregory Freiman (1964, 1966). Much interest in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Additive Number Theory
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'', :A + B = \, and the h-fold sumset of ''A'', :hA = \underset\,. Additive number theory The field is principally devoted to consideration of ''direct problems'' over (typically) the integers, that is, determining the structure of ''hA'' from the structure of ''A'': for example, determining which elements can be represented as a sum from ''hA'', where ''A'' is a fixed subset.Nathanson (1996) II:1 Two classical problems of this type are the Goldbach conjecture (which is the conjecture that 2 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sidon Set
In number theory, a Sidon sequence is a sequence A=\ of natural numbers in which all pairwise sums a_i+a_j (for i\le j) 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 main problem in the study of Sidon sequences, posed by Sidon, is to find the maximum number of elements that a Sidon sequence can contain, up to some bound x. Despite a large body of research, the question remained unsolved. Early results Paul Erdős and Pál Turán proved that, for every x>0, the number of elements smaller than x in a Sidon sequence is at most \sqrt+O(\sqrt . Several years earlier, James Singer had constructed Sidon sequences with \sqrt(1-o(1)) terms less than ''x''. Infinite Sidon sequences Erdős also showed that, for any particular infinite Sidon sequence A with A(x) denoting the number of its elements up to x, \liminf_ \frac\leq 1. That is, infinite S ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sum-free Set
In additive combinatorics and number theory, a subset ''A'' of an abelian group ''G'' is said to be sum-free if the sumset ''A'' + ''A'' is disjoint from ''A''. In other words, ''A'' is sum-free if the equation a + b = c has no solution with a,b,c \in A. For example, the set of odd numbers is a sum-free subset of the integers, and the set forms a large sum-free subset of the set . Fermat's Last Theorem is the statement that, for a given integer ''n'' > 2, the set of all nonzero ''n''th powers of the integers is a sum-free set. Some basic questions that have been asked about sum-free sets are: * How many sum-free subsets of are there, for an integer ''N''? Ben Green has shown that the answer is O(2^), as predicted by the Cameron–Erdős conjecture. * How many sum-free sets does an abelian group ''G'' contain?Ben Green and Imre RuzsaSum-free sets in abelian groups 2005. * What is the size of the largest sum-free set that an abelian group ''G'' contains? A sum-free set is said ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Schnirelmann Density
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.Schnirelmann, L.G. (1930).On the additive properties of numbers, first published in "Proceedings of the Don Polytechnic Institute in Novocherkassk" (in Russian), vol XIV (1930), pp. 3-27, and reprinted in "Uspekhi Matematicheskikh Nauk" (in Russian), 1939, no. 6, 9–25.Schnirelmann, L.G. (1933). First published asÜber additive Eigenschaften von Zahlen in "Mathematische Annalen" (in German), vol 107 (1933), 649-690, and reprinted asOn the additive properties of numbers in "Uspekhin. Matematicheskikh Nauk" (in Russian), 1940, no. 7, 7–46. Definition The Schnirelmann density of a set of natural numbers ''A'' is defined as :\sigma A = \inf_n \frac, where ''A''(''n'') denotes the number of elements of ''A'' not exceeding ''n'' and inf is infimum.Nathanson (1996) pp.191–19 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Shapley–Folkman Lemma
The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ross M. Starr. The lemma may be intuitively understood as saying that, if the number of summed sets exceeds the dimension of the vector space, then their Minkowski sum is approximately convex. Related results provide more refined statements about ''how close'' the approximation is. For example, the Shapley–Folkman theorem provides an upper bound on the distance between any point in the Minkowski sum and its convex hull. This upper bound is sharpened by the Shapley–Folkman–Starr theorem (alternatively, Starr's corollary). The Shapley–Folkman lemma has applications in economics, optimization and probability theory. In economics, it can be used to extend results proved for convex preferences to non-convex preferences. In op ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graduate Texts In Mathematics
Graduate Texts in Mathematics (GTM) (ISSN 0072-5285) is a series of graduate-level textbooks in mathematics published by Springer-Verlag. The books in this series, like the other Springer-Verlag mathematics series, are yellow books of a standard size (with variable numbers of pages). The GTM series is easily identified by a white band at the top of the book. The books in this series tend to be written at a more advanced level than the similar Undergraduate Texts in Mathematics series, although there is a fair amount of overlap between the two series in terms of material covered and difficulty level. List of books #''Introduction to Axiomatic Set Theory'', Gaisi Takeuti, Wilson M. Zaring (1982, 2nd ed., ) #''Measure and Category – A Survey of the Analogies between Topological and Measure Spaces'', John C. Oxtoby (1980, 2nd ed., ) #''Topological Vector Spaces'', H. H. Schaefer, M. P. Wolff (1999, 2nd ed., ) #''A Course in Homological Algebra'', Peter Hilton, Urs Stammbac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Additive Combinatorics
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 A and B? 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. Another typical problem is to find a lower bound for , A + B, in terms of , A, and , B, . This can be viewed as an inverse problem with the given information that , A+B, is sufficiently small and the structural conclusion is then of the form that either A or B is the empty set; however, in literature, such problems are sometimes considered to be direct problems as well. Examples of this type include the Erdős–Heilbronn Conjecture (for a restricted sumset) and the Cauchy–Davenport Theorem. The methods used for tackling such questions often come from many different fi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Abelian Group
In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commutative. With addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples. Abelian groups are named after early 19th century mathematician Niels Henrik Abel. The concept of an abelian group underlies many fundamental algebraic structures, such as fields, rings, vector spaces, and algebras. The theory of abelian groups is generally simpler than that of their non-abelian counterparts, and finite abelian groups are very well understood and fully classified. Definition An abelian group is a set A, together with an operation \cdot that combines any two elements a and b of A to form another element of A, denoted a \cdot b. The symbo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lagrange's Four-square Theorem
Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares. That is, the squares form an additive basis of order four. p = a_0^2 + a_1^2 + a_2^2 + a_3^2 where the four numbers a_0, a_1, a_2, a_3 are integers. For illustration, 3, 31, and 310 in several ways, can be represented as the sum of four squares as follows: \begin 3 & = 1^2+1^2+1^2+0^2 \\ pt31 & = 5^2+2^2+1^2+1^2 \\ pt310 & = 17^2+4^2+2^2+1^2 \\ pt& = 16^2 + 7^2 + 2^2 +1^2 \\ pt& = 15^2 + 9^2 + 2^2 +0^2 \\ pt& = 12^2 + 11^2 + 6^2 + 3^2. \end This theorem was proven by Joseph Louis Lagrange in 1770. It is a special case of the Fermat polygonal number theorem. Historical development From examples given in the '' Arithmetica,'' it is clear that Diophantus was aware of the theorem. This book was translated in 1621 into Latin by Bachet (Claude Gaspard Bachet de Méziriac), who stated the theorem in the notes of his translation. Bu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
