BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We establish various upper bounds on Type-I and Type-II shifted bilinear sums with Salié sums modulo a large prime q. We use these bounds to study, for fixed integers a,b≡0modq, the distribution ofsolutions to the congruence x2≡ap+bmodq, over primes p≤P. This is similar to the recently studied case of b=0, however the case b≡0modq exhibits some new difficulties.
For a wide class of integer linear recurrence sequences (u(n))n=1∞, we give an upper bound on the number of s-tuples (n1,…,ns)∈(Z∩[M+1,M+N])s such that the corresponding elements u(n1),…,u(ns) in the sequence are multiplicatively dependent.
We use a new argument to improve the error term in the asymptotic formula for the number of Diophantine m-tuples in finite fields, which is due to A. Dujella and M.Kazalicki (2021) and N. Mani and S. Rubinstein-Salzedo (2021).
We obtain upper bounds on the cardinality of Hilbert cubes in finite fields, which avoid large product sets and reciprocals of sum sets. In particular, our results replace recent estimates of N. Hegyvári and P. P. Pach (2020), which appear to be void for all admissible parameters. Our approach is different from that of N. Hegyvári and P. P. Pach and is based on some well-known bounds of double character and exponential sums over arbitrary sets, due to A. A. Karatsuba (1991) and N. G. Moshchevitin (2007), respectively.
Given an integer g and also some given integers m (sufficiently large) and c1,…,cm, we show that the number of all non-negative integers n≤M with the property that there exist non-negative integers k1,…,km such that n2=∑i=1mcigki is o((logM)m−1/2). We also obtain a similar bound when dealing with more general inequalities Q(n)−∑i=1mciλki≤B, where Q∈C[X] and also λ∈C (while B is a real number).
Let q be a prime, P≥1 and let Nq(P) denote the number of rational primes p≤P that split in the imaginary quadratic field Q(−q). The first part of this paper establishes various unconditional and conditional (under existence of a Siegel zero) lower bounds for Nq(P) in the range q1/4+ε≤P≤q, for any fixed ε>0. This improves upon what is implied by work of Pollack and Benli-Pollack. The second part of this paper is dedicated to proving an estimate for a bilinear form involving Weyl sums for modular square roots (equivalently Salié sums). Our estimate has a power saving in the so-called P{ó}lya-Vinogradov range, and our methods involve studying an additive energy coming from quadratic residues in Fq. This bilinear form is inspired by the recent automorphic motivation: the second moment for twisted L-functions attached to Kohnen newforms has recently been computed by the first and fourth authors. So the third part of this paper links the above two directions together and outlines the arithmetic applications of this bilinear form. These include the equidistribution of quadratic roots of primes, products of primes, and relaxations of a conjecture of Erdos-Odlyzko-Sarkozy.
We obtain effective bounds on the heights of algebraic integers whose orbits contain multiplicatively dependent values modulo S-integers. Our method is based on a new upper bound on the so-called S-height of polynomial values over the ring of integers of K. Our results provide an effective variant of a recent result of A.Bérczes, A.Ostafe, I.E.Shparlinski and J.H.Silverman (arXiv:1811.04971) on multiplicative dependence modulo a finitely generated subgroup by eliminating the use of non-effective results by K.F.Roth and G.Faltings.
We obtain new bounds of exponential sums modulo a prime p with sparse polynomials a0xn0+⋯+aνxnν. The bounds depend on various greatest common divisors of exponents n0,…,nν and their differences. In particular, two new bounds for binomials are obtained, improving previous results in broad ranges of parameters.
We obtain a new bound on Weyl sums with degree k≥2 polynomials of the form (τx+c)ω(n)+xn, n=1,2,…, with fixed ω(T)∈Z[T] and τ∈R, which holds for almost all c∈[0,1) and all x∈[0,1). We improve and generalise some recent results of M.~B.~Erdogan and G.~Shakan (2019), whose work also shows links between this question and some classical partial differential equations. We extend this to more general settings of families of polynomials xn+yω(n) for all (x,y)∈[0,1)2 with f(x,y)=z for a set of z∈[0,1) of full Lebesgue measure, provided that f is some Hölder function.
Recently E. Bombieri and N. M. Katz (2010) have demonstrated that several well-known results about the distribution of values of linear recurrence sequences lead to interesting statements for Frobenius traces of algebraic curves. Here we continue this line of study and establish the Möbius randomness law quantitatively for the normalised form of Frobenius traces.
Let H be a multiplicative subgroup of Fp∗ of order H>p1/4. We show that max(a,p)=1∑x∈Hep(ax)≤H1−31/2880+o(1), where ep(z)=exp(2πiz/p), which improves a result of Bourgain and Garaev (2009). We also obtain new estimates for double exponential sums with product nx with x∈H and n∈N for a short interval N of consecutive integers.
Let E1 and E2 be elliptic curves in Legendre form with integer parameters. We show there exists a constant C such that for almost all primes, for all but at most C pairs of points on the reduction of E1×E2 modulo p having equal x coordinate, at least one among P1 and P2 has a large group order. We also show similar abundance over finite fields of elements whose images under the reduction modulo p of a finite set of rational functions have large multiplicative orders
A special case of the Menshov--Rademacher theorem implies for almost all polynomials x1Z+…+xdZd∈R[Z] of degree d for the Weyl sums satisfy the upper bound ∑n=1Nexp(2πi(x1n+…+xdnd))⩽N1/2+o(1),N→∞. Here we investigate the exceptional sets of coefficients (x1,…,xd) with large values of Weyl sums for infinitely many N, and show that in terms of the Baire categories and Hausdorff dimension they are quite massive, in particular of positive Hausdorff dimension in any fixed cube inside of [0,1]d. We also use a different technique to give similar results for sums with just one monomial xnd. We apply these results to show that the set of poorly distributed modulo one polynomials is rather massive as well.
We use recent bounds on bilinear sums with modular square roots to study the distribution of solutions to congruences x2≡p(modq) with primes p≤P and integers q≤Q. This can be considered as a combined scenario of Duke, Friedlander and Iwaniec with averaging only over the modulus q and of Dunn, Kerr, Shparlinski and Zaharescu with averaging only over p.
We study the distribution of the sequence of elements of the discrete dynamical system generated by iterations of the Möbius map x↦(ax+b)/(cx+d) over a finite field of p elements at the moments of time that correspond to prime numbers. In particular, we obtain nontrivial estimates of exponential sums with such sequences.
We obtain a new bound for the number of solutions to polynomial equations in cosets of multiplicative subgroups in finite fields, which generalises previous results of P. Corvaja and U. Zannier (2013). We also obtain a conditional improvement of recent results of J. Bourgain, A. Gamburd and P. Sarnak (2016) and S. V. Konyagin, S. V. Makarychev, I. E. Shparlinski and I. V. Vyugin (2019) on the structure of solutions to the reduction of the Markoff equation x2+y2+z2=3xyz modulo a prime p.
We study an apparently new question about the behaviour of Weyl sums on a subset X⊆[0,1)d with a natural measure μ on X. For certain measure spaces (X,μ) we obtain non-trivial bounds for the mean values of the Weyl sums, and for μ-almost all points of X the Weyl sums satisfy the square root cancellation law. Moreover we characterise the size of the exceptional sets in terms of Hausdorff dimension. Finally, we derive variants of the Vinogradov mean value theorem averaging over measure spaces (X,μ). We obtain general results, which we refine for some special spaces X such as spheres, moment curves and line segments.
A Ducci sequence is a sequence of integer n-tuples obtained by iterating the map D:(a1,a2,…,an)↦(∣a1−a2∣,∣a2−a3∣,…,∣an−a1∣). Such a sequence is eventually periodic and we denote by P(n) the maximal period of such sequences for given n. We prove lower bounds for P(n) by counting certain partitions.
A. Booker and C. Pomerance (2017) have shown that any residue class modulo a prime p≥11 can be represented by a positive p-smooth square-free integer s=pO(logp) with all prime factors up to p and conjectured that in fact one can find such s with s=pO(1). Using bounds on double Kloosterman sums due to M. Z. Garaev (2010) we prove this conjecture in a stronger form s≤p3/2+o(1) and also consider more general versions of this question replacing p-smoothness of s by the stronger condition of pα-smoothness. Using bounds on multiplicative character sums and a sieve method, we also show that we can represent all residue classes by a positive square-free integer s≤p2+o(1) which is p1/(4e/2)+o(1)-smooth. Additionally, we obtain stronger results for almost all primes p.
We obtain a new lower bound on the size of value set f(F_p) of a sparse polynomial f in F_p[X] over a finite field of p elements when p is prime. This bound is uniform with respect of the degree and depends on some natural arithmetic properties of the degrees of the monomial terms of f and the number of these terms. Our result is stronger than those which canted be extracted from the bounds on multiplicities of individual values in f(F_p).
Recently, there has been a sharp rise of interest in properties of digits primes. Here we study yet another question of this kind. Namely, we fix an integer base g≥2 and then for every infinite sequence D={di}i=0∞∈{0,…,g−1}∞ of g-ary digits we consider the counting function ϖD,g(N) of integers n≤N for which ∑i=0n−1digi is prime. We construct sequences D for which ϖD,g(N) grows fast enough, and show that for some constant ϑg<g there are at most O(ϑgN) initial elements (d0,…,dN−1) of D for which ϖD,g(N)=N+O(1). We also discuss joint arithmetic properties of integers and mirror reflections of their g-ary expansions.
We obtain several estimates for bilinear form with exponential sums with binomials mxk+nxℓ. In particular we show the existence of nontrivial cancellations between such sums when the coefficients m and n vary over rather sparse sets of general nature
We obtain several estimates for bilinear form with Kloosterman sums. Such results can be interpreted as a measure of cancellations amongst with parameters from short intervals. In particular, for certain ranges of parameters we improve some recent results of Blomer, Fouvry, Kowalski, Michel and Milićević and also of Fouvry, Kowalski and Michel. In particular, we improve the bound on the error term in the asymptotic formula for mixed moments of L-series associated with Hecke eigenforms.
We obtain a nontrivial bound for cancellations between the Kloosterman sums modulo a large prime power with a prime argument running over very short interval, which in turn is based on a new estimate on bilinear sums of Kloosterman sums. These results are analogues of those obtained by various authors for Kloosterman sums modulo a prime. However the underlying technique is different and allows us to obtain nontrivial results starting from much shorter ranges.
We give an efficient construction of a reasonably small dominating set in a circulant graph on n notes and k distinct chord lengths. This result is based on bounds on some double exponential sums. .
We obtain an asymptotic formula for the average value of the divisor function over the integers n≤x in an arithmetic progression n≡a(modq), where q=pk for a prime p≥3 and a sufficiently large integer k. In particular, we break the classical barrier q≤x2/3 for such formulas, and generalise a recent result of R.~Khan (2015), making it uniform in k.
In this paper, we give several asymptotic formulas for the number of multiplicatively dependent vectors of algebraic numbers of fixed degree, or within a fixed number field, and bounded height.
Let g>1 be an integer and f(X)∈Z[X] a polynomial of positive degree with no multiple roots, and put u(n)=f(gn). In this note, we study the sequence of quadratic fields Q(u(n)) as n varies over the consecutive integers M+1,…,M+N. Fields of this type include Shanks fields and their generalizations. Using the square sieve together with new bounds on character sums, we improve an upper bound of Luca and Shparlinski (2009) on the number of n∈{M+1,…,M+N} with Q(u(n))=Q(s) for a given squarefree integer s.
We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm's success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability. We end with a conjecture about the quantum query complexity of multivariate polynomial interpolation.
We study how well Fekete polynomials Fp(X)=∑n=0p−1(pn)Xn∈Z[X] with the coefficients given by Legendre symbols modulo a prime p, can be approximated by power series representing algebraic functions of a given degree. We also obtain some explicit results describing polynomial recurrence relations which are satisfied by the coefficients of such algebraic functions.
We study the distribution of squares in a Piatetski-Shapiro sequence (⌊nc⌋)n∈N with c>1 and c∈N. We also study more general equations ⌊nc⌋=sm2, n,m∈N, 1≤n≤N for an integer s and obtain several bounds on the number of solutions for a fixed s and on average over s in an interval. These results are based on various techniques chosen depending on the range of the parameters.
We obtain lower bounds for the cardinality of k-fold sum-sets of reciprocals of elements of suitable defined short intervals in high degree extensions of finite fields. Combining our results with bounds for multilinear character sums we obtain new results on incomplete multilinear Kloosterman sums in finite fields.
Given a polynomial g of positive degree over a finite field, we show that the proportion of polynomials of degree n, which can be written as h+gk, where h is an irreducible polynomial of degree n and k is a nonnegative integer, has order of magnitude 1/°g.
There is a well-known asymptotic formula, due to W. M. Schmidt (1968) for the number of full-rank integer lattices of index at most V in Zn. This set of lattices L can naturally be partitioned with respect to the factor group Zn/L. Accordingly, we count the number of full-rank integer lattices L⊆Zn such that Zn/L is cyclic and of order at most V, and deduce that these co-cyclic lattices are dominant among all integer lattices: their natural density is (ζ(6)∏k=4nζ(k))−1≈85%. The problem is motivated by complexity theory, namely worst-case to average-case reductions for lattice problems.
We improve several recent results by Hong, Lee, Lee and Park (2012) on gaps and Bzdȩga (2014) on jumps amongst the coefficients of cyclotomic polynomials. Besides direct improvements, we also introduce several new techniques that have never been used in this area.
Using a recent improvement by Bettin and Chandee to a bound of Duke, Friedlander and Iwaniec~(1997) on double exponential sums with Kloosterman fractions, we establish a uniformity of distribution result for the fractional parts of Dedekind sums s(m,n) with m and n running over rather general sets. Our result extends earlier work of Myerson (1988) and Vardi (1987). Using different techniques, we also study the least denominator of the collection of Dedekind sums {s(m,n):m∈(Z/nZ)∗} on average for n∈[1,N].
Given a function f in a finite field Fq of q elements, we define the functional graph of f as a directed graph on q nodes labelled by the elements of Fq where there is an edge from u to v if and only if f(u)=v. We obtain some theoretic estimates on the number of non-isomorphic graphs generated by all polynomials of a given degree. We then develop a simple and practical algorithm to test the isomorphism of quadratic polynomials that has linear memory and time complexities. Furthermore, we extend this isomorphism testing algorithm to the general case of functional graphs, and prove that, while its time complexity increases only slightly, its memory complexity remains linear. We exploit this algorithm to provide an upper bound on the number of functional graphs corresponding to polynomials of degree d over Fq. Finally, we present some numerical results and compare function graphs of quadratic polynomials with those generated by random maps and pose interesting new problems.
We obtain new results concerning Lang-Trotter conjecture on Frobenius traces and Frobenius fields over single and double parametric families of elliptic curves. We also obtain similar results with respect to the Sato-Tate conjecture. In particular, we improve a result of A.C. Cojocaru and the second author (2008) towards the Lang-Trotter conjecture on average for polynomially parameterized families of elliptic curves when the parameter runs through a set of rational numbers of bounded height. Some of the families we consider are much thinner than the ones previously studied.
We use new bounds of double exponential sums with ratios of integers from prescribed intervals to get an asymptotic formula for the number of solutions to congruences ∑j=1najxjyj−1≡a0(modp), with variables from rather general sets.
We obtain a tight, up to a logarithmic factor, upper bound on the number of solutions to the equation ∑j=1najrjsj=a0, with variables r1,...,rn in an arbitrary box at the origin and variables s1,...,sn in an essentially arbitrary translation of this box. We apply this result to get an upper bound on the number of stochastic matrices with rational entries of bounded height.
We give nontrivial bounds for the bilinear sums ∑u=1U∑v=1Vαuβvep(u/f(v)) where ep(z) is a nontrivial additive character of the prime finite field Fp of p elements, with integers U, V, a polynomial f∈Fp[X] and some complex weights {αu}, {βv}. In particular, for f(X)=aX+b we obtain new bounds of bilinear sums with Kloosterman fractions. We also obtain new bounds for similar sums with multiplicative characters of Fp.
We show that for any ε>0 and a sufficiently large cube-free q, any reduced residue class modulo q can be represented as a product of 14 integers from the interval [1,q1/4e1/2+ε]. The length of the interval is at the lower limit of what is possible before the Burgess bound on the smallest quadratic nonresidue is improved. We also consider several variations of this result and give applications to Fermat quotients.
Let Pc=(⌊pc⌋)p∈P(c>1, c∈N), where P is the set of prime numbers, and ⌊⋅⌋ is the floor function. We show that for every such c there are infinitely many members of Pc having at most R(c) prime factors, giving explicit estimates for R(c) when c is near one and also when c is large.
We obtain optimal lower bounds for moments of theta functions. On the other hand, we also get new upper bounds on individual theta values and moments of theta functions on average over primes. The upper bounds are based on bounds of character sums and in particular on a modification of some recent results of M. Z. Garaev.
We improve upper bounds of F. R. K. Chung and of M. Lu, D. Wan, L.-P. Wang, X.-D. Zhang on the diameter of some Cayley graphs constructed from polynomials over finite fields.
Given two sets A and B of integers, we consider the problem of finding a set S⊆A of the smallest possible cardinality such the greatest common divisor of the elements of S∪B equals that of those of A∪B. The particular cases of B=∅ and #B=1 are of special interest and have some links with graph theory. We also consider the corresponding question for the least common multiple of the elements. We establish NP-completeness and approximation results for these problems by relating them to the Minimum Cover Problem.
We say that a set S is additively decomposed into two sets A and B if S={a+b:a∈A, b∈B}. A. Sárközy has recently conjectured that the set Q of quadratic residues modulo a prime p does not have nontrivial decompositions. Although various partial results towards this conjecture have been obtained, it is still open. Here we obtain a nontrivial upper bound on the number of such decompositions.
We estimate double sums Sχ(a,I,G)=∑x∈I∑λ∈Gχ(x+aλ),1≤a<p−1, with a multiplicative character χ modulo p where I={1,…,H} and G is a subgroup of order T of the multiplicative group of the finite field of p elements. A nontrivial upper bound on Sχ(a,I,G) can be derived from the Burgess bound if H≥p1/4+ε and from some standard elementary arguments if T≥p1/2+ε, where ε>0 is arbitrary. We obtain a nontrivial estimate in a wider range of parameters H and T. We also estimate double sums Tχ(a,G)=∑λ,μ∈Gχ(a+λ+μ),1≤a<p−1, and give an application to primitive roots modulo p with 3 non-zero binary digits.
In this paper, we mainly give a general explicit form of Cassels' p-adic embedding theorem for number fields. We also give its refined form in the case of cyclotomic fields. As a byproduct, given an irreducible polynomial f over Z, we give a general unconditional upper bound for the smallest prime number p such that f has a simple root modulo p.
Assuming the Generalized Riemann Hypothesis, we design a deterministic algorithm that, given a prime p and positive integer m=o(sqrt(p)/(log p)^4), outputs an elliptic curve E over the finite field F_p for which the cardinality of E(F_p) is divisible by m. The running time of the algorithm is mp^(1/2+o(1)), and this leads to more efficient constructions of rational functions over F_p whose image is small relative to p. We also give an unconditional version of the algorithm that works for almost all primes p, and give a probabilistic algorithm with subexponential time complexity.
Motivated by a recently introduced HIMMO key distribution scheme, we consider a modification of the noisy polynomial interpolation problem of recovering an unknown polynomial f(X)∈Z[X] from approximate values of the residues of f(t) modulo a prime p at polynomially many points t taken from a short interval.
We use bounds of mixed character sums modulo a square-free integer q of a special structure to estimate the density of integer points on the hypersurface f1(x1)+…+fn(xn)=ax1k1…xnkn for some polynomials fi∈Z[X] and nonzero integers a and ki, i=1,…,n. In the case of f1(X)=…=fn(X)=X2andk1=…=kn=1 the above hypersurface is known as the Markoff-Hurwitz hypersurface, while for f1(X)=…=fn(X)=Xnandk1=…=kn=1 it is known as the Dwork hypersurface. Our results are substantially stronger than those known for general hypersurfaces.
We use bounds of mixed character sums modulo a prime p to estimate the density of integer points on the hypersurface f1(x1)+…+fn(xn)=ax1k1…xnkn for some polynomials fi∈Z[X], nonzero integer a and positive integers ki i=1,…,n. In the case of f1(X)=…=fn(X)=X2andk1=…=kn=1 the above congruence is known as the Markoff-Hurwitz hypersurface, while for f1(X)=…=fn(X)=Xnandk1=…=kn=1 it is known as the Dwork hypersurface. Our result is substantially stronger than those known for general hypersurfaces.
Given a prime ℓ≥3 and a positive integer k≤ℓ−2, one can define a matrix Dk,ℓ, the so-called Demjanenko matrix, whose rank is equal to the dimension of the Hodge group of the Jacobian Jac(Ck,ℓ) of a certain quotient of the Fermat curve of exponent ℓ. For a fixed ℓ, the existence of k for which Dk,ℓ is singular (equivalently, for which the rank of the Hodge group of Jac(Ck,ℓ) is not maximal) has been extensively studied in the literature. We provide an asymptotic formula for the number of such k when ℓ tends to infinity.
We obtain a nontrivial upper bound for almost all elements of the sequences of real numbers which are multiplicative and at the prime indices are distributed according to the Sato--Tate density. Examples of such sequences come from coefficients of several L-functions of elliptic curves and modular forms. In particular, we show that ∣τ(n)∣≤n11/2(logn)−1/2+o(1) for a set of n of asymptotic density 1, where τ(n) is the Ramanujan τ function while the standard argument yields log2 instead of −1/2 in the power of the logarithm. Another consequence of our result is that in the number of representations of n by a binary quadratic form one has slightly more than square-root cancellations for almost all integers n. In addition we obtain a central limit theorem for such sequences, assuming a weak hypothesis on the rate of convergence to the Sato--Tate law. For Fourier coefficients of primitive holomorphic cusp forms such a hypothesis is known conditionally assuming the automorphy of all symmetric powers of the form and seems to be within reach unconditionally using the currently established potential automorphy.
For a large prime p, and a polynomial f over a finite field Fp of p elements, we obtain a lower bound on the size of the multiplicative subgroup of Fp∗ containing H≥1 consecutive values f(x), x=u+1,…,u+H, uniformly over f∈Fp[X] and an u∈Fp.
For a large prime p, a rational function ψ∈Fp(X) over the finite field Fp of p elements, and integers u and H≥1, we obtain a lower bound on the number consecutive values ψ(x), x=u+1,…,u+H that belong to a given multiplicative subgroup of Fp∗.
For a set $\cM=\{-μ,-μ+1,\ldots, λ\}\setminus\{0\}$ with non-negative integers λ,μ<q not both 0, a subset $\cS$ of the residue class ring Zq modulo an integer q≥1 is called a (λ,μ;q)-\emph{covering set} if $$ \cM \cS=\{ms \bmod q : m\in \cM,\ s\in \cS\}=\Z_q. $$ Small covering sets play an important role in codes correcting limited-magnitude errors. We give an explicit construction of a (λ,μ;q)-covering set $\cS$ which is of the size q1+o(1)max{λ,μ}−1/2 for almost all integers q≥1 and of optimal size pmax{λ,μ}−1 if q=p is prime. Furthermore, using a bound on the fourth moment of character sums of Cochrane and Shi we prove the bound ωλ,μ(q)≤q1+o(1)max{λ,μ}−1/2, for any integer q≥1, however the proof of this bound is not constructive.
We derive a new bound for some bilinear sums over points of an elliptic curve over a finite field. We use this bound to improve a series of previous results on various exponential sums and some arithmetic problems involving points on elliptic curves.
For the Gauss sums which are defined by S_n(a,q) := \sum_{x (mod q)} e(ax^n/q), Stechkin (1975) conjectured that the quantity A := \sup_{n,q\ge 2} \max_{\gcd(a,q)=1} |S_n(a,q)|/q^(1-1/n) is finite. Shparlinski (1991) proved that A is finite, but in the absence of effective bounds on the sums S_n(a,q) the precise determination of A has remained intractable for many years. Using recent work of Cochrane and Pinner (2011) on Gauss sums with prime moduli, in this paper we show that with the constant given by A = |S_6(4787,4606056)|/4606056^(5/6) = 4.709236... one has the sharp inequality |S_n(a,q)| \le Aq^(1-1/n) for all n,q \ge 2 and all integers a with gcd(a,q)=1. One interesting aspect of our method is that we apply effective lower bounds for the center density in the sphere packing problem due to Cohn and Elkies (2003) to optimize the running time of our primary computational algorithm.
We investigate the periodic structure of the exponential pseudorandom number generator obtained from the map x↦gx(modp) that acts on the set {1,…,p−1}.
We use the Burgess bound and combinatorial sieve to obtain an upper bound on the number of primes p in a dyadic interval [Q,2Q] for which a given interval [u+1,u+ψ(Q)] does not contain a quadratic non-residue modulo p. The bound is nontrivial for any function ψ(Q)→∞ as Q→∞. This is an analogue of the well known estimates on the smallest quadratic non-residue modulo p on average over primes p, which corresponds to the choice u=0.
We give a survey of a variety of recent results about the distribution and some geometric properties of points (x,y) on modular hyperbolas xy≡a(modm). We also outline a very diverse range of applications of such results, discuss multivariate generalisations and suggest a number of open problems of different levels of difficulty.
Recently, several bounds have been obtained on the number of solutions to congruences of the type (x1+s)...(xν+s)≡(y1+s)...(yν+s)≡0(modp) modulo a prime p with variables from some short intervals. Here, for almost all p and all s and also for a fixed p and almost all s, we derive stronger bounds. We also use similar ideas to show that for almost all primes, one can always find an element of a large order in any rather short interval.
We show that, for any fixed ε>0 and almost all primes p, the g-ary expansion of any fraction m/p with gcd(m,p)=1 contains almost all g-ary strings of length k<(5/24−ε)loggp. This complements a result of J. Bourgain, S. V. Konyagin, and I. E. Shparlinski that asserts that, for almost all primes, all g-ary strings of length k<(41/504−ε)loggp occur in the g-ary expansion of m/p.
We consider a modification of the classical number theoretic question about the gaps between consecutive primitive roots modulo a prime p, which by the well-known result of Burgess are known to be at most p1/4+o(1). Here we measure the distance in the Hamming metric and show that if p is a sufficiently large r-bit prime, then for any integer n∈[1,p] one can obtain a primitive root modulo p by changing at most 0.11002786...r binary digits of n. This is stronger than what can be deduced from the Burgess result. Experimentally, the number of necessary bit changes is very small. We also show that each Hilbert cube contained in the complement of the primitive roots modulo p has dimension at most O(p1/5+ε), improving on previous results of this kind.
Let $G_1,..., G_n \in \Fp[X_1,...,X_m]$ be n polynomials in m variables over the finite field $\Fp$ of p elements. A result of {É}. Fouvry and N. M. Katz shows that under some natural condition, for any fixed ε and sufficiently large prime p the vectors of fractional parts $$ (\{\frac{G_1(\vec{x})}{p}},...,\{\frac{G_n(\vec{x})}{p}}), \qquad \vec{x} \in Γ, $$ are uniformly distributed in the unit cube [0,1]n for any cube Γ∈[0,p−1]m with the side length h≥p1/2(logp)1+ε. Here we use this result to show the above vectors remain uniformly distributed, when x runs through a rather general set. We also obtain new results about the distribution of solutions to system of polynomial congruences.
We show that the reductions modulo primes p≤x of the elliptic curve Y2=X3+f(a)X+g(b), behave as predicted by the Lang-Trotter and Sato-Tate conjectures, on average over integers a∈[−A,A] and b∈[−B,B] for A and B reasonably small compared to x, provided that f(T),g(T)∈Z[T] are not powers of another polynomial over $\Q$. For f(T)=g(T)=T first results of this kind are due to E. Fouvry and M. R. Murty and have been further extended by other authors. Our technique is different from that of E. Fouvry and M. R. Murty which does not seem to work in the case of general polynomials f and g.
We consider various arithmetic questions for the Piatetski-Shapiro sequences $\fl{n^c}$ (n=1,2,3,...) with c>1, c∈N. We exhibit a positive function θ(c) with the property that the largest prime factor of $\fl{n^c}$ exceeds $n^{θ(c)-\eps}$ infinitely often. For c∈(1,87149) we show that the counting function of natural numbers n≤x for which $\fl{n^c}$ is squarefree satisfies the expected asymptotic formula. For c∈(1,145147) we show that there are infinitely many Carmichael numbers composed entirely of primes of the form $p=\fl{n^c}$.
We introduce several new methods to obtain upper bounds on the number of solutions of the congruences f(x)≡y(modp) and f(x)≡y2(modp), with a prime p and a polynomial f, where (x,y) belongs to an arbitrary square with side length M. We use these results and methods to derive non-trivial upper bounds for the number of hyperelliptic curves Y2=X2g+1+a2g−1X2g−1+...+a1X+a0 over the finite field $\F_p$ of p elements, with coefficients in a 2g-dimensional cube (a0,...,a2g−1)∈[R0+1,R0+M]×...×[R2g−1+1,R2g−1+M] that are isomorphic to a given curve and give an almost sharp lower bound on the number of non-isomorphic hyperelliptic curves with coefficients in that cube. Furthermore, we study the size of the smallest box that contain a partial trajectory of a polynomial dynamical system over $\F_p$.
We obtain a series of estimates on the number of small integers and small order Farey fractions which belong to a given coset of a subgroup of order t of the group of units of the residue ring modulo a prime p, in the case when t is small compared to p. We give two applications of these results: to the simultaneous distribution of two high degree monomials xk1 and xk2 modulo p and to a question of J. Holden and P. Moree on fixed points of the discrete logarithm.
For a prime p and an integer u with gcd(u,p)=1, we define Fermat quotients by the conditions qp(u)≡pup−1−1(modp),0≤qp(u)≤p−1. D. R. Heath-Brown has given a bound of exponential sums with N consecutive Fermat quotients that is nontrivial for N≥p1/2+ε for any fixed ε>0. We use a recent idea of M. Z. Garaev together with a form of the large sieve inequality due to S. Baier and L. Zhao, to show that on average over p one can obtain a nontrivial estimate for much shorter sums starting with N≥pε. We also obtain lower bounds on the image size of the first N consecutive Fermat quotients and use it to prove that there is a positive integer n≤p3/4+o(1) such that qp(n) is a primitive root modulo p.
We estimate the number of possible types degree patterns of k-lacunary polynomials of degree t<p which split completely modulo p. The result is based on a combination of a bound on the number of zeros of lacunary polynomials with some graph theory arguments.
Given an elliptic curve E over a finite field F_q of q elements, we say that an odd prime ell not dividing q is an Elkies prime for E if t_E^2 - 4q is a square modulo ell, where t_E = q+1 - #E(F_q) and #E(F_q) is the number of F_q-rational points on E; otherwise ell is called an Atkin prime. We show that there are asymptotically the same number of Atkin and Elkies primes ell < L on average over all curves E over F_q, provided that L >= (log q)^e for any fixed e > 0 and a sufficiently large q. We use this result to design and analyse a fast algorithm to generate random elliptic curves with #E(F_p) prime, where p varies uniformly over primes in a given interval [x,2x].
Given a prime p, an elliptic curve $\E/\F_p$ over the finite field $\F_p$ of p elements and a binary \lrs\ $\(u(n)\)_{n =1}^\infty$ of order~r, we study the distribution of the sequence of points ∑j=0r−1u(n+j)Pj,n=1,...,N, on average over all possible choices of $\F_p$-rational points P1,...,Pr on~$\E$. For a sufficiently large N we improve and generalise a previous result in this direction due to E.~El~Mahassni.
We consider the problem of recovering a hidden element s of a finite field $\F_q$ of q elements from queries to an oracle that for a given $x\in \F_q$ returns (x+s)e for a given divisor e∣q−1. We use some techniques from additive combinatorics and analytic number theory that lead to more efficient algorithms than the naive interpolation algorithm, for example, they use substantially fewer queries to the oracle.
We improve an estimate of A.Granville (1987) on the number of vanishing Fermat quotients qp(ℓ) modulo a prime p when ℓ runs through primes ℓ≤N. We use this bound to obtain an unconditional improvement of the conditional (under the Generalised Riemann Hypothesis) estimate of Y. Ihara (2006) on a certain sum, related to vanishing Fermat quotients. In turn this sum appears in the study of the index of certain subfields of of cyclotomic fields $\Q(\exp(2 πi/p^2))$.
We obtain explicit formulas for the number of non-isomorphic elliptic curves with a given group structure (considered as an abstract abelian group). Moreover, we give explicit formulas for the number of distinct group structures of all elliptic curves over a finite field. We use these formulas to derive some asymptotic estimates and tight upper and lower bounds for various counting functions related to classification of elliptic curves accordingly to their group structure. Finally, we present results of some numerical tests which exhibit several interesting phenomena in the distribution of group structures. We pose getting an explanation to these as an open problem.
We study the collection of group structures that can be realized as a group of rational points on an elliptic curve over a finite field (such groups are well known to be of rank at most two). We also study various subsets of this collection which correspond to curves over prime fields or to curves with a prescribed torsion. Some of our results are rigorous and are based on recent advances in analytic number theory, some are conditional under certain widely believed conjectures, and others are purely heuristic in nature.
Following Kraitchik and Lehmer, we say that a positive integer n≡1(mod8) is an x-pseudosquare if it is a quadratic residue for each odd prime p≤x, yet is not a square. We extend this defintion to algebraic curves and say that n is an x-pseudopoint of a curve f(u,v)=0 (where f∈Z[U,V]) if for all sufficiently large primes p≤x the congruence f(n,m)≡0(modp) is satisfied for some m. We use the Bombieri bound of exponential sums along a curve to estimate the smallest x-pseudopoint, which shows the limitations of the modular approach to searching for points on curves.
Given integers a and m≥2, let $\Hm$ be the following set of integral points $$ \Hm= \{(x,y) \ : \ xy \equiv a \pmod m,\ 1\le x,y \le m-1\} $$ We improve several previously known upper bounds on va(m), the number of vertices of the convex closure of $\Hm$, and show that uniformly over all a with gcd(a,m)=1 we have va(m)≤m1/2+o(1) and furthermore, we have va(m)≤m5/12+o(1) for m which are almost squarefree.
Let $\cC$ be a smooth absolutely irreducible curve of genus g≥1 defined over $\F_q$, the finite field of q elements. Let $# \cC(\F_{q^n})$ be the number of $\F_{q^n}$-rational points on $\cC$. Under a certain multiplicative independence condition on the roots of the zeta-function of $\cC$, we derive an asymptotic formula for the number of n=1,...,N such that $(# \cC(\F_{q^n}) - q^n -1)/2gq^{n/2}$ belongs to a given interval $\cI \subseteq [-1,1]$. This can be considered as an analogue of the Sato-Tate distribution which covers the case when the curve $\E$ is defined over $\Q$ and considered modulo consecutive primes p, although in our scenario the distribution function is different. The above multiplicative independence condition has, recently, been considered by E. Kowalski in statistical settings. It is trivially satisfied for ordinary elliptic curves and we also establish it for a natural family of curves of genus g=2.
For a prime p and an integer a∈Z we obtain nontrivial upper bounds on the number of solutions to the congruence xx≡a(modp), 1≤x≤p−1. We use these estimates to estimate the number of solutions to the congruence xx≡yy(modp), 1≤x,y≤p−1, which is of cryptographic relevance.
We obtain several asymptotic estimates for the sums of the restricted divisor function $$ τ_{M,N}(k) = #\{1 \le m \le M, \ 1\le n \le N: mn = k\} $$ over short arithmetic progressions, which improve some results of J. Truelsen. Such estimates are motivated by the links with the pair correlation problem for fractional parts of the quadratic function αk2, k=1,2,... with a real α.
Let $\E$ be an elliptic curve over a finite field $\F_{q}$ of q elements, with gcd(q,6)=1, given by an affine Weierstraß equation. We also use x(P) to denote the x-component of a point $P = (x(P),y(P))\in \E$. We estimate character sums of the form $$ \sum_{n=1}^N χ\(x(nP)x(nQ)\) \quad \text{and}\quad \sum_{n_1, \ldots, n_k=1}^N ψ\(\sum_{j=1}^k c_j x\(\(\prod_{i =1}^j n_i\) R\)\) $$ on average over all $\F_q$ rational points P, Q and R on $\E$, where χ is a quadratic character, ψ is a nontrivial additive character in $\F_q$ and $(c_1, \ldots, c_k)\in \F_q^k$ is a non-zero vector. These bounds confirm several recent conjectures of D. Jao, D. Jetchev and R. Venkatesan, related to extracting random bits from various sequences of points on elliptic curves.
Dynamical systems generated by iterations of multivariate polynomials with slow degree growth have proved to admit good estimates of exponential sums along their orbits which in turn lead to rather stronger bounds on the discrepancy for pseudorandom vectors generated by these iterations. Here we add new arguments to our original approach and also extend some of our recent constructions and results to more general orbits of polynomial iterations which may involve distinct polynomials as well. Using this construction we design a new class of hash functions from iterations of polynomials and use our estimates to motivate their "mixing" properties.
We obtain some theoretic and experimental results concerning various properties (the number of fixed points, image distribution, cycle lengths) of the dynamical system naturally associated with Fermat quotients acting on the set {0,...,p−1}. We also consider pseudorandom properties of Fermat quotients such as joint distribution and linear complexity.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.