1,721,006 research outputs found
Primary decomposition of zero-dimensional ideals over finite fields
No full textGao, Shuhong; Wan, Daqing; Wang, Mingsheng. (2006). Primary decomposition of zero-dimensional ideals over finite fields. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/4347
Recommended from our members
Refining Multivariate Value Set Bounds
Full text linkOver finite fields, if the image of a polynomial map is not the entire field, then its cardinality can be bounded above by a significantly smaller value. Earlier results bound the cardinality of the value set using the degree of the polynomial, but more recent results make use of the powers of all monomials. In this paper, we explore the geometric properties of the Newton polytope and show how they allow for tighter upper bounds on the cardinality of the multivariate value set. We then explore a method which allows for even stronger upper bounds, regardless of whether one uses the multivariate degree or the Newton polytope to bound the value set. Effectively, this provides an alternate proof of Kosters' degree bound, an improved Newton polytope-based bound, and an improvement of a degree matrix-based result given by Zan and Cao
Recommended from our members
On Calculating the Cardinality of the Value Set of a Polynomial (and some related problems)
Full text linkWe prove a combinatorial identity that relates the size of the value set of a map with the sizes of various iterated fiber products by this map. This identity is then used as the basis for several algorithms that calculate the size of the value set of a polynomial for a broad class of algebraic spaces, most generally an algorithm to calculate the size of the value set of a suitably well-behaved morphism between "nice" affine varieties defined over a finite field. In particular, these algorithms specialize to the case of calculating the size of the value set of a polynomial, viewed as a map between finite fields. These algorithms operate in deterministic polynomial time for fixed input polynomials (thus a fixed number of variables and polynomial degree), so long as the characteristic of the field grows suitably slowly as compared to the other parameters. Each of these algorithms also produces a fiber signature for the map, which for each positive integer j, specifies how many points in the image have fibers of cardinality exactly j. We adapt and analyze the zeta function calculation algorithms due to Lauder-Wan and Harvey, both as point counting algorithms and as algorithms for computation of one or many zeta functions. These value set cardinality calculation algorithms extend to amortized cost algorithms that offer dramatic computational complexity advantages, when the computational cost is amortized over all the results produced. The last of these amortized algorithms partially answers a conjecture of Wan, as it operates in time that is polynomial in log q per value set cardinality calculated. For the value set counting algorithms, these are the first such results, and offer a dramatic improvement over any previously known approach
Recommended from our members
Higher Moments Subset Sum Problem over Finite Fields
Full text linkLet F_q be a finite field and let D ⊆ F_q. Let m be a positive integer and let k be an integer such that 1 ≤ k ≤ |D|. For b = (b_1,...,b_m) ∈ (F_q)^m , let N_m(k,b) denote the number of subsets S ⊆ D with cardinality k such that for i = 1,...,m, the sum, over a ∈ S, of a^i = b_i. The Moments Subset Sum Problem is to determine if N_m(k,b) > 0. There are many results for when m = 1, but not much is known about the higher moments. In this dissertation, we obtain a formula for N_m(k, b) when m = 2 and conditions on the solvability of the Moments Subset Sum Problem by using the Li-Wan sieve and properties of character sums and Gauss sums
Recommended from our members
Extended Wenger Graphs
Full text linkWenger graphs were originally introduced as examples of dense graphs that do not have cycles of a given size. Graphs with similar properties were known at the time, but Wenger graphs are based on algebraic relations in finite fields, and as such are easier to understand and analyze. Wenger graphs are bipartite, with the vertices consisting of two copies of the vector space of dimension m+1 over the finite field of order q. These two sets of vertices are called points and lines, with a point vertex connected to a line vertex if the equations are satisfied for k = 2, 3, ..., m+1. In the original Wenger graph, the function was given by . Since their introduction in 1991, the original Wenger graph concept has been extended to include linearized and jumped Wenger graphs, and some results are known for extensions in general. In this dissertation, another extension, the extended Wenger graph, is introduced and analyzed, and a new result about polynomial root patterns is proven
Recommended from our members
Overconvergent Families of p-adic Representations
Full text linkLet X be a variety over a finite field of characteristic p. The purpose of this dissertation is to extend many known results about p-adic representations of the fundamental group π1(X) to families of p-adic representations. The notion of a family of p-adic representations parameterized by a rigid analytic space arises naturally in many contexts, including geometric Iwasawa theory and the theory of p-adic modular forms. In either context there is significant interest in understanding the variation of the p-adic L-functions L(ρ,s) as ρ moves through a given family. It seems unlikely that we can say much in general, as there are far too many p-adic representations of the group π1(X). In this dissertation we restrict our attention to so-called overconvergent representations, which have the property that the L-function L(ρ,s) is always a p-adic meromorphic function in s. Thus for overconvergent families of representations, the question of understanding the p-adic variation of the L(ρ,s) reduces to the understanding of the variation of their zeroes and poles. Our main theorem is a relative version of the Dwork-Monsky trace formula, which says that these zeroes and poles are are naturally interpolated by rigid analytic objects which we call spectral varieties. In general, the geometry of these spectral varieties is quite mysterious: in the context of p-adic modular forms, the question is the subject of Coleman’s well known spectral halo conjecture. For a few specific examples of overconvergent families, analogues of Coleman’s conjecture have been proven by studying suitable integral models of the parameter space. For this reason, we choose to work primarily with formal schemes and their overconvergent analogues. We hope that this paves the way to a greater understanding of the arithmetic of these overconvergent families
Recommended from our members
Reed-Solomon Codes and the Deep Hole Problem
Full text linkIn many types of modern communication, a message is transmitted over a noisy medium. When this is done, there is a chance that the message will be corrupted. An error-correcting code adds redundant information to the message which allows the receiver to detect and correct errors accrued during the transmission. We will study the famous Reed-Solomon code (found in QR codes, compact discs, deep space probes,\ldots) and investigate the limits of its error-correcting capacity. It can be shown that understanding this is related to understanding the ``deep hole" problem, which is a question of determining when a received message has, in a sense, incurred the worst possible corruption. We partially resolve this in its traditional context, when the code is based on the finite field or , as well as new contexts, when it is based on a subgroup of or the image of a Dickson polynomial. This is a new and important problem that could give insight on the true error-correcting potential of the Reed-Solomon code
Recommended from our members
L-functions of Exponential Sums over Finite Fields
Full text linkLet be a finite field with characteristic . A fundamental problem in number theory is to estimate the reciprocal zeros and poles of L-functions of exponential sums over . In this dissertation, we focus on two classical families of exponential sums which have been widely used in the literature. For the type \mathrm{\RNum{1}} family, we compute the weights and -adic slopes of the associated L-functions. One consequence of our main result is a sharp estimate of these exponential sums. Another consequence is to obtain an explicit counterexample of Adolphson-Sperber's conjecture on the weights of toric exponential sums. For the type \mathrm{\RNum{2}} family, the associated L-functions has pure weights. We study the -adic slopes of the reciprocal roots and extend Zhang and Feng's results of Hasse polynomials. Our main tools include Adolphson-Sperber’s work on toric exponential sums and Wan’s decomposition theorems
Recommended from our members
Arithmetic Stability of Higher Rank Artin--Schreier--Witt Towers
Full text linkLet be a prime and be a power of . Consider a tower of finite Galois covers , whose total Galois group is a compact -adic Lie group, where are smooth projective geometrically irreducible curves over \F_q. It is conjectured by Daqing Wan that if this tower is naturally arising from algebraic geometry, then the zeta functions must have a stable pattern when . The most general form of this conjecture is wide open, and it is already very difficult even when is abelian. In this dissertation, we study the case where the tower is a higher rank Artin--Schreier--Witt tower totally ramified at infinity and unramified at other points. We prove that if this tower is strongly genus stable, then the slopes of the Newton polygon of are uniformly distributed on the interval when . Furthermore, if the tower satisfies a slightly stronger condition than being strongly genus stable, we prove that the slopes of are given by a finite union of arithmetic progressions. This generalizes the main results of \cite{kosterszhu} from rank one case to higher rank case d>1. We also prove a spectral halo property for Artin--Schreier--Witt eigenvarieties corresponding to overconvergent higher rank Artin--Schreier--Witt towers
- …
