Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



An algorithm for finding a nearly minimal balanced set in $ \mathbb{F}_p$

Author: Zhivko Nedev
Journal: Math. Comp. 78 (2009), 2259-2267
MSC (2000): Primary 11Y16
Published electronically: March 26, 2009
MathSciNet review: 2521288
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Browkin, J., Diviš, B., and Schinzel, A., Addition of sequences in general fields, Monatshefte für Mathematik 82, pp. 261-268, 1976. MR 0432581 (55:5568)
  • 2. Johnson, Charles R. and Newman, Morris, A surprising determinantal inequality for real matrices, Math. Ann. 247, pp. 179-186, 1980. MR 568207 (83h:15005)
  • 3. Nedev, Zhivko, Lower bound for balanced sets, preprint.
  • 4. Nedev, Zhivko, Universal sets and the vector game, INTEGERS: The Electronic Journal of Combinatorial Number Theory, 8 (2008), #A45.
  • 5. Nedev, Zhivko and and Muthukrishnan, S., The Magnus-Derek Game, Theoretical Computer Science, Volume 393, Issues 1-3, 20 March 2008, pp. 124-132. MR 2397246
  • 6. Nedev, Zhivko and Quas, Anthony, Balanced sets and the vector game, International Journal of Number Theory, 4 (2008), pp. 339-347. MR 2424326
  • 7. Straus, E. G., Differences of residues $ \pmod p$, Journal of Number Theory 8, pp. 40-42, 1976. MR 0392876 (52:13689)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16

Retrieve articles in all journals with MSC (2000): 11Y16

Additional Information

Zhivko Nedev
Affiliation: Department of Mathematics and Statistics, University of Victoria, P.O. Box 3060, STN CSC, Victoria, B.C., Canada V8W 3R4

Received by editor(s): April 25, 2008
Received by editor(s) in revised form: October 29, 2008
Published electronically: March 26, 2009
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society