Sum-free sequence

Last updated

In mathematics, a sum-free sequence is an increasing sequence of positive integers,

Contents

such that no term can be represented as a sum of any subset of the preceding elements of the same sequence.

This differs from a sum-free set, where only pairs of sums must be avoided, but where those sums may come from the whole set rather than just the preceding terms.

Example

The powers of two,

1, 2, 4, 8, 16, ...

form a sum-free sequence: each term in the sequence is one more than the sum of all preceding terms, and so cannot be represented as a sum of preceding terms.

Sums of reciprocals

A set of integers is said to be small if the sum of its reciprocals converges to a finite value. For instance, by the prime number theorem, the prime numbers are not small. PaulErdős  ( 1962 ) proved that every sum-free sequence is small, and asked how large the sum of reciprocals could be. For instance, the sum of the reciprocals of the powers of two (a geometric series) is two.

If denotes the maximum sum of reciprocals of a sum-free sequence, then through subsequent research it is known that . [1]

Density

It follows from the fact that sum-free sequences are small that they have zero Schnirelmann density; that is, if is defined to be the number of sequence elements that are less than or equal to , then . Erdős (1962) showed that for every sum-free sequence there exists an unbounded sequence of numbers for which where is the golden ratio, and he exhibited a sum-free sequence for which, for all values of , , subsequently improved to by Deshouillers, Erdős and Melfi in 1999 and to by Luczak and Schoen in 2000, who also proved that the exponent 1/2 cannot be furthermore improved.

Notes

Related Research Articles

In mathematics, a Sobolev space is a vector space of functions equipped with a norm that is a combination of Lp-norms of the function together with its derivatives up to a given order. The derivatives are understood in a suitable weak sense to make the space complete, i.e. a Banach space. Intuitively, a Sobolev space is a space of functions possessing sufficiently many derivatives for some application domain, such as partial differential equations, and equipped with a norm that measures both the size and regularity of a function.

Klaus Roth British mathematician

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 mathematics, Property B is a certain set theoretic property. Formally, given a finite set X, a collection C of subsets of X, has Property B if we can partition X into two disjoint subsets Y and Z such that every set in C meets both Y and Z.

Giuseppe Melfi

Giuseppe Melfi is an Italo-Swiss mathematician who works on practical numbers and modular forms.

Sylvesters sequence

In number theory, Sylvester's sequence is an integer sequence in which each term of the sequence is the product of the previous terms, plus one. The first few terms of the sequence are

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 and combinatorics, a restricted sumset has the form

In combinatorics, a Davenport–Schinzel sequence is a sequence of symbols in which the number of times any two symbols may appear in alternation is limited. The maximum possible length of a Davenport–Schinzel sequence is bounded by the number of its distinct symbols multiplied by a small but nonconstant factor that depends on the number of alternations that are allowed. Davenport–Schinzel sequences were first defined in 1965 by Harold Davenport and Andrzej Schinzel to analyze linear differential equations. Following Atallah (1985) these sequences and their length bounds have also become a standard tool in discrete geometry and in the analysis of geometric algorithms.

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.

András Hajnal was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.

The Jurkat–Richert theorem is a mathematical theorem in sieve theory. It is a key ingredient in proofs of Chen's theorem on Goldbach's conjecture. It was proved in 1965 by Wolfgang B. Jurkat and Hans-Egon Richert.

In discrete geometry, the Erdős distinct distances problem states that every set of points in the plane has a nearly-linear number of distinct distances. It was posed by Paul Erdős in 1946 and almost proven by Larry Guth and Nets Katz in 2015.

In mathematics, a sequence of positive integers an is called an irrationality sequence if it has the property that for every sequence xn of positive integers, the sum of the series

Gradient discretisation method

In numerical mathematics, the gradient discretisation method (GDM) is a framework which contains classical and recent numerical schemes for diffusion problems of various kinds: linear or non-linear, steady-state or time-dependent. The schemes may be conforming or non-conforming, and may rely on very general polygonal or polyhedral meshes.

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 additive number theory, an area of mathematics, the Erdős–Tetali theorem is an existence theorem concerning economical additive bases of every order. More specifically, it states that for every fixed integer , there exists a subset of the natural numbers satisfying

The Erdős–Tenenbaum–Ford constant is a mathematical constant that appears in number theory. Named after mathematicians Paul Erdős, Gérald Tenenbaum, and Kevin Ford, it is defined as

In number theory, the prime omega functions and count the number of prime factors of a natural number Thereby counts each distinct prime factor, whereas the related function counts the total number of prime factors of honoring their multiplicity. For example, if we have a prime factorization of of the form for distinct primes , then the respective prime omega functions are given by and . These prime factor counting functions have many important number theoretic relations.

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.

References