= Function collision
{title2=$x\neq x',\quad f(x)=f(x')$}
A function collision is a pair of distinct inputs $x\neq x'$ with $f(x)=f(x')$. An <injective function> has no collisions. For a two-to-one function every nonempty <fiber> has two elements and hence one unordered collision pair. Finding such a pair through an oracle is the task of <quantum collision finding>.
In the finite example under <image and preimage of a function>, the pair $\{a,b\}$ is a <function collision>: both inputs give zero. The <function> retains their shared output but loses the distinction between them. If a <finite set> has more inputs than the number of available outputs, the <pigeonhole principle> forces a <function collision>. Equal source and target <cardinalities> alone do not prevent one.
For a finite <function>, let $m_y$ be the <cardinality> of its <fiber of a function> over $y$. The number of unordered <function collisions> is $\sum_y\binom{m_y}{2}$, because each pair must lie in one common <fiber>. The example's nonempty fiber sizes are $2,1,1$, giving exactly one collision pair.
Back to article page
