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.
- 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.
- 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.
- 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.
- 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.
- 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.
| Symbol | Read as | Meaning |
|---|---|---|
| ¬P | not P | P is false |
| P ∧ Q | P and Q | both are true |
| P ∨ Q | P or Q | at least one is true (inclusive or) |
| P ⇒ Q | P implies Q | if P then Q; vacuously true when P is false |
| P ⇔ Q, iff | P if and only if Q | P ⇒ Q and Q ⇒ P |
| ∀x | for all x | every x satisfies what follows |
| ∃x | there exists x | at least one x does |
| ∃!x | there exists a unique x | exactly one x does |
| := or ≜ | is defined as | the left side is a new name for the right side |
| ≡ | is equivalent to | logical equivalence, identity, or congruence mod n, depending on context |
| ⊢ | proves | derivable in a formal system |
| ⊨ | models | true in a model |
| ∴ / ∵ | therefore / because | proof shorthand |
| ∎ or □ | end of proof | QED |
The order of quantifiers is everything.
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
| Symbol | Name | Contents |
|---|---|---|
| ℕ | naturals | {0, 1, 2, …} or {1, 2, …}, because authors disagree, so check the preliminaries |
| ℤ | integers | {…, −1, 0, 1, …}, from the German Zahlen |
| ℚ | rationals | fractions p/q |
| ℝ | reals | the continuum |
| ℂ | complex | a + bi |
| ℝ⁺, ℝ≥0 | positive / non-negative reals | subscripts and superscripts restrict a set |
| [n] | "bracket n" | {1, 2, …, n}, everywhere in CS and combinatorics |
Membership and operations
| Symbol | Read as | Meaning |
|---|---|---|
| x ∈ A | x in A | x is an element of A |
| A ⊆ B | A subset of B | every element of A is in B, and A may equal B |
| A ⊊ B | proper subset | A ⊆ B and A ≠ B (some authors write ⊂ for ⊆, so check) |
| ∅ | empty set | {} |
| A ∪ B | A union B | in A or B |
| A ∩ B | A intersect B | in both |
| A \ B | A minus B | in A, not in B |
| Aᶜ, Ā | complement | everything in the universe that isn't in A |
| A △ B | symmetric difference | in exactly one of A and B |
| A × B | Cartesian product | all ordered pairs (a, b) |
| Aⁿ | n-fold product | n-tuples of elements of A |
| 𝒫(A), 2A | power set | the set of all subsets of A |
| |A|, #A | cardinality | number of elements |
Set-builder notation reads "the set of all x such that…". The bar or colon in the middle means "such that".
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.
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.
| Notation | Read as | Meaning |
|---|---|---|
| g ∘ f | g after f | (g ∘ f)(x) = g(f(x)), applied right to left |
| f⁻¹ | f inverse | the 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|S | f restricted to S | same rule, smaller domain |
| BA | functions from A to B | all f : A → B, so |BA| = |B||A| |
| f(·, y) | f with a blank | a function of the dotted argument, with the others fixed |
| f ≡ c | f identically c | f(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.
// Σ: 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.
| Notation | Read as | Meaning |
|---|---|---|
| n! | n factorial | n·(n−1)···1, the number of ways to order n items |
| (n over k) | n choose k | n! / (k!(n−k)!), the number of ways to pick k of n |
| a | b | a divides b | b = ka for some integer k |
| a ∤ b | a does not divide b |
Identities worth recognising on sight:
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.
| Notation | Read as | Like | Meaning |
|---|---|---|---|
| f = O(g) | big-O | f ≤ g | f grows no faster than g (upper bound) |
| f = Ω(g) | big-Omega | f ≥ g | f grows at least as fast (lower bound) |
| f = Θ(g) | big-Theta | f = g | same growth rate (tight bound) |
| f = o(g) | little-o | f < g | f/g → 0 |
| f = ω(g) | little-omega | f > g | f/g → ∞ |
| f ~ g | asymptotic to | f ≈ g | f/g → 1, constants included |
| Õ(g) | soft-O | O(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:
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.
| Notation | Read as | Meaning |
|---|---|---|
| Pr[A], P(A) | probability of A | a number in [0, 1] |
| Pr[A | B] | A given B | Pr[A ∧ B] / Pr[B] |
| Prx~D[A] | over x drawn from D | the subscript tells you what's random |
| X ~ D | X is distributed as D | X is a random variable with distribution D |
| E[X], 𝔼[X] | expected value | the probability-weighted average |
| Var(X) | variance | E[(X − E[X])²] |
| X ⊥ Y | X independent of Y | Pr[X, Y] = Pr[X]·Pr[Y] |
| i.i.d. | independent, identically distributed | separate samples from the same distribution |
| U(S) | uniform over S | every element of S is equally likely |
| 𝒩(μ, σ²) | normal (Gaussian) | mean μ, variance σ² |
| Ber(p), Bin(n, p) | Bernoulli, binomial | a coin with bias p, and the count of heads in n flips |
| Pois(λ) | Poisson | the 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:
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.
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.
| Notation | Read as | Meaning |
|---|---|---|
| ℝⁿ | n-dimensional space | vectors of n real numbers |
| ℝm×n | m-by-n matrices | m rows, n columns |
| Aij | entry i, j | row i, column j |
| Aᵀ, A⊤ | A transpose | rows become columns |
| A† | conjugate transpose | also written A* or AH; quantum papers use it everywhere |
| A⁻¹ | A inverse | AA⁻¹ = I, which exists iff det A ≠ 0 |
| I, In | identity | 1s on the diagonal, 0 elsewhere |
| det(A) | determinant | the volume scaling factor; 0 means not invertible |
| tr(A) | trace | the sum of the diagonal |
| rank(A) | rank | the number of linearly independent rows |
| ⟨u, v⟩, u·v, uᵀv | inner product | Σ uᵢvᵢ |
| ‖v‖, ‖v‖₂ | norm | √⟨v, v⟩, i.e. the length |
| ‖v‖₁, ‖v‖∞ | 1-norm, ∞-norm | Σ|vᵢ|, and max |vᵢ| |
| A ⊗ B | tensor product | combines spaces; the core of quantum notation |
| A ⊙ B | Hadamard product | element-wise multiplication |
| u ⊥ v | orthogonal | ⟨u, v⟩ = 0 |
| span(S) | span | every 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).
| Notation | Read as | Meaning |
|---|---|---|
| ℤn, ℤ/nℤ | integers mod n | {0, …, n−1}, with + and × wrapping around |
| ℤn* | multiplicative group mod n | the elements that have an inverse, i.e. those coprime to n |
| gcd(a, b) | greatest common divisor | gcd = 1 means coprime |
| a⁻¹ mod n | inverse of a mod n | a·a⁻¹ ≡ 1 (mod n), found with extended Euclid |
| φ(n) | Euler's totient | |ℤn*| |
| 𝔽q, GF(q) | finite field of size q | q is a prime power, and 𝔽p = ℤp for a prime p |
| 𝔽q[X] | polynomials over 𝔽q | coefficients in 𝔽q, variable X |
| ⟨g⟩ | group generated by g | {g⁰, g¹, g², …} |
| ord(g) | order of g | the smallest k > 0 with gᵏ = 1 |
| G ≅ H | G isomorphic to H | same structure, different names |
| H ≤ G | subgroup | H is a subgroup of G |
The structure ladder. Each level adds rules on top of the one before.
- Group (G, ·): one associative operation, with an identity and inverses. Example: ℤn under +.
- Abelian group: a group whose operation also commutes. Example: ℤ under +.
- Ring: two operations, + and ×, where × doesn't need inverses. Example: ℤn, or polynomials with integer coefficients.
- 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.
| Notation | Read as | Meaning |
|---|---|---|
| limn→∞ aₙ | limit as n → ∞ | the value aₙ approaches |
| f′(x), df/dx | derivative of f | rate of change (a dot on top, ḟ, means a time derivative) |
| ∂f/∂x | partial derivative | how f changes when only x varies |
| ∇f | gradient ("nabla f") | the vector of all partials, which points uphill |
| ∫ab f(x) dx | integral from a to b | the area under f; dx names the variable |
| sup S, inf S | supremum, infimum | the least upper / greatest lower bound, which always exists for bounded sets, unlike max/min |
| argmaxx f(x) | argmax | the x that maximises f (you get the input, not the value) |
| ∝ | proportional to | equal 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:
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.
| Notation | Read as | Meaning |
|---|---|---|
| G = (V, E) | graph G | a set of vertices V and a set of edges E |
| n, m | by convention n = |V| and m = |E|, so "O(n + m)" means linear in the graph size | |
| {u, v}, uv | undirected edge | an edge joining u and v |
| (u, v), u → v | directed edge (arc) | an edge from u to v |
| N(v) | neighbourhood of v | the vertices adjacent to v |
| deg(v), d(v) | degree of v | the number of edges at v; directed graphs split it into in- and out-degree |
| w : E → ℝ | weight function | a cost or length on each edge |
| d(u, v) | distance | the length of a shortest path from u to v |
| G[S] | induced subgraph | the vertices in S and every edge between them |
| Kₙ | complete graph | n vertices, every pair joined |
| Δ(G), δ(G) | max / min degree | yes, Δ also means a distance elsewhere, so check |
| χ(G) | chromatic number | the 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
| Notation | Meaning |
|---|---|
| {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, xy | concatenation |
| x ⊕ y | bitwise 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 ← eandx := eboth 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.
| Letter | Name | Usually means |
|---|---|---|
| α, β | alpha, beta | parameters, weights, angles, significance levels |
| γ, Γ | gamma | a constant or gap, or the discount factor in RL; Γ is the gamma function |
| δ, Δ | delta | a small quantity or failure probability; Δ is a change, a difference or a max degree |
| ε | epsilon | a small positive number or an error, or the empty string |
| ζ | zeta | the Riemann zeta function, or a damping ratio |
| η | eta | a learning rate or an efficiency |
| θ, Θ | theta | an angle or model parameters; Θ is the tight asymptotic bound |
| κ | kappa | a condition number or a curvature |
| λ, Λ | lambda | an eigenvalue, a rate, a wavelength or a regularisation weight; Λ is a diagonal matrix of eigenvalues |
| μ | mu | a mean or a measure |
| ν | nu | a frequency |
| π, Π | pi | 3.14159…, a permutation, or a policy in RL; Π is a product |
| ρ | rho | a correlation, a density or a rate |
| σ, Σ | sigma | a standard deviation; Σ is a sum, a covariance matrix or an alphabet |
| τ | tau | a time constant or a threshold |
| φ, Φ | phi | an angle or phase, the golden ratio, or Euler's totient; Φ is the normal CDF |
| χ | chi | the chi-squared distribution (χ²), or a chromatic number |
| ψ, Ψ | psi | a wave function or quantum state |
| ω, Ω | omega | an 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
ℙ 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
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
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
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
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.