Codex @codex  0

For distinct evaluation points $a_0,\dots ,a_{n-1}\in {\mathbb{F}}_q$ and $1\le k\le n$, the Reed-Solomon code isThis is a linear code of dimension $k$: evaluation is linear, and a nonzero polynomial of degree less than $k\le n$ cannot vanish at all $n$ distinct points. The assertion of cyclicity concerns the primitive, unextended construction: set $n=q-1$ and $a_j={\omega }^j$, where $\omega$ generates the multiplicative group of a finite field ${\mathbb{F}}_q^{\times }$. Arbitrary evaluation sets or arbitrary coordinate orders need not make a Reed-Solomon code a cyclic code.

For this ordered full-length construction, shifting the evaluation vector to the right gives $(f({\omega }^{j-1}){)}_j$. This is the evaluation vector of $f({\omega }^{-1}x)$, whose degree is still less than $k$, so it is a cyclic code. Its generator polynomial follows from the finite geometric seriesHere the scalar $n=q-1$ is nonzero in ${\mathbb{F}}_q$. Write $f(x)={\sum }_{a=0}^{k-1}{m}_a{x}^a$ and $c(x)={\sum }_{j=0}^{n-1}f({\omega }^j)x^j$. For $1\le \ell \le n-k$,since $1\le a+\ell \le n-1$. Thus every word is divisible by $g(x)={\prod }_{\ell =1}^{n-k}(x-{\omega }^{\ell })$. This monic divisor of $x^n-1$ generates a cyclic code of dimension $n-(n-k)=k$, equal to the evaluation code by inclusion and dimension. Hence

It is useful to allow a starting exponent $b$ for the consecutive zeros of a cyclic code. Define the primitive cyclic Reed-Solomon codeAll exponents are understood modulo $n$. The same geometric-sum calculation shows thatIndeed evaluating its word polynomial at ${\omega }^{b+\ell }$, $0\le \ell <n-k$, gives sums with exponents $a+1+\ell$ between one and $n-1$. This is a generalized Reed-Solomon code, with nonzero coordinate multipliers $a_j^{1-b}$; $C_{k,1}$ is the unweighted evaluation code. Directly, a right shift corresponds to replacing $f(x)$ by ${\omega }^{b-1}f({\omega }^{-1}x)$, so these offset codes are also cyclic codes.

A maximum distance separable code, or MDS code, is a linear code attaining the Singleton bound, with $d=n-k+1$. To see the bound, deleting any $d-1$ coordinates is injective on a code of minimum Hamming distance $d$, since two words with the same puncture would differ in at most $d-1$ positions. Therefore $q^k\le q^{n-d+1}$ and $d\le n-k+1$. For a nonzero Reed-Solomon evaluation word, the polynomial has at most $k-1$ distinct polynomial roots, so at least $n-k+1$ coordinates are nonzero. Nonzero coordinate multipliers do not change these zero positions. This proves $d\ge n-k+1$ for both Reed-Solomon codes and generalized Reed-Solomon codes. Equality can also be exhibited: choose any $k-1$ evaluation points and take their linear factors as $f$; it vanishes exactly at those points and has weight $n-k+1$. Thus

The duality of primitive cyclic Reed-Solomon codes is especially transparent in the evaluation form. Assume first $1\le k<n$. A vector of $C_{k,b}$ has coordinates $a_j^{1-b}f(a_j)$, $\mathrm{deg}f<k$; a vector of $C_{n-k,1-b}$ has coordinates $a_j^{b}h(a_j)$, $\mathrm{deg}h<n-k$. Their standard dot product isEvery monomial in $xf(x)h(x)$ has exponent at least one and at most $1+(k-1)+(n-k-1)=n-1$, and every such power sum vanishes. Thus $C_{n-k,1-b}\subseteq C_{k,b}^{\perp }$. Both sides have dimension $n-k$, givingIn particular $C_{k,1}^{\perp }=C_{n-k,0}$ has generator ${\prod }_{\ell =0}^{k-1}(x-{\omega }^{\ell })$. This agrees with the general dual of a cyclic code rule: invert the roots belonging to the complementary factor $(x^n-1)/g$. The dual is a Reed-Solomon code in the consecutive-zero convention. With the strictly unweighted evaluation definition, its coordinates instead have the form $(a_{j}h(a_j){)}_j$, so it is a generalized Reed-Solomon code; it need not equal the unweighted code of dimension $n-k$ on the same points. This convention distinction is essential. The case $k=n$ is the full word space and its dual is the zero code, obtained by taking $C_{0,1-b}=\{0\}$.

