skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Counting points on smooth plane quartics
Abstract We present efficient algorithms for counting points on a smooth plane quartic curve X modulo a prime p . We address both the case where X is defined over  $${\mathbb {F}}_p$$ F p and the case where X is defined over $${\mathbb {Q}}$$ Q and p is a prime of good reduction. We consider two approaches for computing $$\#X({\mathbb {F}}_p)$$ # X ( F p ) , one which runs in $$O(p\log p\log \log p)$$ O ( p log p log log p ) time using $$O(\log p)$$ O ( log p ) space and one which runs in $$O(p^{1/2}\log ^2p)$$ O ( p 1 / 2 log 2 p ) time using $$O(p^{1/2}\log p)$$ O ( p 1 / 2 log p ) space. Both approaches yield algorithms that are faster in practice than existing methods. We also present average polynomial-time algorithms for $$X/{\mathbb {Q}}$$ X / Q that compute $$\#X({\mathbb {F}}_p)$$ # X ( F p ) for good primes $$p\leqslant N$$ p ⩽ N in $$O(N\log ^3 N)$$ O ( N log 3 N ) time using O ( N ) space. These are the first practical implementations of average polynomial-time algorithms for curves that are not cyclic covers of $${\mathbb {P}}^1$$ P 1 , which in combination with previous results addresses all curves of genus $$g\leqslant 3$$ g ⩽ 3 . Our algorithms also compute Cartier–Manin/Hasse–Witt matrices that may be of independent interest.  more » « less
Award ID(s):
1946311
PAR ID:
10420423
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Research in Number Theory
Volume:
9
Issue:
1
ISSN:
2522-0160
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Mathematische Zeitschrift)
    Abstract For every integer k there exists a bound $$B=B(k)$$ B = B ( k ) such that if the characteristic polynomial of $$g\in \textrm{SL}_n(q)$$ g ∈ SL n ( q ) is the product of $$\le k$$ ≤ k pairwise distinct monic irreducible polynomials over $$\mathbb {F}_q$$ F q , then every element x of $$\textrm{SL}_n(q)$$ SL n ( q ) of support at least B is the product of two conjugates of g . We prove this and analogous results for the other classical groups over finite fields; in the orthogonal and symplectic cases, the result is slightly weaker. With finitely many exceptions ( p ,  q ), in the special case that $$n=p$$ n = p is prime, if g has order $$\frac{q^p-1}{q-1}$$ q p - 1 q - 1 , then every non-scalar element $$x \in \textrm{SL}_p(q)$$ x ∈ SL p ( q ) is the product of two conjugates of g . The proofs use the Frobenius formula together with upper bounds for values of unipotent and quadratic unipotent characters in finite classical groups. 
    more » « less
  2. ; (, The Electronic Journal of Combinatorics)
    Let $$p$$ be an odd  prime, $q=p^e$, $$e \geq 1$$, and $$\mathbb{F} = \mathbb{F}_q$$ denote the finite field of $$q$$ elements.  Let $$f: \mathbb{F}^2\to \mathbb{F}$$ and  $$g: \mathbb{F}^3\to \mathbb{F}$$  be functions, and  let $$P$$ and $$L$$ be two copies of the 3-dimensional vector space $$\mathbb{F}^3$$. Consider a bipartite graph $$\Gamma_\mathbb{F} (f, g)$$ with vertex partitions $$P$$ and $$L$$ and with edges defined as follows: for every $$(p)=(p_1,p_2,p_3)\in P$$ and every $$[l]= [l_1,l_2,l_3]\in L$$, $$\{(p), [l]\} = (p)[l]$$ is an edge in $$\Gamma_\mathbb{F} (f, g)$$ if $$p_2+l_2 =f(p_1,l_1) \;\;\;\text{and}\;\;\; p_3 + l_3 = g(p_1,p_2,l_1).$$The following question  appeared in Nassau: Given $$\Gamma_\mathbb{F} (f, g)$$,  is it always possible to find a function $$h:\mathbb{F}^2\to \mathbb{F}$$ such that the graph $$\Gamma_\mathbb{F} (f, h)$$  with the same vertex set as $$\Gamma_\mathbb{F} (f, g)$$ and with edges $(p)[l]$  defined in a similar way  by the system $$p_2+l_2 =f(p_1,l_1) \;\;\;\text{and}\;\;\; p_3 + l_3 = h(p_1,l_1),$$ is isomorphic to $$\Gamma_\mathbb{F} (f, g)$$ for infinitely many $$q$$?  In this paper we show that the  answer to the question is negative and the graphs $$\Gamma_{\mathbb{F}_p}(p_1\ell_1, p_1\ell_1p_2(p_1 + p_2 + p_1p_2))$$ provide such an example for $$p \equiv 1 \pmod{3}$$. Our argument is based on proving that the automorphism group of these graphs has order $$p$$, which is the smallest possible order of the automorphism group of graphs of the form $$\Gamma_{\mathbb{F}}(f, g)$$. 
    more » « less
  3. ; ; ; ; (, International Conference on Learning Representations (ICLR))
    We study the $$\ell_p$$ regression problem, which requires finding $$\mathbf{x}\in\mathbb R^{d}$$ that minimizes $$\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_p$$ for a matrix $$\mathbf{A}\in\mathbb R^{n \times d}$$ and response vector $$\mathbf{b}\in\mathbb R^{n}$$. There has been recent interest in developing subsampling methods for this problem that can outperform standard techniques when $$n$$ is very large. However, all known subsampling approaches have run time that depends exponentially on $$p$$, typically, $$d^{\mathcal{O}(p)}$$, which can be prohibitively expensive. We improve on this work by showing that for a large class of common \emph{structured matrices}, such as combinations of low-rank matrices, sparse matrices, and Vandermonde matrices, there are subsampling based methods for $$\ell_p$$ regression that depend polynomially on $$p$$. For example, we give an algorithm for $$\ell_p$$ regression on Vandermonde matrices that runs in time $$\mathcal{O}(n\log^3 n+(dp^2)^{0.5+\omega}\cdot\text{polylog}\,n)$$, where $$\omega$$ is the exponent of matrix multiplication. The polynomial dependence on $$p$$ crucially allows our algorithms to extend naturally to efficient algorithms for $$\ell_\infty$$ regression, via approximation of $$\ell_\infty$$ by $$\ell_{\mathcal{O}(\log n)}$$. Of practical interest, we also develop a new subsampling algorithm for $$\ell_p$$ regression for arbitrary matrices, which is simpler than previous approaches for $$p \ge 4$$. 
    more » « less
  4. ; ; ; ; ; ; (, Journal of the ACM)
    We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q , and since the mid-1990s all results had polynomial time-space tradeoffs, e.g., Q = ~ Θ( n/√ S ) or Q = ~Θ( n 5/2 /S 3/2 ). In this article we show that there is no polynomial tradeoff between time and space and that it is possible to simultaneously achieve almost optimal space n 1+ o (1) and almost optimal query time n o (1) . More precisely, we achieve the following space-time tradeoffs: n 1+ o (1) space and log 2+ o (1) n query time, n log 2+ o (1) n space and n o (1) query time, n 4/3+ o (1) space and log 1+ o (1) n query time. We reduce a distance query to a variety of point location problems in additively weighted Voronoi diagrams and develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures. 
    more » « less
  5. ; (, Mathematika)
    We examine correlations of the Möbius function over $$\mathbb{F}_{q}[t]$$ with linear or quadratic phases, that is, averages of the form 1 $$\begin{eqnarray}\frac{1}{q^{n}}\mathop{\sum }_{\deg f0$$ if $$Q$$ is linear and $$O(q^{-n^{c}})$$ for some absolute constant $c>0$ if $$Q$$ is quadratic. The latter bound may be reduced to $$O(q^{-c^{\prime }n})$$ for some $$c^{\prime }>0$$ when $Q(f)$ is a linear form in the coefficients of $$f^{2}$$ , that is, a Hankel quadratic form, whereas, for general quadratic forms, it relies on a bilinear version of the additive-combinatorial Bogolyubov theorem. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email