A sequence of positive integers
 |
(1)
|
is a nonaveraging sequence in the sense used here if no three distinct terms form an arithmetic progression. Equivalently,
there are no distinct 
, 
, 
such that
 |
(2)
|
Sets with this property are also called Salem-Spencer sets, 3-AP-free sets, and progression-free sets (Salem and Spencer 1942, Dybizbański 2012). The empty set and one-element sets are therefore trivially nonaveraging.
The terminology is not uniform. Wróblewski (1984) calls a set nonaveraging when no member is the arithmetic mean of two distinct other members, as above. Abbott (1980), however, calls a set nonaveraging when no member is the arithmetic mean of any two or more distinct other members. Abbott's condition is therefore stronger.
Consider all subsets of 
. There is one nonaveraging sequence on 
(
), two on 
(
and 
), four on 
, and so on. For example, 13 of the 16 subsets of 
are nonaveraging, with 
, 
, and 
excluded. The numbers of nonaveraging subsets on 
, 
, ... are 1, 2, 4, 7, 13, 23, 40, ... (OEIS A051013).
Let 
be the largest cardinality of a nonaveraging subset
of 
.
The values of 
for 
,
1, ... are 0, 1, 2, 2, 3, 4, 4, 4, 4, 5, ... (OEIS A003002).
Equivalently, the smallest values of 
for which 
has a nonaveraging subset of cardinality 
, for 
, 2, ..., are 1, 2, 4, 5, 9, 11, 13, 14, 20, ... (OEIS A065825). If 
denotes the latter sequence, then 
exactly when 
.
For each 
,
5, ..., 43, the illustration above shows one nonaveraging subset of 
having cardinality 
. Each row is centered at the midpoint of its smallest and
largest elements, with the endpoints shown in red. The labels at left give 
, and those at right give 
. These representatives need not be unique.
The study of 
was initiated by Erdős and Turán (1936), who conjectured both that 
and that 
for some 
. Salem and Spencer (1942) disproved the latter conjecture
by showing that 
for sufficiently large 
. Behrend (1946) improved this lower bound to 
. In the opposite direction, Roth
(1952, 1953) proved the upper bound 
, and therefore established the first conjecture.
The positive constants in these bounds need not be the same (Dybizbański 2012).
Wróblewski (1984) showed that for infinite nonaveraging sequences,
 |
(3)
|
Terms." Proc. Amer. Math. Soc. 62, 211-214,
1977.Gerver, J. L. and Ramsey, L. "Sets of Integers with no
Long Arithmetic Progressions Generated by the Greedy Algorithm." Math. Comput. 33,
1353-1360, 1979.Guy, R. K. "Nonaveraging Sets. Nondividing
Sets." §C16 in