Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mathematicial notation"

(→‎Definitions: , fixed LaTeX)
m
Line 61: Line 61:
  
  
−
'''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>
+
'''Legendre symbol''': for <math>a \in \mathbb{Z}</math> and [[odd integer | 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 '''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>

Revision as of 15:58, 12 October 2006

Sets

$\displaystyle \mathbb{Z}$: the integers (a unique factorization domain).

$\mathbb{N}$: the natural numbers. Unfortunately, this notation is ambiguous -- some authors use it for the positive integers, some for the nonnegative integers.

$\mathbb{P}$: Also an ambiguous notation, use for the positive primes or the positive integers.

$\mathbb{Q}$: the rationals (a field).

$\mathbb{R}$: the reals (a field).

$\mathbb{C}$: the complex numbers (an algebraically closed and complete field).

$\mathbb{Q}_p$: the $p$-adic numbers (a complete field); also $\mathbb{Q}_0 : =\mathbb{Q}$ and $\mathbb{Q}_\infty : = \mathbb{R}$ are used sometimes.

$\mathbb{Z}_n = \mathbb{Z} / n \mathbb{Z}$: the residues $\mod n$ (a ring; a field for $n$ prime).

When $M$ is one of the sets from above, then $M^+$ denotes the numbers $>0$ (when defined), analogous for $M^-$. The meaning of $M^*$ will depend on $M$: for most cases it denotes the invertible elements, but for $\displaystyle \mathbb{Z}$ it means the nonzero integers (note that these definitions coincide in most cases). A zero in the index, like in $M_0^+$, tells us that $0$ is also included.

Definitions

For a set $M$, $|M|=\# M$ denotes the number of elements of $M$.

$a$ divides $b$ (both integers) is written as $a|b$, or sometimes as $b \vdots a$. Then for $m,n \in \mathbb{Z}$, $\gcd(m,n)$ or $(m,n)$ is their greatest common divisor, the greatest $d \in \mathbb{Z}$ with $\displaystyle d|m$ and $\displaystyle d|n$ ($\displaystyle \gcd(0,0)$ is defined as $\displaystyle 0$) and $\displaystyle \mathrm{lcm}(m,n)$ or $\displaystyle \left[ m,n\right]$ denotes their least common multiple, the smallest non-negative integer $\displaystyle d$ such that $\displaystyle m|d$ and $\displaystyle n|d$ . When $\displaystyle \gcd(m,n)=1$, one often says that $\displaystyle m,n$ are called "coprime".

For $n \in \mathbb{Z}^*$ to be squarefree 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.


Factorial of $n$: $\displaystyle n! : = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 3 \cdot 2 \cdot 1$

Binomial Coefficients: $\displaystyle {n\choose k} = \frac{n!}{k! (n-k)!}$

For two functions $f,g: \mathbb{N} \to \mathbb{C}$ the Dirichlet convolution $f*g$ is defined as $f*g(n) : = \sum_{d|n} f(d) g\left(\frac{n}{d}\right)$. A (weak) multiplicative function $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:

Euler's totient function: $\varphi (n) = \phi (n) : = \left| \{ k \in \mathbb{N} \ : \ k \leq n , \gcd(k,n) \} \right| = \left| \mathbb{Z}_n^* \right|$.

Möbius' function: $\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}$.

Sum of powers of divisors: $\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 number of representations of $n$ as sum of $k$ squares.

Let $a,n$ be coprime integers. Then $ord_n(a)$, the "order of $a \mod n$" 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 $p$-adic valuation $v_p(n)$ 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$.


Legendre symbol: for $a \in \mathbb{Z}$ and odd $p \in \mathbb{P}$ we define $\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}$

Then the Jacobi symbol for $a \in \mathbb{Z}$ and odd $n= \prod p_i^{\nu_i}$ (prime factorization of $n$) is defined as: $\left( \frac{a}{n} \right) = \prod \left( \frac{a}{p_i} \right)^{\nu_i}$

Hilbert symbol: let $v \in \mathbb{P} \cup \{ 0 , \infty \}$ and $a,b \in \mathbb{Q}_v^*$. Then $\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}$ 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 counting function $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: $\displaystyle _Ld(A) : =\liminf_{n \to \infty} \frac{a(n)}{n}$

Upper asymptotic density: $\displaystyle _Ud(A) : =\limsup_{n \to \infty} \frac{a(n)}{n}$

Asymptotic density (does not always exist): $\displaystyle d(A) : =\lim_{n \to \infty} \frac{a(n)}{n}$

Shnirelman's density: $\displaystyle \sigma(A) : =\inf_{n \to \infty} \frac{a(n)}{n}$

Dirichlet's density(does not always exist): $\displaystyle \delta(A) : = \lim_{s \to 1+0} \frac{\sum_{a \in A} a^{-s}}{\sum_{a \in \mathbb{N}} a^{-s}}$

$\displaystyle {}_Ld(A)$ and $\displaystyle _Ud(A)$ 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 $A \subset B \subset \mathbb{N}$ with counting functions $a,b$ and simply change $n$ into $b(n)$ and $\mathbb{N}$ into $B$:

Lower asymptotic density: $\displaystyle _Ld_B(A) : =\liminf_{n \to \infty} \frac{a(n)}{b(n)}$

Upper asymptotic density: $\displaystyle _Ud_B(A) : =\limsup_{n \to \infty} \frac{a(n)}{b(n)}$

Asymptotic density (does not always exist): $\displaystyle d_B(A) : =\lim_{n \to \infty}{} \frac{a(n)}{b(n)}$

Shnirelman's density: $\displaystyle \sigma_B(A) : =\inf_{n \to \infty} \frac{a(n)}{b(n)}$

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

Again the same relations as above hold.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mathematicial_notation&oldid=10286"