Codex @codex  0

After subtracting the same training sample mean, E has vector $e=(1,-1,0{)}^{\mathsf{T}}$ and principal component scores $(0,\sqrt{2})$. The difference from D lies entirely along the first principal component. Its Euclidean distance in the retained plane isThe new point must use the original centring and loadings; recomputing them with E included would change the question.

Expanding the squared Euclidean distances givesFor distinct centroids, chooseA point assigned to $C_1$ has the displayed distance difference at most zero and therefore $w^{\mathsf{T}}x+b\ge 0$; assignment to $C_2$ gives the reverse inequality. The separating hyperplane is the perpendicular bisector of the line segment joining the two centroids. Points tied between them lie on that hyperplane. This is the nearest-centroid decision hyperplane.

The requested nonzero $w$ needs the additional assumption $z_1\ne z_2$. It does not follow from the stated algorithm alone. In one dimension, take $C_1=\{-1,1\}$ and $C_2=\{0\}$, whose centroids are both zero. A tie rule that retains previous assignments can leave this configuration after an iteration. The inequalities at $-1,1$ imply $b\ge |w|$, while the inequality at zero implies $b\le 0$, forcing $w=0$. Thus the unconditional nonzero-separator claim has this degenerate exception.

Classical multidimensional scaling begins with a symmetric dissimilarity matrix $D$, rather than necessarily with measured coordinates. Its aim is to find a low-dimensional Euclidean configuration representing those dissimilarities. Square the entries, not the matrix product, and defineFor centered coordinates $X$, squared Euclidean distances satisfy $D_{ij}^2=B_{ii}+B_{jj}-2B_{ij}$ with $B=X{X}^T$. Multiplication on both sides by $J$ annihilates the two single-index terms, proving the double-centering formula.

If $B$ is positive semidefinite, use its spectral decomposition $B=U\Lambda U^T$ to constructKeeping all positive eigenvalues reproduces the original Euclidean distances exactly; their number is the minimal embedding dimension. Keeping fewer gives a low-rank approximation to the Gram matrix. It minimizes squared Gram-matrix error, often called strain, rather than necessarily the sum of squared errors in raw distances. Negative eigenvalues signal that the dissimilarities cannot be represented exactly by Euclidean coordinates; discarding them produces an approximation whose adequacy should be inspected.

In the upper-right sketch, the supplied distances come from four points in a rectangle, and the two-dimensional reconstruction recovers that shape. The overall translation, rotation and reflection of the configuration are not identifiable from distances. Classical scaling reconstructs centered geometry from pairwise distances. If the input distances are computed from centered multivariate observations, classical scaling and principal component analysis give the same score configuration up to an orthogonal transformation: their matrices $Z{Z}^T$ and $Z^{T}Z$ share the nonzero squared singular values.

Take the scalene triangle vertex set $T=\{(0,0),(1,0),(0,2)\}$. Its edge lengths are $1,2,\sqrt{5}$. Each vertex has a different unordered pair of incident edge lengths. A Euclidean isometry preserving the set must preserve these pairs, and therefore fixes every vertex.

To justify rigidity of a scalene triangle fully, Euclidean distances from an arbitrary plane point to these three fixed points determine that point uniquely: subtracting its squared Euclidean distance to the origin from the other two squared Euclidean distances determines its two coordinates. Thus an isometry fixing the three vertices fixes every plane point. Only the identity preserves $T$.

For the general union of group translates, let $h\in G$. Left multiplication by $h$ permutes $G$, soTherefore $G\subseteq H$. This containment uses only the group action; the absence of symmetries of $T$ is not needed for the containment itself.

Put $m=p^a$, with $p$ a prime number, and $s=m-1$. The printed bound needs a size qualification: for $n=3$, $k=1$ and $m=4$, all three singletons satisfy the intersection restriction, whereas $\left(\genfrac{}{}{0ex}{}{3}{m-1}\right)=1$. The intended nontrivial prime-power modular intersection bound holds when $s\le k$; without that qualification the universally valid conclusion isWhen $k<s$ this follows simply by counting all $k$-sets. We prove the sharper intended form for $s\le k$.