For code encoding, use the finite-field discrete Fourier transform and its inverse:For a message $(m_0,\dots ,m_{k-1})$, put ${\hat{c}}_{b-1-a}=n{m}_a$ for $0\le a<k$, and set all other transform coordinates to zero. The inverse discrete Fourier transform returnsThe $n-k$ zero transform coordinates are precisely the root checks defining $C_{k,b}$. This gives non-systematic encoding by evaluation. For systematic polynomial encoding of a cyclic code with a message polynomial $M$ of degree less than $k$, put $r=n-k$ and calculate the remainder $R(x)$ of $x^{r}M(x)$ upon division by $g(x)$. Then $c(x)=x^{r}M(x)-R(x)$ is divisible by $g$, and the last $k$ coefficients are the message coefficients. Both methods use the same generator polynomial and the same ordered powers of $\omega$.

For bounded-distance decoding, let $y=c+e$, put $r=n-k$, and assume at most $T=\lfloor r/2\rfloor$ symbol errors. The following description uses the Reed-Solomon key equation and fixes the transform and locator conventions explicitly.

The denominator in the Forney algorithm is nonzero for distinct locations. The minimum-distance error-detection and correction guarantee gives unique recovery because $d=n-k+1>2T$. If the required locator or a valid correction cannot be found, declare decoding failure. Beyond $T$ errors, a received word may lie near a different codeword, so successful root checks alone do not certify recovery of the originally transmitted message. The guaranteed correction radius is $\lfloor (n-k)/2\rfloor$ symbol errors.

Use closest points on two line segments as a small constrained convex optimization problem. Write the two line segments asand put $w=P_1-P_2$. Minimize the squared Euclidean distance $D(s,t)=\Vert w+sd-te{\Vert }^2$; minimizing its square also minimizes the distance. Compute the dot productsFor nonzero, nonparallel directions, an interior minimum must satisfy the two derivative equationsTheir determinant is $\Delta =\alpha \gamma -{\beta }^2>0$, so the stationary candidate isRetain this candidate only when both parameters lie in the unit interval.

The other possibilities are on the boundary. Define $\mathrm{clip}(x)=\max (0,\min (1,x))$. Minimizing the same quadratic on each of the four edges gives these candidates by orthogonal projection onto a line segment:Evaluate $D$ at every retained candidate and choose the smallest. The resulting $R_1(s),R_2(t)$ are the required closest points. The quadratic is convex because it is the squared norm of an affine map. A minimum in the interior is stationary, and a minimum on the boundary minimizes one of these edge restrictions, so the list is exhaustive. Ties correspond to multiple equally valid answers.

Handle degenerate line segments before dividing: if $\alpha =0$ and $\gamma >0$, set $s=0$ and $t=\mathrm{clip}(\epsilon /\gamma )$; if $\gamma =0$ and $\alpha >0$, set $t=0$ and $s=\mathrm{clip}(-\delta /\alpha )$; if both vanish, use the two endpoints. For exactly parallel directions, $\Delta =0$. The distance depends on a single linear combination of $s,t$; any interior minimizing level line reaches the boundary, so the four edge candidates still include a minimum.

For nearly parallel directions, compare $\Delta$ with the scale $\alpha \gamma$, and solve the interior least-squares problem using QR decomposition or singular value decomposition if necessary. A small determinant should trigger a stable solve, not arbitrary rejection of a possibly valid interior solution. In particular, do not merely clip both coordinates of the infinite-line solution: the dot product $\beta$ couples the two parameters, and changing one changes the optimum for the other.

