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): = | ||
+ | |||
+ | '''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) : = | ||
− | + | 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 11: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.