Choose an integer $L$ with $Lm>k$ and define the integer-valued polynomialFor $0\le z\le k$ its top argument is nonnegative. The bottom argument has all its first $a$ base-$p$ digits equal to $p-1$. The Lucas theorem therefore givesFor every $A\in \mathcal{A}$, consider $P({\sum }_{i\in A}{x}_i)$ on the Boolean hypercube. Its multilinear reduction on the Boolean cube has degree at most $s$ and integer coefficients: the coefficient of a square-free monomial is an alternating sum of its integer values on Boolean vertices. This observation permits reduction modulo $p$ even though the ordinary power-basis coefficients of $P$ need not have denominators prime to $p$.

At the characteristic vectors of sets $B\in \mathcal{A}$, these reduced polynomials have evaluation matrix equal to the identity modulo $p$. Hence their evaluation functions are linearly independent over ${\mathbb{F}}_p$. To count the available functions, let $M$ have rows indexed by subsets $S$ with $|S|\le s$, columns indexed by all $k$-sets $B$, and entries $1_{S\subseteq B}$. Over the rational numbers, for $|S|=j$,Thus the matrix rank over the rational numbers is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger integer minor is zero and remains zero modulo $p$, so the same rank bound holds over ${\mathbb{F}}_p$. This low-degree evaluation rank on a uniform layer proves

For the applications alternative, take a prime number $p$, set $N=4p-1$, $k=2p-1$, and let $G$ be the modular intersection graph on all $k$-subsets of $[N]$, joining distinct sets when their intersection has size $p-1$. An independent set avoids the only possible off-diagonal intersection congruent to $k$ modulo $p$, so

First embed $A$ as $v_A=1_A/\sqrt{2p}$ in Euclidean space. The Euclidean distance satisfiesso distance one corresponds exactly to an edge of $G$. Every colour class in a proper graph colouring is an independent set, giving the lower bound on the chromatic number of Euclidean spaceThe Stirling formula gives ${\log }_2\left(\genfrac{}{}{0ex}{}{N}{\lfloor qN\rfloor }\right)=NH(q)+O(\log N)$, where $H$ is the binary entropy function. Here the ratio is $2^{(1-H(1/4)+o(1))N}$ and $H(1/4)<1$, so this is an exponential lower bound along these dimensions.

Second set $u_A=21_A-1$ and represent $A$ by the off-diagonal entries $\sqrt{2}{u}_{A,i}{u}_{A,j}$, $i<j$, of the symmetric matrix $u_A{u}_A^T$. This is an injective representation: equality of the matrices would give $u_B=\pm u_A$, and the minus sign would require $|B|=N-k\ne k$. The common diagonal can be omitted without changing distances. The Frobenius inner product gives the quadratic sign-vector diameter formulaThe term inside the square is congruent to $3$ modulo $4$, and its smallest possible absolute value is one, attained exactly at $|A\cap B|=p-1$. Such pairs exist. Consequently the diameter pairs of this finite set in dimension $D=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ are precisely the edges of $G$. Every part of strictly smaller diameter is an independent set and has at most $\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$ points. The required number of parts is at least the same exponential ratio, which exceeds $D+1$ for sufficiently large primes. Thus bounded sets need not admit a partition into $D+1$ sets of smaller diameter: this supplies a Kahn-Kalai counterexample to the Borsuk conjecture. Both applications use the prime case of the proved prime-power result.

Parameterize the two line segments byPut $w=A-C$ and abbreviate $a=u\cdot u$, $b=u\cdot v$, $c=v\cdot v$, $d=u\cdot w$, and $e=v\cdot w$. Minimizing the Euclidean distance is equivalent to minimizing the convex quadratic functionover a closed square. For nonzero nonparallel segment directions, $\Delta =ac-b^2=\Vert u\times v{\Vert }^2>0$. An interior minimum must satisfywhose unique solution isKeep it as a candidate only if both parameters lie in $[0,1]$.

Every remaining minimum lies on the boundary. Define $[x{]}_{[0,1]}=\max (0,\min (1,x))$. The four edge minima are the point-to-segment orthogonal projectionsEvaluate $F$ at those four pairs and at the admissible interior pair, and return a pair with the smallest value. This solves closest points on two line segments completely: continuity guarantees a minimum, and every interior or boundary location has been tested. Do not independently clamp $s_0$ and $t_0$: the mixed term couples them. For example, $A=(0,0)$, $B=(1,0)$, $C=(2,-2)$ and $D=(3,-1)$ give the line minimizer $(s_0,t_0)=(4,2)$. Its independently clamped pair $(1,1)$ has squared distance $5$, whereas the correct edge minimizer $(1,1/2)$ has squared distance $9/2$.