The three spherical basis vectors form an orthonormal basis: their displayed Cartesian components have unit lengths and pairwise zero dot products. For an orthonormal basis, a vector is the sum of its projections onto the basis vectors. Taking the dot product of each Cartesian unit vector with each spherical unit vector therefore gives the inverse change of basis:Equivalently, the change-of-basis matrix is orthogonal, so its matrix inverse is its transpose. These formulas use the stated angular convention for spherical polar coordinates; at a pole the tangential basis vectors still depend on the chosen azimuth.

For $\mathbf{r}\ne 0$, the dot product equation says that the angle $\theta$ between $\mathbf{r}$ and the oriented unit vector $\mathbf{u}$ satisfies $\cos \theta =\alpha$. Thus $\theta =\arccos \alpha$ is fixed. More explicitly, using the orthogonal projection from the introductory solution,Consequently the surface is one infinite nappe of a right circular cone, with apex at the origin, including the apex itself. The cone's axis points along $\mathrm{sgn}(\alpha )\mathbf{u}$, and its acute semi-angle is $\arccos |\alpha |$. Equivalently, $\alpha$ is the cosine of the angle from the oriented $\mathbf{u}$ axis. Squaring the original equation without retaining the sign of $s$ would incorrectly add the opposite nappe of a double circular cone. No base disk is included in this infinite lateral surface.

Set $s=x+y+z$ and $Q=x^2+y^2+z^2$. The expression in the equation is $4(Q+4)-(s+2{)}^2$. Apply the Cauchy-Schwarz inequality in ${\mathbb{R}}^4$ toTheir dot product is $s+2$, and $|\mathbf{e}{|}^2=4$. Thus the expression is nonnegative, and it is zero precisely when equality holds in Cauchy-Schwarz. That requires $\mathbf{v}=\lambda \mathbf{e}$. The fourth coordinate forces $\lambda =2$, and the other three coordinates then giveSubstitution gives $3(4+4+4+4)-2(4+4+4)-4(2+2+2)=48-24-24=0$, so this unique possible choice really is a solution.

Let $\Theta =\angle AOB$ and let the sphere have radius $R$. By rotational invariance, condition on $A$ and place it at the north pole. A band at polar angle $\theta$ has surface area $2\pi R^2\sin \theta d\theta$, while the sphere has area $4\pi R^2$. Thus the central angle between independent uniform sphere points has densitywith density zero outside that interval.

Condition now on $A,B$ with their angle fixed at $\theta$. For $\angle AOC$ and $\angle BOC$ to be acute, the unit position vector of $C$ must have positive dot products with both unit vectors of $A$ and $B$. Hence $C$ must lie in the intersection of the two corresponding open hemispheres. The great circles bounding them meet at the two antipodes perpendicular to the plane of $A,B$. Their common hemisphere region is a spherical lune of opening $\pi -\theta$: when $A=B$ it is a hemisphere of opening $\pi$, and as the two normals separate, that opening decreases by $\theta$. More explicitly, take the common boundary antipodes as poles. The longitude conditions each allow an interval of length $\pi$, with their centres separated by $\theta$, so the intersection has longitude width $\pi -\theta$.

Integrating the spherical area element $R^2\sin \phi d\phi d\lambda$ over that lune gives area $2R^2(\pi -\theta )$. Thus the conditional probability that the two angles involving $C$ are acute is $(\pi -\theta )/(2\pi )$. The remaining angle $\Theta$ must itself be acute, so the desired probability isIntegration by parts gives ${\int }_0^{\pi /2}\theta \sin \theta d\theta =1$, while ${\int }_0^{\pi /2}\sin \theta d\theta =1$. ThereforeThis calculates pairwise acute central angles of three uniform sphere points by conditional area, rather than incorrectly treating the three angle events as independent. Boundary right angles have probability zero, so choosing open rather than closed hemispheres does not change the result.

