Computing the Ramanujan tau function
type: Item
instance of: scholarly article
title: Computing the Ramanujan tau function
zbMATH Open document ID: 1109.11066
author: Denis Xavier Charles
published in: The Ramanujan Journal
publication date: 2006-11-03T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 11Y55
Mathematics Subject Classification ID: 11F11
Mathematics Subject Classification ID: 11-04
zbMATH DE Number: 5070735
zbMATH Keywords: Ramanujan tau function
zbMATH Keywords: Selberg trace formula
zbMATH Keywords: Algorithms
zbMATH Keywords: Generalized Riemann Hypothesis
reviewed by: Tom M. Apostol
MaRDI profile type: Publication
full work available at URL: s11139-006-6509-y
OpenAlex ID: W2089345203
cites work: Q3995823
cites work: Q3139838
cites work: Asymptotically Fast Factorization of Integers
cites work: Q4111656
cites work: Q5617656
cites work: Q3237356
cites work: Q3123961
DOI: 10.1007/S11139-006-6509-Y
description: scientific article; zbMATH DE number 5070735