\documentclass[12pt]{article}
\usepackage{amssymb, amsmath}
\usepackage{latexsym}
\usepackage{graphics}



%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%   FORMAT
%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\textheight}{23.0cm}
\setlength{\textwidth}{15.75cm}
\setlength{\topmargin}{-.5cm}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%   SPANISH
%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[spanish]{babel}
\usepackage[latin1]{inputenc}
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%   MACROS
%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\R}{\mbox{${\mathbb R}$}}
\newcommand{\C}{\mbox{${\mathbb C}$}}
\newcommand{\N}{\mbox{${\mathbb N}$}}
\newcommand{\Z}{\mbox{${\mathbb Z}$}}
\newcommand{\Q}{\mbox{${\mathbb Q}$}}
\def\refe#1{{\rm(\ref{#1})}}
\def\notdiv{{\kern-1pt\not\kern2pt}|}

\newtheorem{theo}{Teorema}
\newtheorem{coro}[theo]{Corolario}
\newtheorem{lemm}[theo]{Lema}
\newtheorem{prop}[theo]{Proposici\'{o}n}
%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\begin{LARGE}


\begin{center}
\fbox{\textbf{\fbox{$\phantom{\frac12}$1. Recordando$\phantom{\frac12}$}}}
\end{center}

\

{\sc Criba combinatoria}:

\

Hallar $\mathcal{D}^-,\mathcal{D}^+\subset [1,D]$ tales que

\[
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^-\end{smallmatrix}}
\mu(d)|A_d|
\le S(A,z)\le
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^+\end{smallmatrix}}
\mu(d)|A_d|.
\]

\ 

\begin{large}$
XV^-(z)+R^-\le  S(A,z)\le XV^+(z)+R^+
$\end{large}

\

\

{\sc Identidad de Buchstab}:


\[
\begin{array}{ccccc}
|A|& = & S(A,z) & + & \displaystyle{\sum_{p<z}S(A_p,p)}
\\ 
\text{\begin{large}todos\end{large}}&  &
\text{\begin{large}sin factores $<z$\end{large}}&  & 
\text{ \begin{large}menor factor $=p$\end{large}}
\end{array}
\]

\


\[
\begin{array}{ccccc}
1& = & V(z) & + & \displaystyle{\sum_{p<z}\frac{\rho(p)}pV(p)}
\\ 
&  & \text{\begin{large}Prob no factor $p<z$\end{large}}&  & \text{\begin{large}Prob menor factor $=p$\end{large}}
\end{array}
\]

\newpage 

\begin{center}
\fbox{\textbf{\fbox{$\phantom{\frac12}$2. Pidiendo$\phantom{\frac12}$}}}
\end{center}

\

$
z=X^{\text{algo}},\quad
D=X^{\text{algo mayor}}$

\

Notación: 
$s=\frac{\log D}{\log z}>1,\quad z^s=D$

\

\

Esperamos:




\begin{center}
\fbox{ $\phantom{\frac12}f(s)XV(z)-E\le S(A,z)\le F(s)XV(z)+E\phantom{\frac12}$ }
\end{center}

\

\

Digamos que

\[
V(z)\sim\frac{\text{Cte}}{\log^\kappa z}
\qquad\text{supongamos $\kappa=1$ (criba lineal)}
\]

Queremos que el error no engulla al término principal:

\[
E=
\sum_{\begin{smallmatrix}d|P(z)\\ d\le D\end{smallmatrix}}
|r_d|\ll
\frac{X}{\log^2 X}
\]

\

\

\begin{center}
$
z=p,\ A_p\ \Rightarrow \ s_p=\frac{\log D/p}{\log p}=\frac{\log D}{\log p}-1
$

\end{center}
\newpage

\begin{center}
\fbox{\textbf{\fbox{$\phantom{\frac12}$3. Soñando$\phantom{\frac12}$}}}
\end{center}

\


\[
\left.
\begin{array}{l}
V(z)={\text{Cte}}/{\log z}
\\
1=V(z)+\displaystyle{\sum_{p<z}}\frac{\rho(p)}pV(p)
\end{array}
\kern-9pt
\right\}
\kern-4pt
\Rightarrow
-\frac{\rho(t)}tV(t)=\Delta\big(\frac{\text{Cte}}{\log t}\big)
\]

\


\[
S(A,z)=X-\sum_{p<z}S(A_p,p)\qquad\ \qquad\ \qquad
\]
\[
\lesssim
X-\sum_{p<z}f\big(\frac{\log D/p}{\log p}\big)X\frac{\rho(p)}pV(p)
\qquad\ \qquad\ \qquad
\]
\[
=
XV(z)\bigg(
1+\frac1{V(z)}
\sum_{p<z}\big(1-f(\frac{\log D}{\log t} -1)\big)\frac{\rho(p)V(p)}{V(z)}\bigg)
\]
\[
\approx 
XV(z)\bigg(
1+\frac1{V(z)}
\int_1^z\big(1-f(\frac{\log D}{\log t} -1)\big)\;d\big(\frac{\text{Cte}}{\log t}\big)\bigg)
\]
\[
=XV(z)\bigg(1+\frac 1s\int_s^\infty\big(1-f(t-1)\big)\; dt\bigg)
\qquad\ \qquad\ \qquad
\]

\

\

$f$ cota inferior $\Rightarrow$ $F(s)=1+\frac1s\int_s^\infty\dots$ cota superior $(sF(s))'=f(s-1)$.


\newpage

{\sc Problema de ecuaciones diferenciales en diferencias}

\

\[
\left.
\begin{array}{l}
(sF(s))'=f(s-1)\quad s>\beta+1
\\
(sf(s))'=F(s-1)\quad s>\beta
\\
F(\infty)=f(\infty)=1
\\
0\le f\le F
\\
f(s)=0\ \Leftrightarrow\ s\le \beta
\\
F(s)=A/s\quad s\le \beta+1
\end{array}
\right\}
\Rightarrow
\begin{array}{l}
A=2e^\gamma
\\
\ \ \ \;=3'56\dots
\\
\beta=2
\end{array}
\]

