P-adic arithmetic

Dec 12 2012 Published by under Numbers

I've been having a pretty rough month. The day after thanksgiving,
I was diagnosed with shingles. Shingles is painful - very, very painful. Just the friction of clothing brushing over the shingles when I move caused so much pain that I spent weeks being as immobile as possible.

Needless to say, this has been extremely boring. When I wasn't fuzzed out on pain-killers, I've been doing some reading lately on something called p-adic numbers. p-adics are a very strange kind of number: They're strange-looking, strange-acting, and strangely useful.

P-adics are an alternative to the real numbers. In fact, in a way, they are the alternative to real numbers.

If you go back to number theory, there's a reason why the rational numbers aren't sufficient, and why we have to extend them to the reals by adding irrational numbers. If you take all of the possible rational numbers, you find that there are gaps - places where we know that there must be a number, and yet, if we limit ourselves to fractions, there isn't anything to fit. For example, we know that there must be some number where if we multiply it by itself, it's equal to 2. It's more than 1 4/10ths, by about 1/100th. But it's more than 141/100ths, but about 4/1,000ths. It's more that 1,414/1,000s, by about 2/10,000ths. No matter how far we go, there's no fraction that's exactly right. But we know that there's a number there! If we look at those gaps carefully, we'll find that most numbers are actually in those gaps! The real numbers and the p-adics are both ways of creating number systems that allow us to define the numbers that fit in to those gaps.

The easiest way to understand p-adic numbers is think about how we
represent real numbers in base-P. In real numbers, we represent them using the powers of the base. So, for example, we'd write 24.31 in base-5 to mean 2*51 + 4*50 + 3*5-1 + 1*5-2. Using our normal notation for real numbers, we fill in the gaps by writing numbers as an integer part, followed by a decimal point, followed by a fractional part. For real numbers that aren't rationals, we say that the fractional part goes on forever. So the square root of two starts 1.4142135624, and continues on and on, forever, without repeating. That gives us the real numbers. In that system, every number can be written using a finite number of digits to the left of the decimal point, and an infinite number of digits to the right.

P-adic numbers are exactly the opposite: every P-adic number has a finite number of digits to the right of the decimal, but it can have an infinite number to the left!

Defining p-adic numbers starts off being pretty similar to how we compute the representation of numbers in a standard numeric base. Take a number for your base, like 10. For a number n in base 10, take n modulo 10. That's the right-most digit of your number. Divide by ten, dropping the fractional part, and take the result modulo 10, and that's the second-rightmost digit. Continue this until there's nothing left.

For example, take the number 222 in base-10. If we wanted to represent that in base-7, we'd do:

  1. If we divide 222 by 7, we get 31 with a remainder of 5. So the rightmost digit is 5.
  2. We take 31, and divide it by 7, giving us 4, with a remainder of 3. So the second digit is 3.
  3. We're left with 4, so the last digit is 4.

So - 222 in base-7 is 435. It's the same in 7-adic. For a particular base B, all positive integers are written the same in both base-B and B-adic. Integer arithmetic that doesn't involve negative numbers is also the same.

There's one reallybig catch, and it's one that would make a lot of cranks (like E. E. Escultura) very happy: for real numbers, the decimal notation (for example) is a just a representation - 35 in base 10 is written differently from 43 in base 8 but they're the same actual number, just written differently. 35 in 10-adic is not the same number as 43 in 8-adic. As we'll see when we get to metrics, they're quite different. Each p-adic base produces a distinct system of p-adic numbers, and you can't convert between them as freely as you can in the conventional reals. Decimal notation and hexidecimal notation are writing numbers in the same number system; 2-adic and 3-adic are different number systems!

The first essential difference between p-adic numbers and the reals comes when you try to do arithmetic.

As I said above, for integers, if you don't
do anything with negative numbers, P-adic arithmetic is the same as real number integer arithmetic. In fact, if you're working with P-adic numbers, there are no negative numbers at all! In a P-adic number system, subtracting 1 from 0 doesn't give you -1. It "rolls over" like an infinite odometer. So for 7-adic, 0-1 = ...666666666! That means that arithmetic gets a bit different. Actually, it's really pretty easy: you just do arithmetic from the right to the left, exactly the way that you're used to.

For addition and subtraction, P-adic works almost like normal real-number arithmetic using decimals. Addition is basically what you know from decimal arithmetic. Just go right to left, adding digits, and carrying to the left.

