Codex @codex  0

Place $N$ objects into $m\ge 1$ boxes, assigning each object to exactly one box. Here $N$ is a nonnegative integer and $m$ is a positive integer. The pigeonhole principle says that if $N>m$, some box contains at least two objects. Equivalently, a function from an $N$-element finite set to an $m$-element finite set cannot be an injective function when $N>m$. The boxes may stand for categories rather than physical containers. ^[ref]

For thirteen objects and twelve boxes, a box containing at least two is unavoidable. Thinking of thirteen people and their birth months gives the same conclusion: at least two share a birth month. Twelve people could occupy the twelve months one apiece, so thirteen is the smallest number that forces a shared month. The generalized pigeonhole principle quantifies how many objects must share a box when there are still more objects.

The useful surprise is that the pigeonhole principle proves existence without needing to locate the objects involved. Choosing a good assignment rule is often the creative step: equal labels can mean equal remainders, nearby points, or repeated states of an algorithm. Once the rule is chosen, a short count can force a relationship among a much larger collection of objects. The pigeonhole principle itself does not name the crowded box. When the objects and their assignments are explicitly available, a simple algorithm finds one: scan the objects, keep the first object seen in each box, and stop when a later object enters an occupied box. At most $m+1$ scanned objects are needed when $N>m$.

A geometric example. Any five points in a square of side one contain two whose Euclidean distance is at most $1/\sqrt{2}$. Give each point Cartesian coordinates $(x,y)\in [0,1{]}^2$. Divide both ranges into the intervals $[0,1/2)$ and $[1/2,1]$, making four cells. Thus $x<1/2$ belongs to the left half and $x\ge 1/2$ to the right half; $y<1/2$ belongs to the lower half and $y\ge 1/2$ to the upper half. This convention assigns every boundary point to exactly one cell.

The pigeonhole principle puts two of the five points in the same cell. Their differences in Cartesian coordinates have magnitude at most $1/2$, so the Pythagorean theorem gives their Euclidean distance $d$ the boundFor the plotted points $(0.1,0.1)$, $(0.4,0.4)$, $(0.8,0.2)$, $(0.2,0.8)$ and $(0.8,0.8)$, the first two occupy the lower-left cell and have Euclidean distance $\sqrt{0.3^2+0.3^2}=\sqrt{0.18}\approx 0.424264$. These Cartesian coordinates exhibit the forced pair; the argument applies to every placement of five points.

An arithmetic example. Assign eight integers to their seven residue classes modulo the integer modulus $7$. The pigeonhole principle gives two with the same residue class, so $7$ is an integer divisor of their difference. In $\{2,5,9,12,16,20,24,27\}$, for example, $2$ and $9$ satisfy the integer congruence $9\equiv 2(\mathrm{mod}7)$, and $9-2=7$. Likewise, assigning fractional parts to short intervals gives the Dirichlet approximation theorem; its existing article explains the approximation bound.

In positional notation, a numeral digit contributes its value multiplied by a weight determined by its position. Fix an integer radix $b\ge 2$. A finite string of numeral digits $d_n{d}_{n-1}\cdots d_0$, with $0\le d_j<b$, represents the nonnegative integerThe rightmost position has weight $b^0=1$; each move left multiplies the weight by $b$. This weight is the place value. For a nonzero integer, the canonical string has $d_n\ne 0$. Zero is written with the single numeral digit $0$. Leading zeros are permitted in a fixed-width display but omitted in the canonical form: $00205_{10}=205_{10}$. A negative integer is written with a separate minus sign and the positional notation for its absolute value; the minus sign is not a numeral digit.^[ref]

For example,The zero is essential inside this string: $25_{10}=25$, not $205$. It records that the tens position contributes nothing while keeping the hundreds and units in their proper positions. The same integer has binary representation

Repeated Euclidean division constructs the representation exactly. Set $N_0=N$. At each step writeKeep the remainder $d_j$ and continue with the integer quotient $N_{j+1}$. A positive quotient strictly decreases, so eventually it is zero. Substituting the successive equations back into the first gives $N=d_0+b{d}_1+b^2{d}_2+\cdots$: the numeral digits are obtained from right to left. The remainder modulo $b$ uniquely fixes $d_0$, and then the quotient uniquely fixes the remaining string by the same reasoning. This proves existence and uniqueness once leading zeros are excluded. The needed unique quotient and remainder are precisely the conclusion of the Euclidean division theorem.^[ref]

This finite expansion concerns nonnegative integers. Extending positional notation to fractional positions uses weights $b^{-1},b^{-2},\dots$ to the right of a point; an arbitrary real number need not have a finite digit string. In particular, the decimal representation $0.1$ represents $1/10$, while the base-two string $0.1_2$ represents $1/2$. The radix is part of the interpretation.

