An algorithm for finding a nearly minimal balanced set in 𝔽_{𝕡}

Nedev, Zhivko

doi:10.1090/S0025-5718-09-02237-6

An algorithm for finding a nearly minimal balanced set in $\mathbb {F}_p$
HTML articles powered by AMS MathViewer

by Zhivko Nedev;

Math. Comp. 78 (2009), 2259-2267

DOI: https://doi.org/10.1090/S0025-5718-09-02237-6

Published electronically: March 26, 2009

PDF | Request permission

Abstract:

For a prime $p$, we call a non-empty subset $S$ of the group $\mathbb {F}_p$ balanced if every element of $S$ is the midterm of a three-term arithmetic progression, contained in $S$. A result of Browkin, Diviš and Schinzel implies that the size of a balanced subset of $\mathbb {F}_p$ is at least $\log _{2} p + 1$. In this paper we present an efficient algorithm which yields a balanced set of size $(1 + o(1)) \log _{2} p$ as $p$ grows.

References

J. Browkin, B. Diviš, and A. Schinzel, Addition of sequences in general fields, Monatsh. Math. 82 (1976), no. 4, 261–268. MR 432581, DOI 10.1007/BF01540597
Charles R. Johnson and Morris Newman, A surprising determinantal inequality for real matrices, Math. Ann. 247 (1980), no. 2, 179–185. MR 568207, DOI 10.1007/BF01364143
Nedev, Zhivko, Lower bound for balanced sets, preprint.
Nedev, Zhivko, Universal sets and the vector game, INTEGERS: The Electronic Journal of Combinatorial Number Theory, 8 (2008), #A45.
Z. Nedev and S. Muthukrishnan, The Magnus-Derek game, Theoret. Comput. Sci. 393 (2008), no. 1-3, 124–132. MR 2397246, DOI 10.1016/j.tcs.2007.11.016
Zhivko Nedev and Anthony Quas, Balanced sets and the vector game, Int. J. Number Theory 4 (2008), no. 3, 339–347. MR 2424326, DOI 10.1142/S179304210800133X
E. G. Straus, Differences of residues $(\textrm {mod}\ p)$, J. Number Theory 8 (1976), no. 1, 40–42. MR 392876, DOI 10.1016/0022-314X(76)90019-6