So, for example, in 5-adic, if you have a number ...33333, and 24, to add them, you'd go through the following steps.

  1. 3 + 4 is 7, which is 12 in base-5. So the first digit of the sum is 2, and we carry 1.
  2. 3 + 2 is 6, plus the carried one is 6 - so again, 12 in base-5. So the second digit is also 2, and we carry 1.
  3. 3 + 0 is 3, plus the carried one is 4, se the third digit is 4.
  4. For all the rest of the infinite digits streaming off to the left, it's 3+0=3.

So the sum is ...3333422.

To do subtraction, it's still basically the same as what you're used to from decimal. There's just one simple change: infinite borrowing. In normal subtraction, you can borrow from the position to your left if there's anything to your left to borrow from. For example, in decimal, if you wanted to subtract 9 from 23, you'd borrow 10 from the 2, then subtract 9 from 13, giving you a result of 14. But if you wanted to substract 3-9, you couldn't borrow, because there's nothing to the left to borrow from. In p-adic, you can always borrow. If you're subtracting 3-9 in 10-adic, then you can borrow from the 0 to the left of the 3. Of course, there's nothing there - so it needs to borrow from its left. And so on - giving you an infinite string of 9s. So 3-9 in 10-adic gives you ....999999994.

Let's do a full example: ...33333 - 42 in 5-adic.

  1. As always, we start from the right. 3 - 2 = 1, so the first digit is 1.
  2. Since 3 is smaller than 4, we need to borrow 1 - so we have 13 base 5, which is 8. 8 - 4 = 4. So
    the second digit is 4.
  3. For the third digit, we just subtract the borrowed 1, so it's 2.

So the result is ...3333241.

Multiplication and division get even stranger in P-adic. Because we can't have an infinite number of digits to the right of the decimal, p-adic ends up representing fractions using infinite numbers of digits on the right of the decimal. And that means that we get collisions between fractions and negative numbers. (This should start to give you a clue why each p-adic base is really a different number system: the correspondance between roll-over negatives and infinitely long fractions is different in each base.) It's easiest to see how this works by looking at a concrete example.

The fraction 1/3 can't be written as finite-length string in base-5. In 5-adic, that means we can't write it using digits to the right of the decimal point - we would need an infinite number of digits, and we're not allowed to do that. Instead, we need to write it with an infinite number of digits to the left! 1/3 in 5-adic is: ...1313132.

Looks crazy, but it does work: if you do a tabular multiplication, right to left, multiplying ...1313132 by 3 gives you one! Let's work it through:

  • Start from the right: the rightmost digit is 2. 3*2 is 6, which is 11 in base 5; so the rightmost digit is 1, and you carry a one.
  • The next digit is 3: 3 times 3 is - 9, plus the carried 1, gives 10 - which is 20 in base-5, so the next digit is a 0, and you carry 2.
  • The next digit is 1: 3*1 is 3 plus the carried 2 = 5; so 0, carry 1.

And so on - ....13131313132 * 3 = 1, so ....131313132 == 1/3 in 5-adic.

How can we compute the value of 1/3? Just like decimal real numbers: division.

Division in p-adics is actually easy. The trick is that like all of the other arithmetic, it goes from right to left. Suppose we want to divide N by M. To make it easy, we'll talk about the digits of M and N using subscripts. The rightmost digit of a number X is X1; the second-rightmost is X2, etc. The multiplication algorithm is:

  1. Start at the rightmost digit of both numbers.
  2. Find the smallest number d which, multiplied by M, has as Ni as its rightmost digit.
  3. Subtract d*Mi from N.
  4. Drop the trailing last digits from N, giving N'.
  5. Now divide N' by M, and put d on the right.

Let's walk through 1/3 in 5-adic:

  • The rightmost digit of 1 is 1.
  • What, multiplied by 3 will have a trailing digit of 1 in base-5? 2*3=6, which is 11 in base-5. So d = 2.
  • Now we subtract the "11" from 1 - which is really ...00001. So it becomes ...444440.
  • We drop the trailing 0, and N' is ...4444.
  • So now we divide ...4444 by 3. What's the smallest number which, multiplied by 3, ends in a 4 in base-5? 3*3=9, which is 14 in base-5. So the next digit of the result is 3.
  • Now, we subtract 14 from ...4444. That gives us ...44430. Drop the zero, and it's ...4443
  • Next digit is a 1, leaving ...444