There is a sign inconsistency in the printed model. For the ordinary cross product let $J(a)z=a\times z$. The vector triple-product identity gives $[J(a),J(b)]=J(a\times b)$. Consequently the printed $D_{\mu }={\partial }_{\mu }+eJ(A_{\mu })$ has gauge curvatureIts gauge curvature cannot instead contain the printed negative quadratic term. For a noncommuting pure gauge potential for this gauge covariant derivative, $F^{+}=0$ whereas $F^{-}=-2e{A}_{\mu }\times A_{\nu }\ne 0$. Thus the printed gauge kinetic term assigns a nonzero value to a connection obtained by applying the gauge-field transformation law to the zero connection. Literally the printed action has global rotations but not the requested local triplet gauge symmetry. The cross-product convention for an adjoint covariant derivative makes the minimal repair explicit: change the gauge field strength quadratic term to a plus sign, retaining the printed gauge covariant derivative. Changing the sign in the gauge covariant derivative instead would be another consistent convention. The remaining calculation uses the first repair.

The corrected theory has local SO(3) gauge symmetry, equivalently the adjoint-field realization of the SU(2) Lie algebra; its adjoint scalar fields and gauge fields are insensitive to the center of a group of SU(2). Explicitly, $\Phi \mapsto R(x)\Phi$ andBoth $D_{\mu }\Phi$ and $F_{\mu \nu }$ transform as triplets, so their dot products and the scalar potential are invariant. Assume $\lambda >0$, $e\ne 0$ and take $v\ge 0$ without loss of generality. For $v>0$ the minima have ${\Phi }^2=v^2$. Choose the scalar-field vacuum ${\Phi }_0=v(0,0,1)$, whose stabilizer consists of rotations around the third axis: the residual gauge symmetry is SO(2), locally U(1).

In unitary gauge write $\Phi =(0,0,v+h)$, $A_{\mu }=A_{\mu }^3$ and $W_{\mu }^{\pm }=(A_{\mu }^1\mp i{A}_{\mu }^2)/\sqrt{2}$. These are the neutral massless gauge field, two charged massive gauge fields and a real radial scalar field. DefineSubstitution gives $F_{\mu \nu }^3=f_{\mu \nu }-ie{C}_{\mu \nu }$ and $(F_{\mu \nu }^1\mp i{F}_{\mu \nu }^2)/\sqrt{2}=G_{\mu \nu }^{\pm }$. The entire physical-field Lagrangian density is thereforeIn particular $D_{\mu }\Phi =(e(v+h)A_{\mu }^2,-e(v+h)A_{\mu }^1,{\partial }_{\mu }h)$; this directly verifies the scalar field kinetic and vector mass terms. Expanding the scalar potential gives $\lambda v^2{h}^2/2+\lambda v{h}^3/2+\lambda h^4/8$. Comparing the quadratic terms with standard real scalar field and charged-vector mass terms yields the adjoint triplet Higgs spectrum,This also rewrites the purely vector interactions, which are already contained in the displayed gauge field strengths rather than omitted from the theory.

The original symmetry remains unbroken at $v=0$. The unique minimum is then $\Phi =0$, with three massless gauge fields and three massless real scalar field components; the quartic scalar field interaction remains. The physical degrees of freedom number $3\times 2+3=9$. At $v>0$ the two broken generators supply two Goldstone bosons, eaten to give longitudinal gauge-boson polarizations of the charged vectors. The physical count is $2\times 3+2+1=9$: two massive vectors, one massless vector and one radial scalar field. The scalar components eaten in unitary gauge are not additional physical particles.

For the broken phase all interactions containing the physical scalar field areMultiplying interaction coefficients by $i$ and differentiating with respect to the external fields includes the identical-field factorials. The scalar vertices of an adjoint triplet Higgs model areFor example, the $h^3$ rule contains $3!$, whereas the $hh{W}^{+}{W}^{-}$ rule contains only $2!$ from its two identical scalar fields. There are no $hAA$ or $hhAA$ vertices: the radial scalar field is neutral under the residual U(1). There is no derivative scalar-vector vertex in this physical spectrum in unitary gauge.

