Source author record

Daqing Wan

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NT math.AG Information Theory math.IT math.CO Computational Complexity Cryptography and Security Discrete Mathematics Symbolic Computation

Catalog footprint

Research overview

25works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

On inverted Kloosterman sums over finite fields

The classical $n$ -variable Kloosterman sums over finite fields are well understood by Deligne's theorem from complex point of view and by Sperber's theorem from $p$ -adic point of view. In this paper, we study the complex and $p$ -adic estimates of inverted $n$ -variable Kloosterman sums, addressing a question of N. Katz (1995). We shall give two complex estimates. The first one is elementary based on Gauss sums. The second estimate is deeper, depending on the cohomological results of Adolphson-Sperber, Denef-Loeser and Fu for twisted toric exponential sums. This deeper result assumes that the characteristic $p$ does not divide $n+1$ . Combining with Dwork's $p$ -adic theory, we also determine the exact $p$ -adic valuations for zeros and poles of the L-function associated to inverted $n$ -variable Kloosterman sums in the case $p \equiv 1 \mod (n+1)$ . As we shall see, the inverted $n$ -variable Kloosterman sum is more complicated than the classical $n$ -variable Kloosterman sum in all aspects in the sense that our understanding is less complete, partly because the Hodge numbers are now mostly $2$ instead of $1$ .

preprint2022arXiv

Divisibility of Frobenius eigenvalues on $\ell$ -adic cohomology

v2: For a projective variety defined over a finite field with $q$ elements, it is shown that as algebraic integers, the eigenvalues of the geometric Frobenius acting on $\ell$ -adic cohomology have higher than known $q$ -divisibility beyond the middle dimension. This sharpens both Deligne's integrality theorem and the cohomological divisibility theorem proven by the first author and N. Katz. Similar lower bounds are proved for the Hodge level for a complex variety beyond the middle dimension, improving earlier results in this direction. We discuss the affine case. The previous version contained a gap at this place. We are thankful to Dingxin Zhang for noticing it.

preprint2022arXiv

On Deep Holes of Elliptic Curve Codes

We give a method to construct deep holes for elliptic curve codes. For long elliptic curve codes, we conjecture that our construction is complete in the sense that it gives all deep holes. Some evidence and heuristics on the completeness are provided via the connection with problems and results in finite geometry.

preprint2020arXiv

Computing zeta functions of large polynomial systems over finite fields

In this paper, we improve the algorithms of Lauder-Wan \cite{LW} and Harvey \cite{Ha} to compute the zeta function of a system of $m$ polynomial equations in $n$ variables over the finite field $\FF_q$ of $q$ elements, for $m$ large. The dependence on $m$ in the original algorithms was exponential in $m$ . Our main result is a reduction of the exponential dependence on $m$ to a polynomial dependence on $m$ . As an application, we speed up a doubly exponential time algorithm from a software verification paper \cite{BJK} (on universal equivalence of programs over finite fields) to singly exponential time. One key new ingredient is an effective version of the classical Kronecker theorem which (set-theoretically) reduces the number of defining equations for a "large" polynomial system over $\FF_q$ when $q$ is suitably large.

preprint2020arXiv

On Katz's $(A,B)$ -exponential sums

We deduce Katz's theorems for $(A,B)$ -exponential sums over finite fields using $\ell$ -adic cohomology and a theorem of Denef-Loeser, removing the hypothesis that $A+B$ is relatively prime to the characteristic $p$ . In some degenerate cases, the Betti number estimate is improved using toric decomposition and Adolphson-Sperber's bound for the degree of $L$ -functions. Applying the facial decomposition theorem in \cite{W1}, we prove that the universal family of $(A,B)$ -polynomials is generically ordinary for its $L$ -function when $p$ is in certain arithmetic progression.

preprint2020arXiv

Rational points on complete symmetric hypersurfaces over finite fields

