Advanced Number Theory
module DirichletSeries
DirichletSeries.hsA Dirichlet series is a series of the form a1/1s+a2/2s+...+an/ns+...
Dirichlet series are important in multiplicative number theory because of the way they multiply together. If (an) and (bn) are Dirichlet series, then their product (cn) is given by
cn=sum {adbn/d s.t. d divides n}.
If we consider Dirichlet series as generating functions for various multiplicative functions, we find many interesting relationships between them. For example, the Riemann zeta function is the Dirichlet series (an) where an=1 for all n. If we consider the Dirichlet series zeta(s)*zeta(s), then from the above we know that its coefficients are cn = sum {adbn/d}. But in this case am and bm are 1 for all m, so we find that cn is a sum of d(n) 1s, where d(n) is the number of divisors of n. Hence zeta(s)*zeta(s) is a Dirichlet generating function for the d (number of divisors) function.
Exports
- data DirichletSeries a = DS [a] - the type used to represent Dirichlet series, for which the arithmetic operations +, -, *, / are defined.
- coeffsDS - function to return the coefficients of a Dirichlet series. By default only 16 are displayed, so if you want more you need to use this function.
- zeta(s) - the Riemann zeta function. This function takes as argument a linear expression a*s+b, where a, b are integers with a > 0. For example we can write zeta (s-1) or zeta (2*s)
- d_DGF - defined as (zeta(s))^2 - this is the Dirichlet generating function for the d (number of divisors) function.
- sigmaDGF - defined as zeta(s) * zeta(s-1) - this is the DGF for the sigma (sum of divisors) function.
- mobiusDGF - defined as 1 / zeta(s), this is the DGF for the Mobius function.
- eulerTotientDGF - defined as zeta(s-1) / zeta(s), this is the DGF for the Euler totient function, which counts how many numbers less than n are coprime to n.
zeta s / zeta (2*s) returns DS [1,1,1,0,1,1,1,0,0,1,1,0,1,1,1,0]. This is the DGF for the function which returns 1 if a number is squarefree, 0 otherwise.
module QuadraticField
QuadraticField.hsStill under development
This module contains code for working with quadratic extension fields of the rationals, that is, fields of the form QQ(sqrt d), formed by adjoining an irrational square root to the rationals.
Exports
- data QuadraticField = QF Integer QQ QQ - QF d a b represents the quadratic number a + b sqrt d. The arithmetic operations +, -, *, / are defined.
- normQF - return the norm of a quadratic number
- isIntegerQF - return whether the number is in the ring of integers of the quadratic field
- isUnitQF - return whether the number is a unit in the ring of integers of the quadratic field
- quotRemQF - Euclidean algorithm for ring of integers of Q(sqrt d) - currently only defined for d = -11,-7,-3,-2,-1,2,3,5
- divQF, modQF, gcdQF, coprimeQF - Euclidean domain operations defined in terms of quotRemQF
- data PrimeType = Inert | Split | Ramified - the different ways in which a rational prime can decompose in Q(sqrt d)
- primeType d p - returns the decomposition type of the rational prime p in the quadratic field Q(sqrt d)
- decomposePrimeQF d p - returns the prime decomposition of p in the ring of integers of Q(sqrt d)
- zetaCoeffQF d n - returns the number of ideals of norm n in the ring of integers of Q(sqrt d)
- zetaQF d - the zeta function of QQ(sqrt d), whose coefficients count the number of ideals of norm n in the ring of integers.
- decomposePrimeQF (-1) 2 - returns [[1+i]], because in the Gaussian integers ZZ[i], the prime < 2 > ramifies to < 1+i >
- decomposePrimeQF (-1) 3 - returns [[3]], because < 3 > is inert in the Gaussian integers
- decomposePrimeQF (-1) 5 - returns [[2+i],[2-i]] because < 5 > splits as < 2+i > < 2-i >
- decomposePrimeQF (-5) 7 - returns [[7,4-sqrt-5],[7,4+sqrt-5]] - note that ZZ[sqrt (-5)] is not a principal ideal domain, and in this case the ideals are each generated by two elements.
- zetaQF (-1) returns DS [1,1,0,1,2,0,0,1,1,2,0,0,2,0,0,1]. This is because, as we have seen, 2 ramifies, so there is one ideal of norm 2; 3 is inert, so there are no ideals of norm 3 (but one of norm 9); 5 splits, so there are two ideals of norm 5; there is one ideal of norm 4 - the square of the ideal of norm 2; there are two ideals of norm 10, obtained by multiplying each of the ideals of norm 5 by the ideal of norm 2; etc
module NonArchimedean
NonArchimedean.hsThis module contains code for working with p-adic numbers - a completion of the integers or rationals using a non-archimedean metric rather than the usual metric which leads to the reals.
(See introduction to p-adic numbers for more explanation.)
Exports
data Qp - the class of p-adic rationals, for which the usual arithmetic operations +, -, *, / are defined.
toQp p x - convert the rational x to its p-adic representation.
solvePolyQp p f - use Hensel's lemma to find p-adic solutions to a polynomial with coefficients in QQ, if they exist.
normQp x - the p-adic norm logQp x - p-adic logarithm defined by power series - only converges for normQp (x-1) < 1
expQp x - p-adic exponential defined by power series - only converges for normQp x < (1/p) ^ 1/(p-1)
iwasawaLog x - continuation of log to whole of Qp*
Examples
toQp 5 (1/2) returns Qp 5^0 [3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] - alternatively, we can show this another way as:
showQp' (toQp 5 (1/2)), which returns:
"3*5^0 + 2*5^1 + 2*5^2 + 2*5^3 + 2*5^4 + 2*5^5 + 2*5^6 + 2*5^7 + 2*5^8 + 2*5^9 + 2*5^10 + 2*5^11 + 2*5^12 + 2*5^13 + 2*5^14 + 2*5^15 + O(5^16)"
solvePolyQp 5 (x^2 - 11) returns [Qp 5^0 [1,1,2,0,0,2,0,3,3,2,0,1,4,3,2,3],Qp 5^0 [4,3,2,4,4,2,4,1,1,2,4,3,0,1,2,1]], which are the 5-adic square roots of 11.
solvePolyQp 5 (x^2 + 1) returns the two 5-adic square roots of -1:
[Qp 5^0 [2,1,2,1,3,4,2,3,0,3,2,2,0,4,1,3],Qp 5^0 [3,3,2,3,1,0,2,1,4,1,2,2,4,0,3,1]]
solvePolyQp 5 (x^2 - 2) returns [], because 2 does not have square roots among the 5-adic integers.
module ModularForms
ModularForms.hsStill under development
This module contains code for investigating number-theoretic properties of modular forms.
module EllipticCurves
EllipticCurves.hsStill under development
This module contains code for investigating elliptic curves, especially over finite fields.
Exports
- data EllipticCurve a = EC a a - EC a b represents the elliptic curve y2 = x3 + a*x + b.
- data EllipticCurvePt a = Inf | P a a - points on an elliptic curve - Inf is the point at infinity, P x y is the point (x,y).
- ecAdd curve pt1 pt2 - use the group law on the curve to add two points. Not valid over fields of characteristic 2 or 3.
- ecMult curve k pt - use the group law to calculate an integer multiple of a point.
- ecfp p a b - shortcut way of defining the curve y^2 = x^3 + a*x + b over the finite field Fp
- ptfp p x y - shortcut way of defining the point (x,y) over Fp
- ptsECFp curve - list the points of an elliptic curve over Fp
- numPtsECFp curve - the number of points of an elliptic curve over Fp. For small p, we basically just count the points, but for large p we use a more sophisticated algorithm - see the code for details.
- zetaECFp - the zeta function of an elliptic curve over Fp, defined as exp (sum (Nk tk / k)), where Nk is the number of points on the curve over the finite field Fpk. However, we calculate it a different way.
- _L_EC - return the Hasse-Weil L-function of an elliptic curve
- ptsECFp (ecfp 5 0 1) returns [Inf,P 0 1,P 0 4,P 2 2,P 2 3,P 4 0] - the points of the elliptic curve y2 == x3+1 over F5
- ecAdd (ecfp 5 0 1) (ptfp 5 0 1) (ptfp 5 4 0) returns P 2 2 - the sum of (0,1) and (4,0) is (2,2)
- ecAdd (ecfp 5 0 1) (ptfp 5 0 1) (ptfp 5 0 4) returns Inf - the sum of (0,1) and (0,4) is Inf (the additive zero of the group), as they are additive inverses of one another.
- numPtsECFp (ecfp 5 0 1) returns 6, as we should expect on counting the list above.
- zetaECFp (ecfp 5 0 1) returns 1+6t+36t^2+186t^3+936t^4+... :: PowerSeries, indicating that the elliptic curve has 36 points over F25, 186 points over F125, etc.
- _L_EC (EC 0 1) returns DS [1,0,0,0,0,0,-4,0,0,0,0,0,2,0,0,0] :: DirichletSeries QQ