\magnification=\magstep1
\input amstex
\hsize=16truecm
\parskip=2pt plus0.5pt
\parindent=18pt
\TagsOnRight
 
\define\({\left(}
\define\){\right)}
\define\e{\varepsilon}
 
 
\centerline{\bf Kombinatorikus sz\'amelm\'elet}
\bigskip
\item{1.)} Konstru\'aljunk (a moh\'o algoritmus seg\'\i{}ts\'eg\'evel)
olyan Sidon halmazt, (azaz a ter\-m\'e\-sze\-tes sz\'amoknak olyan $\Cal
A$ r\'eszhalmaz\'at, melyre az $x+y=u+v$ egyenletnek, ahol $u,v,x,y\in
\Cal A$ k\"ul\"onb\"oz\H o sz\'amok, nincs megold\'asa) melynek
metszete az $\{1,\dots,n\}$ halmazzal legal\'abb const.$n^{1/3}$
sz\'amot tartalmaz. \medskip \noindent
A k\"ovetkez\H o feladatokban fontos szerepet j\'atszik a k\"ovetkez\H
o \medskip \noindent
{\bf Szemer\'edi t\'etel:} {\it Tetsz\'oleges $k>0$ pozit\'\i{}v
eg\'esz  \'es $\e>0$ val\'os sz\'amra l\'etezik
olyan $N_0=N_0(\e,k)$ k\"usz\"obindex, melyre igaz, hogy minden
olyan $\Cal A\subset \{1,\dots,N\}$ halmaz, $N\ge N_0$, melyre $|\Cal
A|\ge N\e$ tartalmaz $k$ hossz\'us\'ag\'u sz\'amtani sorozatot.}
\medskip
\item{2.)} Legyen $\bold A$ eg\'esz sz\'amokb\'ol \'all\'o m\'atrix,
$\bold b$ eg\'esz elemekb\H ol \'all\'o vektor, melyekre az $\bold
x\bold A=\bold b$ egyenletnek van olyan $\bold x=(x_1,\dots,x_k)$
megold\'asa, melynek minden  $x_j$ koordin\'at\'aja k\"ul\"onb\"oz\H o.
\itemitem{a.)} Bizony\'\i{}tsuk be a Szemer\'edi t\'etel
seg\'\i{}ts\'eg\'evel azt, hogy ha $\Cal A$ a term\'eszetes sz\'amok
pozit\'\i{}v s\H ur\H us\'eg\H u r\'eszhalmaza, a fenti
egyenletben $\bold b=0$ \'es $ \bold 1\bold A=0$, $\bold 1=(1,\dots,
1)$, akkor l\'etezik (v\'egtelen sok) olyan $\{m_1,\dots, m_k\}\subset
\Cal A$, r\'eszhalmaz, melyre $\bold m=(m_1,\dots, m_k)$ teljes\'\i{}ti
az $\bold m \bold A=0$ egyenletet.
\itemitem{b.)} Ha a $\bold b\neq 0$ vagy $\bold 1 \bold A\neq0$
felt\'etel teljes\"ul, akkor l\'etezik a term\'eszetes sz\'amoknak olyan
pozit\'\i{}v s\H ur\H us\'eg\H u $\Cal A$ r\'eszhalmaza, melyb\H ol nem
v\'alaszthat\'o ki az $\bold m\bold A=\bold b$, $\bold
m=(m_1,\dots,m_k)$, $\{m_1,\dots,m_k\}\subset \Cal A$ egyenletet
kiel\'eg\'\i{}t\H o $k$ elem\H u sz\'am\-hal\-maz.
\medskip A k\"ovetkez\H o feladatban viszonylag s\H ur\H u h\'arom
elem\H u sz\'amtani sorozatot nem tartalmaz\'o halmazt konstru\'alunk.
(Behrend konstrukci\'oja.)
\medskip \item{3.)} R\"ogz\'\i{}ts\"unk egy $d$ \'es $s$ eg\'esz
sz\'amot. Defini\'aljuk a
$$
\Cal B(s,d)=\left\{l\:\,l=\sum_{j=0}^s a_j(2d+1)^j,\quad 0\le a_j\le
d,\; 0\le j\le k \right\}
$$
halmazt, \'es vezess\"uk be rajta az $\|l\|=\left(\sum\limits_{j=0}^s
a_j^2\right)^{1/2}$ norm\'at. L\'assuk be, hogy tetsz\H oleges $n$
sz\'amra az $\Cal A_n=\{l\:\;l\in\Cal B(s,d),\,\,\|l\|=n\}$ halmaz nem
tartalmaz h\'arom elem\H u sz\'amtani sorozatot.
\itemitem{a.)} Az $s$, $d$ \'es $n$ sz\'amok alkalmas
megv\'alaszt\'as\'aval meg lehet adni az $\{1,\dots,N\}$ halmaz olyan
h\'arom elem\H u sz\'amtani sorozatot nem tartalmaz\'o ($\Cal A_n$
tipus\'u) r\'eszhalmaz\'at, melynek sz\'amoss\'aga nagyobb mint
$Ne^{-\text{const.}\,\sqrt{\log N}}$. (\'Erdemes
$s=\text{const.}\,\sqrt{\log N}$, $\log (2d+1)=\dfrac1s\log N$
v\'alaszt\'ast tenni. Mi\'ert?)
\medskip
Be k\'\i{}v\'anjuk l\'atni a Szemer\'edi t\'etel ekvivalenci\'aj\'at
egy F\"urstenberg \'altal megfogalmazott \'es k\"ozvetlen\"ul (a
Szemer\'edi t\'etel felhaszn\'al\'asa n\'elk\"ul) bebizony\'\i{}tott
ergod elm\'eleti t\'etellel.
\medskip\noindent{\bf F\"urstenberg t\'etel:} {\it Legyen $(X,\Cal B,
\mu)$ val\'osz\'\i{}n\H us\'egi mez\H o, $\bold T$ invert\'alhat\'o
m\'ert\'ektart\'o lek\'epez\'es ezen a t\'eren. Ekkor tetsz\H oleges
pozit\'\i{}v m\'ert\'ek\H u, $\mu(A)> 0$, $A\in \Cal B$ halmazra,
 \'es $k$ eg\'esz sz\'amra l\'etezik olyan $n$ eg\'esz sz\'am, melyre}
$$
\mu\left(\bigcap_{j=0}^k \bold T^{-jn}A\right)>0  \tag$*$
$$
\medskip
\item{4.)} L\'assuk be, hogy a Szemer\'edi t\'etel ekvivalens a
k\"ovetkez\H o \'all\'\i{}t\'assal: Ha $\Cal A$ a ter\-m\'e\-sze\-tes
sz\'amok pozit\'\i{}v fels\H o s\H ur\H us\'eg\H u halmaza, azaz
$\limsup\limits_{n\to\infty}\dfrac 1n|\Cal A\cap\{1,\dots,n\}|>0$,
$k>1$ tetsz\H oleges term\'eszetes sz\'am, akkor $\Cal A$ tartalmaz $k$
hossz\'us\'ag\'u sz\'amtani sorozatot.
\item{5.)} Legyen $B_j$, $j=1,2,\dots$, olyan halmazok egy $(X,\Cal
B,\mu)$ t\'eren, melyekre $\mu(B_j)>\e$ minden $j=1,2,\dots$-ra
valamilyen r\"ogz\'\i{}tett $\e>0$-ra. L\'assuk be a Szemer\'edi
t\'etel seg\'\i{}ts\'eg\'evel, hogy ha $N>N_0$ valamilyen
$N_0=N_0(\e,k)$ k\"usz\"obindex-szel, akkor l\'etezik olyan
$a$ \'es $b$ pozit\'\i{}v eg\'esz sz\'am, melyre
$$
\mu(\{x\: x\in B_{a+bj}\quad\text{ha } j=1,2,\dots,k\})>\frac\e{2N^2}
$$
E t\'eny seg\'\i{}ts\'eg\'evel mutassuk meg, hogy a Szemer\'edi
t\'etelb\H ol k\"ovetkezik a F\"ur\-sten\-berg t\'etel.
\item{} {\it Seg\'\i{}ts\'eg:}\/ $x\in X$ pontok viszonylag nagy
m\'erer\H u halmaz\'ara igaz, hogy az $x\in B_j$  esem\'eny sok $j$-re
teljes\"ul. Az ilyen $x$-ekre a $\Lambda(x)=\{j\: x\in B_j\}$ halmaz
tartalmaz $k$ hossz\'us\'ag\'u sz\'amtani sorozatot a Szemer\'edi
t\'etel szerint. \medskip
Legyen $X=\prod\limits_{n=-\infty}^\infty Z_n$, $Z_n=\{0,1\}$, azaz $X$
a k\'et ir\'anyban v\'egtelen $0,\,1$ sorozatok halmaza, $\Cal B$ (a
$\{0,1\}$ halmazon \'ertelmezett diszkr\'et topol\'ogia \'altal
gener\'alt) szorzat $\sigma$-algebra az $X$ t\'eren. Defini\'aljuk a
$\bold T$ shift oper\'atort $X$-en, azaz
$x=(\dots,\e_j,\e_{j+1},\dots)$-ra legyen $\bold
Tx=(\dots,\e_{j+1},\e_{j+2},\dots)$, ($\e_j=0$ vagy
$\e_j=1$, $j=0,\pm1,\pm2,\dots$). Ahhoz, hogy a F\"urstenberg
t\'etelb\H ol levezess\"uk a Szemer\'edi t\'etelt (annak a 4.
feladatban megfogalmazott v\'altozat\'at) sz\"uks\'eg\"unk van az
$(X,\Cal B)$ t\'eren olyan $\bold T$ invari\'ans  $\mu$
val\'osz\'\i{}n\H us\'egi m\'ert\'ekre, mely l\'enyeg\'eben egy el\H
ore megadott pozit\'\i{}v fels\H o s\H ur\H us\'eg\H u halmaz
eltoltjaira van koncentr\'alva. (E konstrukci\'oban j\'ol
haszn\'alhat\'o egy standard eredm\'eny az anal\'\i{}zisb\'ol
(val\'osz\'\i{}n\H us\'egsz\'am\'\i{}t\'asb\'ol), mely szerint kompakt
t\'eren defini\'alt val\'osz\'\i{}n\H us\'egi m\'ert\'ekeknek van
gyeng\'en konvergens r\'eszsorozata. A k\"ovetkez\H o feladat c\'elja
ennek az \'all\'\i{}t\'asnak a bizony\'\i{}t\'asa a 7. feladatban
sz\"uks\'eges speci\'alis esetben.
 \medskip
\item{6.)} Legyen $\mu_n$, $n=1,2,\dots$ val\'osz\'\i{}n\H us\'egi
m\'ert\'ekek egy sorozata a fent defini\'alt $(X,\Cal B)$ t\'eren.
($X=\prod\limits_{n=-\infty}^\infty Z_n$, $Z_n=\{0,1\}$). A $\mu_n$
sorozatnak l\'etezik olyan $\mu_{n_k}$ r\'esz\-so\-ro\-za\-ta, \'es
olyan $\mu^*$ val\'osz\'\i{}n\H us\'egi m\'ert\'ek, melyre igaz, hogy
tetsz\H oleges $A\subset X$ hengerhalmazra,
$\lim\limits_{k\to\infty}\mu_{n_k}(A)
=\mu^*(A)$. (Az $A\subset X$ halmaz hengerhalmaz, ha l\'etezik olyan
$m$ csak az $A$ halmazt\'ol f\"ugg\H o sz\'am, melyre ha $x\in X$ \'es
$y\in X$ olyan sorozatok, melyeknek az $m$-n\'el nagyobb abszolut
\'ert\'ek\H u koordin\'at\'ai megegyeznek, akkor $x$ \'es $y$ egyszerre
van vagy nincs benne az $A$ halmazban.)
\item{} {\it Megjegyz\'es:}\/ Az \'atl\'os elj\'ar\'as
seg\'\i{}ts\'eg\'evel tal\'alhatunk olyan $\mu^*$ additiv
hal\-maz\-f\"ugg\-v\'enyt, melyre $\lim_{k\to\infty}\limits
\mu_{n_k}(A)=\mu^*(A)$. De a feladat \'all\'\i{}t\'as\'anak
bizony\'\i{}t\'as\'ahoz be kell l\'atni azt is, hogy $\mu^*$
$\sigma$-additiv. Ehhez kompakts\'agi meggondol\'asok kellenek.
\item{7.)} Legyen $\bold x=(x_n,\; n=0,\pm1,\pm2,\dots)$ eg\'esz
sz\'amoknak pozit\'\i{}v fels\H o s\H ur\H us\'eg\H u so\-ro\-za\-ta,
$\bar \omega\in X$ az $\bold x$ sorozat indik\'atorf\"uggv\'enye, azaz
legyen $\bar \omega=(\dots,\e_j,\e_{j+1},\dots)$, $\e_j=1$, ha
$j\in\bold x$, \'es $\e_j=0$, ha $j\notin\bold x$. Legyen $a_n$, $b_n$
eg\'esz sz\'amok olyan sorozata, melyre $b_n-a_n\to\infty$, \'es
$\lim\limits_{k\to\infty}\dfrac{\#\{j\:a_n<j\le b_n,\,j\in \bold
x\}}{b_n-a_n}>0$ ha $n\to\infty$. Defini\'aljuk a
$\mu_n=\dfrac1{b_n-a_n}\sum\limits_{j=a_n+1}^{b_n}\delta_{\bold
T^{-j}\bar \omega}$ m\'ert\'ekeket, ahol $\bold T$ a shift oper\'ator,
\'es $\delta_u$, $u\in X$ az $u$ pontba koncentr\'alt m\'ert\'ek. Legyen
$\mu^*$ a $\mu_n$ sorozat egy $\mu_{n_k}$ r\'eszsorozat\'anak a limesze
az 6.) feladatban defini\'alt \'ertelemben. L\'assuk be, hogy $\mu^*$
m\'ert\'ek $\bold T$ invari\'ans, \'es a $\mu^*$ m\'ert\'ek szerint a $0$-ik
koordin\'ata pozit\'\i{}v val\'osz\'\i{}n\H us\'eggel 1, azaz
$\mu^*(A)>0$ az $A=\{\omega\in X\:\,\omega=(\dots,\e_{-1},\e_0,
\e_1\dots), \e_0=1\}$ halmazra. L\'assuk be e t\'enyek
seg\'\i{}ts\'eg\'evel, hogy a F\"urstenberg t\'etelb\H ol k\"ovetkezik
a Szemer\'edi t\'etel. \bigskip \noindent
A F\"urstenberg t\'etelben a $(*)$ rel\'aci\'o helyett a k\"ovetkez\H
o \'elesebb \'all\'\i{}t\'ast bizony\'\i{}tj\'ak:
$$
\liminf_{N\to\infty}\frac 1N\sum_{n=1}^N\mu\left(\bigcap_{j=0}^k \bold
T^{-jn}A\right)>0\;. \tag $**$
$$
Tov\'abb\'a el\'eg feltenni azt, hogy $\bold T$ m\'ert\'ektart\'o
transzform\'aci\'o, de nem kell felt\'etlen\"ul invert\'alhat\'onak
lenni. Nem ismeretes, hogy $(**)$ rel\'aci\'oban a $\liminf$
helyettes\'\i{}thet\H o-e $\lim$-mel. A bizony\'\i{}t\'as transzfinit
indukci\'oval t\"ort\'enik egyre bonyolultabb szerkezet\H u
rendszerekre.
 
\bye