\

\

$\beta$=límite de criba (sieving limit)

\

\


{\sc Problema bueno}

\

\[
\text{(B) }\left\{
\begin{array}{l}
(sF(s))'=f(s-1)\quad s>3
\\
(sf(s))'=F(s-1)\quad s>2
\\
f(s)=0\text{ si $s\le 2$}
\\
F(s)=2e^\gamma/s\text{ si $s\le 3$}
\end{array}
\right.
\]

\

Dado un $s$ se puede hallar fácilmente $f(s)$ y $F(s)$ iterando a partir de las condiciones iniciales.


\newpage

\begin{center}
\fbox{\textbf{\fbox{$\phantom{\frac12}$4. Cribando$\phantom{\frac12}$}}}
\end{center}

\

Para no acumular errores,  tratamos de no sumar términos triviales, que suponemos que aparecen si $s>\beta=2$.

\[
S(A,z)=|A|-\sum_{p<z}S(A_p,p)
\]
\[
S(A_p,p)\gtrsim f(s_p)\frac{X\rho(p)}p V(p),
\quad
s_p>2\Rightarrow D/p>p^2
\]

\

Por tanto, escribimos:

\[
S(A,z)\le |A|-
\sum_{\begin{smallmatrix}
p<z \\ p^{3}<D\end{smallmatrix}}
S(A_p,p).
\]

\

En la segunda iteraci\'{o}n de Buchstab no podemos eliminar t\'{e}rminos
sin perder la desigualdad,

\[
S(A,z)\le |A|-
\sum_{\begin{smallmatrix}
p_1<z \\ p_1^{3}<D\end{smallmatrix}}
|A_{p_1}|
+\sum_{\begin{smallmatrix}
p_2<p_1<z \\ p_1^{3}<D \end{smallmatrix}}
S(A_{p_1p_2},p_2).
\]

\newpage 

Pero sí en la tercera:

\begin{eqnarray*}
S(A,z)\le |A|&-&
\sum_{\begin{smallmatrix}
p_1<z \\ p_1^{3}<D\end{smallmatrix}}
|A_{p_1}|
+\sum_{\begin{smallmatrix}
p_2<p_1<z \\ p_1^{3}<D \end{smallmatrix}}
|A_{p_1p_2}|
\\
&-&\sum_{\begin{smallmatrix}
p_3<p_2<p_1<z \\ p_1^{3}<D,\ p_3^{3}p_2p_1<D
\end{smallmatrix}}
S(A_{p_1p_2p_3},p_3).
\end{eqnarray*} 

\


Iterando, probamos que
\begin{eqnarray*}
\mathcal{D}^+&=&
\{p_1p_2\cdots p_m
\;:\;
p_m<p_{m-1}<\dots <p_1,
\\
& & 
p_{2r+1}^{3}p_{2r}\cdots p_2p_1<D\text{ para todo }2r+1\le m\}
\\
\mathcal{D}^-&=&
\{p_1p_2\cdots p_m
\;:\;
p_m<p_{m-1}<\dots <p_1,
\\
& &
p_{2r}^{3}p_{2r-1}\cdots p_2p_1<D\text{ para todo }2r\le m\}
\end{eqnarray*}
definen una criba.

\

{\sc Gran problema}:

\ 

Demostrar

\[
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^-\end{smallmatrix}}
\mu(d)|A_d|
\approx f(s)XV(z)
\]
y
\[
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^+\end{smallmatrix}}
\mu(d)|A_d|
\approx F(s)XV(z)
\]


\newpage

{\sc El teorema}

\

Una  vez superado este obstáculo, el teorema fundamental sería:

\begin{theo}[Jurkat-Richter]
Supongamos $\kern-1pt\kappa=1$ 
y $f$ y $F$ soluciones de {\rm (B)}, entonces:
\[
(f(s)-\epsilon)XV(z)-E
\kern-2pt\le\kern-2pt S(A,z)\kern-2pt\le\kern-2pt 
(F(s)+\epsilon)XV(z)+E
\]
donde $\epsilon$ tiende a cero si $D$ crece.
\end{theo}

\

\textbf{Obs. 1}: $\epsilon$ decae algo más lento que $(\log\log D)^{-1}$, con constantes que dependen de las de la definición de dimensión.

\

\textbf{Obs. 2}:  El teorema se generaliza a todas las dimensiones  $\kappa>1/2$ cambiando el problema (B) por 
\[
\begin{cases}
(s^\kappa F(s))'=\kappa s^{\kappa-1}f(s-1) 
\\
(s^\kappa f(s))'=\kappa s^{\kappa-1}F(s-1) 
\end{cases}
\]
con ciertas condiciones iniciales y límite de criba $\beta$ que dependen de $\kappa$ (de una forma muy complicada).

\newpage

{\sc Ideas en la prueba}

\

$\bullet$ 
$V_m$ \lq\lq trozo'' de $V(z)$ tal que la condición que define $\mathcal{D}^+$ y $\mathcal{D}^-$ falla para el $m$-ésimo mayor primo:
\[
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^-\end{smallmatrix}}
\mu(d)\frac{\rho(d)}d
=V(z)-\sum_{2|m}V_m(z)
\]
y
\[
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^+\end{smallmatrix}}
\mu(d)\frac{\rho(d)}d
=V(z)+\sum_{2\notdiv m}V_m(z)
\]
con
\[
V_m(z)=\sum_{(p_1,p_2,\dots,p_m)\in\mathcal{N}_m}
\frac{\rho(p_1p_2\cdots p_m)}{p_1p_2\cdots p_m}V(p_m)
\]
donde
\begin{eqnarray*}
\mathcal{N}_m&=&\big\{(p_1,p_2,\dots,p_m)\; :\;
p_m<\dots <p_1<z, 
\\
& & p_m^{3}p_{m-1}\cdots p_1\ge D,
\\
& & p_n^{3}p_{n-1}\cdots p_1< D\text{ si $m-n=$\;par$>0$}\big\}
\end{eqnarray*}

