Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Finding finite $ B\sb 2$-sequences with larger $ m-a\sp {1/2}\sb m$

Author: Zhen Xiang Zhang
Journal: Math. Comp. 63 (1994), 403-414
MSC: Primary 11Y55; Secondary 11B75
MathSciNet review: 1223235
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A sequence of positive integers $ {a_1} < {a_2} < \cdots < {a_m}$ is called a (finite) $ {B_2}$-sequence, or a (finite) Sidon sequence, if the pairwise differences are all distinct. Let

$\displaystyle K(m) = \max (m - a_m^{1/2}),$

where the maximum is taken over all m-element $ {B_2}$-sequences. Erdős and Turán ask if $ K(m) = O(1)$. In this paper we give an algorithm, based on the Bose-Chowla theorem on finite fields, for finding a lower bound of $ K(p)$ and a p-element $ {B_2}$-sequence with $ p - a_p^{1/2}$ equal to this bound, taking $ O({p^3}{\log ^2}pK(p))$ bit operations and requiring $ O(p\log p)$ storage, where p is a prime. A search for lower bounds of $ K(p)$ for $ p \leq {p_{145}}$ is given, especially $ K({p_{145}}) > 10.279$, where $ {p_i}$ is the ith prime.

References [Enhancements On Off] (What's this?)

  • [1] R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (1962-63), 141-147. MR 0144877 (26:2418)
  • [2] P. Erdős and P. Turán, On a problem of Sidon in additive number theory and on some related problems, J. London. Math. Soc. 16 (1941), 212-215; Addendum, 19 (1944), 208. MR 0006197 (3:270e)
  • [3] Richard K. Guy, Unsolved problems in number theory, Springer-Verlag, New York, 1981. MR 656313 (83k:10002)
  • [4] H. Halberstam and K. F. Roth, Sequences, Oxford Univ. Press, New York, 1966. MR 0210679 (35:1565)
  • [5] D. E. Knuth, The art of computer programming: Semi-numerical algorithms, Vol. 2, 2nd ed., Addison-Wesley, Reading, MA, 1981. MR 0378456 (51:14624)
  • [6] B. Lindstrom, An inequality for $ {B_2}$-sequences, J. Combin. Theory 6 (1969), 211-212. MR 0236138 (38:4436)
  • [7] H. Riesel, Prime numbers and computer methods for factorization, Birkhäuser, Boston, 1985. MR 897531 (88k:11002)
  • [8] K. H. Rosen, Elementary number theory and its applications, Addison-Wesley, Reading, MA, 1984. MR 1739433 (2000i:11001)
  • [9] J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), 377-385. MR 1501951
  • [10] B. L. Van der Waerden, Modern algebra, English transl., Ungar, New York, 1949.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y55, 11B75

Retrieve articles in all journals with MSC: 11Y55, 11B75

Additional Information

Keywords: $ {B_2}$-sequences, Erdős-Turán conjecture, Bose-Chowla theorem, finite fields, algorithms
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society