Logo
All Problems Random Solved Random Open
Here are some frequently used definitions and notations. Many of these were also used by Erdős, although in some cases the modern convention has changed, and in such cases I have changed the problem formulation to match. This is just an unordered list at the moment.

General

  • $f=O(g)$ or $f\ll g$ means there exists some absolute constant $C>0$ such that $\lvert f(x)\rvert\leq Cg(x)$ for all sufficiently large $x$. If the constant depends on some parameter this is indicated by subscripts, such as $f=O_k(g)$.
  • $f=o(g)$ means for all $\epsilon>0$ we have $\lvert f(x)\rvert\leq \epsilon g(x)$ for all sufficiently large $x$.
  • A sequence $a_1\leq a_2\leq \cdots$ is lacunary if there exists some $\lambda > 1$ such that $a_{i+1}\geq \lambda a_i$ for all $i\geq 1$.

Combinatorics and Graph Theory

  • If $n\geq 1$ and $G$ is a finite graph then $\mathrm{ex}(n;G)$ is the maximum number of edges that a graph on $n$ vertices without $G$ as a subgraph can contain.
  • If $k\geq 1$ then $R(k)$ is the smallest $N$ such that any 2-colouring of the edges of $K_N$ contains a monochromatic $K_k$.
  • More generally, for any finite graphs $G,H$ we write $R(G,H)$ for the smallest $N$ such that any $2$-colouring of the edges of $K_N$ contains either a red $G$ or a blue $H$. If $G=H$ we just write $R(G)$.
  • Let $r\geq 2$. The hypergraph Ramsey number $R_r(k)$ is the smallest $N$ such that any 2-colouring of the edges of the $r$-uniform hypergraph on $N$ vertices contains a monochromatic copy of the complete $r$-uniform hypergraph on $k$ vertices.

Number Theory

  • The (natural) density of a set $A\subseteq \mathbb{N}$ is \[d(A)=\lim_{N\to \infty}\frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N},\] when this limit exists. The upper and lower density are this with $\lim$ replaced by $\limsup$ and $\liminf$ respectively. The Schnirelmann density $d_s(A)$ is this with $\lim$ replaced by $\inf$.
  • A Sidon set is a set such that the only solutions to $a+b=c+d$ are when $\{a,b\}=\{c,d\}$.
  • If $f,g$ are functions then \[f\ast g(n) = \sum_{a+b=n}f(a)g(b)\] and \[f\circ g(n) = \sum_{a-b=n}f(a)\overline{g(b)}.\] In particular if $A$ is a set then $1_A\ast 1_A(n)$ counts the number of representations of $n$ as a sum of elements from $A$ and $1_A\circ 1_A(n)$ the number of representations as a difference.
  • A set $A\subseteq \mathbb{N}$ is an additive basis of order $r$ if all sufficiently large integers are the sum of at most $r$ integers from $A$.
  • For $A\subseteq\mathbb{N}$ we write \[P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}.\] If $P(A)$ contains all sufficiently large integers then $A$ is complete. If $P(A)$ contains an infinite arithmetic progression then $A$ is subcomplete. If $A\backslash B$ is complete for any finite set $B$ then $A$ is strongly complete.