hypertex/pages/INTHEORY.ht

% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\IntegerNumberTheoryFunctionsXmpTitle}{IntegerNumberTheoryFunctions}
\newcommand{\IntegerNumberTheoryFunctionsXmpNumber}{9.40}
%
% =====================================================================
\begin{page}{IntegerNumberTheoryFunctionsXmpPage}{9.40 IntegerNumberTheoryFunctions}
% =====================================================================
\beginscroll

%
%
%
%
%


The \spadtype{IntegerNumberTheoryFunctions} package contains a variety of
operations of interest to number theorists.
%-% \HDindex{number theory}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
Many of these operations deal with divisibility properties of integers.
(Recall that an integer \spad{a} divides an integer \spad{b} if there is
an integer \spad{c} such that \spad{b = a * c}.)

\xtc{
The operation \spadfunFrom{divisors}{IntegerNumberTheoryFunctions}
returns a list of the divisors of an integer.
}{
\spadpaste{div144 := divisors(144) \bound{div144}}
}
\xtc{
You can now compute the number of divisors of \spad{144} and the sum of
the divisors of \spad{144} by counting and summing the elements of the
list we just created.
}{
\spadpaste{\#(div144) \free{div144}}
}
\xtc{
}{
\spadpaste{reduce(+,div144) \free{div144}}
}

Of course, you can compute the number of divisors of an integer \spad{n},
usually denoted \spad{d(n)}, and the sum of the divisors of an integer
\spad{n}, usually denoted \spad{sigma(n)},
%-% \HDindex{sigma@{$\sigma$}}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
without ever listing the divisors of \spad{n}.

\xtc{
In \Language{}, you can simply call the operations
\spadfunFrom{numberOfDivisors}{IntegerNumberTheoryFunctions} and
\spadfunFrom{sumOfDivisors}{IntegerNumberTheoryFunctions}.
}{
\spadpaste{numberOfDivisors(144)}
}
\xtc{
}{
\spadpaste{sumOfDivisors(144)}
}

The key is that \spad{d(n)} and
\spad{sigma(n)}
are ``multiplicative functions.''
This means that when \spad{n} and \spad{m} are relatively prime, that is, when
\spad{n} and \spad{m} have no prime factor in common, then
\spad{d(nm) = d(n) d(m)} and
\spad{sigma(nm) = sigma(n) sigma(m)}.
Note that these functions are trivial to compute when \spad{n} is a prime
power and are computed for general \spad{n} from the prime factorization
of \spad{n}.
Other examples of multiplicative functions are
\spad{sigma\_k(n)}, the sum of the \eth{k} powers of
the divisors of \spad{n} and \spad{phi(n)}, the
number of integers between 1 and \spad{n} which are prime to \spad{n}.
The corresponding \Language{} operations are called
\spadfunFrom{sumOfKthPowerDivisors}{IntegerNumberTheoryFunctions} and
\spadfunFrom{eulerPhi}{IntegerNumberTheoryFunctions}.
%-% \HDindex{phi@{$\varphi$}}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
%-% \HDindex{Euler!phi function@{$\varphi$ function}}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}

