DefinitionDefinition: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Pairwise independent hash family interface

Definition

Let D,R be finite sets with R nonempty and let K be a finite nonempty set of seeds, each having probability $1 / ∣ K ∣$ . A family $(h_{k} : D \to R)_{k \in K}$ is pairwise independent if, for every $x \in D$ and $u \in R$ , $\frac{∣ {k : h_{k} (x) = u} ∣}{∣ K ∣} = \frac{1}{∣ R ∣},$ and, for distinct $x, y \in D$ and all $u, v \in R$ , $\frac{∣ {k : h_{k} (x) = u, h_{k} (y) = v} ∣}{∣ K ∣} = \frac{1}{∣ R ∣^{2}} .$ This is the finite joint-probability factorization of Pairwise and mutual independence of finite-valued random variables, stated by counts so R need not be a subset of the reals. Distinct seeds may encode the same function. For $∣ D ∣ \leq 1$ the pair condition is vacuous, but the marginal requirement remains. Collision-probability bounds alone are not this definition.

For any finite field F, the seeds $(a, b) \in F^{2}$ and maps $h_{a, b} (x) = a x + b$ form such a family on $D = R = F$ . Zero slopes are included.

Facts & Assumptions

Given: A finite field F; all ordered seed pairs are equally likely.

[F1]

A field has distinct zero and one, distributive operations and multiplicative inverses of nonzero elements (Field).

Verification

1.1

Fix x and a desired u. For each $a \in F$ , the equation $a x + b = u$ has the unique solution $b = u - a x$ by additive cancellation. Hence exactly $∣ F ∣$ of $∣ F ∣^{2}$ seeds give u, proving marginal probability $1 / ∣ F ∣$ . In particular the seed with a=0 is necessary to this full family and is permitted. F is nonempty, indeed has at least two elements by F1.

F1given

2.1

For distinct x,y and prescribed u,v, subtraction gives $a (x - y) = u - v$ . The nonzero $x - y$ has an inverse, so necessarily $a = (u - v) (x - y)^{- 1}$ and $b = u - a x$ . These values work: $a y + b = u - a (x - y) = v$ . They are unique by multiplication by the inverse and additive cancellation; uniqueness of an inverse itself follows from $c = c ((x - y) d) = (c (x - y)) d = d$ when c,d are both inverses. Exactly one seed therefore realizes each ordered output pair, with probability $1 / ∣ F ∣^{2}$ , equal to the product of the marginals from step 1.1. This proves pairwise independence. Equal x,y are intentionally excluded: their values cannot be independently prescribed.

step 1.1F1∎

Depends on

Used by

Pairwise independent affine hashing over a prime field Example

Dependency tree · two levels

4 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Aspnes pairwise-independence/hash-family treatment, complete locator/reading pending; explicit local affine proof (standard reference, not scraped)