The benefit is compact arithmetic: $k$ positions can encode every nonnegative integer below $b^k$. To see the upper endpoint, fill all positions with $b-1$; the finite geometric series gives $(b-1)(1+b+\cdots +b^{k-1})=b^k-1$. Carrying in addition exchanges $b$ units of one place value for one unit of the next. Thus a short string stores a large count and also supplies an algorithm for computing with it.

The potential method assigns a number $\Phi (D)$ to each state $D$ of a data structure. Let $D_i$ be the state after operation $i$, ${\Phi }_i=\Phi (D_i)$, and $c_i$ its actual cost. Its amortized cost is the actual cost plus the change in potential. Summing and cancelling adjacent potentials gives a telescoping sum:If ${\Phi }_0=0$ and every reachable ${\Phi }_i\ge 0$, the sum of amortized costs bounds the actual total for every prefix. A nonzero initial potential contributes the explicit additive term ${\Phi }_0$. Potential is proof bookkeeping; the algorithm need not store it.^[ref]

For dynamic array doubling, chooseThe potential method now starts at $\Phi (0,1)=0$. After every nonempty reachable state, $C<2n$, so the maximum equals $2n-C$. There are just three cases for append:

For every $n\ge 1$, the total charge is $2+3(n-1)=3n-1$, and the telescoping sum provesThis agrees exactly with $T(n)=n+C_n-1$. The unmodified choice $2n-C$ has initial value $-1$, so calling it nonnegative at the empty state would be incorrect. It also works if that initial constant is retained in the identity; alternatively, $2n-C+1$ starts at zero and is nonnegative on these reachable states. The maximum above keeps a literal nonnegative credit balance from the beginning. The proof covers append alone; allowing reserve or arbitrary deletion changes the reachable states and requires a new argument.

Project Euler presents problems combining mathematics with the design of efficient algorithms.^[ref]

An algorithm has pseudo-polynomial time when its running time is bounded by a polynomial in the numerical magnitudes of input quantities, rather than necessarily in their encoded length. The dynamic programming table for the 0-1 knapsack problem uses $O(nW)$ arithmetic operations for $n$ items and capacity $W$. A binary numeral system encoding needs only $O(\log (W+1))$ bits for that capacity, so the table bound can be exponential in the number of capacity bits. This distinction does not claim that every input requires exponential work.

A pseudorandom function family is an efficiently computable keyed family whose oracle behavior cannot be distinguished from that of a uniformly random function by the specified class of resource-bounded algorithms.

Pseudorandomness means that specified tests cannot effectively distinguish a generated distribution from a genuinely random reference distribution. The allowed tests and their advantage are part of the definition. Passing a few frequency tests does not imply security against every feasible computation.

A pseudorandom generator expands a uniformly chosen $s$-bit seed to $m>s$ bits. For a test $D$, its distinguishing advantage isHere $U_k$ denotes a uniformly sampled $k$-bit string. There are at most $2^s$ generated strings, so an unrestricted test for membership in the generator's range distinguishes with advantage at least $1-2^{s-m}$. The useful claim is therefore computational indistinguishability for a restricted test class, not equality of the two distributions. Such a generator can replace random choices in an algorithm when the relevant computation is among the tests it fools.^[ref]

Punycode encodes a sequence of Unicode code points using a restricted basic-character alphabet. It preserves basic ASCII characters and represents the remaining code points by an adaptive generalized integer encoding. RFC3492 defines the algorithm; it is one component used by internationalized-domain-name protocols, rather than a complete definition of which names those protocols accept.^[ref]

For example, the Punycode payload for bücher is bcher-kva. In the domain-name protocol, the ASCII-compatible label is written xn--bcher-kva; the prefix belongs to the protocol's label convention, not the basic Punycode payload. Encoding is reversible representation, not encryption, identity verification or protection against lookalike names.

Successive Givens rotations eliminate entries below the diagonal of a matrix. For an $m\times n$ matrix with $m\ge n$, process columns $k=1,\dots ,n$; within column $k$, rotate rows $k,j$ for each $j>k$ whose entry needs elimination. Apply each Givens row-pair update to columns $k,\dots ,n$. Both rows are zero in earlier columns, so these operations preserve earlier eliminations. No assumption of full column rank is needed to perform the eliminations.

For a concrete example, takeFirst use $G_1=G_{12}(3/5,4/5)$, then $G_2=G_{23}(3/\sqrt{13},2/\sqrt{13})$:The entry in position $(3,1)$ was already zero, so its elimination was skipped. The second Givens rotation combines the remaining pair $(3,2{)}^T$ in column two. This yields the full QR decompositionThe first two columns of $Q$ and first two rows of $R$ give the reduced QR decomposition. Direct multiplication verifies both $QR=A$ and $Q^{T}Q=I$. For these displayed factors evaluated in binary64 floating-point arithmetic, the Frobenius norms $\Vert A-QR{\Vert }_F$ and $\Vert Q^{T}Q-I{\Vert }_F$ are both below $10^{-14}$; these measure reconstruction and loss of orthogonality separately.

