Typical ambiguity is the schema asserting that every closed well-typed sentence is equivalent to its uniform type-raise. It is not an assertion that adjacent types have the same cardinality. To obtain finite satisfiability, color finite increasing rank selections by the truth values of the finitely many sentences concerned. The Ramsey's theorem gives a homogeneous rank set; two overlapping windows then have equal truth vectors, yielding the desired type-raise equivalences. The compactness theorem gives a first-order model of the entire schema.

A similarity ansatz assumes a profile invariant under a prescribed rescaling, commonly in the displayed power-law form. Substitution into a partial differential equation fixes compatible exponents and can reduce it to an ordinary differential equation for $F$. Boundary conditions and conserved quantities must also be compatible with the scaling; the ansatz alone does not establish existence of a solution.

A reduction obtained by substituting a scale-invariant ansatz into a differential equation.

Partition each ordered integration simplex according to the number of times before the concatenation point. The integral over each resulting region factors into an initial iterated integral and a final iterated integral. Summing these factorizations proves the identity in the truncated tensor algebra.

For a continuous path of bounded variation, integrate successively over the ordered simplex using Riemann-Stieltjes integrals. These integrals form the levels of its path signature. Appending the final integration variable gives the differential recursion $d{S}_t^{(k)}=S_t^{(k-1)}\otimes d{x}_t$.

For a noncritical least-period-$n$ cycle of $g(x)=\mu -x^2$, the multiplier sign is $(-1{)}^n{\prod }_k\mathrm{sgn}(x_k)$. A positive multiplier gives two symmetry-related period-$n$ cycles of the odd quadratic Lorenz map; a negative multiplier gives one period-$2n$ cycle. Their multipliers are respectively $|(g^n{)}^{\prime }|$ and $|(g^n{)}^{\prime }{|}^2$. Distinct points of a quadratic-map cycle cannot have the same absolute value, since the map is even and acts bijectively on its cycle; this proves the asserted least periods.

// Target: dynamical-systems.bigb

Divisibility information by small primes cannot by itself reliably distinguish integers with an odd or even total number of prime factors. Consequently an upper-bound Selberg sieve can bound prime pairs and related sifted sets but does not supply a positive lower bound or the conjectured twin-prime asymptotic. This limitation concerns the information available to the sieve, not merely a choice of weight normalization.

// Target: number-theory.bigb

For $M<N$ homogeneous equations with integer coefficients of absolute value at most $A\ge 1$, map the box $\{0,\dots ,Q{\}}^N$ to its $M$ equation values. There are $(Q+1{)}^N$ inputs and at most $(2NAQ+1{)}^M$ outputs. Taking $Q=\lfloor (2NA{)}^{M/(N-M)}\rfloor$ makes the first count larger, since $2NAQ+1\le 2NA(Q+1)$. The difference of two inputs with the same output is the required nonzero bounded integer solution. Clearing denominators also treats rational equations; expanding a number-field basis replaces each field equation by finitely many rational equations.

Choose a generator $\theta$ of the multiplicative group of the quadratic finite field extension. Its $p$ shifts $\theta +t$ define $p$ distinct exponents modulo $p^2-1$. Equality of two sums of exponents gives $(\theta +s)(\theta +t)=(\theta +u)(\theta +v)$. Since $1,\theta$ are independent over the prime field, $s+t=u+v$ and $st=uv$, so the unordered pairs coincide. Thus the exponents form a Sidon set in the cyclic group. Taking integer representatives preserves the Sidon property. Primes within $o(\sqrt{N})$ below $\sqrt{N}$ give $\sqrt{N}-o(\sqrt{N})$ representatives in an interval of length $N$.

For a Sidon set $A\subseteq [1,N]$, put $m=|A|$ and let $A_i$ count points in a window of $u$ consecutive integers. Each point occurs in $u$ windows, so $\sum A_i=um$. Cauchy-Schwarz gives $\sum \left(\genfrac{}{}{0ex}{}{A_i}{2}\right)\ge [u^2{m}^2/(N+u)-um]/2$. Each positive difference occurs at most once and contributes $u-d$ windows, giving the upper bound $u(u-1)/2$. Thus $m^2\le (N+u)(1+(m-1)/u)$. Taking $u=\lfloor N^{3/4}\rfloor$ gives the displayed estimate, which combines with the Bose-Chowla Sidon construction to determine the asymptotic maximum.

