Finding finite -sequences with larger

Author:
Zhen Xiang Zhang

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

MSC:
Primary 11Y55; Secondary 11B75

MathSciNet review:
1223235

Full-text PDF Free Access

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/1963), 141–147. MR**0144877****[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. MR**0006197****[3]**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****[4]**H. Halberstam and K. F. Roth,*Sequences. Vol. I*, Clarendon Press, Oxford, 1966. MR**0210679****[5]**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****[6]**Bernt Lindström,*An inequality for 𝐵₂-sequences*, J. Combinatorial Theory**6**(1969), 211–212. MR**0236138****[7]**Hans Riesel,*Prime numbers and computer methods for factorization*, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR**897531****[8]**Kenneth H. Rosen,*Elementary number theory and its applications*, 4th ed., Addison-Wesley, Reading, MA, 2000. MR**1739433****[9]**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**, 10.1090/S0002-9947-1938-1501951-4**[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:
http://dx.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