Erdős–Heilbronn Conjecture
   HOME

TheInfoList



OR:

In
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 semigro ...
and
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
, a restricted sumset has the form :S=\, where A_1,\ldots,A_n are finite
nonempty In mathematics, the empty set or void set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, whi ...
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
s of a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
''F'' and P(x_1,\ldots,x_n) is a
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
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 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- ...
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 Baron Augustin-Louis Cauchy ( , , ; ; 21 August 1789 – 23 May 1857) was a French mathematician, engineer, and physicist. He was one of the first to rigorously state and prove the key theorems of calculus (thereby creating real a ...
and
Harold Davenport Harold Davenport FRS (30 October 1907 – 9 June 1969) was an English mathematician, known for his extensive work in number theory. Early life and education Born on 30 October 1907 in Huncoat, Lancashire, Davenport was educated at Accringto ...
, asserts that for any
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
''p'' and nonempty subsets ''A'' and ''B'' of the prime
order Order, ORDER or Orders may refer to: * A socio-political or established or existing order, e.g. World order, Ancien Regime, Pax Britannica * Categorization, the process in which ideas and objects are recognized, differentiated, and understood ...
cyclic group In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
\mathbb/p\mathbb we have the
inequality Inequality may refer to: * Inequality (mathematics), a relation between two quantities when they are different. * Economic inequality, difference in economic well-being between population groups ** Income inequality, an unequal distribution of i ...
Geroldinger & Ruzsa (2009) pp.141–142 :, A+B, \ge \min\ where A+B := \, i.e. we're using
modular arithmetic In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to mo ...
. It can be generalised to arbitrary (not necessarily abelian) groups using a Dyson transform. If A, B are subsets of a group G, then :, A+B, \ge \min\ where p(G) is the size of the smallest nontrivial subgroup of G (we set it to 1 if there is no such subgroup). We may use this to deduce the
Erdős–Ginzburg–Ziv theorem 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'' s ...
: given any sequence of 2''n''−1 elements in the cyclic group \mathbb/n\mathbb, there are ''n'' elements that sum to zero modulo ''n''. (Here ''n'' does not need to be prime.)Geroldinger & Ruzsa (2009) p.53 A direct consequence of the Cauchy-Davenport theorem is: Given any sequence ''S'' of ''p''−1 or more nonzero elements, not necessarily distinct, of \mathbb/p\mathbb, every element of \mathbb/p\mathbb can be written as the sum of the elements of some subsequence (possibly empty) of ''S''. Kneser's theorem generalises this to general
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 commu ...
s.Geroldinger & Ruzsa (2009) p.143


Erdős–Heilbronn conjecture

The Erdős–Heilbronn conjecture posed by
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
Hans Heilbronn Hans Arnold Heilbronn (8 October 1908 – 28 April 1975) was a mathematician. Education He was born into a German-Jewish family. He was a student at the universities of Berlin, Freiburg and Göttingen, where he met Edmund Landau, who supervis ...
in 1964 states that , 2^\wedge A, \ge \min\ if ''p'' is a prime and ''A'' is a nonempty subset of the field Z/''p''Z. This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994 who showed that :, n^\wedge A, \ge \min\, where ''A'' is a finite nonempty subset of a field ''F'', and ''p''(''F'') is a prime ''p'' if ''F'' is of characteristic ''p'', and ''p''(''F'') = ∞ if ''F'' is of characteristic 0. Various extensions of this result were given by
Noga Alon Noga Alon (; born 1956) is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers. Education and career ...
, M. B. Nathanson and I. Ruzsa in 1996, Q. H. Hou and
Zhi-Wei Sun Sun Zhiwei (, born October 16, 1965) is a Chinese mathematician, working primarily in number theory, combinatorics, and group theory. He is a professor at Nanjing University. Biography Sun Zhiwei was born in Huai'an, Jiangsu. Sun and his twin ...
in 2002, and G. Karolyi in 2004.


Combinatorial Nullstellensatz

A powerful tool in the study of lower bounds for
cardinalities In mathematics, the cardinality of a finite set is the number of its elements, and is therefore a measure of size of the set. Since the discovery by Georg Cantor, in the late 19th century, of different sizes of infinite sets, the term ''cardinal ...
of various restricted sumsets is the following fundamental principle: the combinatorial Nullstellensatz. Let f(x_1,\ldots,x_n) be a polynomial over a field F. Suppose that the
coefficient In mathematics, a coefficient is a Factor (arithmetic), multiplicative factor involved in some Summand, term of a polynomial, a series (mathematics), series, or any other type of expression (mathematics), expression. It may be a Dimensionless qu ...
of the
monomial In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered: # A monomial, also called a power product or primitive monomial, is a product of powers of variables with n ...
x_1^\cdots x_n^ in f(x_1,\ldots,x_n) is nonzero and k_1+\cdots+k_n is the total degree of f(x_1,\ldots,x_n). If A_1,\ldots,A_n are finite subsets of F with , A_i, >k_i for i=1,\ldots,n, then there are a_1\in A_1,\ldots,a_n\in A_n such that f(a_1,\ldots,a_n)\not = 0 . This tool was rooted in a paper of N. Alon and M. Tarsi in 1989, and developed by Alon, Nathanson and Ruzsa in 1995–1996, and reformulated by Alon in 1999.


See also

*
Polynomial method in combinatorics In mathematics, the polynomial method is an algebraic approach to combinatorics problems that involves capturing some combinatorial structure using polynomials and proceeding to argue about their algebraic properties. Recently (around 2016), the pol ...


References

* *


External links

*{{mathworld , urlname = Erdos-HeilbronnConjecture , title = Erdős-Heilbronn Conjecture Augustin-Louis Cauchy Sumsets Additive combinatorics Additive number theory