11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vzn Oct 25 '14 at 17:19
13
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is Good example. $\endgroup$ – 1.. Oct 26 '14 at 4:51
10
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ From polynomials in $\Bbb Z_p[x]$, we cannot say anything about representation in $\Bbb R[x]$. Right? $\endgroup$ – 1.. Oct 26 '14 at 4:52
  • 1
    $\begingroup$ @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 $\endgroup$ – Joshua Grochow Oct 26 '14 at 13:52
  • $\begingroup$ yes the $p$-adic integers. $\endgroup$ – 1.. Oct 26 '14 at 17:14
  • $\begingroup$ 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? $\endgroup$ – 1.. Oct 26 '14 at 17:16
  • $\begingroup$ @J.A: I don't know - if you find a use or a reference to a use, please let us know! $\endgroup$ – Joshua Grochow Oct 26 '14 at 20:31
6
$\begingroup$

There are also some computational models:

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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

What are p-Adic Numbers? What are They Used for? / Rozikov

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].

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting. where in straight line programs is it used? $\endgroup$ – 1.. Oct 26 '14 at 4:53
  • 1
    $\begingroup$ Also these dont seem mainstream work. $\endgroup$ – 1.. Oct 26 '14 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.