padics.info

This is padics.info, produced by makeinfo version 6.6 from padics.texi.

INFO-DIR-SECTION Mathematics/Maxima
START-INFO-DIR-ENTRY
* Package padics: (maxima)Maxima package for p-adic computations.
END-INFO-DIR-ENTRY


File: padics.info,  Node: Top,  Next: Introduction to package padics,  Prev: (dir),  Up: (dir)

Package padics
**************

* Menu:

* Introduction to package padics::
* Definitions for package padics::
* Function and variable index::

1 Package padics
****************


File: padics.info,  Node: Introduction to package padics,  Next: Definitions for package padics,  Prev: Top,  Up: Top

1.1 Introduction to package padics
==================================

Package 'padics' implements some Maxima functions for computing with
p-adic numbers, where p stands for a prime number.  These numbers, whose
set is denoted *Q*_{p}, are obtained by a process of completion of the
usual rational numbers but with respect to a p-adic norm, which is
different from the Euclidean norm on *Q* (the absolute value).  The
p-adic norm of a rational number r=a/b is obtained as follows: factor
out all the powers of <p> in the numerator and the denominator, and
simplify them so you get r=p^{<g>}(a'/b').  For example, if <p=3> and
r=36/15

     36/15=3^{<2>}*4/(3*5)=3*(4/5)

   The exponent <g> of <p> in this reduced expression is called the
p-adic order of the rational <r>; thus, padicorder(36/15)=1 if p=3.
Using the built-in functions of the package, we would do

     (%i1)	load("padics.mac");
     (%o1)	"padics.mac"
     (%i2)	padic_order(36/15,3);
     (%o2)	1

   Then, the p-adic norm of the rational <r>, denoted |r|_{<p>}, is
1/p^{<g>}.  In the example above,

     |36/15|_{<3>}=1/(3^1)

   and using the package,

     (%i3)	padic_norm(36/15,3);
     (%o3)	1/3

   Intuitively, we can say that in the p-adic norm, a rational is small
if it is divisible by a big power of <p>, so a big number is one that is
coprime with <p>, or contains higher powers of <p> only in the
denominator.

   Of course, once defined the p-adic norm, there is also a p-adic
distance between rational numbers <r> and <s>, given by |r-s|_{<p>}.
This distance is ultrametric, which means that it satisfies the triangle
equality:

     |r+s|_{<p>}= max(|r|_{<p>},|s|_{<p>}) (if <r>,<s> are not equal).

   A geometric consequence of this fact is that in the p-adic plane,
