Crate adic

Expand description

Adic number math

§Adic numbers

p-adic numbers are an alternate number system to the reals. This system is p-periodic and hierarchical. It is used throughout number theory, but it not well-known outside of pure math. This crate is partially an attempt to change that.

§Links

crates.io/adic
docs/adic
gitlab/adic
adicmath.com - our site, to learn about and play with adic numbers
crates.io/adic-shape - crate for visualizations and charts of adic numbers
wiki/P-adic_number - wikipedia for p-adic numbers

§References

Murty: Introduction to p-adic… - Introduces p-adics starting from Bernoulli numbers and interpolation; good first book
Koblitz: p-adic Numbers… - Introduces p-adics slowly while analyzing zeta functions; good first book
Gouveau: p-adic Numbers Widely recommended; likely a good first book
Roberts: A Course in p-adic Analysis - p-adics from Z_p through analytical functions; formal and thorough, fantastic

§Motivation

Adic numbers can represent any rational number as well as many numbers between them, just like the real numbers. They can be represented similarly to the reals as infinite digital expansions. Except where the reals have a finite number of digits to the left of the decimal and possibly infinite to the right (1.414...), the adics have finite digits to the right and infinite to the left (...4132.13).

assert_eq!("2314._5", UAdic::new(5, vec![4, 1, 3, 2]).to_string());
assert_eq!("2314._5", EAdic::new(5, vec![4, 1, 3, 2]).to_string());
assert_eq!("(4)11._5", EAdic::new_neg(5, vec![1, 1]).to_string());
assert_eq!("(233)4._5", EAdic::new_repeating(5, vec![4], vec![3, 3, 2]).to_string());
assert_eq!("...004123._5", ZAdic::new_approx(5, 6, vec![3, 2, 1, 4]).to_string());
assert_eq!("...0041.23_5", QAdic::new(ZAdic::new_approx(5, 6, vec![3, 2, 1, 4]), -2).to_string());

You might think this means they are “infinite” numbers, but they are not. The key difference is how a number’s size is measured.

For a number, its size is its norm, its absolute value. In the reals, the size of 4 is 4, the size of -2.31 is 2.31, etc.

Each p-adic space is linked to a prime, p. In the p-adics, the size of a number is the inverse of how many powers of p are in it: |x| = |a/b * p^v| = p^(-v). So in the 5-adics, 1, 2, 3, and 4 are all size 1, while 5, 10, 15, and 20 are size 1/5. When you represent these numbers as digital expansions in base-p, the numbers further to the left are smaller, not bigger.

let one = EAdic::new(5, vec![1]);
let two = EAdic::new(5, vec![2]);
let three = EAdic::new(5, vec![3]);
let five = EAdic::new(5, vec![0, 1]);
let ten = EAdic::new(5, vec![0, 2]);
let twenty_five = EAdic::new(5, vec![0, 0, 1]);
let six_hundred_twenty_five = EAdic::new(5, vec![0, 0, 0, 0, 1]);
assert_eq!(Ratio::new(1, 1), one.norm());
assert_eq!(Ratio::new(1, 1), two.norm());
assert_eq!(Ratio::new(1, 1), three.norm());
assert_eq!(Ratio::new(1, 5), five.norm());
assert_eq!(Ratio::new(1, 5), ten.norm());
assert_eq!(Ratio::new(1, 25), twenty_five.norm());
assert_eq!(Ratio::new(1, 625), six_hundred_twenty_five.norm());

Adic numbers are used:

to solve diophantine equations
as fundamental examples of ultrametric spaces
to form combined local/global structures, e.g. adeles and ideles
in glassy physical systems, like in replica/cavity theory
in tropical geometry

§Crate

This crate handles adic numbers, arithmetic, and calculations.

Calculations:

Adic arithmetic: Add, Sub, Mul, Div, Pow, Neg
Rootfinding, through use of hensel lifting
Polynomial, power series, and sequence manipulations
Idempotent computation for MAdic zero divisors

Adic number structs:

Struct	Type	Represents	Example
`UAdic`	Integer	Unsigned ordinary integers	86 = `321._5`
`EAdic`	Integer	Exact p-adic integers	-7/6 = `(31)2._5`
`ZAdic`	Integer	Approximate p-adic integers	sqrt(6) ~= `...24031._5`
`QAdic<A>`	Fraction	p-fractional numbers	86/5 = `32.1_5`
`PowAdic<A>`	Composite	p^n-adic numbers	86 = `3b._25`
`MAdic`	Composite	Non-prime adic numbers	86 = `...0086._10`

