Finding finite $B_ 2$-sequences with larger $m-a^ {1/2}_ m$

Author:
Zhen Xiang Zhang

Journal:
Math. Comp. **63** (1994), 403-414

MSC:
Primary 11Y55; Secondary 11B75

DOI:
https://doi.org/10.1090/S0025-5718-1994-1223235-2

MathSciNet review:
1223235

Full-text PDF Free Access

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 \[ 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 *i*th prime.

- R. C. Bose and S. Chowla,
*Theorems in the additive theory of numbers*, Comment. Math. Helv.**37**(1962/63), 141–147. MR**144877**, DOI https://doi.org/10.1007/BF02566968 - 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. MR**6197**, DOI https://doi.org/10.1112/jlms/s1-16.4.212 - Richard K. Guy,
*Unsolved problems in number theory*, Unsolved Problems in Intuitive Mathematics, vol. 1, Springer-Verlag, New York-Berlin, 1981. Problem Books in Mathematics. MR**656313** - H. Halberstam and K. F. Roth,
*Sequences. Vol. I*, Clarendon Press, Oxford, 1966. MR**0210679** - Donald E. Knuth,
*The art of computer programming*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**0378456** - Bernt Lindström,
*An inequality for $B_{2}$-sequences*, J. Combinatorial Theory**6**(1969), 211–212. MR**236138** - Hans Riesel,
*Prime numbers and computer methods for factorization*, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR**897531** - Kenneth H. Rosen,
*Elementary number theory and its applications*, 4th ed., Addison-Wesley, Reading, MA, 2000. MR**1739433** - James Singer,
*A theorem in finite projective geometry and some applications to number theory*, Trans. Amer. Math. Soc.**43**(1938), no. 3, 377–385. MR**1501951**, DOI https://doi.org/10.1090/S0002-9947-1938-1501951-4
B. L. Van der Waerden,

*Modern algebra*, English transl., Ungar, New York, 1949.

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

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

Additional Information

Keywords:
<IMG WIDTH="30" HEIGHT="38" ALIGN="MIDDLE" BORDER="0" SRC="images/img1.gif" ALT="${B_2}$">-sequences,
Erdős-Turán conjecture,
Bose-Chowla theorem,
finite fields,
algorithms

Article copyright:
© Copyright 1994
American Mathematical Society