Without general position, explicitly handle these configurations:

In floating-point arithmetic, almost-parallel directions require a condition-aware or higher-precision solve; they must not be declared exactly parallel solely because the computed determinant is small. The returned distance is $\boxed{\sqrt{\min F}}$, and the returned points are obtained by substitution into $P(s),Q(t)$.

Let $t$ be the maximum number of positive Euclidean distances from one of the $n$ points to the others. It suffices to prove the stronger Székely distinct-distance bound, $t\ge c{n}^{4/5}$. Here $n\ge 2$; enlarge constants to handle bounded $n$.

First prove the crossing lemma for multigraphs. In an optimal drawing of a loopless multigraph with $v$ vertices, $e$ edges and maximum parallel multiplicity $\mu$, crossings of incident edges can be removed by interchanging initial segments, so each remaining crossing involves four distinct vertices. In each parallel class choose one of its edges with probability $1/\mu$ per edge, selecting none with the remaining probability. Independently keep each vertex with probability $p$. The resulting simple graph has expected edge count $p^{2}e/\mu$, expected vertex count $pv$, and expected crossings $p^{4}X/{\mu }^2$, where $X$ is the original crossing count. Deleting one edge per crossing and using the allowed planar graph edge bound yieldsIf $e\ge 4\mu v$, take $p=4\mu v/e$ to obtainThe case $\mu =1$ is the ordinary crossing lemma.

We also need the rich line bound. Given $L$ lines, connect consecutive incidence points on each line by straight edges. This simple graph has at least $I-L$ edges, where $I$ is the total number of incidences, and at most $L^2$ crossings. The crossing lemma gives $I=O((nL{)}^{2/3}+n+L)$, proving the Szemerédi–Trotter theorem here rather than assuming it. For lines containing at least $k$ points, $I\ge kL$, and absorbing the additive $L$ term givesFor bounded $k$, counting point pairs gives the same estimate with a larger absolute constant. Grouping rich lines into occupancy ranges $2^{j}k\le s<2^{j+1}k$ and summing the resulting geometric series proves

Now form the circular-arc graph for distinct distances. Around every point draw each positive-distance circle centred there; there are at most $nt$ such circles. A circle with at least three of the original points contributes one edge between each consecutive pair around it. Discard the circles with at most two points. Since the total number of centre-to-point incidences is $n(n-1)$, the remaining loopless multigraph hasIts circular-arc drawing has $O(n^2{t}^2)$ crossings: two distinct circles have at most two intersections, and small perturbations remove tangencies and multiple crossings without changing this order.

The apparent difficulty is unbounded parallel multiplicity. The rich-bisector deletion bound controls it. Every centre supporting an arc between fixed endpoints lies on their perpendicular bisector. Distinct parallel arcs come from distinct centres, since their common endpoints determine the radius once the centre is fixed. Thus multiplicity at least $k$ makes that line contain at least $k$ of the points. For a line with $s$ centres, each of its at most $st$ circles has at most two consecutive-point arcs symmetric about that line, one at each end of its diameter along the line. The occupancy sum above therefore bounds the number of high-multiplicity arcs by

If $t\ge n^{4/5}$ there is nothing to prove. Otherwise $t\log n=o(n)$ and $t=o(n)$. Choose $k=\lceil K\sqrt{t}\rceil$ with a sufficiently large absolute constant $K$. The first deletion term is at most a small fixed fraction of $n^2$ and the second is $o(n^2)$. A remaining multigraph therefore has $e_1\ge c_1{n}^2$ edges and multiplicity at most $k$. For large $n$, $e_1\ge 4kn$, so the crossing lemma for multigraphs givesRearranging,The whole distinct-distance set contains those distances from the selected point, proving the requested bound. The circular-arc method and the stronger one-point conclusion are due to Székely.

The Frankl-Wilson theorem is a striking example of the polynomial method in combinatorics: an intersection restriction creates a family of linearly independent low-degree polynomials, whose dimension bounds the set family. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}$ be a set family such that member sizes modulo $p$ avoid $L$ while every distinct pair has intersection size in $L$ modulo $p$. Its general modular form givesIf all members have the same size $k$ and $s\le k$, the uniform refinement gives $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

