Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSub-Linear Point Counting for Variable Separated Curves over Prime Power Rings
451
0
0.0
(
0
)
Added by
J. Maurice Rojas
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $k,pin mathbb{N}$ with $p$ prime and let $finmathbb{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_iinmathbb{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 $(dklog p)^{O(1)}sqrt{p}$, and admits a quantum version for smooth curves working in time $(dlog 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.
rate research
Read More
Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings from the viewpoint of logical (inter-)definability. All problems that we consider are decidable in polynomial time, but not expressible in fixed-point logic with counting. They also provide natural candidates for a separation of polynomial time from rank logics, which extend fixed-point logics by operators for determining the rank of definable matrices and which are sufficient for solvability problems over fields. Based on the structure theory of finite rings, we establish logical reductions among various solvability problems. Our results indicate that all solvability problems for linear equation systems that separate fixed-point logic with counting from PTIME can be reduced to solvability over commutative rings. Moreover, we prove closure properties for classes of queries that reduce to solvability over rings, which provides normal forms for logics extended with solvability operators. We conclude by studying the extent to which fixed-point logic with counting can express problems in linear algebra over finite commutative rings, generalising known results on the logical definability of linear-algebraic problems over finite fields.
The aim of this article is to establish the specialization method on characteristic ideals for finitely generated torsion modules over a complete local normal domain R that is module-finite over $O[[x_1, ..., x_d]]$, where $O$ is the ring of integers of a finite extension of the field of p-adic integers $Q_p$. The specialization method is a technique that recovers the information on the characteristic ideal $char_R(M)$ from $char_{R/I}(M/IM)$, where I varies in a certain family of nonzero principal ideals of R. As applications, we prove Euler system bound over Cohen-Macaulay normal domains by combining the main results in an earlier article of the first named author and then we prove one of divisibilities of the Iwasawa main conjecture for two-variable Hida deformations generalizing the main theorem obtained in an article of the first named author.
In this paper we use a theorem first proved by S.W.Golomb and a famous inequality by J.B. Rosser and L.Schoenfeld in order to prove that there exists an exact formula for $pi(n)$ which holds infinitely often.
Let $G$ be a finite cyclic group. Every sequence $S$ of length $l$ over $G$ can be written in the form $S=(x_1g)cdotldotscdot(x_lg)$ where $gin G$ and $x_1, ldots, x_lin[1, ord(g)]$, and the index $ind(S)$ of $S$ is defined to be the minimum of $(x_1+cdots+x_l)/ord(g)$ over all possible $gin G$ such that $langle g rangle =G$. Recently the second and the third authors determined the index of any minimal zero-sum sequence $S$ of length 5 over a cyclic group of a prime order where $S=g^2(x_2g)(x_3g)(x_4g)$. In this paper, we determine the index of any minimal zero-sum sequence $S$ of length 5 over a cyclic group of a prime power order. It is shown that if $G=langle grangle$ is a cyclic group of prime power order $n=p^mu$ with $p geq 7$ and $mugeq 2$, and $S=(x_1g)(x_2g)(x_2g)(x_3g)(x_4g)$ with $x_1=x_2$ is a minimal zero-sum sequence with $gcd(n,x_1,x_2,x_3,x_4,x_5)=1$, then $ind(S)=2$ if and only if $S=(mg)(mg)(mfrac{n-1}{2}g)(mfrac{n+3}{2}g)(m(n-3)g)$ where $m$ is a positive integer such that $gcd(m,n)=1$.
In this paper, we study expanding phenomena in the setting of matrix rings. More precisely, we will prove that If $A$ is a set of $M_2(mathbb{F}_q)$ and $|A|gg q^{7/2}$, then we have [|A(A+A)|, ~|A+AA|gg q^4.] If $A$ is a set of $SL_2(mathbb{F}_q)$ and $|A|gg q^{5/2}$, then we have [|A(A+A)|, ~|A+AA|gg q^4.] We also obtain similar results for the cases of $A(B+C)$ and $A+BC$, where $A, B, C$ are sets in $M_2(mathbb{F}_q)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