every triangle is isosceles (see the readable paper by P. N. Natarajan
and K. N. Ranganathan, A geometry where all triangles are isosceles,
Resonance 5(10) (2012) 32-42).

   Just as every real number (resulting from the completion with respect
to the absolute value norm) can be represented by a decimal expansion,
in such a way that rationals correspond precisely to reals with a finite
or periodic decimal expansion, elements of *Q*_{p} can be represented by
p-adic expansions (in powers, both positive and negative, of a prime
number <p>), where the coefficients are integers between <0> and <p-1>
modulo p.  Notice, however, that the convergence of these series is
considered with respect to the p-adic norm, and not the absolute value.
This has some striking consequences: for instance, the series of
rational numbers whose general term is r_{<n>} is sumable in *Q*_{p} if
and only if the limit of |r_{<n>}|_{<p>} when <n> tends to infinity is
zero!  (This is sometimes dubbed as the bad student's dream).  Thus, the
series with general term p^{<n>} is convergent in *Q*_{p}, and being
geometric its sum equals 1/(1-p)=-1/(p-1) (this fact, that a certain
notion of convergence can lead to a negative number when adding up
infinite positive numbers, is an endless source of fun in the internet
forums).  Another difference with the real case is that a convergent
series is unconditionally convergent, so reorderings have no effect (the
proof of these facts can be found in the book by F. Q. Gouve^a, p-adic
Numbers (Springer Verlag, 2003)).

   When we represent p-adic numbers by truncating their p-adic
expansions at a certain length, we get what are called their Hensel
codes.  For instance, in *Q*_{3} we have seen that the series with
general term 3^{<n>} converges to -1/2.  Hence

     -1/2 = 1*3^0 + 1*3^1 + 1*3^2 + 1*3^3 + ...

   so we could represent -1/2 by a list of the form [[0],1,1,1,...].
The first element [0] is another list with only one element, indicating
at which power of <p> we begin to count, and the remaining elements give
the coefficients of -1/2 in its expansion with respect to powers of <p>.
If we choose to work with truncated expressions of length 4, then we
would have that -1/2 is represented by the Hensel code [[0],1,1,1,1].
In the syntax of the 'padics' package:

     (%i4)	hensel(-1/2,3,4)
     (%o4)	[[0],1,1,1,1]

   That is: the Hensel code of -1/2 in *Q*_{3}, truncated at length 4 is
[[0],1,1,1,1].  It is possible to define the usual arithmetic operations
on Hensel codes: we can add, substract, multiply and divide them, and
the result will be another Hensel code which will represent a p-adic
number.  The computations have a distinctive feature: they are carried
on from left to right, modulo <p>, in contrast to the operations with
real numbers.  As these operations are defined on lists of a definite
length, they are collectively called a finite segment arithmetic.
Consider for example the representation on the number 2/3 in *Q*_{3}.
Clearly we can write

     2/3 = 2*3^(-1) + 0*3^0 + 0*3^1 +0*3^2 + 0*3^3 + ...

   so its Hensel code of length 4 would be [[-1],2,0,0,0] (because we
begin to count at the power 3^{<-1>}, which is accompanied by the
coefficient 2, and the remaining coefficients are all 0).  Notice that
adding their expansions we get

     -1/2 + 2/3 = 1*3^0 + 1*3^1 + 1*3^2 + 1*3^3 + ... + 2*3^(-1) + 0*3^0 + 0*3^1 +0*3^2 + 0*3^3 + ...

   so, grouping coefficients of the same power and keeping the length as
4,

     -1/2 + 2/3 = 2*3^(-1) +1*3^0 + 1*3^1 + 1*3^2 + ... = [[-1],2,1,1,1]

   On the other hand, the sum -1/2 + 2/3 equals 1/6.  What is the Hensel
code of 1/6 in *Q*_{3} (with length 4)?  We can use the preceding
results as follows:

     1/6 = 1/3*(1/2) = 1/3*(1-1/2) = 1/3*(1*3^0 + 1*3^0 +1*3^1 +1*3^1 + ...) = 2*3^(-1) +1*3^0 + 1*3^1 + 1*3^2 + ...

   which is the same as above, that is, 1/6 = [[-1],2,1,1,1].  We can
check all these computations with the following commands (notice how we
declare the value p=3 as an argument in both of them):

     (%i5)	padic_sum([[0],1,1,1,1],[[-1],2,0,0,0],3);
     (%o5)	[[-1],2,1,1,1]
     (%i6)	hensel_to_farey([[-1],2,1,1,1],3);
     (%o6)	1/6

   Thus, it is possible to represent p-adic numbers by Hensel codes and
to define the four usual arithmetic operations on these, following some
simple rules.  As a consequence, other operations such as taking square
roots, can be performed given the appropriate conditions (if we are
computing on *Q*_{p}, only quadratic residues modulo <p> have roots).
For instance, we can compute the square roots of r=25 in *Q*_{7} using
'padic_sqrt' as follows:

     (%i7)	padic_sqrt(25,7);
     (%o7)	[552213837122886833247075521/110442767424206762611644736,5]
     (%i8)	map(lambda([u],hensel(u,7,8)),%);
     (%o8)	[[[0],2,6,6,6,6,6,6,6],[[0],5,0,0,0,0,0,0,0]]

   A more difficult computation is: given a certain Hensel code, how to
recover a rational approximation to the p-adic number it represents?
The mathematics behind the algorithm are quite involved, and can be
consulted in the book by R. T. Gregory and E. V. Krishnamurthy, Methods
and Applications of Error-Free Computation (Springer Verlag, 1984).  The
set of rationals that represent the p-adic numbers in a given finite
segment are known as Farey fractions, hence the name 'hensel_to_farey'
for the command above.  The Farey sequence of fractions of order <n> is
the sequence of all reduced fractions between <0> and <1> whose
denominator is less than or equal to <n>, arranged in order of
increasing size.

   The package 'padics' contains functions for computing the p-adic
order and norm of rational numbers, and the p-adic distance between two
of them.  Also, there are functions to obtain the Hensel code of a
rational and vice-versa (the Farey fraction representing a given Hensel
code).  The sum, difference, product and quotient of rationals in
*Q*_{p} are implemented, as well as more advanced functions for
computing square roots and solving linear systems of equations by the
method of Gaussian elimination.  The accompanying documentation file
'padics-doc.pdf' describes a Maxima session using the commands in the
package and contains lots of examples.  The session is also available as
a wxMaxima worksheet 'padics-doc.wxm'.


File: padics.info,  Node: Definitions for package padics,  Next: Function and variable index,  Prev: Introduction to package padics,  Up: Top

1.2 Definitions for package padics
==================================

 -- Function: padic_order (<r>, <p>)

     Computes the <p>-adic order of the rational number <r>.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	padic_order(3/10,5);
          (%o1)	-1

 -- Function: padic_canonical (<r>, <p>)

     Computes the canonical form of the rational number <r> with respect
     to <p>: r=a/b=p^{padic_order(r)}a'/b'.  The result has the form of
     a list [p^{padic_order(r)},a'/b'].

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	padic_canonical(0.234,2);
          (%o1)	[1/4,117/125]
          (%i2)	padic_canonical(0,3);
          (%o2)	[1,0]

 -- Function: padic_norm (<r>, <p>)

     Computes the <p>-adic norm of the rational number <r>.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	makelist(padic_norm(140/297,k),k,[2,3,5,7,11]);
          (%o1)	[1/4,27,1/5,1/7,11]

 -- Function: padic_distance (<x>, <y>, <p>)

     Computes the <p>-adic distance between <x> and <y>.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	padic_distance(2166^2,2,7);
          (%o1)	1/2401
          (%i2)	padic_distance(82,1,3);
          (%o2)	1/81

 -- Function: hensel (<r>, <p>, <N>)

     Computes the <p>-adic Hensel code of length <N> for the rational
     number <r>.  The result is a list of the form
     [[e],a0,a1,a2,...,aN], where <e> is the exponent of the code and
     a0a1...aN is the mantissa.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	hensel(7/6,5,4);
          (%o1)	[[0],2,4,0,4]
          (%i2)	hensel(1/25,5,4);
          (%o2)	[[-2],1,0,0,0]
          (%i3)	hensel(-7/8,3,5);
          (%o3)	[[0],1,2,1,2,1]

 -- Function: nicehensel (<r>, <p>, <N>)

     Computes the <p>-adic Hensel code of length <N> for the rational
     number <r>, but displays the result in the form commonly found in
     textbooks and expository works, that is, something like
                 r = a_{-e}...a_{-1}.a_{0}a_{1}a_{2}...
     where <e> is the order of <r>.  The result is a string (not a
     number).

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	nicehensel(8/3,5,9);
          (%o1)	.123131313
          (%i2)	nicehensel(2/15,5,7);
          (%o2)	4.131313
          (%i3)	nicehensel(-1/3,5,7);
          (%o3)	.3131313
          (%i4)	stringp(%);
          (%o4)	true

 -- Function: normalize_hensel (<list>)

     normalizes the Hensel code <list> so that the first digit after the
     dot is not zero.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	normalize_hensel([[-1],0,0,1,2,3]);
          (%o1)	[[1],1,2,3]

 -- Function: padic_sum (<l1>, <l2>, <p>)

     Computes the sum of the Hensel codes <l1> and <l2> in *Q*_{p}.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	padic_sum([[2],2,5,1,5],[[-3],3,3,3,2],7);
          (%o1)	[[-3],3,3,3,2]
          (%i2)	h1:hensel(2/3,5,9);
          (h1)	[[0],4,1,3,1,3,1,3,1,3]
          (%i3)	h2:hensel(5/6,5,9);
          (h2)	[[1],1,4,0,4,0,4,0,4,0]
          (%i4)	padic_sum(h1,h2,5);
          (%o4)	[[0],4,2,2,2,2,2,2,2,2]

 -- Function: padic_substract (<l1>, <l2>, <p>)

     Computes the difference of the Hensel codes <l1> and <l2> in
     *Q*_{p}.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	padic_substract(hensel(3/4,5,4),hensel(3/2,5,4),5);
          (%o1)	[[0],3,3,3,3]

 -- Function: padic_multiply (<l1>, <l2>, <p>)

     Computes the product of the Hensel codes <l1> and <l2> in *Q*_{p}.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	t1:hensel(4/15,5,4);
          (t1)	[[-1],3,3,1,3]
          (%i2)	t2:hensel(5/2,5,4);
          (t2)	[[1],3,2,2,2]
          (%i3)	padic_multiply(t1,t2,5);
          (%o3)	[[0],4,1,3,1]

 -- Function: padic_divide (<l1>, <l2>, <p>)

     Computes the division of the Hensel code <l1> by the Hensel code
     <l2> in *Q*_{p}.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	dividend:[[0],4,1,3,1,3,1,3];
          (dividend)	[[0],4,1,3,1,3,1,3]
          (%i2)	divisor:[[0],3,4,2,4,2,4,2];
          (divisor)	[[0],3,4,2,4,2,4,2]
          (%i3)	padic_divide(dividend,divisor,5);
          (%o3)	[[0],3,1,0,0,0,0,0]

 -- Function: farey (<n>)

     Generates the Farey sequence of fractions of order <n>.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	farey(8);
          (%o1)	[0,1/8,1/7,1/6,1/5,1/4,2/7,1/3,3/8,2/5,3/7,1/2,4/7,3/5,5/8,2/3,5/7,3/4,4/5,5/6,6/7,7/8,1]

 -- Function: hensel_to_farey (<list>, <p>)

     Given a Hensel code <list>, 'hensel_to_farey' computes its Farey
     fraction, a rational number close in *Q*_{p} to the rational number
     represented by <list>.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	hensel_to_farey([[0],3,3,3,3,3,3,3],5);
          (%o1)	-3/4
          (%i2)	hensel_to_farey([[0],2,3,1,5],7);
          (%o2)	9/43
          (%i3)	hensel_to_farey([[-1],3,2,2,2],5);
          (%o3)	1/10
          (%i4)	hensel(1/10,5,4);
          (%o4)	[[-1],3,2,2,2]

 -- Function: sqrtmod (<n>, <p>)

     Determines whether <n> is a quadratic residue modulo <p> or not.
     If the answer is negative, it prints a message.  In the affirmative
     case, it returns a list [k,mod(-k,p)] where <k> is such that
     k^{2}=n mod p.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	sqrtmod(2,5);
          (%o1)	Not a quadratic residue
          (%i2)	sqrtmod(2,7);
          (%o2)	[3,4]

 -- Function: padic_sqrt (<n>, <p>, <[k]>)

     Computes the square roots of <n> in *Q*_{p} using Newton's method.
     The optional argument <k> determines the number of iterations.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	padic_sqrt(7,3,3);
          (%o1)	[977/368,108497/41008]
          (%i2)	padic_sqrt(6,5)[1];
          (%o2)	80746825394092993/32964753427463648

 -- Function: padic_gauss (<M>, <p>, <[t]>)

     Given a linear system of equations Ax=b, where A is a square matrix
     of order m whose coefficients are rational numbers, and b is a
     column matrix of dimension m'x'1, let M be the augmented matrix
     M=A|b.  Then, 'padic_backsub' triangularizes the system using the
     arithmetic in *Q*_{p} (so the triangularized system it returns has
     Hensel codes as coefficients).  A heuristic routine is used to
     determine the number of digits in the resulting Hensel codes (never
     more than <8> to avoid an excessive computational cost).  The
     optional argument <t> allows the user to fix the number of digits
     to be used.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	D:matrix([3,1,3,16],[1,3,1,8],[1,1,3,12]);
          (D)	matrix(
          		[3,	1,	3,	16],
          		[1,	3,	1,	8],
          		[1,	1,	3,	12]
          	)
          (%i2)	padic_gauss(D,11);
          (%o2)	matrix(
          		[[[0],3,0,0,0],	[[0],1,0,0,0],	[[0],3,0,0,0],	[[0],5,1,0,0]],
          		[[[0],0,0,0,0],	[[0],10,3,7,3],	[[0],0,0,0,0],	[[0],10,3,7,3]],
          		[[[0],0,0,0,0],	[[0],0,0,0,0],	[[0],2,0,0,0],	[[0],6,0,0,0]]
          	)

 -- Function: padic_backsub (<M>, <p>)

     Solves a triangularized system whose coefficients are Hensel codes,
     such as the ones returned by 'padic_gauss', using backward
     substitution in *Q*_{p}.

     'load("padics.mac")' loads this function.

     Example:

          (%i1)	D:matrix([3,1,3,16],[1,3,1,8],[1,1,3,12]);
          (D)	matrix(
          		[3,	1,	3,	16],
          		[1,	3,	1,	8],
          		[1,	1,	3,	12]
          	)
          (%i2)	padic_gauss(D,11);
          (%o2)	matrix(
          		[[[0],3,0,0,0],	[[0],1,0,0,0],	[[0],3,0,0,0],	[[0],5,1,0,0]],
          		[[[0],0,0,0,0],	[[0],10,3,7,3],	[[0],0,0,0,0],	[[0],10,3,7,3]],
          		[[[0],0,0,0,0],	[[0],0,0,0,0],	[[0],2,0,0,0],	[[0],6,0,0,0]]
          	)
          (%i3)	padic_backsub(%,11);
          (%o3)	[[[0],2,0,0,0],[[0],1,0,0,0],[[0],3,0,0,0]]
          (%i4)	map(lambda([x],hensel_to_farey(x,11)),%);
          (%o4)	[2,1,3]


File: padics.info,  Node: Function and variable index,  Prev: Definitions for package padics,  Up: Top

Appendix A Function and variable index
**************************************

[index]
* Menu:

* farey:                                 Definitions for package padics.
                                                              (line 168)
* hensel:                                Definitions for package padics.
                                                              (line  56)
* hensel_to_farey:                       Definitions for package padics.
                                                              (line 179)
* nicehensel:                            Definitions for package padics.
                                                              (line  74)
* normalize_hensel:                      Definitions for package padics.
                                                              (line  96)
* padic_backsub:                         Definitions for package padics.
                                                              (line 258)
* padic_canonical:                       Definitions for package padics.
                                                              (line  17)
* padic_distance:                        Definitions for package padics.
                                                              (line  43)
* padic_divide:                          Definitions for package padics.
                                                              (line 152)
* padic_gauss:                           Definitions for package padics.
                                                              (line 228)
* padic_multiply:                        Definitions for package padics.
                                                              (line 137)
* padic_norm:                            Definitions for package padics.
                                                              (line  32)
* padic_order:                           Definitions for package padics.
                                                              (line   6)
* padic_sqrt:                            Definitions for package padics.
                                                              (line 214)
* padic_substract:                       Definitions for package padics.
                                                              (line 125)
* padic_sum:                             Definitions for package padics.
                                                              (line 108)
* sqrtmod:                               Definitions for package padics.
                                                              (line 198)



Tag Table:
Node: Top216
Node: Introduction to package padics492
Node: Definitions for package padics8651
Node: Function and variable index17046

End Tag Table