small medium large xlarge

P-adic Math

Playing with Unreal Numbers

by Mark Chu-Carroll

Generic image illustrating the article
  P-adic numbers are an alternative to the reals. They have real applications, but playing with p-adics is also math geek fun.  

I’m a guy who spends a lot of time in abstract math-land. I love math, and one of my passions is trying to take the beautiful abstractions of math, and explain them in ways that make them at least a little bit comprehensible to people who don’t spend as much time with their heads in the clouds as I do.

When someone says “math,” what you probably think of is numbers. Math is actually a lot more than numbers—but even when we’re dealing with something as common and everyday as numbers, there are different ways of looking at things that are both fascinating and strange.

Everyone is familiar with the idea of the real numbers. The real numbers are part of a progression of types of numbers. In math, we generally start with the natural numbers—that’s 0, 1, 2, and so on. Then we expand the range of values we can describe by adding negative numbers, which gives us integers. Then we allow ratios of two different numbers, which gives us fractions. Finally, we add irrational numbers, and we get the reals.

P-adics are an alternative (in fact, the only real alternative!) to the real numbers. Instead of going from the rationals to the reals, we can go from the rationals to the p-adic numbers.

A Real Alternative

There’s a reason why we couldn’t stop at the rational numbers, why we needed to keep going and add another class of numbers. When you look at the class 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 such that if we multiply it by itself, the result is 2. That number is almost 1 4/10ths, but that’s off by about 1/100th. We can try 141/100, but that’s not quite right either: it’s off by about 4/1000. That’s still not quite right—our refined estimate is now off by about 2/10,000. No matter how far we go, no fraction is ever quite right. There are fractions that are just a tiny, miniscule bit too small, and there are fractions that are a tiny miniscule bit too big, but there’s no fraction that’s exactly the right number.

That number, which we call the square root of two, fits into a gap in the rational numbers. It’s not a rational number, 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, in base 10, when we write 123, what we mean is 1 * 102 + 2*101 + 3*100. We can do the same thing with other number bases—so, for example, in base 5, if we wrote 24.31, that would mean 2*51 + 4*50 + 3*5-1 + 1*5-2—or, in the familiar base-10, 14.64.

Using our normal notation for real numbers, we fill in the gaps between the rational numbers 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 a P-adic Number System

Defining a system of p-adic numbers starts off being pretty similar to how we compute the representation of numbers in a standard numeric base. We need to pick a prime number, p as the base of our system—that’s the p in p-adic. So base-7 in p-adic is called 7-adic numbers.

To express a number n in base 7, take n modulo 7. That’s the right-most digit of your number. Divide by 7, dropping the fractional part, and take the result modulo 7, 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. Well, 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 really big catch that’s a bit of a mind-blower for most people. If you’re used to the real numbers, you know that 35 in base 10 and 43 in base-8 are the same number—they’re just different representations. But in p-adic numbers, each possible p creates a whole different system of numbers! 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 just different ways of writing numbers in the same number system; 2-adic and 3-adic are different number systems!

Doing Arithmetic in P-adic

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

As I said earlier, 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 5, plus the carried 1 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 1 is 4, so 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 reals. 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.

It Gets Stranger

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 left 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—the rest are zeroes, so ....13131313132 * 3 = 1, so ....131313132 == 1/3 in 5-adic.

OK, we’ve shown that ....131313132 is 1/3 because we get 1 when we multiply it by 3, but how can we actually compute this value of 1/3? Just like we do with decimal real numbers: by 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 clear, we’ll talk about the digits of M and N using subscripts, so 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 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 into trouble, because your p-adic system of numbers isn’t a field if p is non-prime.

Although it takes getting used to, 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!

The Power of P-adic Metrics

So that’s the basics of arithmetic. But what makes p-adic numbers really interesting and valuable is metrics.

Metrics are one of those ideas that are simultaneously simple and astonishingly complicated. The basic concept of a metric is straightforward: I’ve got two numbers, and I want to know how far apart they are. But it turns out that there are many different ways of defining “how far apart” things are. Our common notion comes from our geometric intuition. In math, though, you can’t ever just rely on intuition: you need to be able to define things precisely. And precisely defining a metric is difficult. It’s also fascinating: you can create the real numbers from the integers and rationals by defining a metric, and the metric will reveal the gaps between the rationals. Completing the metric—filling in those gaps—gives you the real numbers. Or, if you fill them in differently, the p-adic numbers.

