Finding finite sequences with larger
Author:
Zhen Xiang Zhang
Journal:
Math. Comp. 63 (1994), 403414
MSC:
Primary 11Y55; Secondary 11B75
MathSciNet review:
1223235
Fulltext 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 where the maximum is taken over all melement sequences. Erdős and Turán ask if . In this paper we give an algorithm, based on the BoseChowla theorem on finite fields, for finding a lower bound of and a pelement 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 ith 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
(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. MR 0006197
(3,270e)
 [3]
Richard
K. Guy, Unsolved problems in number theory, Unsolved Problems
in Intuitive Mathematics, vol. 1, SpringerVerlag, New York, 1981.
Problem Books in Mathematics. MR 656313
(83k:10002)
 [4]
H.
Halberstam and K.
F. Roth, Sequences. Vol. I, Clarendon Press, Oxford, 1966. MR 0210679
(35 #1565)
 [5]
Donald
E. Knuth, The art of computer programming, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Volume 1: Fundamental algorithms; AddisonWesley Series in Computer Science
and Information Processing. MR 0378456
(51 #14624)
 [6]
Bernt
Lindström, An inequality for 𝐵₂sequences,
J. Combinatorial Theory 6 (1969), 211–212. MR 0236138
(38 #4436)
 [7]
Hans
Riesel, Prime numbers and computer methods for factorization,
Progress in Mathematics, vol. 57, Birkhäuser Boston Inc., Boston,
MA, 1985. MR
897531 (88k:11002)
 [8]
Kenneth
H. Rosen, Elementary number theory and its applications, 4th
ed., AddisonWesley, Reading, MA, 2000. MR 1739433
(2000i:11001)
 [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, http://dx.doi.org/10.1090/S00029947193815019514
 [10]
B. L. Van der Waerden, Modern algebra, English transl., Ungar, New York, 1949.
 [1]
 R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (196263), 141147. 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), 212215; Addendum, 19 (1944), 208. MR 0006197 (3:270e)
 [3]
 Richard K. Guy, Unsolved problems in number theory, SpringerVerlag, 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: Seminumerical algorithms, Vol. 2, 2nd ed., AddisonWesley, Reading, MA, 1981. MR 0378456 (51:14624)
 [6]
 B. Lindstrom, An inequality for sequences, J. Combin. Theory 6 (1969), 211212. 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, AddisonWesley, 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), 377385. 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
DOI:
http://dx.doi.org/10.1090/S00255718199412232352
PII:
S 00255718(1994)12232352
Keywords:
sequences,
ErdősTurán conjecture,
BoseChowla theorem,
finite fields,
algorithms
Article copyright:
© Copyright 1994 American Mathematical Society
