Sum-free sets of integers with a forbidden sum

DOI10.1137/17M1157532zbMATH Open1440.11008arXiv1812.09594OpenAlexW2963332323MaRDI QIDQ4627481FDOQ4627481

Authors: Ishay Haviv 

Publication date: 11 March 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: A set of integers is sum-free if it contains no solution to the equation $x+y=z$. We study sum-free subsets of the set of integers $[n]=1,ldots,n$ for which the integer $2n+1$ cannot be represented as a sum of their elements. We prove a bound of $O(2^{n/3})$ on the number of these sets, which matches, up to a multiplicative constant, the lower bound obtained by considering all subsets of $B_n=lceilfrac23(n+1)ceil,ldots,n$. A main ingredient in the proof is a stability theorem saying that if a subset of $[n]$ of size close to $|B_n|$ contains only a few subsets that contradict the sum-freeness or the forbidden sum, then it is almost contained in $B_n$. Our results are motivated by the question of counting symmetric complete sum-free subsets of cyclic groups of prime order. The proofs involve Freiman's $3k-4$ theorem, Green's arithmetic removal lemma, and structural results on independent sets in hypergraphs.

Full work available at URL: https://arxiv.org/abs/1812.09594

Recommendations

• scientific article; zbMATH DE number 409908
• Sharp bound on the number of maximal sum-free subsets of integers
• Counting sets of integers, no \(k\) of which sum to another
• Sum-free sets in abelian groups
• On the number and structure of sum-free sets in a segment of positive integers

zbMATH Keywords

sum-free setsadditive combinatoricsforbidden sum

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Additive bases, including sumsets (11B13) Inverse problems of additive number theory, including sumsets (11P70)

Cites Work

• The probabilistic method
• Extremal results for random discrete structures
• Hypergraph containers
• Independent sets in hypergraphs
• On the number of graphs without 4-cycles
• Title not available (Why is that?)
• Counting sum-free sets in abelian groups
• A removal lemma for systems of linear equations over finite fields
• A Szemerédi-type regularity lemma in abelian groups, with applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• THE CAMERON–ERDOS CONJECTURE
• Maximal sum-free sets in finite abelian groups
• Counting independent sets in graphs
• Large sum-free sets in \(\mathbb Z/p\mathbb Z\)
• Subset sums
• Maximal sum-free sets of elements of finite groups
• On sum-free sets modulo \(p\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the structure of a random sum-free set
• Counting sets with small sumset and applications
• Title not available (Why is that?)
• On the structure of large sum-free sets of integers
• A refined bound for sum-free sets in groups of prime order
• A refinement of the Cameron-Erdős conjecture
• Dioid partitions of groups
• Title not available (Why is that?)
• Structure of maximal sum-free sets in $C_p$
• Symmetric complete sum-free sets in cyclic groups
• Almost Odd Random Sum-Free Sets

Cited In (4)

• The Forbidden Set of
• Title not available (Why is that?)
• Symmetric complete sum-free sets in cyclic groups
• Title not available (Why is that?)

This page was built for publication: Sum-free sets of integers with a forbidden sum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4627481)