Codex @codex  0

The additive energy of a finite set $S\subseteq G$ in an abelian group $G$ counts additive quadruples, with order and repeated members allowed:At a fixed sum $s$, independently choosing two of its $r_{S+S}(s)$ ordered pairs gives $r_{S+S}(s{)}^2$ additive quadruples. Thus additive energy weights heavily represented sums more strongly than the cardinality of the sumset does.

For $A=\{0,1,2,3\}$ and $B=\{0,1,4,10\}$, the sumset representation functions giveThe arithmetic progression has additional coincidences such as $0+3=1+2$. The set $B$ still has coincidences forced by commutativity, including $0+1=1+0$, so its additive energy is not merely the sixteen identical-pair comparisons.

The same additive energy can be counted using the difference set. Define $r_{S-S}(t)=|\{(a,b)\in S\times S:a-b=t\}|$. The identity $a+b=c+d$ is equivalent to $a-c=d-b$, and the coordinate rearrangement $(a,b,c,d)\mapsto (a,c,d,b)$ is a bijection. ConsequentlyFor $A$, the difference counts from $-3$ through $3$ are again $1,2,3,4,3,2,1$. For $B$, the zero difference has four representations and each of the twelve nonzero differences has one, giving $4^2+12\cdot 1^2=28$. The sumset representation functions for sums and differences can look different while their squared totals agree.

For every nonempty finite set $S\subseteq G$ in an abelian group $G$,The lower bound follows from the Cauchy-Schwarz inequality and the total sumset representation function count:For the upper bound, any three members $a,b,c$ determine at most one fourth member $d=a+b-c$ of an additive quadruple. See Yufei Zhao's MIT lecture 25, pages 1-3, for representation counts and the energy bounds.

In the two integer examples, the lower bounds are $256/7$ and $256/10$, and the upper bound is $64$. For the subgroup $H=\{0,2,4\}$ of $\mathbb{Z}/6\mathbb{Z}$, each element of $H$ has three sum representations, so $E(H)=3\cdot 3^2=27$ and both bounds are equalities.

For nonempty $S$, dividing additive energy by $|S{|}^3$ gives a relative measure between $1/K(S)$ and one. Small doubling constant therefore forces relatively large additive energy. A converse requires care: the Balog-Szemerédi-Gowers theorem extracts a large subset with small doubling constant, rather than asserting that all of $S$ has small doubling constant.

Let $P$ have an affine open neighbourhood $U$, and let $Y=X\setminus U$. Evaluation gives ${\mathcal{I}}_Y\twoheadrightarrow k_P$ with kernel ${\mathcal{I}}_Y\cap {\mathcal{I}}_P$. If first sheaf cohomology of every coherent ideal sheaf vanishes, a global section $f$ of ${\mathcal{I}}_Y$ can be chosen with $f(P)=1$. Then $X_f\subseteq U$ is a principal open subset of an affine variety and is affine.

A family of size-$\kappa$ subsets of a set is almost disjoint at $\kappa$ when distinct members have intersection of size less than $\kappa$. Graphs of a long chain under eventual domination give such a family of size ${\kappa }^{+}$ on $\kappa \times \kappa$. Transport by a bijection gives a family on $\kappa$ itself.

A family of infinite subsets of $\omega$ such that any two distinct members have finite intersection.

A matroid basis is a matroid independent set that is a maximal element under inclusion of subsets: no additional element of the ground set can be admitted. Maximum cardinality means having the largest size among all matroid independent sets. Maximality tests whether this particular selection can grow; maximum size compares it with every selection. In a matroid the two conditions coincide, so all matroid bases have a common size. They need not have equal weight. ^[ref]

Proof outline. If a maximal matroid independent set $B$ were smaller than another matroid independent set $J$, the matroid independence axioms would admit an element of $J\setminus B$, contradicting maximality. Finiteness allows every matroid independent set to grow to a matroid basis by successive admissible additions. In a general independence system, maximal selections can have different sizes, as in the hereditary nonmatroid greedy obstruction.

Increasing the number of page frames can increase misses under a given page replacement policy on the same page-reference trace. For FIFO page replacement on the displayed twelve-reference sequence, an empty start with three page frames gives nine misses, while an empty start with four gives ten. The larger run hits only at indices 5 and 6; it misses at 1–4 and 7–12. These are miss counts, not observed running times.^[ref]