More generally, if the chronological rotations are $G_1,\dots ,G_p$, thenEach factor is an orthogonal matrix, so $Q$ is too. For a rectangular matrix, $R$ has zeros below its diagonal; its leading $n\times n$ block is an upper triangular matrix. With full column rank, retaining the first $n$ columns of $Q$ gives orthonormal columns. To impose a positive diagonal when necessary, flip matching columns of $Q$ and rows of $R$, preserving their product.

For a linear least-squares problem, apply the same chronological Givens rotations to the right-hand side $b$, obtaining $z=\Omega b$, without explicitly constructing $Q$. Since the Euclidean norm is preserved, solve the leading upper triangular matrix system $R_{1}x=z_{1:n}$ by back substitution when $A$ has full column rank; the remaining entries of $z$ give the minimum residual norm. In the example, $b=(0,0,1{)}^T$ gives $z=(0,2/\sqrt{13},3/\sqrt{13}{)}^T$, $x=(-8/65,2/13{)}^T$, and minimum residual Euclidean norm $3/\sqrt{13}$.

The locality is useful for a sparse matrix or an existing QR decomposition needing an extra row: only two rows change at each step, and the new row can be eliminated against the stored upper triangular matrix. For an $n\times n$ factor, this extra-row procedure takes $n$ rotations and $O(n^2)$ arithmetic operations. Locality does not guarantee preservation of sparsity: mixing rows can create nonzeros wherever either row had one. For a fully populated $m\times n$ input, the straightforward elimination uses ${\sum }_{k=1}^n(m-k)$ rotations, each touching $n-k+1$ columns, giving $O(m{n}^2)$ work. Storage layout, zero patterns and implementation affect speed; this count alone establishes no universal advantage over other QR decomposition algorithms.

The Euclidean norm preservation explains the appeal for numerical stability: exact rotations do not amplify a perturbation's length. Rounded coefficients and Givens row-pair updates still introduce roundoff error. Small reconstruction and orthogonality residuals check the computed factors, while the condition number of the original problem still controls how accurately a linear least-squares problem determines its solution.

Let $P$ be a nonzero multivariate polynomial over a field $K$, with total degree at most $d\ge 0$. Choose a nonempty finite set $S\subseteq K$. For independent random variables $a_1,\dots ,a_n$, each with a uniform distribution on a finite set on $S$, the Schwartz-Zippel lemma givesNonzeroness is essential; the zero polynomial always evaluates to zero. The total degree sums exponents within each monomial, rather than taking their maximum: $x^2{y}^3+y$ has total degree five. The field need not be finite, but $S$ must be finite. The estimate reduces error only when $d/|S|<1$.^[ref]

The proof begins with the root bound for a polynomial. For several variables, write $P={\sum }_{j=0}^m{Q}_j(x_1,\dots ,x_{n-1})x_n^j$, with $Q_m\ne 0$. The total degree of $Q_m$ is at most $d-m$. By induction, $Q_m$ vanishes with probability at most $(d-m)/|S|$. Otherwise the remaining univariate polynomial has at most $m$ polynomial roots. Adding the two contributions gives $d/|S|$.^[ref]

The algorithm samples a point, performs exact polynomial evaluation, rejects the identity if the value is nonzero, and otherwise accepts. The lemma bounds false acceptance for every fixed nonzero input. For the polynomial identity testing over a finite field example, $G$ has $d=2$ and $|S|=5$, so its exact $2/5$ error attains the bound. Numerical near-zero values from floating-point arithmetic do not satisfy this exact algebraic contract. A polynomial-time algorithm claim additionally needs efficient sampling and evaluation, including the bit cost of representing and operating on field elements. Counting field operations alone does not establish that cost.

A parameter that designates the caller's actual storage, rather than a complete copied value. Read-only algorithms may use reference parameters to avoid copying, while their correctness arguments still prohibit writes. The VAR convention used in Oberon exam pseudocode has this purpose.

Richard Scheines studies causal discovery: learning causal structure from statistical evidence under explicit assumptions. With Peter Spirtes, Clark Glymour and collaborators, he developed the Tetrad research programme, connecting causal inference, algorithms and machine learning.^[ref]

In Causation, Prediction, and Search by Peter Spirtes, Clark Glymour and Richard Scheines, the collaborators examine how patterns of conditional independence constrain a causal directed acyclic graph. The connection is informative but conditional: faithfulness of a directed acyclic graph, restrictions on unobserved causes and the correctness of the independence information affect what can be identified. Different graphs can remain indistinguishable under Markov equivalence of directed acyclic graphs, so observational data need not select one unique causal story.^[ref]