\

$\bullet$ 
Sumación por partes (usando la definición de dimensión, $K\approx 1$) $\Rightarrow$  
$V_m(z)/V(z)\approx f_m(s)=$
\[
\frac 1s
\int_{
\begin{smallmatrix}
0<t_m<\dots <t_1<1/s
\\
t_1+\dots +t_{n-1}+3t_n<1\text{ si $m-n=$par$>0$}
\\
t_1+\dots +t_{m-1}+3t_m\ge 1
\end{smallmatrix}
}
\kern-50pt
t_1^{-1}\cdots t_{m-1}^{-1}t_m^{-2}
\;dt_1\dots\;dt_m
\]


\newpage

$\bullet$ 
Relaciones de recurrencia para $V_m$ y $f_m$ $\Rightarrow$
\[
\sum_{\begin{smallmatrix}
m\le M \\
m\equiv M\ (2)
\end{smallmatrix}}
V_m(z)
<V(z)
\sum_{\begin{smallmatrix}
m\le M \\
m\equiv M\ (2)
\end{smallmatrix}}
f_m(s)+\text{\tt Error}
\]
$\text{\tt Error}$ es muy malo, crece exponencialmente en la cons\-tante $K$ de la definición de criba.

\

$\bullet$ Podemos aproximar $K$ a 1 a voluntad si sólo se consideran los primos grandes. Se dividen los primos entre los que cumplen $p\le w$ y $p>w$ y se hace una composición de cribas. En los primeros primos la criba vendrá de aplicar el lema fundamental, y en los segundos se utilizará la fórmula anterior.

Los parámetros son:
\begin{itemize}
\item Truncación: $w=D^{-\epsilon/\log\epsilon}$
\item Criba pequeña: $\text{nivel}=D^\epsilon$
\item Criba grande: $\text{nivel}=D$
\end{itemize} 

\newpage

\begin{center}
\fbox{\textbf{\fbox{$\phantom{\frac12}$5. Practicando$\phantom{\frac12}$}}}
\end{center}

\

$f(s)=2e^\gamma s^{-1}\log(s-1)$ en $(2,4]$ $\Rightarrow$ Cota inferior 

(no trivial siempre que $s>\beta$)

\

\

\textbf{1)} ¿Hay infinitos primos de la forma $n^2+1$?
\[
A=\{n^2+1\; :\; n\le X\}
\]

\[
|A_p|=\{n^2\equiv -1\ (p) \; :\; n\le X\}=X\frac{\rho(p)}p+r_p
\]
\[
\rho(p)=\begin{cases}
2 &\text{ si $p\equiv 1\ (4)$}
\\
0 &\text{ si $p\equiv 3\ (4)$}
\\
1 &\text{ si $p=2$}
\end{cases}
\qquad\ \qquad V(z)\sim\frac{\text{Cte}}{\log z}
\]

\

