A Crash Course in Maths Notation

for reading papers without guessing

This is a cheat sheet for reading research papers. It's long, so skim through just whatever you need.

How to read notation

Every symbol expands into a sentence, and every paper defines its own dialect in a "Notation" or "Preliminaries" section. Read that section first, every time, even when it looks routine. That's where the author tells you whether ℕ starts at 0 or 1.

  1. Expand it aloud. Turn each formula into an English sentence before you move on. If you can't, stop there, because the rest of the proof depends on it.
  2. Find the type of every symbol. Is x a number, a vector, a set, a function, a distribution or an algorithm? Most confusion is a type error in your head.
  3. Check the quantifiers. "For every x there is a y" and "there is a y for every x" are different claims, and the order matters.
  4. Plug in a tiny example. Use n = 2, a 2×2 matrix, or a 3-bit string. Abstraction falls apart quickly once you try one concrete case.
  5. Expect overloading. |x| can mean an absolute value, a string length or a set size. Context and the preliminaries decide which.

Formulas below are typeset the way papers typeset them. If they show up as raw TeX, that's the source the author actually wrote, which is also worth learning to recognise.

Logic and quantifiers

Logic symbols are the grammar of every theorem, and misreading one flips the meaning of the whole statement.

SymbolRead asMeaning
¬Pnot PP is false
P ∧ QP and Qboth are true
P ∨ QP or Qat least one is true (inclusive or)
P ⇒ QP implies Qif P then Q; vacuously true when P is false
P ⇔ Q, iffP if and only if QP ⇒ Q and Q ⇒ P
∀xfor all xevery x satisfies what follows
∃xthere exists xat least one x does
∃!xthere exists a unique xexactly one x does
:= or ≜is defined asthe left side is a new name for the right side
≡is equivalent tological equivalence, identity, or congruence mod n, depending on context
⊢provesderivable in a formal system
⊨modelstrue in a model
∴ / ∵therefore / becauseproof shorthand
∎ or □end of proofQED

The order of quantifiers is everything.

$$\forall x \, \exists y : y > x \qquad \text{vs} \qquad \exists y \, \forall x : y > x$$

The first says "for every number there's a bigger one", which is true for the integers. The second says "there's one number bigger than all numbers", which is false. The symbols are the same, but swapping their order reverses whether the statement is true.

Negation flips quantifiers. ¬(∀x P(x)) ⇔ ∃x ¬P(x), and ¬(∃x P(x)) ⇔ ∀x ¬P(x). You use this to build counterexamples and to read proofs by contradiction.

Contrapositive. P ⇒ Q is equivalent to ¬Q ⇒ ¬P. Many proofs quietly prove the contrapositive instead and assume you'll notice.

Prose abbreviations: s.t. means "such that". w.r.t. means "with respect to". WLOG means "without loss of generality", i.e. the other cases are symmetric. resp. means "respectively". w.h.p. means "with high probability". a.s. means "almost surely".

Sets

Almost every definition in a paper starts with "let X be the set of…", so set notation is the vocabulary everything else is written in.

Standard number sets

SymbolNameContents
ℕnaturals{0, 1, 2, …} or {1, 2, …}, because authors disagree, so check the preliminaries
ℤintegers{…, −1, 0, 1, …}, from the German Zahlen
ℚrationalsfractions p/q
ℝrealsthe continuum
ℂcomplexa + bi
ℝ⁺, ℝ≥0positive / non-negative realssubscripts and superscripts restrict a set
[n]"bracket n"{1, 2, …, n}, everywhere in CS and combinatorics

Membership and operations

SymbolRead asMeaning
x ∈ Ax in Ax is an element of A
A ⊆ BA subset of Bevery element of A is in B, and A may equal B
A ⊊ Bproper subsetA ⊆ B and A ≠ B (some authors write ⊂ for ⊆, so check)
∅empty set{}
A ∪ BA union Bin A or B
A ∩ BA intersect Bin both
A \ BA minus Bin A, not in B
Aᶜ, Ācomplementeverything in the universe that isn't in A
A △ Bsymmetric differencein exactly one of A and B
A × BCartesian productall ordered pairs (a, b)
Aⁿn-fold productn-tuples of elements of A
𝒫(A), 2Apower setthe set of all subsets of A
|A|, #Acardinalitynumber of elements