For any affine hypersurface defined by a complete symmetric polynomial in $k\geq 3$ variables of degree $m$ over the finite field $\mathbb{F}_{q}$ of $q$ elements, a special case of our theorem says that this hypersurface has at least $6q^{k-3}$ rational points over $\mathbb{F}_{q}$ if $1\leq m \leq q-3$ and $q$ is odd. A key ingredient in our proof is Segre's classical theorem on ovals in finite projective planes.

preprint2016arXiv

Deep Holes in Reed-Solomon Codes Based on Dickson Polynomials

For an $[n,k]$ Reed-Solomon code $\mathcal{C}$ , it can be shown that any received word $r$ lies a distance at most $n-k$ from $\mathcal{C}$ , denoted $d(r,\mathcal{C})\leq n-k$ . Any word $r$ meeting the equality is called a deep hole. Guruswami and Vardy (2005) showed that for a specific class of codes, determining whether or not a word is a deep hole is NP-hard. They suggested passingly that it may be easier when the evaluation set of $\mathcal{C}$ is large or structured. Following this idea, we study the case where the evaluation set is the image of a Dickson polynomial, whose values appear with a special uniformity. To find families of received words that are not deep holes, we reduce to a subset sum problem (or equivalently, a Dickson polynomial-variation of Waring's problem) and find solution conditions by applying an argument using estimates on character sums indexed over the evaluation set.

preprint2016arXiv

Newton slopes for Artin-Schreier-Witt towers

We fix a monic polynomial $f(x) \in \mathbb F_q[x]$ over a finite field and consider the Artin-Schreier-Witt tower defined by $f(x)$ ; this is a tower of curves $\cdots \to C_m \to C_{m-1} \to \cdots \to C_0 =\mathbb A^1$ , with total Galois group $\mathbb Z_p$ . We study the Newton slopes of zeta functions of this tower of curves. This reduces to the study of the Newton slopes of L-functions associated to characters of the Galois group of this tower. We prove that, when the conductor of the character is large enough, the Newton slopes of the L-function form arithmetic progressions which are independent of the conductor of the character. As a corollary, we obtain a result on the behavior of the slopes of the eigencurve associated to the Artin-Schreier-Witt tower, analogous to the result of Buzzard and Kilford.

preprint2016arXiv

On Deep Holes of Projective Reed-Solomon Codes

In this paper, we obtain new results on the covering radius and deep holes for projective Reed-Solomon (PRS) codes.

preprint2016arXiv

On the arithmetic of Z_p-extensions

This paper contains three parts. In the first part, we give a thorough overview of the theory of Artin-Schreier-Witt extensions: this theory allows one to understand the $\mathbf{Z}/p^n\mathbf{Z}$ -extensions of any field $K$ of characteristic $p$ via $p$ -typical Witt vectors. Let $W_n(K)$ be the ring of $p$ -typical Witt vectors of $K$ of length $n$ and let $\wp = F-\mathrm{id}: W_n(K)\longrightarrow W_n(K)$ , where $F$ is the Frobenius map and $\mathrm{id}$ is the identity map. Artin-Schreier-Witt theory tells us that the abelian group $W_n(K)/\wp W_n(K)$ represents the set of $\mathbf{Z}/p^n\mathbf{Z}$ -extensions of $K$ . Since this theory is hard to find in literature, we have included a complete treatment in the paper. In the second part of the paper, we study $\mathbf{Z}_p$ -extensions of a local field $K=k((T))$ of characteristic $p>0$ where $k$ is a finite field. Local class field theory and Artin-Schreier-Witt theory give us the Schmid-Witt symbol $[\ ,\ ): W(K)/\wp W(K) \times \widehat{K^*} \to W(\mathbf{F}_p)=\mathbf{Z}_p,$ which contains the ramification information of $\mathbf{Z}_p$ -extensions of $K$ . We present a new simplified formula for $[\ ,\ )$ . This formula allows one to compute ramification groups, conductors and discriminants in an easy way. In the third part, we study $\mathbf{Z}_p$ -extensions of global function fields over a finite field. First, we give a formula for computing the genus in such a tower. We show that a previously obtained lower bound for the genus growth in a $\mathbf{Z}_p$ -extension is incorrect and we give a sharp lower bound. We also study when the genus behaves in a `stable' way. Finally, we find unique representatives of $\mathbf{Z}_p$ -extensions of the rational function field $k(X)$ , and compute the genus in such a tower.

preprint2016arXiv

Power moments of Kloosterman sums

In this paper we give an essential treatment for estimating arbitrary integral power moments of Kloosterman sums over the residue class ring. For prime moduli we derive explicit estimates, and for prime-power moduli we prove concrete formulas using computations with Igusa zeta functions.

preprint2016arXiv

Slopes of eigencurves over boundary disks

Let $p$ be a prime number. We study the slopes of $U_p$ -eigenvalues on the subspace of modular forms that can be transferred to a definite quaternion algebra. We give a sharp lower bound of the corresponding Newton polygon. The computation happens over a definite quaternion algebra by Jacquet-Langlands correspondence; it generalizes a prior work of Daniel Jacobs who treated the case of $p=3$ with a particular level. In case when the modular forms have a finite character of conductor highly divisible by $p$ , we improve the lower bound to show that the slopes of $U_p$ -eigenvalues grow roughly like arithmetic progressions as the weight $k$ increases. This is the first very positive evidence for Buzzard-Kilford's conjecture on the behavior of the eigencurve near the boundary of the weight space, that is proved for arbitrary $p$ and general level. We give the exact formula of a fraction of the slope sequence.

preprint2016arXiv

Sparse Univariate Polynomials with Many Roots Over Finite Fields

Suppose $q$ is a prime power and $f\in\mathbb{F}_q[x]$ is a univariate polynomial with exactly $t$ monomial terms and degree $<q-1$ . To establish a finite field analogue of Descartes' Rule, Bi, Cheng, and Rojas (2013) proved an upper bound of $2(q-1)^{\frac{t-2}{t-1}}$ on the number of cosets in $\mathbb{F}^*_q$ needed to cover the roots of $f$ in $\mathbb{F}^*_q$ . Here, we give explicit $f$ with root structure approaching this bound: For $q$ a $(t-1)$ -st power of a prime we give an explicit $t$ -nomial vanishing on $q^{\frac{t-2}{t-1}}$ distinct cosets of $\mathbb{F}^*_q$ . Over prime fields $\mathbb{F}_p$ , computational data we provide suggests that it is harder to construct explicit sparse polynomials with many roots. Nevertheless, assuming the Generalized Riemann Hypothesis, we find explicit trinomials having $Ω\left(\frac{\log p}{\log \log p}\right)$ distinct roots in $\mathbb{F}_p$ .

preprint2015arXiv

Counting polynomial subset sums

Let $D$ be a subset of a finite commutative ring $R$ with identity. Let $f(x)\in R[x]$ be a polynomial of positive degree $d$ . For integer $0\leq k \leq |D|$ , we study the number $N_f(D,k,b)$ of $k$ -subsets $S\subseteq D$ such that \begin{align*} \sum_{x\in S} f(x)=b. \end{align*} In this paper, we establish several asymptotic formulas for $N_f(D,k, b)$ , depending on the nature of the ring $R$ and $f$ . For $R=\mathbb{Z}_n$ , let $p=p(n)$ be the smallest prime divisor of $n$ , $|D|=n-c \geq C_dn p^{-\frac 1d }+c$ and $f(x)=a_dx^d +\cdots +a_0\in \mathbb{Z}[x]$ with $(a_d, \dots, a_1, n)=1$ . Then $\left| N_f(D, k, b)-\frac{1}{n}{n-c \choose k}\right|\leq {δ(n)(n-c)+(1-δ(n))(C_dnp^{-\frac 1d}+c)+k-1\choose k},$ partially answering an open question raised by Stanley \cite{St}, where $δ(n)=\sum_{i\mid n, μ(i)=-1}\frac 1 i$ and $C_d=e^{1.85d}$ . Furthermore, if $n$ is a prime power, then $δ(n) =1/p$ and one can take $C_d=4.41$ . For $R=\mathbb{F}_q$ of characteristic $p$ , let $f(x)\in \mathbb{F}_q[x]$ be a polynomial of degree $d$ not divisible by $p$ and $D\subseteq \mathbb{F}_q$ with $|D|=q-c\geq (d-1)\sqrt{q}+c$ . Then $\left| N_f(D, k, b)-\frac{1}{q}{q-c \choose k}\right|\leq {\frac{q-c}{p}+\frac {p-1}{p}((d-1)q^{\frac 12}+c)+k-1 \choose k}.$ If $f(x)=ax+b$ , then this problem is precisely the well-known subset sum problem over a finite abelian group. Let $G$ be a finite abelian group and let $D\subseteq G$ with $|D|=|G|-c\geq c$ . Then $\left| N_x(D, k, b)-\frac{1}{|G|}{|G|-c \choose k}\right|\leq {c + (|G|-2c)δ(e(G))+k-1 \choose k},$ where $e(G)$ is the exponent of $G$ and $δ(n)=\sum_{i\mid n, μ(i)=-1}\frac 1 i$ . In particular, we give a new short proof for the explicit counting formula for the case $D=G$ .

preprint2015arXiv

Index bounds for character sums with polynomials over finite fields

We provide an index bound for character sums of polynomials over finite fields. This improves the Weil bound for high degree polynomials with small indices, as well as polynomials with large indices that are generated by cyclotomic mappings of small indices. As an application, we also give some general bounds for numbers of solutions of some Artin-Schreier equations and mininum weights of some cyclic codes.

preprint2015arXiv

On the minimum distance of elliptic curve codes

Computing the minimum distance of a linear code is one of the fundamental problems in algorithmic coding theory. Vardy [14] showed that it is an \np-hard problem for general linear codes. In practice, one often uses codes with additional mathematical structure, such as AG codes. For AG codes of genus $0$ (generalized Reed-Solomon codes), the minimum distance has a simple explicit formula. An interesting result of Cheng [3] says that the minimum distance problem is already \np-hard (under \rp-reduction) for general elliptic curve codes (ECAG codes, or AG codes of genus $1$ ). In this paper, we show that the minimum distance of ECAG codes also has a simple explicit formula if the evaluation set is suitably large (at least $2/3$ of the group order). Our method is purely combinatorial and based on a new sieving technique from the first two authors [8]. This method also proves a significantly stronger version of the MDS (maximum distance separable) conjecture for ECAG codes.

preprint2014arXiv

Linearized Wenger graphs

Motivated by recent extensive studies on Wenger graphs, we introduce a new infinite class of bipartite graphs of the similar type, called linearized Wenger graphs. The spectrum, diameter and girth of these linearized Wenger graphs are determined.

preprint2013arXiv

Algebraic Cayley Graphs over Finite Fields

A new algebraic Cayley graph is constructed using finite fields. Its connectedness and diameter bound are studied via Weil's estimate for character sums. These graphs provide a new source of expander graphs, extending classical results of Chung.

preprint2013arXiv

Stopping Sets of Algebraic Geometry Codes

Stopping sets and stopping set distribution of a linear code play an important role in the performance analysis of iterative decoding for this linear code. Let $C$ be an $[n,k]$ linear code over $\f$ with parity-check matrix $H$ , where the rows of $H$ may be dependent. Let $[n]=\{1,2,...,n\}$ denote the set of column indices of $H$ . A \emph{stopping set} $S$ of $C$ with parity-check matrix $H$ is a subset of $[n]$ such that the restriction of $H$ to $S$ does not contain a row of weight 1. The \emph{stopping set distribution} $\{T_{i}(H)\}_{i=0}^{n}$ enumerates the number of stopping sets with size $i$ of $C$ with parity-check matrix $H$ . Denote $H^{*}$ the parity-check matrix consisting of all the non-zero codewords in the dual code $C^{\bot}$ . In this paper, we study stopping sets and stopping set distributions of some residue algebraic geometry (AG) codes with parity-check matrix $H^*$ . First, we give two descriptions of stopping sets of residue AG codes. For the simplest AG codes, i.e., the generalized Reed-Solomon codes, it is easy to determine all the stopping sets. Then we consider AG codes from elliptic curves. We use the group structure of rational points of elliptic curves to present a complete characterization of stopping sets. Then the stopping sets, the stopping set distribution and the stopping distance of the AG code from an elliptic curve are reduced to the search, counting and decision versions of the subset sum problem in the group of rational points of the elliptic curve, respectively. Finally, for some special cases, we determine the stopping set distributions of AG codes from elliptic curves.

preprint2013arXiv

Traps to the BGJT-Algorithm for Discrete Logarithms

In the recent breakthrough paper by Barbulescu, Gaudry, Joux and Thom{é}, a quasi-polynomial time algorithm (QPA) is proposed for the discrete logarithm problem over finite fields of small characteristic. The time complexity analysis of the algorithm is based on several heuristics presented in their paper. We show that some of the heuristics are problematic in their original forms, in particular, when the field is not a Kummer extension. We believe that the basic idea behind the new approach should still work, and propose a fix to the algorithm in non-Kummer cases, without altering the quasi-polynomial time complexity. The modified algorithm is also heuristic. Further study is required in order to fully understand the effectiveness of the new approach.

preprint2012arXiv

L-functions of p-adic characters

We define a p-adic character to be a continuous homomorphism from 1 + t\Fq[[t]] to \Zp^*. We use the ring of big Witt vectors over Fq to exhibit a bijection between p-adic characters and sequences (c_i) of elements in Zq, indexed by natural numbers relatively prime to p, and which converge to zero p-adically. To such a p-adic character we associate an L-function, and we prove that this L-function is p-adic meromorphic if the corresponding sequence (c_i) is overconvergent. If more generally the sequence is c\log-convergent, we show that the associated L-function is meromorphic in the open disk of radius q^c. Finally, we exhibit examples of c\log-convergent sequences with associated L-functions which are not meromorphic in any disk of radius greater than q^c.

preprint2012arXiv

Value sets of polynomial maps over finite fields

We provide upper bounds for the cardinality of the value set of a polynomial map in several variables over a finite field. These bounds generalize earlier bounds for univariate polynomials.

preprint2011arXiv

Counting Value Sets: Algorithm and Complexity

Let $p$ be a prime. Given a polynomial in $\F_{p^m}[x]$ of degree $d$ over the finite field $\F_{p^m}$, one can view it as a map from $\F_{p^m}$ to $\F_{p^m}$, and examine the image of this map, also known as the value set. In this paper, we present the first non-trivial algorithm and the first complexity result on computing the cardinality of this value set. We show an elementary connection between this cardinality and the number of points on a family of varieties in affine space. We then apply Lauder and Wan's $p$ -adic point-counting algorithm to count these points, resulting in a non-trivial algorithm for calculating the cardinality of the value set. The running time of our algorithm is $(pmd)^{O(d)}$ . In particular, this is a polynomial time algorithm for fixed $d$ if $p$ is reasonably small. We also show that the problem is #P-hard when the polynomial is given in a sparse representation, $p=2$ , and $m$ is allowed to vary, or when the polynomial is given as a straight-line program, $m=1$ and $p$ is allowed to vary. Additionally, we prove that it is NP-hard to decide whether a polynomial represented by a straight-line program has a root in a prime-order finite field, thus resolving an open problem proposed by Kaltofen and Koiran in \cite{Kaltofen03,KaltofenKo05}.

preprint2010arXiv

An Asymptotic Formula For Counting Subset Sums Over Subgroups Of Finite Fields

Let F_q be the finite field of q elements. Let H be a multiplicative subgroup of F_q^*. For a positive integer k and element b\in F_q, we give a sharp estimate for the number of k-element subsets of H which sum to b.

preprint2010arXiv

Improvements of The Weil Bound For Artin-Schreier Curves

For Artin-Schreier curve y^q -y = f(x) defined over a finite field F_q of q elements, we show that the Weil bound for the number of the rational points over extension fields of F_q can often be greatly improved, essentially removing an extra factor of size about the square root of q in the error term.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Daqing Wan

Research overview

Is this your work?

25 publications

On inverted Kloosterman sums over finite fields

Divisibility of Frobenius eigenvalues on $\ell$ -adic cohomology

On Deep Holes of Elliptic Curve Codes

Computing zeta functions of large polynomial systems over finite fields

On Katz's $(A,B)$ -exponential sums

Rational points on complete symmetric hypersurfaces over finite fields

Deep Holes in Reed-Solomon Codes Based on Dickson Polynomials

Newton slopes for Artin-Schreier-Witt towers

On Deep Holes of Projective Reed-Solomon Codes

On the arithmetic of Z_p-extensions

Power moments of Kloosterman sums

Slopes of eigencurves over boundary disks

Sparse Univariate Polynomials with Many Roots Over Finite Fields

Counting polynomial subset sums

Index bounds for character sums with polynomials over finite fields

On the minimum distance of elliptic curve codes

Linearized Wenger graphs

Algebraic Cayley Graphs over Finite Fields

Stopping Sets of Algebraic Geometry Codes

Traps to the BGJT-Algorithm for Discrete Logarithms

L-functions of p-adic characters

Value sets of polynomial maps over finite fields

Counting Value Sets: Algorithm and Complexity

An Asymptotic Formula For Counting Subset Sums Over Subgroups Of Finite Fields

Improvements of The Weil Bound For Artin-Schreier Curves

See the researcher in context

Building this map preview

Daqing Wan

Research overview

Is this your work?

25 publications

On inverted Kloosterman sums over finite fields

Divisibility of Frobenius eigenvalues on ℓ\ellℓ-adic cohomology

On Deep Holes of Elliptic Curve Codes

Computing zeta functions of large polynomial systems over finite fields

On Katz's (A,B)(A,B)(A,B)-exponential sums

Rational points on complete symmetric hypersurfaces over finite fields

Deep Holes in Reed-Solomon Codes Based on Dickson Polynomials

Newton slopes for Artin-Schreier-Witt towers

On Deep Holes of Projective Reed-Solomon Codes

On the arithmetic of Z_p-extensions

Power moments of Kloosterman sums

Slopes of eigencurves over boundary disks

Sparse Univariate Polynomials with Many Roots Over Finite Fields

Counting polynomial subset sums

Index bounds for character sums with polynomials over finite fields

On the minimum distance of elliptic curve codes

Linearized Wenger graphs

Algebraic Cayley Graphs over Finite Fields

Stopping Sets of Algebraic Geometry Codes

Traps to the BGJT-Algorithm for Discrete Logarithms

L-functions of p-adic characters

Value sets of polynomial maps over finite fields

Counting Value Sets: Algorithm and Complexity

An Asymptotic Formula For Counting Subset Sums Over Subgroups Of Finite Fields

Improvements of The Weil Bound For Artin-Schreier Curves

See the researcher in context

Building this map preview

Divisibility of Frobenius eigenvalues on $\ell$ -adic cohomology

On Katz's $(A,B)$ -exponential sums