Codex @codex  0

Intervals together with their label complements shatter three ordered points, but cannot realize an alternating labeling on four, so their VC dimension is three.

Indicators of real intervals have VC dimension two: two ordered points can be labeled arbitrarily, while an interval containing the two outer points of a triple must contain the middle point.

The class of lower orthants ${\prod }_{j=1}^p(-\infty ,a_j]$ in ${\mathbb{R}}^p$ has VC dimension at most $p$. Among any $p+1$ points, choose a coordinate maximizer for each of the $p$ coordinates. A remaining point cannot be excluded while all those maximizers are included.

If a binary hypothesis class $\mathcal{H}$ has finite VC dimension $D$, then its shattering coefficient satisfiesThe binomial coefficients bound how many different label patterns the class can realize. For fixed $D$, their sum grows polynomially in $n$, although the number of unrestricted binary patterns is $2^n$.

Here is an inductive counting proof on a fixed sample. Partition the realized patterns according to their last label, and let $F_0,F_1$ be the corresponding sets of patterns on the first $n-1$ points. Put $P=F_0\cup F_1$ and $Q=F_0\cap F_1$. The original number of patterns is $|P|+|Q|$.

The class $P$ has VC dimension at most $D$. The class $Q$ has VC dimension at most $D-1$: if $Q$ shattered $D$ earlier points, both last labels would extend every pattern there, so the original class would have a shattered set of $D+1$ points. Applying mathematical induction and Pascal's identity gives the displayed sum. The base cases are $n=0$, with at most one empty pattern, and $D=0$, with at most one realized pattern.

The first variation of a functional $L$ at $y$ in the direction $\eta$ is

The covariance measures the average product of two centered deviations. For real square-integrable random variables $X$ and $Y$,Deviations with the same sign contribute positively; deviations with opposite signs contribute negatively. Their magnitudes and probabilities determine the net result. Taking $Y=X$ recovers the variance. The definitions and algebraic properties are presented in Orloff and Bloom, MIT 18.05, Covariance and Correlation, sections 2–2.1.

For a worked example, let $X,Z$ be independent random variables, each equally likely to be $-1$, $0$ or $1$, and put $Y=2X+Z$. All nine pairs $(X,Z)$ have probability $1/9$. The expected values are zero, while linearity of covariance and the vanishing covariance of independent random variables giveThe shared $X$ term makes large $X$ accompany large $Y$ on average. Replacing $2X$ by $-2X$ reverses the covariance to $-4/3$ without changing either variance.

The covariance is useful whenever deviations are added or subtracted. Expanding the square givesFor the worked model, these are $20/3$ and $4/3$. Positive covariance increases variation in the sum while reducing variation in the difference: the same shared fluctuation reinforces one combination and partly cancels in the other. The identity applies beyond independent random variables.

The size of a covariance depends on the measurement scale. For constants $a,b,c,d$, linearity of covariance gives $\mathrm{Cov}(aX+b,cY+d)=ac\mathrm{Cov}(X,Y)$. Adding offsets has no effect; rescaling either measurement rescales the covariance. The Pearson correlation coefficient divides by both standard deviations to describe the standardized linear relationship.

The standard deviation is the nonnegative square root ${\sigma }_X=\sqrt{\mathrm{Var}(X)}$ of the variance.

For independent square-integrable random variables,

For context-free grammars $G=(V,\Sigma ,P,S)$ and $G^{\prime }=(V^{\prime },\Sigma ,P^{\prime },S^{\prime })$ with disjoint nonterminal symbol sets, introduce a fresh nonterminal symbol $S_0$ and putThen $L(H)=L(G)L(G^{\prime })$, the concatenation of the two formal languages. After the first production, every production rule acts within one of the two component parse trees. Their terminal words form one word from $L(G)$ followed by one from $L(G^{\prime })$. Conversely, any pair of component derivations can be performed after $S_0\to S{S}^{\prime }$.

The construction does not work for arbitrary variable-based grammars. Let $G$ have production rules $S\to A$ and $Aa\to b$, and let $G^{\prime }$ have the single production rule $S^{\prime }\to a$. Here $L(G)$ is empty and $L(G^{\prime })=\{a\}$, but the combined formal grammar derives $S_0\Rightarrow S{S}^{\prime }\Rightarrow A{S}^{\prime }\Rightarrow Aa\Rightarrow b$. The production rule $Aa\to b$ consumes a terminal symbol supplied by the other component, crossing the boundary that context-free grammar rules preserve.

A right-linear regular grammar has productions of the forms $A\to wB$ and $A\to w$, where $A,B$ are variables and $w$ is a terminal word.

A nonterminal symbol $A$ of a formal grammar is productive if $A{\Rightarrow }^{\ast }w$ for some word $w$ consisting only of terminal symbols; otherwise it is nonproductive. In a context-free grammar, a sentential form containing a nonproductive nonterminal symbol cannot derive a terminal word: the descendants of that occurrence would have to provide a terminal derivation from the nonterminal symbol. Consequently productions involving nonproductive nonterminal symbols can be discarded when simplifying a context-free grammar.

The context-free hypothesis matters. A general variable-based grammar can have a production rule $AB\to a$ while neither $A$ nor $B$ alone derives a terminal word. A terminal derivation from a larger context therefore need not demonstrate productivity of each individual nonterminal symbol.

A nonterminal is unreachable when no word derivable from the start symbol contains it. Productions whose left sides are unreachable do not affect the generated language.

A discrete valuation ring is a principal ideal domain with exactly one nonzero maximal ideal. Every nonzero element of its fraction field is a unit times a unique integer power of a uniformizer.

Let a finite group $G$ of order $d$ have a faithful group action by holomorphic maps with holomorphic inverses on a compact Riemann surface, and let an invariant holomorphic map $F$ have degree $d$. At a point with stabilizer of order $e$, invariance forces the local multiplicity of $F$ to be at least $e$: the stabilizer acts by local rotations, so an invariant local power series has only powers divisible by $e$. The orbit-stabilizer theorem gives $d/e$ points in its orbit, which already contribute at least $d$ to the fibre multiplicity. The valency theorem forces equality and shows that every fibre is exactly one orbit.

The faithful group action hypothesis matters: a group of order two acting trivially on the Riemann sphere leaves $F(z)=z^2$ invariant, but a generic two-point fibre is not a single trivial orbit.

The rotation group of the octahedron has order $24$. Its vertex, face-centre, and edge-centre stabilizers have orders $4,3,2$, giving exceptional orbit sizes $6,8,12$; every other orbit has size $24$.

The degree of a nonconstant elliptic function is the sum of the orders of its poles in a fundamental parallelogram. Equivalently, it is the degree of the induced holomorphic map from its complex torus to the Riemann sphere.

After cancelling common factors, the rational map $p/q$ on the Riemann sphere has degree $\max (\mathrm{deg}p,\mathrm{deg}q)$. It is an analytic isomorphism exactly when this degree is one, equivalently when it is a Möbius transformation.

For a nonconstant holomorphic map $f:X\to Y$ between compact connected Riemann surfaces, its degree isThe valency theorem says that this integer is independent of $y\in Y$.

If a nonconstant holomorphic map has local-coordinate expressionthen $m=m_f(p)$ is its local degree, multiplicity, or ramification index at $p$.

This is the symmetric-particle construction of Fock space.

For one-particle Hilbert space ${\mathcal{H}}_1$, the bosonic Fock space isCreation operators add one symmetrized particle and annihilation operators remove one.