An interesting function is \spad{mu(n)},
%-% \HDindex{mu@{$\mu$}}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
the Moebius mu function, defined
%-% \HDindex{Moebius@{M\"{o}bius}!mu function@{$\mu$ function}}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
as follows:
\spad{mu(1) = 1}, \spad{mu(n) = 0},
when \spad{n} is divisible by a
square, and
\spad{mu(n) = (-1) ^ k}, when \spad{n}
is the product of \spad{k} distinct primes.
The corresponding \Language{} operation is
\spadfunFrom{moebiusMu}{IntegerNumberTheoryFunctions}.
This function occurs in the following theorem:

\noindent
{\bf Theorem} (Moebius Inversion Formula): \newline
%\newline\indent{5}
Let \spad{f(n)} be a function on the positive integers and let \spad{F(n)}
be defined by
\spad{F(n) =} sum of \spad{f(n)} over \spad{d | n}
where the sum is taken over the positive divisors of \spad{n}.
Then the values of \spad{f(n)} can be recovered from the values of
\spad{F(n)}:
\spad{f(n) =} sum of \spad{mu(n) F(n/d)} over \spad{d | n},
where again the sum is taken over the positive divisors of \spad{n}.

\xtc{
When \spad{f(n) = 1}, then \spad{F(n) = d(n)}.
Thus, if you sum \spad{mu(d) d(n/d)}
over the positive divisors
\spad{d} of \spad{n}, you should always get \spad{1}.
}{
\spadpaste{f1(n) == reduce(+,[moebiusMu(d) * numberOfDivisors(quo(n,d)) for d in divisors(n)]) \bound{f1}}
}
\xtc{
}{
\spadpaste{f1(200) \free{f1}}
}
\xtc{
}{
\spadpaste{f1(846) \free{f1}}
}
\xtc{
Similarly, when \spad{f(n) = n}, then \spad{F(n) = sigma(n)}.
Thus, if you sum
\spad{mu(d) sigma (n/d)} over the positive divisors
\spad{d} of \spad{n}, you should always get \spad{n}.
}{
\spadpaste{f2(n) == reduce(+,[moebiusMu(d) * sumOfDivisors(quo(n,d)) for d in divisors(n)]) \bound{f2}}
}
\xtc{
}{
\spadpaste{f2(200) \free{f2}}
}
\xtc{
}{
\spadpaste{f2(846) \free{f2}}
}

%-% \HDindex{Moebius@{M\"{o}bius}!inversion formula}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
%-% \HDindex{Dirichlet series}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
%-% \HDindex{series!Dirichlet}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
%-% \HDindex{zeta@$\zeta$}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
%-% \HDindex{Riemann!zeta function@{$\zeta$ function}}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}

The Fibonacci numbers are defined by \spad{F(1) = F(2) = 1} and
%-% \HDindex{Fibonacci numbers}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
\spad{F(n) = F(n-1) + F(n-2)} for \spad{n = 3,4, ...}.
\xtc{
The operation \spadfunFrom{fibonacci}{IntegerNumberTheoryFunctions}
computes the \eth{n} Fibonacci number.
}{
\spadpaste{fibonacci(25)}
}
\xtc{
}{
\spadpaste{[fibonacci(n) for n in 1..15]}
}
\xtc{
Fibonacci numbers can also be expressed as sums of binomial coefficients.
}{
\spadpaste{fib(n) == reduce(+,[binomial(n-1-k,k) for k in 0..quo(n-1,2)]) \bound{fib}}
}
\xtc{
}{
\spadpaste{fib(25) \free{fib}}
}
\xtc{
}{
\spadpaste{[fib(n) for n in 1..15] \free{fib}}
}

Quadratic symbols can be computed with the operations
\spadfunFrom{legendre}{IntegerNumberTheoryFunctions} and
\spadfunFrom{jacobi}{IntegerNumberTheoryFunctions}.
The Legendre symbol
%-% \HDindex{Legendre!symbol}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
\spad{(a/p)}
is defined for integers \spad{a} and
\spad{p} with \spad{p} an odd prime number.
By definition, \spad{(a/p) = +1},
when \spad{a} is a square \spad{(mod p)},
\spad{(a/p) = -1},
when \spad{a} is not a square \spad{(mod p)}, and
\spad{(a/p) = 0},
when \spad{a} is divisible by \spad{p}.
\xtc{
You compute \spad{(a/p)}
via the command \spad{legendre(a,p)}.
}{
\spadpaste{legendre(3,5)}
}
\xtc{
}{
\spadpaste{legendre(23,691)}
}
The Jacobi symbol \spad{(a/n)}
is the usual extension of the Legendre
symbol, where \spad{n} is an arbitrary integer.
The most important property of the Jacobi symbol is the following:
if \spad{K} is a quadratic field with discriminant \spad{d} and quadratic
character \spad{chi},
then \spad{chi}\spad{(n) = (d/n)}.
Thus, you can use the Jacobi symbol
%-% \HDindex{Jacobi symbol}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
to compute, say, the class numbers of
%-% \HDindex{class number}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
imaginary quadratic fields from a standard class number formula.
%-% \HDindex{field!imaginary quadratic}{IntegerNumberTheoryFunctionsXmpPage}{9.40}{IntegerNumberTheoryFunctions}
\xtc{
This function computes the class number of the imaginary
quadratic field with discriminant \spad{d}.
}{
\spadpaste{h(d) == quo(reduce(+, [jacobi(d,k) for k in 1..quo(-d, 2)]), 2 - jacobi(d,2)) \bound{h}}
}
\xtc{
}{
\spadpaste{h(-163) \free{h}}
}
\xtc{
}{
\spadpaste{h(-499) \free{h}}
}
\xtc{
}{
\spadpaste{h(-1832) \free{h}}
}
\endscroll
\autobuttons
\end{page}
%