Sumset

Last updated

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,

Minkowski addition

In geometry, the Minkowski sum 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

Abelian group group whose group operation is commutative

In abstract algebra, 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, these are the groups that obey the axiom of commutativity. Abelian groups generalize the arithmetic of addition of integers. They are named after early 19th century mathematician Niels Henrik Abel.

The n-fold iterated sumset of A is

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

In number theory, the specialty additive number theory studies 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,

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.

where 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.

In mathematics, a square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 9 is a square number, since it can be written as 3 × 3.

In mathematics, Freiman's theorem is a combinatorial result in additive number theory. In a sense it accounts for the approximate structure of sets of integers that contain a high proportion of their internal sums, taken two at a time.

See also

Geometry branch of mathematics that measures the shape, size and position of objects

Geometry is a branch of mathematics concerned with questions of shape, size, relative position of figures, and the properties of space. A mathematician who works in the field of geometry is called a geometer.

In additive number theory and combinatorics, a restricted sumset has the form

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 has no solution with .

Related Research Articles

Field (mathematics) algebraic structure

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined, and behave as the corresponding operations on rational and real numbers do. A field is thus a fundamental algebraic structure, which is widely used in algebra, number theory and many other areas of mathematics.

Partition (number theory) multiset of integers whose sum is a given integer

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 can be partitioned in five distinct ways:

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.

In additive number theory, the Fermat polygonal number theorem states that every positive integer is a sum of at most nn-gonal numbers. That is, every positive integer can be written as the sum of three or fewer triangular numbers, and as the sum of four or fewer square numbers, and as the sum of five or fewer pentagonal numbers, and so on.

In number theory, natural density is one of the possibilities to measure how large a subset of the set of natural numbers is.

Ben Green (mathematician) British mathematician

Ben Joseph Green FRS is a British mathematician, specialising in combinatorics and number theory. He is the Waynflete Professor of Pure Mathematics at the University of Oxford.

Abstract analytic number theory is a branch of mathematics which takes the ideas and techniques of classical analytic number theory and applies them to a variety of different mathematical fields. The classical prime number theorem serves as a prototypical example, and the emphasis is on abstract asymptotic distribution results. The theory was invented and developed by mathematicians such as John Knopfmacher and Arne Beurling in the twentieth century.

In mathematics, a multiple arithmetic progression, generalized arithmetic progression, k-dimensional arithmetic progression or a linear set, is a set of integers or tuples of integers constructed as an arithmetic progression is, but allowing several possible differences. So, for example, we start at 17 and may add a multiple of 3 or of 5, repeatedly. In algebraic terms we look at integers

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.

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

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.

In mathematics, Kneser's theorem is an inequality among the sizes of certain sumsets in abelian groups. It belongs to the field of additive combinatorics, and is named after Martin Kneser, who published it in 1953. It may be regarded as an extension of the Cauchy–Davenport theorem, which also concerns sumsets in groups but is restricted to groups whose order is a prime number.

In mathematics, the Davenport constantD(G) is an invariant of a group studied in additive combinatorics, quantifying the size of nonunique factorizations. Given a finite abelian group G is defined as the smallest number, such that every sequence of elements of that length contains a non-empty sub-sequence adding up to 0. In symbols, this is

Rudin's conjecture is a mathematical hypothesis concerning an upper bound for the number of squares in finite arithmetic progressions. The conjecture, which has applications in the theory of trigonometric series, was first stated by Walter Rudin in his 1960 paper Trigonometric series with gaps.

References

Henry Berthold Mann </ref> was a professor of mathematics and statistics at Ohio State University. Mann proved the Schnirelmann-Landau conjecture in number theory, and as a result earned the 1946 Cole Prize. He and his student developed the ("Mann-Whitney") U-statistic of nonparametric statistics. Mann published the first mathematical book on the design of experiments Mann (1949).

International Standard Book Number Unique numeric book identifier

The International Standard Book Number (ISBN) is a numeric commercial book identifier which is intended to be unique. Publishers purchase ISBNs from an affiliate of the International ISBN Agency.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.