Functions:

Polynomial - Polynomial, enhanced with adic integer or adic number coefficients e.g. with rootfinding
PowerSeries - A power series, useful for expressing special functions e.g. the Iwasawa Log function
Variety - A collection of approximate items representing the roots of a polynomial

§Example: calculate the two varieties for 7-adic sqrt(2) to 6 digits:

use adic::{traits::AdicInteger, EAdic, Variety, ZAdic};
// Create the 7-adic number 2
let seven_adic_two = EAdic::new(7, vec![2]);
// Take the square root of seven_adic_two, to 6 "decimal places"
let sqrt_two_variety = seven_adic_two.nth_root(2, 6);
assert_eq!(Ok(Variety::new(vec![
    ZAdic::new_approx(7, 6, vec![3, 1, 2, 6, 1, 2]),
    ZAdic::new_approx(7, 6, vec![4, 5, 4, 0, 5, 4]),
])), sqrt_two_variety);
let roots = sqrt_two_variety?.into_roots().collect::<Vec<_>>();
assert_eq!("...216213._7", roots[0].to_string());
assert_eq!("...450454._7", roots[1].to_string());

§Example: 5-adic arithmetic

use adic::{traits::CanTruncate, EAdic, UAdic};
// 3 is a single digit (3) and no repeating digits
let three = EAdic::new_repeating(5, vec![3], vec![]);
// -1/6 consists only of repeating ...040404.
let neg_one_sixth = EAdic::new_repeating(5, vec![], vec![4, 0]);
// 3 - 1/6 = 17/6 is two digits 12. and then repeating 04
let seventeen_sixth = three + neg_one_sixth;
assert_eq!(EAdic::new_repeating(5, vec![2, 1], vec![4, 0]), seventeen_sixth);
assert_eq!(UAdic::new(5, vec![2, 1, 4, 0, 4, 0]), seventeen_sixth.truncation(6));

§Example: 5-adic fourth roots of unity

use num::traits::Pow;
use adic::{traits::AdicInteger, Variety, ZAdic};
// Every (odd) p-adic number space has p-1 roots of unity
let roots = ZAdic::roots_of_unity(5, 6)?;
assert_eq!(
    Variety::new(vec![
        ZAdic::new_approx(5, 6, vec![1]),
        ZAdic::new_approx(5, 6, vec![2, 1, 2, 1, 3, 4]),
        ZAdic::new_approx(5, 6, vec![3, 3, 2, 3, 1, 0]),
        ZAdic::new_approx(5, 6, vec![4, 4, 4, 4, 4, 4]),
    ]),
    roots
);
// Each root taken to the (5-1)-th power is approximately one
for root in roots.into_roots() {
    assert!(root.pow(4).is_approx_one());
}

§Future

QXAdic for a number from a finite extension of QAdic
QCAdic for a number in the algebraic closure of QAdic
CAdic, a “complex adic number”, in the norm completion of QCAdic
SAdic, a “spherically complete adic number”, in the spherical completion of QCAdic/CAdic

Re-exports§

pub use num;

Modules§

divisible: Divisible numbers
error: adic error module
function: Various functions, implementing Mapping and IndexedMapping
local_num: Traits for “local” numbers
mapping: Mapping: A general kind of function
normed: Structures with archimedian and ultrametric norms
num_adic: Adic number objects
sequence: Sequences, with emphasis on UltraNormed sequences
traits: Adic traits

Structs§

EAdic: Exact adic integer
Polynomial: Polynomial
PowerSeries: A series with a power of x multiplied by a Sequence of coefficients
QAdic: Fractional adic number
UAdic: Arbitrary precision unsigned integer
Variety: An algebraic variety, often a set of “roots” to an algebraic equation
ZAdic: Approximate adic integer

Traits§

Sequence: A general sequence of terms

Crate adic

Crate adic Copy item path

§Adic numbers

§Links

§References

§Motivation

§Crate

§Example: calculate the two varieties for 7-adic sqrt(2) to 6 digits:

§Example: 5-adic arithmetic

§Example: 5-adic fourth roots of unity

§Future

Re-exports§

Modules§

Structs§

Traits§

Crate adic