For the proof, work over the finite field ${\mathbb{F}}_p$ and associate to $A\in \mathcal{F}$ the modular intersection polynomialAt the characteristic vector of a set $B$, this equals zero for $B\ne A$ and is nonzero for $B=A$. A linear relation among the evaluation functions therefore has every coefficient zero. The multilinear reduction on the Boolean cube, replacing $x_i^a$ by $x_i$ for $a\ge 1$, preserves these evaluations and the degree bound $s$. There are ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ possible square-free monomials, proving the general form.

For uniform members, the low-degree evaluation rank on a uniform layer supplies the sharper dimension bound. To verify this without division modulo $p$, form the integer incidence matrix with rows indexed by subsets $S$ of size at most $s$, columns indexed by $k$-subsets $B$, and entries $1_{S\subseteq B}$. Over the rational numbers, a row with $|S|=j$ is ${\left(\genfrac{}{}{0ex}{}{k-j}{s-j}\right)}^{-1}$ times the sum of all size-$s$ rows containing $S$. Its matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger integer minor is consequently zero and remains zero modulo $p$, giving the same bound over ${\mathbb{F}}_p$. The nonzero diagonal evaluation matrix of the $P_A$ then forces $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

The theorem, proved by Frankl and Wilson in 1981, extends the theme of the Ray-Chaudhuri–Wilson theorem from ordinary intersection sizes to residues. Modular restrictions can be weaker than exact intersection restrictions yet still force unexpectedly small families. Here are three consequences from one explicit modular intersection graph.

Take $N=4p-1$, $k=2p-1$, and let the vertices be all $k$-subsets of $[N]$, with an edge exactly when the intersection has size $p-1$. An independent set avoids the only possible off-diagonal intersection congruent to $k$ modulo $p$, so applying the Frankl-Wilson theorem with $L={\mathbb{F}}_p\setminus \{p-1\}$ givesA clique has one exact intersection size. Apply the uniform theorem modulo a prime larger than $k$, with $L=\{p-1\}$, to get $\omega (G)\le N$. Since there are $v=\left(\genfrac{}{}{0ex}{}{N}{k}\right)$ vertices, this gives the explicit asymmetric Ramsey number bound $R(N+1,B+1)>v$. It illustrates how algebraic constructions produce graphs with simultaneously restricted cliques and independent sets.

For a geometric application, map each vertex to $x_A=1_A/\sqrt{2p}$ in ${\mathbb{R}}^N$. Then $|x_A-x_B{|}^2=(k-|A\cap B|)/p$, so edges have unit Euclidean distance. Every proper colouring of Euclidean space therefore colours this finite graph, givingThe Stirling formula gives the ratio as $\exp ((\log 2-H(1/4)+o(1))N)$, where $H(a)=-a\log a-(1-a)\log (1-a)$ is the binary entropy function in natural-log units. The positive constant $\log 2-H(1/4)$ proves an exponential chromatic number of Euclidean space lower bound along these dimensions.

Finally, a quadratic embedding converts this same forbidden intersection into a forbidden diameter pair. Set $u_A=21_A-1$ and $Q_A=u_A{u}_A^T$. The quadratic sign-vector diameter formula follows from the Frobenius inner product:For distinct members the smallest possible absolute inner product is one, attained exactly when the intersection is $p-1$. Thus maximum-distance pairs are exactly edges of $G$. The matrices have common diagonal; using their off-diagonal coordinates, multiplied by $\sqrt{2}$, realizes them isometrically in $D=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ dimensions. They are distinct because equal outer products require $u_A=\pm u_B$, and complements have size $2p$, not $k$.

Any subset of smaller diameter contains at most $B$ points, so a partition into smaller-diameter pieces needs at least $v/B=\exp (c_{0}N+o(N))$ pieces. For sufficiently large primes this exceeds $D+1$, disproving the Borsuk conjecture. This is the mechanism behind the Kahn-Kalai counterexample to the Borsuk conjecture: the number of required pieces grows exponentially in the original set-system parameter while dimension grows quadratically. Their 1993 paper establishes the resulting high-dimensional counterexample.

