Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Finding finite $B_2$-sequences faster


Author: Bernt Lindström
Journal: Math. Comp. 67 (1998), 1173-1178
MSC (1991): Primary 11B75, 11Y55, 12E20
DOI: https://doi.org/10.1090/S0025-5718-98-00986-7
MathSciNet review: 1484901
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A $B_2$-sequence is a sequence $a_1<a_2<\cdots<a_r$ of positive integers such that the sums $a_i+a_j$, $1\le i\le j\le r$, are different. When $q$ is a power of a prime and $\theta$ is a primitive element in $GF(q^2)$ then there are $B_2$-sequences $A(q,\theta)$ of size $q$ with $a_q<q^2$, 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 $A(q,\theta)$ by integers relatively prime to the modulus is equivalent to varying $\theta$. Theorem 3.1 is my main result. It contains a fast method to find primitive quadratic polynomials over $GF(p)$ when $p$ 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 $B_2$-sequences'', to appear in Portugaliae Mathematica (1999).


References [Enhancements On Off] (What's this?)

  • 1. R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (1962-63), 141-147. MR 26:2418
  • 2. R. C. Bose, S. Chowla and C. R. Rao, On the integral order $(\operatorname{mod}p)$ of quadratics $x^2+ax+b$, with applications to the construction of minimum functions for $GF(p^2)$ and to some number theory results, Bull. Calcutta Math. Soc. 36 (1944), 153-174. 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), 212-215; ibid 19 (1944), 208.
  • 5. B. Lindström, An inequality for $B_2$-sequences, J. Comb. Theory 6 (1969), 211-212. MR 38:4436
  • 6. I. Z. Ruzsa, Solving a linear equation in a set of integers, Acta Arith. 65 (1993), 259-282. MR 94k:11112
  • 7. Z. Zhang, Finding finite $B_2$-sequences with larger $m-a_m^{1/2}$, Math. Comp. 63 (1994), 403-414. 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, S-100 44, Stockholm, Sweden
Address at time of publication: Turbingränd 18, S-17675 Järfälla, Sweden

DOI: https://doi.org/10.1090/S0025-5718-98-00986-7
Keywords: $B_2$-sequence, Bose-Chowla theorem, finite field, primitive element, primitive quadratic
Received by editor(s): November 21, 1996
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society