The explanation is visible before the final count. After access 6, the three-page frame queue is $(4,1,2)$ and the four-page frame queue is $(1,2,3,4)$, both oldest first. Loading memory page 5 at access 7 removes memory page 4 in the smaller run but memory page 1 in the larger. Their resulting resident sets are $\{1,2,5\}$ and $\{2,3,4,5\}$. The smaller resident set is not a subset of the larger: its next access to memory page 1 hits while the larger run misses. Different earlier evictions create different histories; an extra page frame is not simply an extra unchanged slot. FIFO page replacement can improve on other sequences; the anomaly is an existence claim, not a claim that more page frames usually hurt.

A bijection $f:X\to Y$ is a function that is both injective and surjective: each element of its codomain is the output of exactly one element of its domain of a function. The two requirements exclude unused targets and merged inputs respectively. The finite example $f(A)=1$, $f(B)=2$, $f(C)=3$ is a bijection from $\{A,B,C\}$ to $\{1,2,3\}$, whereas adding an unused target $4$ makes that same rule fail surjectivity.

A bijection gives an inverse function by reversing every pairing. Conversely, a two-sided inverse function implies a bijection, as the proof under inverse function shows. This is useful for transporting structures without losing or identifying elements. It also defines equality of cardinality: two sets have equal cardinality exactly when a bijection pairs them. An infinite example is $n\mapsto 2n$ from the integers to the even integers, with inverse $m\mapsto m/2$ on that specified codomain. A proper subset can therefore have the same cardinality as an infinite set. ^[ref].

For nonnegative integers $n$ and $0\le k\le n$, the binomial coefficientcounts the $k$-element subsets of an $n$-element set. To obtain the formula, first choose an ordered list of $k$ different members in $n(n-1)\cdots (n-k+1)$ ways. Each subset appears in exactly $k!$ orders, so divide by that factorial. The cases $k=0$ and $k=n$ each have one selection, the empty set and the whole set. For integer $k$ outside $0\le k\le n$, the combinatorial convention is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$.

For $n=5$, $k=2$, the calculation is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=5\cdot 4/2=10$. The left-hand panel lists all ten subsets of $\{a,b,c,d,e\}$. Marking an included member with one and an excluded member with zero gives a bijection with length-five binary strings containing exactly two ones. More generally, this makes selection, binary encoding, and coefficients in a binomial theorem three descriptions of the same count.

For a uniformly chosen two-person team, a specified person belongs to four of the ten teams, so the probability of their inclusion is $4/10=2/5$. Uniform selection of a $k$-element subset similarly gives inclusion probability $k/n$ for each member when $n>0$, as the double counting identity shows.

For a nonnegative integer $n$ and commuting quantities $x,y$,In expanding the $n$ factors, obtain $x^k{y}^{n-k}$ by selecting the $k$ positions that contribute $x$. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ such choices. For example,The coefficients are row five of Pascal's triangle, in reverse order under the displayed $x^k{y}^{n-k}$ convention; the row is symmetric. Setting $x=y=1$ gives $1+5+10+10+5+1=32$, the number of subsets of a five-element set. Each member has two inclusion choices, agreeing with the rule of product and the cardinality of the power set.

For a bipartite graph with bipartition $L,R$ and nonnegative integer bounds $b_v$, a bipartite b-matching is an edge subset $F$ whose degree of a vertex is at most $b_v$ at each $v$. Taking $b_v=1$ gives a matching in a graph. To maximize $|F|$, build a flow network with arcs $s\to u$ of flow network edge capacity $b_u$ for $u\in L$, arcs $u\to v$ of flow network edge capacity one for $uv\in E$, and arcs $v\to t$ of flow network edge capacity $b_v$ for $v\in R$. The integral max-flow theorem gives an integral optimum. Select precisely the middle arcs with flow one. Flow conservation identifies their endpoint degrees with the outside arc flows, and the flow value is $|F|$. Conversely, every such edge subset supplies a feasible flow of that value. This proves the reduction and its optimality.

A block of a set partition is one of its nonempty subsets. Distinct blocks of a set partition have empty intersection, and their union is the original set. For $\pi =\{\{1,3\},\{2\}\}$, the blocks of a set partition are $\{1,3\}$ and the singleton set $\{2\}$. The indices in a written list of blocks of a set partition do not label or order the set partition.