The stochastic SI model with susceptible fraction $X_n$, initial limit $a$, and total infection rate $n\lambda X_n(1-X_n)$ has deterministic limitThe Poisson time-change representation of a Markov chain writes $X_n$ as its integrated drift minus a centered Poisson error. On $[0,T]$ its clock is at most $n\lambda T/4$. The Poisson maximal concentration bound makes every fixed error tolerance have summable probabilities in $n$, so the Borel-Cantelli lemma gives uniform error decay almost surely. The Gronwall inequality transfers that decay to $X_n-x$, because the drift is Lipschitz continuous. The assertion is for fixed finite intervals and does not claim approximation over times growing with $n$.

The Dijkstra algorithm solves the single-source shortest path problem in a finite graph with nonnegative edge weights, finding distances to all reachable vertices. Start with tentative distance $d(A)=0$ and $d(v)=\infty$ elsewhere. Repeatedly choose the unfinalized vertex with least tentative distance, declare that label permanent, and perform edge relaxation on its outgoing edges. For an undirected graph, inspect both directions. A finite tentative distance always records the cost of a discovered graph path, but can improve before finalization.

In our example, finalizing $A$ discovers $C$ at $1$, $B$ at $4$, and $D$ at $10$. Choose $C$ next: edge relaxation through $C$ lowers $B$ to $1+2=3$ and $D$ to $1+5=6$. Choose $B$: edge relaxation through $B$ lowers $D$ to $3+1=4$. Finally choose $D$. The permanent distances are therefore $A:0$, $C:1$, $B:3$, $D:4$; the evolving tentative distances were $B:4\to 3$ and $D:10\to 6\to 4$.

Store a shortest-path predecessor whenever edge relaxation improves a label. The final table contains enough information to reconstruct routes, rather than merely their costs:

Following shortest-path predecessors backwards gives $D,B,C,A$; reversing the order gives $A,C,B,D$. If only this destination matters, stop when $D$ is finalized. Stopping when $D$ is first discovered would incorrectly return $10$. If the smallest remaining tentative distance is $\infty$, all remaining vertices are unreachable.

Why is the permanent choice safe? Suppose the selected vertex $u$ had a cheaper graph path. Let $y$ be the first unfinalized vertex on that graph path. Its preceding vertex was finalized, so edge relaxation has already offered $y$ a label no larger than that prefix's cost. Nonnegative remaining edge weights make the whole cost at least this prefix's cost; selection gives $d(u)\le d(y)$. A cheaper graph path would contradict these comparisons. Zero weights are allowed; ties can be resolved arbitrarily. This is the reason the label-setting shortest-path algorithm works, rather than a lucky feature of the drawing.

Negative weights break that reasoning. In a directed graph with $s\to u$ costing $2$, $s\to v$ costing $5$, and $v\to u$ costing $-4$, the Dijkstra algorithm would finalize $u$ at $2$ before discovering the cheaper cost $1$. The Bellman-Ford algorithm handles negative edge weights when no relevant negative directed cycle exists.

With an adjacency list and an indexed binary heap implementing a priority queue, the time complexity is $O((|V|+|E|)\log |V|)$ for $|V|\ge 2$, using Big O notation. Each vertex is extracted at most once, each edge is inspected once per direction, and each successful edge relaxation decreases a heap key in $O(\log |V|)$ time. This assumes constant-cost arithmetic and comparisons; exact computation with very large weights adds their representation cost. The queue uses $O(|V|)$ space beyond the graph. Simply scanning all remaining vertices gives $O(|V{|}^2+|E|)$ instead.^[ref][ref]

The 1959 paper presents the shortest path problem as its second problem, after the minimum spanning tree problem, and grows known shortest routes in increasing distance order.^[ref] In his later recollection, Dijkstra dated the shortest-route discovery to 1956: a demonstration for the ARMAC computer used a simplified Dutch railway map and printed the route between towns. A practical request became an enduring algorithm because the same distance rule applies to any suitable graph.^[ref]

The Bellman-Ford algorithm solves the single-source shortest path problem in a finite directed graph with finite real edge weights, allowing negative weights. It repeatedly applies edge relaxation, so an improved tentative distance can improve its neighbours on a later visit. This makes it a label-correcting shortest-path algorithm.^[ref] If no negative-cost directed cycle is reachable from the source, at most $|V|-1$ complete passes suffice for all distances; a further check detects a reachable negative-cost directed cycle.^[ref]