$D\ll X/\log^3X\ \Rightarrow $ Error despreciable
\[
s>2\qquad\Rightarrow\qquad S(A,z)\gg \frac{X}{\log X}\quad\text{ con $z=X^{0'49}$}
\]

Como $(X^{0'49})^5>X^2+1$

\

{\sl Hay infinitos números de la forma $n^2+1$ con a lo más cuatro factores primos.}

\newpage

\textbf{2)} Detectando primos
\[
A=\{1,2,3,\dots, X\}
\]

$S(A,x^{1/2+\epsilon})\asymp X/\log X$ pero no podemos tratar el caso $\epsilon=0$ que daría una cota inferior para $\pi(x)$.

\

\ 

\textbf{3)} Problema de paridad
\begin{eqnarray*}
A^0&=&\{n\le 2X\; :\; 2|\text{num.  factores primos de }n\}
\\
A^1&=&\{n\le 2X\; :\; 2\not|\text{num. factores primos de }n\}
\end{eqnarray*} 

\


Selberg: \quad $z=x^{1/s}$ \quad ($D\ll X$)

\begin{eqnarray*}
S(A^0,z)&=& f(s)XV(z)+O(X/\log^2 X)
\\
S(A^1,z)&=& F(s)XV(z)+O(X/\log^2 X)
\end{eqnarray*} 

¡El teorema es óptimo!
$A^0$ y $A^1$ son indistinguibles desde el punto de vista de la criba. ($\rho^0(d)$ y $\rho^1(d)$ iguales con errores $r_d^0$, $r_d^0$ comparables)  {\sl Fenómeno de paridad}. Sin embargo son bien diferentes y $A_0$ ni si\-quiera contiene primos.

\

Entonces...¿no se puede ir más allá? ¿guardamos en el almacén los libros de criba?
No se pierda las próximas \textit{xerrades}.

\end{LARGE}


\newpage

\pagestyle{myheadings} %% running title
\markboth{}{{\sc El garbell combinatori}}

\begin{center}
\begin{LARGE}
\bf Seminario de Criba. Barcelona 2005
\end{LARGE}
\end{center}

\

\section{Cribas combinatorias}
La f\'{o}rmula exacta de la criba de Erat\'{o}stenes-Legendre
(inclusi\'{o}n-exlusi\'{o}n),
\begin{equation}\label{eraleg}
S(A,z)=\sum_{d|P(z)}\mu(d)|A_d|,
\end{equation}
tiene una serie deficiencia, y es que el n\'{u}mero de sumandos crece
exponencialmente con $z$ y por tanto en las aproximaciones
$|A_d|=X\rho(d)/d+r(A,d)$ la acumulaci\'{o}n de los t\'{e}rminos de error
$r(A,d)$ arruina el t\'{e}rmino principal excepto para $z$
excesivamente peque\~{n}o.

Supongamos que s\'{o}lo tenemos un control adecuado de los t\'{e}rminos de
error cuando  $d<D$ con $D=z^s$, para alg\'{u}n $s>1$; t\'{\i}picamente una
cota de la forma
\begin{equation}\label{nivcri}
\sum_{\begin{smallmatrix}d|P(z)\\ d<D\end{smallmatrix}}
|r(A,d)|\ll\frac{X}{\log^C X}
\end{equation}
para $C>0$ suficientemente grande, una vez establecida una cota para $D$ en funci\'{o}n
de~$X$.

La \underbar{criba combinatoria} consiste en
despreciar en \refe{eraleg} los
sumandos correspondientes a los valores de $d$ que est\'{e}n fuera de
cierto subconjunto de $[1,D]$ (a $D$ se le llama \underbar{nivel de criba}). Con ello perderemos la igualdad
pero procediendo adecuadamente todav\'{\i}a podremos conseguir
desigualdades.

Concretamente, dados dos subconjuntos
$\mathcal{D}^+,\mathcal{D}^-\subset [1,D]$ para los que se
verifique
\[
\sum_{\begin{smallmatrix}d|n\\ d\in\mathcal{D}^-\end{smallmatrix}}
\mu(d)
\le
\sum_{d|n}
\mu(d)
\le
\sum_{\begin{smallmatrix}d|n\\ d\in\mathcal{D}^+\end{smallmatrix}}
\mu(d)
\]
se obtiene
\begin{equation}\label{cricom}
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^-\end{smallmatrix}}
\mu(d)|A_d|
\le S(A,z)\le
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^+\end{smallmatrix}}
\mu(d)|A_d|.
\end{equation}
La aproximaci\'{o}n $A_d\approx X\rho(d)/d$ lleva com\'{u}nmente a
t\'{e}rminos principales comparables a $XV(z)$, salvo constantes
dependiendo de $s$,  y se siguen desigualdades del tipo
\begin{equation}\label{descri}
f(s)XV(z)+\text{\tt error}
\le S(A,z)\le
F(s)XV(z)+\text{\tt error},
\end{equation}
donde, como antes, $s=\log D/\log z$ (esto es, $D=z^s$), $s\ge 1$, y el error viene de \refe{nivcri}.

\section{La criba de Brun}
La \underbar{criba de Brun} se basa en las desigualdades
\[
\sum_{\begin{smallmatrix}d|n\\
\omega(d)\le 2k+1\end{smallmatrix}}
\mu(d)
\le
\sum_{d|n}
\mu(d)
\le
\sum_{\begin{smallmatrix}d|n\\
\omega(d)\le 2k\end{smallmatrix}}
\mu(d)
\qquad
\text{con $\omega(d)=$nº de factores primos de $d$,}
\]
De forma que $\mathcal{D}^-$ y $\mathcal{D}^+$ son subconjuntos de
enteros con un n\'{u}mero impar y par de factores primos,
respectivamente.

Brun perfeccion\'{o} esta elecci\'{o}n y prob\'{o} algunos resultados notables
(el m\'{a}s conocido es que la suma de los inversos de los primos
gemelos converge). Como es de esperar, cuando $s\to\infty$, es
decir cuando la restricci\'{o}n dada por el tama\~{n}o de $D$ no se hace
sentir, los t\'{e}rminos principales en \refe{descri} se acercan al
t\'{e}rmino esperado desde el punto de vista probabilista: $XV(z)$. A la cuantificaci\'{o}n de esta propiedad se le
suele llamar {\it lema fundamental}. Expl\'{\i}citamente, si $K$ y
$\kappa$ son como en la definici\'{o}n de dimensi\'{o}n de criba:
\begin{equation}\label{dimcri}
\prod_{w\le p<z}\big(1-\rho(p)/p\big)^{-1}\le K(\log z/\log
w)^{\kappa},
\end{equation}
una forma del lema fundamental afirma que
para $s$ suficientemente grande en comparaci\'{o}n con $\kappa$, se
cumple que $f(s)$ y $F(s)$ son $1+O\big(K^{10}e^{9\kappa-s}\big)$
con una constante $O$ absoluta.

\section{Las iteraciones de Buchstab}
Buchstab introdujo la f\'{o}rmula
\begin{equation}\label{buchst}
S(A,z)=|A|-\sum_{p<z}S(A_p,p),
\end{equation}
cuya demostraci\'{o}n se reduce a notar que los elementos cribados
est\'{a}n en alguno de los conjuntos contados por los $S(A_p,p)$ y que
\'{e}stos son disjuntos. Una de las virtudes de esta f\'{o}rmula es que
permite transformar cotas inferiores en cotas superiores y
viceversa. Pero sobre todo, permite en algunas ocasiones mejorar
resultados de criba.

Procediendo sin rigor, se pueden anticipar los resultados de la
criba $\beta$ aplicando sucesivamente \refe{buchst}, \'{e}stas son
las \underbar{iteraciones de Buchstab}. Antes de ilustrar este
punto, n\'{o}tese la f\'{o}rmula
\begin{equation}\label{igualv}
V(z)=1-\sum_{p<z}\frac{\rho(p)}p V(p)
\end{equation}
que, aunque inmediata, podr\'{\i}a considerarse una consecuencia de
\refe{buchst}.

Supongamos que en \refe{descri} despreciamos el error (lo que
indicamos empleando $\lesssim$ en lugar de $\le$). Por
\refe{buchst}
\[
S(A,z)\lesssim X-\sum_{p<z}f(s_p)\frac Xp V(p)
\]
donde $s_p=\log(D/p)/\log p=\log D/\log p-1$. Empleando
\refe{igualv} esto se puede reescribir  como
\[
S(A,z)\lesssim XV(z)\left(
1+\sum_{p<z}\big(1-f\big(\frac{\log D}{\log p}-1\big)\big)
\frac{\rho(p)}p \frac{V(p)}{V(z)}
\right).
\]
Si pudi\'{e}ramos aplicar la definici\'{o}n de dimensi\'{o}n \refe{dimcri} con $K=1$ e
igualdad, por \refe{igualv} se tendr\'{\i}a que $-\rho(t)V(t)/t$ es el
incremento de $\log^{-\kappa}t$ y $V(z)$ es como  $\log^{-\kappa}z$
de modo que el par\'{e}ntesis exterior se deber\'{\i}a aproximar por
\[
1+\int_0^z
\big(1-f\big(\frac{\log D}{\log t}-1\big)\big)
\frac{d(\log^{-\kappa}t)}{\log^{-\kappa}z}
=1+\kappa s^{-\kappa}\int_s^\infty(1-f(t-1))t^{\kappa-1}\; dt
\]
(esta igualdad  se sigue del cambio $\log D/\log t\mapsto t$).

Lo mismo se aplica con la cota inferior. Si este proceso fuera
\lq\lq contractivo'' en el l\'{\i}mite se obtendr\'{\i}a \refe{descri} con
funciones $f$ y $F$ cumpliendo
\[
F(s)=1+\kappa s^{-\kappa}
\int_s^\infty(1-f(t-1))t^{\kappa-1}\; dt
,
\quad
f(s)=1+\kappa s^{-\kappa}
\int_s^\infty(1-F(t-1))t^{\kappa-1}\; dt,
\]
o lo que es lo mismo
\begin{equation}\label{difdif}
\begin{cases}
&(s^\kappa f(s))'=\kappa s^{\kappa-1}F(s-1)
\\
&(s^\kappa F(s))'=\kappa s^{\kappa-1}f(s-1)
\end{cases}
\end{equation}
Si todo este proceso se pudiera justificar, y supi\'{e}ramos resolver
las ecuaciones \refe{difdif} con $f(\infty)=F(\infty)=1$,
tendr\'{\i}amos un candidato para desigualdad de criba \'{o}ptima. Sin
embargo, la acumulaci\'{o}n de t\'{e}rminos de error y las
simplificaciones incorrectas, hacen de ello una tarea poco
realista. En su lugar, veremos una criba combinatoria que permite
alcanzar el l\'{\i}mite de las iteraciones de Buchstab.

\section{La criba $\beta$}

Ciertamente no parece \'{u}til contemplar en las iteraciones de
Buchstab rangos en los que las desigualdades de criba
\refe{descri} sean triviales. Supongamos que existe un $\beta>1$ a
partir del cual la cota inferior en \refe{descri} deja de ser
trivial, esto es, $f(\beta)=0$ y $f(s)>0$ para $s>\beta$.
A este valor se le llama \underbar{l\'{\i}mite de criba} ({\it sieving limit}).

El $s$ correspondiente a $S(A_p,p)$ es $s_p=\log(D/p)\big/\log p$,
y lo anterior sugiere desconsiderar en \refe{buchst} los t\'{e}rminos
con $\beta\ge s_p$, obteni\'{e}ndose
\[
S(A,z)\le |A|-
\sum_{\begin{smallmatrix}
p<z \\ p^{\beta+1}<D\end{smallmatrix}}
S(A_p,p).
\]
En la segunda iteraci\'{o}n de Buchstab no podemos eliminar t\'{e}rminos
sin perder la desigualdad, por tanto tenemos simplemente
\[
S(A,z)\le |A|-
\sum_{\begin{smallmatrix}
p_1<z \\ p_1^{\beta+1}<D\end{smallmatrix}}
|A_{p_1}|
+\sum_{\begin{smallmatrix}
p_2<p_1<z \\ p_1^{\beta+1}<D \end{smallmatrix}}
S(A_{p_1p_2},p_2).
\]
Pero en la tercera iteraci\'{o}n podemos eliminar los t\'{e}rminos con
$\beta\ge s_{p_1p_2p_3}$, donde
$s_{p_1p_2p_3}=\log(D/p_1p_2p_3)\big/\log p_3$, y se tiene
\[
S(A,z)\le |A|-
\sum_{\begin{smallmatrix}
p_1<z \\ p_1^{\beta+1}<D\end{smallmatrix}}
|A_{p_1}|
+\sum_{\begin{smallmatrix}
p_2<p_1<z \\ p_1^{\beta+1}<D \end{smallmatrix}}
|A_{p_1p_2}|
-\sum_{\begin{smallmatrix}
p_3<p_2<p_1<z \\ p_1^{\beta+1}<D,\ p_3^{\beta+1}p_2p_1<D
\end{smallmatrix}}
S(A_{p_1p_2p_3},p_3).
\]
Razonamientos an\'{a}logos dan lugar a cotas inferiores. Con ello
hemos creado una criba combinatoria determinada por
\begin{eqnarray*}
\mathcal{D}^+&=&
\{p_1p_2\cdots p_m
\;:\;
p_m<p_{m-1}<\dots<p_1\text{ y }
p_{2r+1}^{\beta+1}p_{2r}\cdots p_2p_1<D\text{ para }2r+1\le m\}
\\
\mathcal{D}^-&=&
\{p_1p_2\cdots p_m
\;:\;
p_m<p_{m-1}<\dots<p_1\text{ y }
p_{2r}^{\beta+1}p_{2r-1}\cdots p_2p_1<D\text{ para }2r\le m\}
\end{eqnarray*}
\'{E}sta es la \underbar{criba $\beta$} (desarrollada por H. Iwaniec).

\

Al ser una criba combinatoria, se pueden controlar los t\'{e}rminos de
error bajo la condici\'{o}n \refe{nivcri} y se obtienen cotas del tipo
\[
X
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^-\end{smallmatrix}}
\mu(d)\frac{\rho(d)}d+\text{\tt error}
\le S(A,z)\le
X
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^+\end{smallmatrix}}
\mu(d)\frac{\rho(d)}d+\text{\tt error}.
\]
Ahora esperamos extraer de estos sumandos un factor $V(z)$ y
acumular las cantidades sobrantes en las funciones $f$ y $F$. Con
tal fin escribimos cada sumatorio como $V(z)$ quitando los
productos correspondientes a los elementos que no est\'{e}n en
$\mathcal{D}^-$
o en
$\mathcal{D}^+$, y estos productos eliminados los clasificamos en
diferentes sumatorios $V_m$, donde $m$ indica que el $m$-\'{e}simo
mayor primo es el primero para el que falla la condici\'{o}n que
define $\mathcal{D}^-$ y $\mathcal{D}^+$. Concretamente:
\[
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^-\end{smallmatrix}}
\mu(d)\frac{\rho(d)}d
=V(z)-\sum_{2|m}V_m(z)
\quad\text{y}\quad
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}^+\end{smallmatrix}}
\mu(d)\frac{\rho(d)}d
=V(z)+\sum_{2\notdiv m}V_m(z)
\]
con
\[
V_m(z)=\sum_{(p_1,p_2,\dots,p_m)\in\mathcal{N}_m}
\frac{\rho(p_1p_2\cdots p_m)}{p_1p_2\cdots p_m}V(p_m)
\]
donde
\begin{eqnarray*}
\mathcal{N}_m=\big\{(p_1,p_2,\dots,p_m)\; :\;
&\ &
p_m<\dots <p_1<z, \
p_m^{\beta+1}p_{m-1}\cdots p_1\ge D,
\\
&\ &\qquad\ \qquad
p_n^{\beta+1}p_{n-1}\cdots p_1< D\text{ si $m-n=$\;par$>0$}\big\}
\end{eqnarray*}

