When almost all sets are difference dominated
From MaRDI portal
Abstract: We investigate the relationship between the sizes of the sum and difference sets attached to a subset of {0,1,...,N}, chosen randomly according to a binomial model with parameter p(N), with N^{-1} = o(p(N)). We show that the random subset is almost surely difference dominated, as N --> oo, for any choice of p(N) tending to zero, thus confirming a conjecture of Martin and O'Bryant. The proofs use recent strong concentration results. Furthermore, we exhibit a threshold phenomenon regarding the ratio of the size of the difference- to the sumset. If p(N) = o(N^{-1/2}) then almost all sums and differences in the random subset are almost surely distinct, and in particular the difference set is almost surely about twice as large as the sumset. If N^{-1/2} = o(p(N)) then both the sum and difference sets almost surely have size (2N+1) - O(p(N)^{-2}), and so the ratio in question is almost surely very close to one. If p(N) = c N^{-1/2} then as c increases from zero to infinity (i.e., as the threshold is crossed), the same ratio almost surely decreases continuously from two to one according to an explicitly given function of c. We also extend our results to the comparison of the generalized difference sets attached to an arbitrary pair of binary linear forms. For certain pairs of forms f and g, we show that there in fact exists a sharp threshold at c_{f,g} N^{-1/2}, for some computable constant c_{f,g}, such that one form almost surely dominates below the threshold, and the other almost surely above it. The heart of our approach involves using different tools to obtain strong concentration of the sizes of the sum and difference sets about their mean values, for various ranges of the parameter p.
Recommendations
- When almost all sets are difference dominated in \(\mathbb{Z}/n\mathbb{Z}\)
- Almost difference sets and reversible divisible difference sets
- scientific article; zbMATH DE number 3103693
- A generalization of set-difference
- A new family of almost difference sets and some necessary conditions
- A note on difference sets
- Some nonexistence results on generalized difference sets
- scientific article; zbMATH DE number 3817970
- Some new difference sets
- On subsets of partial difference sets
Cites work
- A new look at independence
- Binary linear forms over finite sets of integers
- Concentration of multivariate polynomials and its applications
- Concentration of non‐Lipschitz functions and applications
- Explicit constructions of infinite families of MSTD sets
- Many sets have more sums than differences
- New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
- Problems in additive number theory. I
- Random Sidon sequences
- Sets with more sums than differences
- Some explicit constructions of sets with more sums than differences
Cited in
(22)- On the number of sums and differences
- MSTD sets and Freiman isomorphisms
- A geometric perspective on the MSTD question
- Sets characterized by missing sums and differences in dilating polytopes
- Generalizing the distribution of missing sums in sumsets
- Generalized more sums than differences sets
- When sets can and cannot have sum-dominant subsets
- Fringe pairs in generalized MSTD sets
- Sums and differences of correlated random sets
- Distribution of Missing Differences in Diffsets
- Generalizations of a curious family of MSTD sets hidden by interior blocks
- The union of two arithmetic progressions with the same common difference is not sum-dominant
- Infinite Families of Partitions into MSTD Subsets
- Distribution of Missing Sums in Sumsets
- Almost everywhere domination and superhighness
- When almost all sets are difference dominated in \(\mathbb{Z}/n\mathbb{Z}\)
- The bidirectional ballot polytope
- Sets characterized by missing sums and differences
- Counting MSTD sets in finite abelian groups
- Additional constructions of sequences of alternating sum and difference dominated sets
- Constructing MSTD sets using bidirectional ballot sequences
- Explicit constructions of infinite families of MSTD sets
This page was built for publication: When almost all sets are difference dominated
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3055768)
