Lower bound for balanced sets (Q690486)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lower bound for balanced sets |
scientific article |
Statements
Lower bound for balanced sets (English)
0 references
27 November 2012
0 references
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.
0 references
balanced sets
0 references