New estimates for character sums over sparse elements of finite fields

• URL: http://arxiv.org/abs/2502.14436v1
• Date: Thu, 20 Feb 2025 10:40:48 GMT
• Title: New estimates for character sums over sparse elements of finite fields
• Authors: Kaimin Cheng, Arne Winterhof,
• Abstract summary: We provide new estimates for the character sums $sum_ginmathcalGchi(f(g))$, where $mathcalG$ is a given sparse subsets of $mathbbF_qr$ and $f(X)$ is a sum over $mathbbF_qr$ of certain type.
• Score: 6.5990719141691825
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Let $q$ be a prime power and $r$ a positive integer. Let $\mathbb{F}_q$ be the finite field with $q$ elements, and let $\mathbb{F}_{q^r}$ be its extension field of degree $r$. Let $\chi$ be a nontrivial multiplicative character of $\mathbb{F}_{q^r}$. In this paper, we provide new estimates for the character sums $\sum_{g\in\mathcal{G}}\chi(f(g))$, where $\mathcal{G}$ is a given sparse subsets of $\mathbb{F}_{q^r}$ and $f(X)$ is a polynomial over $\mathbb{F}_{q^r}$ of certain type. Specifically, by extending a sum over sparse subsets to subfields, rather than to general linear spaces, we obtain significant improvements of previous estimates.

Related papers

• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  We introduce a general framework for constrained subspace approximation. We show it provides new algorithms for partition-constrained subspace approximation with applications to $k$-means clustering, and projected non-negative matrix factorization.
  arXiv  Detail & Related papers  (2025-04-29T15:56:48Z)
• Weight distribution of a class of $p$-ary codes [0.0]
  We prove all possible weights of codewords in $mathcalC_alpha,beta,beta$, demonstrating that it has at most $p+1$ distinct nonzero weights. We also prove that the dual code $mathcalC_alpha,beta$ is optimal with respect to the sphere packing bound.
  arXiv  Detail & Related papers  (2025-03-24T20:53:04Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• A class of ternary codes with few weights [0.0]
  In this paper, we investigate a ternary code $mathcalC$ of length $n$, defined by $mathcalC$ := (textTr) := (textTr(dx), dots, dots, d_n$. Using recent results on explicit evaluations of exponential sums, we determine the Weil bound, and techniques, we show that the dual code of $mathcalC$ is optimal with respect to the Hamming bound.
  arXiv  Detail & Related papers  (2024-10-05T16:15:50Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Dimension-free discretizations of the uniform norm by small product sets [45.85600902330814]
  A classical inequality of Bernstein compares the supremum norm of $f$ over the unit circle to its supremum norm over the sampling set of the $K$-th roots of unity.<n>We show that dimension-free discretizations are possible with sampling sets whose cardinality is independent of $deg(f)$ and is instead governed by the maximum individual degree of $f$.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• Noncompact uniform universal approximation [0.0]
  The universal approximation theorem is generalised to uniform convergence on the (noncompact) input space $mathbbRn$. All continuous functions that vanish at infinity can be uniformly approximated by neural networks.
  arXiv  Detail & Related papers  (2023-08-07T08:54:21Z)
• Increasing subsequences, matrix loci, and Viennot shadows [0.0]
  We show that the quotient $mathbbF[mathbfx_n times n]/I_n$ admits a standard monomial basis. We also calculate the structure of $mathbbF[mathbfx_n times n]/I_n$ as a graded $mathfrakS_n times mathfrakS_n$-module.
  arXiv  Detail & Related papers  (2023-06-14T19:48:01Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• A Canonical Transform for Strengthening the Local $L^p$-Type Universal Approximation Property [4.18804572788063]
  $Lp$-type universal approximation theorems guarantee that a given machine learning model class $mathscrFsubseteq C(mathbbRd,mathbbRD)$ is dense in $Lp_mu(mathbbRd,mathbbRD)$. This paper proposes a generic solution to this approximation theoretic problem by introducing a canonical transformation which "upgrades $mathscrF$'s approximation property"
  arXiv  Detail & Related papers  (2020-06-24T17:46:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.