Upper bounds for k-th coset representatives modulo n (Q5569217)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3282747
Language Label Description Also known as
default for all languages
No label defined
    English
    Upper bounds for k-th coset representatives modulo n
    scientific article; zbMATH DE number 3282747

      Statements

      Upper bounds for k-th coset representatives modulo n (English)
      0 references
      0 references
      1969
      0 references
      coprime residue-class group mod n
      0 references
      upper bounds
      0 references
      Let \(n\) and \(k\) be positive integers, let \(C(n)\) denote the coprime residue-class group mod \(n\) (i.e., the multiplicative group of residue classes mod \(n\) which are relatively prime to \(n\)), and let \(C_k(n)\) denote the subgroup of \(k\)-th powers. Write \(\nu = \nu_k(n) = [C(n) :C_k(n)]\), and let \(1 = g_0 < g_1< \ldots < g_{\nu-1}\) be the smallest positive representatives of the \(\nu\) cosets of \(C_k(n)\). The author obtains several upper bounds for \(g_n = g_n(n,k)\). The first of these has the form \[ g_n \le 1 + \frac{An}{\varphi(n)}\left(\frac{m\nu}{\nu-m}\right)^{1/2}\, n^{1/2}\, \log n \tag{1} \] for \(0\le m\le \nu-1\), where \(\varphi\) is Euler's function and \(A = (2 + 3\sqrt 5)/\sqrt{30}<1.59\). He also obtains a similar result which is more effective when \(n\) is large, and from it he deduces that \[ g_{\nu-1} = O_{k,\varepsilon}\left(n^{3/8 + \varepsilon}\right) \tag{2} \] in any case, while if a certain technical condition on the prime factorizations of \(n\) and \(k\) holds, then \[ g_{\nu-1} = O_{k,\varepsilon}\left(n^{(1 - \delta)/4 + \varepsilon}\right). \tag{3} \] Here \(\delta\) is any positive real number, the notation indicates that the implied constants depend only on \(k\) and \(\varepsilon\), and the technical condition (Condition A) certainly holds if \(n\) is cubefree or if \(k\) is odd and squarefree. Let Condition B be the statement that the number of distinct prime factors of \(n\) is bounded above by a function of \(k\) alone. If Condition B holds, then (2) can be improved to read \[ g_{\nu-1} = O_{k,\varepsilon}\left(n^{3(1 - \delta)/8 + \varepsilon}\right). \tag{4} \] while if Conditions A and B both hold, then (3) can be replaced by \[ g_{\nu-1} = O_{k,\varepsilon}\left(n^{(1 - \delta)/4 + \varepsilon}\right). \tag{3} \] Here \(\delta\) is a very small positive function of \(k\) (an explicit formula is given), and \(\delta\to 0\) as \(k\to+\infty\). The results (2), (3), (4), (5) generalize and strengthen certain theorems of \textit{H. Davenport} and \textit{P. Erdős} [Publ. Math. 2, 252--265 (1953; Zbl 0050.04302)]. The strengthening is made possible by the remarkable estimates for character sums obtained by \textit{D. A. Burgess} [Proc. Lond. Math. Soc. (3) 13, 524--536 (1963; Zbl 0123.04404)]. In addition to these estimates, the proofs require several lemmas of independent interest. The author concludes by pointing out that inequalities of the type (1) have a non-trivial application to the theory of homogeneous diagonal congruences. Details of this will appear in a later paper.
      0 references

      Identifiers