Finding finite sequences faster
Author:
Bernt Lindström
Journal:
Math. Comp. 67 (1998), 11731178
MSC (1991):
Primary 11B75, 11Y55, 12E20
MathSciNet review:
1484901
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A sequence is a sequence of positive integers such that the sums , , are different. When is a power of a prime and is a primitive element in then there are sequences of size with , which were discovered by R. C. Bose and S. Chowla. In Theorem 2.1 I will give a faster alternative to the definition. In Theorem 2.2 I will prove that multiplying a sequence by integers relatively prime to the modulus is equivalent to varying . Theorem 3.1 is my main result. It contains a fast method to find primitive quadratic polynomials over when is an odd prime. For fields of characteristic 2 there is a similar, but different, criterion, which I will consider in ``Primitive quadratics reflected in sequences'', to appear in Portugaliae Mathematica (1999).
 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.
R.
C. Bose, S.
Chowla, and C.
R. Rao, On the integral order, (mod 𝑝) of quadratics
𝑥²+𝑎𝑥+𝑏, with applications to the
construction of minimum functions for 𝐺𝐹(𝑝²),
and to some number theory results, Bull. Calcutta Math. Soc.
36 (1944), 153–174. MR 0012086
(6,256b)
 3.
Paul
Erdős, Quelques problèmes de théorie des
nombres, Monographies de L’Enseignement Mathématique, No.
6, L’Enseignement Mathématique, Université, Geneva,
1963, pp. 81–135 (French). MR 0158847
(28 #2070)
 4.
P. Erdös and P. Turán, On a problem in additive number theory, J. London Math. Soc. 16 (1941), 212215; ibid 19 (1944), 208.
 5.
Bernt
Lindström, An inequality for 𝐵₂sequences,
J. Combinatorial Theory 6 (1969), 211–212. MR 0236138
(38 #4436)
 6.
Imre
Z. Ruzsa, Solving a linear equation in a set of integers. I,
Acta Arith. 65 (1993), no. 3, 259–282. MR 1254961
(94k:11112)
 7.
Zhen
Xiang Zhang, Finding finite
𝐵₂sequences with larger
𝑚𝑎^{1/2}_{𝑚}, Math.
Comp. 63 (1994), no. 207, 403–414. MR 1223235
(94i:11109), http://dx.doi.org/10.1090/S00255718199412232352
 1.
 R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (196263), 141147. MR 26:2418
 2.
 R. C. Bose, S. Chowla and C. R. Rao, On the integral order of quadratics , with applications to the construction of minimum functions for and to some number theory results, Bull. Calcutta Math. Soc. 36 (1944), 153174. MR 6:256b
 3.
 P. Erdös, Quelques problèmes de la théorie des nombres, Monographies de l'Enseignement Math., No. 6 (Genève 1963), Problème 31. MR 28:2070
 4.
 P. Erdös and P. Turán, On a problem in additive number theory, J. London Math. Soc. 16 (1941), 212215; ibid 19 (1944), 208.
 5.
 B. Lindström, An inequality for sequences, J. Comb. Theory 6 (1969), 211212. MR 38:4436
 6.
 I. Z. Ruzsa, Solving a linear equation in a set of integers, Acta Arith. 65 (1993), 259282. MR 94k:11112
 7.
 Z. Zhang, Finding finite sequences with larger , Math. Comp. 63 (1994), 403414. MR 94i:11109
Similar Articles
Retrieve articles in Mathematics of Computation of the American Mathematical Society
with MSC (1991):
11B75,
11Y55,
12E20
Retrieve articles in all journals
with MSC (1991):
11B75,
11Y55,
12E20
Additional Information
Bernt Lindström
Affiliation:
Department of Mathematics, Royal Institute of Technology, S100 44, Stockholm, Sweden
Address at time of publication:
Turbingränd 18, S17675 Järfälla, Sweden
DOI:
http://dx.doi.org/10.1090/S0025571898009867
PII:
S 00255718(98)009867
Keywords:
$B_2$sequence,
BoseChowla theorem,
finite field,
primitive element,
primitive quadratic
Received by editor(s):
November 21, 1996
Article copyright:
© Copyright 1998 American Mathematical Society