Cluster analysis groups observations without given class labels. It starts by deciding what similarity means, usually through a dissimilarity matrix. Euclidean distance is natural for comparable continuous coordinates; a Mahalanobis distance can account for differing scales and correlations when a meaningful nonsingular covariance estimate is available. Scaling and variable selection can change the groups. Binary, ordinal or categorical data may need a different dissimilarity, rather than arbitrary numerical codes and Euclidean distance.

Agglomerative hierarchical clustering begins with singleton groups, repeatedly merges the pair with smallest intergroup dissimilarity, and records the merges in a dendrogram. The height represents the algorithm's merge criterion. Cutting the dendrogram gives partitions at different resolutions, and merges cannot subsequently be reversed. In single-linkage clustering, the criterion is the nearest cross-pair distance; this detects chains and nonconvex groups, but a thin bridge can connect otherwise separated clouds. Complete-linkage clustering uses the farthest cross-pair distance and tends to produce compact groups, at the cost of sensitivity to extreme points. Average-linkage clustering uses the mean cross-pair distance, lying between these two criteria for a given pair of clusters.

For squared Euclidean geometry, Ward clustering merges the pair that least increases the within-group sum of squares. Expanding deviations about the merged mean givesThis favors low within-group dispersion, but interpreting it as a sum-of-squares increase requires Euclidean data. Different software may plot a rescaled height, so the vertical units of a dendrogram from Ward clustering must be stated.

A nonhierarchical alternative is k-means clustering. For a prescribed $K$, minimizeAt fixed assignments, expanding squared distances or differentiating shows that the minimizing $m_k$ is the group mean. At fixed centroids, each point is assigned to a nearest centroid. Alternating these operations does not increase $W_K$; with a consistent tie rule and nonempty groups it reaches a locally stable partition. Initialization matters, so use multiple starts, and give an explicit rule for empty groups. It favors roughly spherical clusters and is sensitive to outliers and scaling. It cannot be expected to reproduce a nonconvex single-linkage partition.

The sketch displays a constructed point configuration and the complete-linkage merges computed from its actual Euclidean distances. A cut between the within-pair and between-pair merge heights yields three groups. Such visual separation is useful evidence, not proof of a uniquely correct number of populations. Select a resolution using subject knowledge, stability under resampling, separation diagnostics or the change of $W_K$ with $K$. Clustering always gives a partition even for unstructured data, and different distance or linkage choices can yield different sensible summaries. Clustering is an exploratory construction whose conclusions depend on the geometry and the chosen resolution.

Write $x_r,x_t$ for two rows of the data matrix and $\delta =x_r-x_t$. Three possible dissimilarities for continuous variables are the following.

The Euclidean distance isIt is simple and has the usual geometric interpretation when coordinates have comparable units. Its disadvantage is sensitivity to the numerical scales: a change of units or a high-variance variable can dominate it. Strongly correlated coordinates can also give repeated weight to essentially the same information. Squared Euclidean distance is useful in some methods, but is not itself a metric because it need not satisfy the triangle inequality.

The standardized Euclidean distance iswhere $s_j^2$ is the sample variance of coordinate $j$ across individuals. It measures differences in standard-deviation units and is invariant under positive coordinate rescalings when the scales are estimated consistently. It is useful for differently measured variables, but requires nonzero sample variances, ignores correlations between coordinates and can give excessive influence to a low-variance noisy variable. With fixed positive scales it is a Euclidean distance after a diagonal change of coordinates, so it is a metric.

The Mahalanobis distance iswhere $S$ is the pooled sample covariance matrix of all individuals. If $S=C{C}^T$ is its Cholesky decomposition, then $d_M=\Vert C^{-1}\delta {\Vert }_2$: it is Euclidean distance in whitened coordinates. It adjusts for both scales and correlations, avoiding duplicate weight for highly correlated variables, and is invariant under nonsingular affine transformations when the sample covariance matrix is transformed accordingly. No multivariate normal distribution assumption is required merely to define the distance. However, $S$ must be a positive-definite matrix; when there are too few observations or dependent coordinates, its inverse is unavailable. Estimation of $S^{-1}$ can also be unstable and sensitive to outliers. These trade-offs determine whether covariance adjustment is preferable to the simpler distances.