Crazy, huh? There is one catch about division: it only really works if the p-base in your p-adic system is a prime number. Otherwise, you get trouble - your p-adic system of numbers isn't a field if p is non-prime.

If you think about it, arithmetic with the P-adics is actually simpler than it is with conventional real numbers. Everything goes right to left. It's all more uniform. In fact, p-adic has been seriously proposed as a number representation for computer hardware, because the hardware is much easier to build when everything can be done uniformly right to left!

There's a lot more wierdness in the p-adics. We haven't even started to talk about metrics and distances in p-adic numbers. That's both where the p-adics get even stranger, and where they actually get useful. That'll be the next post, hopefully within a day or two!

13 responses so far

  • Jeff says:

    Ask any number theorist (or Ostrowski)...it's the reals that are strange, not the p-adics!

  • Henning says:

    Thanks for this wonderful article, can't wait to read the next one
    (and also I'm curious how things like sqrt(2) will look).

    Some typo hints:
    - "Because we can't have an infinite number of digits to the right of the decimal, p-adic ends up representing fractions using infinite numbers of digits on the right of the decimal."
    - "The multiplication algorithm is:" (just before you explain the division algorithm)

    Again, nice read, please more of those! (and get well soon!)

  • Rob Ryan says:

    Interesting, I'd heard the phrase but never made their acquaintance. I'll be looking forward to your next post.

    Very sorry to hear about your shingles though.

  • jre says:

    Mark -
    You have all my sympathy regarding the shingles thing. It may be of limited comfort when you're in the middle of it, but I can assure you that after the attack subsides it goes away entirely and becomes just a really, really unpleasant memory. Until you're an older grownup, that is, and need to get the shingles vaccine -- so don't forget that part. And. let us remember, this is why we give kids the chickenpox vaccine, and why antivax advocates should be subjected to an appropriate punishment. But not shingles. I wouldn't wish that on anybody.
    Get well soon!

  • This is fascinating - I had heard of the technique sometimes used in computing of replacing a division by a constant by a multiplication by a different constant, and I realized in this course of reading this article that the constant in question is actually the 2-adic reciprocal of of the original divisor. I had no idea there was such a wealth of mathematics behind this technique!

  • Jonathan says:

    Small typo:
    3 + 2 is 6, plus the carried one is 6 - so again, 12 in base-5. So the second digit is also 2, and we carry 1.

    The first 6 should be 5. (I'm impressed everything else is right, though.)

  • AG says:

    Yes, we can represent ratios (even infinite) with only changing base. But where we can use this in embedded programming on MCU WITHOUT FPU? For example, we can use fixed point arithmetic (FPA) to present real numbers with some error but is the real domain of usage of "p-adic" arithmetic for the same goals? FPA is possible in MCU because it's fast! But if we present different numbers in different bases? p-adic arith. is based on fact that when we convert ratio from on base to another we have error and this error is real (infinite?) number. But it's the same and fast to use rational arithmetic instead of P-adic arithmetic. So, what are the ideas for usage of P-adic arithmetic?

  • Isaac Schwabacher says:

    @Henning: Try applying the algorithms you know and love to compute sqrt(2). I think you'll notice something interesting when you do it with p-adic numbers instead of real numbers. Make sure to try it with several different choices of p.

    For example,
    sqrt(2._(7)) = ...1266421216213._(7)

  • Isaac Schwabacher says:

    That's not how I did it, but I guess it would work. You have to be careful, though, because there's no ordering on the p-adic numbers, so you can't use the largest integer method to find the next approximation, and instead you have to take (say) the integer between 0 and p-1 that gets you closest. But can you prove that you can always improve the approximation? It's not trivial, but I suspect you can do it. If you get stuck, look up Hensel's Lemma (and if you do, you'll figure out what method I used).

  • [...] an explanation of what p-adic numbers are, and how arithmetic on them works, you can refer to my first post on the p-adics, and for an explanation of p-adic metrics and distance, you can look at this [...]

  • collin237 says:

    Is there any legit use of p-adic numbers in physics? What I've seen about p-adic physics seems to be a shameless promotion of mentalism, homeopathy, creationism, etc.

    Why isn't anyone speaking out against this?

  • anton says:

    Now divide N' by M, and put d on the right.
    To the left, that is.
    I remember there was another occasion of mixing right-left above.

Leave a Reply

Bad Behavior has blocked 1386 access attempts in the last 7 days.