×

zbMATH — the first resource for mathematics

Character sums, primitive elements, and powers in finite fields. (English) Zbl 1008.11069
Let \(F_{q}\) be a finite field of characteristic \(p\) with \(q=p^{n}\) elements, and \(F_{q^{m}}=F_{q}( \alpha)\) its extension of degree \(m \geq 1\). H. Davenport [On primitive roots in finite fields, Q. J. Math., Oxf. Ser. 8, 308-312 (1937; Zbl 0018.10901)] proved that the set \(F_{q}+ \alpha\) contains at least one primitive element of \(F_{q^{m}}\) if \(q\) is sufficiently large with respect to \(m\).
The author extends this result to certain subsets of \(F_{q}+ \alpha\) of cardinality at least of the order of magnitude \(O(q^{1/2+ \varepsilon})\). The proof is based on a new bound for incomplete character sums \[ S_{K}( \alpha)= \sum_{k=0}^{K-1} \chi( \alpha+ \zeta_{k}), \qquad 1 \leq K < q^{m}, \] where \( \chi\) is a nontrivial multiplicative character of \(F_{q^{m}}\) and \( \zeta_{0}, \zeta_{1}, \ldots , \zeta_{K-1}\) are elements of \(F_{q^{m}}\) defined as follows: if \(k=k_{1}+k_{2} p+ \cdots +k_{mn} p^{mn-1}\) is the \(p\)-adic expansion of \(0 \leq k < q^{m}\) with \(0 \leq k_{i} < p\), \( \{ \omega_{1}, \ldots , \omega_{n} \}\) is a basis of \(F_{q}\) over \(F_{p}\), and \( \omega_{1}, \ldots , \omega_{mn}\) its completion to a basis of \(F_{q^{m}}\) over \(F_{p}\) then \[ \zeta_{k}=k_{1} \omega_{1}+ \cdots k_{mn} \omega_{mn}. \] The author shows that \[ |S_{K}( \alpha)|< 2.2 (Km)^{1/2} q^{1/4}, \] for \(1 \leq K < q\), and deduces that the set \( \{ \alpha, \alpha+ \zeta_{1}, \ldots, \alpha+ \zeta_{K} \}\), with \( \zeta_{i} \in F_{q}\), contains at least \[ \frac{ \varphi(q^{m}-1)}{q^{m}-1}(K+O(K^{1/2}q^{1/4+ \varepsilon})) \] primitive elements of \(F_{q^{m}}\) for any \( \varepsilon > 0\). Moreover, the author obtains a new upper bound for the longest sequence \[ \alpha, \alpha+ \zeta_{1}, \ldots, \alpha+ \zeta_{L-1} \] of consecutive powers in \(F_{q^{m}}\).