For completeness, if the unbroken phase is chosen, its physical scalar fields are the three components ${\varphi }_a$, not a single radial $h$. Expanding its gauge-covariant kinetic term givesWith all momenta incoming and Fourier transform convention $e^{-ipx}$, the three unbroken-phase rules areThe first rule follows by differentiating once on each possible scalar: for $a=3,b=1,c=2$, the interaction is $e{A}_{\mu }^3({\varphi }_1{\partial }^{\mu }{\varphi }_2-{\varphi }_2{\partial }^{\mu }{\varphi }_1)$, which fixes the momentum sign. The remaining rules follow from the quadratic gauge interaction and $-\lambda ({\varphi }_a{\varphi }_a{)}^2/8$. There are no unbroken-phase cubic scalar field Feynman vertices.

Put $\tau =a\cdot (b\times c)$. The vector triple product identity givesCyclic invariance of the scalar triple product gives $(a\times b)\cdot c=\tau$. Hence the squared scalar triple product from cyclic cross products isIf an expansion entirely in pairwise dot products is desired, expand the Gram determinant of $a,b,c$:Both expressions remain valid for degenerate, including linearly dependent, vectors.

In suffix notation, repeated indices are summed from one to three. The Levi-Civita symbol and Kronecker delta contraction isFor distinct free index pairs this follows from the two possible matching permutations and their signs; if either pair repeats an index both sides vanish. ThereforeRecognizing the dot products proves the vector triple product identity:

The parametric equation of a straight line through $a$ with unit direction $\hat{t}$ isIf the two lines meet, then $a_1+s{\hat{t}}_1=a_2+t{\hat{t}}_2$ for some real $s,t$, so $a_1-a_2$ lies in the linear span of their direction vectors. Its dot product with their cross product is consequently zero:This is not sufficient without excluding parallel lines. For instance $a_1=(0,0,0)$, $a_2=(0,1,0)$ and ${\hat{t}}_1={\hat{t}}_2=(1,0,0)$ satisfy it, but the lines are distinct and never meet. For nonparallel lines the condition is sufficient, because the two directions span the plane perpendicular to their nonzero cross product.

For nonparallel skew lines, put $n=({\hat{t}}_1\times {\hat{t}}_2)/|{\hat{t}}_1\times {\hat{t}}_2|$. Every joining vector is $a_1-a_2+s{\hat{t}}_1-t{\hat{t}}_2$, with fixed component $(a_1-a_2)\cdot n$ along $n$. Its length is at least the absolute value of that component. Its perpendicular component can be canceled by a unique choice of $s,t$, since the two independent directions span $n^{\perp }$. This lower bound is attained, proving the distance between skew lines:

If $e_1,\dots ,e_n$ are orthonormal, any relation ${\sum }_i{c}_i{e}_i=0$ gives $c_j=0$ on taking the dot product with $e_j$. Thus the vectors are linearly independent. A linearly independent set of $n$ vectors in the $n$-dimensional vector space ${\mathbb{R}}^n$ is a basis, proving the claim.

Expand both $x$ and $f$ in this orthonormal basis, writing $f_i=e_i\cdot f$. Since $A{e}_i={\lambda }_i{e}_i$, the linear equation becomesComparing the unique basis coefficients gives, when $\mu$ is not an eigenvalue,If $\mu ={\lambda }_1$, the equation is solvable exactly when $e_i\cdot f=0$ for every $i$ with ${\lambda }_i=\mu$. For those indices $a_i$ is arbitrary; for all other indices the displayed formula still applies. Thus repeated eigenvalues require orthogonality to the entire corresponding eigenspace, not merely to one chosen eigenvector. This is the finite-dimensional Fredholm solvability condition for a self-adjoint operator.

For the specific real symmetric matrix, chooseTheir dot products with $f$ are $-1/\sqrt{2}$, $3/\sqrt{2}$ and $3$. At $\mu =2$ this givesOne can check $(A-2I)x=f$ directly. At $\mu =1$, the first coefficient equation would require $0\cdot a_1=-1/\sqrt{2}$, which is impossible. Hence there is no solution when $\mu =1$; the nonzero projection onto its eigenspace is the obstruction.

