Abstract
Let \(\mathbb {F}_q\) be a finite field with q elements, where q is a power of a prime p. In this paper, we obtain an improvement on Weil bounds for character sums associated to a polynomial f(x) over \(\mathbb {F}_q \), which extends the results of Wan et al. (Des. Codes Cryptogr. 81, 459–468, 2016) and Wu et al. (Des. Codes Cryptogr. 90, 2813–2821, 2022).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let \(\mathbb {F}_q\) be a finite field with q elements, where \(q=p^m\), p is a prime and m is a positive integer. The trace function from \(\mathbb {F}_{q}\) onto \(\mathbb {F}_p\) is defined by \({\text {Tr}}_{q/p}(x)=x+x^p+\cdots +x^{p^{m-1}}\), \( x\in \mathbb {F}_{q}\). The canonical additive character of \(\mathbb {F}_{q}\) is defined as follows:
where \(\zeta _{p}=e^{\frac{2\pi \sqrt{-1}}{p}}\) denotes the p-th primitive root of unity. It is well-known that an arbitrary nontrivial additive character \(\psi \) of \(\mathbb {F}_q\) can be expressed by \(\psi =\psi _1(c), c\in \mathbb {F}_q^*\).
Let f(x) be a polynomial over \(\mathbb {F}_q\) of degree n with \(\gcd (n, p)=1\). Define the character sum \(S( f, \psi )=\sum _{x\in \mathbb {F}_q}\psi (f(x))\). A well-known result for \(S( f, \psi )\) says that
The upper bound in (1.1) is called the Weil bound. In general, the bound is tight and cannot be improved except some special families of conditions.
For a positive integer \(d\le q= p^m\), the p-ary expansion of \(d=d_0+d_1p+\ldots +d_{m-1}p^{m-1}\), the p-ary weight of d, denoted by \(W_p(d)\), is equal to \( \sum _{i=0}^{m-1}d_i\). In [6], let \( f(x)=ax^d+g(x)\) be a polynomial defined over \(\mathbb {F}_{q }\), where d is the only exponent in the support of f(x) with p-ary weight equal to \(\deg _p(f)\) and \(\deg _p(f)=\max \limits _{d\in supp(f)}\{W_p(d)\}\), Gillot obtained the Weil bound of f(x) under the assumption \( d = 1 + d_rp^r\) with \(\gcd (p, d_r)= 1\) is
Later, Gillot and Langevin [7] gave a further improvement on this bound.
In [5], let \(q=2^m\), for some positive integer N, suppose that \(f(x)=x^c+\sum _{i=1}^N\beta ^ix^{ a_i(2t-1)}\), where \(\beta _i\in \mathbb {F}_{q}\), t|m, \(\gcd (c,q-1)=1\), and each \(a_i\) is a positive integer, Gangopadhyay obtained that
which improved the Weil bound when \(\deg (f(x))\ge 2^{\frac{m}{2} -t+1}+1\).
In [15], suppose that \(f(x)=x^n\), where \( p^{\frac{2}{m}}\le n\le p^{\frac{m}{2}+\frac{1}{2}}\), Shparlinski estimated the character sum \( \bigg |\sum _{x\in \mathbb {F}_q}\psi (x^n) \bigg | \); later, Bourgain and Chang in [2] also obtained a nontrivial estimate of \(\bigg |\sum _{x\in \mathbb {F}_q}\psi (x^n)\bigg | \) under the assumption \(\gcd (n, \frac{q-1}{p^v-1} )<p^{-v} q^{1-\varepsilon }\), where \(q=p^m\), \(1\le v< m\),v|m, and \( \varepsilon >0\), which extended the results of Bourgain et al. in [3].
Furthermore, there are a lot of attentions on improving the Weil bound for the Artin-Schreier curves, that is \(y^q-y=f(x)\) for \((x,y)\in \mathbb {F}_{q^m}^2\), because of their applications in coding theory and computer sciences, which are referred as [4, 9, 13, 14] and therein. About character sums for polynomials, there are a lot of papers to investigate them and presented their applications in cryptography radar and wireless communication systems. Wu et al. in [22] computed the cross correlation distributions of a p-ary m-sequence for several decimations with \(d=\frac{q-1}{p^m}\) in case of \(p=2\) and \(p=3\). Li and Wu et al. in [10, 12, 20, 21] gave some low valued Walsh spectrums of monomial functions. Heng et al. in [8, 11] constructed two families of linear codes with a few weights based on special polynomials over finite fields and some near MDS codes which are optimal locally recoverable codes.
In [18], for character sums associated to a polynomial f(x) over \(\mathbb {F}_q \), Wan and Wang presented a new bound, which is called an index bound. They improved the Weil bound for high degree polynomials with small indices. The idea was to use monomial bounds over each cyclotomic cosets because each polynomial can be presented as a cyclotomic mapping. Recently, the index bound was slightly improved by Wu et al. in [19] by using the least index obtained from all possible conjugated exponents of the polynomial f(x).
In this paper, let \(\mathbb {F}_q\) be a finite field, where \(q=p^m\) and p is a prime. Let \(\psi \) be an arbitrary nontrivial additive character of \(\mathbb {F}_q\). For an arbitrary polynomial \(f(x)\in \mathbb {F}_q[x]\), we investigate the Weil bound of character sum \(\sum _{x\in \mathbb {F}_q}\psi (f(x))\) associated to f(x) by considering all possible conjugated exponents of f(x) and present an improved upper bound compared to the results of Wan et al. in [18] and Wu et al. in [19].
2 An improvement of Weil bound for character sums of polynomials
In this section, we always assume that \(\mathbb {F}_q\) is a finite field, where \(q=p^m\), p is a prime, and m is a positive integer. Let \(\gamma \) be a primitive element of \(\mathbb {F}_q\), i.e., \(\mathbb {F}_{q}^*=\langle \gamma \rangle \) and l, s two positive integers with \(ls=q-1\), then we define the cyclotomic cosets of order l in \(\mathbb {F}_q\) as follows:
where \(C_0=\langle \gamma ^l\rangle \) is a cyclic subgroup of \(\mathbb {F}_{q}^*\) generated by \(\gamma ^l\).
For any \(a_0, a_1, \cdots , a_{l-1} \in \mathbb {F}_q\) and a positive integer r, Wang [16] defined the r-th order cyclotomic mapping \(f_{a_0, a_1, \cdots , a_{l-1}}^r\) of index l from \(\mathbb {F}_q\) to itself:
It is shown that the r-th order cyclotomic mappings of index l produce the polynomials of the form \(f(x)=x^{r}h( x^{\frac{q-1}{l}})\). More generally any nonconstant polynomial f(x) with degree \(\le q-1\) over \(\mathbb {F}_q\) such that \(f(0)=a_0\) can be written uniquely as \(f(x)=x^{r}h( x^{\frac{q-1}{l}})+a_0\) with some positive integers r, l such that \(l| (q-1)\). We call l the index of f(x) (see [1, 17]).
Let \(Gal(\mathbb {F}_q/\mathbb {F}_p)\) be the Galois group of \(\mathbb {F}_q\) over \(\mathbb {F}_p\), it is clear that
where \(\sigma : c\mapsto c^p \) is an automorphism of \(\mathbb {F}_q\), which is called Frobenius automorphism of \(\mathbb {F}_q\) over \(\mathbb {F}_p\). A well-known fact is that \( \sigma (c)=c\) if and only if \(c\in \mathbb {F}_p\). We extend \( \sigma \) to a map \(\tilde{\sigma }\) of \(\mathbb {F}_q[x]\): \(f(x) \mapsto (f(x))^p\), where f(x) is an arbitrary polynomial over \(\mathbb {F}_q\).
In the following, we always assume that
where \( q-1\ge r_k>r_{k-1}>\cdots >r_1\ge 1\) and \(a_{r_i}\ne 0\), \(i=1,2,\ldots ,k\). Denote \(r=r_1\). Then
and the index l of f(x) is
Lemma 2.1
[18] Let \(f(x)=x^{r}h( x^{\frac{q-1}{l}})\in \mathbb {F}_q[x]\) be a polynomial with the index l. Let \(n_0=\sharp \{ i, 0\le i\le l-1: h(\zeta ^i)=0 \} \), where \(\zeta \) is a primitive l-th root of unity in \(\mathbb {F}_q\). For a nontrivial additive character \(\psi \) of \(\mathbb {F}_q\),
Let f(x) be given in (2.1). Define a transformation of \(\mathbb {F}_q[x]\):
where
\( 0\le v_{ i}\le m-1, i=0, 1,2,\ldots ,k\).
For \(x\in \mathbb {F}_q\), let \({\text {Tr}}_{q/p}(x)\) be the absolute trace of x over \(\mathbb {F}_p\), then \({\text {Tr}}_{q/p}(\phi (f(x) ))={\text {Tr}}_{q/p}(f(x)) \). For convenience, let \(\psi \) be the canonical additive character of \(\mathbb {F}_q\). Then
In fact, for an arbitrary nontrivial additive character of \(\mathbb {F}_q\), (2.3) holds. Hence, Wu et al. [19] obtained the following result, which is an improvement of Lemma 2.1.
Lemma 2.2
[19] The notations are as above. Suppose that \(l^*\) is the least index of \( \phi (f(x))\) and \( \phi (f(x))=x^{r^*}h(x^{\frac{q-1}{l^*}})\). Let \(n_0=\sharp \{ i, 0\le i\le l^*-1: h({\zeta }^i)=0 \} \), where \(\zeta \) is a primitive \(l^*\) root of unity in \(\mathbb {F}_q\). Then
In this paper, we shall generalize Lemma 2.2 to get improved bound for character sums of f(x). In order to investigate the bound for character sum of polynomial f(x), we consider the set of all positive divisors of \(q-1\):
Let \(f(x)=\sum _{i=1}^ka_{r_i}x^{r_i}+a_0\) be defined as (2.1). Fix a \(d\in D\) and \(ds=q-1\). Then by division algorithm,
where \(0\le r_{0}^{(d,i)},\ldots , r_{m-1}^{(d,i)}\le s-1\).
Let
and
Without loss of generality, let \(t=|T_d|\),
and \(r^{(d,1)}<r^{(d,2)}<\cdots < r^{(d,t)}\).
By (2.5), there exists a transformation \(\phi _d\) of \(\mathbb {F}_q[x]\) defined as (2.2) such that
where \(b\in \mathbb {F}_q\) and \(h_j(x^s)\) is a polynomial of \(x^s\) over \(\mathbb {F}_q\). In the following, we present our main result in Theorem 2.3.
Theorem 2.3
Let \(d\in D\) and \(sd=q-1\). Let \(\gamma \) be a primitive element of the finite field \(\mathbb {F}_q\) and \(\zeta =\gamma ^s\) be a fixed primitive d-th root of unity in \(\mathbb {F}_q\). Let f(x) be defined as (2.1) and \(T_d\) be given by (2.5). Let \(\phi _d\) be the transformation of \(\mathbb {F}_q[x]\) such that \(\phi _d( f(x))=\sum _{j=1}^{t } x^{r^{(d,j)}}h_j(x^s)+b\), where \(b\in \mathbb {F}_q\) and \(t=|T_d|\). Let
and \(n_{d,0}=d-|I_d|\). Then for each \(d\in D\),
Moreover, if d runs over all positive factors of \(q-1\), then
Proof
Take a \(d\in D\) and \(ds=q-1\), let
\(C_0=\langle \gamma ^d \rangle \) be a subgroup of \(\mathbb {F}_q^*\) of index d, and \(\mathbb {F}_q^*=\cup _{i=0}^{d-1}\gamma ^i C_0\).
Let
be a subset of \(\{0,1,\ldots , d-1\}\). Then
Furthermore,
note that
where \(|\psi (-b)|=1\). Recall that \( \sum _{x\in \mathbb {F}_q}\psi (f(x))=\sum _{x\in \mathbb {F}_q}\psi ( \phi (f(x))) \), then
Moreover, if d runs over all positive divisors of \(q-1\), then
\(\square \)
In fact, we may obtain an improved upper bound than one in (2.6). In Theorem 2.3, if \(d\in D\) is fixed and \(|T_d|=1\), then a generalized form of Lemma 2.2 in [19] is obtained immediately.
Corollary 2.4
Let f(x) be defined as (2.1), d, s two positive integers with \(ds=q-1\), and \(T_d=\{r^{(d,1)}\}\) with \(r^{(d,1)}>0\). Let \(\phi _d\) be the transformation of \(\mathbb {F}_q[x]\) such that \(\phi _d( f(x))= x^{r^{(d,1)}}h(x^s)\). Let \(\gamma \) be a primitive element of the finite field \(\mathbb {F}_q\) and \(\zeta =\gamma ^s\) be a fixed primitive d-th root of unity in \(\mathbb {F}_q\). Let \(I_{d}=\{ i: 0\le i\le d-1 \text{ and } h(\zeta ^i)=0 \} \) and \(n_{d,0}=|I_d|\). Then
Remark 2.5
In Theorem 2.3, the Weil bound of character sum associated to an arbitrary polynomial f(x) depends on \(d\in D, n_{d,0}\), and \( r^{(d,t)}\). The Weil bound in Theorem 2.3 is much better than the ones of Lemmas 2.1 and 2.2. In fact, the bound for character sum of f(x) in Lemma 2.2 presented by Wu et al. in [19] is a special case of Corollary 2.4.
In the following, we give some examples to show that the Weil bound for character sums of f(x) in Theorem 2.3 is indeed an improved bound compared to the bounds in (1.1), Lemmas 2.1 and 2.2.
Example 2.6
Let \(q=5^2\) and \(f(x)=x^{19}+x^{11}+x^5\in \mathbb {F}_q[x]\). The Weil bound in (1.1) is trivial because of the high degree. The bound in Lemma 2.1 is also trivial since the index of f(x) is 12.
In Lemma 2.2, the least index of \( \phi (f(x))\) is
and \( \phi (f(x))=x^{5}((x^{6})^3+x^6+1)\). Then the bound for character sums of f(x) in Lemma 2.2 is
In Theorem 2.3, \(D=\{d: d|24\}=\{ 2,3,4,6,8,12\}\).
(i) For \(d=2\), we have \(R_{2,1}=\{1,5\}\) and \(R_{2,2}=R_{2,3}=\{7,11\}\). Let \(T_2=\{1,7\}\), there exists the transformation \(\phi _2\) of \(\mathbb {F}_q[x]\) such that \( \phi _2(f(x))=x^7((x^{12})^4+x^{12})+x(x^{12})^2\), then \( |\sum _{x\in \mathbb {F}_q}\psi (f(x)) |\le 10\).
(ii) For \(d=3\), we have \(R_{3,1}= R_{3,2}=R_{3,3}=\{1,5\}\). Let \(T_3=\{5\}\), there exists the transformation \(\phi _3\) of \(\mathbb {F}_q[x]\) such that \( \phi _3(f(x))=x^5((x^6)^{15}+(x^6)+1)\), then \( |\sum _{x\in \mathbb {F}_q}\psi (f(x)) |\le 20\).
(iii) For \(d=4\), we have \(R_{4,1}=\{1,5\}\) and \(R_{4,2}=R_{4,3}=\{3,7\}\). Let \(T_4=\{1,3\}\), there exists the transformation \(\phi _4\) of \(\mathbb {F}_q[x]\) such that \( \phi _4(f(x))=x^3((x^8)^{2}+(x^8)) +x((x^8)^3) \), then \( |\sum _{x\in \mathbb {F}_q}\psi (f(x)) |\le 15\). Similarly, for other \(d\in D\), the bounds of f(x) are larger than the above cases. Hence by Theorem 2.3, the bound for character sums of f(x) is
Example 2.7
Let \(f(x)=x^{19}+ax^4\in \mathbb {F}_{27}[x]\), where \(a\in \mathbb {F}_{27}^*\). The bounds given by (1.1), Lemmas 2.1 and 2.2 are all trivial. Another upper bound for exponential sums of f(x) presented by Wu et al. in [19, Example 1.5] is \( |\sum _{x\in \mathbb {F}_{27}} \psi (f(x)) |\le 4\sqrt{27}\).
In Theorem 2.3, take \(d=2\), we have \(R_{2,1}=\{ 4,12,10\}\), \(R_{2,2}=\{ 6,5,2\}\), and \(T_2=\{4,2\}\), there exists the map \(\phi _2\) of \(\mathbb {F}_{27}[x]\) such that \(\phi _2(f(x))=x^2((x^{s})^{13} )+cx^4\), by Theorem 2.3, \( |\sum _{x\in \mathbb {F}_{27}}\psi (f(x)) |\le 2\sqrt{27}\).
Example 2.8
Let \(f(x)=x^{10}+ax^5\in \mathbb {F}_{27}[x]\), where \(a\in \mathbb {F}_{27}^*\). The bounds given by (1.1), Lemmas 2.1 and 2.2 are all trivial. Another upper bound for exponential sums of f(x) presented by Wu et al. in [19, Example 1.6] is \( |\sum _{x\in \mathbb {F}_{27}} \psi (f(x)) |\le 4\sqrt{27}\).
In Theorem 2.3, take \(d=2\), we have \(R_{2,1}=\{ 5,2,4\}\), \(R_{2,2}=\{ 10,4,6\}\), and \(T_2=\{4\}\), there exists the map \(\phi _2\) of \(\mathbb {F}_q[x]\) such that \(\phi _2(f(x))=x^4( (x^{s})^{2} +c(x^{s})^{2})\), by Theorem 2.3, \( |\sum _{x\in \mathbb {F}_q}\psi (f(x)) |\le 2\sqrt{27}\).
From the above examples one sees that the bound we obtained is indeed an improvement compared to that Wan and Wu et al. in [18] and [19].
References
Akbary, A., Ghioca, D., Wang, Q.: On permutation polynomials of prescribed shape. Finite Fields Appl. 15, 195–206 (2009)
Bourgain, J., Chang M.C.: A Gauss sum estimate in arbitrary finite fields. C. R. Math. Acad. Sci. Paris, Ser. I, vol. 342, no. 9, pp. 643–646, (2006)
Bourgain, J., Glibichuk, A.A., Konyagin, S.V.: Estimates for the number of sums and products and for exponential sums in fields of prime order. J. Lond. Math. Soc. 73(2), 380–398 (2016)
Cramer, R., Xing, C.: An improvement to the Hasse-Weil bound and applications to character sums. Adv. Math. 309, 238–253 (2017)
Gangopadhyay, S.: A note on character sums with polynomial arguments. Finite Fields Appl. 9(4), 449–457 (2003)
Gillot, V.: Bounds for exponential sums over finite fields. Finite Fields Appl. 1(4), 421–436 (1995)
Gillot, V., Langevin, P.: Estimation of some exponential sum by means of \(q\)-degree. Glasg. Math. J. 52(2), 315–324 (2010)
Heng, Z., Wang, X., Li, X.: Constructions of cyclic codes and extended primitive cyclic codes with their applications. Finite Fields Appl. 89, 102208 (2023)
Kaufman, T., Lovett, S.: New Extension of the Weil Bound for Character Sums with Applications to Coding. In: Proc. 2011 IEEE 52nd Annual symposium on foundations of computer science (FOCS), Palm Springs, California, USA, pp. 788–796, 2011
Li, F.: Several classes of exponential sums and three-valued Walsh spectrums over finite fields. Finite Fields Appl. 87, 102142 (2023)
Li, X., Heng, Z.: Constructions of near MDS codes which are optimal locally recoverable codes. Finite Fields Appl. 88, 102184 (2023)
Li, F., Wu, Y., Yue, Q.: Evalutions on Moisio’s type exponential sums. Scientia Sinica Mathe. 51(10), 1627–1634 (2021)
Mullen, G.L., Wan, D., Wang, Q.: An index bound on value sets of polynomial maps over finite fields. Appl. Algebra Number Theory, pp. 23–27. Cambridge University Press, United Kingdom (2014)
Rojas-Leon, A., Wan, D.: Improvements of the Weil bound for Artin-Schreier curves. Math. Ann. 351, 417–442 (2011)
Shparlinski, I.E.: Bounds of Gauss sums in finite fields. Proc. Am. Math. Soc. 132(10), 2817–2824 (2004)
Wang, Q.: Cyclotomic mapping permutation polynomials over finite fields. In: Sequences subsequences, and consequences (international workshop, SSC 2007, Los Angeles, May 31-June 2, 2007). Lecture Notes in Computer Science, vol. 4893, pp. 119–128. Springer, Berlin (2007)
Wang, Q.: Cyclotomy and permutation polynomials of large indices. Finite Fields Appl. 22, 57–69 (2013)
Wan, D., Wang, Q.: Index bounds for character sums of polynomials over finite fields. Des. Codes Cryptogr. 81, 459–468 (2016)
Wu, Y., Lee, J., Wang, Q.: Further improvement on index bounds. Des. Codes Cryptogr. 90, 2813–2821 (2022)
Wu, Y., Yue, Q., Li, F.: Three families of monomial functions with three-valued Walsh spectrum. IEEE Trans. Inf. Theory 65(5), 3304–3314 (2019)
Wu, Y., Yue, Q., Li, F.: More functions with three-valued Walsh transformation from linear combinations. IEEE Commun. Lett. 23(4), 564–567 (2019)
Wu, Y., Yue, Q., Shi, X., Zhu, X.: Binary and ternary sequences with a few cross correlations. Cryptogr. Commun. 12, 511–525 (May2020)
Acknowledgements
The authors are very grateful to the reviewers and the Editor for their valuable suggestions that much improved the quality of this paper.
Funding
The paper was supported by National Natural Science Foundation of China under Grants 12171420, 62172219, 12271059, Natural Science Foundation of Shandong Province under Grant ZR2021MA046, Natural Science Research Start up Foundation of Recruiting Talents of Nanjing University of Posts and Telecommunications (Grant No.NY223199), and the Fundamental Research Funds for the Central Universities, CHD, under Grant 300102122202.
Author information
Authors and Affiliations
Contributions
F. Li and F. Meng wrote the main manuscript text and Z. Heng and Q. Yue gave examples. All authors reviewed the manuscript.
Corresponding author
Ethics declarations
Competing interests
The authors declare no competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Li, F., Meng, F., Heng, Z. et al. An improvement on Weil bounds for character sums of polynomials over finite fields. Cryptogr. Commun. 16, 879–887 (2024). https://doi.org/10.1007/s12095-024-00706-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12095-024-00706-1