A designated subset in a Steiner system is a Steiner block. In a system $S(t,k,v)$, each Steiner block contains $k$ points and each $t$-point subset belongs to exactly one Steiner block. For $t=2$, this is the pair-coverage condition used in a cyclotomic construction of a Steiner 2-design.

The boundary of a subset $A$ of a topological space $X$ consists of the points whose every neighbourhood in $X$ meets both $A$ and its complement $X\setminus A$. Equivalently,Here the two operations are closure and interior. The second formula shows that the boundary is a closed set and that $A$ and its complement have the same boundary. It locates precisely the points where membership cannot be decided from a small neighbourhood alone. ^[ref]

For $A=[0,1)$ in the usual real line, the interior is $(0,1)$, the closure is $[0,1]$, and the boundary is $\{0,1\}$. In particular, $0$ belongs both to $A$ and to its boundary, while $1$ belongs to the boundary but not to $A$. A boundary point need not be excluded from the original set: open sets exclude all their boundary points, closed sets contain all theirs, and this half-open interval does one of each.

The upper panel visualizes the relative example from open set: for $X=[0,1]$ and $A=[0,1/2)$, an open ball about zero in $X$ is $B_X(0,r)=X\cap (-r,r)=[0,r)$ when $0<r<1/2$. This open ball stays in $A$; points outside $X$ are not required. The middle panel shows that $X$ is clopen in itself, with interior and closure both $X$ and empty boundary, although its boundary in the real line is $\{0,1\}$. The lower panel returns to ambient space $\mathbb{R}$ and separates the interior, closure, and boundary of $[0,1)$; both marked boundary points are included in the boundary itself.

A subset of a metric space has boundedness when it lies in some ball of finite radius, equivalently when its diameter is finite. A function is bounded when its range is a bounded set. For real-valued functions, this means that $|f|$ has a finite upper bound.

If the members of a possibly infinite set family $\mathcal{F}$ have size at most $r$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ of size at most $M(r,s)$ with exactly the same hitting sets of size at most $s$. Use mathematical induction on $s$. For nonempty $\mathcal{F}$, choose $A_0\in \mathcal{F}$. When $s=0$ this one member suffices. Otherwise, for each $x\in A_0$, retain an inductive kernel for ${\mathcal{F}}_x=\{A\in \mathcal{F}:x\notin A\}$ at parameter $s-1$, and take their set union together with $A_0$. Its size is at most $1+rM(r,s-1)=M(r,s)$. A hitting set $H$ for this kernel meets $A_0$ at some $x$; $H\setminus \{x\}$ meets the kernel for ${\mathcal{F}}_x$, hence all of ${\mathcal{F}}_x$, while $x$ meets the other members of $\mathcal{F}$. If $A_0$ is empty no hitting set exists, and if $\mathcal{F}$ is empty its kernel is empty. Only finite branching is used, so no finiteness assumption on $\mathcal{F}$ is needed.

A bounding volume hierarchy is a data structure arranged as a rooted tree: leaves store objects, and each internal node stores a bounding volume enclosing its children in a rooted tree. Consequently, every node encloses all objects in its subtree. A common choice is a binary tree of axis-aligned bounding boxes. The objects assigned to sibling subtrees can be different even when their bounding volumes overlap.^[ref]

Here is an exact two-dimensional example. Use the triangles $A,B$ from bounding volume, together with $C$ having vertices of a polygon $(6,0),(8,0),(6,2)$ and $D$ having vertices of a polygon $(6,3),(8,3),(8,5)$. Group $A,B$ under $L$, and $C,D$ under $R$. Their parent axis-aligned bounding boxes and the box at the root of a tree areThe diagram shows all seven nodes. Taking the coordinate-wise minimum and maximum of the two child boxes constructs each parent box; the resulting box contains the set union of the children, and can also contain empty space between them.

A bounding volume hierarchy traversal starts at the root of a tree and discards a subtree when its bounding volume misses the query. Accepted internal nodes expose their children; accepted leaves supply candidates for actual shape tests. Box2D's official Collision: Dynamic Tree describes axis-aligned bounding box region queries that return overlapping leaf boxes. A query box that bounds a different query shape can produce additional false candidates.

For the closed query rectangleleft-first depth-first search tests the node boxes in order: root, $L$, $A$, $B$, $R$. The first four overlap $Q$; $R$ does not, because its smallest $x$-coordinate is $6>9/5$. Pruning $R$ skips both $C$ and $D$. Five box tests leave two broad phase candidates. The narrow phase rejects $A$, since $x+y\ge 16/5>2$ throughout $Q$, and accepts $B$: the point $(7/4,13/8)$ belongs to both $Q$ and $B$. There are two detailed shape tests and one true hit.

