2.
Reprezentáció-függvények, Erdős-Fuchs tétel
A kör-probléma a következőképpen is megközelíthető: Jelölje S a négyzetszámok halmazát. Jelölje rS (n) azt az értéket, ahány féleképpen n felírható két pozitív négyzetszám összegeként, azaz rS (n) = #{(a2 , b2 ) : a2 + b2 = n}. Ekkor N (R) =
X
rS (n) − 4[R] − 3.
n≤R
Ezért
X
rS (n) =
0≤n≤R2
π 2 R + R + O(Rα ), 4
teljesül α = 0, 5 + ², de nem teljesül α = 0, 5 − ² értékkel. Ez motiválja az alábbi definíciókat és kérdéseket: Legyen A ⊂ N, |A| = ∞ és a reprezentáció-függvényeket az alábbi módon értelmezzük: rA (n) = #{(a, a0 ),
a, a0 ∈ A,
a + a0 = n}
r≤,A (n) = #{(a, a0 ),
a, a0 ∈ A,
a ≤ a0
a + a0 = n}
r<,A (n) = #{(a, a0 ),
a, a0 ∈ A,
a < a0
a + a0 = n}
A kérdés az, hogy a fenti reprezentációfüggvények mennyire lehetnek egyenletesek. Először a legegyszerübb kérdéseket tesszük fel: Van-e olyan A ⊂ N részhalmaz, amelyre 1. rA (n) vagy 2. r≤,A (n) vagy 3. r<,A (n) reprezentációfüggvények konstansak valahonnan kezdve? Az 1. kérdésre a válasz nyilvánvalóan tagadó, mivel rA (n) pontosan akkor páratlan, ha n = 2a valamely a ∈ A-val. Emiatt rA (n) végtelen sokszor páros és végtelen sokszor páratlan. A 2. kérdés már egy kis trükköt igényel. Jelölje A(z) az A halmaz generátorfüggvényét, azaz X A(z) = za a∈A
Könnyen látszik, hogy
∞ X
1 r≤,A (n)z n = (A2 (z) + A(z 2 )). 2 n=1
Tegyük fel, hogy r≤,A (n) konstans valahonnan kezdve. Ekkor létezik egy C > 0 konstans és p(z) polinom, amelyre ∞
X C 1 2 (A (z) + A(z 2 )) = r≤,A (n)z n = p(z) + , 2 1−z n=1 |z| < 1 esetén. Tekintsük azt az esetet, amikor z → −1 + 0. Ekkor bal oldal (az A(z 2 ) miatt) a végtelenhez tart, míg a jobb oldal korlátos, ami ellentmondás, tehát ez a reprezentációfüggvény sem lehet korlátos. 1
A 3. kérdés megválaszolása már komplex függvénytant igényel. Nyilván ∞ X
1 r<,A (n)z n = (A2 (z) − A(z 2 )). 2 n=1
Tegyük fel, hogy létezik olyan A ⊂ N, amelyre r<,A (n) konstans valahonnan kezdve. Ekkor létezik egy C > 0 konstans és p(z) polinom, hogy ∞
X 1 2 C (A (z) − A(z 2 )) = r<,A (n)z n = + p(z), 2 1−z n=1 ahol z ∈ C és |z| < 1. Ekkor 2C + |A(z 2 )|. |1 − z|
|A(z)|2 ≤ 2|p(z)| + Legyen z = reiϕ . Ekkor Z2π
Z2π iϕ
2
|A(re )| dϕ ≤ 0
Z2π iϕ
p(re )dϕ + 0
1 dϕ + |1 − reiϕ |
0
Z2π |A(r2 e2iϕ )|dϕ.
(1)
0
A bal oldalra alsó becslést, a jobb oldalra felső becslést adva kapunk ellentmondást. Ehhez szükség van a Parseval-formulára: P∞ n 1. Lemma (Parseval-formula). Legyen f (z) a |z| < R körben knvergens n=0 an z hatványsor összegfüggvénye. Ekkor 0 < r < R esetén Z2π iϕ
2
|f (re )| dϕ =
∞ X
|an |2 r2n .
n=0
0
Bizonyítás. iϕ
2
|f (re )| = (
∞ X
n inϕ
an r e
n=0
)(
∞ X
m imϕ
am r e
m=0
)=
∞ X
an am rn+m ei(n−m)ϕ .
n,m=0
P∞
Ennek majoránsa a n,m=0 |an ||am |rn+m konvergens numerikus sor, így tagonként integrálhatunk. A Lemma nyilvánvaló mivel ½
Z2π ikϕ
e
dϕ =
2π, ha k = 0; ¥ 0, egyébként.
0
A Parseval-formula bizonyításából még kiolvasható a következő azonosság is, amire később szükségünk lesz Z2π |f (r2 ei2ϕ )|2 dϕ = 2πA(r4 ). (2) 0
A Parseval-formula szerint Z2π |A(reiϕ )|2 dϕ = 2π
X a∈A
0
2
r2a = 2πA(r2 ).
Mivel A2 (r2 ) − A(r4 ) = 2p(r2 ) + ezért A(r2 ) ≥ √
2C , 1 − r2
c1 , 1 − r2
(3)
ha r elég közel van az 1-hez, ezért Z2π |A(reiϕ )|2 dϕ ≥ √ 0
Nyilván
c1 . 1 − r2
(4)
Z2π |p(reiϕ )|dϕ ≤ c2 ,
(5)
0
valamely c2 esetén. R2π 1 Az |1−re iϕ | dϕ becsléséhez használjuk, hogy 0
|1 − reiϕ |2 = (1 − r cos ϕ)2 + (r sin ϕ)2 = (1 − r)2 + 2r(1 − cos ϕ) = (1 − r)2 + 4r sin2 Mivel sin α ≥ kapjuk, hogy
2α , π
ϕ . 2
ha 0 ≤ α ≤ π2 , ezért 0 ≤ ϕ ≤ π esetén, feltéve hogy 0, 25 < r < 1 azt |1 − reiϕ | ≥ max{1 − r,
ϕ }. π
Ezért Z2π
1 dϕ = 2 |1 − reiϕ |
0
Zπ
1 dϕ ≤ |1 − reiϕ |
0
Igy
Z1−r
1 dϕ + 1−r
0
Z2π
Zπ
π dϕ = 2 + 2π ln π − 2π ln(1 − r) ϕ
1−r
2C 1 dϕ ≤ c3 ln iϕ |1 − re | 1−r
(6)
0
Az
R2π
|A(r2 e2iϕ )|dϕ integrált a Cauchy-Schwarz egyenlőtlenséggel becsüljük meg, a (2)
0
egyenlőséget használva. Z2π
v uZ2π Z2π u p u |1 · A(r2 e2iϕ )|dϕ ≤ t 1dϕ |A(r2 e2iϕ )|2 dϕ = 2π A(r4 )
0
0
0
Az A(r4 ) ≤ A(r2 ) nyilvánvaló egyenlőtlenséget alapján kapjuk, hogy Z2π |A(r2 e2iϕ )|dϕ ≤ 2π 0
3
p A(r2 ).
(7)
A (4), (5), (6), (7) egyenlőtlenségeket (1)-re alkalmazva kapjuk, hogy 2πA(r2 ) ≤ 2c2 + 2c3 ln
p 1 + 2π A(r2 ). 1−r
Igy A(r2 ) ≤ c4 ln
1 1−r
Innen (3) szerint
c1 1 ≤ c5 ln , 2 1−r 1−r ami ellentmondás, ha r elég közel van az 1-hez. √
Az rA (n) egyenletesség lehetőségét szinte teljesen leírja az Erdős-Fuchs tétel 1. Tétel (Erdős-Fuchs tétel). Egy A ⊂ Z+ halmazra a rA (1) + rA (2) + · · · + rA (n) = Cn + O(nα ) egyenlőség C > 0-val nem teljesülhet α <
1 4
esetén.
Bizonyítás. Tegyük fel, hogy létezik olyan A ⊂ N, amelyre rA (0) + rA (1) + rA (2) + · · · + rA (n) = C(n + 1) + O(nα ) teljesül egy C > 0-val és α < 14 -del. Legyen rA (0) + rA (1) + rA (2) + · · · + rA (n) = C(n + 1) + en és
X
A(z) = 2
Mivel A (z) =
za.
a∈A
P∞
n=0 rA (n)z
n
, ezért
∞ X 1 2 2 n A (z) = (1 + z + z + · · · + z + . . . ) rA (n)z n = 1−z n=0 ∞ X
∞ X
∞
X C (rA (0) + rA (1) + rA (2) + · · · + rA (n))z = (C(n + 1) + en )z = + en z n . 2 (1 − z) n=0 n=0 n=0 n
Ekkor
n
∞ X C + (1 − z) en z n . A (z) = 1−z n=0 2
Ismert, hogy β ≥ 0 esetén
∞ X
nβ r n <
n=0
cβ , (1 − r)1+α
ha r → 1 − 0. Magyarázat ehhez: Legyen r = 1 − ∞ X n=0
β n
n r =
∞ X n=0
µ β
n
1 1− M
¶n =
akkor
∞ nMX +M −1 X n=0
4
1 , M
(8)
k=nM
µ k
β
1 1− M
¶k ≤
∞ X
µ β
M ((n + 1)M )
n=0
Ezért az
1 1− M
¶nM < M 1+β
∞ X 1 (n + 1)β n . e n=0
∞ X C A (r) = + (1 − r) en rn 1−r n=1 2
C tag a domináns. Azt szeretnénk, hogy ez a tulajdonság egyenlet jobb oldalán a 1−r megörződjön az integrálásnál, emiatt egy olyan szorzótényezőt választunk, ami az 1 körül nagy, egyébként kicsi. Kézenfekvő az
S(z) = 1 + z + z 2 + · · · + z N −1 négyzetének választása, ahol N -et később választjuk meg alkalmasan. Ekkor ∞ X CS 2 (z) N A (z)S (z) = + (1 − z )S(z) en z n , 1−z n=0 2
2
ezért |A2 (z)S 2 (z)| ≤
∞ X CN 2 + 2|S(z) en z n |. |1 − z| n=0
Innen a Z2π
Z2π 2
iϕ
2
iϕ
|A (re )S (re )|dϕ ≤ 0
CN 2 dϕ + |1 − reiϕ |
Z2π
0
iϕ
2|S(re )
∞ X
en rn einϕ |dϕ
(9)
n=0
0
egyenlőtlenséget használva kapunk ellentmondást a bal oldalra alsó, a jobb oldalra felső becslést adva. P n Legyen A(z)S(z) = ∞ n=0 dn z . Ekkor a Parseval-formula szerint Z2π 2
iϕ
2
iϕ
|A (re )S (re )|dϕ = 2π
∞ X
d2n r2n
≥ 2π
n=0
0
mivel dn nemnegatív egész. Ha 1−
∞ X
dn r2n = 2πA(r2 )S(r2 ),
n=0
1 < r2 < 1 N
akkor S(r2 ) = 1 + r2 + r4 + · · · + r2(N −1) =
(10) 1 − r2N ≥ c6 N, 1 − r2
továbbá (8) implikája az ∞ X C 2 A (r ) = + (1 − r ) en r2n , 1 − r2 n=0 2
2
egyenletből, hogy A(r2 ) ≥ c7 √ Innen kapjuk, hogy
1 . 1 − r2
Z2π |A2 (reiϕ )S 2 (reiϕ )|dϕ ≥ √ 0
5
c8 N . 1 − r2
(11)
(6) egyenlőtlenség alapján Z2π
1 CN 2 dϕ < c9 N 2 log . iϕ |1 − re | 1−r
(12)
0
Hátra van még a
R2π
2|S(reiϕ )
0
P∞
n=0 en r
n inϕ
e
|dϕ integrál becslése. Ezt a Cauchy-Schwarz
egyenlőtlenséggel érjük el, a Parseval-formulát használva: v uZ2π Z2π Z2π X u ∞ ∞ X u iϕ n inϕ 2 iϕ 2|S(re ) en r e |dϕ ≤ 2t |S (re )|dϕ | en rn einϕ |2 dϕ = 0
n=0
0
0
n=0
và !à ∞ ! u X u X 4π t r2k |en |2 r2n . n=0
0≤k
Ezért (8) alapján Z2π 0
√ c10 N 2|S(z) en z |dϕ ≤ . 2 )0,5+α (1 − r n=0 ∞ X
n
(13)
Innen a (11), (12), (13) egyenlőtlenségeket használva (9) alapján azt kapjuk, hogy √ c8 N 1 c N 10 √ ≤ c9 N 2 log + , 2 1 − r (1 − r )1+2α 1 − r2 azaz
√ c8 ≤ c9 1 − r2 N log
1 c10 +√ . 1−r N (1 − r2 )α
(14)
Végül alkalmasan megválasztjuk r-et. Legyen r olyan, hogy √ N 1 − r2 = √ Ekkor
1 . N (1 − r2 )α 3
1 − r2 = N − 2α+1 , így
√ 1,5 2α−0,5 N 1 − r2 = N N − 2α+1 = N 2α+1 .
De
1 1 ≤ c11 log ≤ c12 log N, 1−r 1 − r2 ezért (14) alapján kapjuk, hogy log
c8 ≤ N
2α−0,5 2α+1
(c13 log N + c10 ),
ami α < 14 esetén elég nagy N -re ellentmondás és ha N elég nagy, akkor a hozzá tartozó r-rel az adott becslések érvényeek. ¥
6
Házi feladatok 1. Bizonyítsa be, hogy végtelen A ⊂ N esetén az rA (2n) nem lehet konstans valahonnan kezdve! (3p) 2. Adott A ⊂ N esetén jelölje sA (n) = {(a, a0 ) :
a, a0 ∈ A,
a0 − a = n}.
Bizonítsa be, hogy van olyan A ⊂ N, amelyre sA (n) = 1 minden n ∈ Z+ esetén és 1/3 |A ∩ [1, N ]| > n100 . (3p) 3. Adott G Abel-csoport (a + a művelet) és A ⊂ G esetén legyen rA (g) = {(a, a0 ) :
a, a0 ∈ A,
a + a0 = g}.
Határozza meg azokat a G Abel-csoportokat és A ⊂ G részhalmazokat, amelyekre rA (g) = rG\A (g) minden g ∈ G-re! (3p) 4. Adott G Abel-csoport (a + a művelet) és A ⊂ G esetén legyen 0 rA (g) = {{a, a0 } :
a, a0 ∈ A,
a + a0 = g}.
Határozza meg azokat a G Abel-csoportokat és A ∈ G részhalmazokat, amelyekre 0 0 rA (g) = rG\A (g) minden g ∈ G-re! (3p)
7