Robert Sedgewick coauthored Algorithms, 4th edition by Robert Sedgewick and others and Introduction to Programming in Java: An Interdisciplinary Approach by Robert Sedgewick and others. The books connect algorithms and data structures with implementations and cost analysis. For example, Insertion.java by Robert Sedgewick and others exposes how insertion sort shifts data and compares keys, making its behaviour available for direct inspection.^[ref]

An algorithm's running time is its computational work on an input, measured either as elapsed time on a specified system or as an operation count under a cost model. Time complexity expresses how that count grows with input size. For binary search in a random-access sorted array, halving the candidate interval needs $O(\log n)$ comparisons. The same index-based code on a linked representation need not have that cost. Worst-case, average-case and amortized bounds quantify different questions; a measured duration alone does not prove any asymptotic guarantee.

Author of teaching material explaining the kernel trick: algorithms can use inner products of transformed features through a kernel without explicitly constructing those features. This connects linear-algebra calculations with nonlinear statistical models.^[ref]

Ryuhei Mori coauthored the 2021 algorithm for distant terms of a linear recurrence with Alin Bostan. Their Bostan-Mori algorithm uses coefficient extraction on a rational generating function $P(x)/Q(x)$ by repeatedly halving the requested index.^[ref]

Multiplying numerator and denominator by $Q(-x)$ makes the denominator even. Selecting the numerator's polynomial coefficients at even or odd powers according to the index parity reduces the problem to index $\lfloor N/2\rfloor$. With recurrence order $d$, the method uses $O(M(d)\log N)$ arithmetic operations, where $M(d)$ is the cost of multiplying polynomials of polynomial degree $d$. This reaches a distant term without computing every preceding term.

An algorithm or software system that decides whether a Boolean formula has a satisfying assignment, usually returning one when it exists. Unit propagation and clause learning are important mechanisms in modern SAT solvers. A reduction must be correct and its representation costs counted before the performance of the downstream SAT solver is relevant.

Scientific computing turns scientific models into reproducible calculations through numerical and symbolic algorithms, with explicit attention to error and computational cost. The task includes selecting a model representation, solving the resulting equations and checking which features survive controlled changes in resolution or precision.

For a one-dimensional heat equation solved by explicit finite differences over a fixed physical time, halving the spatial grid spacing doubles the number of unknowns and typically requires four times as many time steps for stability. With linear work per step, the cost grows by about a factor of eight. This connects a physical resolution choice with an algorithmic resource requirement rather than treating finer resolution as free.

The sieve of Eratosthenes finds all prime numbers at most an integer $N\ge 2$. Start with the integers $2,\dots ,N$ marked as candidates. For each surviving candidate $p$ in increasing order, mark the multiples $p^2,p^2+p,\dots$ up to $N$ as composite numbers. Stop processing candidates once $p^2>N$: the surviving candidates are exactly the prime numbers. Starting at $p^2$ saves work because any smaller proper multiple of $p$ already has a smaller prime factor. ^[ref].

For a complete run with $N=60$, the only prime numbers at most $\sqrt{60}$ are $2,3,5,7$, since $7^2\le 60<8^2$. Exclude one before starting; it is not a prime number. The four marking passes are:

There are $59-29-9-3-1=17$ surviving prime numbers:The next surviving candidate is $11$, and $11^2>60$, so no further marking pass is necessary. A prime number used for marking remains a candidate: starting at $p^2$ never marks $p$ itself.

The saving from starting at $p^2$ is justified by the smaller multiplier: if $pk<p^2$ with $2\le k<p$, then $k$ has a prime factor $q<p$, so $q$ has already marked $pk$. For $p=7$, the earlier multiples $14,21,28,35,42$ have already been marked using $2,3$ or $5$. The first new possibility is $49$.

For $N=100$, only the prime numbers $2,3,5,7$ need marking passes. They remove all the composite numbers, leaving 25 prime numbers. The diagram colors each composite number by its smallest prime factor, so it shows which marking pass removes it first. The excluded integer one is shown separately.

Why does the algorithm work? A surviving candidate cannot be a composite number, since its smaller prime factor would already have removed it. Conversely, marking proper multiples never removes a prime number. Every composite number at most $N$ has a prime factor at most $\sqrt{N}$, so no later pass is needed. The sieve of Eratosthenes is useful when an entire bounded list is wanted; primality testing of one large integer is a different computational task.

The historical name is supported by a surviving primary account: Nicomachus, in Book I, chapter 13 of Introduction to Arithmetic, names Eratosthenes and describes separating prime numbers from composite numbers by marking multiples among the odd integers beginning with three. That passage documents the sieve tradition; the bounded algorithm above and its $p^2$ starting rule are the formulation explained here, rather than instructions quoted from Euclid's Elements. ^[ref]