Archive for the ‘p-adic numbers’ Category

Finally, Witt Vectors

June 1, 2009

Now, let us try to do arithmetic operations on p-adic numbers written in terms of Teichmüller representatives. Suppose

a = t(a_0) + t(a_1)p + t(a_2)p^2 + \ldots

and

b = t(b_0) + t(b_1)p + t(b_2)p^2 + \ldots.

In other words,

a \equiv a_0 \pmod{p},

a \equiv a_0^p + a_1 p \pmod{p^2},

a \equiv a_0^{p^2} + a_1^p p + a_2 p^2 \pmod{p^2},

and ditto for b. Then

a + b \equiv a_0 + b_0\pmod{p}\\ \text{\ \ \ \ \ \ } \equiv t(a_0 + b_0) \pmod{p}.

a + b \equiv a_0^p + a_1 p + b_0^p + b_1 p \pmod{p^2}\\ \text{\ \ \ \ \ \ }\equiv (a_0+b_0)^p + \big(a_1 + b_1 - \sum_{i=1}^{p-1} \frac{1}{p}\binom{p}{i} a_0^i b_0^{p-i} \big)p \pmod{p^2}.

a b \equiv a_0 b_0 \pmod{p}\\ \text{\ \ \ \ \ \ } \equiv t(a_0 b_0) \pmod{p}.

a b \equiv (a_0^p + a_1 p )( b_0^p + b_1 p) \pmod{p^2}\\\text{\ \ \ \ \ \ } \equiv (a_0 b_0)^p + (a_0^p b_1 + a_1 b_0^p)p \pmod{p^2}.

So, if we define polynomials in x = (x_0, x_1, \ldots) and y = (y_0, y_1, \ldots)

S_0(x, y) = x_0 + y_0,

S_1(x, y) = x_1 + y_1 - \sum_{i=1}^{p-1} \frac{1}{p}\binom{p}{i} x_0^i y_0^{p-i},

P_0(x, y) = x_0 y_0,

P_1(x, y) = x_0^p y_1 + x_1 y_0^p,

then

a+b \equiv t(S_0(a,b)) \pmod{p},

a+b \equiv t(S_0(a,b)) + t(S_1(a,b))p \pmod{p^2},

ab \equiv t(P_0(a,b)) \pmod{p},

ab \equiv t(P_0(a,b)) + t(P_1(a, b))p \pmod{p^2}.

One can also show that there exist polynomials S_j(x, y) and P_j(x, y) for all integer j\geq 0 such that

a+b \equiv \sum_{j=0}^{i-1} t(S_j(a,b))p^j \pmod{p^i} and

ab \equiv \sum_{j=0}^{i-1} t(P_j(a,b))p^j \pmod{p^i},

for all i\geq 1, or, more curtly,

a+b = \sum_{j=0}^{\infty} t(S_j(a,b))p^j and

ab = \sum_{j=0}^{\infty} t(P_j(a,b))p^j.

In other words, the addition and multiplication of p-adic integers can be written in polynomial form when those numbers are written in terms of Teichmüller representatives.

Tags:, ,
Posted in Witt vectors, p-adic numbers | Leave a Comment »

More on Teichmüller Representatives

June 1, 2009

As I mentioned before, Teichmüller’s great insight was that one might have better luck if using representatives

t(m) = (m, m^p, m^{p^2}, \ldots)

for m = 0, \ldots, p-1, instead of integers 0, \ldots, p-1 themselves. One of the advantages, for example is that this set of representatives is closed under multiplication. In other words, it is an monomorphism of multiplicative monoids from {\mathbb F}_p to {\mathbb Z}_p.

But is this really a set of representative? In other words, can every p-adic integer be written as a p-series in t(0), \ldots, t(p-1)? Since t(m) \equiv m \pmod{p} for each m, and integers 0,\ldots, p-1 form a set of representatives, the answer to this question is yes.

Let’s offer a demonstration. Say we would like to write 5-adic integer 7 in terms of Teichmüller representatives. Say,