Set-builder notation reads "the set of all x such that…". The bar or colon in the middle means "such that".

$$E = \{\, x \in \mathbb{Z} : x \bmod 2 = 0 \,\} \qquad S = \{\, f(x) \mid x \in A \,\}$$

The left one is the even integers. The right one is the image of A under f, meaning every value f(x) for x in A.

Tuples vs sets. (a, b) is ordered and allows repeats, while {a, b} is unordered and has no repeats. A graph is written G = (V, E) as a tuple because the order tells you which part is the vertices and which is the edges.

Intervals. [a, b] includes both ends, (a, b) excludes both, and [a, b) includes only a. Some European texts write ]a, b[ for (a, b). And yes, (a, b) also means a pair, so context decides.

Quick sanity check: |A × B| = |A|·|B| and |𝒫(A)| = 2|A|, which is why the power set is also written 2A.

Functions and relations

A function signature in maths reads exactly like a type signature in code, with the domain going in and the codomain coming out.

$$f : A \to B, \qquad x \mapsto x^2$$

Read it as "f maps A to B, sending x to x squared." The arrow → joins sets, which play the role of types, and the barred arrow ↦ joins elements, which play the role of values. As a signature it's just f(x: A) -> B, with a body of return x * x.

NotationRead asMeaning
g ∘ fg after f(g ∘ f)(x) = g(f(x)), applied right to left
f⁻¹f inversethe inverse function, which exists only if f is a bijection
f⁻¹(S)preimage of S{x : f(x) ∈ S}, which exists for any f
f(S)image of S{f(x) : x ∈ S}
f|Sf restricted to Ssame rule, smaller domain
BAfunctions from A to Ball f : A → B, so |BA| = |B||A|
f(·, y)f with a blanka function of the dotted argument, with the others fixed
f ≡ cf identically cf(x) = c for every x

Kinds of function.

  • Injective (one-to-one) means different inputs give different outputs. Hash functions aren't injective, which is why collisions exist.
  • Surjective (onto) means every element of B is hit by some input.
  • Bijective means both, so f has an inverse. A permutation is a bijection from a set to itself.

Handy special functions.

  • ⌊x⌋ is the floor (round down), ⌈x⌉ is the ceiling (round up), and ⌊x⌉ rounds to the nearest integer.
  • 𝟙[P] is the indicator, which is 1 if P is true and 0 otherwise. It's also written [P] (the Iverson bracket).
  • In CS, log x usually means base 2, while in maths it usually means base e. ln is always base e, and lg is base 2.

Relations. A relation R on A is a subset of A × A, written a R b. An equivalence relation (~ or ≡) is reflexive, symmetric and transitive. It splits A into classes [a], and A/~ is the set of those classes. A partial order (≤ or ⪯) is reflexive, antisymmetric and transitive.

Sums, products and indices

A big Σ is just a for-loop with an accumulator. Once you read it that way, most scary formulas turn into three lines of code.

$$\sum_{i=1}^{n} a_i = a_1 + a_2 + \dots + a_n \qquad \prod_{i=1}^{n} a_i = a_1 \cdot a_2 \cdots a_n$$
// Σ: start at 0, keep adding
sum ← 0
for i ← 1 to n: sum ← sum + a[i]

// Π: start at 1, keep multiplying
prod ← 1
for i ← 1 to n: prod ← prod × a[i]
  • Σi ∈ S loops over the elements of the set S.
  • Σi<j loops over every pair with i less than j, which is a double loop.
  • Σx with no bounds means "over everything sensible", usually the whole domain.
  • Σd | n loops over the divisors of n.
  • An empty sum is 0 and an empty product is 1. That's why 0! = 1.

The same pattern works with other operators: ⋃ for a union of many sets, ⋂ for intersection, ⨁ for a direct sum (or for XOR-ing many values), and max or min taken over an index.

Subscripts and superscripts. xi is the i-th item, and xij is row i, column j. Superscripts are ambiguous. x² is a square, but x(k) with parentheses is usually the k-th iterate or k-th sample, not a power.

NotationRead asMeaning
n!n factorialn·(n−1)···1, the number of ways to order n items
(n over k)n choose kn! / (k!(n−k)!), the number of ways to pick k of n
a | ba divides bb = ka for some integer k
a ∤ ba does not divide b

Identities worth recognising on sight:

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} \qquad \sum_{i=0}^{n} r^i = \frac{r^{n+1}-1}{r-1} \qquad \sum_{k=0}^{n} \binom{n}{k} = 2^n$$

