Theorem index

Every named theorem, law, inequality and principle in the guide, with a one-line statement and the chapter that explains (and usually proves or derives) it.

Foundations, algebra and number theory

Result	One-line statement	Used for	Ch.
De Morgan's laws	`¬(A ∧ B) = ¬A ∨ ¬B` and `¬(A ∨ B) = ¬A ∧ ¬B`	simplifying firewall and access rules	3
Pigeonhole principle	`n + 1` items in `n` boxes put two in one box	why hash collisions must exist	15
Pythagorean theorem	`a² + b² = c²`	distances, the L2 norm	7, 10
Fundamental Theorem of Arithmetic	every integer `> 1` factors uniquely into primes	the basis of RSA	19
Bézout's identity	`a·x + b·y = gcd(a, b)` has integer solutions	modular inverses via extended Euclid	19
Fermat's Little Theorem	`a^(p-1) ≡ 1 (mod p)` for prime `p ∤ a`	primality tests	19
Euler's theorem	`a^φ(n) ≡ 1 (mod n)` when `gcd(a, n) = 1`	why RSA decryption works	19, 24
Chinese Remainder Theorem	residues mod coprime `n₁…nₖ` determine `x` mod their product	4× faster RSA, and the fault attack on it	19
Prime Number Theorem	primes near `N` have density `≈ 1/ln N`	how long prime generation takes	19
Miller–Rabin error bound	a composite survives `k` rounds with probability `≤ 4⁻ᵏ`	trusting generated primes	19
Inclusion–exclusion	`\|A ∪ B\| = \|A\| + \|B\| - \|A ∩ B\|`	`P(A ∪ B)`, `φ(pq)`	8, 19
Rule of 72	doubling time `≈ 72 / (rate %)`	growth, compounding	6, 12

Linear algebra

Result	One-line statement	Used for	Ch.
Characteristic equation	eigenvalues solve `det(A - λI) = 0`	finding eigenvalues by hand	11
Trace / determinant identities	`trace = Σ λᵢ`, `det = ∏ λᵢ`	sanity-checking eigenvalues	11
Diagonalization	`Aᵏ = P·Dᵏ·P⁻¹`	long-run behaviour of repeated processes	11
Spectral theorem	symmetric matrices have real eigenvalues and orthogonal eigenvectors	PCA, Hessians, Laplacians	11
Perron–Frobenius theorem	a positive stochastic matrix has a unique steady state for `λ = 1`	PageRank, Markov chains	11
Normal equations	least squares solves `XᵀX·w = Xᵀy`	linear regression	10
Eckart–Young theorem	truncated SVD is the best rank-`k` approximation, error `Σ_{i>k} σᵢ²`	compression, LoRA, PCA anomaly detection	20
Kirchhoff's matrix-tree theorem	spanning trees = any cofactor of the Laplacian	network redundancy	17

Calculus and optimization

Result	One-line statement	Used for	Ch.
Fundamental Theorem of Calculus	`∫ₐᵇ f dx = F(b) - F(a)` where `F' = f`	totals from rates, CDFs	12
Taylor's theorem	`f(x) ≈ f(a) + f'(a)(x-a) + f''(a)(x-a)²/2 + …`	gradient descent, approximations	12, 13
Gaussian integral	`∫ e^(-x²) dx = √π`	the normal distribution's constant	12, 14
Chain rule	`(f∘g)' = f'(g(x))·g'(x)`; for vectors, `∂L/∂x = Jᵀ·∂L/∂y`	backpropagation	13
Steepest ascent	`∇f` points uphill, and `‖∇f‖` is the steepest slope	why gradient descent follows `-∇f`	13
Schwarz's theorem	mixed partials commute, so the Hessian is symmetric	second-order optimization	13
Second-derivative test	`f' = 0` and `f'' > 0` (Hessian positive definite) means a minimum	optimum vs saddle	12, 13
Newton's method convergence	correct digits roughly double each step	square roots, solvers	12
Lagrange multipliers	at a constrained optimum, `∇f = λ·∇g`	SVMs, fair bandwidth sharing	21
Learning-rate stability	gradient descent converges iff `η < 2/λ_max`	choosing learning rates	21
Convexity	convex functions have a single global minimum	when optimization is easy	21

Probability and statistics

