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

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