To define just what a metric is, we need to start with fields and norms. A field is an abstract algebraic structure that describes the behavior of numbers. It’s an abstract way of talking about the basic structure of numbers with addition and multiplication operations.

A norm is a generalization of the concept of absolute value. If you’ve got a field F, then a norm of F is a function | x | from values in F to non-negative numbers, with the following properties:

  1. | x | = 0 if and only if x = 0.

  2. |x y| = |x| |y|

  3. |x + y| <= |x| + |y|

A norm on F can be used to define a distance metric d(x, y) between x and y in F as | x - y|.

For example, the absolute value is clearly a norm over the real numbers, and it defines the Euclidean distance between them.

Using the norm, we can see where the gaps between the rational numbers come from.

You can define a sequence a of values in F as a = { ai } for some set of values i. There’s a special kind of sequence called a Cauchy sequence, which is a sequence where limi,j -> infinity |an - am| = 0.

You can show that any Cauchy sequence converges to a real number. But even if every element of a Cauchy sequence is a rational number, it’s pretty easy to show that many (in fact, most!) Cauchy sequences do not converge to rational numbers. There’s something in between the rational numbers which Cauchy sequences of rational numbers can converge to, but it’s not a rational number. When we talk about the gaps in the rational numbers, that’s what we mean. (Yes, I’m hand-waving a bit, but getting into the details would be a distraction, and this is the basic idea!)

When you’re playing with number fields, the fundamental choice that you get is just how to fill in those gaps. If you fill them in using a metric based on a Euclidean norm, you get the real numbers. What makes the p-adic numbers is just a different norm, which defines a different metric.

The idea of the p-adic metric is that there’s another way of describing the distance between numbers. We’re used to thinking about distance measured like a ruler on a numberline, which is what gives us the reals. For the p-adics, we’re going to define distance in a different way, based on the structure of numbers. The way that the p-adic metric works is based on how a number is built relative to the prime-number base.

We define the p-adic metric in terms of the p-adic norm exactly the way that we defined Euclidean distance in terms of the absolute value norm. For the p-adic number, we start off with a norm on the integers, and then generalize it. In the p-adic integers, the norm of a number is based around the largest power of the base that’s a factor of that number: for an integer x, if pn is the largest power of p that’s a factor of x, then the the p-adic norm of x (written |x|p) is p-n. So the more times you multiply a number by the p-adic base, the smaller the p-adic norm of that number is.

The way we apply that to the rationals is to extend the definition of p-factoring: if p is our p-adic base, then we can define the p-adic norm of a rational number as:

  • |0|p = 0

  • For other rational numbers x: |x|p = p to the -ordp(x) power where:

    • If x is a natural number, then ord p(x) is the exponent of the largest power of p that divides x.

    • If x is a rational number a/b, then ord p(a/b) = ord p(a) - ord p(b).

Another way of saying that is based on a property of rational numbers and primes. For any prime number p, you can take any rational number x, and represent it as a p-based ratio pn*(a/b), where neither a nor b is divisible by p. That representation is unique—there’s only one possible set of values for a, b, and n where that’s true. In that case, the p-adic norm of x, |x|p == p-n.

Ok, that’s a nice definition, but what on earth does it mean?

Two p-adic numbers x and y are close together if x - y is divisible by a large power of p.

In effect, this is the exact opposite of what we’re used to. In the real numbers written out in decimal for as a series of digits, the metric says that the more digits numbers have in common moving from left to right, the closer together they are. So 9999 and 9998 are closer than 9999 and 9988.

But with p-adic numbers, it doesn’t work that way. The p-adic numbers are closer together if, moving right to left, they have a common prefix. The distance ends up looking very strange. In 7-adic, the distance between 56666 and 66666 is smaller than the distance between 66665 and 66666!

As strange as it looks, it does make a peculiar kind of sense. The p-adic distance is measuring a valuable and meaningful kind of distance between numbers—their distance in terms of their relationship to the base prime number p. That leads to a lot of interesting stuff, much of which is, to be honest, well beyond my comprehension. For example, the Wiles proof of Fermat’s last theorem uses properties of the p-adic metric!

Mark Chu-Carroll is a PhD computer scientist and professional software engineer. He works as a server engineer at foursquare. His professional interests include collaborative software development, programming languages and tools, and how to improve the daily lives of software developers. Mark blogs about math related topics on Scientopia. Aside from general geekery and blogging, he plays classical music on the clarinet, traditional Irish music on the wooden flute, and folds elaborate structures out of paper.

Send the author your feedback or discuss the article in the magazine forum.