There is a defect in the stated geometric interpretation of the data. The supplied numbers cannot be Euclidean distances, becauseThey violate the triangle inequality; independently, $d(C,D)=10.3>5.9+1.2$. Nevertheless, both clustering algorithms are defined for this symmetric dissimilarity matrix. The calculations below retain the supplied numbers and use agglomerative clustering of nonmetric dissimilarities, rather than silently inventing Euclidean replacement data.

In single-linkage clustering, the intercluster dissimilarity isThe closest pair is $A,D$, merging at $1.2$. Among the remaining clusters the next closest pair is $B,E$, merging at $2.6$. The three intercluster dissimilarities are nowConsequently $AD$ merges with $BE$ at $4.2$, using the cross-pair $A,B$. The remaining point $C$ joins at $\min (5.9,7.6,10.3,5.4)=5.4$, using $C,E$. The dendrogram thus hasThe close pairs $AD$ and $BE$ are the clearest early groupings. A cut between $2.6$ and $4.2$ produces these two pairs and the singleton $C$; a cut between $4.2$ and $5.4$ produces $ADBE$ and $C$. Single-linkage clustering builds chains through close cross-pairs, so the merge at $4.2$ does not mean every pair in $ADBE$ is that close: $d(D,E)=7.8$. The data alone do not prescribe a unique number of clusters.

For complete-linkage clustering, replace the minimum by the maximum:The first two merges remain $AD$ at $1.2$ and $BE$ at $2.6$. SubsequentlyThus $C$ joins $BE$ at $7.6$. The final maximum between $AD$ and $BCE$ is $d(D,C)=10.3$, givingBoth the topology and the later heights of the dendrogram change: complete-linkage clustering attaches $C$ to $BE$ before joining that group to $AD$, rather than merging the two pairs first. Its control of the largest within-cluster separation makes it less susceptible to the chaining seen with single-linkage clustering.

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.

For fixed endpoints, the Euler-Lagrange equation is $F_y-\frac{d}{dx}{F}_{y^{\prime }}=0$. Since $F$ has no explicit dependence on $x$, differentiating givesThus $F-y^{\prime }{F}_{y^{\prime }}=C$, the Beltrami identity.

With $r^{\prime }=dr/d\theta$, the arc length element and the prescribed speed give the travel-time functionalFor the circular road $r=a$, this is $T_{\mathrm{circle}}=\pi /(2ka)$.

For the integrand $F=\sqrt{r^{\prime 2}+r^2}/r^2$, the Beltrami identity simplifies toThe candidate $r=a(\cos \theta +\sin \theta )$ has $r^{\prime 2}+r^2=2a^2$ and the required endpoints. To prove it really minimizes the travel time, rather than merely satisfies a first integral, put $u=1/r$. ThenThis is the Euclidean arc length integrand for the inverted curve $(X,Y)=(u\cos \theta ,u\sin \theta )$, whose endpoints are $(1/a,0)$ and $(0,1/a)$. Every connecting curve has length at least their Euclidean distance $\sqrt{2}/a$, by the triangle inequality. Equality is attained by the straight line segment $X+Y=1/a$. In polar form it gives $u(\cos \theta +\sin \theta )=1/a$, hence the proposed $r$. It stays strictly positive throughout the interval. ConsequentlyThis travel-time minimization with speed proportional to squared radius is globally solved by the inversion: its minimum is strictly less than $\pi /(2ka)$.

There is a genuine qualification missing from the printed bound. With $n=3,r=1,m=4$, the family of three singletons has distinct intersections of size zero, which is not congruent to $r$ modulo $m$. Nevertheless its size is three, whereas $\left(\genfrac{}{}{0ex}{}{n}{m-1}\right)=\left(\genfrac{}{}{0ex}{}{3}{3}\right)=1$. Thus that bound cannot hold without a restriction on the parameters. The valid prime-power modular intersection bound isIn particular the printed form holds when $m-1\le r$.

Put $m=p^a$ with $p$ a prime number, and $d=m-1$. If $r<d$, the corrected bound is simply the total number $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ of $r$-sets. Assume henceforth $d\le r$. For an integer $z$, consider the residue detectorFor nonnegative upper arguments, the Lucas theorem and the fact that every base-$p$ digit of $d$ equals $p-1$ show that $f(z)$ is one when $z\equiv r(\mathrm{mod}m)$ and zero otherwise. The assertion also holds for negative upper arguments, using integer-valued generalized binomial coefficients. Indeed the coefficient of $u^d$ in $(1+u{)}^q$ is periodic in the integer exponent $q$ modulo $m$: in characteristic $p$, $(1+u{)}^m=1+u^m$, so multiplying even a formal power series by $(1+u{)}^m$ does not change coefficients of degrees below $m$. Reduce any exponent modulo $m$ to obtain the stated detector.

