# Applications of $p$-adic numbers in CS

Are there any concrete (or a rich source of) examples of application of $p$-adic numbers in computer science?

• p-adic number / Wikipedia. used in number theory. somewhat indirect, eg there is some analysis of the Collatz conjecture via p-adic theory & Collatz is considered by some to be deeply connected to TCS undecidability research. – vzn Oct 25 '14 at 17:19

De, Kurur, Saha and Saptharishi gave a modular version of Fürer's integer multiplication algorithm in their paper Fast integer multiplication using modular arithmetic, in which the p-adic numbers replace the complex numbers used by Fürer. Both algorithms give the best bit-complexity for integer multiplication.

• This is Good example. – 1.. Oct 26 '14 at 4:51

Hensel lifting is very closely related to the $p$-adics: it's basically getting a better and better approximation to a $p$-adic number, "better" in the sense of "closer in the $p$-adic valuation. Hensel lifting is used in many algorithms such as factoring polynomials or doing linear algebra over $\mathbb{Z}$ (if I recall correctly Dixon has a paper on the latter).

• From polynomials in $\Bbb Z_p[x]$, we cannot say anything about representation in $\Bbb R[x]$. Right? – 1.. Oct 26 '14 at 4:52
• @J.A: Unlikely (I assume here by $\mathbb{Z}_p$ you mean the $p$-adic integers). Perhaps some relationship between $\mathbb{Q}_p[x]$ and $\mathbb{R}[x]$ (especially if one considers questions over all $p$) or between $\mathbb{Z}_p[x]$ and $\mathbb{Z}[x]$... See the Hasse principle: en.wikipedia.org/wiki/Hasse_principle – Joshua Grochow Oct 26 '14 at 13:52
• yes the $p$-adic integers. – 1.. Oct 26 '14 at 17:14
• Has the relation between $\Bbb Q_p[x]$ and $\Bbb R[x]$ been ever used? say in size of circuits and polynomials and rational functions or rank in communication complexity? – 1.. Oct 26 '14 at 17:16
• @J.A: I don't know - if you find a use or a reference to a use, please let us know! – Joshua Grochow Oct 26 '14 at 20:31

There are also some computational models:

Here is the first paper: Rusins Freivalds: Ultrametric automata and Turing machines. Turing-100 2012: 98-112

here is a nice general survey with a brief overview of diverse (recent) CS applications for p-adic theory, p3

Here are areas where p-adic dynamics proved to be effective: computer science (straight line programs), numerical analysis and simulations (pseudorandom numbers), uniform distribution of sequences, cryptography (stream ciphers, T- functions), combinatorics (Latin squares), automata theory and formal languages, genetics. The monograph [9] contains the corresponding survey. For a newer results see recent papers and references therein: [10, 14, 15, 28, 36, 37, 38, 48, 51]. Moreover, there are studies in computer science and cryptography which along with mathematical physics stimulated in 1990th intensive research in p-adic dynamics since it was observed that major computer instructions (and therefore programs composed of these instructions) can be considered as continuous transformations with respect to the 2-adic metric, see [11, 12].

• Interesting. where in straight line programs is it used? – 1.. Oct 26 '14 at 4:53
• Also these dont seem mainstream work. – 1.. Oct 26 '14 at 4:56