7 = t(a_0) + t(a_1)5 + t(a_2)5^2 + \ldots.

Then

  • 7 \equiv 2 \pmod{5}, so let a_0 = 2.
  • 7 \equiv a_0^5 + 5 a_1 \pmod{5^2}, i.e., 5 a_1 \equiv 7 - 2^5 \equiv 0 \pmod{25}, so we take a_1=0.
  • 7 \equiv a_0^{25} + 5 a_1^5 + 5^2 a_2 \pmod{5^3}, i.e., 25 a_2 \equiv 7 - 2^{25} - 0^5 \equiv 75 \pmod{125}, so we take a_2=3.
  • 7 \equiv a_0^{125} + 5 a_1^{25} + 5^2 a_2^5 + 5^3 a_3 \pmod{5^4}, i.e., 125 a_3 \equiv 0 \pmod{125}, so we take a_3=0.
  • etc.

So,

7 = t(2) + t(0) 5 + t(3) 5^2 + t(0) 5^3 + \ldots.

Therein lies a seed of the inductive proof of the fact that

\{t(m) | m\in 0,\ldots, p-1\}

is a set of representatives. If for a fixed p-adic integer a one can choose a_0, \ldots, a_{n-1} \in 0,\ldots, p-1 so that

a \equiv t(a_0) + t(a_1) p + \cdots + t(a_{n-1}) p^{n-1} \pmod{p^n},

or, equivalently,

a \equiv a_0^{p^{n-1}} + a_1^{p^{n-2}} p + \cdots + a_{n-1} p^{n-1} \pmod{p^n},

then

a - (a_0^{p^n} + a_1^{p^{n-1}} p + \cdots + a_{n-1}^p p^{n-1}) \equiv 0 \pmod{p^n},

and there exists a_n \in 0, \ldots, p-1 such that

a - (a_0^{p^n} + a_1^{p^{n-1}} p + \cdots + a_{n-1}^p p^{n-1}) \equiv a_n p^{n} \pmod{p^{n+1}}.

Then

a \equiv a_0^{p^n} + a_1^{p^{n-1}} p + \cdots + a_{n-1}^p p^{n-1} + a_n p^{n} \pmod{p^{n+1}},

or, equivalently,

a \equiv t(a_0) + t(a_1) p + \cdots + t(a_{n}) p^{n} \pmod{p^{n+1}}.

The short version is that any overshot modulo p^{n} can be corrected modulo p^{n+1} using only multiples of p^n.

Tags:,
Posted in Witt vectors, p-adic numbers | Leave a Comment »

Motivation for Witt Vectors

June 1, 2009

If we write two p-adic integers a and b as p-series in integers 0, \ldots, p-1, and then multiply them together to get c, it goes something like this:

(a_0 + a_1 p + \cdots)(b_0 + b_1 p + \cdots) = a_0 b_0 + (a_1 b_0 + a_0 b_1) p + \cdots

Therefore, c_0 \equiv a_0 b_0 \pmod{p}. So far so good. But as we move to the next congruence class, we get

c_1 \equiv a_1 b_0 + a_0 b_1 + \text{ carry from }a_0 b_0 \pmod{p}.

Good luck figuring out the formula for the carry part.

Tags:
Posted in Witt vectors, p-adic numbers | Leave a Comment »

Teichmüller Representatives

January 21, 2009

Let us solve a particular equation in p-adic numbers:

x^p - x = 0.

Notice that since this equation has precisely p distinct solutions in {\mathbb F}_p={\mathbb Z}/p {\mathbb Z} (actually, all of its elements), by p-adic mojo, it has p solutions in {\mathbb Z}_p.

It is easy to figure out the sequence representations of these solutions:

(m, m^p, m^{p^2}, \ldots)

for m=0,\ldots, p-1. By Euler’s Theorem,

m^{p^r} \equiv m^{p^{r-1}} \pmod{p^{r-1}},

