josanvallejo/padics

A package for computing with p-adic numbers in Maxima CAS

padics: A package for computing with p-adic numbers in Maxima CAS

Overview

This is just a first attempt to create a Maxima package for working with p-adic numbers. It is extremely ugly and slow, lacking anything remotely resembling elegance or optimization, but at least it gives correct answers (for all those examples that I have been able to find in the literature). The current version is suitable for basic courses on the subject of p-adic analysis, and maybe for studying examples illustrating simple theoretical constructions. Topics covered are:

• p-adic norm and distance
• Finite-segment representations of Q_p (Hensel codes)
• p-adic arithmetic
• Conversion from Hensel codes to rational functions (through Farey fractions)
• Newton's method and square roots in Q_p
• p-adic systems of linear equations

Remark: Some functions in the package make use of the commands firstn and lastn, which were introduced in Maxima 5.39. If firstn or lastn are not detected as built-in functions, equivalent functions are defined here.

Installation

To install the package, simply copy padics.mac to your working directory, or make a global installation by copying the file to /usr/share/maxima/5.42.1/share/contrib (or its Windows/MacOS equivalent).

The package can be loaded inside a Maxima session by typing

load("padics.mac");

The file padics-doc.pdf describes a Maxima session using the commands in the package. After loading the file padics-index.lisp, the Maxima commands ? and ?? will find items in the index and display them, e.g.

? padic_sum;

Loading via a specific path e.g.

load("path/to/padics/padics-index.lisp")

and loading via appending the padics package directory e.g.

push("path/to/padics/###.lisp");
load("padics-index.lisp");

both load the index and append the padics documentation items to the online help system.

Examples

(%i1)	load("padics.mac")$

An example giving the p-adic norm of the rational 140/297 for several values of p (taken from http://mathworld.wolfram.com/p-adicNorm.html)

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

The next example (3-adic distance between 82 and 1) comes from

(%i3)	padic_distance(82,1,3);
(%o3)	1/81

Hensel codes are displayed as lists, as in this example (giving the Hensel code of length 4 of the rational 2/7 in Q₅):

(%i4)	hensel(2/7,5,4);
(%o4)	[[0],1,2,1,4]

To display the result in the form commonly found in textbooks and expository works, we have the command nicehensel:

(%i5)	nicehensel(2/7,5,4);
(%o5)	.1214

Arithmetic operations are carried using the format used by hensel. This example is taken from C. Limongelli and R. Pirastu (p-adic Arithmetic and Parallel Symbolic Computation: An Implementation for Solving Linear Systems. Computers and Artificial Intelligence 14 1 (1996) 35–62):

(%i6)	padic_sum(padic_divide([[0],4,3,3,3],padic_sum([[0],3,2,2,2],[[0],2,3,1,3],5),5),[[-2],1,0,0,0],5);
(%o6)	[[-2],1,4,2,2]

A quick check that the answer is correct, because 1/4/(1/2+1/3)+1/25=17/50

(%i7)	hensel(17/50,5,4);
(%o7)	[[-2],1,4,2,2]

We can convert Hensel codes back to rationals using Farey sequences:

(%i8)	hensel_to_farey([[1],2,4,1,4],5);
(%o8)	5/8

We can compute p-adic roots using Newton's method, and the command padic_sqrt --whose syntax is padic_sqrt(number,p)-- admits an optional argument fixing the number of iterations to be done, as in padic_sqrt(number,p,iterations):

(%i9)	padic_sqrt(2,7);
(%o9)	[215912063945802350977/152672884556058511392,2267891697076964737/1603641597827614272]
(%i10)	padic_sqrt(7,3,3);
(%o10)	[977/368,108497/41008]

To solve the problem Ax=b, we have the commands padic_gauss and padic_backsub. The first one triangularizes the system, and its syntax is padic_gauss(B,p), where B=A|b is the augmented matrix of the system (that is, the coefficient matrix A augmented with the column b of non homogeneous terms). The resulting triangular matrix is processed by padic_backsub to obtain the Hensel codes of the solution:

(%i11)	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]
	)
(%i12)	padic_gauss(D,11);
(%o12)	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]]
	)
(%i13)	padic_backsub(%,11);
(%o13)	[[[0],2,0,0,0],[[0],1,0,0,0],[[0],3,0,0,0]]

Converting to Farey fractions we get the rational form of the solutions:

(%i14)	map(lambda([x],hensel_to_farey(x,11)),%);
(%o14)	[2,1,3]

padics's Issues

Compiling padics-doc.pdf

I have uploaded padics-doc.pdf, compiled from padics-doc.tex as modified by R.Dodier. No problem from my side, everything ran smoothly using 'pdflatex padics-doc.tex' twice. I put the files padics-tex.tex, cas-common.sty, cas-cs.cls, thumbnails/cas-email.jpeg, and thumbnails/cas-url.jpeg from the padics repository in the same folder to run the pdflatex command above.
Using TeXLive texlive-2018.180822 compiled for x86_64.

Texinfo template file with deffn item for each padics function

Hi, I've created a Texinfo file which I think can be a good place to start writing documentation for padics. For each function in padics, I generated a skeleton of the Texinfo stuff for it. Since there are a lot of functions, it seems like this could help save some time.

To be specific, after loading padics.mac, I executed for f in functions do emitfn(f) where emitfn is defined as follows:

emitfn(f) :=
 (printf (true, "@deffn {Function} ~a (~{@var{~a}~^, ~})~%~%", op(f), args(f)),
  printf (true, "Computes FOO for ~{@var{~a}~^, ~}.~%~%", args(f)),
  printf (true, "@code{load(\"padics.mac\")} loads this function.~%~%"),
  printf (true, "Example:~%~%@c ===beg===~%@c load(\"padics.mac\");~%@c ~a~%@c ===end===~%~%", f),
  printf (true, "@end deffn~%~%"));

I pasted the resulting output into a Texinfo file and I've attached it to this issue as padics.txt, but it is really padics.texi (I had to change the name to make it acceptable to Github). I hope this is helpful to you for creating documentation for each padics function.

padics.txt