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 Free Access

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?)


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
Email: znedev@gmail.com

DOI: https://doi.org/10.1090/S0025-5718-09-02237-6
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.