which takes care of both the condition on sequences defining a p-adic number and the fact that every element of the sequence is a solution of our equation in its respective modular ring.

Teichmüller’s insight was that it might be easier to write down the arithmetic laws on p-adic numbers expressed as p-series in these numbers (zero and (p-1)st roots of unity) rather than just the integers 0, \ldots, p-1 themselves. But more on that later.

Tags:,
Posted in Witt vectors, p-adic numbers | Leave a Comment »

Topological construction of p-adic integers

December 26, 2008

One of the interesting things to observe is what multiplication by p does to p-adic integers:

p(u_1, u_2, u_3, \ldots) = (p u_1, p u_2, p u_3, \ldots).

But what matters is the congruence class of the components modulo p^r, and pu_1 \equiv 0 \pmod p, pu_{r}\equiv pu_{r-1} \pmod{p^r}, so

p(u_1, u_2, u_3, \ldots) = (0, p u_1, p u_2, \ldots).

Iterating gives us

p^n (u_1, u_2, u_3, \ldots) = (\underbrace{0, \ldots, 0}_{n\text{ times}}, p^n u_1, p^n u_2, \ldots).

This is, of course, a lot easier when using the series notation.

So, we can tell that p^n divides u precisely when the first n components of u are zero. As a corollary, we obtain that if u\neq 0, then there exist a largest n such that p^n divides u (i.e., p^{n+1} does not divide u). This n is precisely the number of the initial components of u that are congruent to zero in their respective {\mathbb Z}/p^r{\mathbb Z}.

Definition. The number n as above is called the p-adic valuation of u, and is denoted by \mathrm{ord}_p(u):

\mathrm{ord}_p(u) := \mathrm{max}\{n\in {\mathbb N} | p^n\text{ divides }u\text{ in }{\mathbb Z}_p \}.

We set \mathrm{ord}_p(0) = \infty.

The p-adic valuation function satisfies the following properties:

  • \mathrm{ord}_p(u) = \infty if and only if u=0,
  • \mathrm{ord}_p(uv) = \mathrm{ord}_p(u)\mathrm{ord}_p(v), and
  • \mathrm{ord}_p(u+v) \geq \mathrm{min}(\mathrm{ord}_p(u), \mathrm{ord}_p(v)).

The last property is referred to as the ultrametric property for reasons to be explained right now.

Given any number 0 < \sigma < 1 (customarily, \sigma = 1/p), we can define

|u|_p := \sigma^{\mathrm{ord}_p(u)}.