Como hab\'{\i}amos visto, la definici\'{o}n de dimensi\'{o}n de criba
\refe{dimcri}, suponiendo $K\approx 1$ y \refe{igualv}, sugiere
que $-\rho(t)V(t)/t$ se comporta como el incremento de
$\log^{-\kappa}t$, $V(z)$ como $\log^{-\kappa}z$ y $\rho(t)/t$
como el incremento de $\kappa\log \log t$. As\'{\i} que una conjetura
plausible es que
\[
\frac{V_m(z)}{V(z)}\approx
\log^\kappa z\int_{(t_1,\dots,t_m)\in\mathcal{N}_m}
\frac{\kappa \; dt_1}{t_1\log t_1}\cdot
\frac{\kappa \; dt_2}{t_2\log t_2}
\cdots
\frac{\kappa \; dt_{m-1}}{t_{m-1}\log t_{m-1}}
\; d(-\log^{-\kappa}t_m).
\]
Con el cambio $\log t_j/\log D\mapsto u_j$ se sigue
$V_m(z)/V(z)\approx f_m(s)$ donde
\[
f_m(s)=\kappa^ms^{-\kappa}
\int_{
\begin{smallmatrix}
0<t_m<\dots <t_1<1/s
\\
t_1+\dots +t_{n-1}+(\beta+1)t_n<1\text{ si $m-n=$par$>0$}
\\
t_1+\dots +t_{m-1}+(\beta+1)t_m\ge 1
\end{smallmatrix}
}
t_1^{-1}t_2^{-1}\cdots t_{m-1}^{-1}t_m^{-\kappa -1}
\;dt_1\;dt_2\dots\;dt_m.
\]
En definitiva, cabe esperar que se cumplan las desigualdades de
criba \refe{descri} con
\begin{equation}\label{serief}
f(s)=1-\sum_{2|m}f_m(s)
\qquad\text{y}\qquad
F(s)=1+\sum_{2\notdiv m}f_m(s)
\end{equation}
para $s>\beta$ con $\beta$ el \lq\lq \'{u}ltimo cero'' de $f$.