There are two orientations to keep distinct. The usual single-source problem asks for distances from $s$, extending routes along outgoing directed edges. The Bellman inequalities above instead concern distances to a sink $r$, prepending incoming directed edges to known routes. The All-to-one Bellman-Ford recurrence below preserves that convention. Reversing every directed edge, with its weight unchanged, converts one problem into the other.

Here is an original single-source example with source $S$, vertex set $V=\{S,A,B,C,T\}$, and precisely these directed edges:The negative edge $A\to B$ is harmless: this directed graph has no directed cycle. Its best route to $T$ is $S\to A\to B\to C\to T$, of cost $4-2+3+2=7$. The other routes to $T$ cost $12$ through $S,A,T$ and $10$ through $S,B,C,T$.

Initialize $d(S)=0$ and the other tentative distances to $\infty$. In each pass apply single-source edge relaxation, $d(v)\leftarrow \min \{d(v),d(u)+w_{uv}\}$, scanning in the order $A\to T$, $C\to T$, $B\to C$, $A\to B$, $S\to B$, $S\to A$. Skip a candidate with $d(u)=\infty$. The figure records labels after each complete pass and uses current labels immediately: it is an in-place trace. In pass 2, $B\to C$ still uses $d(B)=5$, giving $8$; only later does $A\to B$ lower $B$ to $2$. Pass 3 carries that improvement to $C$, and pass 4 carries it to $T$. The final labels in order $(S,A,B,C,T)$ are $(0,4,2,5,7)$; the final shortest-path predecessors are $S,A,B,C$ for $A,B,C,T$ respectively.

The scan order explains the delay. Scanning instead as $S\to A$, $S\to B$, $A\to B$, $B\to C$, $C\to T$, $A\to T$ gives those same final labels in just one in-place pass. The Synchronous Bellman-Ford recurrence has a precise bound on the number of edges used by a recorded route; an in-place pass can propagate along several edges and need not have that interpretation. Both implementations have the $|V|-1$ pass guarantee under the stated no-reachable-negative-cycle hypothesis.

With a stored list of edges, complete-pass Bellman-Ford algorithm has time complexity $O(|V||E|+|V|)$ and uses $O(|V|)$ extra space for labels and shortest-path predecessors, using Big O notation and constant-cost arithmetic. The extra $|V|$ accounts for initialization even when $E$ is empty. A pass with no strict decrease permits early termination. A queue variant instead revisits outgoing edges of vertices whose labels improved; the authored implementation provides this alternative and has $O(|V||E|)$ worst-case running time on its usual nontrivial instances.^[ref] For nonnegative weights, the Dijkstra algorithm and its existing distance-frontier figure explain how permanent labels can avoid these repeated passes; the existing edge relaxation figure illustrates one update at a time.

An algorithm whose tentative distance labels may be revised repeatedly until all relevant Bellman inequalities hold. Bellman-Ford algorithm uses this approach: a label is an upper bound supplied by a discovered directed walk, and relaxing an directed edge can replace it with a shorter discovered directed walk. A finite label is not declared permanent merely because it has been processed.

The Bellman inequalities turn local directed edge checks into a global certificate for the shortest path problem. Here the convention is all-to-one: every journey ends at a fixed vertex $r$, and $c_{ij}$ is the cost of the original directed edge $i\to j$. Work in a finite directed graph with finite real costs. Write $L_i$ for candidate labels, normalized by $L_r=0$, on the vertices that can reach $r$. A feasible potential means precisely that these finite labels satisfyfor every directed edge within that set. These labels give lower bounds on costs to $r$. A discovered directed path of cost $U_i$ instead gives an upper bound. The following constructed graph shows both bounds and the exact distances between them; its weights are illustrative costs, not measured travel data.

The arrows in the picture point toward the destination, whereas edge relaxation propagates an improved label in the opposite direction: an improved $d_j$ can lower $d_i$. In the pictured graph, the directed paths from $a$ to $r$ cost $7$, $2+3=5$, and $2-2+4=4$. Thus $\delta (a,r)=4$. The candidate $L=(3,1,3,0)$ in vertex order $(a,b,c,r)$ is feasible, but underestimates the exact distances $(4,2,4,0)$. Merely satisfying the Bellman inequalities does not make a candidate exact.

