Sum-Free Sequence¶

A strictly increasing sequence of positive integers in which no term is representable as a sum of a subset of its predecessors, coupling prefix-dependent additive avoidance to sparse-growth and reciprocal-sum questions.

Version: v1 · 2026-08-30 · History
Domain-specific #: 2894
Origin domain: number theory
Subdomain: additive combinatorics
Aliases: Strongly sum-free sequence

Core Idea¶

A sum-free sequence in this number-theoretic sense is a strictly increasing sequence of positive integers

\[ a_1<a_2<a_3<\cdots \]

such that for every \(n\), the term \(a_n\) is not a sum of any subset of its predecessors:

\[ a_n\notin \left\{\sum_{i\in I}a_i:I\subseteq\{1,\ldots,n-1\}\right\}. \]

Because the terms are distinct, this is equivalently avoidance of sums of distinct smaller sequence elements. Deshouillers, Erdős, and Melfi use this exact prefix/subset-sum identity and study how slowly such a sequence can grow.^[1]

The adjective does not mean merely that no pair of elements sums to a third. Every forbidden subset may have any finite size, and only predecessors of the target are available. The sequence's order is therefore constitutive, although strict increase makes the same condition expressible as “no element is the sum of distinct smaller elements.” The abstraction organizes additive avoidance, density, growth, and reciprocal-sum extremal questions.

Structural Signature¶

Positive integers: every term lies in \(\mathbb N_{>0}\).
Strict increase: \(a_1<a_2<\cdots\), giving a unique predecessor prefix for each term.
Finite prefix: the admissible summands for \(a_n\) are \(a_1,\ldots,a_{n-1}\).
Subset selection: each predecessor can be used at most once.
Empty-subset convention: its sum is zero and cannot equal a positive term.
Forbidden equality: no selected predecessor subset has sum \(a_n\).
Global recurrence of the test: the exclusion holds at every index.
Counting function: \(A(x)=|\{a_n:a_n\le x\}|\) measures sparsity.
Reciprocal sum: \(\sum_n 1/a_n\) measures global size on a harmonic scale.
Construction or bound: examples and theorems analyze how densely the exclusion can be sustained.

The identity is the all-subsets prefix exclusion. Growth bounds, zero density, and convergent reciprocal sum are consequences or research directions, not extra defining axioms.

What It Is Not¶

It is not a sum-free set in the standard additive-combinatorics sense \(A\cap(A+A)=\varnothing\), which forbids pair sums and may allow repeated summands depending on convention. A set can avoid pair sums yet contain one element equal to a sum of three distinct smaller elements; it then fails the present sequence condition.

It is not a zero-sum-free sequence over a finite abelian group, where no nonempty subsequence sums to the identity. Here the forbidden target is another positive term of the same increasing sequence, not zero modulo a group. It is not a Sidon sequence, whose constraint concerns equality of two pair sums. It is not simply a superincreasing sequence: \(a_n>\sum_{i<n}a_i\) is a sufficient construction rule, but the sum-free condition can hold without that stronger inequality.

Scope of Application¶

The abstraction belongs to additive number theory and extremal integer-sequence research. Questions include reciprocal-sum maxima, counting-function bounds, possible polynomial growth, and gaps \(a_{n+1}-a_n\). Deshouillers, Erdős, and Melfi prove the existence of polynomial-growth examples with successive-term ratio tending to one, showing that sum-free sequences need not look exponentially spaced.^[1]

Levine's extremal result studies sequences in which no term is a sum of distinct other terms and proves a sharp asymptotic reciprocal-sum bound when the first term is constrained.^[2] These results demonstrate a stable literature identity beyond a single puzzle. Finite prefixes also qualify when the exclusion is stated through their final index, but asymptotic density and reciprocal-sum claims apply only to infinite sequences.

The same definition supports both constructive and extremal programs. A constructive question asks how to choose the next legal integer while preserving a desired growth profile. An extremal question fixes information such as the first term and asks how large a counting function or reciprocal sum can become. These are different uses of one abstraction: neither a particular construction algorithm nor a particular sharp bound is part of the identity. This distinction also prevents the node from collapsing into a named sequence entry, since many nonisomorphic sequences satisfy the same recognition rule.

Clarity¶

The powers of two

\[ 1,2,4,8,16,\ldots \]

form a sum-free sequence because

\[ 2^n=1+\sum_{j=0}^{n-1}2^j \]

is one larger than the sum of all preceding powers. Therefore no subset of predecessors can reach \(2^n\).

By contrast, \(1,3,4,10,\ldots\) fails at the third term because \(4=1+3\). The pair \(1+3\) is a predecessor subset. The sequence \(2,3,6,\ldots\) passes its first three positions: the available subset sums before \(6\) are \(0,2,3,5\). Passing a finite prefix does not prove an arbitrary continuation will remain sum-free.

Manages Complexity¶

Naively, testing \(a_n\) appears to require enumerating \(2^{n-1}\) predecessor subsets. The abstraction separates identity from algorithms: dynamic subset-sum methods, generating functions, modular arguments, or sufficient growth conditions can certify avoidance without listing every subset.

At the research level, the definition compresses a tension between additive richness and sequence density. A dense collection has many subset sums and is more likely to represent a later element; a sparse collection avoids collisions but yields small reciprocal mass. Counting functions and reciprocal sums make this tension measurable.

