Finding finite -sequences with larger

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

Abstract | References | Similar Articles | Additional Information

Abstract: A sequence of positive integers is called a (finite) -sequence, or a (finite) Sidon sequence, if the pairwise differences are all distinct. Let

*m*-element -sequences. Erdős and Turán ask if . In this paper we give an algorithm, based on the Bose-Chowla theorem on finite fields, for finding a lower bound of and a

*p*-element -sequence with equal to this bound, taking bit operations and requiring storage, where

*p*is a prime. A search for lower bounds of for is given, especially , where is the

*i*th prime.

**[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*-*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.

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

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

Additional Information

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

Keywords:
-sequences,
Erdős-Turán conjecture,
Bose-Chowla theorem,
finite fields,
algorithms

Article copyright:
© Copyright 1994
American Mathematical Society