Constructing MSTD sets using bidirectional ballot sequences (Q971849): Difference between revisions

An MSTD (More Sums Than Differences) set is finite set \(A\) of integers, such that \(|A+A|>|A-A|\) (in general, because the sum is a commutative operation and difference is not, this type of sets forms a singularity). The first example was found by Conway in the 1960s: \(\{0,2,3,4,7,11,12,14\}\). The author improves another result presented in the same issue of J. Number Theory. In [\textit{S. J. Miller, B. Orosz} and \textit{D. Scheinerman}, J. Number Theory 130, No. 5, 1221--1233 (2010; Zbl 1216.11095)], a construction of an infinite family of MSTD sets, with the density \(\Omega (1/n^4)\) (as subsets of \([1,n]=\{1,2,\dots,n\}\)) was presented. Starting with a similar idea -- a symmetric set augmented by few elements that increase the number of sums more than the number of differences -- the paper makes use of a combinatorial object named \textit{bidirectional ballot sequence} (a 0-1 sequence where every prefix and suffix contain more 1's than 0's). It results an infinite family of MSTD subsets of \([1,n]\) with the density \(\Theta (1/n)\). The paper is very interesting, with many possibilities for sequels. The author suggests some other results, like \(n\Omega(2^n/n)/2^{n-2}\rightarrow 1\), but it claims that ``the proof is rather long and technical'', so it is not presented. Moreover, the last sentence of the paper is ``The asymptotics related to bidirectional ballot sequences are very intriguing, and we hope to generate more interest in these objects''. I agree.