Add quadratic problem definition.

[Projet_Recherche_Operationnelle.git] / présentation / Slides_SGeomComp.tex

\documentclass[9pt,blackandwhite,roman,handout]{beamer}
\usepackage{etex}

\usefonttheme{professionalfonts}


% Setup appearance:
%\usetheme{Warsaw}
\usetheme{Darmstadt}

%\usecolortheme{seahorse}
%\usecolortheme{dove}
\usecolortheme{seagull}
%\usefonttheme[onlylarge]{structurebold}
%\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
%\setbeamertemplate{navigation symbols}{}



% Standard packages
%\usepackage[frenchb]{babel}
%\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
\usepackage{cmbright}
\usepackage[sans]{dsfont}
\usepackage{pifont}
%calscaled=.94,
%frakscaled=.97,
\usepackage[cal=euler,scr=rsfso]{mathalfa}%bb=cm,
%frak=mma,
%scr=esstix
\usepackage{mathrsfs} % pour faire des majuscules calligraphiées \mathcal{blabla}
%\usepackage[french,lined]{algorithm2e} % rajouter linesnumbered dans les arguments pour numéroter les lignes des algos, boxed pour l'encadrement
%\usepackage{extsizes}
%\usepackage{MnSymbol}
\usepackage{graphicx}
\usepackage{mathabx}
\usepackage[all]{xy}
\usepackage{ulem}

\usepackage{DotArrow}
%\usepackage[varg]{txfonts}
%\usepackage{matptmx}
\usepackage{extpfeil}
%\usepackage{MyMnSymbol}
\usepackage{comment}
%\usepackage{etex}
%usepackage{mathtools}
%\usepackage{fourier}

\usepackage{ragged2e}
\justifying

% Setup TikZ
\usepackage{tikz}
\usetikzlibrary{matrix,arrows}
\tikzstyle{block}=[draw opacity=0.7,line width=1.4cm]