Result	One-line statement	Used for	Ch.
Kolmogorov axioms	`P ≥ 0`, `P(Ω) = 1`, disjoint probabilities add	the base of all probability	8
Law of total probability	`P(A) = Σ P(A\|Bᵢ)·P(Bᵢ)`	blending per-zone rates	8
Linearity of expectation	`E[X + Y] = E[X] + E[Y]`, even if dependent	expected collisions, dropout	8
Bayes' theorem	`P(A\|B) = P(B\|A)·P(A) / P(B)`	detection, spam filters, base-rate fallacy	16, 26
Beta–Binomial conjugacy	`Beta(α, β)` + `k` of `n` → `Beta(α+k, β+n-k)`	Bayesian A/B tests, Thompson sampling	16
68–95–99.7 rule	normal data lies within 1/2/3 σ with these shares	3-sigma alerts	9
Bessel's correction	sample variance divides by `n - 1`	unbiased spread estimates	9
Poisson limit theorem	`Binomial(n, p) → Poisson(np)` as `n → ∞`, `p → 0`	why arrivals are Poisson	14
Memorylessness	`P(T > s+t \| T > s) = P(T > t)` for exponentials	reliability, timeouts	14
Law of Large Numbers	sample averages converge to the true mean	why measurement works	14
Central Limit Theorem	averages are approximately `N(μ, σ²/n)`	A/B tests, mini-batch noise	14, 22
Markov's inequality	`P(X ≥ a) ≤ E[X]/a`	crude tail bounds	14
Chebyshev's inequality	`P(\|X - μ\| ≥ kσ) ≤ 1/k²`	bounds without normality	14
Hoeffding's inequality	`P(\|X̄ - μ\| ≥ ε) ≤ 2e^(-2nε²)`	sizing eval sets	14
Maximum likelihood ⇒ least squares	Gaussian noise MLE = minimizing squared error	why MSE is the default loss	22
Rule of three	0 failures in `n` trials ⇒ rate `< 3/n` at 95%	probes, red-team results	22
Simpson's paradox	a trend can reverse when data is aggregated	reading segmented metrics	22
Mann–Whitney / AUC	AUC = `P(score(positive) > score(negative))`	comparing detectors	26

Information theory and cryptography

Result	One-line statement	Used for	Ch.
Shannon's source coding theorem	lossless codes need `≥ H(X)` bits per symbol, and `< H(X) + 1` is achievable	compression limits	23
Kraft inequality	a prefix code with lengths `ℓᵢ` exists iff `Σ 2^(-ℓᵢ) ≤ 1`	Huffman coding	23
Shannon–Hartley theorem	`C = B·log₂(1 + S/N)`	channel capacity, QAM limits	23, 27
Birthday bound	collisions appear after `≈ 1.18·√N` draws	hash sizes, nonce limits	15, 24
RSA correctness	`m^(ed) ≡ m (mod n)`	RSA	24
Discrete-log / factoring hardness	believed hard classically, not proven	DH, ECC, RSA security	19, 24
Shor's / Grover's algorithms	quantum: break factoring and discrete log / square-root brute force	post-quantum planning	24
Learning With Errors	recovering `s` from `A·s + e (mod q)` is hard	ML-KEM	24
Differential privacy composition	`k` queries at `ε` each cost `k·ε`	privacy budgets	26

Networks, systems, signals and games

Result	One-line statement	Used for	Ch.
Little's Law	`L = λ·W` for any stable system	capacity, concurrency limits	25
M/M/1 results	`P(n) = (1-ρ)ρⁿ`, `W = 1/(μ - λ)`	queue latency, buffer overflow	25
Erlang C formula	probability of waiting with `c` servers	sizing worker pools	25
Kingman's formula	`W_q ≈ (ρ/(1-ρ))·((c_a² + c_s²)/2)·τ`	why variability hurts	25
Chiu–Jain (AIMD)	AIMD converges to an efficient and fair share	TCP congestion control	25
`BDP/√n` buffer rule	many desynchronized flows need much smaller buffers	router design, bufferbloat	25
Kelly's proportional fairness	TCP-like control maximizes `Σ log xᵢ`	bandwidth sharing	21
Minimum-delay routing (Gallager)	at the optimum, used paths have equal marginal delay	load balancing	13
Mathis formula	throughput `≈ (MSS/RTT)·1.22/√p`	loss sensitivity of TCP	12
Dijkstra's correctness	popped distances are final if weights `≥ 0`	OSPF, IS-IS	17
Bellman–Ford	converges in `V - 1` rounds; counts to infinity on failure	RIP, distance vector	17
Max-flow min-cut theorem	maximum flow = minimum cut capacity	bottlenecks, DDoS capacity	17
Menger's theorem	disjoint paths = links needed to disconnect	redundancy planning	17
Cayley's formula	the complete graph `Kₙ` has `n^(n-2)` spanning trees	topology counting	17
Euler's formula	`e^(iθ) = cos θ + i·sin θ`	Fourier analysis	27
Convolution theorem	convolution in time = multiplication in frequency	fast filtering, CNNs	27
Nyquist–Shannon sampling theorem	sample above `2·f_max` or alias	ADCs, monitoring intervals	27
Feedback stability	a loop is stable iff every pole has `\|z\| < 1`; delay shrinks the stable gain	autoscalers, PID	11, 29
Nash equilibrium	no player gains by deviating alone	security incentives	28
Minimax / Stackelberg equilibrium	randomize so the attacker is indifferent	patrols, adversarial training	28