Namespaces
Variants
Actions

Difference between revisions of "Distribution of power residues and non-residues"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Fixed a TeX problem on displayed eq after "he obtained a bound")
Line 7: Line 7:
 
$n>1$, is solvable (or unsolvable) in integers. Questions on the distribution of power residues and non-residues have been studied most fully in the case modulo a prime number $p$. Let $q=\mathrm{gcd}(n,p-1)$. Then the congruence $y^n\equiv x\pmod{p}$ is solvable for $(p-1)/q$ values of $x$ in the set $1,\ldots,p-1$ and unsolvable for the remaining $(q-1)(p-1)/q$ values (see [[Two-term congruence|Two-term congruence]]). However, comparatively little is known about how these values are distributed among the numbers $1,\ldots,p-1$.
 
$n>1$, is solvable (or unsolvable) in integers. Questions on the distribution of power residues and non-residues have been studied most fully in the case modulo a prime number $p$. Let $q=\mathrm{gcd}(n,p-1)$. Then the congruence $y^n\equiv x\pmod{p}$ is solvable for $(p-1)/q$ values of $x$ in the set $1,\ldots,p-1$ and unsolvable for the remaining $(q-1)(p-1)/q$ values (see [[Two-term congruence|Two-term congruence]]). However, comparatively little is known about how these values are distributed among the numbers $1,\ldots,p-1$.
  