Asymptotics: O, Ω, Θ and friends

Asymptotic notation compares how fast functions grow as n → ∞, ignoring constants and small inputs. Think of the five main symbols as ≤, ≥, =, < and >, applied to growth rates.

NotationRead asLikeMeaning
f = O(g)big-Of ≤ gf grows no faster than g (upper bound)
f = Ω(g)big-Omegaf ≥ gf grows at least as fast (lower bound)
f = Θ(g)big-Thetaf = gsame growth rate (tight bound)
f = o(g)little-of < gf/g → 0
f = ω(g)little-omegaf > gf/g → ∞
f ~ gasymptotic tof ≈ gf/g → 1, constants included
Õ(g)soft-OO(g), ignoring log factors

The formal definition of big-O is worth reading slowly once, because it's the template for a lot of other definitions:

$$f(n) = O(g(n)) \iff \exists\, c > 0,\ \exists\, n_0 \ \ \forall n \ge n_0 : \ |f(n)| \le c \cdot g(n)$$

Read it as "there's a constant c and a starting point n₀ such that, past n₀, f is always at most c times g." Look at the quantifier order. You choose c and n₀ first, and then they have to work for every larger n.

The equals sign is lying to you. f = O(g) really means f ∈ O(g), where O(g) is a set of functions. So O(n) = O(n²) is true, but O(n²) = O(n) is false. The "=" only goes one way.

O inside expressions. n² + O(n) means "n² plus some function that's at most linear". 2O(n) means "2 raised to something at most linear", which is a much bigger class than O(2ⁿ).

Growth ladder. Each of these eventually dominates the one before it: 1 < log n < √n < n < n log n < n² < nk < 2ⁿ < n! < nⁿ.

Complexity extras.

  • poly(n) means some polynomial in n, with the degree unspecified. "Efficient" usually means polynomial time.
  • polylog(n) means (log n)c for some constant c.
  • P, NP, BPP and PSPACE are classes of problems, usually set in sans-serif or bold. "L ∈ NP" means the problem L is in NP.
  • A ≤p B means A reduces to B in polynomial time, so B is at least as hard as A.

Probability

Randomised algorithms, machine learning, networking and statistics papers are all full of statements about probabilities. This is the section to know cold.

NotationRead asMeaning
Pr[A], P(A)probability of Aa number in [0, 1]
Pr[A | B]A given BPr[A ∧ B] / Pr[B]
Prx~D[A]over x drawn from Dthe subscript tells you what's random
X ~ DX is distributed as DX is a random variable with distribution D
E[X], 𝔼[X]expected valuethe probability-weighted average
Var(X)varianceE[(X − E[X])²]
X ⊥ YX independent of YPr[X, Y] = Pr[X]·Pr[Y]
i.i.d.independent, identically distributedseparate samples from the same distribution
U(S)uniform over Severy element of S is equally likely
𝒩(μ, σ²)normal (Gaussian)mean μ, variance σ²
Ber(p), Bin(n, p)Bernoulli, binomiala coin with bias p, and the count of heads in n flips
Pois(λ)Poissonthe number of events in an interval at average rate λ

The subscript tells you what's random. This is the most common source of confusion, so read it carefully:

$$\Pr_{(x, y) \sim \mathcal{D}} \left[ h(x) \neq y \right]$$

Read it as "the probability, over a random example (x, y) drawn from the distribution 𝒟, that the predictor h gets the label wrong." That's the error rate of a classifier. Some papers put the randomness after a colon inside the brackets instead.

Core rules. From left to right: the union bound (used in practically every proof), linearity of expectation (which holds even without independence) and Bayes' rule.

