# Difference between revisions of "Mathematicial notation"

Mysmartmouth (talk | contribs) |
m (a little LaTeXing) |
||

Line 1: | Line 1: | ||

− | |||

== Sets == | == Sets == | ||

Line 31: | Line 30: | ||

<math>a</math> divides <math>b</math> (both integers) is written as <math>a|b</math> or sometimes as <math>b \vdots a</math>. | <math>a</math> divides <math>b</math> (both integers) is written as <math>a|b</math> or sometimes as <math>b \vdots a</math>. | ||

− | Then for <math>m,n \in \mathbb{Z}</math>, <math>\gcd(m,n)</math> or <math>(m,n)</math> is their | + | Then for <math>m,n \in \mathbb{Z}</math>, <math>\gcd(m,n)</math> or <math>(m,n)</math> is their '''greatest common divisor''', the greatest <math>d \in \mathbb{Z}</math> with <math>d|m</math> and <math>d|n</math> (<math>\gcd(0,0)</math> is defined as <math>0</math>) and <math>\mathrm{lcm}(m,n)</math> or <math>\left[ m,n\right]</math> denotes their [[least common multiple]], the smallest non-negative integer <math>d</math> such that <math>m|d</math> and <math>n|d</math> |

. | . | ||

When <math>\gcd(m,n)=1</math>, one often says that <math>m,n</math> are called "[[coprime]]". | When <math>\gcd(m,n)=1</math>, one often says that <math>m,n</math> are called "[[coprime]]". | ||

Line 71: | Line 70: | ||

With counting functions, some types of densities can be defined: | With counting functions, some types of densities can be defined: | ||

− | + | '''Lower asymptotic density''': <math>\displaystyle _Ld(A) : =\liminf_{n \to \infty} \frac{a(n)}{n}</math> | |

− | + | ||

− | + | '''Upper asymptotic density''': <math>\displaystyle _Ud(A) : =\limsup_{n \to \infty} \frac{a(n)}{n}</math> | |

− | + | ||

− | + | '''Asymptotic density''' (does not always exist): <math>\displaystyle d(A) : =\lim_{n \to \infty} \frac{a(n)}{n}</math> | |

− | + | ||

+ | '''Shnirelman's density''': <math>\displaystyle \sigma(A) : =\inf_{n \to \infty} \frac{a(n)}{n}</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 $d(A)$ exists and all three are equal then and equal to Dirichlet's density. | ||

+ | |||

+ | |||

+ | Often, '''density''' is meant '''in relation to some other set''' $B$ (often the primes). Then we need <math>A \subset B \subset \mathbb{N}</math> with counting functions <math> a,b </math> and simply change $n$ into <math>b(n)</math> and <math>\mathbb{N}</math> into $B$: | ||

+ | |||

+ | '''Lower asymptotic density''': <math>\displaystyle _Ld_B(A) : =\liminf_{n \to \infty} \frac{a(n)}{b(n)} </math> | ||

+ | |||

+ | '''Upper asymptotic density''': <math>\displaystyle _Ud_B(A) : =\limsup_{n \to \infty} \frac{a(n)}{b(n)} </math> | ||

+ | |||

+ | '''Asymptotic density''' (does not always exist): <math>\displaystyle d_B(A) : =\lim_{n \to \infty}{} \frac{a(n)}{b(n)} </math> | ||

+ | '''Shnirelman's density''': <math>\displaystyle \sigma_B(A) : =\inf_{n \to \infty} \frac{a(n)}{b(n)} </math> | ||

− | + | '''Dirichlet's density'''(does not always exist): <math>\displaystyle \delta_B(A) : = \lim_{s \to 1+0} \frac{\sum_{a \in A} a^{-s}}{\sum_{a \in B} a^{-s}} </math> | |

− | |||

− | |||

− | |||

− | |||

− | |||

Again the same relations as above hold. | Again the same relations as above hold. |

## Revision as of 10:24, 27 June 2006

## Sets

: the integers (a unique factorisation domain).

: the positive integers, meaning those $>0$.

: the positive primes.

: the rationals (a field).

: the reals (a field).

: the complex numbers (a algebraically closed and complete field).

: the -adic numbers (a complete field); also and is 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 this 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 $n \in \mathbb{Z}^*$ to be "[b]squarefree[/b]" means that there is no integer $k>1$ with $k^2|n$. Equivalently, this means that no prime factor occurs more than once in the decomposition.

