Pa ame ic Algo i hms o he 5-Modula Analog o ES
(Sie pi´nski): S uc u e o Solu ions, Pa ame e iza ion, and
Cons uc i e P oo s (SERP)
E. Dyachenko
dyachenk[email p o ec ed]
No embe 25, 2025
Abs ac
We conside he p oblem o ep esen ing he ac ion
5
P
as a sum o h ee dis inc uni
ac ions: 5
P=1
A+1
B+1
C, A < B < C, A, B, C ∈N.
We analyze he case o p imes
P≡
1 (
mod
5), o which wo ypes o solu ions a e
dis inguished:
ED1
(exac ly one denomina o di isible by
P
, namely
C
=
cP
) and
ED2
(exac ly wo denomina o s di isible by
P
, namely
B
=
bP
and
C
=
cP
). Pa ame ic
cons uc ions and enume a ion algo i hms a e de eloped, including ansi ions be ween ypes
o solu ions.
The pape p oposes a de e minis ic algo i hm based on sea ching o he in e sec ion
o a pa ame ic la ice, de ined by a pai (
αi, d′
i
), wi h he box
Bk
(
T
). Fo any ixed
p ime
P≡
1 (
mod
5) he algo i hm cons uc i ely p oduces a solu ion. Using analy ic
me hods (Bombie i–Vinog ado heo em, Chebo a e heo em), i is shown ha he densi y
o admissible pa ame e s is high, which ensu es polyloga i hmic sea ch complexi y in he
a e age case, i.e., o mos p imes. A s ic complexi y gua an ee o all p imes emains
condi ional and depends on he ini e co e ing hypo hesis.
This s udy con inues he wo k o coe icien 4( he E d˝os–S aus conjec u e) [
2
]; he e
a simila s uc u e o pa ame e iza ion and solu ions is ex ended o coe icien 5. In he
analy ic applica ions, a e aging ools a e p o ided, used o densi y es ima es in pa ame ic
boxes.
1 In oduc ion
The Sie pi´nski p oblem in he 5-modula a ian is o mula ed as ollows: o a p ime
P
one
mus ind na u al numbe s A<B<Csa is ying
5
P=1
A+1
B+1
C.(1.1)
2020 Ma hema ics Subjec Classi ica ion: P ima y 11N05, 11P21; Seconda y 94A60, 20P05.
Key wo ds and ph ases: ac o iza ion, Bombie i–Vinog ado la ge sie e, he la ge sie e o G ea es, de e min-
is ic algo i hms; analy ic numbe heo y; numbe heo y.
* Licence: Tex is a ailable unde he C ea i e Commons NonComme cial-NoDe i a i es 4.0 In e na ional
(CC BY-NC-ND 4.0)
1
Analogous o he E d˝os–S aus conjec u e o
4
P
, he e he coe icien 5leads o a change in
he s uc u e o pa ame e iza ions and o new ypes o solu ions. Fo p imes
P≡
1 (
mod
5) wo
cons uc i e classes a e dis inguished:
•ED1: exac ly one denomina o di isible by P(wi hou loss o gene ali y C=cP );
•ED2: exac ly wo denomina o s di isible by P(namely B=bP and C=cP).
1.1 T ansi ion om 4/P o 5/P
The me hods o pa ame e iza ion and p oo s om [
2
] a e p ese ed in he p esen s udy, bu he
co e o mulas change in he ansi ion 4→5. In pa icula :
•es ima e o he minimal denomina o : P < 5A < 3P;
•in ED1 he ela ion akes he o m 5c−1 = γP (ins ead o 4c−1 = γP);
•in ED2 he co e akes he o m = 5bc −b−cand (5b−1)(5c−1) = 5Pδ + 1.
Thus, he p oblem 5
/P
is a di ec analogue o he case 4
/P
, bu equi es new cons uc i e
echniques. Unlike ac o iza ion-based app oaches used in classical wo ks on ESC, he e me hods
o ini e co e ing o esidue classes and la ice algo i hms a e applied. These ools allow one
o p o e he exis ence o solu ions o e e y p ime
P≡
1 (
mod
5) and ensu e polyloga i hmic
complexi y o he sea ch algo i hm.
2 Mo i a ion
The pa ame e iza ion o he equa ion and he di ision in o mul iplici y con igu a ions (
P|B
and/o
P|C
) make i possible o cons uc explici sea ch p ocedu es and o p o e he exis ence
o solu ions o he case
P≡
1 (
mod
5). This app oach no only gua an ees he exis ence o
solu ions bu also de ines he s uc u e o amilies in a i hme ic p og essions.
The possibili y o ans e ing he cons uc i e me hod om coe icien 4 o coe icien 5
was co ec ly no ed in [
7
]. In he p esen wo k his ans e is ca ied ou explici ly wi hin he
amewo k o he
ED1/ED2
me hods de eloped in [
2
]. The key elemen he e is he mechanism
o ini e co e ing o esidue classes, which gua an ees he exis ence o solu ions o e e y p ime
P≡
1 (
mod
5) wi hou ecou se o ac o iza ion. Thus, he mo i a ion o he s udy is o show
ha cons uc i e me hods based on la ices and co e ing o esidue classes allow one o mo e
om asymp o ic easoning o e ec i e algo i hms wi h polyloga i hmic complexi y.
3 O de ing
Fo he classes
P≡
4
,
3
,
2 (
mod
5) explici decomposi ions a e a ailable; he emaining case is
P≡1 (mod 5).
3.1 Explici decomposi ions o P≡ 1 (mod 5)
Le P= 5P′+ 4 be p ime:
5
P=5
5P′+ 4 =1
P′+ 1 +1
2·(P′+ 1) ·(5P′+ 4) +1
2·(P′+ 1) ·(5P′+ 4).
Le P= 5P′+ 3 be p ime:
5
P=1
P′+ 1 +1
(P′+ 1)(5P′+ 3) +1
(P′+ 1)(5P′+ 3).
2
Le P= 5P′+ 2 be p ime (he e P′is odd):
5
P=1
P′+ 1+2
(P′+ 1) ·(5P′+ 2)+1
(P′+ 1) ·(5P′+ 2) =1
P′+ 1+1
(P′+1)
2·(5P′+ 2)+1
(P′+ 1) ·(5P′+ 2),
whe e he hi d summand is u he de ailed as a sum o wo pa s, since
P′
+ 1 is e en. The
case P= 5P′+ 1 is he subjec o his pape .
3.2 Es ima e o he minimal denomina o
I A≤B≤Cand A, B, C ∈N, hen
5
P>1
A⇒5A > P ⇒P < 5A.
Mo eo e , om A≤B≤Ci ollows ha
5
P=1
A+1
B+1
C≤3
A⇒5A≤3P,
and, excluding he degene a e case A=B=C, we ob ain s ic bounds:
P < 5A < 3P. (3.1)
3
4 No a ion
Main pa ame e s
Pp ime numbe >2, wi h 5∤P; o en P≡1 (mod 5),P≡2 (mod 5),P≡3 (mod 5),P≡4 (mod 5)
P′in ege : P= 5P′+ 1
A, B, C denomina o s in he Sie pi´nski hypo hesis o mula, o de ed A≤B≤C
H(S) Sie pi´nski hypo hesis: 5
P=1
A+1
B+1
C
Pa ame e s o he ED1 and ED2 me hods
γ5c−1
P(o 5b−1
Pin he second case); o en γ≡4 (mod 5),gcd(γ, c)=1o gcd(γ, b) = 1
u, “mul iplie s” in he iden i y: o ED1 u=γA −c, =γB −c,u =c2;
o he a ian wi h b:u=γA −b, =γC −b,u =b2; always u≤ . The ac o iza ion dimension in he case o 5 is achie ed by passing o no malized pa ame e s uand .
δ =P·δ, wi h ED2 equi ing δ|bc
b, c in ED2 B=bP and/o C=cP
= 5bc −b−c
, s = 5b−1,s= 5c−1, wi h ≡s≡4 (mod 5), s = 5Pδ + 1
ggcd(b, c)
b′, c′decomposi ion b=b′g,c=c′g(no malized o m)
d′squa e ac o in he decomposi ion o δ
αsqua e ee ac o in he decomposi ion o δ
T ansi ions be ween me hods
CED1(P)se o admissible quad uples (γ, c, u, ) o ED1
CED2(P)se o admissible iples (δ, b, c) o ED2
yminimal di iso o 5c−1, wi h y≡3 (mod 5)
P′′ modulus o ED1 in con olu ion, de ined ia γby he o mula ...
ED2→ED1 ansi ion: A=bc
δ,B=bP;u=γA −c, =γB −c
ED1→ED2 ansi ion: A=u+c
γ,b= +c
γP ,δ=bc
A
An icon olu ion algo i hm o he e e se s ep ED1→ED2 acco ding o he o mulas abo e
La ices and boxes
kdimension o he ec o pa ame e
u0(P) ec o shi o he a ine class
Λ,Λjsubla ices o Zko index Mo Mj
M, Mjindices o subla ices
Bk(T)box {u∈Zk: 1 ≤ui≤T}
B(I)
P,B(II)
Pboxes o ype I/II wi h addi ional condi ions
GP(T)admissible pa ame e s in he box
G∗
Pclass o admissible quad uples (γ, c, u, ) o ED1, sa is ying:
γ∈N,c∈Z,u=γA −c, =γB −c,u =c2,u≤
Analy ic no a ion
a
PLegend e symbol;
o composi e modulus he a
γ(Jacobi symbol, o p ime P) is used
π(y)p ime coun ing unc ion
≪,≫,≍s anda d asymp o ic symbols
Dse δ≤X,δ≡4 (mod 5)
T(δ)p ime coun ing unc ion in p og ession, see Appendix §A
4
5 Pa ame iza ion o ED1 (one mul iple, C=cP)
5.1 Ke nel and iden i ies
Le C=cP. F om (1.1) i ollows ha
(5c−1)AB =cP(A+B).(5.1)
Se ing γ=5c−1
P∈N, we ob ain
(γA −c)(γB −c) = c2.(5.2)
Hence γ≡4 (mod 5) and gcd(γ, c)=1(since 5c≡1 (mod γ)).
Lemma 5.1. We always ha e gcd(γ, c)=1.
P oo . F om 5c−1 = γP we ob ain 5c≡1 (mod γ), hence gcd(γ, c)=1.
5.2 Full pa ame iza ion o ED1 wi h il e s by P
Theo em 5.2. Le
P≡
1 (
mod
5),
γ≡
4 (
mod
5),5
c−
1 =
γP
,
gcd
(
γ, c
) = 1. Le
u, ∈N
such ha
u =c2, u ≡ ≡ −c(mod γ), u ≡ −c(mod P), ≡ −c(mod P).
Then
A=u+c
γ, B = +c
γ, C =cP
gi e a solu ion o
(1.1)
o ype
ED1
wi h
P∤A, B
. Con e sely, e e y
ED1
-solu ion gene a es
such γ, c, u, .
P oo .
F om
(5.1)
i ollows ha
(5.2)
holds. Se ing
u
=
γA −c
,
=
γB −c
, we ob ain
u
=
c2
and
u≡ ≡ −c
(
mod γ
), whence
γ|
(
u
+
c
),
γ|
(
+
c
)and
A, B ∈N
. The condi ions
u≡ −c
(
mod P
),
≡ −c
(
mod P
)a e equi alen o
P∤A
,
P∤B
hanks o
gcd
(
γ, c
)=1and
5c−1 = γP. Re e sibili y ollows om (5.2).
5.3 Mul iplici y il e s by P
F om A= (u+c)/γ,B= ( +c)/γ,5c−1 = γP we ha e
P|A⇐⇒ u≡ −c(mod P), P |B⇐⇒ ≡ −c(mod P).
Fo ED1 i is equi ed simul aneously ha u≡ −c(mod P)and ≡ −c(mod P).
5.4 Example: P= 11
The minimal
γ≡
4 (
mod
5) wi h 5
c−
1 =
γP
gi es
γ
= 4,
c
= (4
·
11 + 1)
/
5=9. Di iso s o
c2
= 81, compa ible wi h
u≡ −c≡
3 (
mod
4) and
u≡ −c≡
2 (
mod
11), include
u
= 3,
= 27.
Then
A=3+9
4= 3, B =27 + 9
4= 9, C = 99,1
3+1
9+1
99 =5
11.
5
6 Pa ame iza ion o ED2 ( wo mul iples, B=bP,C=cP)
6.1 Se up and iden i ies
Conside
5
P=1
A+1
bP +1
cP , A < bP ≤cP, P ∤A.
Mul iplying by AbcP , we ob ain
A(5bc −b−c) = Pbc. (6.1)
Le := 5bc −b−c=Pδ,δ∈N. Then
A=bc
δ.(6.2)
Equi alen ly,
(5b−1)(5c−1) = 5Pδ + 1.(6.3)
Se ing = 5b−1,s= 5c−1, we ob ain s = 5Pδ + 1 and ≡s≡4 (mod 5).
6.2 Full pa ame iza ion o ED2
Theo em 6.1. Le Pbe p ime and δ∈N. Le , s ∈Nsuch ha
s = 5Pδ + 1, ≡s≡4 (mod 5).
Se b= ( + 1)/5,c= (s+ 1)/5. I δ|bc, hen
A=bc
δ, B =bP, C =cP
gi e a solu ion o
(1.1)
o ype
ED2
. Unde pe mu a ion
↔s
we ha e
b↔c
and
B↔C
;
o de ing B≤Cis achie ed by choosing ≤s. Mo eo e , o b≤cwe ha e A≤B.
P oo .
F om
(6.1)
and
=
Pδ
i ollows ha
(6.2)
holds. Equali y
(6.3)
is ob ained om
(5
b−
1)(5
c−
1) = 25
bc −
5
b−
5
c
+ 1 = 5(5
bc −b−c
) + 1 = 5
Pδ
+ 1. The cong uences
≡s≡
4
(mod 5) a e ob ious. Fo b≤cwe ha e
A≤B⇐⇒ bc
δ≤bP ⇐⇒ c≤Pδ = 5bc −b−c⇐⇒ c(5b−2) ≥b,
which holds o b≥1,c≥b.
6.3 Example: P= 11
Take
δ
= 1. Then 5
Pδ
+ 1 = 56 = 4
·
14,4
≡
14
≡
4 (
mod
5). The pai
= 4,
s
= 14 gi es
b
= 1,
c= 3,A= 3,B= 11,C= 33. Ve i ica ion:
1
3+1
11 +1
33 =11 + 3 + 1
33 =15
33 =5
11.
6
7
Mul iplici y con igu a ions wi h espec o
P
and classi ica ion
Lemma 7.1. In any solu ion o (1.1)a leas one o A, B, C is di isible by P.
P oo .
Mul iplying
(1.1)
by
ABCP
:5
ABC
=
P
(
AB
+
AC
+
BC
). Modulo
P
:5
ABC ≡
0,
hence P|ABC.
Lemma 7.2. I is impossible ha A=aP,B=bP ,C=cP simul aneously.
P oo . Then 5 = 1/a + 1/b + 1/c ≤3— impossible.
Lemma 7.3. The minimal denomina o Ais no di isible by P.
P oo . F om (3.1) we ha e 5A < 3P; i A=aP, hen 5A≥5P > 3P, a con adic ion.
P oposi ion 7.4. E e y solu ion o
(1.1)
o p ime
P
= 5 alls in o exac ly one o he classes: -
ED1
: exac ly one denomina o di isible by
P
(wi hou loss o gene ali y
C
=
cP
), wi h
P∤A, B
;
-
ED2
: exac ly wo denomina o s di isible by
P
(namely
B
=
bP
,
C
=
cP
), wi h
P∤A
. The
cases “none” and “all h ee” a e excluded by Lemmas 7.1 and 7.2, and Lemma 7.3 excludes
P|A
.
7.1 In e media e ansi ion o pa ame e s b′, c′
F om P oposi ion 7.4 i ollows ha e e y solu ion o
(1.1)
o
P≡
1 (
mod
5) belongs ei he o
class ED1 o o class ED2. In bo h cases i is con enien o isola e no malized pa ame e s ha
desc ibe he pa o denomina o s di isible by P.
•
In he case
ED1
we ha e
C
=
cP
, and he pa ame e s
γ, c
a ise om no malizing he
condi ion 5c−1 = γP.
•
In he case
ED2
we ha e
B
=
bP
,
C
=
cP
, and he pa ame e s
b′, c′
a ise om he ke nel
(5b−1)(5c−1) = 5Pδ + 1.
Thus, in he case
ED2
he p oblem educes o analyzing pai s (
b′, c′
)wi h addi ional di isibili y
and cong uence condi ions.
7.2 Pa ame ic box in coo dina es (b′, c′)
Fo a ixed h eshold Tconside he se
Bb′,c′(T) = {(b′, c′)∈N2: 1 ≤b′, c′≤T, b′< c′}.
This se con ains all candida es o solu ions in he o iginal pa ame e s. Addi ional condi ions
(e.g.,
gcd
(
b′, c′
)=1, cong uences modulo
d
, di isibili y 4
b′c′
=
P
+
d
) a e imposed as il e s on
he poin s (b′, c′).
7.3 Box h eshold ia Aand P
F om he inequali y
P < 5A < 3P
i ollows ha he minimal denomina o
A
always lies in he in e al (
P/
5
,
3
P/
5). This p o ides
na u al bounds o he pa ame ic box.
De ini ion 7.5. Fo a ixed p ime Pwe de ine he box in he o iginal pa ame e s (b′, c′)as
Bb′,c′(P) = {(b′, c′)∈N2: 1 ≤b′, c′≤3P/5, b′< c′}.
7
7.4 T ansi ion o coo dina es (x, y)
Unde he linea ans o ma ion
x=b′+c′, y =c′−b′,
he image o he se Bb′,c′(P)is he subla ice
Bx,y(P) = {(x, y)∈Z2:x≡y(mod 2), x > y > 0, x, y ≤6P/5}.
7.5 Condi ion o d′
In he o iginal sys em he pa ame e
d′
appea s as he squa e ac o in he decomposi ion o
δ
.
In he new coo dina es he condi ion d′|(b′+c′)is ew i en as
d′|x.
P oposi ion 7.6. The exis ence o a poin (
x, y
)
∈Bx,y
(
P
)sa is ying he condi ions
x≡y
(
mod
2),
y >
0,
x, y ≤
6
P/
5and
d′|x
, is equi alen o he exis ence o an admissible pai (
b′, c′
)
and hence o a solu ion o (1.1).
7.6 Co olla y
De ining he box
Bb′,c′
(
T
)and ans e ing i o coo dina es (
x, y
), we ob ain a la ice wi h simple
linea condi ions: - pa i y x≡y(mod 2), - o de y > 0, - bound x, y ≤2T, - di isibili y d′|x.
Thus, he exis ence o a solu ion is equi alen o he p esence o a poin (
x, y
)in he box
Bx,y
(
T
)sa is ying hese condi ions. This makes he p oo cons uc i e and allows he use o
me hods o ini e co e ing o esidue classes.
Example Table 1
Table 1: ED2-decomposi ions o P= 73
P A B C b c δ α, d′
73 15 584 8760 8 120 64 α= 1, d′= 8
73 15 657 3285 9 45 27 α= 3, d′= 3
73 15 730 2190 10 30 20 α= 5, d′= 2
73 15 876 1460 12 20 16 α= 1, d′= 4
7.7 Geome y o he su ace and hickenings
Conside he quad a ic su ace
F(δ, b, c) = (5b−1)(5c−1) −5Pδ −1 = 0.
The hickening o his su ace, gi en by he condi ion
|F| ≤
∆in he pa ame e space (
δ, b, c
),
yields he se o
ED2
candida es. Since we wo k in he con ex o disc e e alues, i is c i ical o
es ima e he numbe o solu ions sa is ying modula condi ions.
Lemma 7.7 (Window in
δ
).Fo ixed alues o
b
and
c
, and o ∆
≥
0, he numbe o in ege s
δsa is ying he condi ion |F(δ, b, c)| ≤ ∆does no exceed:
1 + 2∆
5P.
P oposi ion 7.8 (Es ima e o hickening size).In he box whe e
b∈
[
B,
2
B
]and
c∈
[
C,
2
C
],
he o al numbe o iples (δ, b, c) o which he condi ion |F| ≤ ∆holds can be es ima ed as:
≪1 + ∆
PBC +B+C.
Rema k 7.9.Fo pai s (
b, c
)subjec o he condi ion
δ|bc
, he numbe o such pai s in he
co esponding ec angle is ≪BC
δτ(δ) + B+C.
8
8
Cons uc i e geome y o ED2 o he Sie pi´nski hypo hesis
(p ese ing he logic o ESC)
8.1 Se up and ke nel, ully analogous o ESC
Fo a p ime P≡1 (mod 5) we p o e he exis ence o a solu ion
5
P=1
A+1
B+1
C, B =bP, C =cP, P ∤A, b =c.
Mul iplying by AbcP and in oducing he pa ame e δ∈N, we ob ain
A(5bc −b−c) = P bc, 5bc −b−c=Pδ, A =bc
δ.
Quad a ic ke nel ED2:
(5b−1)(5c−1) = 5Pδ + 1.
This is ully isomo phic o he ke nel o ESC (
k
= 4) unde he subs i u ion 4
7→
5: all checks
and cons uc ions ans e e ba im.
8.2 No maliza ion and linea sys em (as in ESC)
Le b=g b′,c=g c′, whe e g=αd′and gcd(b′, c′)=1, and
δ=α(d′)2, α squa e ee.
Then he canonical condi ions (ED2) ake he linea o m
b′c′=M=Aα, b′+c′=m d′, m = 5A−P > 0.
In coo dina es x=b′+c′,y=c′−b′we ha e
x=m d′,x2−y2
4=Aα, x ≡y(mod 2).
This is exac ly he same a ine la ice o ini e index as in he ESC sec ion, wi h he coe icien
k
eplaced.
8.3 Pa ame ic box and geome ic co e ing ( ans e om ESC)
The minimal denomina o is bounded by
P
5<A<3P
5.
The p ojec ion o he la ice Λ
ED2
on o he (
x, y
)-plane lies in a box o linea size
O
(
P
); he
diagonal pe iod equals
d′
, and o
H, W ≥d′
he in e sec ion o he box wi h he la ice is
nonemp y. The la ice index does no depend on
P
, as in ESC, which s abilizes he densi y o
admissible poin s and ensu es cons uc i e co e ing wi hou ac o iza ion.
8.4 Back- es il e s and non-degene a ion (iden ical o ESC scheme)
Fo any assembled ow we check:
(5b−1) ≡(5c−1) ≡4 (mod 5), δ |bc, gcd(b′, c′) = 1,
b′+c′=m d′, b′c′=Aα, A =bc
δ∈Z,P
5<A<3P
5.
O de and dis inc ness:
b
=
c
, consis en o de ing o denomina o s (acco ding o you edi o ial
scheme), wi hou degene a ion.
9
Commen .
Summa ion o he main e m ollows om P oposi ion B.1 and linea i y; summa ion
o e o e ms gi es he s a ed emainde . The es ima e o
P
1
/φ
(5
)is s anda d:
φ
(5
) = 4
φ
(
)
when gcd( , 5) = 1, and Pn≤R, (n,m)=1 1/φ(n) = c(m) log R+O(1).
P oposi ion B.5 (Excep ional se ia he la ge sie e).Le
R≤x1/2/
(
log x
)
C
. Then he
numbe o ≤R, ≡4 (mod 5),gcd( , 5δ)=1, o which he p og ession
P≡1 (mod 5), P ≡ −(5δ)−1(mod )
con ains no p imes P≤x, sa is ies
≪Rexp
−clog R
log log R,
whe e c > 0is an absolu e cons an ( ollows om Theo em A.2).
Rema k B.6 (Chebo a e : addi ional local il e s).I necessa y, one can simul aneously impose
spli ing condi ions o
and/o
s
= (5
Pδ
+ 1)
/
in a ixed ex ension o numbe ields; by
Theo em A.3 he co esponding classes ha e posi i e na u al densi y, and in e sec ion wi h he
speci ied AP e ains posi i e densi y.
How o use in he algo i hm. - P eselec ion o
: ix se e al small
≡
4 (
mod
5) (o
enume a e
≤R
in he BV ange). - P e-sie ing by p og essions: o each
p ecompu e he
class
P≡ −
(5
δ
)
−1
(
mod
)and combine wi h
P≡
1 (
mod
5) (CRT). - Enume a ion o
P
: scan
p imes
P
in he combined classes; by P oposi ion B.1 he expec ed equency is
≍
1
/φ
(5
).
- Ve i ica ion o
ED2
: o a ound
P
compu e
s
= (5
Pδ
+ 1)
/
, check
s≡
4 (
mod
5), and
econs uc
b
= (
+ 1)
/
5,
c
= (
s
+ 1)
/
5,
A
=
bc/δ
. - Balancing: choosing
R≤x1/2/
(
log x
)
C
gi es an op imal comp omise be ween he numbe o p og essions and con ol o e o s (BV),
while P oposi ion B.5 gua an ees he smallness o he excep ional se o .
Double summa ion: a e age o e p imes P
De ine o ixed δand R≥2 he quan i y
N(P;R, δ) = #n ≤R: ≡4 (mod 5),gcd( , 5δ)=1, |(5Pδ + 1) o.
This is he numbe o “local” pa ame e s
o a gi en p ime
P
. Then o
R≤x1/2/
(
log x
)
C
we
ha e he a e age asymp o ic
1
#{P≤x:P≡1 (mod 5)}X
P≤x
P≡1 (5)
N(P;R, δ) = C5,δ log R+O(1),(B.1)
whe e C5,δ >0is a cons an depending only on δand classes modulo 5.
Idea o p oo . Change he o de o summa ion:
X
P≤x
P≡1 (5)
N(P;R, δ) = X
≤R
≡4 (5)
gcd( ,5δ)=1
#{P≤x:P≡1 (5), P ≡ −(5δ)−1( )}.
Fo each apply P oposi ion B.1 (modulus 5 ) and sum he main e ms:
X
Li(x)
φ(5 )= Li(x)X
≤R
≡4 (5)
gcd( ,5δ)=1
1
φ(5 )= Li(x)C5,δ log R+O(1),
and he o al e o is con olled linea ly in
using P oposi ion B.1. Di ision by he numbe o
p imes P≤x,P≡1 (5), gi es (B.1).
16
Co olla y B.7 (A e age supply o local pa ame e s).Fo
R
= (
log x
)
B
wi h ixed
B >
0, he
a e age alue o
N
(
P
;
R, δ
)o e p imes
P≤x
,
P≡
1 (
mod
5), g ows as
C5,δ Blog log x
+
O
(1).
In pa icula , he a e age numbe o admissible ends o in ini y.
Rema k B.8 (On es ima es o “mos
P
”).The ansi ion om he a e age o a s a emen o he
o m “ o mos
P
he e exis s a leas one
≤R
” can be ob ained by second momen me hods o
ia he la ge sie e (P oposi ion B.5) wi h a coo dina ed choice o
R
and
x
. These de ails a e no
equi ed o he cons uc i e pa o he algo i hm, bu hey explain i s good a e age beha io .
17