$$\Pr[A \cup B] \le \Pr[A] + \Pr[B] \qquad \mathbb{E}[X+Y] = \mathbb{E}[X] + \mathbb{E}[Y] \qquad \Pr[A \mid B] = \frac{\Pr[B \mid A]\Pr[A]}{\Pr[B]}$$

Comparing distributions. Δ(P, Q) or dTV(P, Q) is the statistical (total variation) distance. DKL(P ‖ Q) is the Kullback–Leibler divergence, which measures how badly Q approximates P and isn't symmetric. P ≈ Q means "close", and the paper will say in what sense.

Linear algebra

Here the font tells you the type. A bold lowercase v is a vector, a bold uppercase A is a matrix, and a plain italic x is a scalar. Machine learning, graphics, signal processing and quantum computing papers are written almost entirely in this notation.

NotationRead asMeaning
ℝⁿn-dimensional spacevectors of n real numbers
ℝm×nm-by-n matricesm rows, n columns
Aijentry i, jrow i, column j
Aᵀ, A⊤A transposerows become columns
A†conjugate transposealso written A* or AH; quantum papers use it everywhere
A⁻¹A inverseAA⁻¹ = I, which exists iff det A ≠ 0
I, Inidentity1s on the diagonal, 0 elsewhere
det(A)determinantthe volume scaling factor; 0 means not invertible
tr(A)tracethe sum of the diagonal
rank(A)rankthe number of linearly independent rows
⟨u, v⟩, u·v, uᵀvinner productΣ uᵢvᵢ
‖v‖, ‖v‖₂norm√⟨v, v⟩, i.e. the length
‖v‖₁, ‖v‖∞1-norm, ∞-normΣ|vᵢ|, and max |vᵢ|
A ⊗ Btensor productcombines spaces; the core of quantum notation
A ⊙ BHadamard productelement-wise multiplication
u ⊥ vorthogonal⟨u, v⟩ = 0
span(S)spanevery linear combination of the vectors in S

Eigenvalues. Av = λv says that A only scales v, by a factor λ. v is the eigenvector and λ is its eigenvalue.

Matrix-vector product as code. (Av)ᵢ = Σⱼ Aᵢⱼvⱼ, so each output entry is the dot product of one row of A with v.

Dirac (bra-ket) notation is what you'll see in quantum computing and physics papers. |ψ⟩ ("ket psi") is a column vector, i.e. a quantum state. ⟨ψ| ("bra psi") is its conjugate transpose. ⟨φ|ψ⟩ is the inner product of the two, and |ψ⟩⟨ψ| is an outer product, a matrix that projects onto ψ. The computational basis is |0⟩, |1⟩, and the Hadamard basis is |+⟩, |−⟩.

Modular arithmetic and algebra

Number theory, coding theory and cryptography all work in finite structures, and papers name those structures in one or two symbols. Learning these few will save you pages of confusion.

"mod" has two meanings. As an operator, 17 mod 5 = 2 is the remainder. Watch out with negatives: the % operator in C-family languages keeps the sign, so −3 % 5 is −3, while the maths answer is 2. As a relation, a ≡ b (mod n) means n divides a − b, so 17 ≡ 2 ≡ −3 (mod 5).

NotationRead asMeaning
ℤn, ℤ/nℤintegers mod n{0, …, n−1}, with + and × wrapping around
ℤn*multiplicative group mod nthe elements that have an inverse, i.e. those coprime to n
gcd(a, b)greatest common divisorgcd = 1 means coprime
a⁻¹ mod ninverse of a mod na·a⁻¹ ≡ 1 (mod n), found with extended Euclid
φ(n)Euler's totient|ℤn*|
𝔽q, GF(q)finite field of size qq is a prime power, and 𝔽p = ℤp for a prime p
𝔽q[X]polynomials over 𝔽qcoefficients in 𝔽q, variable X
⟨g⟩group generated by g{g⁰, g¹, g², …}
ord(g)order of gthe smallest k > 0 with gᵏ = 1
G ≅ HG isomorphic to Hsame structure, different names
H ≤ GsubgroupH is a subgroup of G

