Combinatorial number theory deals with
number theoretic problems which involve
combinatorial
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 ...
ideas in their formulations or solutions.
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 ...
is the main founder of this branch of number theory. Typical topics include
covering system
In mathematics, a covering system (also called a complete residue system) is a collection
:\
of finitely many residue classes
: a_i\pmod = \,
whose union contains every integer.
Examples and definitions
The notion of covering system was i ...
,
zero-sum problem
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 ...
s, various
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 ...
s, and
arithmetic progression
An arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called common difference of that ...
s in a set of integers. Algebraic or analytic methods are powerful in this field.
In combinatorial number theory, the barycentric-sum problems are questions that can be answered using combinatorial techniques. The context of barycentric-sum problems are the barycentric sequences.
Example
Let
be the
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 ...
of integers modulo ''n''. Let ''S'' be a sequence of elements of
, where the repetition of elements is allowed. Let
be the length of ''S''. A sequence
with
is barycentric or has a
barycentric-sum if it contains one element
such that
.
Informally, if
contains one element
, which is the ”average” of its terms. A barycentric sequence of length
is called a t-barycentric sequence. Moreover, when ''S'' is a set, the term barycentric set is used instead of barycentric sequence. For example, the set
is 5-barycentric with barycenter 2, however the set {0,2,3,4,5}
is not 5-barycentric. The barycentric-sum problem consist in finding the smallest integer ''t'' such that any sequence of length ''t'' contains a ''k''-barycentric sequence for some given ''k''. The study of the existence of such t related with k and the study of barycentric constants are part of the barycentric-sum problems. It has been introduced by Ordaz, inspired in a theorem of Hamidoune: every sequence of length
in
contains a k-barycentric sequence. Notice that a ''k''-barycentric sequence in
, with k a multiple of n, is a sequence with zero-sum. The
zero-sum problem
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 ...
on sequences started in 1961 with the Erdős, Ginzburg and Ziv theorem: every sequence of length
in an
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 ...
of order ''n'', contains an ''n''-subsequence with zero-sum.
Barycentric-sum problems have been defined in general for finite abelian groups. However, most of the main results obtained up to now are in
.
The barycentric constants introduced by Ordaz are:
[C. Guia, F. Losavio, O. Ordaz M.T. Varela and F. Villarroel, Barycentric Davenport constants. To appear in Divulgaciones Matemáticas.] ''k''-barycentric Olson constant, ''k''-barycentric
Davenport constant
In mathematics, the Davenport constant is an invariant of a group studied in additive combinatorics, quantifying the size of nonunique factorizations. Given a finite abelian group , is defined as the smallest number such that every sequence of ...
, barycentric Davenport constant, generalized barycentric Davenport constant, constrained barycentric Davenport constant. This constants are related to the Davenport constant i.e. the smallest integer ''t'' such that any ''t''-sequence contains a
subsequence
In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence \langle A,B,D \rangle is a ...
with zero-sum. Moreover, related to the classical
Ramsey numbers
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (sa ...
, the barycentric Ramsey numbers are introduced. An overview of the results computed manually or automatically are presented.
[L. González, F. Losavio, O. Ordaz, M.T. Varela and F. Villarroel. Barycentric Integers sequences. Sumited to Expositiones Mathematicae.] The implemented algorithms are written in C.
[F. Villarroel, Tesis Doctoral en Matemática. La constante de Olson k baricéntrica y un teorema inverso de Erdős-Ginzburg-Ziv. Facultad de Ciencias. Universidad Central de Venezuela, (2008).]
References
External links
Divulgacions Matemáticas (Spanish)
Combinatorics