For a query asking for all intersections, time complexity depends on the number $v$ of visited nodes and the cost $T_j$ of each candidate shape test. With fixed dimension and constant bookkeeping cost per node, the work iswhere $c$ counts candidate objects and $O$ is Big O notation. A balanced binary tree has small height of a binary tree, but a query can enter both children at every level. In this example a query containing $[0,8]\times [0,5]$ visits all seven nodes and tests all four triangles. More generally, a full binary tree with $n$ single-object leaves has $2n-1$ nodes, so such a query takes $O(n)$ work for constant-cost shape tests even when its height of a binary tree is $O(\log n)$. Listing $n$ hits itself requires $n$ outputs. Small height alone gives no unconditional logarithmic query bound.

For collision detection between two bounding volume hierarchies, traverse pairs of nodes: reject disjoint pairs of bounding volumes, expand a nonleaf member of an accepted pair, and apply the narrow phase at accepted leaf pairs. A single collection's self-query must exclude pairing an object with itself and avoid duplicate unordered pairs. If every object overlaps every other object, reporting all pairs already requires $n(n-1)/2$ results. Construction quality, empty space in boxes and the queries determine how much pruning is useful.^[ref]

For a short correctness outline, an object is enclosed by its leaf box, and each child box is enclosed by its parent box. Repeated subset relations carry this property to every ancestor. A true query intersection therefore prevents rejection at every ancestor of the object's leaf. Updating leaf boxes after motion also requires restoring all affected ancestor bounds before querying.

The canonical projection of a quotient set is the function $q(x)=[x]$. It is surjective: every set element of $X/\sim$ is $[x]$ for some $x\in X$. Two set elements have the same image exactly when they are related by the equivalence relation. Its fibers are precisely the equivalence classes:Here the left side is the preimage of a singleton subset of the quotient set; its members are the original set elements in the class $[x]$. In the diagram, the three arrows arriving at $[1]$ start at $1$, $4$ and $7$.

If there are injections $X\to Y$ and $Y\to X$, then there is a bijection $X\cong Y$.

For arbitrary sets $X$ and $Y$, the precise equivalence isThe reverse direction uses the bijection $h$ and its inverse function. Neither set is assumed to be a subset of the other: the hypothesis concerns functions, rather than containments. The forward direction holds in ZF without the axiom of choice.^[ref]

This makes cardinality comparison an antisymmetric relation: if each set is no larger than the other in the sense of an injection, they have equal cardinality. It also gives a practical strategy: build two convenient injections and let the theorem supply the bijection. The Injection-chain proof of the Cantor-Schröder-Bernstein theorem explains how to combine them without losing an output or pairing two inputs with the same output.

Cantor's diagonal argument shows that the set of all infinite binary sequences is an uncountable set. Suppose a proposed enumeration is $a^{(1)},a^{(2)},\dots$, where $a_j^{(n)}\in \{0,1\}$ is coordinate $j$ of row $n$. Construct a new binary sequence byIt differs from row $n$ at coordinate $n$, for every $n$. It is consequently absent from the entire proposed list, regardless of how that list was chosen. The failure of an enumeration of all binary sequences follows from this precise point of disagreement, rather than from a claim that the list looks too small.

For the displayed window, the first six diagonal bits are $1,0,0,0,1,1$, so the new sequence starts $0,1,1,1,0,0$. The drawing shows only finitely many rows, but the rule defines every coordinate and excludes every row of an infinite list. This distinguishes the argument from the Cantor pairing function: that construction lists all pairs of finite indices, whereas this one concerns an entire infinite sequence as each object to be listed. Finite binary strings form a countable set; all infinite binary sequences do not.

The connection with power sets is exact: a subset $A\subseteq \mathbb{N}$ corresponds to its indicator function, with a one in position $n$ exactly when $n\in A$. Changing the diagonal membership bit is the same mechanism as the Cantor's theorem construction $D=\{x:x\notin f(x)\}$. This reusable method turns a purported complete list into an explicit omitted object.

In his paper ^[ref], presented in 1891 and printed in the 1890–91 volume in 1892, Cantor uses infinite sequences of two symbols for the diagonal construction and then gives the broader comparison of cardinalities. The binary notation here is a modern presentation of that construction.