The structure ladder. Each level adds rules on top of the one before.

  1. Group (G, ·): one associative operation, with an identity and inverses. Example: ℤn under +.
  2. Abelian group: a group whose operation also commutes. Example: ℤ under +.
  3. Ring: two operations, + and ×, where × doesn't need inverses. Example: ℤn, or polynomials with integer coefficients.
  4. Field: a ring where every non-zero element has a multiplicative inverse. Example: 𝔽p, ℚ or ℝ.

Additive vs multiplicative writing. The same kind of group can be written additively, as a + b and n·a ("a added to itself n times"), or multiplicatively, as ab and aⁿ. It's only a choice of notation, but it changes how every formula after it looks.

Quotients. A/B means "A, with elements that differ by something in B treated as the same". ℤ/nℤ is the integers with every multiple of n collapsed to 0, which is exactly "mod n".

Calculus and analysis

You mostly need these for machine learning, information theory, physics and signal-processing papers. Knowing the notation matters more than knowing the techniques.

NotationRead asMeaning
limn→∞ aₙlimit as n → ∞the value aₙ approaches
f′(x), df/dxderivative of frate of change (a dot on top, ḟ, means a time derivative)
∂f/∂xpartial derivativehow f changes when only x varies
∇fgradient ("nabla f")the vector of all partials, which points uphill
∫ab f(x) dxintegral from a to bthe area under f; dx names the variable
sup S, inf Ssupremum, infimumthe least upper / greatest lower bound, which always exists for bounded sets, unlike max/min
argmaxx f(x)argmaxthe x that maximises f (you get the input, not the value)
∝proportional toequal up to a constant factor
≪, ≫much less / greater than

max vs argmax is a classic trip-up. For f(x) = −(x − 3)², max f = 0 but argmax f = 3.

The ε–δ definition of a limit. The same quantifier shape turns up all over analysis, so it's worth reading slowly:

$$\lim_{x \to a} f(x) = L \iff \forall \varepsilon > 0 \ \exists \delta > 0 \ \forall x : 0 < |x - a| < \delta \Rightarrow |f(x) - L| < \varepsilon$$

Read it as "however close (ε) you demand f be to L, there's a neighbourhood (δ) around a where it's at least that close."

Information theory.

  • H(X) is the Shannon entropy, −Σ p(x) log p(x), measured in bits when the log is base 2.
  • H∞(X) is the min-entropy, −log maxx Pr[X = x]. It measures how hard X is to guess in one try.
  • I(X; Y) is the mutual information, and H(X | Y) is the conditional entropy.

Graphs

Networks, compilers, databases and scheduling papers all reduce problems to graphs, and graph notation is compact enough to be confusing.

NotationRead asMeaning
G = (V, E)graph Ga set of vertices V and a set of edges E
n, mby convention n = |V| and m = |E|, so "O(n + m)" means linear in the graph size
{u, v}, uvundirected edgean edge joining u and v
(u, v), u → vdirected edge (arc)an edge from u to v
N(v)neighbourhood of vthe vertices adjacent to v
deg(v), d(v)degree of vthe number of edges at v; directed graphs split it into in- and out-degree
w : E → ℝweight functiona cost or length on each edge
d(u, v)distancethe length of a shortest path from u to v
G[S]induced subgraphthe vertices in S and every edge between them
Kₙcomplete graphn vertices, every pair joined
Δ(G), δ(G)max / min degreeyes, Δ also means a distance elsewhere, so check
χ(G)chromatic numberthe fewest colours that colour G with no edge joining two vertices of the same colour

A graph is often stored as an adjacency matrix A, where Auv = 1 if there's an edge from u to v. That's where graph theory and linear algebra meet: (Ak)uv counts the walks of length k from u to v.

Computer science conventions

CS papers add a layer of programming-like notation on top of the maths: strings, algorithms as objects, and pseudocode.

Strings and bits

NotationMeaning
{0,1}ⁿall bit strings of length n
{0,1}*all finite bit strings, of any length, including the empty one
Σ*, Σ⁺all strings over the alphabet Σ, and the non-empty ones only
εthe empty string (elsewhere ε is a small number, so be careful)
x ‖ y, xyconcatenation
x ⊕ ybitwise XOR
|x|length of x
x[i], xᵢthe i-th symbol (0- or 1-indexed, so check)
1ⁿn ones, i.e. n written in unary, so that an algorithm's running time can be measured in n
L(M)the language of M: the set of strings the machine or grammar M accepts
⊥"bottom": failure, an undefined result, or "no answer"

