Lower bound for balanced sets
Let \(S\) be a non-empty subset of \(\mathbb Z/p\mathbb Z\), where \(p\) is an odd prime. We call \(S\) \textit{balanced} if for every \(x \in S\) there are distinct elements \(y, z \in S\) such that \(x = (y+z)/2\). This is a curious condition that arises in combinatorial game theory but appears to be of independent interest. Probabilistically one expects that a set of size \(\gg \sqrt{p \log p}\) will typically be balanced. It is then natural to consider the \textit{minimum} cardinality \(\alpha(p)\) among all balanced subsets of \(\mathbb Z/p\mathbb Z\). A theorem of \textit{J. Browkin, B. Diviš} and \textit{A. Schinzel} [Monatsh. Math. 82, 261--268 (1976; Zbl 0349.12012)] shows that \(\alpha(p) > \log_2(p) + 1\). In the converse direction, the author has shown in [Math. Comput. 78, No. 268, 2259--2267 (2009; Zbl 1223.11153)] that this lower bound is in fact asymptotically optimal in the sense that \(\alpha(p) \leq (1 + o(1)) \log_2(p)\). Thus, minimal balanced sets are far, far smaller than typical ones. In the present note, the author continues the study of minimal balanced sets, improving the lower bound slightly to \(\alpha(p) > \log_2(p) + 1.41\). The methods are elementary, making clever use of linear algebra together with a determinantal inequality of \textit{Ch. R. Johnson} and \textit{M. Newman} [Math. Ann. 247, 179--186 (1980; Zbl 0407.15009)]. The proof further shows that a stronger bound \(\alpha(p) > \log_2(p) + 2\) holds unless every \(x \in S\) admits a unique representation as \((y+z)/2\). Some closely related open questions are given in the concluding section.
- Balanced minimum covers of a finite set
- scientific article; zbMATH DE number 3876428
- On linear balancing sets
- Upper bounds on minimum balanced bipartitions
- Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
- Balanced subset sums in dense sets of integers
- scientific article; zbMATH DE number 4195978
- scientific article; zbMATH DE number 6302886
- Balanced 2-subsets
- An algorithm for finding a nearly minimal balanced set in \(\mathbb{F}_p\)
- A surprising determinantal inequality for real matrices
- Addition of sequences in general fields
- An \(O(n)\)-round strategy for the Magnus-Derek game
- An algorithm for finding a nearly minimal balanced set in \(\mathbb{F}_p\)
- BALANCED SETS AND THE VECTOR GAME
- The Magnus-Derek game
- Universal sets and the vector game
- On balanced sets mod p
- The maximum number of balancing sets
- Unique differences in symmetric subsets of F_p
- Balanced and absorbing subsets with empty interior
- Unique sums and differences in finite abelian groups
- \(L\)-balancing families
- Balanced minimum covers of a finite set
- An algorithm for finding a nearly minimal balanced set in \(\mathbb{F}_p\)
- On sets whose subsets have integer mean
- scientific article; zbMATH DE number 3190563 (Why is no real title available?)
- Balanced 2-subsets
This page was built for publication: Lower bound for balanced sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690486)