\newcommand{\gk}{$g_k = \left \{ \begin{array}{ll}
                q^k+q^{k-1}-q^\frac{k+1}{2} - 2q^\frac{k-1}{2}+1 & \mbox{si } k \equiv 1 \pmod 2,\\
                q^k+q^{k-1}-\frac{1}{2}q^{\frac{k}{2}+1} - \frac{3}{2}q^{\frac{k}{2}}-q^{\frac{k}{2}-1} +1& \mbox{si } k \equiv 0 \pmod 2.
                \end{array} \right .$}

\newcommand{\ext}{\xymatrix{
    \FF= \Fq(x)(y) \ar@{-}[d]^{<\infty} \\ \Fq(x) \ar@{-}[d] \\ \Fq} }

\newcommand{\twoheaddownarrow}{%
\mathrel{\reflectbox{\rotatebox[origin=c]{-90}{$\xtwoheadrightarrow[ \; ]{   \reflectbox{\rotatebox[origin=c]{-90}{$\pi_Q \ $}} \ \  }$}}}}

\newcommand{\longdownmapsto}{%
\mathrel{\reflectbox{\rotatebox[origin=c]{-90}{$\xmapsto{ \ \ \ \reflectbox{\rotatebox[origin=c]{-90}{$\pi_Q \ $}} \ \ \ }$}}}}

\newcommand{\bigubrace}[1]{\underbrace{\mbox{}f(P_i), f'(P_i), \ldots, f^{(\ell_i-1)}(P_i)\vphantom{\sum_0^0}\hspace{#1}\mbox{}}_?}

\newcommand{\myubrace}[2]{\rotatebox[origin=c]{90}{$
\rotatebox[origin=c]{-90}{#1} \left \{
\begin{array}{l}
         \vspace{#2} \\
\end{array}
\right . \hspace{-1em}
$}}

\newcommand{\bluebrace}{{\color{blue}\left\{}}


\definecolor{mycvblue}{rgb}{0.302,0.537,0.737}


\setbeamercolor{structure}{fg=mycvblue}
\setbeamercolor{palette primary}{fg=mycvblue}
\setbeamercolor{subsection in head/foot}{parent=palette primary}

\setbeamertemplate{navigation symbols}{
%      \insertslidenavigationsymbol
%      \insertframenavigationsymbol
%      \insertsubsectionnavigationsymbol
%      \insertsectionnavigationsymbol
%      \insertdocnavigationsymbol
%      \insertbackfindforwardnavigationsymbol
}

%\renewcommand{\item}{\item[$\bullet$]}



\title[]{\LARGE{\textsc{Familles denses de courbes modulaires, nombres premiers\\ et \\rang de tenseur symétrique uniforme de la multiplication dans les corps finis}}}

\author[Alexey {\textsc Zykin}]{\textbf{Alexey {\textsc Zykin}$^{\dag}$} \\ (\textbf{1984 - 2017}) \\Laboratoire GAATI \\Université de la Polynésie Française\\
{\small National Research University Higher School of Economics} \\ Institute for Information Transmission Problems of the Russian Academy of Sciences\\\vspace{1em}\textbf{\textcolor{mycvblue}{en collaboration avec}}\\ \vspace{1em}  \textbf{Stéphane {\textsc Ballet}}\\ Equipe Arithmétique et Théorie de l'Information\\ Institut de Mathématiques de Marseille \\ Aix-Marseille Université}


\date[]{\\ \vspace{2em} {\bf Séminaire GAATI}\\  {\bf UPF} \\{\small  Avril  2017}}

\newtheorem{defin}{Définition}
\newtheorem{theoreme}{Théorème}
\newtheorem{lemme}{Lemme}
\newtheorem{corollaire}{Corollaire}
\newtheorem{proposition}{Proposition}
\newtheorem{propriete}{Propriété}
%\newtheorem{exemple}[definition]{Exemple}

\newcommand{\NN}{\ensuremath{\mathbb{N}}}
\newcommand{\CC}{\ensuremath{\mathbb{C}}}
\newcommand{\ZZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\PF}{\mathbf{P}_F}
\newcommand{\DF}{\mathsf{Div}(F)}
\newcommand{\Jac}{\ensuremath{\mathcal{J}\mathsf{ac}(F/\Fq)}}
\newcommand{\Fqr}[2][q]{\mathds{F}_{\!{#1}^{#2}}}
\newcommand{\Fq}{\Fqr{}}
\newcommand{\F}{\mathds{F}}
\newcommand{\FF}{\mathsf{F}}
\newcommand{\Fqn}{\Fqr{n}}
\newcommand{\D}[1][D]{\ensuremath{\mathcal{#1}}}
\newcommand{\Ld}[1][\D]{\ensuremath{\mathscr{L}\!\!\left(#1\right)}} % utilisation :  \Ld ou \Ld[A] pour un diviseur A au lieu de D
\newcommand{\Ak}[1][k]{\ensuremath{\mathbb{A}_{#1}}}
\newcommand{\A}{\ensuremath{\mathsf{A}}}
\newcommand{\Cl}{\ensuremath{\mathsf{Cl}}}
\newcommand{\mus}{\ensuremath{\mu^\mathsf{sym}}}
\newcommand{\Ms}{\ensuremath{M^\mathsf{sym}}}
\newcommand{\ms}{\ensuremath{m^\mathsf{sym}}}
\newcommand{\chch}{{C}hudnovsky-{C}hudnovsky}
\newcommand{\ch}{{C}hudnovsky}



\addtobeamertemplate{footline}{\texttt{\hfill\insertframenumber/{\inserttotalframenumber}}}
%
%\AtBeginSubsection[] {
%\begin{frame}<beamer>
%\frametitle{Plan}
%\tableofcontents[currentsection,currentsubsection]
%\end{frame}
%}
%\AtBeginSection[] {
%\begin{frame}<beamer>
%\frametitle{Plan}
%\tableofcontents[currentsection]%,currentsubsection]
%\end{frame}
%}

\setbeamertemplate{sections/subsections in toc}[sections numbered]
%\setbeamertemplate{sections in toc}[sections numbered]

\begin{document}

\begin{frame}[plain]

\begin{center}

{\bf Institut de Mathématiques de Marseille}\\

{\bf Equipe Analyse, Géométrie et Topologie (AGT) }\\

\vspace{2em}

{\bf Séminaire de Géométrie Complexe}\\
 Mardi 12 Juin 2018
\end{center}

\begin{center}

 \end{center}
\end{frame}


\begin{frame}[plain]

  \titlepage

\end{frame}



\begin{frame}[plain]{Plan}
  \tableofcontents
\end{frame}


\section{Introduction}


\subsection{Définitions}

%%%%% SLIDE 1
\begin{frame}{Définition formelle I}

Multiplication dans $\Fqn$, le corps fini avec $q^n$ éléments:
$$
\mathsf{m}: \Fqn \times \Fqn \rightarrow \Fqn
$$
%\uncover<2->{
$$
\rotatebox[origin=c]{270}{{\color{mycvblue}$\rightsquigarrow$}}
$$

$$
\mathsf{M}: \Fqn \otimes_{\Fq} \Fqn \rightarrow \Fqn
$$

%}
%\uncover<3->{

$$
\rotatebox[origin=c]{270}{{\color{mycvblue}$\rightsquigarrow$}}
$$

$$
t_\mathsf{m} \in \Fqn^\star \otimes \Fqn^\star \otimes \Fqn
$$
\vspace{5em}

 $\Fqn^\star$: dual de $\Fqn$ sur $\Fq$.\\
 %}

\end{frame}

%%%%% SLIDE 2
\begin{frame}{Définition formelle II}

\begin{block}{}
Si
\begin{equation}
t_\mathsf{m} := \displaystyle\sum_{i=1}^{N}\;a_i^\star \otimes b_i^\star \otimes c_i \label{eqn1}
\end{equation}
où $a_i^\star, b_i^\star \in \Fqn^\star$ et $c_i \in \Fqn$, alors pour tous $x, y \in \Fqn$, on a
\begin{equation}
x y = t_\mathsf{m}(x \otimes y) = \displaystyle\sum_{i=1}^{N}\;a_i^\star(x) b_i^\star(y) c_i \label{eqn2}.
\end{equation}
\justifying
Chaque expression ($\ref{eqn2}$) est appelée un \textbf{algorithme de multiplication bilinéaire de complexité ~$N$}.
\end{block}
\vspace{2em}

\uncover<2->{
\begin{block}{}
Si $a_i^\star = b_i^\star$ pour tout $i$, l'algorithme est \textbf{symmétrique}.
\end{block}
}

\end{frame}


%%%%% SLIDE 3
\begin{frame}{Définition formelle III}

\vspace{-1em}
\begin{defin}
Soit
$$
\mu_q(n) := \min \bigg \{ k \ \Big | \ t_\mathsf{m} = \sum_{i=1}^k a_i^\star \otimes b_i^\star \otimes c_i \bigg \}
$$
la \textbf{complexité bilinéaire de la multiplication dans $\Fqn$ sur $\Fq$}, ou \textbf{rang de tenseur de la multiplication dans $\Fqn$ sur $\Fq$}, \uncover<2->{et
$$
\mus_q(n) := \min \bigg \{ k \ \Big | \ t_\mathsf{m} = \sum_{i=1}^k a_i^\star \otimes a_i^\star \otimes c_i \bigg \}
$$
la \textbf{complexité bilinéaire symétrique de la multiplication dans $\Fqn$ sur $\Fq$}, ou \textbf{rang de tenseur symétrique de la multiplication dans $\Fqn$ sur $\Fq$}.}
\end{defin}
%\vspace{2em}
%
%\uncover<3->{
%\rk \ \ $\displaystyle{\mu_q(n) \leq \mus_q(n)}$
%}

\end{frame}


\subsection{Quantités asymptotiques}

%%%%% SLIDE 6
\begin{frame}

\vspace{-0.5em}
\begin{defin}
On pose:
$$
\Ms_q := \displaystyle \limsup_{n \rightarrow \infty} \frac{\mus_q(n)}{n}
$$
%and
%$$
%\ms_q := \displaystyle \liminf_{n \rightarrow \infty} \frac{\mus_q(n)}{n}.
%$$
\end{defin}
\vspace{0.3em}

%Note that ${\ms_q \leq \Ms_q \leq C_q}$.

%\vspace{1em}
%\uncover<2->{
%\textbf{{\color{mycvblue}Known bounds:}} \\
%\vspace{0.3em}
%\begin{enumerate}[(i)]
%       \item $\displaystyle{\ms_{q^2} \leq 2\left( 1 + \frac{1}{q-3}\right)}$ \hfill  [Chudnovsky, Chudnovsky (1988)]}\\
%       \vspace{0.3em}
%       \uncover<3->{
%       \item $\Ms_2 \leq 18.35$ \hfill [Ballet, P. (2010)]\\ }
%       \vspace{0.3em}
%       \uncover<4->{
%       \item If $q\geq4$, then $\displaystyle{\Ms_q \leq 6 \left(1+ \frac{p}{q-3}\right)} $ \hfill [Ballet (2003)] \\}
%       \vspace{0.3em}\uncover<5->{
%       \item If ${q \geq2,t\geq1}$ are such that $q^t-5>0$, then
%       $$
%       \Ms_{q} \leq \mu_{q}(2t)\frac{(q^t-1)}{t(q^t-5)} \qquad \mbox{ and }
%        \qquad
%       \Ms_{q^2} \leq \mu_{q}(t)\frac{2(q^t-1)}{t(q^t-5)}
%       $$
%       which gives:
%       \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
%       \hline
%       $q$ & 2 & 3 & 4 & 5 & 7 & 8 & 9 & 11 &13 \\
%       \hline
%       $\Ms_q$ & 7.47 & 5.49 & 4.98 & 4.8 & 3.82 & 3.74 & 3.68 & 3.62 & 3.59 \\
%       \hline
%       \end{tabular}
%       \begin{flushright}[Cascudo, Cramer, Xing, Yang (2011)]\end{flushright} }
%       \vspace{1em}
%\end{enumerate}

\vspace{1.5em}

\end{frame}

\section{Algorithme de D.V. et G.V. Chudnovsky (1987)}

\subsection{Avec des places rationnelles}

%%%%% SLIDE 9
\begin{frame}{Algorithme original de Chudnovsky et Chudnovsky}
\vspace{.5em}
Soit
\begin{itemize}
        \item[$\bullet$] $\FF/\Fq$ un corps de fonctions algébriques défini sur $\Fq$,
        \item[$\bullet$]  $Q$ une place de degré $n$,
        \item[$\bullet$] $P_1,\ldots, P_N$, $N$ places distinctes de $\FF/\Fq$ de degré 1,
        \item[$\bullet$] $\D$ un diviseur tel que $\mathsf{supp}\,\D\cap\{Q, P_1, \ldots, P_N\}~=\varnothing$.
\end{itemize}
\vspace{1em}
\uncover<2->{
\begin{block}{}
Si
\begin{enumerate}[(i)]
        \item la première fonction d'évaluation
        $\displaystyle{
        \begin{array}[t]{cccc}
                \mathsf{Ev}_Q : & \Ld{} & \longrightarrow & \mathsf{F}_Q \simeq \Fqn \\
                         & f & \longmapsto & f(Q)
        \end{array}
        }$
        est \textbf{surjective},
        \vspace{1em}
        \item la seconde fonction d'évaluation est \textbf{injective}:
         $$
         \begin{array}[t]{cccl}
                \mathsf{Ev}_{\mathscr{P}} : & \Ld[2\D] & \longrightarrow & \mathbb{F}_q^N \\
                    & f & \longmapsto & \big(f(P_1),  \ldots, f(P_N)\big)
        \end{array}
        $$

 \end{enumerate}
 \vspace{1.5em}

alors
$$
\mus_q(n) \leq N.
$$
\end{block}
}
\vspace{3mm}

\end{frame}

\subsection{Principe}

%%%%% SLIDE 8
\begin{frame}{Principe pour multiplier avec l'algorithme de Chudnovsky}

\vspace{1.5em}

\hspace{-2.5em}
$
\begin{array}[c]{cccl}
\hspace{-2em}\uncover<3->{       & \mathcal{O}_Q}&\uncover<3->{\xtwoheadrightarrow[]{ \hspace{4em} \pi_Q \hspace{4em} } } & \uncover<2->{ \mathsf{F}_Q } \\
         \uncover<3>{Q \notin \mathsf{supp}\; \D} & \uncover<3->{\cup} & & \; \uncover<2->{ \hspace{-0.3em}\shortparallel \ \\ }
         \uncover<1,2>{\mathsf{Ev}_Q :} & \Ld{} & \xtwoheadrightarrow[]{ \uncover<3->{\hspace{1.6em} \mathsf{Ev}_Q = {\pi_Q}_{|\Ld{}} \hspace{1.6em}} } &  \Fqn \\
         & & & \uncover<2->{\rotatebox[origin=c]{90}{$\in $}} \\
\uncover<4->{ & f & \dotarrow{\hspace{12.7em}  } } & \uncover<2->{x} \uncover<4->{ = f(Q) \\ }
\uncover<5->{ & g & \dotarrow{\hspace{12.7em}  } } & \uncover<2->{y} \uncover<5->{= g(Q) \\ }
         %\uncover<1,2>{\mathsf{Ev}_Q :} & &  & \\
         %& & & \\
         %& & & \\
          \uncover<1,2>{\mathsf{Ev}_\mathscr{P} :}  & \Ld[2\D] & \xhookrightarrow{\hspace{4.2em}\mathsf{Ev}_\mathscr{P}  \hspace{4.2em}}  & \mathsf{F}_{P_1} \times \cdots \times \mathsf{F}_{P_N} \simeq\Fq^N  \\
         & & & \\
  \uncover<6->{ & f }& \uncover<7->{  \xmapsto{\hspace{10em}  } & \big( f(P_1), \ldots, f(P_N)\big)}\\
      \uncover<6->{ & g }& \uncover<7->{  \xmapsto{\hspace{10em}  } & \big( g(P_1), \ldots, g(P_N)\big)\\ }
         & & & \\
            &  \uncover<9->{fg \ \ & \dotarrow{\hspace{12.7em}  } }&\uncover<8->{ \big( {\color<11>{mycvblue}f(P_1)g(P_1)}, {\color<11>{mycvblue}\ldots}, {\color<11>{mycvblue}f(P_N)g(P_N)}\big)}\\
                % & & &\\
                  & \uncover<10->{\longdownmapsto\hspace{2.5em}}& &  \hspace{6em} {\color<11>{mycvblue}  \uncover<11->{\rotatebox[origin=c]{-90}{$\leadsto$}}}    \\
                 & & &{\color<11>{mycvblue}  \uncover<11->{\mbox{N mult. \textbf{bilinéaires} dans $\Fq$ }}}  \\
         &  \uncover<10->{\ \ (fg)(Q) & = f(Q)g(Q) = xy \  \ \ \ } &  \\
\end{array}
$

\end{frame}

\subsection{Avec des places de degré un et deux}

%%%%% SLIDE 10
\begin{frame}{Evaluations sur des places de degré 1 et 2}

\vspace{.1em}
Soit
\begin{itemize}
        \item[$\bullet$] $\FF/\Fq$ un corps de fonctions algébriques défini sur $\Fq$,
        \item[$\bullet$]  $Q$ une place de degré $n$,
        \item[$\bullet$] $P_1,\ldots, P_{N_1}$, $N_1$ places distinctes de $\FF/\Fq$ de degré 1,
        \item[$\bullet$] $S_1,\ldots, S_{N_2}$ $N_2$ places distinctes de $\FF/\Fq$ de degré 2,
        \item[$\bullet$] $\D$ un diviseur tel que $\mathsf{supp}\,\D\cap\{Q, P_1, \ldots, P_{N_1},S_1,\ldots,S_{N_2}\}~=\varnothing$.
\end{itemize}
\vspace{.1em}
\uncover<2->{
\begin{block}{}
Si
\begin{enumerate}[(i)]
        \item la première fonction d'évaluation
        $\displaystyle{
        \begin{array}[t]{cccc}
                \mathsf{Ev}_Q : & \Ld{} & \longrightarrow & \mathsf{F}_Q \simeq \Fqn \\
                         & f & \longmapsto & f(Q)
        \end{array}
        }$
        \vspace{1em}
        est \textbf{surjective},
        \item la seconde fonction d'évaluation est  \textbf{injective}:
         $$
         \begin{array}[t]{cccl}
                \mathsf{Ev}_{\mathscr{P}} : & \Ld[2\D] & \longrightarrow & \F_q^{N_1} \times \F_{q^2}^{N_2} \\
                    & f & \longmapsto & \big(f(P_1), \ldots, f(P_{N_1}), f(S_1), \ldots, f(S_{N_2})\big)
        \end{array}
        $$

 \end{enumerate}

 \vspace{.1em}

alors
$$
\mus_q(n) \leq \displaystyle N_1 + \underbrace{3}_{\mu_q(2)}N_2.
$$
 \end{block}
 }

\end{frame}


\section{Conditions permettant l'utilisation de l'algorithme}

\subsection{Conditions principales}

%%%%% SLIDE 11
\begin{frame}{Conditions suffisantes pour appliquer l'algorithme}

\begin{theoreme}[B. (1999), B., Pieltant, Rambaud, et Sisjling (2017)]
\justify
Soit $\FF/\F_q$ un corps de fonctions algébriques de genre $g$.
Soit $N_k$ le nombre de places de degré $k$ dans $F/\F_q$.\\
Si $\FF/\F _q$ est tel que $2g+1 \leq q^{\frac{n-1}{2}}(\sqrt{q}-1)$ alors:
\begin{enumerate}[1)]
        \uncover<2->{
        \item si $N_1 > 2n+2g-2$, alors
                $$
                \mus_q(n) \leq 2n+g-1,
                $$}
                \uncover<3->{
        \item si il existe un diviseur non-spécial de degré $g-1$ et ${N_1+2N_2>2n+2g-2}$, alors
                $$
                \mus_q(n)\leq 3n+2g,
                $$
                }
%               \uncover<4->{
%       \item if $N_1+2N_2>2n+4g-2$, then
%               $$
%               \mus_q(n)\leq 3n+6g.
%               $$}
\end{enumerate}
\end{theoreme}
\uncover<5->{
\vspace{1em}

{\bf Objet "géométrico-algébrique" pertinent:}

\vspace{.1em}

$---->$ \textbf{corps de fonctions avec beaucoup de places} (rationnelles ou de degré deux) relativement à leur genre.}

\end{frame}

\subsection{Applications}

%%%%% SLIDE 11
\begin{frame}{Le cas des extensions de petits degré}

\begin{theoreme}[Winograd et de Groote (1979, 1983)]
La complexité bilinéaire de la multiplication dans $\Fqn$ sur $\Fq$ satisfait
$$
 \mu_q(n) \geq 2n-1.
$$
De plus,
$$
\mus_q(n) = 2n-1\  \   \Longleftrightarrow \  \   n \leq \frac{q}{2}+1.
$$
\end{theoreme}
\vspace{1.5em}

\begin{theoreme}[Shokrollahi (1992), Chaumine (2004)]

Si $\displaystyle{n \leq \frac{1}{2}\left(q+1+\epsilon(q)\right)}$, alors
$$
\mus_q(n) \leq 2n
$$
où
$
\epsilon(q) = \left\{
    \begin{array}{l}
         2\sqrt{q} \mbox{ si }q\mbox{ est un carré parfait,} \\
         \mbox{le plus grand entier inférieur ou égal à } 2\sqrt{q}\mbox{ co-premier avec } q \mbox{ sinon.}
    \end{array}
\right.
$
\end{theoreme}

\end{frame}


\begin{frame}{Algorithme de Chudnovsky sur un corps de fonctions hyperelliptique de genre 2}
%\vspace{-3em} \chch~

Soit $\FF/\Fqr{2}=\F_{16}(x,y) \qquad \mbox{ où } \quad y^2+y =x^{5}$\\

\vspace{1em}

Alors
${\qquad g(\FF) = 2 \quad \mbox{ et } \quad N_1(\FF) = q^2+1 + 2g(\FF)q =  33.}$\\
\vspace{2.5em}

\uncover<2->{
\begin{block}{}
Si \qquad
$\displaystyle{
N_1 \geq 2n +2g-1 \qquad \mbox{ i.e. } \qquad n \leq \frac{1}{2}(N_1-2g+1)
}$\\
\vspace{0.8em}
\justifying
alors on peut appliquer l'algorithme de Chudnovsky sur le corps de fonctions algébriques ~$\FF/\Fqr{2}$ pour multiplier dans ~$\Fqr{2n}$.\\
\end{block}
%\chch~
}
\vspace{1.8em}

\uncover<3,4->{
{\color{mycvblue}\textbf{Conséquence:}} multiplication dans des extensions de degré $n$ de $\F_{16}$.% $\F_{{16}^n} / \F_{16}$.
%\vspace{0.5em}
$$
\left.
\begin{array}{l}
g(\FF/\F_{16}) =2 \\
N(\FF/\F_{16}) = 33
\end{array}\right\}
\leadsto
\begin{array}{c}
\\
        \mbox{si $n\leq 15$, on a un algorithme de multiplication}\\ \mbox{dans $\F_{16^n}$ à partir de ${\FF/\F_{16}}$, de complexité} \\  \mu_q(n) \leq   \alt<3>{2n +g(\FF) -1.}{2n +1.}
\end{array}
$$
}
\vspace{0.7em}
\end{frame}


\begin{frame}{Exemple pour les \textit{petites} extensions $\F_{16^n}$ de $\F_{16}$}

\setlength{\unitlength}{1cm}
\begin{picture}(7,6)(-3,0)


  \put(0,-1){\vector(0,1){7.5}}
  \put(-0.1,6.7){$n$}% degré de l'extension de $\F_{16}$} % legend top flèche
   \put(-0.2,-0.78){\line(1,0){0.4}}
   \put(-0.4,-0.88){1}


\uncover<2->{
    \put(-0.2,1.2){\line(1,0){0.4}}
     \put(-1.95,1.1){$\frac{1}{2}q^2+1=9$}
   \put(0.4,0.115){$\left \}  \begin{array}{c} \\  \mbox{évaluations sur } \mathsf{P}^1(\F_{16})\\  \\   \mus_{q^2}(n) = 2n-1\\ \\ \end{array}\right.$}
     \put(7.5,0.16){\color{mycvblue}$(g=0)$}
}


 \uncover<3->{
    \put(-0.2,1.86){\line(1,0){0.4}}
    \put(-3.4,1.76){$\left[\frac{1}{2}(q^2+1+2q)\right]=12$}
    \put(0.42,1.45){$\left \}  \begin{array}{c}  \mbox{évaluations sur une courbe sur  $\F_{16}$}\\ \mbox{avec $2n$ points rationnels:  $\mus_{q^2}(n) = 2n$}\end{array}\right.$}
    \put(7.5,1.45){\color{mycvblue}$(g=1)$}
}


\uncover<4->{
  \put(-0.2,5.6){\line(1,0){0.4}}
 \put(-3.7,5.5){$\frac{1}{2}(q^2+4q-2)=15$}
    \put(0.4,3.68){$\left \}  \begin{array}{c} \\  \\ \\  \mbox{évaluations sur une courbe hyperelliptique sur  $\F_{16}$} \\  \mbox{avec $2n+2g-1$ points rationnels:}\\ \mus_{q^2}(n) \leq 2n+1\\  \\      \\ \\ \end{array}\right.$}
      \put(7.5,3.68){\color{mycvblue}$(g=2)$}

}

\uncover<5->{
 \put(0.9,5.85){{\color{mycvblue} $\fbox{$\begin{array}{c} \\ n\leq \frac{1}{2}(N-2g+1) \quad  \Longrightarrow \quad \mus_q(n) \leq 2n +g -1\\ \\ \end{array}$}$}}
}


\end{picture}

\end{frame}

\setbeamercovered{transparent}
\begin{frame}

\justifying
%Application de l'algorithme sur une \textbf{suite asymptotiquement bonne de corps de fonctions} :

Application de l'algorithme sur \textbf{une bonne famille asymptotiquement de corps de fonctions algébriques :}

\begin{theoreme}[\ch$^2$(1987), Shparlinski-Tsfasman-Vladut (1992), B.~(1999)]
Soit $q=p^r$ avec $p$ un nombre premier et $r$ un entier. Alors il existe une constante $C_q$ telle que pour tout $n$,
$$
\mus_q(n) \leq C_q n.
$$
\end{theoreme}

%\visible<2,3>{
%\vspace{2em}
%{\color{mycvblue}\textbf{Objectifs.}}
%\begin{itemize}
%       \item[$\bullet$] \'Etablir des bornes théoriques :
%               \begin{itemize}
%                       \uncover<1,2>{\item[$\bullet$] améliorer l'algorithme: évaluations sur des places de degré supérieur, dissymétrisation (Randriambololona 2012)…}
%                       \item[$\bullet$] démontrer l'existence de corps de fonctions avec de meilleures propriétés
%               \end{itemize}
%\uncover<1,2>{ \item[$\bullet$] Construire des algorithmes explicites pour la multiplication dans $\Fqn$, pour $n$ choisi.}
%\end{itemize}
%}

\end{frame}



%%%%%%%%%%%%% T  %%%%%%%%%%%%%%%


%%%%%%%%%%%%% T  %%%%%%%%%%%%%%%

%\begin{frame}
%
%\begin{Theorem}\label{lemmek0}
%Let $l_k$ be the $k$-th prime number. Then there exists a real number $\alpha<1$ such that the difference between two consecutive prime numbers $l_k$ and $l_{k+1}$ satisfies
%$$l_{k+1}-l_k\leq l_k^{\alpha}$$ for any prime $l_k\geq x_{\alpha}.$
%
%In particular, one can take $\alpha=\frac{21}{40}$ with the value of $x_{\alpha}$ that can in principle be determined effectively, or $\alpha=\frac{2}{3}$ with $x_{\alpha}=\exp(\exp(33.3)).$
%\end{Theorem}
%
%
%\end{frame}

%%%%%%%%%%%%% T  %%%%%%%%%%%%%%%

\section{Nouveau résultats}

\subsection{Bornes uniformes connues}

\begin{frame}

\begin{theoreme}\label{theo_arnaudupdate}
  Soit ${q=p^r}$ une puissance d'un premier $p$ et $n$ un entier $>1$. Alors:
  \begin{enumerate}[(i)]
   %\item If ${q=2}$, then $\displaystyle{\mus_{q}(n) \leq 15.46n}$ (cf. \cite[Corollary 29]{bapi2} and \cite{ceoz})
  % \item If ${q=3}$, then $\displaystyle{\mus_{q}(n) \leq  7.732 n}$ (cf. \cite[Corollary 29]{bapi2} and \cite{ceoz})
    \item Si ${q\geq 4}$, alors $\displaystyle{\mus_{q}(n) \leq 3 \left(1 +
      \frac{\frac{4}{3}p}{q-3+2(p-1)\frac{q}{q+1}} \right)n}$  (cf. [2])
    \item  Si $p\geq5$, alors  $\displaystyle{\mus_{p}(n) \leq  3\left(1+
      \frac{8}{3p-5}\right)n}$  (cf. [2])
      \item Si ${q\geq 4}$, alors  $\displaystyle{\mus_{q^2}(n) \leq 2 \left(1 +
      \frac{p}{q-3 + (p-1)\frac{q}{q+1}} \right)n}$  (cf. [1] and [2])
       \item Si $p\geq5$, alors  $\displaystyle{\mus_{p^2}(n) \leq 2 \left(1 +
      \frac{2}{p-\frac{33}{16}} \right)n}$  (cf. [2])
  \end{enumerate}
\end{theoreme}

[1] Arnaud, 2006.

\vspace{1em}

[2] B., Pieltant, Rambaud et Sisjling, 2017.

\end{frame}


\subsection{Nouvelles bornes uniformes}

\begin{frame}

\begin{proposition}[B. et Zykin (2017)]
Soit $p\geq 5$ un nombre premier.
%and let $x_{\alpha}$ be the constant from Theorem \ref{lemmek0}.
%\ref{lemmek0}.

\begin{enumerate}
\item Si $p\neq 11,$ alors pour tout entier $ n\geq \frac{p-3}{2}x_\alpha+\frac{p+1}{2}$:
%$$\Ms_{q^2}\leq 2\left(1+\frac{1}{q-3}\right).$$
$$
\mus_{p^2}(n) \leq 2\left(1+\frac{1+\epsilon_p(n)}{p-3}\right)n-\frac{(1+\epsilon_p(n))(p+1)}{p-3} - 1,
$$
où $\epsilon_p(n)=\left(\frac{2n}{p-3}\right)^{\alpha-1},$ $\alpha=\frac{2}{3}$ avec $x_{\alpha}=\exp(\exp(33.217)).$

\item Si $p=11$ et $ n\geq (p-3)x_\alpha+p-1=8x_\alpha+10$:
$$
\mus_{p^2}(n) \leq 2\left(1+\frac{1+\epsilon_p(n)}{p-3}\right)n-\frac{2(1+\epsilon_p(n))(p-1)}{p-3},
$$
où $\epsilon_{p}(n)=\left(\frac{n}{p-3}\right)^{\alpha-1},$ $\alpha=\frac{2}{3}$ avec $x_{\alpha}=\exp(\exp(33.217)).$

%\item Asymptotically the following inequality holds for any $p\geq 5$:
\item Asymptotiquement, pour tout $p\geq 5$:
$$
\Ms_{p^2} \leq 2\left(1+\frac{1}{p-3}\right).
$$
\end{enumerate}
\end{proposition}

\end{frame}


%%%%% SLIDE 14
\begin{frame}{Corps de fonctions sur $\F_{p^2}$}

\textbf{Preuve: idées principales}\\

\textbf{Courves modulaires:} $\qquad  \displaystyle{\mathsf{X}_0(N) := \Gamma_0(N) \backslash \mathfrak{h} \mbox{, pour }N \in \NN^*}$\\
\vspace{1.5em}

où \\
$\displaystyle{
\left\{
\begin{array}{rcl}
\mathfrak{h} & = & \big\{z\in \CC \ | \ Im(z)>0\big\}\\
& & \\
\Gamma_0(N) & = & \left\{
\begin{pmatrix}
a & b \\
c & d
\end{pmatrix} \in \mathsf{SL}_2(\ZZ) \ \Big\vert \ c \equiv 0 \pmod{N}
\right\}
\mbox{ \ "sg. de congruence"}
\end{array}
\right.}$

\vspace{.5em}

\underline{Pour  $p\neq 11:$}

\vspace{.5em}

%\uncover<2->{
On utilise la famille de corps de fonctions $\FF_{k}/\F_{p^2}$ associés aux courbes  $\mathsf{X}_k := \mathsf{X}_0(11\ell_k)$ avec $\ell_k$ le $k$ième nombre premier, qui satisfait pour chaque $k$:

\begin{enumerate}
        \item[$\bullet$] $g(\FF_{k}) = \ell_{k}$,
        \item[$\bullet$] $N_1(\FF_{k}/\F_{p^2}) \geq (p-1)(\ell_{k}+1)$.
\end{enumerate}

\vspace{.5em}

\underline{Pour  $p=11$:} %Idem but with $\mathsf{X}_k := \mathsf{X}_0(23\ell_k)$, $g(\FF_{k}) = 2\ell_{k}+1$, $N_1(\FF_{k}/\F_{p^2})) \geq 2(p-1)(\ell_{k}+1)$

\vspace{.5em}

 Idem mais avec $\mathsf{X}_k := \mathsf{X}_0(23\ell_k)$, $g(\FF_{k}) = 2\ell_{k}+1$, $N_1(\FF_{k}/\F_{p^2}) \geq 2(p-1)(\ell_{k}+1)$
%}
%\uncover<3->{
%Thus we get for each \textit{sufficiently large} integer $n$, a function field which satisfies the conditions allowing the use of the algorithm.
%}

\end{frame}

\begin{frame}

En conséquence, on obtient pour chaque entier entier \textit{{\bf suffisamment grand}} $n$, un corps de fonctions qui satisfait les conditions permettant l'utilisation de l'algorithme.

\vspace{.5em}

{\bf Théorème de densité des nombres premiers de type Hoheisel}

\vspace{.5em}

\begin{theoreme}[Baker, Harman et Pintz (2001), Dudek (2016)]\label{lemmek0}
Soit $l_k$ le $k$-ième nombre premier. Alors il existe un nombre réel $\alpha<1$ tel que la différence entre deux nombres premiers consécutifs $l_k$ et $l_{k+1}$ satisfait
$$l_{k+1}-l_k\leq l_k^{\alpha}$$ pour tout premier $l_k\geq x_{\alpha}.$

En particulier, on peut prendre $\alpha=\frac{21}{40}$ avec la valeur de $x_{\alpha}$ qui peut {\bf "en principe"} être déterminée effectivement, ou $\alpha=\frac{2}{3}$ avec $x_{\alpha}=\exp(\exp(33.217)).$
\end{theoreme}

\end{frame}

%%%%%%%%%%%%% T  %%%%%%%%%%%%%%%

\begin{frame}

\begin{proposition}[B. et Zykin (2017)]
Soit $p\geq 5$ un nombre premier.
%, let $x_{\alpha}$ be defined as in Theorem \ref{lemmek0}, and $\epsilon_p(n)$ as in Proposition above.

\begin{enumerate}
\item Si $p\neq 11,$ alors pour tout entier $ n\geq \frac{p-3}{2}x_\alpha+\frac{p+1}{2}$:
%$$\Ms_{q^2}\leq 2\left(1+\frac{1}{q-3}\right).$$
$$
\mus_{p}(n) \leq 3\left(1+\frac{\frac{4}{3}(1+\epsilon_p(n))}{p-3}\right)n-\frac{2(1+\epsilon_p(n))(p+1)}{p-3}.
$$
où $\epsilon_p(n)=\left(\frac{2n}{p-3}\right)^{\alpha-1},$ $\alpha=\frac{2}{3}$ avec $x_{\alpha}=\exp(\exp(33.217)).$
%where $\ds\epsilon_p(n)=\left(\frac{2n}{p-3}\right)^{\alpha-1}.$

\item Si $p=11$ et $ n\geq (p-3)x_\alpha+p-1=8x_\alpha+10$:
$$
\mus_{p}(n) \leq 3\left(1+\frac{\frac{4}{3}(1+\epsilon_p(n))}{p-3}\right)n-\frac{4(1+\epsilon_p(n))(p-1)}{p-3}+1.
$$
où $\epsilon_{p}(n)=\left(\frac{n}{p-3}\right)^{\alpha-1},$ $\alpha=\frac{2}{3}$ avec $x_{\alpha}=\exp(\exp(33.217)).$
%where $\ds\epsilon_{p}(n)=\left(\frac{n}{p-3}\right)^{\alpha-1}.$

%\item Asymptotically the following inequality holds for any $p\geq 5$:
\item Asymptotiquement, pour $p\geq 5$:
$$
\Ms_{p} \leq 3\left(1+\frac{\frac{4}{3}}{p-3}\right).
$$
\end{enumerate}
\end{proposition}

\end{frame}

\begin{frame}

\textbf{Preuve: idées principales}

\vspace{1em}

\textbf{Descente de courbes modulaires sur le corps de définition $\F_p$:}

\vspace{1em}

Soit $\FF_{0}(N)$ le corps de fonctions algébriques associé à la courbe $\mathsf{X}_0(N)$:

\vspace{1em}

$$\qquad  \FF_0(N)=\FF_0(N)/\F_p\otimes \F_{p^2}$$

\vspace{1em}

$\FF_0(N)/\F_p$:

\vspace{1em}

\begin{enumerate}
        \item[$\bullet$] $g(\FF_0(N)/\F_p) = g(\FF_0(N))$
        \item[$\bullet$] $N_1(\FF_{0}(N)/\F_{p^2}) = N_1(\FF_{0}(N)/\F_{p})+2N_2(\FF_{0}(N)/\F_{p})$.
\end{enumerate}

\vspace{1em}

{\bf Algorithme généralisé de type Chudnovsky avec des places de degré deux}

\vspace{.5em}

{\bf Théorème de densité des nombres premiers de type Hoheisel}


\vspace{1em}


\end{frame}

\section{Conclusions et perspectives}

\subsection{Problèmes et/ou travail en cours}

%%%%% SLIDE 15

\begin{frame}{Conclusion}

\vspace{-1em}

\vspace{1em}

{\bf Projet (suite)}

\vspace{.5em}

1) Expliciter le théorème de densité des nombres premiers de Baker-Harman-Pintz:

\vspace{.5em}

$--->$ Déterminer de manière effective $x_{\alpha}$ pour le meilleur $\alpha$ connu i.e. $\alpha=\frac{21}{40}$.

\vspace{.5em}

Commentaires de {\bf Sary Drapeau} et {\bf Olivier Ramaré}: $$"\hbox{{\bf Hautement non trivial}}".$$

\vspace{.5em}

2) Généraliser les bornes uniformes "obtenues à partir des courbes modulaires"  pour les corps finis $\F_{p^2}$
et $\F_{p}$ aux corps finis $\F_{q^2}$ et $\F_{q}$ où $q=p^r$ avec $r>1$:

 \vspace{.5em}

$--->$ Objectif principal de notre projet avec {\bf Alexey Zykin}, commencé en Avril 2017 à Tahiti.

 \vspace{.5em}

Commentaires d'{\bf Alexey}: {\bf "C'est maintenant que le vrai travail commence!"}

% Alexey said to me "It's now that the true work begin!" and he was pleased because the ingredients of this work seemed to be both analytic number theory and algebraic geometry

\vspace{.5em}

\end{frame}

\begin{frame}
\justify

%Pour avoir {\bf une famille de corps de fonctions définis sur $\F_{q^2}$} (avec ${q=p^m}$ et ${m>1}$) et de {\bf densité comparable} à celle utilisant les courbes modulaires, on a besoin d'une {\bf généralisation des courbes modulaires}, à savoir {\bf les courbes de Shimura}. Ces courbes doivent être définies sur un corps de nombres, extension abélienne totalement réelle de ${\mathbb Q}$ de degré $m$, où $p$ est inerte.

- une famille de corps de fonctions {\bf  définis sur $\F_{q^2}$} (avec ${q=p^m}$ et ${m>1}$)

\vspace{.5em}

- {\bf suffisamment dense}

\vspace{.5em}

$--->$  généralisation des courbes modulaires: {\bf les courbes de Shimura}

%To have function fields over $\F_{q^2}$ when ${q=p^m}$ with ${m>1}$, we need a {\bf generalization of modular curves}, namely Shimura curves which are defined over a totally real abelian over ${\mathbb Q}$ number field of degree $m$, where $p$ is inert.

\vspace{2em}
%\uncover<2->{
\textbf{Courbes de Shimura :} {\it Asymptotiquement} (Shparlinski-Tsfasman-Vladut) (1992)

\vspace{0.5em}

$\qquad \displaystyle{\mathsf{X}_\ell(\CC) := \Gamma_\ell\backslash\mathfrak{h}\mbox{, pour $\ell$ un nombre premier {\bf "suffisamment grand''} (?)}}$\\
\vspace{0.5em}
\indent où $\Gamma_\ell$ est un sous-groupe d'indice $\ell$ de $\Gamma$, le groupe des unités d'un ordre maximal
$\mathcal{O}$ d'une algèbre des quaternions $B$.\\
%}
\vspace{1em}
%\uncover<3->{
On utilise la famille des corps de fonctions $\FF_{k}/\F_{q^2}$ associés aux courbes $\mathsf{X}_{\ell_k,p}$
qui sont la réduction des $\mathsf{X}_{\ell_k}$ modulo $p$, avec $\ell_k$ le $k$-ième nombre premier.
%\\}
\vspace{1em}

%\uncover<4->{
Chaque $\FF_k/\F_{q^2}$ satisfait:

\vspace{0.7em}

\begin{enumerate}
        \item[$\bullet$] $g(\FF_{k}) = 1+\ell_{k}(g-1)$
        \item[$\bullet$] $N_1(\FF_{k}/\F_{q^2}) \geq \ell_{k}(q-1)(g+1)$
\end{enumerate}
\vspace{0.7em}
avec $g$ le genre de  $\mathsf{X}_{\Gamma,p}(\F_{p^2})$, la réduction modulo $p$
de la courbe de Shimura associée à $\Gamma$.
%}

\vspace{2em}

\end{frame}

%\section{Conclusions et perspectives}
%
%
%\begin{frame}
%
%\vspace{1em}
%
%\subsection{Open problems and/or in work in progress}
%
%\underline{Les problèmes ouverts et en cours de traitement :} \\
%
%
%\begin{itemize}
%\item[$\bullet$]  {\it \bf Amélioration  des constantes $C_q$}
%
%$$\hbox{-----$>$ {\bf Dans le cas général:} }$$
%
%- Utilisation de familles de courbes plus denses qu'une tour:
%courbes modulaires, de Shimura (travail en cours avec Alexey Zykin).
%
%\vspace{.5em}
%
%- Utilisation de familles de courbes ayant bcp de diviseurs non-spéciaux de degré $g-1$ et peu de points de 2-torsion.
%
%
%$$\hbox{-----$>$ {\bf Sur les petits corps:} }$$
%
%
%- Existence des diviseurs non-spéciaux de degré $g-1$ dans des tours de corps de fonctions non-ordinaires définis sur $\F_2$ et $\F_3$
%(travail en cours avec Julia Pieltant).
%
%
%\end{itemize}
%
%\end{frame}
%
%\begin{frame}
%
%\vspace{1em}
%
%
%\begin{center}
%MERCI BEAUCOUP POUR VOTRE ACCUEIL
%\end{center}
%
%\end{frame}
%

% \begin{frame}[plain]
% \begin{center}
% \includegraphics[height=2cm]{thu_zykin}
% \end{center}
%\end{frame}

%%%%% SLIDE DE FIN

%\begin{frame}[plain]
% \begin{beamerboxesrounded}%
%       [lower=block title, %
%       upper=block title,%
%       shadow=true]{}
%       \begin{center}
% {\Large  \textbf{{\color{mycvblue}Thank you for your attention.}}}\\
% \vspace{3em}
%  {\Large  \textbf{{\color{mycvblue}Questions?}}}\\
% \end{center}
% \end{beamerboxesrounded}
%
%\end{frame}

\section{Hommage à Alexey}
\begin{frame}[plain]
 \begin{beamerboxesrounded}%
       [lower=block title, %
       upper=block title,%
       shadow=true]{}
       \begin{center}
 {\Large  \textbf{{\color{mycvblue}A la Mémoire de mon Ami \\ \vspace{2em} {\bf Alexey Zykin}}}}\\
 \vspace{1em}
  %{\Large  \textbf{{\color{mycvblue}Questions?}}}\\
  \includegraphics[height=2cm]{thu_zykin}
  \end{center}
  \vspace{1em}
 \end{beamerboxesrounded}

\end{frame}

% 1. "Everything is good at home, there is nothing to throw out."
% ou plutôt chez lui est "at HIS home", mais c'est maladroit.

% 2. "Everything is good at his place, there is nothing to throw out."
%Le "at his place" is plus familier.


%Mais en français poetique, "chez lui" peut dire quelque chose plus générale,
%comme "autour de lui". On peut éventuellement le traduire ce sens par :
% 3. "Everything he does is good, there is nothing to throw out."

%This was what caracterized our friend Alexey Zykin


\end{document}