Hostname: page-component-669899f699-g7b4s Total loading time: 0 Render date: 2025-04-30T05:03:39.788Z Has data issue: false hasContentIssue false
  • English
  • Français

Smooth numbers with few nonzero binary digits

Part of: Elementary number theory Multiplicative number theory Exponential sums and character sums

Published online by Cambridge University Press:  20 June 2023

Maximilian Hauck  and
Igor E. Shparlinski Open the ORCID record for Igor E. Shparlinski [Opens in a new window]
Maximilian Hauck
Affiliation:
Department of Mathematics, Universität Bonn, Endenicher Allee 60, 53115 Bonn, Germany e-mail: [email protected]
Igor E. Shparlinski*
Affiliation:
School of Mathematics and Statistics, University of New South Wales, Sydney, NSW 2052, Australia
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We use bounds of character sums and some combinatorial arguments to show the abundance of very smooth numbers which also have very few nonzero binary digits.

Keywords

Smooth integerssparse binary representationscharacter sums

MSC classification

Primary: 11A63: Radix representation; digital problems 11L40: Estimates on character sums 11N25: Distribution of integers with specified multiplicative constraints
Type
Article
Information
Canadian Mathematical Bulletin , Volume 67 , Issue 1 , March 2024 , pp. 74 - 89
Check for updates
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of The Canadian Mathematical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

Footnotes

This work started during a very enjoyable visit by the authors to the Max Planck Institute for Mathematics, Bonn, whose hospitality and support is very much appreciated. During the preparation of this work, I.S. was also supported in part by the Australian Research Council Grant DP200100355.

References

Banks, W. and Shparlinski, I. E., Bounds on short character sums and $L$ -functions with characters to a powerful modulus . J. Anal. Math. 139(2019), 239–263.CrossRefGoogle Scholar
Bateman, P. T., Note on the coefficients of the cyclotomic polynomial . Bull. Amer. Math. Soc. 55(1949), 1180–1181.CrossRefGoogle Scholar
Bourgain, J., Estimates on exponential sums related to Diffie–Hellman distributions . Geom. Funct. Anal. 15(2005), 1–34.CrossRefGoogle Scholar
Bourgain, J., Prescribing the binary digits of primes . Israel J. Math. 194(2013), 935–955.CrossRefGoogle Scholar
Bourgain, J., Prescribing the binary digits of primes, II . Israel J. Math. 206(2015), 165–182.CrossRefGoogle Scholar
Bugeaud, Y., On the digital representation of integers with bounded prime factors . Osaka J. Math. 55(2018), 315–324.Google Scholar
Bugeaud, Y., On the Zeckendorf representation of smooth numbers . Mosc. Math. J. 21(2021), 31–42.CrossRefGoogle Scholar
Bugeaud, Y. and Kaneko, H., On the digital representation of smooth numbers . Math. Proc. Cambridge Philos. Soc. 165(2018), 533–540.CrossRefGoogle Scholar
Chang, M.-C., Kerr, B., and Shparlinski, I. E., On the exponential large sieve inequality for sparse sequences modulo primes . J. Math. Anal. Appl. 459(2018), 53–81.CrossRefGoogle Scholar
Col, S., Palindromes dans les progressions arithmétiques . Acta Arith. 137(2009), 1–41.CrossRefGoogle Scholar
Dietmann, R., Elsholtz, C., and Shparlinski, I. E., On gaps between primitive roots in the Hamming metric . Quart. J. Math. 64(2013), 1043–1055.CrossRefGoogle Scholar
Dietmann, R., Elsholtz, C., and Shparlinski, I. E., On gaps between quadratic non-residues in the Euclidean and Hamming metrics . Indag. Math. 24(2013), 930–938.CrossRefGoogle Scholar
Dietmann, R., Elsholtz, C., and Shparlinski, I. E., Prescribing the binary digits of squarefree numbers and quadratic residues . Trans. Amer. Math. Soc. 369(2017), 8369–8388.CrossRefGoogle Scholar
Drmota, M., Mauduit, C., and Rivat, J., Prime numbers in two bases . Duke Math. J. 169(2020), 1809–1876.CrossRefGoogle Scholar
Graham, S. W. and Shparlinski, I. E., On RSA moduli with almost half of the bits prescribed . Discrete Appl. Math. 56(2008), 3150–3154.CrossRefGoogle Scholar
Granville, A., Smooth numbers: computational number theory and beyond . In Proc. MSRI Conf. Algorithmic Number Theory: Lattices, Number Fields, Curves, and Cryptography, Cambridge University Press, Cambridge, 2008, pp. 267–323.Google Scholar
Hare, K. G., Laishram, S., and Stoll, T., Stolarsky’s conjecture and the sum of digits of polynomial values . Proc. Amer. Math. Soc. 139(2011), 39–49.CrossRefGoogle Scholar
Harper, A. J., Minor arcs, mean values, and restriction theory for exponential sums over smooth numbers . Compos. Math. 152(2016), 1121–1158.CrossRefGoogle Scholar
Hildebrand, A. and Tenenbaum, G., On integers free of large prime factors . Trans. Amer. Math. Soc. 296(1986), 265–290.CrossRefGoogle Scholar
Iwaniec, H., On zeros of Dirichlet’s $L$ series . Invent. Math. 23(1974), 97–104.CrossRefGoogle Scholar
Iwaniec, H. and Kowalski, E., Analytic number theory, Amer. Math. Soc., Providence, RI, 2004.Google Scholar
Karwatowski, F., Primes with one excluded digit . Acta Arith. 202(2022), 105–121.CrossRefGoogle Scholar
MacWilliams, F. J. and Sloane, N. J. A., The theory of error-correcting codes, North-Holland, Amsterdam, 1977.Google Scholar
Mauduit, C. and Rivat, J., La somme des chiffres des carrés . Acta Math. 203(2009), 107–148.CrossRefGoogle Scholar
Mauduit, C. and Rivat, J., Sur un problème de Gelfond: la somme es chiffres des nombres premiers . Ann. of Math. 171(2010), 1591–1646.CrossRefGoogle Scholar
Maynard, J., Primes with restricted digits . Invent. Math. 217(2019), 127–218.CrossRefGoogle Scholar
Maynard, J., Primes and polynomials with restricted digits . Int. Math. Res. Not. 2022(2022), 10626–10648.CrossRefGoogle Scholar
Meng, X., On RSA moduli with half of the bits prescribed . J. Number Theory. 133(2013), 105–109.CrossRefGoogle Scholar
Mertens, F., Ein Beitrag zur analytischen Zahlentheorie . J. Reine Angew. Math. 78(1874), 46–62.Google Scholar
Naslund, E., The tail distribution of the sum of digits of prime numbers . Unif. Distrib. Theor. 10(2015), 63–68.Google Scholar
Pratt, K., Primes from sums of two squares and missing digits . Proc. Lond. Math. Soc. 120(2020), 770–830.CrossRefGoogle Scholar
Shparlinski, I. E., On primitive polynomials . Problemy Peredachi Informatsii 23 (1987), 100–103 (in Russian).Google Scholar
Shparlinski, I. E., On RSA moduli with prescribed bit patterns . Des. Codes Cryptogr. 39(2006), 113–122.CrossRefGoogle Scholar
Shparlinski, I. E., Exponential sums and prime divisors of sparse integers . Period. Math. Hungar. 57(2008), 93–99.CrossRefGoogle Scholar
Swaenepoel, C., Prime numbers with a positive proportion of preassigned digits . Proc. Lond. Math. Soc. 121(2020), 83–151.CrossRefGoogle Scholar