Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Prescribing the binary digits of squarefree numbers and quadratic residues


Authors: Rainer Dietmann, Christian Elsholtz and Igor E. Shparlinski
Journal: Trans. Amer. Math. Soc. 369 (2017), 8369-8388
MSC (2010): Primary 11A63, 11B30, 11N25; Secondary 11H06, 11L40, 11P70, 11T30
DOI: https://doi.org/10.1090/tran/6903
Published electronically: May 5, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the equidistribution of multiplicatively defined sets, such as the squarefree integers, quadratic non-residues or primitive roots, in sets which are described in an additive way, such as sumsets or Hilbert cubes. In particular, we show that if one fixes any proportion less than $ 40\%$ of the digits of all numbers of a given binary bit length, then the remaining set still has the asymptotically expected number of squarefree integers. Next, we investigate the distribution of primitive roots modulo a large prime $ p$, establishing a new upper bound on the largest dimension of a Hilbert cube in the set of primitive roots, improving on a previous result of the authors. Finally, we study sumsets in finite fields and asymptotically find the expected number of quadratic residues and non-residues in such sumsets, given that their cardinalities are big enough. This significantly improves on a recent result by Dartyge, Mauduit and Sárközy. Our approach introduces several new ideas, combining a variety of methods, such as bounds of exponential and character sums, geometry of numbers and additive combinatorics.


