تقرير
Sub-Linear Point Counting for Variable Separated Curves over Prime Power Rings
| العنوان: | Sub-Linear Point Counting for Variable Separated Curves over Prime Power Rings |
|---|---|
| المؤلفون: | Robelle, Caleb, Rojas, J. Maurice, Zhu, Yuyu |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Number Theory, Computer Science - Computational Complexity, Mathematics - Algebraic Geometry |
| الوصف: | Let $k,p\in \mathbb{N}$ with $p$ prime and let $f\in\mathbb{Z}[x_1,x_2]$ be a bivariate polynomial with degree $d$ and all coefficients of absolute value at most $p^k$. Suppose also that $f$ is variable separated, i.e., $f=g_1+g_2$ for $g_i\in\mathbb{Z}[x_i]$. We give the first algorithm, with complexity sub-linear in $p$, to count the number of roots of $f$ over $\mathbb{Z}$ mod $p^k$ for arbitrary $k$: Our Las Vegas randomized algorithm works in time $(dk\log p)^{O(1)}\sqrt{p}$, and admits a quantum version for smooth curves working in time $(d\log p)^{O(1)}k$. Save for some subtleties concerning non-isolated singularities, our techniques generalize to counting roots of polynomials in $\mathbb{Z}[x_1,\ldots,x_n]$ over $\mathbb{Z}$ mod $p^k$. Our techniques are a first step toward efficient point counting for varieties over Galois rings (which is relevant to error correcting codes over higher-dimensional varieties), and also imply new speed-ups for computing Igusa zeta functions of curves. The latter zeta functions are fundamental in arithmetic geometry. Comment: 18 pages, no figures. Submitted to a conference. Comments and questions welcome! |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2102.01626 |
| رقم الأكسشن: | edsarx.2102.01626 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |