(Dernière révision le 7 avril 2020.)
du choix de $k=\lfloor\log_p\frac{n}{s}\rfloor+1\in[\log_p\frac{n}{s},\log_pn]$.par
du choix $k:=\lfloor\log_p\frac{n}{s}\rfloor+1$, lequel, avec $s\ge p$, implique $\log_p\frac{n}{s} < k \le \log_pn$ et en particulier $\frac{n}{p^k} < s$..
pour tout $x\ge1$,.
\[x^k \le x \cdot x^{\log_p(n/s)} = x^{1-\log_ps} \cdot x^{\log_pn} = x^{1-\log_ps} \cdot n^{\log_px} \le n^{\log_px},\].
Si $m < q$, la somme entre parenthèses est majorée par la série géométrique et le résultat s'obtient en observant que $m^k = n^{\log_p m}$. Si $m=q$, la somme comporte $k$ termes égaux, avec $k \leq \log_p n$, et le résultat s'obtient avec maintenant $m^k = n^{\log_p q}$. Si $m>q$, la somme géométrique s'évalue à \[ \frac{\left(\frac mq\right)^k - 1}{\frac mq - 1} , \] ce qui montre que le premier terme de (1.6) est majoré par \[ T(n)\left(\frac{m}{q}\right)^{k}\frac{q}{m-q} . \] L'inégalité (1.7) avec $x=m/q$ et l'égalité $m^k = n^{\log_p m}$ fournissent le résultat..
et on obtient donc une majoration (1.5) où $n$ est remplacé par $N$.par
. On obtient donc une majoration de $C(n)$ avec comme majorant l'expression tirée de (1.6) en remplaçant $n$ par $N$..
$O(T(n)\log n)$par
$O(T(n)\log_p n)$.
$N = p^\ell$ pour $\ell := \lceil\log_p n\rceil$.
l'opération $x\mapsto\lceil x/p\rceil$par
l'opération croissante $\alpha:x\mapsto\lceil x/p\rceil$.
toutes ces valeurs de $T$ sont majorées par les valeurs en $N/p^i$,par
toutes ces valeurs de $T$ aux itérées $\alpha^{[i]}(n) = \alpha\bigl(\alpha^{[i-1]}(n)\bigr)$ sont majorées par les valeurs en $\alpha^{[i]}(N) = N/p^i$,.
par $N$. Le lemme précédent s'applique alors pour majorer cette expression, majoration qu'il ne reste plus qu'à majorer à son tour.par
par $N$ et $k$ par $K := \lfloor\log_p\frac{N}{s}\rfloor+1 \leq \log_pN = \ell$: \[ C(n) \le T(N)\left(1+\frac{m}{q} +\dots+\left(\frac{m}{q}\right)^{K-1}\right)+m^K\kappa . \] La preuve par cas du Lemme 1.13 s'applique alors pour majorer cette expression, fournissant la majoration (1.9) ci-dessous, analogue à (1.4), majoration qu'il ne reste plus qu'à majorer à son tour lorsque $n\rightarrow\infty$ : si $q>m$, \[ C(n) \le \left(1-\frac{m}{q}\right)^{-1}T(N)+ \kappa \, N^{\log_p m} ; \] si $q=m$, \[ C(n) \le T(N)\log_p N+ \kappa \, N^{\log_p q} ; \] et si $q<m$, \[ C(n) \le N^{\log_pm}\frac{T(N)}{N^{\log_pq}}\left(\frac{q}{m-q}+\kappa\frac{N^{\log_pq}}{T(N)}\right) . \].
avec $n\geq2$.
Décomposer $F$ et $G$ selonpar
Poser $k=\lceil n/2\rceil$ et décomposer $F$ et $G$ selon.
$t<n$par
$t\in\{1,\dots,n-1\}$.
\[\sum_{k=0}^{n-1}{\omega^{(i-1)k}\omega^{-(j-1)k}} =\sum_{k=0}^{n-1}{\omega^{(i-j)k}}.\]par
\[\sum_{k=0}^{n-1}{\omega^{-(i-1)k}\omega^{(j-1)k}} =\sum_{k=0}^{n-1}{\omega^{(j-i)k}}.\].
$0<i-j<n$par
$0<j-i<n$.
$0<j-i<n$par
$0<i-j<n$.
ces anneauxpar
les anneaux $\mathbb{A}[X]/(X^n+1)$ introduits par le Lemme 2.10.
$X^n+1$par
$X^n-1$.
Pour cela,par
Pour utiliser la FFT,.
si $k$ est pair, calculer $\bar{H}(X,X^2Y)\bmod Y^\delta-1$ avec $X^4$ comme racine de l'unité, puis reconstruire $\bar{H}$ avec $X^{-2}=-X^{2d-2}$;par
si $k$ est pair, calculer $\tilde{H}(X,Y)=\bar{F}(X,X^2Y)\bar{G}(X,X^2Y)\bmod Y^\delta-1$ avec $X^4$ comme racine $\delta$-ième de l'unité, puis reconstruire $\bar{H}(X,Y)=\tilde{H}(X,-X^{2d-2}Y)\bmod X^{2d}+1$;.
si $k$ est impair, calculer $\bar{H}(X,XY)\bmod Y^\delta-1$ avec $X^2$ comme racine de l'unité, puis reconstruire $\bar{H}$ avec $X^{-1}=-X^{2d-1}$.par
si $k$ est impair, calculer $\tilde{H}(X,Y)=\bar{F}(X,XY)\bar{G}(X,XY)\bmod Y^\delta-1$ avec $X^2$ comme racine $\delta$-ième de l'unité, puis reconstruire $\bar{H}(X,Y)=\tilde{H}(X,-X^{2d-1}Y)\bmod X^{2d}+1$..
\[F(G(X))=f_0+f_1G(X)+f_2G(X)^2+\dotsb\]par
\[F(G(X))=f_0+f_1G(X)+f_2G(X)^2+\dotsb.\].
de la forme $X^{\lceil{N/2}\rceil} R_N$par
de la forme $1 + X^{\lceil{N/2}\rceil} R_N$.
$\mathbb{Q} \subset \mathbb{A}$.
dans un anneau $\mathbb{A}$,par
dans un anneau commutatif $\mathbb{A}$,.
Ajouter La démonstration qui suit justifie un facteur 13 à la place du facteur 5 de l'énoncé, lequel s'obtient par une variante algorithmique..
et soit $P$ un polynôme non nul de degré $d$..
de degré $n$par
de degré $<n$.
$(X^{n-1},0),\, (X^{n-2},0),\ldots\, (1,0),\, (0,X^{m-1}),\, (0,X^{m-2}), \ldots\, (0,1)$par
$\bigl( (X^{n-1},0),\, (X^{n-2},0),\ldots\, (1,0),\, (0,X^{m-1}),\, (0,X^{m-2}),\ldots\, (0,1) \bigr)$.
sont dans $\mathbb{K}[X]$ où $\mathbb{K}$ est un corpspar
sont dans $\mathbb{K}[X]$, avec $a_m\neq 0$ et $b_n\neq 0$, et où $\mathbb{K}$ est un corps.
Démonstration succintepar
Démonstration succincte.
10$\,$000 chiffrespar
environ 10$\,$000 chiffres.
$\deg(V_1)=0$.par
$V_1=1$ est de degré $0=n-n_0$, et $V_2=-Q_1$ est de degré $n_0-n_1$..
\[ \sum_{i \geq 0} F(p_1^i,\ldots,p_n^i) t^i = \sum_{i=1}^\tau \frac{P_i}{1 - p_1^{e_{i,1}} \cdots p_n^{e_{i,n}} t} \]par
\[ \sum_{i \geq 0} F(p_1^i,\ldots,p_n^i) z^i = \sum_{i=1}^\tau \frac{P_i}{1 - p_1^{e_{i,1}} \cdots p_n^{e_{i,n}} z} \].
polynôme $D(t) = \prod_{i=1}^\tau (1 - p_1^{e_{i,1}} \cdots p_n^{e_{i,n}} t)$ de $\mathbb{Q}[t]$par
polynôme $D(z) = \prod_{i=1}^\tau (1 - p_1^{e_{i,1}} \cdots p_n^{e_{i,n}} z)$ de $\mathbb{Q}[z]$.
de la multiplication.
dans cette taillepar
en taille $2 \times 2$.
Par récurrence, puisque $0\notin p_d(k-d+1\mathbb{N})$par
Par récurrence, puisque $0\notin p_d(k-d+1+\mathbb{N})$.
\[\left(\frac{4X+2}{1-X^2}+\frac{6X^2}{(1-X^2)^2}\right)yy' + \frac{2X}{1-X^2}y'^2\]par
\[\left(\frac{2}{1-X^2}+\frac{6X^2}{(1-X^2)^2}\right)yy' + \frac{6X}{1-X^2}y'^2\].
vectorielle despar
des vecteurs.
\[ (n+1)(n+3)u_{n+2}-2(n+2)nu_{n+1}+(n-1)(n+1)=0 \]par
\[ (n+1)(n+3)u_{n+2}-2(n+2)nu_{n+1}+(n-1)(n+1)u_n=0 \].
factorizationpar
factorisation.
${}+60T^4$par
${}-60T^4$.
qui n'annule pas le terme constant de $f$par
qui n'annule pas le terme dominant de $f$.
Si l'idéal $I$ est radical, l'appartenance de $\chi(f)$ à $I$ entraîne celle de $\bar{\chi}(f)$, où $\bar{\chi}$ est la partie sans carré de $f$. Par minimalité, le polynôme minimal est donc égal à $\bar{\chi}$.par
Si l'idéal $I$ est radical, l'appartenance de $\chi_f(f)$ à $I$ entraîne celle de $\bar{\chi}_f(f)$, où $\bar{\chi}_f$ est la partie sans carré de $\chi_f$. Par minimalité, le polynôme minimal est donc égal à $\bar{\chi}_f$..
Si $I$ est un idéal radical zéro-dimensionnelpar
Si $I$ est un idéal zéro-dimensionnel.
paramétrisation de ${\mathbf V}_{\bar{k}_\Lambda}(I)$par
paramétrisation de ${\mathbf V}_{\bar{k}_\Lambda}(I_\Lambda)$.
il se récrit sous la forme $g = \operatorname{ct}_<(g) + (g - \operatorname{ct}_<(g))$par
il se récrit sous la forme $g = \operatorname{tt}_<(g) + (g - \operatorname{tt}_<(g))$.
on vérifie que $\operatorname{ct}_<(g)^e$ est dans $I$, ce qui conduit à $\operatorname{ct}(g) \in I$, puis à $(g - \operatorname{ct}_<(g))^e \in I_\Lambda$par
on vérifie que $\operatorname{tt}_<(g)^e$ est dans $I$, ce qui conduit à $\operatorname{tt}(g) \in I$, puis à $(g - \operatorname{tt}_<(g))^e \in I_\Lambda$.
inverser $\mu'_u$ modulo $\mu$par
inverser $\mu'_u$ modulo $\mu_u$.
mais l'évaluation en $X_0=1,X_1=0$par
mais l'évaluation en $X_0=0,X_1=0$.
si $m$ est un monôme de degré inférieur àpar
si $m$ est un monôme de $f$ de degré inférieur à.
$-3X_1$par
$X_1$.
dans $E_r$par
dans $B_r$.
la composante homogène de degré $m - di$ de $q_i$par
la composante homogène de degré $d(m - i)$ de $q_i$.
Une base de $R/(f_1)$ est $\{1, X_3\}$.par
Une base de $R/(f_1)$ en tant que $k[X_0,X_1,X_2]$-module est $\{1, X_3\}$..
la suite $f_1,\dots,f_n$ est régulière dans $R_\Lambda$;par
la suite $f_1,\dots,f_{n-r}$ est régulière dans $R_\Lambda$;.
Le fait que la suite $f_1,\dots,f_r$ est régulière dans $R_\Lambda$par
Le fait que la suite $f_1,\dots,f_{n-r}$ est régulière dans $R_\Lambda$.
$q(T)=T^2-9(2X_0^2+X_1^2+X_2^2)$par
$q(T)=T^2-9(2X_0^2-X_1^2-X_2^2)$.
$\dim_{K_{\Lambda,r}} E_r$.par
$\dim_{K_{\Lambda,r}} E_{\Lambda,r}$..
On note \[J=\left(\partial F_j/\partial X_k\right)\]par
On note \[J=\left(\partial f_j/\partial X_k\right)\].
$\log(1+x) = 2F1(1, 1;2;-x)$par
$\log(1+x) = x \, 2F1(1, 1;2;-x)$.
l'opérateur $Q$ ne dépend pas de $k$par
l'opérateur $Q$ dépend polynomialement de $k$.
\[ \frac {\prod_{1\leq\ell L, e_\ell<0} (a_\ell n+b_\ell k+c_\ell+\sigma_\ell)!} {\prod_{1\leq\ell L, e_\ell>0} (a_\ell n+b_\ell k+c_\ell-\sigma_\ell)!} \frac {u(n+i, k+j)} {u(n, k)} \]par
\[\begin{split} \Biggl[ Z^{-k} \prod_{\stackrel{1\leq\ell\leq L}{e_\ell<0}} (a_\ell n+b_\ell k+c_\ell+\sigma_\ell)!^{-e_\ell} \prod_{\stackrel{1\leq\ell\leq L}{e_\ell>0}} (a_\ell n+b_\ell k+c_\ell-\sigma_\ell)!^{-e_\ell} \Biggr] \times u(n+i, k+j) = \\ P(n+i, k+j) \, Z^j \prod_{\stackrel{1\leq\ell\leq L}{e_\ell<0}} \left(\frac {(a_\ell n+b_\ell k+c_\ell+\sigma_\ell)!} {(a_\ell n+b_\ell k+c_\ell+\delta_\ell(i,j))!} \right)^{-e_\ell} \prod_{\stackrel{1\leq\ell\leq L}{e_\ell>0}} \left(\frac {(a_\ell n+b_\ell k+c_\ell+\delta_\ell(i,j))!} {(a_\ell n+b_\ell k+c_\ell-\sigma_\ell)!} \right)^{e_\ell} \end{split}\].
Montrer que toute fraction rationnelle peut se décomposer sous la forme ci-dessus. Donner un algorithme calculant les polynômes $A$, $B$, $C$ et les constantes $Z$ correspondant à une fraction rationnelle donnée en entrée. On pourra représenter $Z$ par son polynôme annulateur minimal.par
Montrer, en donnant un algorithme calculant la constante $Z$ et les polynômes $A$, $B$, $C$, que toute fraction rationnelle peut se décomposer sous la forme ci-dessus..
équationspar
équation.
liouviliennespar
liouvilliennes.
\[ J_\mu(z)\sim\frac1{2^\mu}\sum_{n=0}^\infty \]par
\[ J_\mu(z) \sim \left(\frac{z}{2}\right)^\mu \sum_{n=0}^\infty \].
Bostanpar
Borwein.
$F \bmod G$ est le reste de la division euclidienne de $F$ par $G$, parfois aussi noté $\operatorname{rem}(F,G)$.et
$F = G \mod H$ signifie que les restes des divisions euclidiennes de $F$ et $G$ par $H$ sont égaux, autrement dit, que $F \bmod H = G \bmod H$..