[b]factorial[/b] of $n$: $n! : = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 3 \cdot 2 \cdot 1$
[b]binomial coefficients[/b]: $\binom{n}{k} = \frac{n!}{k! (n-k)!}$

For two functions $f,g: \mathbb{N} \to \mathbb{C}$ the [b]Dirichlet convolution[/b] $f*g$ is defined as $f*g(n) : = \sum_{d|n} f(d) g\left(\frac{n}{d}\right)$. A (weak) [b]multiplicative function[/b] $f: \mathbb{N} \to \mathbb{C}$ is one such that $f(a\cdot b) = f(a) \cdot f(b)$ for all $a,b \in \mathbb{N}$ with $\gcd(a,b)=1$. Some special types of such functions: [b]Euler's totient function[/b]: $\varphi (n) = \phi (n) : = \left| \{ k \in \mathbb{N} \ : \ k \leq n , \gcd(k,n) \} \right| = \left| \mathbb{Z}_n^* \right|$. [b]Möbius' function[/b]: $\mu(n): = \begin{cases} 0 \text{ iff } n \text{ is not squarefree} \\ (-1)^s \text{ where } s \text{ is the number of prime factors of } n \text{ otherwise} \end{cases}$. [b]Sum of powers of divisors[/b]: $\sigma_k(n) : = \sum_{d|n} d^k$; often $\tau$ is used for $\sigma_0$, the number of divisors, and simply $\sigma$ for $\sigma_1$.

For any $k,n \in \mathbb{N}$ it denotes $r_k(n) : = \left| \{ (a_1,a_2,...,a_k) \in \mathbb{Z}^k | \sum a_i^2 = n \} \right|$ the [b]number of representations of $n$ as sum of $k$ squares[/b].

Let $a,n$ be coprime integers. Then $ord_n(a)$, the "[b]order of $a \mod n$[/b]" is the smallest $k \in \mathbb{N}$ with $a^k \equiv 1 \mod n$.

For $n \in \mathbb{Z}^*$ and $p \in \mathbb{P}$, the [b]$p$-adic valuation $v_p(n)$[/b] can be defined as the multiplicity of $p$ in the factorisation of $n$, and can be extended for $\frac{m}{n} \in \mathbb{Q}^* , \ m,n \in \mathbb{Z}^*$ by $v_p\left( \frac{m}{n} \right) = v_p(m)-v_p(n)$. Additionally often $v_p(0) = \infty$ is used.

For any function $f$ we define $\Delta (f)(x) : = f(x+1)-f(x)$ as the (upper) finite difference of $f$. Then we set $\Delta^0(f)(x) : = f(x)$ and then iteratively $\Delta^n (f) (x) : = \Delta(\Delta^{n-1} (f)) (x)$ for all integers $n \geq 1$.

[b]Legendre symbol:[/b] for $a \in \mathbb{Z}$ and odd $p \in \mathbb{P}$ we define $\left( \frac{a}{p} \right) : = \begin{cases} 1 & \text{ when } x^2 \equiv a \mod p \text{ has a solution } x \in \mathbb{Z}_p^* \\ 0 & \text{ iff } p|a \\ -1 & \text{ when } x^2 \equiv a \mod p \text{ has no solution } x \in \mathbb{Z}_p \end{cases}$
Then the [b]Jacobi symbol[/b] for $a \in \mathbb{Z}$ and odd $n= \prod p_i^{v_i}$ (prime factorisation of $n$) is defined as: $\left( \frac{a}{n} \right) = \prod \left( \frac{a}{p_i} \right)^{v_i}$

[b]Hilbert symbol[/b]: let $v \in \mathbb{P} \cup \{ 0 , \infty \}$ and $a,b \in \mathbb{Q}_v^*$. Then \[ \left( a , b \right)_v : = \begin{cases} 1 & \text{ iff } x^2=ay^2+bz^2 \text{ has a nontrivial solution } (x,y,z) \in \mathbb{Q}_v^3 \\ -1 & \text{ otherwise} \end{cases} \] is the "Hilbert symbol of $a,b$ in respect to $v$" (nontrivial means here that not all numbers are $0$).

When $A \subset \mathbb{N}$, then we can define a [b]counting function[/b] $a(n) : = | \{ a \in A | a \leq n \}$.
One special case of a counting function is the one that belongs to the primes $\mathbb{P}$, which is often called $\pi$.
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 $d(A)$ exists and all three are equal then and equal to Dirichlet's density.

Often, **density** is meant **in relation to some other set** $B$ (often the primes). Then we need with counting functions and simply change $n$ into and into $B$:

**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.