For each $A\in \mathcal{F}$, apply that detector to $|A\cap B|$. Its evaluations on $B\in \mathcal{F}$ form the identity matrix, since the diagonal intersection is $r$ and every off-diagonal intersection has a different residue. The detector is represented on Boolean vectors by the multilinear polynomialTo check this expression, evaluate at the characteristic vector of $B$: summing by $j=|S|$ gives ${\sum }_j\left(\genfrac{}{}{0ex}{}{|A\cap B|}{j}\right)\left(\genfrac{}{}{0ex}{}{d-r}{d-j}\right)=\left(\genfrac{}{}{0ex}{}{|A\cap B|+d-r}{d}\right)$ by the coefficient identity for $(1+u{)}^{|A\cap B|}(1+u{)}^{d-r}$.

Here is the necessary low-degree evaluation rank on a uniform layer, with care about characteristic $p$. Let $M$ be the integer incidence matrix whose rows are subsets $S$ of size at most $d$, whose columns are all $r$-sets $B$, and whose entries are $1_{S\subseteq B}$. Over the rational numbers, for $|S|=j\le d$ its row satisfiesThus its rational matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$. Every larger square minor has integer determinant zero; reducing those determinants modulo $p$ gives ${\mathrm{rank}}_{{\mathbb{F}}_p}M\le \left(\genfrac{}{}{0ex}{}{n}{d}\right)$ too. This argument does not divide by a potentially zero element of the finite field. The identity evaluation matrix $(f_A(1_B){)}_{A,B\in \mathcal{F}}$ factors through these incidence rows, so its rank $|\mathcal{F}|$ is at most $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$. This proves the qualified bound.

Choose the two-applications alternative. First, the polynomial method in combinatorics yields a constructive lower bound for a diagonal Ramsey number. Let $p\ge 3$ be prime, set $N=p^3,r=p^2-1$, and use all $r$-subsets of $[N]$ as vertices of a complete graph. Color a pair red when its intersection size is $-1$ modulo $p$, and blue otherwise. A blue clique has size at most $D=\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$ by the proved bound with modulus $p$. In a red clique, all distinct intersections belong toFor each vertex $A$ of that clique, the polynomial $P_A(x)={\prod }_{\ell \in L}({\sum }_{i\in A}{x}_i-\ell )$ vanishes at all the other vertices' characteristic vectors and is nonzero at its own. Replace repeated powers $x_i^j$ by $x_i$ on Boolean vectors. Its degree is at most $p-1$, so the rational version of the same incidence-rank argument bounds a red clique by $D$ as well. Therefore this two-coloring has neither color containing a clique of size $D+1$, andThe usual estimates $(N/k{)}^k\le (\genfrac{}{}{0ex}{}{N}{k})\le (eN/k{)}^k$ give $\log D=\Theta (p\log p)$ and $\log \left(\genfrac{}{}{0ex}{}{p^3}{p^2-1}\right)=\Theta (p^2\log p)$. Thus along this explicit sequence the diagonal Ramsey number exceeds $\exp (c(\log s{)}^2/\log \log s)$ for some absolute $c>0$. This is substantially larger than any fixed power of $s$.

Second, obtain an exponential lower bound for the chromatic number of Euclidean space. Let $N=4p-1,r=2p-1$, and join two $r$-subsets exactly when their intersection has size $p-1$. An independent set in this graph avoids that intersection. Among the possible distinct intersection sizes $0,\dots ,2p-2$, the only one congruent to $r$ modulo $p$ is $p-1$. Hence every independent set has size at most $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$. Embed each vertex as $v_A=1_A/\sqrt{2p}$ in Euclidean space. Thenso the graph's edges have exactly Euclidean distance one. Each color class must be an independent set, givingThe Stirling formula makes the logarithm of this ratio $N(\log 2-h(1/4))+o(N)$, where $h(x)=-x\log x-(1-x)\log (1-x)$. Since $\log 2-h(1/4)>0$, this is an exponential dimensional lower bound for the chromatic number of Euclidean space. Both applications lie in the valid parameter range of the proved modular bound.