Abstract Reasoning¶

For a finite prefix define its subset-sum set

\[ \Sigma_{n-1}= \left\{\sum_{i\in I}a_i:I\subseteq\{1,\ldots,n-1\}\right\}. \]

Then legality of the next term is exactly \(a_n\notin\Sigma_{n-1}\), together with \(a_n>a_{n-1}\). When \(a_n\) is added, the new subset-sum set is

\[ \Sigma_n=\Sigma_{n-1}\cup(a_n+\Sigma_{n-1}). \]

This recurrence exposes why the constraint becomes harder: each accepted term translates the prior reachable set and unions it with the original. Collisions can reduce cardinality, but the reachable region generally expands. Superincreasing sequences force the two portions into disjoint intervals, yielding an easy sufficient certificate but not a necessary characterization.

Knowledge Transfer¶

The portable pattern is prefix-generated forbidden set + choose the next element outside it. Similar online constructions occur in coding, combinatorial designs, and conflict-free scheduling. Literal transfer requires a commutative sum operation, one-use predecessor selection, strict order, and avoidance of the generated subset-sum set.

The candidate does not rise to prime status because its mathematical operation and integer-order assumptions are constitutive. Generic Constraint and Sequencing capture parts of the skeleton, while the additive subset-sum closure is the domain-specific residue.

Examples¶

Powers of two: a superincreasing boundary case with reciprocal sum \(2\) when starting at \(1\).
Any superincreasing sequence: if \(a_n>\sum_{i<n}a_i\), the subset-sum exclusion follows immediately.
Failure \(1,3,4\): the term \(4\) equals a sum of predecessors.
Higher-cardinality failure: a sequence may avoid pair representations but fail because one term is a sum of three predecessors.
Polynomial-growth constructions: demonstrate that exponential gaps are not required.^[1]
Finite verification: a bitset of reachable subset sums can test proposed prefixes exactly.

Structural Tensions¶

Local extension vs. global density. Each next-step exclusion is finite, but repeated exclusions govern asymptotic sparsity. Diagnostic: separate a prefix certificate from an infinite growth claim.
Pair-sum language vs. all subsets. Familiar “sum-free” terminology can hide higher-cardinality sums. Diagnostic: test subsets of every size, not only pairs.
Easy sufficient rule vs. full class. Superincreasing growth guarantees legality but excludes denser examples. Diagnostic: do not promote the sufficient inequality to the definition.
Set vs. sequence order. Strict increase makes predecessors equal smaller elements, but order supplies the recognition procedure. Diagnostic: identify the target's smaller admissible summands explicitly.
Autonomous sequence type vs. Constraint plus Sequencing. Generic nodes do not entail subset-sum closure or positive-integer sparsity consequences. Diagnostic: subtract the parents and require the all-distinct-predecessor-sums exclusion.

Structural–Framed Character¶

The structural core is an ordered extension process that avoids a forbidden closure generated by the prefix. The frame is additive number theory: positive integers, subset sums, counting functions, density, gaps, and harmonic-size measures.

The candidate is a domain-specific abstraction. Its recognition criterion recurs across mathematical constructions, but removing integer addition changes the identity rather than merely its accent.

Structural Core vs. Domain Accent¶

Structural core: an ordered collection, a prefix-generated reachability set, an exclusion test for each new term, and long-run sparsity questions.

Domain accent: strictly increasing positive integers, finite subset sums of distinct predecessors, reciprocal series, Schnirelmann/counting density, and additive extremal bounds.

Sum-Free Sequence compositionally presupposes Constraint: at each index, the next integer must lie outside the subset-sum closure of the predecessor prefix. It is not a specialization of Local Sequence Legality because the constraint can depend on the entire prefix rather than a fixed-size window. Sequencing is related, but Constraint is the minimal direct endpoint that remains literal.

Relationships to Other Abstractions¶

Current abstraction Sum-Free Sequence Domain-specific

Parents (1) — more general patterns this builds on

Sum-Free Sequence presupposes Constraint Prime

Sum-Free Sequence compositionally presupposes Constraint: at each index, the next integer must lie outside the subset-sum closure of the predecessor prefix.

Hierarchy path (1) — routes to 1 parentless root

Sum-Free Sequence → Constraint

Neighborhood in Abstraction Space¶

Sum-Free Sequence sits in a sparse region of the domain-specific corpus (82^nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Additive Number Theory & Series Tests (6 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Sum-free set: forbids pair sums within a set.
Zero-sum-free sequence: forbids a subsequence summing to a group identity.
Sidon sequence: requires uniqueness of pair-sum representations.
Superincreasing sequence: satisfies a stronger sufficient growth inequality.
Complete sequence: eventually represents all sufficiently relevant integers by subset sums, an opposing additive-richness notion.
Primitive sequence: forbids divisibility among distinct terms rather than additive representation.

References¶

[1] Jean-Marc Deshouillers, Paul Erdős, and Giuseppe Melfi, “On a Question about Sum-Free Sequences,” Discrete Mathematics 200 (1999), 49–54, DOI: 10.1016/S0012-365X(98)00322-7. registry ↩a ↩b ↩c

[2] Eugene Levine, “An Extremal Result for Sum-Free Sequences,” Journal of Number Theory 12 (1980), 251–257, DOI: 10.1016/0022-314X(80)90061-X. registry ↩