Computing the Ramanujan tau function (Q850530)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computing the Ramanujan tau function |
scientific article |
Statements
Computing the Ramanujan tau function (English)
0 references
3 November 2006
0 references
The Ramanujan tau function \(\tau(n)\) is completely determined by its values at the primes \(p\) dividing \(n\). It is known that \(|\tau|(n)= O(n^6)\), from which it follows that \(\tau(n)\) can be computed in \(O(\log^3n)\) time provided the factorization of \(n\) and the values of \(\tau(p)\) are known for primes \(p\) dividing \(n\). The author shows that, under the generalized Riemann hypothesis, there is a randomized algorithm to compute \(\tau(p)\) with expected running time \(O(p^{{1\over 2}+ \varepsilon})\) for every \(\varepsilon> 0\), and (without assuming the Riemann hypothesis) there is a deterministic algorithm to compute \(\tau(p)\) in time \(O(p^{{1\over 4}+\varepsilon})\) for every \(\varepsilon> 0\).
0 references
Ramanujan tau function
0 references
Selberg trace formula
0 references
Algorithms
0 references
Generalized Riemann Hypothesis
0 references