References [Enhancements On Off] (What's this?)

  • [1] William D. Banks, Alessandro Conflitti, and Igor E. Shparlinski, Character sums over integers with restricted $ g$-ary digits, Illinois J. Math. 46 (2002), no. 3, 819-836. MR 1951242
  • [2] William D. Banks and Igor E. Shparlinski, Arithmetic properties of numbers with restricted digits, Acta Arith. 112 (2004), no. 4, 313-332. MR 2046944, https://doi.org/10.4064/aa112-4-1
  • [3] William D. Banks and Igor E. Shparlinski, Average value of the Euler function on binary palindromes, Bull. Pol. Acad. Sci. Math. 54 (2006), no. 2, 95-101. MR 2266140, https://doi.org/10.4064/ba54-2-1
  • [4] J. Bourgain, Estimates on exponential sums related to the Diffie-Hellman distributions, Geom. Funct. Anal. 15 (2005), no. 1, 1-34. MR 2140627, https://doi.org/10.1007/s00039-005-0500-4
  • [5] Jean Bourgain, Prescribing the binary digits of primes, Israel J. Math. 194 (2013), no. 2, 935-955. MR 3047097, https://doi.org/10.1007/s11856-012-0104-2
  • [6] Jean Bourgain, Prescribing the binary digits of primes, II, Israel J. Math. 206 (2015), no. 1, 165-182. MR 3319636, https://doi.org/10.1007/s11856-014-1129-5
  • [7] Mei-Chu Chang, On a question of Davenport and Lewis and new character sum bounds in finite fields, Duke Math. J. 145 (2008), no. 3, 409-442. MR 2462111, https://doi.org/10.1215/00127094-2008-056
  • [8] Mei-Chu Chang, Burgess inequality in $ \mathbb{F}_{p^2}$, Geom. Funct. Anal. 19 (2009), no. 4, 1001-1016. MR 2570312, https://doi.org/10.1007/s00039-009-0031-5
  • [9] Sylvain Col, Diviseurs des nombres ellipséphiques, Period. Math. Hungar. 58 (2009), no. 1, 1-23 (French, with French summary). MR 2487242, https://doi.org/10.1007/s10998-009-9001-9
  • [10] Sylvain Col, Palindromes dans les progressions arithmétiques, Acta Arith. 137 (2009), no. 1, 1-41 (French). MR 2481980, https://doi.org/10.4064/aa137-1-1
  • [11] Cécile Dartyge, Christian Mauduit, and András Sárközy, Polynomial values and generators with missing digits in finite fields, Funct. Approx. Comment. Math. 52 (2015), no. 1, 65-74. MR 3326124, https://doi.org/10.7169/facm/2015.52.1.5
  • [12] H. Davenport and D. J. Lewis, Character sums and primitive roots in finite fields, Rend. Circ. Mat. Palermo (2) 12 (1963), 129-136. MR 0167482
  • [13] J. A. Dias da Silva and Y. O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994), no. 2, 140-146. MR 1272299, https://doi.org/10.1112/blms/26.2.140
  • [14] Rainer Dietmann, Christian Elsholtz, and Igor E. Shparlinski, On gaps between primitive roots in the Hamming metric, Q. J. Math. 64 (2013), no. 4, 1043-1055. MR 3151603, https://doi.org/10.1093/qmath/has022
  • [15] Rainer Dietmann, Christian Elsholtz, and Igor E. Shparlinski, On gaps between quadratic non-residues in the Euclidean and Hamming metrics, Indag. Math. (N.S.) 24 (2013), no. 4, 930-938. MR 3124809, https://doi.org/10.1016/j.indag.2013.02.005
  • [16] Michael Drmota and Christian Mauduit, Weyl sums over integers with affine digit restrictions, J. Number Theory 130 (2010), no. 11, 2404-2427. MR 2678855, https://doi.org/10.1016/j.jnt.2010.04.006
  • [17] Michael Drmota, Christian Mauduit, and Joël Rivat, Primes with an average sum of digits, Compos. Math. 145 (2009), no. 2, 271-292. MR 2501419, https://doi.org/10.1112/S0010437X08003898
  • [18] Paul Erdős, Christian Mauduit, and András Sárközy, On arithmetic properties of integers with missing digits. II. Prime factors, Paul Erdős memorial collection, Discrete Math. 200 (1999), no. 1-3, 149-164. MR 1692287, https://doi.org/10.1016/S0012-365X(98)00331-8
  • [19] M. Gabdullin, On squares in special sets of finite fields (in Russian), Chebyshevskii Sbornik 17 (2016), no. 2, 56-63.
  • [20] M. R. Gabdullin, On the squares in the set of elements of a finite field with constraints on the coefficients of its basis expansion, Mat. Zametki 100 (2016), no. 6, 807-824 (Russian, with Russian summary). MR 3588906, https://doi.org/10.4213/mzm11091
  • [21] Sidney W. Graham and Igor E. Shparlinski, On RSA moduli with almost half of the bits prescribed, Discrete Appl. Math. 156 (2008), no. 16, 3150-3154. MR 2462121, https://doi.org/10.1016/j.dam.2007.12.012
  • [22] Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, 2nd ed., Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. MR 1261419
  • [23] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
  • [24] Glyn Harman and Imre Kátai, Primes with preassigned digits. II, Acta Arith. 133 (2008), no. 2, 171-184. MR 2417463, https://doi.org/10.4064/aa133-2-5
  • [25] N. Hegyvári and A. Sárközy, On Hilbert cubes in certain sets, Ramanujan J. 3 (1999), no. 3, 303-314. MR 1714944, https://doi.org/10.1023/A:1009883404485
  • [26] Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214
  • [27] A. A. Karatsuba, Distribution of values of Dirichlet characters on additive sequences, Dokl. Akad. Nauk SSSR 319 (1991), no. 3, 543-545 (Russian); English transl., Soviet Math. Dokl. 44 (1992), no. 1, 145-148. MR 1148968
  • [28] Anatolij A. Karatsuba, Basic analytic number theory, Springer-Verlag, Berlin, 1993. Translated from the second (1983) Russian edition and with a preface by Melvyn B. Nathanson. MR 1215269
  • [29] Sergei Konyagin, Arithmetic properties of integers with missing digits: distribution in residue classes, Period. Math. Hungar. 42 (2001), no. 1-2, 145-162. MR 1832701, https://doi.org/10.1023/A:1015256809636
  • [30] S. V. Konyagin, Estimates for character sums in finite fields, Mat. Zametki 88 (2010), no. 4, 529-542 (Russian, with Russian summary); English transl., Math. Notes 88 (2010), no. 3-4, 503-515. MR 2882215, https://doi.org/10.1134/S0001434610090221
  • [31] Sergei Konyagin, Christian Mauduit, and András Sárközy, On the number of prime factors of integers characterized by digit properties, Period. Math. Hungar. 40 (2000), no. 1, 37-52. MR 1774933, https://doi.org/10.1023/A:1004887821978
  • [32] Florian Luca, Arithmetic properties of positive integers with fixed digit sum, Rev. Mat. Iberoam. 22 (2006), no. 2, 369-412. MR 2294785, https://doi.org/10.4171/RMI/461
  • [33] Christian Mauduit and Joël Rivat, Sur un problème de Gelfond: la somme des chiffres des nombres premiers, Ann. of Math. (2) 171 (2010), no. 3, 1591-1646 (French, with English and French summaries). MR 2680394, https://doi.org/10.4007/annals.2010.171.1591
  • [34] Christian Mauduit and Zaid Shawket, Sommes d'exponentielles associées aux fonctions digitales restreintes, Unif. Distrib. Theory 7 (2012), no. 1, 105-133 (French, with English summary). MR 2943163
  • [35] N. G. Moshchevitin and I. D. Shkredov, On the multiplicative properties modulo $ m$ of numbers with missing digits, Mat. Zametki 81 (2007), no. 3, 385-404 (Russian, with Russian summary); English transl., Math. Notes 81 (2007), no. 3-4, 338-355. MR 2333944, https://doi.org/10.1134/S000143460703008X
  • [36] Alina Ostafe and Igor E. Shparlinski, Multiplicative character sums and products of sparse integers in residue classes, Period. Math. Hungar. 64 (2012), no. 2, 247-255. MR 2925171, https://doi.org/10.1007/s10998-012-6771-2
  • [37] Xuancheng Shao, Character sums over unions of intervals, Forum Math. 27 (2015), no. 5, 3017-3026. MR 3393387, https://doi.org/10.1515/forum-2013-0080
  • [38] Tomasz Schoen, Arithmetic progressions in sums of subsets of sparse sets, Acta Arith. 147 (2011), no. 3, 283-289. MR 2773206, https://doi.org/10.4064/aa147-3-7
  • [39] Igor E. Shparlinski, Prime divisors of sparse integers, Period. Math. Hungar. 46 (2003), no. 2, 215-222. MR 2004674, https://doi.org/10.1023/A:1025996312037
  • [40] Igor E. Shparlinski, On RSA moduli with prescribed bit patterns, Des. Codes Cryptogr. 39 (2006), no. 1, 113-122. MR 2201387, https://doi.org/10.1007/s10623-005-3137-2
  • [41] Igor E. Shparlinski, Exponential sums and prime divisors of sparse integers, Period. Math. Hungar. 57 (2008), no. 1, 93-99. MR 2448400, https://doi.org/10.1007/s10998-008-7093-3

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 11A63, 11B30, 11N25, 11H06, 11L40, 11P70, 11T30

Retrieve articles in all journals with MSC (2010): 11A63, 11B30, 11N25, 11H06, 11L40, 11P70, 11T30


Additional Information

Rainer Dietmann
Affiliation: Department of Mathematics, Royal Holloway, University of London, Egham, Surrey, TW20 0EX, United Kingdom
Email: rainer.dietmann@rhul.ac.uk

Christian Elsholtz
Affiliation: Institute of Analysis and Number Theory, Graz University of Technology, Kopernikusgasse 24/II, A-8010 Graz, Austria
Email: elsholtz@math.tugraz.at

Igor E. Shparlinski
Affiliation: Department of Pure Mathematics, University of New South Wales, Sydney, New South Wales 2052, Australia
Email: igor.shparlinski@unsw.edu.au

DOI: https://doi.org/10.1090/tran/6903
Keywords: Digital problems, square-free numbers, non-residues, finite fields, Hilbert cubes
Received by editor(s): June 17, 2015
Received by editor(s) in revised form: January 12, 2016
Published electronically: May 5, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society