The first results about the distribution of power residues were obtained by C.F. Gauss (see [[#References|[1]]]) in 1796. From that time until the work of I.M. Vinogradov only isolated special results were obtained on questions concerning the distribution of power residues and non-residues. In 1915, Vinogradov (see [[#References|[2]]]) proved a series of general results about the distribution of power residues and non-residues, and about primitive roots (cf. [[Primitive root|Primitive root]]) modulo $p$ among the numbers $1,\ldots,p$. In particular, he obtained the bound
+
The first results about the distribution of power residues were obtained by C.F. Gauss (see {{Cite|Ga}}) in 1796. From that time until the work of I.M. Vinogradov only isolated special results were obtained on questions concerning the distribution of power residues and non-residues. In 1915, Vinogradov (see {{Cite|Vi}}) proved a series of general results about the distribution of power residues and non-residues, and about primitive roots (cf. [[Primitive root|Primitive root]]) modulo $p$ among the numbers $1,\ldots,p$. In particular, he obtained the bound
  
 
$$
 
$$
Line 19: Line 19:
 
where $k$ is the number of distinct prime divisors of $p-1$, for the least primitive root $N_{\mathrm{min}}^*$ modulo $p$.
 
where $k$ is the number of distinct prime divisors of $p-1$, for the least primitive root $N_{\mathrm{min}}^*$ modulo $p$.
  
In addition, he made a number of conjectures on the distribution of quadratic residues and non-residues (see [[Vinogradov hypotheses|Vinogradov hypotheses]]) which stimulated a series of investigations in this area. Thus, Yu.V. Linnik [[#References|[3]]] proved that for sufficiently large $N$, the number of prime numbers $p$ in the interval $[N^{\epsilon},N]$ for which $N_{\mathrm{min}}>p^{\epsilon}$ does not exceed a certain constant $C(\epsilon)$, depending only on $\epsilon>0$. Thus, the prime numbers $p$ for which $N_{\mathrm{min}}>p^{\epsilon}$, if they exist at all, are met only very rarely. Another significant step in the work on Vinogradov's conjectures was the theorem of D.A. Burgess [[#References|[4]]]: For any fixed sufficiently small $\delta>0$, the maximal distance $d(p)$ between neighbouring quadratic non-residues satisfies the inequality
+
In addition, he made a number of conjectures on the distribution of quadratic residues and non-residues (see [[Vinogradov hypotheses|Vinogradov hypotheses]]) which stimulated a series of investigations in this area. Thus, Yu.V. Linnik {{Cite|Li}} proved that for sufficiently large $N$, the number of prime numbers $p$ in the interval $[N^{\epsilon},N]$ for which $N_{\mathrm{min}}>p^{\epsilon}$ does not exceed a certain constant $C(\epsilon)$, depending only on $\epsilon>0$. Thus, the prime numbers $p$ for which $N_{\mathrm{min}}>p^{\epsilon}$, if they exist at all, are met only very rarely. Another significant step in the work on Vinogradov's conjectures was the theorem of D.A. Burgess {{Cite|Bu}}: For any fixed sufficiently small $\delta>0$, the maximal distance $d(p)$ between neighbouring quadratic non-residues satisfies the inequality
  
 
$$d(p)\leq A(\delta)p^{\frac{1}{4}+\delta}.$$
 
$$d(p)\leq A(\delta)p^{\frac{1}{4}+\delta}.$$
Line 31: Line 31:
 
$$y^2\equiv f(x)\pmod{p},$$
 
$$y^2\equiv f(x)\pmod{p},$$
  
the proof of which requires techniques of abstract algebraic geometry. For a simple account of Burgess' theorem see [[#References|[5]]], [[#References|[6]]].
+
the proof of which requires techniques of abstract algebraic geometry. For a simple account of Burgess' theorem see {{Cite|St}}, {{Cite|Ka}}.
  
 
====References====
 
====References====
  
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> C.F. Gauss, "Untersuchungen über höhere Arithmetik" , A. Maser (1889) (Translated from Latin) {{MR|0188045}} {{ZBL|21.0166.04}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> I.M. Vinogradov, "Selected works" , Springer (1985) (Translated from Russian) {{MR|0807530}} {{ZBL|0577.01049}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> Yu.V. Linnik, ''Dokl. Akad. Nauk SSSR'' , '''36''' (1942) pp. 131</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> D.A. Burgess, "The distribution of quadratic residues and non-residues" ''Mathematika'' , '''4''' : 8 (1957) pp. 106–112 {{MR|0093504}} {{ZBL|0081.27101}} </TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> S.A. Stepanov, "Constructive methods in the theory of equations over finite fields" ''Proc. Steklov Inst. Math.'' , '''132''' (1975) pp. 271–281 ''Trudy Mat. Inst. Steklov.'' , '''132''' (1973) pp. 237–246 {{MR|0337976}} {{ZBL|}} </TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> A.A. Karatsuba, "Character sums and primitive roots in finite fields" ''Soviet Math.-Dokl.'' , '''9''' : 3 (1968) pp. 755–757 ''Dokl. Akad. Nauk SSSR'' , '''180''' : 6 (1968) pp. 1287–1289 {{MR|}} {{ZBL|0182.37501}} </TD></TR></table>
+
{|
 +
|-
 +
|valign="top"|{{Ref|Bu}}||valign="top"| D.A. Burgess, "The distribution of quadratic residues and non-residues" ''Mathematika'', '''4''' : 8 (1957) pp. 106–112 {{MR|0093504}} {{ZBL|0081.27101}}
 +
|-
 +
|valign="top"|{{Ref|Ga}}||valign="top"| C.F. Gauss, "Untersuchungen über höhere Arithmetik", A. Maser (1889) (Translated from Latin) {{MR|0188045}} {{ZBL|21.0166.04}}
 +
|-
 +
|valign="top"|{{Ref|Ka}}||valign="top"| A.A. Karatsuba, "Character sums and primitive roots in finite fields" ''Soviet Math.-Dokl.'', '''9''' : 3 (1968) pp. 755–757 ''Dokl. Akad. Nauk SSSR'', '''180''' : 6 (1968) pp. 1287–1289 {{MR|}} {{ZBL|0182.37501}}
 +
|-
 +
|valign="top"|{{Ref|Li}}||valign="top"| Yu.V. Linnik, ''Dokl. Akad. Nauk SSSR'', '''36''' (1942) pp. 131
 +
|-
 +
|valign="top"|{{Ref|St}}||valign="top"| S.A. Stepanov, "Constructive methods in the theory of equations over finite fields" ''Proc. Steklov Inst. Math.'', '''132''' (1975) pp. 271–281 ''Trudy Mat. Inst. Steklov.'', '''132''' (1973) pp. 237–246 {{MR|0337976}} {{ZBL|}}
 +
|-
 +
|valign="top"|{{Ref|Vi}}||valign="top"| I.M. Vinogradov, "Selected works", Springer (1985) (Translated from Russian) {{MR|0807530}} {{ZBL|0577.01049}}
 +
|-
 +
|}

Revision as of 21:28, 20 April 2012


The distribution among the numbers $1,\ldots,m-1$ of those values of $x$ for which the congruence

$$y^n\equiv x\pmod{m},$$

$n>1$, is solvable (or unsolvable) in integers. Questions on the distribution of power residues and non-residues have been studied most fully in the case modulo a prime number $p$. Let $q=\mathrm{gcd}(n,p-1)$. Then the congruence $y^n\equiv x\pmod{p}$ is solvable for $(p-1)/q$ values of $x$ in the set $1,\ldots,p-1$ and unsolvable for the remaining $(q-1)(p-1)/q$ values (see Two-term congruence). However, comparatively little is known about how these values are distributed among the numbers $1,\ldots,p-1$.

The first results about the distribution of power residues were obtained by C.F. Gauss (see [Ga]) in 1796. From that time until the work of I.M. Vinogradov only isolated special results were obtained on questions concerning the distribution of power residues and non-residues. In 1915, Vinogradov (see [Vi]) proved a series of general results about the distribution of power residues and non-residues, and about primitive roots (cf. Primitive root) modulo $p$ among the numbers $1,\ldots,p$. In particular, he obtained the bound

$$ N_{\mathrm{min}} < p^{\frac{1}{2\sqrt{e}}}(\ln p)^2 $$

for the least quadratic non-residue $N_{\mathrm{min}}$, and the bound

$$N^*_{\mathrm{min}}\leq 2^{2k}\sqrt{p}\ln p,$$

where $k$ is the number of distinct prime divisors of $p-1$, for the least primitive root $N_{\mathrm{min}}^*$ modulo $p$.

In addition, he made a number of conjectures on the distribution of quadratic residues and non-residues (see Vinogradov hypotheses) which stimulated a series of investigations in this area. Thus, Yu.V. Linnik [Li] proved that for sufficiently large $N$, the number of prime numbers $p$ in the interval $[N^{\epsilon},N]$ for which $N_{\mathrm{min}}>p^{\epsilon}$ does not exceed a certain constant $C(\epsilon)$, depending only on $\epsilon>0$. Thus, the prime numbers $p$ for which $N_{\mathrm{min}}>p^{\epsilon}$, if they exist at all, are met only very rarely. Another significant step in the work on Vinogradov's conjectures was the theorem of D.A. Burgess [Bu]: For any fixed sufficiently small $\delta>0$, the maximal distance $d(p)$ between neighbouring quadratic non-residues satisfies the inequality

$$d(p)\leq A(\delta)p^{\frac{1}{4}+\delta}.$$

In particular, one has

$$N_{\mathrm{min}}\leq B(\delta)p^{\frac{1}{4\sqrt{e}}+\delta}.$$

In these inequalities, the constants $A(\delta)$, $B(\delta)$ depend only on $\delta$ and not on $p$. The proof of Burgess' theorem is very complicated; it is based on the Hasse–Weil theorem on the number of solutions of the hyper-elliptic congruence

$$y^2\equiv f(x)\pmod{p},$$

the proof of which requires techniques of abstract algebraic geometry. For a simple account of Burgess' theorem see [St], [Ka].

References

[Bu] D.A. Burgess, "The distribution of quadratic residues and non-residues" Mathematika, 4 : 8 (1957) pp. 106–112 MR0093504 Zbl 0081.27101
[Ga] C.F. Gauss, "Untersuchungen über höhere Arithmetik", A. Maser (1889) (Translated from Latin) MR0188045 Zbl 21.0166.04
[Ka] A.A. Karatsuba, "Character sums and primitive roots in finite fields" Soviet Math.-Dokl., 9 : 3 (1968) pp. 755–757 Dokl. Akad. Nauk SSSR, 180 : 6 (1968) pp. 1287–1289 Zbl 0182.37501
[Li] Yu.V. Linnik, Dokl. Akad. Nauk SSSR, 36 (1942) pp. 131
[St] S.A. Stepanov, "Constructive methods in the theory of equations over finite fields" Proc. Steklov Inst. Math., 132 (1975) pp. 271–281 Trudy Mat. Inst. Steklov., 132 (1973) pp. 237–246 MR0337976
[Vi] I.M. Vinogradov, "Selected works", Springer (1985) (Translated from Russian) MR0807530 Zbl 0577.01049
How to Cite This Entry:
Distribution of power residues and non-residues. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Distribution_of_power_residues_and_non-residues&oldid=24932
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article