Then the properties of \mathrm{ord}_p become

  • |u|_p \geq 0 for all u, with |u|_p = 0 if and only if u=0,
  • |uv|_p = |u|_p\, |v|_p, and
  • |u+v|_p \leq \mathrm{max}(|u|_p, |v|_p).

    • In other words, |\bullet|_p: {\mathbb Z}_p \to {\mathbb R} is an ultrametric norm. We can also define a metric

    d_p(u,v) := |u-v|_p,

    which makes {\mathbb Z}_p into an utrametric space. The topology (convergence of sequences) induced by this norm does not change if we choose a different \sigma, so from now on, \sigma = 1/p. Then

    |u|_p = \frac{1}{p^{\mathrm{ord}_p(u)}}.

    In other words, the higher power of p divides you, the smaller you are.

    Note that this norm can be restricted to the rational integers {\mathbb Z} contained in {\mathbb Z}_p. The ring of integers is not complete under this norm, and therefore we can consider its completion, i.e., the smallest complete normed space containing {\mathbb Z}. Then the standard construction of the completion coincides for the p-adic norm with the construction of p-adic integers as sequences. Specifically, the condition that u_r \equiv u_{r+s} \pmod{p^r} translates into the Cauchy criterion d_p(u_r, u_{r+s}) \to 0 as r\to 0 for sequences.

    In light of this norm, the series notation also starts to make sense. Indeed, the truncated series form a Cauchy sequence, since b_r p^r + b_{r+1} p^{r+1} + \cdots + b_{r+s} p^{r+s} has norm no greater than 1/p^r, which goes to zero as r goes off to infinity. Thus the infinite series we work with converge with respect to the ultrametric p-adic norm.

    Tags:
    Posted in p-adic numbers | Leave a Comment »

    The ring of p-adic integers

    December 26, 2008

    In what way can we impose operations of addition, subtraction, and multiplication on the set of p-adic integers? One thing on our wish list is that these operation be compatible with the corresponding operations on the ring of integers embedded in {\mathbb Z}_p. Another, is that they be compatible with the operation on the component considered as elements of {\mathbb Z}/p{\mathbb Z}. It seems that the obvious way to define these operations is componentwise:

    • (u_1, u_2, \ldots) + (v_1, v_2, \ldots) := (u_1 + v_1, u_2 + v_2, \ldots);
    • (u_1, u_2, \ldots) - (v_1, v_2, \ldots) := (u_1 - v_1, u_2 - v_2, \ldots);
    • (u_1, u_2, \ldots) \cdot (v_1, v_2, \ldots) := (u_1 v_1, u_2 v_2, \ldots).

    Another way to define these operations is using the “series” notation. We perform these operations just like base p calculations, only digits extend infinitely to the left (some people write \ldots b_2 b_1 b_0 instead of the series notation b_0 + b_1 p + b_2 p^2 + \cdots). For example, (2 + 1 \cdot 5 + 3 \cdot 5^2 + \cdots)(1 + 2 \cdot 5 + 4 \cdot 5^2 + \cdots) = 2\cdot 1 + (2\cdot 2 + 1\cdot 1) 5 + (2\cdot 4 + 1\cdot 2 + 3\cdot 1) 5^2 + \cdots = 2 + 0\cdot 5 + 4\cdot 5^2 + \cdots. We carry 1 toward 5^2’s and 2 towards 5^3’s. It’s a bit of an exercise to show that these definitions agree. It is not that difficult to check that these operations make {\mathbb Z}_p into a commutative ring.

    Using Abstract Nonsense, the construction of the p-adic numbers as sequences can be reformulated as follows. For each r we have a map

    {\mathbb Z}/p^{r+1}{\mathbb Z} \to {\mathbb Z}/p^r{\mathbb Z}

    of reduction modulo p^r, so rings {\mathbb Z}/p^r{\mathbb Z} form an inverse system. Then

    {\mathbb Z}_p = \displaystyle\mathop{\mathrm{lim}}_{\longleftarrow}\ {\mathbb Z}/p^r{\mathbb Z},

    the inverse limit of this system. Recall that the inverse limit in the category of rings is constructed by taking all elements of the direct product of all rings in the system (a.k.a. sequences) that “agree” with the reduction maps.

    Posted in p-adic numbers | Leave a Comment »

    Introduction to p-adic integers

    December 25, 2008

    I feel like taking a break from elliptic curves and talking about something completely different. For motivation, let’s take a look at solutions of the equation x^2 + x + 3 \equiv 0 \pmod{5^r} for different values of r. For r = 1, we have two solutions: 1, 3 \pmod{5}. For r=2, still two solutions: 8, 16 \pmod{25}. For r=3 we get 33, 91 \pmod{125}. And so on, and so forth.

    Notice something interesting. Reduce 91 modulo 25, and you get 16. Reduce 16 modulo 5, and you get 1. Similarly, reduce 33 modulo 25 to get 8, which reduces to 3 modulo 5. It seems like a solution modulo 5 begets a solution modulo 25, which then yields a solution modulo 125, etc. No surprise there, since all we are doing is reducing the equation x^2 + x + 3 \equiv 0 \pmod{5^r} modulo 5^{r-1}.

    The question is this. Can we go in the opposite direction and keep this string of solutions going ad infimum? Given a solution modulo 125, can we find one modulo 625? (more…)

    Posted in p-adic numbers | Leave a Comment »