\section{El teorema de criba}

Transformar las ideas del apartado anterior en un teorema es una
tarea ardua.

Un punto b\'{a}sico es cuantificar la precisi\'{o}n de la aproximaci\'{o}n  de
$V_m(z)/V(z)$ por $f_m(s)$ lo que  lleva al problema aparentemente
irresoluble de que el error acumulado tiende exponencialmente a
infinito con el n\'{u}mero de t\'{e}rminos.  En concreto, se puede probar
que para $M\in\Z^+$
\begin{equation}\label{induvf}
\sum_{\begin{smallmatrix}
m\le M \\
m\equiv M\ (2)
\end{smallmatrix}}
V_m(z)
<V(z)\bigg(
\sum_{\begin{smallmatrix}
m\le M \\
m\equiv M\ (2)
\end{smallmatrix}}
f_m(s)
+(K-1)M^2K^M\big(\frac{\beta+M}{\beta-1}\big)^{\kappa M}
\bigg)
\end{equation}
donde $K$ es como en \refe{dimcri}.

La forma de llegar a \refe{induvf} pasa por notar primero que
escribiendo $z_m=D^{1/(\beta+m)}$ e
$y_m=\min\big(z,D^{1/(\beta+\delta_m)}\big)$ con
$\delta_m=(1-(-1)^m)/2$, se tiene
\[
V_m(z)=\sum_{z_m\le p<y_m}
\frac{\rho(p)}pV_{m-1}(D/p,p)
\qquad\text{si $\beta-\delta_m\le s<\beta+m$},
\]
donde $V_{m-1}(D/p,p)$ es $V_{m-1}(p)$ cambiando $D$ por $D/p$.
An\'{a}logamente definiendo $s_m=\max(s,\beta+\delta_m)$
se tiene
\begin{equation}\label{recurf}
s^{\kappa}f_m(s)=\kappa\int_{s_m}^{\beta+m}
f_{m-1}(t-1)t^{\kappa-1} \;
dt\qquad\text{si $\beta-\delta_m\le s<\beta+m$}.
\end{equation}
Evidentemente $V_m(z)=f_m(s)=0$ si $s\ge \beta+m$.
Para demostrar \refe{induvf} se aplican estas f\'{o}rmulas de
recurrencia y sumaci\'{o}n por partes complet\'{a}ndose un proceso de
inducci\'{o}n.