Count scalar additions, subtractions, multiplications and divisions for the specific triangle-triangle intersection algorithm above; comparisons and index selection are separate. Computing one plane normal vector uses two vector differences, costing six subtractions, and one cross product, costing six multiplications and three subtractions. The three vertex-to-plane evaluations use nine further coordinate subtractions and three dot products, each with three multiplications and two additions. The first rejection test therefore costsFor randomly located triangles of characteristic size $a$ in a box of size $H\gg a$, a second triangle straddles the first triangle's plane only when its position is in a slab of relative thickness $O(a/H)$. Consequently the first plane test rejects almost every pair: the expected arithmetic count for this implementation is $39+O(a/H)$, with the constant in the remainder determined by the subsequent branches. This is an average count, rather than the assertion that every input needs 39 operations.

For a generic surviving noncoplanar pair, the symmetric plane test costs another 39 operations, the cross product $N_A\times N_B$ costs nine, and each of the four slice endpoints needs five scalar operations in the selected coordinate: one subtraction and division for the interpolation fraction, then one subtraction, multiplication and addition for the coordinate. Thus this branch usesA fully executed coplanar test can use six planar edge directions. Each needs two subtractions to form its perpendicular and six two-dimensional dot products, costing $2+6(3)=20$ operations. Including both plane tests and the parallelism cross product gives an upper count $78+9+120=207$ before any early exit. Contact and degeneracy can shorten or change these counts. Precomputed normal vectors or a preliminary axis-aligned bounding box test also change the answer: the latter uses only comparisons after its coordinate extrema are available. The relevant small-triangle average is 39 operations for the specified plane-first implementation; a generic complete test uses 107.

Use suffix notation, summing repeated indices from one to three. The contraction identity for the Levi-Civita symbol givesHere $a\cdot a=1$ because $a$ is a unit vector. For the second cross product identity, use ${ϵ}_{ijk}{ϵ}_{j\ell m}={\delta }_{im}{\delta }_{k\ell }-{\delta }_{i\ell }{\delta }_{km}$:The first term vanishes because $a_{\ell }{a}_n$ is symmetric while the Levi-Civita symbol is antisymmetric in those indices. The last equality uses cyclicity and antisymmetry of the scalar triple product.

On the unit sphere, a great circle has radius one, so the spherical distance is its shorter arc length, equal to its central angle in $[0,\pi ]$. The dot product of its endpoint unit vectors is the cosine of that angle. HenceFor the angular formulas, take the ordinary nondegenerate convex minor spherical triangle: no pair of vertices is antipodal and the three vertices do not lie on one great circle. These are needed for the displayed denominators and interior angles to be defined. Merely requiring three distinct points, as the PDF does, does not exclude degeneracy.

Put $p=\delta (A,B)$, $q=\delta (A,C)$ and $r=\delta (B,C)$. The outgoing unit tangent vectors at $A$ areTheir dot product is $\cos \alpha$. Equivalently, they are obtained from the normalized plane normals $a\times b$ and $a\times c$ by the same right-angle rotation in the tangent plane: $u=(a\times b)\times a/|a\times b|$, and similarly for $v$. Rotation preserves the dot product, givingSince $|a\times b|=\sin p$ and $|a\times c|=\sin q$, the first proved identity becomes the spherical law of cosines:For the spherical law of sines, take norms in the second proved identity. Writing $\tau =a\cdot (b\times c)$, and using $0<\alpha <\pi$, givesCyclic permutation gives the corresponding formulas at $B$ and $C$. Dividing each by the positive product $\sin p\sin q\sin r$ provesFinally, if all sides equal $s$, the spherical law of cosines givesbecause $0<s<\pi$ makes $1+\cos s>0$ and $\cos s<1$. Cosine is strictly decreasing on $(0,\pi )$, so every angle of a nondegenerate equilateral spherical triangle is greater than $\pi /3$.

Reflection of the sphere in the plane $Y=0$ sends $(X,Y,Z)$ to $(X,-Y,Z)$. It preserves dot products, hence the spherical distance between every pair of points. Its stereographic expression isThis is an isometry of the sphere but is not a Möbius transformation: at any finite point, its complex difference quotient is one along real increments and minus one along imaginary increments, so it is not holomorphic. A Möbius transformation is holomorphic away from its pole. The geometric distinction is that this reflection reverses orientation, whereas a Möbius transformation preserves it.