MSC:
11T24 Other character sums and Gauss sums
11T30 Structure theory for finite fields and commutative rings (number-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Burgess, D.A., On character sums and primitive roots, Proc. London math. soc. (3), 12, 171-192, (1962) · Zbl 0106.04003
[2] Burgess, D.A., A note on the distribution of residues and non-residues, J. London math. soc., 38, 253-256, (1963) · Zbl 0118.04703
[3] Burgess, D.A., Character sums and primitive roots in finite fields, Proc. London math. soc. (3), 17, 11-25, (1967) · Zbl 0166.05105
[4] Chung, F.R.K., Diameters and eigenvalues, J. amer. math. soc., 2, 187-196, (1989) · Zbl 0678.05037
[5] Davenport, H., On primitive roots in finite fields, Quart. J. math., 8, 308-312, (1937) · JFM 63.0905.03
[6] Davenport, H.; Lewis, D.J., Character sums and primitive roots in finite fields, Rend. circ. mat. Palermo (2), 12, 129-136, (1963) · Zbl 0119.04302
[7] Dickson, L.E., History of the theory of numbers 1, (1952), Chelsea New York
[8] Granville, A., Arithmetic properties of binomial coefficients. I. binomial coefficients modulo prime powers, Organic mathematics, burnaby, BC, 1995, CMS conf. proc. 20, (1997), Amer. Math. Soc Providence, p. 253-276 · Zbl 0903.11005
[9] Gutierrez, J.; Niederreiter, H.; Shparlinski, I.E., On the multidimensional distribution of inversive congruential pseudorandom numbers in parts of the period, Monatsh. math., 129, 31-36, (2000) · Zbl 1011.11053
[10] Hlawka, E.; Schoissengeier, J.; Taschner, R., Geometric and analytic number theory, (1991), Springer-Verlag Berlin
[11] Jungnickel, D., Finite fields: structure and arithmetics, (1993), BI-Wiss.-Verl. Mannheim · Zbl 0779.11058
[12] Karacuba, A.A., Character sums and primitive roots in finite fields, Soviet math. dokl., 9, 755-757, (1968) · Zbl 0182.37501
[13] Katz, N.M., An estimate for character sums, J. amer. math. soc., 2, 197-199, (1989) · Zbl 0672.10026
[14] Landau, E., Vorlesungen über zahlentheorie, (1927), Hirzel Leipzig · JFM 53.0123.17
[15] Lidl, R.; Niederreiter, H., Finite fields, (1983), Cambridge University Press Cambridge
[16] Lucas, M.E., Sur LES congruences des nombres euleriennes et des coefficients différentiels des fonctions trigonométriques, suivant un module premier, Bull. soc. math. France, 6, 49-54, (1878) · JFM 10.0139.04
[17] McIntosh, R.J., A generalization of a congruential property of Lucas, Amer. math. monthly, 99, 231-238, (1992) · Zbl 0755.11001
[18] Niederreiter, H.; Shparlinski, I.E., On the distribution and lattice structure of nonlinear congruential pseudorandom numbers, Finite fields appl., 5, 246-253, (1999) · Zbl 0942.11037
[19] Niederreiter, H.; Shparlinski, I.E., Exponential sums and the distribution of inversive congruential pseudorandom numbers with prime-power modulus, Acta arith., 92, 89-98, (2000) · Zbl 0949.11036
[20] Niederreiter, H.; Shparlinski, I.E., On the distribution of pseudorandom numbers and vectors generated by inversive methods, Appl. algebra engrg. comm. comput., 10, 189-202, (2000) · Zbl 0999.11040
[21] Niederreiter, H.; Shparlinski, I.E., On the distribution of inversive congruential pseudorandom numbers in parts of the period, Math. comp., 70, 1569-1574, (2001) · Zbl 0983.11048
[22] Niederreiter, H.; Winterhof, A., Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators, Acta arith., 93, 387-399, (2000) · Zbl 0969.11040
[23] Perel’muter, G.I.; Shparlinskij, I.E., The distribution of primitive roots in finite fields, Russian math. surv., 45, 223-224, (1990) · Zbl 0705.11078
[24] Shparlinski, I., On finding primitive roots in finite fields, Theoret. comput. sci., 157, 273-275, (1996) · Zbl 0871.11091
[25] Sidel’nikov, V.M., Estimates for the number of appearances of symbols on a segment of recurrent sequence over a finite field, Discrete math. appl., 2, 473-481, (1992) · Zbl 0787.11050
[26] Singmaster, D., Notes on binomial coefficients I - A generalization of Lucas’ congruence, J. London math. soc. (2), 8, 545-548, (1974) · Zbl 0293.05005
[27] Wan, D., Generators and irreducible polynomials over finite fields, Math. comp., 66, 1195-1212, (1997) · Zbl 0879.11072
[28] Winterhof, A., On the distribution of powers in finite fields, Finite fields appl., 4, 43-54, (1998) · Zbl 0910.11055
[29] Winterhof, A., Polynomial spaces over finite fields, Linear algebra appl., 295, 223-229, (1999) · Zbl 0990.11078
[30] A. Winterhof, Polynomial interpolation of the discrete logarithm, Des. Codes Cryptogr, in press.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.