Archive for the ‘Witt vectors’ 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 »