Function: teichmuller
Section: transcendental
C-Name: teichmuller
Prototype: GDG
Help: teichmuller(x,{tab}): teichmuller character of p-adic number x. If
x = [p,n], return the lifts of all teichmuller(i + O(p^n)) for
i = 1, ..., p-1. Such a vector can be fed back to teichmuller, as the
optional argument tab, to speed up later computations.
Doc: Teichm\"uller character of the $p$-adic number $x$, i.e. the unique
$(p-1)$-th root of unity congruent to $x / p^{v_p(x)}$ modulo $p$.
If $x$ is of the form $[p,n]$, for a prime $p$ and integer $n$,
return the lifts to $\Z$ of the images of $i + O(p^n)$ for
$i = 1, \dots, p-1$, i.e. all roots of $1$ ordered by residue class modulo
$p$. Such a vector can be fed back to \kbd{teichmuller}, as the
optional argument \kbd{tab}, to speed up later computations.
\bprog
? z = teichmuller(2 + O(101^5))
%1 = 2 + 83*101 + 18*101^2 + 69*101^3 + 62*101^4 + O(101^5)
? z^100
%2 = 1 + O(101^5)
? T = teichmuller([101, 5]);
? teichmuller(2 + O(101^5), T)
%4 = 2 + 83*101 + 18*101^2 + 69*101^3 + 62*101^4 + O(101^5)
@eprog\noindent As a rule of thumb, if more than
$$p \,/\, 2(\log_2(p) + \kbd{hammingweight}(p))$$
values of \kbd{teichmuller} are to be computed, then it is worthwile to
initialize:
\bprog
? p = 101; n = 100; T = teichmuller([p,n]); \\ instantaneous
? for(i=1,10^3, vector(p-1, i, teichmuller(i+O(p^n), T)))
time = 60 ms.
? for(i=1,10^3, vector(p-1, i, teichmuller(i+O(p^n))))
time = 1,293 ms.
? 1 + 2*(log(p)/log(2) + hammingweight(p))
%8 = 22.316[...]
@eprog\noindent Here the precompuation induces a speedup by a factor
$1293/ 60 \approx 21.5$.
\misctitle{Caveat}
If the accuracy of \kbd{tab} (the argument $n$ above) is lower than the
precision of $x$, the \emph{former} is used, i.e. the cached value is not
refined to higher accuracy. It the accuracy of \kbd{tab} is larger, then
the precision of $x$ is used:
\bprog
? Tlow = teichmuller([101, 2]); \\ lower accuracy !
? teichmuller(2 + O(101^5), Tlow)
%10 = 2 + 83*101 + O(101^5) \\ no longer a root of 1
? Thigh = teichmuller([101, 10]); \\ higher accuracy
? teichmuller(2 + O(101^5), Thigh)
%12 = 2 + 83*101 + 18*101^2 + 69*101^3 + 62*101^4 + O(101^5)
@eprog
Variant:
Also available are the functions \fun{GEN}{teich}{GEN x} (\kbd{tab} is
\kbd{NULL}) as well as
\fun{GEN}{teichmullerinit}{long p, long n}.