Algorithms and pseudocode

  • x ← e and x := e both mean assignment. Papers use ← so that = can stay a comparison.
  • y ← A(x) means run algorithm A on input x and call the output y. If A is randomised, y is a random variable.
  • Algorithm names are usually set in small caps or sans-serif, e.g. Dijkstra(G, s).
  • AO means A has oracle access to O. It can query O as a black box and get answers in one step, without seeing how O works.
  • "Returns ⊥" means the algorithm reports failure.

Greek letters and what they usually mean

Greek letters are just variable names, but every field has its habits. Knowing them lets you guess a symbol's type before you find its definition.

LetterNameUsually means
α, βalpha, betaparameters, weights, angles, significance levels
γ, Γgammaa constant or gap, or the discount factor in RL; Γ is the gamma function
δ, Δdeltaa small quantity or failure probability; Δ is a change, a difference or a max degree
εepsilona small positive number or an error, or the empty string
ζzetathe Riemann zeta function, or a damping ratio
ηetaa learning rate or an efficiency
θ, Θthetaan angle or model parameters; Θ is the tight asymptotic bound
κkappaa condition number or a curvature
λ, Λlambdaan eigenvalue, a rate, a wavelength or a regularisation weight; Λ is a diagonal matrix of eigenvalues
μmua mean or a measure
νnua frequency
π, Πpi3.14159…, a permutation, or a policy in RL; Π is a product
ρrhoa correlation, a density or a rate
σ, Σsigmaa standard deviation; Σ is a sum, a covariance matrix or an alphabet
τtaua time constant or a threshold
φ, Φphian angle or phase, the golden ratio, or Euler's totient; Φ is the normal CDF
χchithe chi-squared distribution (χ²), or a chromatic number
ψ, Ψpsia wave function or quantum state
ω, Ωomegaan angular frequency; Ω is the asymptotic lower bound or a sample space

Other alphabets show up too: calligraphic 𝒜, 𝒟 and ℒ for families, distributions and loss functions, fraktur 𝔤 for Lie algebras and other algebraic objects, and the Hebrew ℵ₀ ("aleph-null") for the size of ℕ.

Some Examples

1. A conjecture in pure logic

$$\forall n \in \mathbb{N} : \big( n > 2 \wedge 2 \mid n \big) \Rightarrow \exists\, p, q \in \mathbb{P} : n = p + q$$

ℙ is the set of primes. "Every even number greater than 2 is the sum of two primes." That's Goldbach's conjecture, still unproven, in one line.

2. The handshake lemma

$$\sum_{v \in V} \deg(v) = 2\,|E|$$

Add up the degree of every vertex and you get twice the number of edges, because each edge touches exactly two vertices and gets counted once at each end.

3. Gradient descent

$$\theta_{t+1} = \theta_t - \eta \, \nabla_\theta \mathcal{L}(\theta_t), \qquad \mathcal{L}(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell\big(f_\theta(x_i), y_i\big)$$

To get the next parameters, take the current ones and step a distance η (the learning rate) against the gradient of the loss. The loss ℒ is the average, over n training examples, of how wrong the model fθ is on each one.

4. A complexity claim

$$T(n) = 2T(n/2) + O(n) \ \Rightarrow\ T(n) = \Theta(n \log n)$$

An algorithm that splits its input in half, recurses on both halves and does linear extra work (merge sort) takes time that grows like n log n, tightly.

5. Markov's inequality

$$X \ge 0,\ a > 0 \ \Rightarrow\ \Pr[X \ge a] \le \frac{\mathbb{E}[X]}{a}$$

If a random variable is never negative, the chance it reaches at least a is at most its average divided by a. For example, if the average response time is 100 ms, at most 10% of requests take 1 s or more.

When you get stuck

If a symbol isn't here, check the paper's own preliminaries first. If you want the TeX behind it, Detexify lets you draw the symbol and gives you the command, and the "TeX source" download on arXiv shows you exactly how any formula was written.

Happy studying

back