Difference between revisions of "Mathematicial notation"
(→Sets) |
(→Definitions: , fixed LaTeX) |
||
Line 39: | Line 39: | ||
'''Binomial Coefficients''': <math>\displaystyle {n\choose k} = \frac{n!}{k! (n-k)!}</math> | '''Binomial Coefficients''': <math>\displaystyle {n\choose k} = \frac{n!}{k! (n-k)!}</math> | ||
− | For two functions | + | For two functions <math>f,g: \mathbb{N} \to \mathbb{C}</math> the '''Dirichlet convolution''' <math>f*g</math> is defined as <math>f*g(n) : = \sum_{d|n} f(d) g\left(\frac{n}{d}\right)</math>. |
− | A (weak) | + | A (weak) '''multiplicative function''' <math>f: \mathbb{N} \to \mathbb{C}</math> is one such that <math>f(a\cdot b) = f(a) \cdot f(b)</math> for all <math>a,b \in \mathbb{N}</math> with <math>\gcd(a,b)=1</math>. |
+ | |||
Some special types of such functions: | Some special types of such functions: | ||
− | |||
− | |||
− | |||
− | For any | + | '''Euler's totient function''': <math>\varphi (n) = \phi (n) : = \left| \{ k \in \mathbb{N} \ : \ k \leq n , \gcd(k,n) \} \right| = \left| \mathbb{Z}_n^* \right|</math>. |
+ | |||
+ | '''Möbius' function''': <math>\mu(n): = \begin{cases} 0 & \textrm{ iff } n\; \textrm{ is not squarefree} \\ (-1)^s & \textrm{ where } s \;\textrm{ is the number of prime factors of } n \;\textrm{ otherwise} \end{cases}</math>. | ||
+ | |||
+ | '''Sum of powers of divisors''': <math>\sigma_k(n) : = \sum_{d|n} d^k</math>; often <math>\tau</math> is used for <math>\sigma_0</math>, the number of divisors, and simply <math>\sigma</math> for <math>\sigma_1</math>. | ||
+ | |||
+ | For any <math>k,n \in \mathbb{N}</math> it denotes <math>r_k(n) : = \left| \{ (a_1,a_2,...,a_k) \in \mathbb{Z}^k | \sum a_i^2 = n \} \right|</math> the '''number of representations of <math>n</math> as sum of <math>k</math> squares'''. | ||
+ | |||
+ | Let <math>a,n</math> be coprime integers. Then <math>ord_n(a)</math>, the "'''order of <math>a \mod n</math>'''" is the smallest <math>k \in \mathbb{N}</math> with <math>a^k \equiv 1 \mod n</math>. | ||
− | + | For <math>n \in \mathbb{Z}^*</math> and <math>p \in \mathbb{P}</math>, the '''<math>p</math>-adic valuation <math>v_p(n)</math>''' can be defined as the multiplicity of <math>p</math> in the factorisation of <math>n</math>, and can be extended for <math>\frac{m}{n} \in \mathbb{Q}^* , \ m,n \in \mathbb{Z}^*</math> by <math>v_p\left( \frac{m}{n} \right) = v_p(m)-v_p(n)</math>. | |
+ | Additionally often <math>v_p(0) = \infty</math> is used. | ||
− | For | + | For any function <math>f</math> we define <math>\Delta (f)(x) : = f(x+1)-f(x)</math> as the (upper) finite difference of <math>f</math>. |
− | + | Then we set <math>\Delta^0(f)(x) : = f(x)</math> and then iteratively <math>\Delta^n (f) (x) : = \Delta(\Delta^{n-1} (f)) (x)</math> for all integers <math>n \geq 1</math>. | |
− | |||
− | |||
+ | '''Legendre symbol''': for <math>a \in \mathbb{Z}</math> and odd <math>p \in \mathbb{P}</math> we define <math>\left( \frac{a}{p} \right) : = \begin{cases} 1 & \textrm{ when } x^2 \equiv a \mod p \textrm{ has a solution } x \in \mathbb{Z}_p^* \\ 0 & \textrm{ iff } p|a \\ -1 & \textrm{ when } x^2 \equiv a \mod p \textrm{ has no solution } x \in \mathbb{Z}_p \end{cases}</math> | ||
− | + | Then the '''Jacobi symbol''' for <math>a \in \mathbb{Z}</math> and odd <math>n= \prod p_i^{\nu_i}</math> (prime factorization of <math>n</math>) is defined as: <math>\left( \frac{a}{n} \right) = \prod \left( \frac{a}{p_i} \right)^{\nu_i}</math> | |
− | Then the | ||
− | + | '''Hilbert symbol''': let <math>v \in \mathbb{P} \cup \{ 0 , \infty \}</math> and <math>a,b \in \mathbb{Q}_v^*</math>. Then | |
− | + | <math> \left( a , b \right)_v : = \begin{cases} 1 & \textrm{ iff } x^2=ay^2+bz^2 \textrm{ has a nontrivial solution } (x,y,z) \in \mathbb{Q}_v^3 \\ -1 & \textrm{ otherwise} \end{cases} </math> | |
− | is the "Hilbert symbol of | + | is the "Hilbert symbol of <math>a,b</math> in respect to <math>v</math>" (nontrivial means here that not all numbers are <math>0</math>). |
− | When | + | When <math>A \subset \mathbb{N}</math>, then we can define a '''counting function''' <math>a(n) : = | \{ a \in A | a \leq n \}</math>. |
− | One special case of a counting function is the one that belongs to the primes | + | One special case of a counting function is the one that belongs to the primes <math>\mathbb{P}</math>, which is often called <math>\pi</math>. |
With counting functions, some types of densities can be defined: | With counting functions, some types of densities can be defined: | ||
Line 79: | Line 84: | ||
'''Dirichlet's density'''(does not always exist): <math>\displaystyle \delta(A) : = \lim_{s \to 1+0} \frac{\sum_{a \in A} a^{-s}}{\sum_{a \in \mathbb{N}} a^{-s}}</math> | '''Dirichlet's density'''(does not always exist): <math>\displaystyle \delta(A) : = \lim_{s \to 1+0} \frac{\sum_{a \in A} a^{-s}}{\sum_{a \in \mathbb{N}} a^{-s}}</math> | ||
− | <math>\displaystyle {}_Ld(A)</math> and <math>\displaystyle _Ud(A)</math> are equal iff the asymptotic density | + | <math>\displaystyle {}_Ld(A)</math> and <math>\displaystyle _Ud(A)</math> are equal iff the asymptotic density <math>d(A)</math> exists and all three are equal then and equal to Dirichlet's density. |
− | Often, '''density''' is meant '''in relation to some other set''' | + | Often, '''density''' is meant '''in relation to some other set''' <math>B</math> (often the primes). Then we need <math>A \subset B \subset \mathbb{N}</math> with counting functions <math> a,b </math> and simply change <math>n</math> into <math>b(n)</math> and <math>\mathbb{N}</math> into <math>B</math>: |
'''Lower asymptotic density''': <math>\displaystyle _Ld_B(A) : =\liminf_{n \to \infty} \frac{a(n)}{b(n)} </math> | '''Lower asymptotic density''': <math>\displaystyle _Ld_B(A) : =\liminf_{n \to \infty} \frac{a(n)}{b(n)} </math> |
Revision as of 12:49, 30 August 2006
Sets
: the integers (a unique factorization domain).
: the natural numbers. Unfortunately, this notation is ambiguous -- some authors use it for the positive integers, some for the nonnegative integers.
: Also an ambiguous notation, use for the positive primes or the positive integers.
: the reals (a field).
: the complex numbers (an algebraically closed and complete field).
: the
-adic numbers (a complete field); also
and
are used sometimes.
: the residues
(a ring; a field for
prime).
When is one of the sets from above, then
denotes the numbers
(when defined), analogous for
.
The meaning of
will depend on
: for most cases it denotes the invertible elements, but for
it means the nonzero integers (note that these definitions coincide in most cases).
A zero in the index, like in
, tells us that
is also included.
Definitions
For a set ,
denotes the number of elements of
.
divides
(both integers) is written as
, or sometimes as
.
Then for
,
or
is their greatest common divisor, the greatest
with
and
(
is defined as
) and
or
denotes their least common multiple, the smallest non-negative integer
such that
and
.
When
, one often says that
are called "coprime".
For to be squarefree means that there is no integer
with
. Equivalently, this means that no prime factor occurs more than once in the decomposition.
Factorial of :
Binomial Coefficients:
For two functions the Dirichlet convolution
is defined as
.
A (weak) multiplicative function
is one such that
for all
with
.
Some special types of such functions:
Euler's totient function: .
Möbius' function: .
Sum of powers of divisors: ; often
is used for
, the number of divisors, and simply
for
.
For any it denotes
the number of representations of
as sum of
squares.
Let be coprime integers. Then
, the "order of
" is the smallest
with
.
For and
, the
-adic valuation
can be defined as the multiplicity of
in the factorisation of
, and can be extended for
by
.
Additionally often
is used.
For any function we define
as the (upper) finite difference of
.
Then we set
and then iteratively
for all integers
.
Legendre symbol: for and odd
we define
Then the Jacobi symbol for and odd
(prime factorization of
) is defined as:
Hilbert symbol: let and
. Then
is the "Hilbert symbol of
in respect to
" (nontrivial means here that not all numbers are
).
When , then we can define a counting function
.
One special case of a counting function is the one that belongs to the primes
, which is often called
.
With counting functions, some types of densities can be defined:
Lower asymptotic density:
Upper asymptotic density:
Asymptotic density (does not always exist):
Shnirelman's density:
Dirichlet's density(does not always exist):
and
are equal iff the asymptotic density
exists and all three are equal then and equal to Dirichlet's density.
Often, density is meant in relation to some other set (often the primes). Then we need
with counting functions
and simply change
into
and
into
:
Lower asymptotic density:
Upper asymptotic density:
Asymptotic density (does not always exist):
Shnirelman's density:
Dirichlet's density(does not always exist):
Again the same relations as above hold.