Product sets of rationals, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm

Jean Bourgain; Sergei V. Konyagin; Igor E. Shparlinski

doi:10.1093/imrn/rnn090

Product sets of rationals, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm

Jean Bourgain^*, Sergei V. Konyagin, Igor E. Shparlinski

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

40 Citations (Scopus)

Abstract

We give a lower bound on the size of the product set of two arbitrary subsets of the set of Farey fractions of a given order and apply it to study the distribution of elements of multiplicative groups in residue rings. For example, we prove a conjecture of J. Holden and P. Moree on the behavior of the number of solutions to the congruence g^h ≡ h (mod p), 1 ≤g, h ≤p-1, on average over primes p. This congruence appears in studying fixed points of the discrete logarithm.

Original language	English
Article number	rnn090
Pages (from-to)	1-29
Number of pages	29
Journal	International Mathematics Research Notices
Volume	2008
Issue number	1
DOIs	https://doi.org/10.1093/imrn/rnn090 https://doi.org/10.1093/imrn/rnp041
Publication status	Published - 2008

Bibliographical note

Corrigendum can be found in International Mathematics Research Notices, Volume 2009(16), 3146-3147, http://dx.doi.org/10.1093/imrn/rnp041

Access to Document

Cite this

@article{6c83a6308c5e48389490cb73f0c6eea4,

title = "Product sets of rationals, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm",

abstract = "We give a lower bound on the size of the product set of two arbitrary subsets of the set of Farey fractions of a given order and apply it to study the distribution of elements of multiplicative groups in residue rings. For example, we prove a conjecture of J. Holden and P. Moree on the behavior of the number of solutions to the congruence gh ≡ h (mod p), 1 ≤g, h ≤p-1, on average over primes p. This congruence appears in studying fixed points of the discrete logarithm.",

author = "Jean Bourgain and Konyagin, \{Sergei V.\} and Shparlinski, \{Igor E.\}",

note = "Corrigendum can be found in International Mathematics Research Notices, Volume 2009(16), 3146-3147, http://dx.doi.org/10.1093/imrn/rnp041",

year = "2008",

doi = "10.1093/imrn/rnn090",

language = "English",

volume = "2008",

pages = "1--29",

journal = "International Mathematics Research Notices",

issn = "1073-7928",

publisher = "Oxford University Press",

number = "1",

}

TY - JOUR

T1 - Product sets of rationals, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm

AU - Bourgain, Jean

AU - Konyagin, Sergei V.

AU - Shparlinski, Igor E.

N1 - Corrigendum can be found in International Mathematics Research Notices, Volume 2009(16), 3146-3147, http://dx.doi.org/10.1093/imrn/rnp041

PY - 2008

Y1 - 2008

N2 - We give a lower bound on the size of the product set of two arbitrary subsets of the set of Farey fractions of a given order and apply it to study the distribution of elements of multiplicative groups in residue rings. For example, we prove a conjecture of J. Holden and P. Moree on the behavior of the number of solutions to the congruence gh ≡ h (mod p), 1 ≤g, h ≤p-1, on average over primes p. This congruence appears in studying fixed points of the discrete logarithm.

AB - We give a lower bound on the size of the product set of two arbitrary subsets of the set of Farey fractions of a given order and apply it to study the distribution of elements of multiplicative groups in residue rings. For example, we prove a conjecture of J. Holden and P. Moree on the behavior of the number of solutions to the congruence gh ≡ h (mod p), 1 ≤g, h ≤p-1, on average over primes p. This congruence appears in studying fixed points of the discrete logarithm.

UR - https://www.scopus.com/pages/publications/77952241082

UR - http://www.scopus.com/inward/record.url?scp=84864146205&partnerID=8YFLogxK

U2 - 10.1093/imrn/rnn090

DO - 10.1093/imrn/rnn090

M3 - Article

AN - SCOPUS:77952241082

SN - 1073-7928

VL - 2008

SP - 1

EP - 29

JO - International Mathematics Research Notices

JF - International Mathematics Research Notices

IS - 1

M1 - rnn090

ER -

Product sets of rationals, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this