1 \documentclass[9pt,blackandwhite,roman,handout
]{beamer
}
4 \usefonttheme{professionalfonts
}
11 %\usecolortheme{seahorse}
13 \usecolortheme{seagull
}
14 %\usefonttheme[onlylarge]{structurebold}
15 %\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
16 %\setbeamertemplate{navigation symbols}{}
21 %\usepackage[frenchb]{babel}
22 %\usepackage[english]{babel}
23 \usepackage[utf8
]{inputenc}
24 %\usepackage[T1]{fontenc}
26 \usepackage[sans
]{dsfont
}
30 \usepackage[cal=euler,scr=rsfso
]{mathalfa
}%bb=cm,
33 \usepackage{mathrsfs
} % pour faire des majuscules calligraphiées \mathcal{blabla}
34 %\usepackage[french,lined]{algorithm2e} % rajouter linesnumbered dans les arguments pour numéroter les lignes des algos, boxed pour l'encadrement
35 %\usepackage{extsizes}
36 %\usepackage{MnSymbol}
43 %\usepackage[varg]{txfonts}
46 %\usepackage{MyMnSymbol}
49 %usepackage{mathtools}
57 \usetikzlibrary{matrix,arrows
}
58 \tikzstyle{block
}=
[draw opacity=
0.7,line width=
1.4cm
]
60 \newcommand{\gk}{$g_k =
\left \
{ \begin{array
}{ll
}
61 q^k+q^
{k-
1}-q^
\frac{k+
1}{2} -
2q^
\frac{k-
1}{2}+
1 &
\mbox{si
} k
\equiv 1 \pmod 2,\\
62 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.
63 \end{array
} \right .$
}
65 \newcommand{\ext}{\xymatrix{
66 \FF=
\Fq(x)(y)
\ar@
{-
}[d
]^
{<
\infty} \\
\Fq(x)
\ar@
{-
}[d
] \\
\Fq} }
68 \newcommand{\twoheaddownarrow}{%
69 \mathrel{\reflectbox{\rotatebox[origin=c
]{-
90}{$
\xtwoheadrightarrow[ \;
]{ \reflectbox{\rotatebox[origin=c
]{-
90}{$
\pi_Q \ $
}} \ \
}$
}}}}
71 \newcommand{\longdownmapsto}{%
72 \mathrel{\reflectbox{\rotatebox[origin=c
]{-
90}{$
\xmapsto{ \ \ \
\reflectbox{\rotatebox[origin=c
]{-
90}{$
\pi_Q \ $
}} \ \ \
}$
}}}}
74 \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{}}_?
}
76 \newcommand{\myubrace}[2]{\rotatebox[origin=c
]{90}{$
77 \rotatebox[origin=c
]{-
90}{#1} \left \
{
81 \right .
\hspace{-
1em
}
84 \newcommand{\bluebrace}{{\color{blue
}\left\
{}}
87 \definecolor{mycvblue
}{rgb
}{0.302,
0.537,
0.737}
90 \setbeamercolor{structure
}{fg=mycvblue
}
91 \setbeamercolor{palette primary
}{fg=mycvblue
}
92 \setbeamercolor{subsection in head/foot
}{parent=palette primary
}
94 \setbeamertemplate{navigation symbols
}{
95 % \insertslidenavigationsymbol
96 % \insertframenavigationsymbol
97 % \insertsubsectionnavigationsymbol
98 % \insertsectionnavigationsymbol
99 % \insertdocnavigationsymbol
100 % \insertbackfindforwardnavigationsymbol
103 %\renewcommand{\item}{\item[$\bullet$]}
107 \title[]{\LARGE{\textsc{Familles denses de courbes modulaires, nombres premiers\\ et \
\rang de tenseur symétrique uniforme de la multiplication dans les corps finis
}}}
109 \author[Alexey
{\textsc Zykin
}]{\textbf{Alexey
{\textsc Zykin
}$^
{\dag}$
} \\ (
\textbf{1984 -
2017}) \
\Laboratoire GAATI \
\Université de la Polynésie Française\\
110 {\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é
}
113 \date[]{\\
\vspace{2em
} {\bf Séminaire GAATI
}\\
{\bf UPF
} \\
{\small Avril
2017}}
115 \newtheorem{defin
}{Définition
}
116 \newtheorem{theoreme
}{Théorème
}
117 \newtheorem{lemme
}{Lemme
}
118 \newtheorem{corollaire
}{Corollaire
}
119 \newtheorem{proposition
}{Proposition
}
120 \newtheorem{propriete
}{Propriété
}
121 %\newtheorem{exemple}[definition]{Exemple}
123 \newcommand{\NN}{\ensuremath{\mathbb{N
}}}
124 \newcommand{\CC}{\ensuremath{\mathbb{C
}}}
125 \newcommand{\ZZ}{\ensuremath{\mathbb{Z
}}}
126 \newcommand{\PF}{\mathbf{P
}_F
}
127 \newcommand{\DF}{\mathsf{Div
}(F)
}
128 \newcommand{\Jac}{\ensuremath{\mathcal{J
}\mathsf{ac
}(F/
\Fq)
}}
129 \newcommand{\Fqr}[2][q
]{\mathds{F
}_
{\!
{#1}^
{#2}}}
130 \newcommand{\Fq}{\Fqr{}}
131 \newcommand{\F}{\mathds{F
}}
132 \newcommand{\FF}{\mathsf{F
}}
133 \newcommand{\Fqn}{\Fqr{n
}}
134 \newcommand{\D}[1][D
]{\ensuremath{\mathcal{#1}}}
135 \newcommand{\Ld}[1][\D]{\ensuremath{\mathscr{L
}\!\!
\left(
#1\right)
}} % utilisation : \Ld ou \Ld[A] pour un diviseur A au lieu de D
136 \newcommand{\Ak}[1][k
]{\ensuremath{\mathbb{A
}_
{#1}}}
137 \newcommand{\A}{\ensuremath{\mathsf{A
}}}
138 \newcommand{\Cl}{\ensuremath{\mathsf{Cl
}}}
139 \newcommand{\mus}{\ensuremath{\mu^
\mathsf{sym
}}}
140 \newcommand{\Ms}{\ensuremath{M^
\mathsf{sym
}}}
141 \newcommand{\ms}{\ensuremath{m^
\mathsf{sym
}}}
142 \newcommand{\chch}{{C
}hudnovsky-
{C
}hudnovsky
}
143 \newcommand{\ch}{{C
}hudnovsky
}
147 \addtobeamertemplate{footline
}{\texttt{\hfill\insertframenumber/
{\inserttotalframenumber}}}
149 %\AtBeginSubsection[] {
150 %\begin{frame}<beamer>
152 %\tableofcontents[currentsection,currentsubsection]
156 %\begin{frame}<beamer>
158 %\tableofcontents[currentsection]%,currentsubsection]
162 \setbeamertemplate{sections/subsections in toc
}[sections numbered
]
163 %\setbeamertemplate{sections in toc}[sections numbered]
171 {\bf Institut de Mathématiques de Marseille
}\\
173 {\bf Equipe Analyse, Géométrie et Topologie (AGT)
}\\
177 {\bf Séminaire de Géométrie Complexe
}\\
195 \begin{frame
}[plain
]{Plan
}
200 \section{Introduction
}
203 \subsection{Définitions
}
206 \begin{frame
}{Définition formelle I
}
208 Multiplication dans $
\Fqn$, le corps fini avec $q^n$ éléments:
210 \mathsf{m
}:
\Fqn \times \Fqn \rightarrow \Fqn
214 \rotatebox[origin=c
]{270}{{\color{mycvblue
}$
\rightsquigarrow$
}}
218 \mathsf{M
}:
\Fqn \otimes_{\Fq} \Fqn \rightarrow \Fqn
225 \rotatebox[origin=c
]{270}{{\color{mycvblue
}$
\rightsquigarrow$
}}
229 t_
\mathsf{m
} \in \Fqn^
\star \otimes \Fqn^
\star \otimes \Fqn
233 $
\Fqn^
\star$: dual de $
\Fqn$ sur $
\Fq$.\\
239 \begin{frame
}{Définition formelle II
}
244 t_
\mathsf{m
} :=
\displaystyle\sum_{i=
1}^
{N
}\;a_i^
\star \otimes b_i^
\star \otimes c_i
\label{eqn1
}
246 où $a_i^
\star, b_i^
\star \in \Fqn^
\star$ et $c_i
\in \Fqn$, alors pour tous $x, y
\in \Fqn$, on a
248 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
}.
251 Chaque expression ($
\ref{eqn2
}$) est appelée un
\textbf{algorithme de multiplication bilinéaire de complexité ~$N$
}.
257 Si $a_i^
\star = b_i^
\star$ pour tout $i$, l'algorithme est
\textbf{symmétrique
}.
265 \begin{frame
}{Définition formelle III
}
271 \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 \
}
273 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
275 \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 \
}
277 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$
}.
}
282 %\rk \ \ $\displaystyle{\mu_q(n) \leq \mus_q(n)}$
288 \subsection{Quantités asymptotiques
}
297 \Ms_q :=
\displaystyle \limsup_{n
\rightarrow \infty} \frac{\mus_q(n)
}{n
}
301 %\ms_q := \displaystyle \liminf_{n \rightarrow \infty} \frac{\mus_q(n)}{n}.
306 %Note that ${\ms_q \leq \Ms_q \leq C_q}$.
310 %\textbf{{\color{mycvblue}Known bounds:}} \\
312 %\begin{enumerate}[(i)]
313 % \item $\displaystyle{\ms_{q^2} \leq 2\left( 1 + \frac{1}{q-3}\right)}$ \hfill [Chudnovsky, Chudnovsky (1988)]}\\
316 % \item $\Ms_2 \leq 18.35$ \hfill [Ballet, P. (2010)]\\ }
319 % \item If $q\geq4$, then $\displaystyle{\Ms_q \leq 6 \left(1+ \frac{p}{q-3}\right)} $ \hfill [Ballet (2003)] \\}
320 % \vspace{0.3em}\uncover<5->{
321 % \item If ${q \geq2,t\geq1}$ are such that $q^t-5>0$, then
323 % \Ms_{q} \leq \mu_{q}(2t)\frac{(q^t-1)}{t(q^t-5)} \qquad \mbox{ and }
325 % \Ms_{q^2} \leq \mu_{q}(t)\frac{2(q^t-1)}{t(q^t-5)}
328 % \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
330 % $q$ & 2 & 3 & 4 & 5 & 7 & 8 & 9 & 11 &13 \\
332 % $\Ms_q$ & 7.47 & 5.49 & 4.98 & 4.8 & 3.82 & 3.74 & 3.68 & 3.62 & 3.59 \\
335 % \begin{flushright}[Cascudo, Cramer, Xing, Yang (2011)]\end{flushright} }
343 \section{Algorithme de D.V. et G.V. Chudnovsky (
1987)
}
345 \subsection{Avec des places rationnelles
}
348 \begin{frame
}{Algorithme original de Chudnovsky et Chudnovsky
}
352 \item[$
\bullet$
] $
\FF/
\Fq$ un corps de fonctions algébriques défini sur $
\Fq$,
353 \item[$
\bullet$
] $Q$ une place de degré $n$,
354 \item[$
\bullet$
] $P_1,
\ldots, P_N$, $N$ places distinctes de $
\FF/
\Fq$ de degré
1,
355 \item[$
\bullet$
] $
\D$ un diviseur tel que $
\mathsf{supp
}\,
\D\cap\
{Q, P_1,
\ldots, P_N\
}~=
\varnothing$.
361 \begin{enumerate
}[(i)
]
362 \item la première fonction d'évaluation
364 \begin{array
}[t
]{cccc
}
365 \mathsf{Ev
}_Q : &
\Ld{} &
\longrightarrow &
\mathsf{F
}_Q
\simeq \Fqn \\
366 & f &
\longmapsto & f(Q)
369 est
\textbf{surjective
},
371 \item la seconde fonction d'évaluation est
\textbf{injective
}:
373 \begin{array
}[t
]{cccl
}
374 \mathsf{Ev
}_
{\mathscr{P
}} : &
\Ld[2\D] &
\longrightarrow &
\mathbb{F
}_q^N \\
375 & f &
\longmapsto &
\big(f(P_1),
\ldots, f(P_N)
\big)
392 \subsection{Principe
}
395 \begin{frame
}{Principe pour multiplier avec l'algorithme de Chudnovsky
}
401 \begin{array
}[c
]{cccl
}
402 \hspace{-
2em
}\uncover<
3->
{ &
\mathcal{O
}_Q
}&
\uncover<
3->
{\xtwoheadrightarrow[]{ \hspace{4em
} \pi_Q \hspace{4em
} } } &
\uncover<
2->
{ \mathsf{F
}_Q
} \\
403 \uncover<
3>
{Q
\notin \mathsf{supp
}\;
\D} &
\uncover<
3->
{\cup} & & \;
\uncover<
2->
{ \hspace{-
0.3em
}\shortparallel \ \\
}
404 \uncover<
1,
2>
{\mathsf{Ev
}_Q :
} &
\Ld{} &
\xtwoheadrightarrow[]{ \uncover<
3->
{\hspace{1.6em
} \mathsf{Ev
}_Q =
{\pi_Q}_
{|
\Ld{}} \hspace{1.6em
}} } &
\Fqn \\
405 & & &
\uncover<
2->
{\rotatebox[origin=c
]{90}{$
\in $
}} \\
406 \uncover<
4->
{ & f &
\dotarrow{\hspace{12.7em
} } } &
\uncover<
2->
{x
} \uncover<
4->
{ = f(Q) \\
}
407 \uncover<
5->
{ & g &
\dotarrow{\hspace{12.7em
} } } &
\uncover<
2->
{y
} \uncover<
5->
{= g(Q) \\
}
408 %\uncover<1,2>{\mathsf{Ev}_Q :} & & & \\
411 \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 \\
413 \uncover<
6->
{ & f
}&
\uncover<
7->
{ \xmapsto{\hspace{10em
} } &
\big( f(P_1),
\ldots, f(P_N)
\big)
}\\
414 \uncover<
6->
{ & g
}&
\uncover<
7->
{ \xmapsto{\hspace{10em
} } &
\big( g(P_1),
\ldots, g(P_N)
\big)\\
}
416 &
\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)
}\\
418 &
\uncover<
10->
{\longdownmapsto\hspace{2.5em
}}& &
\hspace{6em
} {\color<
11>
{mycvblue
} \uncover<
11->
{\rotatebox[origin=c
]{-
90}{$
\leadsto$
}}} \\
419 & & &
{\color<
11>
{mycvblue
} \uncover<
11->
{\mbox{N mult.
\textbf{bilinéaires
} dans $
\Fq$
}}} \\
420 &
\uncover<
10->
{\ \ (fg)(Q) & = f(Q)g(Q) = xy \ \ \ \
} & \\
426 \subsection{Avec des places de degré un et deux
}
429 \begin{frame
}{Evaluations sur des places de degré
1 et
2}
434 \item[$
\bullet$
] $
\FF/
\Fq$ un corps de fonctions algébriques défini sur $
\Fq$,
435 \item[$
\bullet$
] $Q$ une place de degré $n$,
436 \item[$
\bullet$
] $P_1,
\ldots, P_
{N_1
}$, $N_1$ places distinctes de $
\FF/
\Fq$ de degré
1,
437 \item[$
\bullet$
] $S_1,
\ldots, S_
{N_2
}$ $N_2$ places distinctes de $
\FF/
\Fq$ de degré
2,
438 \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$.
444 \begin{enumerate
}[(i)
]
445 \item la première fonction d'évaluation
447 \begin{array
}[t
]{cccc
}
448 \mathsf{Ev
}_Q : &
\Ld{} &
\longrightarrow &
\mathsf{F
}_Q
\simeq \Fqn \\
449 & f &
\longmapsto & f(Q)
453 est
\textbf{surjective
},
454 \item la seconde fonction d'évaluation est
\textbf{injective
}:
456 \begin{array
}[t
]{cccl
}
457 \mathsf{Ev
}_
{\mathscr{P
}} : &
\Ld[2\D] &
\longrightarrow &
\F_q^
{N_1
} \times \F_{q^
2}^
{N_2
} \\
458 & f &
\longmapsto &
\big(f(P_1),
\ldots, f(P_
{N_1
}), f(S_1),
\ldots, f(S_
{N_2
})
\big)
468 \mus_q(n)
\leq \displaystyle N_1 +
\underbrace{3}_
{\mu_q(
2)
}N_2.
476 \section{Conditions permettant l'utilisation de l'algorithme
}
478 \subsection{Conditions principales
}
481 \begin{frame
}{Conditions suffisantes pour appliquer l'algorithme
}
483 \begin{theoreme
}[B. (
1999), B., Pieltant, Rambaud, et Sisjling (
2017)
]
485 Soit $
\FF/
\F_q$ un corps de fonctions algébriques de genre $g$.
486 Soit $N_k$ le nombre de places de degré $k$ dans $F/
\F_q$.\\
487 Si $
\FF/
\F _q$ est tel que $
2g+
1 \leq q^
{\frac{n-
1}{2}}(
\sqrt{q
}-
1)$ alors:
488 \begin{enumerate
}[1)
]
490 \item si $N_1 >
2n+
2g-
2$, alors
492 \mus_q(n)
\leq 2n+g-
1,
495 \item si il existe un diviseur non-spécial de degré $g-
1$ et $
{N_1+
2N_2>
2n+
2g-
2}$, alors
501 % \item if $N_1+2N_2>2n+4g-2$, then
503 % \mus_q(n)\leq 3n+6g.
510 {\bf Objet "géométrico-algébrique" pertinent:
}
514 $---->$
\textbf{corps de fonctions avec beaucoup de places
} (rationnelles ou de degré deux) relativement à leur genre.
}
518 \subsection{Applications
}
521 \begin{frame
}{Le cas des extensions de petits degré
}
523 \begin{theoreme
}[Winograd et de Groote (
1979,
1983)
]
524 La complexité bilinéaire de la multiplication dans $
\Fqn$ sur $
\Fq$ satisfait
530 \mus_q(n) =
2n-
1\ \
\Longleftrightarrow \ \ n
\leq \frac{q
}{2}+
1.
535 \begin{theoreme
}[Shokrollahi (
1992), Chaumine (
2004)
]
537 Si $
\displaystyle{n
\leq \frac{1}{2}\left(q+
1+
\epsilon(q)
\right)
}$, alors
543 \epsilon(q) =
\left\
{
545 2\sqrt{q
} \mbox{ si
}q
\mbox{ est un carré parfait,
} \\
546 \mbox{le plus grand entier inférieur ou égal à
} 2\sqrt{q
}\mbox{ co-premier avec
} q
\mbox{ sinon.
}
555 \begin{frame
}{Algorithme de Chudnovsky sur un corps de fonctions hyperelliptique de genre
2}
556 %\vspace{-3em} \chch~
558 Soit $
\FF/
\Fqr{2}=
\F_{16}(x,y)
\qquad \mbox{ où
} \quad y^
2+y =x^
{5}$\\
563 $
{\qquad g(
\FF) =
2 \quad \mbox{ et
} \quad N_1(
\FF) = q^
2+
1 +
2g(
\FF)q =
33.
}$\\
570 N_1
\geq 2n +
2g-
1 \qquad \mbox{ i.e.
} \qquad n
\leq \frac{1}{2}(N_1-
2g+
1)
574 alors on peut appliquer l'algorithme de Chudnovsky sur le corps de fonctions algébriques ~$
\FF/
\Fqr{2}$ pour multiplier dans ~$
\Fqr{2n
}$.\\
581 {\color{mycvblue
}\textbf{Conséquence:
}} multiplication dans des extensions de degré $n$ de $
\F_{16}$.
% $\F_{{16}^n} / \F_{16}$.
592 \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.
}
600 \begin{frame
}{Exemple pour les
\textit{petites
} extensions $
\F_{16^n
}$ de $
\F_{16}$
}
602 \setlength{\unitlength}{1cm
}
603 \begin{picture
}(
7,
6)(-
3,
0)
606 \put(
0,-
1)
{\vector(
0,
1)
{7.5}}
607 \put(-
0.1,
6.7)
{$n$
}% degré de l'extension de $\F_{16}$} % legend top flèche
608 \put(-
0.2,-
0.78)
{\line(
1,
0)
{0.4}}
613 \put(-
0.2,
1.2)
{\line(
1,
0)
{0.4}}
614 \put(-
1.95,
1.1)
{$
\frac{1}{2}q^
2+
1=
9$
}
615 \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.$
}
616 \put(
7.5,
0.16)
{\color{mycvblue
}$(g=
0)$
}
621 \put(-
0.2,
1.86)
{\line(
1,
0)
{0.4}}
622 \put(-
3.4,
1.76)
{$
\left[\frac{1}{2}(q^
2+
1+
2q)
\right]=
12$
}
623 \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.$
}
624 \put(
7.5,
1.45)
{\color{mycvblue
}$(g=
1)$
}
629 \put(-
0.2,
5.6)
{\line(
1,
0)
{0.4}}
630 \put(-
3.7,
5.5)
{$
\frac{1}{2}(q^
2+
4q-
2)=
15$
}
631 \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.$
}
632 \put(
7.5,
3.68)
{\color{mycvblue
}$(g=
2)$
}
637 \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
}$
}$
}}
645 \setbeamercovered{transparent
}
649 %Application de l'algorithme sur une \textbf{suite asymptotiquement bonne de corps de fonctions} :
651 Application de l'algorithme sur
\textbf{une bonne famille asymptotiquement de corps de fonctions algébriques :
}
653 \begin{theoreme
}[\ch$^
2$(
1987), Shparlinski-Tsfasman-Vladut (
1992), B.~(
1999)
]
654 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$,
656 \mus_q(n)
\leq C_q n.
662 %{\color{mycvblue}\textbf{Objectifs.}}
664 % \item[$\bullet$] \'Etablir des bornes théoriques :
666 % \uncover<1,2>{\item[$\bullet$] améliorer l'algorithme: évaluations sur des places de degré supérieur, dissymétrisation (Randriambololona 2012)…}
667 % \item[$\bullet$] démontrer l'existence de corps de fonctions avec de meilleures propriétés
669 %\uncover<1,2>{ \item[$\bullet$] Construire des algorithmes explicites pour la multiplication dans $\Fqn$, pour $n$ choisi.}
677 %%%%%%%%%%%%% T %%%%%%%%%%%%%%%
680 %%%%%%%%%%%%% T %%%%%%%%%%%%%%%
684 %\begin{Theorem}\label{lemmek0}
685 %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
686 %$$l_{k+1}-l_k\leq l_k^{\alpha}$$ for any prime $l_k\geq x_{\alpha}.$
688 %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)).$
694 %%%%%%%%%%%%% T %%%%%%%%%%%%%%%
696 \section{Nouveau résultats
}
698 \subsection{Bornes uniformes connues
}
702 \begin{theoreme
}\label{theo_arnaudupdate
}
703 Soit $
{q=p^r
}$ une puissance d'un premier $p$ et $n$ un entier $>
1$. Alors:
704 \begin{enumerate
}[(i)
]
705 %\item If ${q=2}$, then $\displaystyle{\mus_{q}(n) \leq 15.46n}$ (cf. \cite[Corollary 29]{bapi2} and \cite{ceoz})
706 % \item If ${q=3}$, then $\displaystyle{\mus_{q}(n) \leq 7.732 n}$ (cf. \cite[Corollary 29]{bapi2} and \cite{ceoz})
707 \item Si $
{q
\geq 4}$, alors $
\displaystyle{\mus_{q
}(n)
\leq 3 \left(
1 +
708 \frac{\frac{4}{3}p
}{q-
3+
2(p-
1)
\frac{q
}{q+
1}} \right)n
}$ (cf.
[2])
709 \item Si $p
\geq5$, alors $
\displaystyle{\mus_{p
}(n)
\leq 3\left(
1+
710 \frac{8}{3p-
5}\right)n
}$ (cf.
[2])
711 \item Si $
{q
\geq 4}$, alors $
\displaystyle{\mus_{q^
2}(n)
\leq 2 \left(
1 +
712 \frac{p
}{q-
3 + (p-
1)
\frac{q
}{q+
1}} \right)n
}$ (cf.
[1] and
[2])
713 \item Si $p
\geq5$, alors $
\displaystyle{\mus_{p^
2}(n)
\leq 2 \left(
1 +
714 \frac{2}{p-
\frac{33}{16}} \right)n
}$ (cf.
[2])
722 [2] B., Pieltant, Rambaud et Sisjling,
2017.
727 \subsection{Nouvelles bornes uniformes
}
731 \begin{proposition
}[B. et Zykin (
2017)
]
732 Soit $p
\geq 5$ un nombre premier.
733 %and let $x_{\alpha}$ be the constant from Theorem \ref{lemmek0}.
737 \item Si $p
\neq 11,$ alors pour tout entier $ n
\geq \frac{p-
3}{2}x_
\alpha+
\frac{p+
1}{2}$:
738 %$$\Ms_{q^2}\leq 2\left(1+\frac{1}{q-3}\right).$$
740 \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,
742 où $
\epsilon_p(n)=
\left(
\frac{2n
}{p-
3}\right)^
{\alpha-
1},$ $
\alpha=
\frac{2}{3}$ avec $x_
{\alpha}=
\exp(
\exp(
33.217)).$
744 \item Si $p=
11$ et $ n
\geq (p-
3)x_
\alpha+p-
1=
8x_
\alpha+
10$:
746 \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},
748 où $
\epsilon_{p
}(n)=
\left(
\frac{n
}{p-
3}\right)^
{\alpha-
1},$ $
\alpha=
\frac{2}{3}$ avec $x_
{\alpha}=
\exp(
\exp(
33.217)).$
750 %\item Asymptotically the following inequality holds for any $p\geq 5$:
751 \item Asymptotiquement, pour tout $p
\geq 5$:
753 \Ms_{p^
2} \leq 2\left(
1+
\frac{1}{p-
3}\right).
762 \begin{frame
}{Corps de fonctions sur $
\F_{p^
2}$
}
764 \textbf{Preuve: idées principales
}\\
766 \textbf{Courves modulaires:
} $
\qquad \displaystyle{\mathsf{X
}_0(N) :=
\Gamma_0(N)
\backslash \mathfrak{h
} \mbox{, pour
}N
\in \NN^*
}$\\
773 \mathfrak{h
} & = &
\big\
{z
\in \CC \ | \ Im(z)>
0\big\
}\\
775 \Gamma_0(N) & = &
\left\
{
779 \end{pmatrix
} \in \mathsf{SL
}_2(
\ZZ) \
\Big\vert \ c
\equiv 0 \pmod{N
}
781 \mbox{ \ "sg. de congruence"
}
787 \underline{Pour $p
\neq 11:$
}
792 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$:
795 \item[$
\bullet$
] $g(
\FF_{k
}) =
\ell_{k
}$,
796 \item[$
\bullet$
] $N_1(
\FF_{k
}/
\F_{p^
2})
\geq (p-
1)(
\ell_{k
}+
1)$.
801 \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)$
805 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)$
808 %Thus we get for each \textit{sufficiently large} integer $n$, a function field which satisfies the conditions allowing the use of the algorithm.
815 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.
819 {\bf Théorème de densité des nombres premiers de type Hoheisel
}
823 \begin{theoreme
}[Baker, Harman et Pintz (
2001), Dudek (
2016)
]\label{lemmek0
}
824 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
825 $$l_
{k+
1}-l_k
\leq l_k^
{\alpha}$$ pour tout premier $l_k
\geq x_
{\alpha}.$
827 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)).$
832 %%%%%%%%%%%%% T %%%%%%%%%%%%%%%
836 \begin{proposition
}[B. et Zykin (
2017)
]
837 Soit $p
\geq 5$ un nombre premier.
838 %, let $x_{\alpha}$ be defined as in Theorem \ref{lemmek0}, and $\epsilon_p(n)$ as in Proposition above.
841 \item Si $p
\neq 11,$ alors pour tout entier $ n
\geq \frac{p-
3}{2}x_
\alpha+
\frac{p+
1}{2}$:
842 %$$\Ms_{q^2}\leq 2\left(1+\frac{1}{q-3}\right).$$
844 \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}.
846 où $
\epsilon_p(n)=
\left(
\frac{2n
}{p-
3}\right)^
{\alpha-
1},$ $
\alpha=
\frac{2}{3}$ avec $x_
{\alpha}=
\exp(
\exp(
33.217)).$
847 %where $\ds\epsilon_p(n)=\left(\frac{2n}{p-3}\right)^{\alpha-1}.$
849 \item Si $p=
11$ et $ n
\geq (p-
3)x_
\alpha+p-
1=
8x_
\alpha+
10$:
851 \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.
853 où $
\epsilon_{p
}(n)=
\left(
\frac{n
}{p-
3}\right)^
{\alpha-
1},$ $
\alpha=
\frac{2}{3}$ avec $x_
{\alpha}=
\exp(
\exp(
33.217)).$
854 %where $\ds\epsilon_{p}(n)=\left(\frac{n}{p-3}\right)^{\alpha-1}.$
856 %\item Asymptotically the following inequality holds for any $p\geq 5$:
857 \item Asymptotiquement, pour $p
\geq 5$:
859 \Ms_{p
} \leq 3\left(
1+
\frac{\frac{4}{3}}{p-
3}\right).
868 \textbf{Preuve: idées principales
}
872 \textbf{Descente de courbes modulaires sur le corps de définition $
\F_p$:
}
876 Soit $
\FF_{0}(N)$ le corps de fonctions algébriques associé à la courbe $
\mathsf{X
}_0(N)$:
880 $$
\qquad \FF_0(N)=
\FF_0(N)/
\F_p\otimes \F_{p^
2}$$
889 \item[$
\bullet$
] $g(
\FF_0(N)/
\F_p) = g(
\FF_0(N))$
890 \item[$
\bullet$
] $N_1(
\FF_{0}(N)/
\F_{p^
2}) = N_1(
\FF_{0}(N)/
\F_{p
})+
2N_2(
\FF_{0}(N)/
\F_{p
})$.
895 {\bf Algorithme généralisé de type Chudnovsky avec des places de degré deux
}
899 {\bf Théorème de densité des nombres premiers de type Hoheisel
}
907 \section{Conclusions et perspectives
}
909 \subsection{Problèmes et/ou travail en cours
}
913 \begin{frame
}{Conclusion
}
923 1) Expliciter le théorème de densité des nombres premiers de Baker-Harman-Pintz:
927 $--->$ Déterminer de manière effective $x_
{\alpha}$ pour le meilleur $
\alpha$ connu i.e. $
\alpha=
\frac{21}{40}$.
931 Commentaires de
{\bf Sary Drapeau
} et
{\bf Olivier Ramaré
}: $$"
\hbox{{\bf Hautement non trivial
}}".$$
935 2) Généraliser les bornes uniformes "obtenues à partir des courbes modulaires" pour les corps finis $
\F_{p^
2}$
936 et $
\F_{p
}$ aux corps finis $
\F_{q^
2}$ et $
\F_{q
}$ où $q=p^r$ avec $r>
1$:
940 $--->$ Objectif principal de notre projet avec
{\bf Alexey Zykin
}, commencé en Avril
2017 à Tahiti.
944 Commentaires d'
{\bf Alexey
}:
{\bf "C'est maintenant que le vrai travail commence!"
}
946 % 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
955 %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.
957 - une famille de corps de fonctions
{\bf définis sur $
\F_{q^
2}$
} (avec $
{q=p^m
}$ et $
{m>
1}$)
961 -
{\bf suffisamment dense
}
965 $--->$ généralisation des courbes modulaires:
{\bf les courbes de Shimura
}
967 %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.
971 \textbf{Courbes de Shimura :
} {\it Asymptotiquement
} (Shparlinski-Tsfasman-Vladut) (
1992)
975 $
\qquad \displaystyle{\mathsf{X
}_
\ell(
\CC) :=
\Gamma_\ell\backslash\mathfrak{h
}\mbox{, pour $
\ell$ un nombre premier
{\bf "suffisamment grand''
} (?)
}}$\\
977 \indent où $
\Gamma_\ell$ est un sous-groupe d'indice $
\ell$ de $
\Gamma$, le groupe des unités d'un ordre maximal
978 $
\mathcal{O
}$ d'une algèbre des quaternions $B$.\\
982 On utilise la famille des corps de fonctions $
\FF_{k
}/
\F_{q^
2}$ associés aux courbes $
\mathsf{X
}_
{\ell_k,p
}$
983 qui sont la réduction des $
\mathsf{X
}_
{\ell_k}$ modulo $p$, avec $
\ell_k$ le $k$-ième nombre premier.
988 Chaque $
\FF_k/
\F_{q^
2}$ satisfait:
993 \item[$
\bullet$
] $g(
\FF_{k
}) =
1+
\ell_{k
}(g-
1)$
994 \item[$
\bullet$
] $N_1(
\FF_{k
}/
\F_{q^
2})
\geq \ell_{k
}(q-
1)(g+
1)$
997 avec $g$ le genre de $
\mathsf{X
}_
{\Gamma,p
}(
\F_{p^
2})$, la réduction modulo $p$
998 de la courbe de Shimura associée à $
\Gamma$.
1005 %\section{Conclusions et perspectives}
1012 %\subsection{Open problems and/or in work in progress}
1014 %\underline{Les problèmes ouverts et en cours de traitement :} \\
1018 %\item[$\bullet$] {\it \bf Amélioration des constantes $C_q$}
1020 %$$\hbox{-----$>$ {\bf Dans le cas général:} }$$
1022 %- Utilisation de familles de courbes plus denses qu'une tour:
1023 %courbes modulaires, de Shimura (travail en cours avec Alexey Zykin).
1027 %- Utilisation de familles de courbes ayant bcp de diviseurs non-spéciaux de degré $g-1$ et peu de points de 2-torsion.
1030 %$$\hbox{-----$>$ {\bf Sur les petits corps:} }$$
1033 %- 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$
1034 %(travail en cours avec Julia Pieltant).
1047 %MERCI BEAUCOUP POUR VOTRE ACCUEIL
1053 % \begin{frame}[plain]
1055 % \includegraphics[height=2cm]{thu_zykin}
1061 %\begin{frame}[plain]
1062 % \begin{beamerboxesrounded}%
1063 % [lower=block title, %
1064 % upper=block title,%
1067 % {\Large \textbf{{\color{mycvblue}Thank you for your attention.}}}\\
1069 % {\Large \textbf{{\color{mycvblue}Questions?}}}\\
1071 % \end{beamerboxesrounded}
1075 \section{Hommage à Alexey
}
1076 \begin{frame
}[plain
]
1077 \begin{beamerboxesrounded
}%
1078 [lower=block title,
%
1082 {\Large \textbf{{\color{mycvblue
}A la Mémoire de mon Ami \\
\vspace{2em
} {\bf Alexey Zykin
}}}}\\
1084 %{\Large \textbf{{\color{mycvblue}Questions?}}}\\
1085 \includegraphics[height=
2cm
]{thu_zykin
}
1088 \end{beamerboxesrounded
}
1092 % 1. "Everything is good at home, there is nothing to throw out."
1093 % ou plutôt chez lui est "at HIS home", mais c'est maladroit.
1095 % 2. "Everything is good at his place, there is nothing to throw out."
1096 %Le "at his place" is plus familier.
1099 %Mais en français poetique, "chez lui" peut dire quelque chose plus générale,
1100 %comme "autour de lui". On peut éventuellement le traduire ce sens par :
1101 % 3. "Everything he does is good, there is nothing to throw out."
1103 %This was what caracterized our friend Alexey Zykin