Why do they give lower bounds? Along any directed path $i=v_0\to v_1\to \cdots \to v_k=r$, successive substitution givesThe same calculation works for a directed walk, with repeated vertices allowed. Taking the infimum of route costs gives $L_i\le \delta (i,r)$. A discovered route gives $\delta (i,r)\le U_i$. If the bounds meet, $L_i=U_i$, they certify an optimum without enumerating routes. Equivalently, check the Bellman inequalities for the proposed distances and exhibit directed paths realizing them. The authored Bellman-Ford algorithm implementation checks the corresponding single-source inequalities and equality on recorded route edges; reversing every directed edge gives this all-to-one convention.^[ref]

For the exact labels in the picture, the slack $c_{ij}+d_j-d_i$ is respectively $0,3,1,0,0$ on $a\to b$, $a\to r$, $b\to r$, $b\to c$, $c\to r$. Zero slack means equality; the zero-slack directed path $a\to b\to c\to r$ realizes the cost $4$. This is the useful beauty of the certificate: a few local inequalities rule out every cheaper journey, while one explicit journey attains the bound.

Keep unreachable vertices separate: $\delta (i,r)=\infty$ when no directed path to $r$ exists, and a finite lower bound alone cannot certify that fact. Extended labels can use $\infty +c=\infty$ for finite $c$, but never compute a slack as $\infty -\infty$. If $i$ can reach a negative-cost directed cycle and then reach $r$, repeatedly traversing the directed cycle makes route costs unbounded below: their infimum is $-\infty$, with no finite shortest directed walk. A finite feasible potential on such a directed cycle is impossible, since summing its Bellman inequalities would give $0\le \sum c_{ij}<0$. A negative-cost directed cycle that cannot reach $r$ does not affect distances to $r$. These are statements about unrestricted directed walks; requiring a directed path with no repeated vertices is a different optimization problem when negative-cost directed cycles exist.^[ref]

For the single-source convention, the same original directed edge $u\to v$ instead gives $L(v)\le L(u)+w_{uv}$ with $L(s)=0$, a lower bound on distance from $s$. The endpoint carrying the label on the left therefore changes with the direction of the problem.

An algorithm that makes each vertex's distance permanent once it is selected. With nonnegative directed edge lengths, the Dijkstra algorithm selects the unfinalized vertex with least tentative distance; a shorter route through another unfinalized vertex is impossible because its remaining route has at least that next tentative distance. For an all-to-one problem, incoming directed edges to the selected vertex are relaxed. Negative lengths can invalidate this finalization argument.

Let $I$ index at least two pairs of subsets of an $n$-element ground set, with $|R_i|=r$, $|S_i|=s$, and $R_i\cap S_j\ne \varnothing$ exactly when $i=j$. ThenChoose a witness $x_i\in R_i\cap S_i$ for each pair. The intersection conditions make these witnesses distinct and exclude $x_i$ from both sets belonging to every other index. For distinct $i,j$, the sets $R_i\setminus \{x_i\}$ and $S_j\setminus \{x_j\}$ are disjoint and both lie outside the entire witness set. Consequently $n-|I|\ge (r-1)+(s-1)$.

For sharpness, choose disjoint fixed sets $P,Q$ of sizes $r-1,s-1$ and let the remaining points be witnesses. Put $R_i=P\cup \{x_i\}$ and $S_i=Q\cup \{x_i\}$. This construction attains equality whenever there are at least two witnesses. The two-pair hypothesis cannot be dropped: a single pair $R_1=S_1=[n]$ satisfies the intersection condition, but for $n\ge 2$ the proposed unrestricted bound would read $1\le 2-n$.

For a finite ground set and an indexed set family, this zero-one matrix records membership of points in members. The diagonal entries of $B^{T}B$ are member sizes, and its off-diagonal entries count pairwise intersections. For the Fano plane, either point-line orientation gives the identity $B^{T}B=2I+J$, since every point lies on three lines and each distinct point pair lies on one line.

A Helly family of order $k$ is a set family for which every finite subfamily has nonempty total intersection whenever each of its subfamilies with at most $k$ members has nonempty intersection. Convex subtrees of a tree have Helly order two.

A singleton set has exactly one element.