\

Incluso olvidando el crecimiento del error en \refe{induvf}, hay
un problema de naturaleza m\'{a}s t\'{e}cnica pero en absoluto trivial, y
es la convergencia de las series \refe{serief}. Una vez supuesta
para $s>\beta$, derivando \refe{recurf}
(n\'{o}tese que $s_m=s$ para $s_m\ge \beta+\delta_m$)
se puede deducir que las
funciones \refe{serief} verifican \refe{difdif}.
De hecho la convergencia se prueba definiendo unas soluciones de
ecuaciones de este tipo que act\'{u}an como mayorantes. La
determinaci\'{o}n de $\beta$ en funci\'{o}n de $\kappa$, el \'{u}nico
par\'{a}metro del que depende \refe{recurf} y por tanto $f$ y $F$, no
es f\'{a}cil. Para $\kappa=1$ (criba lineal) se tiene $\beta=2$ y
$\beta\approx 1+3'591\kappa$ para $\kappa$ grande.
De la segunda ecuaci\'{o}n \refe{difdif} se sigue $F(s)=A/s^{\kappa}$
donde la constante $A$ tambi\'{e}n est\'{a} determinada por $\kappa$
(debido a la homogeneidad de \refe{difdif} y la condici\'{o}n
$F(\infty)=f(\infty)=1$). De nuevo, no hay una f\'{o}rmula sencilla
para $A$ pero se puede probar que para $\kappa=1$ se tiene
$A=2e^\gamma=3'562\dots$ y $A\approx 2'556(\beta-1)^{\kappa}$ para
$\kappa$ grande. Una vez hallados $\beta=\beta(\kappa)$ y
$A=A(\kappa)$, es f\'{a}cil calcular num\'{e}ricamente $f(s)$ y $F(s)$ para
cualquier valor de $s$ recursivamente por medio de:
\begin{equation}\label{difbue}
\begin{cases}
(s^\kappa f(s))'=\kappa s^{\kappa-1}F(s-1)&\quad\text{si
$s>\beta$}
\\
(s^\kappa F(s))'=\kappa s^{\kappa-1}f(s-1)&\quad\text{si
$s>\beta+1$}
\\
f(s)=0&\quad\text{si
$s\le\beta$}
\\
F(s)=A/s^{\kappa}&\quad\text{si
$s\le\beta+1$}
\end{cases}
\end{equation}



\

Para compensar el crecimiento exponencial en $M$ del \'{u}ltimo
t\'{e}rmino de \refe{induvf}, deber\'{\i}a ser $K$ muy pr\'{o}ximo a
$1$ pero en \refe{dimcri} esto no va a ser posible si $w$ es
peque\~{n}o. T\'{\i}picamente se tiene $K=1+L/\log w$ con $L$ una constante.
Repitiendo la construcci\'{o}n de $\mathcal{D}^-$ y $\mathcal{D}^+$
pero ahora a\~{n}adiendo la condici\'{o}n de que todos los factores sean
mayores que $w$, podr\'{\i}amos escribir en \refe{induvf} $L/\log w$ en lugar
de $K-1$. Por otra parte, $p_j>w$ implica $v_m(z)=0$ para
$m+\beta\ge \log D/\log w$ de modo que podemos fijar en el t\'{e}rmino
de error $M=\log D/\log w-\beta$ mientras que $M$ contin\'{u}a siendo
arbitrario en los sumatorios. Eligiendo $w=D^{-\epsilon/\log
\epsilon}$ ($w$ \lq\lq poco mayor'' que $D^\epsilon$), $\log D>L$
y $\log\log D>\epsilon^{-1}\log^2\epsilon$, se consigue que el
t\'{e}rmino de error sea comparable a $\epsilon L$ con $\epsilon$ tan
peque\~{n}o como se desee. En definitiva
\[
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}_*^-\end{smallmatrix}}
\mu(d)\frac{\rho(d)}d
=V(z)\big(f(s)+O(\epsilon L)\big)
\quad\text{y}\quad
\sum_{\begin{smallmatrix}d|P(z)\\ d\in\mathcal{D}_*^+\end{smallmatrix}}
\mu(d)\frac{\rho(d)}d
=V(z)\big(F(s)+O(\epsilon L)\big)
\]
donde $\mathcal{D}_*^-$ y $\mathcal{D}_*^+$ son como
$\mathcal{D}^-$ y $\mathcal{D}^+$ pero con la condici\'{o}n de que los
factores primos sean mayores que $w=D^{-\epsilon/\log\epsilon}$.

Evidentemente esto no es directamente aplicable, porque a la hora
de cribar hemos descartado simplemente los primos $p_j\le w$. Pero
el lema fundamental asegura que podemos construir una criba de
nivel $\widetilde{D}=D^\epsilon$ y
$\widetilde{z}=D^{-\epsilon/\log\epsilon}$
para cribar los primos $p_j\le \widetilde{z}=w$ en la que se cumpla
\refe{descri} con $f(s)$ y $F(s)$ iguales a $1+O(\epsilon
L^{10})$.

Finalmente, componiendo ambas cribas se tendr\'{\i}a una criba de nivel
$D^{1+\epsilon}$ y $F(s)$ y $f(s)$ vendr\'{\i}an dadas por las
series
\refe{serief}, que a su vez son soluciones de \refe{difbue} (una vez
determinados $\beta$ y $A$), salvo un error
$(1+O(\epsilon L))(1+O(\epsilon L^{10}))=1+O(\epsilon L^{11})$.

Con algunos cambios, por ejemplo renombrar $D^{1+\epsilon}$ como
$D$ y elegir un $\epsilon$ adecuado, se tiene el teorema de criba:

\begin{theo}
Si $L$ es una constante tal que
\refe{dimcri}
es v\'{a}lido con
$K=1+L/\log w$. Para $\log D>2L$ y suponiendo \refe{nivcri}, se
tiene para $s>\beta=\beta(\kappa)$
\[
\big(f(s)+O(\Delta)\big)XV(z)+O(E)
\le S(A,z)\le
\big(F(s)+O(\Delta)\big)XV(z)+O(E)
\]
donde $E=X/\log^CX$, $\Delta =L^{11}(\log\log\log D)^3/\log\log
D$ y $f(s)$ y $F(s)$ son las soluciones de \refe{difbue}.
\end{theo}


\section{El caso lineal. Ejemplos}

Como hemos mencionado antes, para $\kappa=1$ (criba lineal) se
tiene $\beta=2$ y $A=2e^\gamma$.
Gracias a \refe{difbue},  en el intervalo $[2,3]$
\[
f(s)=\frac{2e^\gamma}s\log(s-1)\qquad\text{y}\qquad F(s)=\frac{2e^\gamma}s.
\]
Iterando se puede extender este rango de definici\'{o}n (con f\'{o}rmulas cada vez m\'{a}s complejas).

\

Como ejemplo ilustrativo cribemos en el conjunto
\[
A=\{n^2+1\;:\; n\le X\}.
\]
De la f\'{o}rmula $\big(\frac{-1}p\big)=(-1)^{(p-1)/2}$, se tiene para $p\ne 2$
\[
|A_p|=|\{n\le X\; :\; p|n^2+1\}|=
\begin{cases}
2X/p+O(1)&\text{si $p\equiv 1\ (4)$}
\\
0&\text{si $p\equiv 3\ (4)$}
\end{cases}
\]
Por tanto $\rho(p)=2$ si  $p\equiv 1\ (4)$, y $\rho(p)=0$ si  $p\equiv 3\ (4)$. La criba es consecuentemente lineal.

En general se tiene por el teorema chino de resto
\[
|A_{p_1p_2\cdots p_r}|=\frac{\rho(p_1p_2\cdots p_r)X}{p_1p_2\cdots p_r}+O(2^r).
\]
As\'{\i} que siempre que $D\le X/\log^{C+1}X$ se tiene asegurado \refe{nivcri}.

La condici\'{o}n $s>2$ que se necesita para tener una cota inferior no trivial lleva a que el mayor $z$ aceptable es $X^{1/2-\epsilon}$ con $\epsilon$ arbitrariamente peque\~{n}o. Con esta elecci\'{o}n se tiene
\[
S(A,z)\ge C_\epsilon\frac{X}{\log X}\qquad
\text{para $X$ grande y cierta $C_\epsilon>0$.}
\]
Los elementos de $A$ est\'{a}n acotados por $X^2+1$ y como para $\epsilon<0'1$ se tiene $5(1/2-\epsilon)>2$, en estas condiciones, los elementos que subsisten tras la criba
tienen menos de $5$ factores primos. Es decir, hemos probado:


\begin{center}
{\sl
Hay infinitos n\'{u}meros de la forma $n^2+1$ con a lo m\'{a}s cuatro factores primos.}
\end{center}

\

Veamos un ejemplo doble de Selberg que tiene gran inter\'{e}s te\'{o}rico. Consideremos
\[
A^{\text{par}}=\{n\le 2X\; :\; \lambda(n)=1\}
\qquad\text{y}\qquad
A^{\text{impar}}=\{n\le 2X\; :\; \lambda(n)=-1\}
\]
donde $\lambda$ es la funci\'{o}n de Liouville que vale $1$ si el n\'{u}mero de factores primos (contando multiplicidades) es par y $-1$ si es impar.

Se tiene
\[
|A^{\text{par}}_d|=|\{n\le 2X/d\; :\; \lambda(d)\lambda(n)=1\}|
=\frac 12\sum_{n\le 2X/d}(1+\lambda(d)\lambda(n)).
\]
Se conoce por m\'{e}todos de teor\'{\i}a anal\'{\i}tica de n\'{u}meros que $\sum_{n\le N}\lambda(n)=O(N/\log^CN)$ para cualquier $C>0$, por tanto $\rho(d)=1$ con un error admisible y se tiene que  la criba es lineal. Lo mismo se aplica a $A^{\text{impar}}$.

Seg\'{u}n el teorema, salvo t\'{e}rminos de error,
$S(A^{\text{par}},z)$
y
$S(A^{\text{impar}},z)$
est\'{a}n entre $f(s)XV(z)$ y $F(s)XV(z)$. Pero por otra parte, aplicando las iteraciones de Buchstab directamente a
$S(A^{\text{par}},z)$
y
$S(A^{\text{impar}},z)$, desarrollando un proceso iterativo, se puede probar que para $D=X$ y cada $s>1$ se tiene
\[
S(A^{\text{par}},z)=f(s)XV(z)+O\big(\frac{X}{\log^2X}\big)
\quad\text{y}\quad
S(A^{\text{impar}},z)=F(s)XV(z)+O\big(\frac{X}{\log^2X}\big).
\]
De aqu\'{\i} se pueden deducir dos consecuencias importantes:
\begin{itemize}
\item
Si $\kappa=1$, el teorema de criba es \'{o}ptimo en el sentido de
que los t\'{e}rminos principales no se pueden mejorar, ya que para
$A^{\text{par}}$ y $A^{\text{impar}}$ se alcanzan.
\item
Los conjuntos  $A^{\text{par}}$ y $A^{\text{impar}}$ son
indistinguibles desde el punto de vista de la criba (ya
que $|A^{\text{par}}_d|$ y $|A^{\text{impar}}_d|$ son similares),
y sin embargo son bien distintos  y $S(A^{\text{par}},z)$
y
$S(A^{\text{impar}},z)$ tienen diferente asint\'{o}tica. Hay un
l\'{\i}mite te\'{o}rico para separar con m\'{e}todos de criba n\'{u}meros con
una cantidad  par o impar de factores (\underbar{fen\'{o}meno de
paridad}).
\end{itemize}

\end{document}
