876:
637:
642:
387:
312:
871:{\displaystyle {\begin{aligned}\Sigma &\ll p^{1/2}\log p,\\\Sigma &\ll 2R^{1/2}p^{3/16}\log p,\\\Sigma &\ll rR^{1-1/r}p^{(r+1)/4r^{2}}(\log p)^{1/2r}\end{aligned}}}
439:
588:
202:
240:
503:
68:
150:
1149:. Mathematics and Its Applications (Soviet Series). Vol. 80. Translated from the Russian by Yu. N. Shakhov. Dordrecht: Kluwer Academic Publishers.
1197:
1104:
1041:
326:
1120:
1154:
1212:
1100:
1037:
322:
318:
1045:
335:
986:
92:
1112:
266:
601:
of the curve in question, and so (Legendre symbol or hyperelliptic case) can be taken as the degree of
403:
1060:
557:
166:
598:
532:
513:
71:
210:
458:
244:
88:
76:
1183:
41:
1180:
1150:
1116:
135:
1160:
1126:
1088:
1078:
1068:
1025:
1017:
994:
974:
253:
110:
17:
1164:
1130:
1092:
1029:
998:
978:
594:
509:
102:
966:
249:
1064:
528:
257:
1206:
536:
524:
517:
548:
87:. Such sums are basic in a number of questions, for example in the distribution of
1006:
Burgess, D. A. (1957). "The distribution of quadratic residues and non-residues".
512:. Here the sum can be evaluated (as −1), a result that is connected to the
1008:
91:, and in particular in the classical question of finding an upper bound for the
31:
1021:
449:
1188:
106:
1083:
989:(1918). "Sur la distribution des residus and nonresidus des puissances".
1073:
969:(1918). "Ueber die Verteilung der quadratischen Reste und Nichtreste".
616:, applying to give non-trivial results beyond Pólya–Vinogradov, for
132:
is then zero. This means that the cases of interest will be sums
971:
Nachrichten von der
Gesellschaft der Wissenschaften zu Göttingen
116:
Assume χ is a non-principal
Dirichlet character to the modulus
452:. A classical result is the case of a quadratic, for example,
397:
Another significant type of character sum is that formed by
1111:. Cambridge tracts in advanced mathematics. Vol. 97.
44:
1198:
PlanetMath article on the Pólya–Vinogradov inequality
640:
560:
461:
406:
338:
269:
213:
169:
138:
1046:"Exponential sums with multiplicative coefficients"
870:
582:
497:
433:
382:{\displaystyle \Sigma =O({\sqrt {N}}\log \log N).}
381:
306:
234:
207:A fundamental improvement on the trivial estimate
196:
144:
62:
949:
925:
329:have shown that there is the further improvement
1109:Multiplicative number theory I. Classical theory
605:. (More general results, for other values of
307:{\displaystyle \Sigma =O({\sqrt {N}}\log N).}
101:. Character sums are often closely linked to
8:
128:The sum taken over all residue classes mod
913:
1082:
1072:
851:
847:
823:
811:
795:
781:
771:
728:
724:
710:
706:
663:
659:
641:
639:
593:The constant implicit in the notation is
567:
559:
460:
405:
351:
337:
282:
268:
212:
168:
137:
43:
609:, can be obtained starting from there.)
152:over relatively short ranges, of length
83:, taken over a given range of values of
1147:Exponential sums and their applications
937:
894:
901:
7:
754:
689:
645:
527:relate to local zeta-functions of
523:More generally, such sums for the
339:
270:
214:
139:
25:
1184:"The Pólya–Vinogradov inequality"
434:{\displaystyle \sum \chi (F(n))}
991:J. Soc. Phys. Math. Univ. Permi
612:Weil's results also led to the
583:{\displaystyle O({\sqrt {p}}).}
551:, there are non-trivial bounds
248:, established independently by
197:{\displaystyle M\leq n<M+R.}
844:
831:
808:
796:
574:
564:
535:; this means that by means of
492:
480:
471:
465:
428:
425:
419:
413:
373:
348:
319:generalized Riemann hypothesis
298:
279:
229:
223:
57:
51:
1:
950:Montgomery & Vaughan 2007
926:Montgomery & Vaughan 1977
987:Vinogradov, Ivan Matveyevich
235:{\displaystyle \Sigma =O(N)}
498:{\displaystyle F(n)=n(n+1)}
245:Pólya–Vinogradov inequality
93:least quadratic non-residue
18:Pólya-Vinogradov inequality
1229:
1113:Cambridge University Press
63:{\textstyle \sum \chi (n)}
1022:10.1112/S0025579300001157
1053:Inventiones Mathematicae
1145:Korobov, N. M. (1992).
624:greater than 1/4.
145:{\displaystyle \Sigma }
109:(this is like a finite
1213:Analytic number theory
872:
584:
499:
435:
383:
308:
236:
198:
146:
64:
27:Mathematical construct
873:
585:
500:
436:
384:
309:
237:
199:
147:
65:
1115:. pp. 306–325.
638:
558:
533:hyperelliptic curves
459:
404:
336:
267:
256:in 1918, stating in
211:
167:
136:
42:
1101:Montgomery, Hugh L.
1065:1977InMat..43...69M
1038:Montgomery, Hugh L.
627:Assume the modulus
514:local zeta-function
393:Summing polynomials
72:Dirichlet character
1181:Weisstein, Eric W.
1105:Vaughan, Robert C.
1074:10.1007/BF01390204
1042:Vaughan, Robert C.
868:
866:
580:
495:
444:for some function
431:
379:
304:
232:
194:
142:
89:quadratic residues
60:
1122:978-0-521-84903-6
572:
356:
287:
16:(Redirected from
1220:
1194:
1193:
1168:
1134:
1096:
1086:
1076:
1050:
1033:
1002:
982:
953:
947:
941:
935:
929:
923:
917:
911:
905:
899:
881:for any integer
877:
875:
874:
869:
867:
863:
862:
855:
830:
829:
828:
827:
815:
790:
789:
785:
737:
736:
732:
719:
718:
714:
672:
671:
667:
589:
587:
586:
581:
573:
568:
539:'s results, for
504:
502:
501:
496:
440:
438:
437:
432:
388:
386:
385:
380:
357:
352:
313:
311:
310:
305:
288:
283:
254:I. M. Vinogradov
241:
239:
238:
233:
203:
201:
200:
195:
151:
149:
148:
143:
124:Sums over ranges
111:Mellin transform
103:exponential sums
69:
67:
66:
61:
21:
1228:
1227:
1223:
1222:
1221:
1219:
1218:
1217:
1203:
1202:
1179:
1178:
1175:
1157:
1144:
1141:
1139:Further reading
1123:
1099:
1048:
1036:
1005:
985:
965:
962:
957:
956:
948:
944:
936:
932:
924:
920:
914:Vinogradov 1918
912:
908:
900:
896:
891:
865:
864:
843:
819:
791:
767:
757:
751:
750:
720:
702:
692:
686:
685:
655:
648:
636:
635:
556:
555:
529:elliptic curves
510:Legendre symbol
457:
456:
402:
401:
395:
334:
333:
323:Hugh Montgomery
265:
264:
209:
208:
165:
164:
134:
133:
126:
70:of values of a
40:
39:
28:
23:
22:
15:
12:
11:
5:
1226:
1224:
1216:
1215:
1205:
1204:
1201:
1200:
1195:
1174:
1173:External links
1171:
1170:
1169:
1155:
1140:
1137:
1136:
1135:
1121:
1097:
1034:
1016:(2): 106–112.
1003:
983:
961:
958:
955:
954:
942:
930:
918:
906:
893:
892:
890:
887:
879:
878:
861:
858:
854:
850:
846:
842:
839:
836:
833:
826:
822:
818:
814:
810:
807:
804:
801:
798:
794:
788:
784:
780:
777:
774:
770:
766:
763:
760:
758:
756:
753:
752:
749:
746:
743:
740:
735:
731:
727:
723:
717:
713:
709:
705:
701:
698:
695:
693:
691:
688:
687:
684:
681:
678:
675:
670:
666:
662:
658:
654:
651:
649:
647:
644:
643:
591:
590:
579:
576:
571:
566:
563:
506:
505:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
464:
448:, generally a
442:
441:
430:
427:
424:
421:
418:
415:
412:
409:
394:
391:
390:
389:
378:
375:
372:
369:
366:
363:
360:
355:
350:
347:
344:
341:
315:
314:
303:
300:
297:
294:
291:
286:
281:
278:
275:
272:
258:big O notation
231:
228:
225:
222:
219:
216:
205:
204:
193:
190:
187:
184:
181:
178:
175:
172:
141:
125:
122:
59:
56:
53:
50:
47:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1225:
1214:
1211:
1210:
1208:
1199:
1196:
1191:
1190:
1185:
1182:
1177:
1176:
1172:
1166:
1162:
1158:
1156:0-7923-1647-9
1152:
1148:
1143:
1142:
1138:
1132:
1128:
1124:
1118:
1114:
1110:
1106:
1102:
1098:
1094:
1090:
1085:
1084:2027.42/46603
1080:
1075:
1070:
1066:
1062:
1058:
1054:
1047:
1043:
1039:
1035:
1031:
1027:
1023:
1019:
1015:
1011:
1010:
1004:
1000:
996:
992:
988:
984:
980:
976:
972:
968:
967:Pólya, George
964:
963:
959:
951:
946:
943:
939:
934:
931:
927:
922:
919:
915:
910:
907:
903:
898:
895:
888:
886:
884:
859:
856:
852:
848:
840:
837:
834:
824:
820:
816:
812:
805:
802:
799:
792:
786:
782:
778:
775:
772:
768:
764:
761:
759:
747:
744:
741:
738:
733:
729:
725:
721:
715:
711:
707:
703:
699:
696:
694:
682:
679:
676:
673:
668:
664:
660:
656:
652:
650:
634:
633:
632:
630:
625:
623:
619:
615:
614:Burgess bound
610:
608:
604:
600:
596:
577:
569:
561:
554:
553:
552:
550:
546:
542:
538:
534:
530:
526:
525:Jacobi symbol
521:
519:
518:conic section
515:
511:
489:
486:
483:
477:
474:
468:
462:
455:
454:
453:
451:
447:
422:
416:
410:
407:
400:
399:
398:
392:
376:
370:
367:
364:
361:
358:
353:
345:
342:
332:
331:
330:
328:
327:R. C. Vaughan
324:
320:
317:Assuming the
301:
295:
292:
289:
284:
276:
273:
263:
262:
261:
259:
255:
251:
247:
246:
226:
220:
217:
191:
188:
185:
182:
179:
176:
173:
170:
163:
162:
161:
159:
155:
131:
123:
121:
119:
114:
112:
108:
104:
100:
97:
94:
90:
86:
82:
79:
78:
73:
54:
48:
45:
37:
36:character sum
33:
19:
1187:
1146:
1108:
1059:(1): 69–82.
1056:
1052:
1013:
1007:
990:
970:
945:
938:Burgess 1957
933:
921:
909:
897:
882:
880:
631:is a prime.
628:
626:
621:
617:
613:
611:
606:
602:
592:
549:prime number
544:
540:
522:
507:
445:
443:
396:
316:
250:George Pólya
243:
206:
157:
153:
129:
127:
117:
115:
98:
95:
84:
80:
75:
35:
29:
1009:Mathematika
620:a power of
32:mathematics
1165:0754.11022
1131:1142.11001
1093:0362.10036
1030:0081.27101
999:48.1352.04
979:46.0265.02
960:References
902:Pólya 1918
537:André Weil
450:polynomial
107:Gauss sums
1189:MathWorld
993:: 18–28.
973:: 21–29.
952:, p. 315.
838:
776:−
762:≪
755:Σ
742:
697:≪
690:Σ
677:
653:≪
646:Σ
411:χ
408:∑
368:
362:
340:Σ
293:
271:Σ
215:Σ
174:≤
140:Σ
49:χ
46:∑
38:is a sum
1207:Category
1107:(2007).
1044:(1977).
508:and χ a
1061:Bibcode
597:in the
242:is the
105:by the
1163:
1153:
1129:
1119:
1091:
1028:
997:
977:
595:linear
96:modulo
77:modulo
1049:(PDF)
889:Notes
885:≥ 3.
599:genus
516:of a
260:that
160:say,
156:<
1151:ISBN
1117:ISBN
531:and
325:and
252:and
180:<
34:, a
1161:Zbl
1127:Zbl
1089:Zbl
1079:hdl
1069:doi
1026:Zbl
1018:doi
995:JFM
975:JFM
835:log
739:log
674:log
365:log
359:log
290:log
113:).
30:In
1209::
1186:.
1159:.
1125:.
1103:;
1087:.
1077:.
1067:.
1057:43
1055:.
1051:.
1040:;
1024:.
1012:.
734:16
547:a
543:=
520:.
321:,
120:.
74:χ
1192:.
1167:.
1133:.
1095:.
1081::
1071::
1063::
1032:.
1020::
1014:4
1001:.
981:.
940:.
928:.
916:.
904:.
883:r
860:r
857:2
853:/
849:1
845:)
841:p
832:(
825:2
821:r
817:4
813:/
809:)
806:1
803:+
800:r
797:(
793:p
787:r
783:/
779:1
773:1
769:R
765:r
748:,
745:p
730:/
726:3
722:p
716:2
712:/
708:1
704:R
700:2
683:,
680:p
669:2
665:/
661:1
657:p
629:N
622:N
618:R
607:N
603:F
578:.
575:)
570:p
565:(
562:O
545:p
541:N
493:)
490:1
487:+
484:n
481:(
478:n
475:=
472:)
469:n
466:(
463:F
446:F
429:)
426:)
423:n
420:(
417:F
414:(
377:.
374:)
371:N
354:N
349:(
346:O
343:=
302:.
299:)
296:N
285:N
280:(
277:O
274:=
230:)
227:N
224:(
221:O
218:=
192:.
189:R
186:+
183:M
177:n
171:M
158:N
154:R
130:N
118:N
99:N
85:n
81:N
58:)
55:n
52:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.