For rows $x_i,x_j$, three useful choices are Euclidean distance, standardized Euclidean distance, and Mahalanobis distance:The Euclidean choice is simple, rotation invariant and appropriate when the original coordinate scales carry comparable meaning. It is sensitive to scale changes, may be dominated by a high-variance variable and gives correlated or duplicate variables repeated influence. Squared Euclidean dissimilarity is sometimes used algorithmically, but removing the square root generally loses the triangle inequality.

The standardized Euclidean choice removes marginal units using fixed positive sample scales $s_r$. It gives equal marginal weight to variables, but ignores correlations and can magnify noise when an estimated variance is small. Constant variables require omission or an explicitly chosen positive external scale.

The Mahalanobis choice incorporates the full positive-definite sample covariance $S$, so it is Euclidean distance after whitening. It accounts for both scale and redundancy and is invariant under an invertible change of coordinates when $S$ is transformed consistently. However estimating $S$ requires enough observations and can be sensitive to extreme values; inversion is unstable near singularity and unavailable when $S$ is singular. With fixed positive scales or positive-definite $S$, all three square-root expressions are genuine metrics on the measurement space. Their different geometries encode different notions of which individuals should be considered similar.

In the parametric description, $a$ is a point of the straight line and the nonzero vector $b$ gives its direction. The real parameter runs through every point of that line. For the cross product description, take another cross product with $c$ and use the vector triple product identity:Hence every solution has the representationHere $a\cdot b=0$ and $|b|=|c|$, as required. Conversely,Thus the perpendicularity assumption is sufficient, and the solutions form a straight line parallel to $c$. When $d\ne 0$, the vector $d$ is perpendicular both to $c$ and to every position vector on the line; it is the normal to the plane through the origin containing that line. The point $a=c\times d/|c{|}^2$ is the perpendicular foot from the origin. Its distance from the origin is $|d|/|c|$, since $c\cdot d=0$.

For a general parametric straight line, minimize the squared Euclidean distanceThis strictly convex quadratic function has its unique minimum at $\lambda =b\cdot (y-a)/|b{|}^2$, giving the orthogonal projectionFor the cross product description, $a\cdot c=0$, so this becomes

For the two planes, put $s=m\cdot n$ and $c=m\times n$. Nonparallel unit normals give $|s|<1$ and $|c{|}^2=1-s^2$. Seek the perpendicular foot in their span, $a=um+vn$. Its two dot products impose $u+sv=\mu$ and $su+v=\nu$. Solving gives both requested descriptions of the intersection:andIndeed the vector triple product identity gives $x\times (m\times n)=m(x\cdot n)-n(x\cdot m)$. Conversely, since $m,n$ are linearly independent, equality to $\nu m-\mu n$ forces both plane equations. Thus neither description introduces extra points.

For the unit-modulus prime values in this question, the Granville-Soundararajan distance isThe second identity uses $|f(p)|=|g(p)|=1$. Thus it is the Euclidean distance between the finite weighted vectors $(f(p)/\sqrt{2p}{)}_{p\le X}$ and $(g(p)/\sqrt{2p}{)}_{p\le X}$. Nonnegativity, symmetry and the triangle inequality follow from that norm representation, and it vanishes exactly when the two prime-value vectors agree. This proves the prime-restriction metric for pretentious distance.

On whole arithmetic functions at fixed $X$ it is a pseudometric. For example $f=1$ and $g={\mu }^2$ have identical values at every prime and zero distance for every $X$, but different values at four. Thus the literal identity-of-indiscernibles assertion needs the prime-restriction quotient.

Since $\mu (p)=-1$,For completeness, partial summation and the prime-counting form of the Prime number theorem giveTo verify the constant and the error, replace $\pi$ by $\mathrm{Li}+E$ in the first expression. Differentiating $\mathrm{Li}(u)/u$ shows its two contributions combine to $\log \log X$ plus a constant. The error integral converges absolutely because $|E(u)|/u^2\ll e^{-c\sqrt{\log u}}/u$, and $E(X)/X\to 0$. This proves the Mertens second theorem in the form needed here. In particular the pretentious distance between one and the Möbius function satisfies