Codex @codex  0

A layered neural network with affine maps and activation functions, usually with dense connections between successive layers. A dense layer with $n$ inputs and $m$ outputs has $m(n+1)$ parameters including biases.

Compose affine maps with nonlinear hidden activation functions, for example $h(x)=W_2\mathrm{ReLU}(W_{1}x+b_1)+b_2$. Several hidden units can respond to different linear combinations of input features; later units combine their responses to represent curved or piecewise-linear decision boundaries and interactions. A product interaction can be understood from $xy=[(x+y{)}^2-(x-y{)}^2]/4$: units approximating nonlinear functions of $x+y$ and $x-y$ can represent effects that no single additive linear fit captures.

Nonlinearity in hidden layers is essential: with only identity activations, repeated affine maps collapse to one affine map regardless of depth. Width and depth determine available representations; regularization, validation and suitable optimization are needed to learn useful rather than overfitted interactions. A nonlinear output activation alone applied to one linear score does not give an unrestricted model of feature interactions.

The main distinctions are connectivity, parameter sharing and internal state. A convolutional neural network can itself be feedforward, and convolution can also be used inside a recurrent neural network; these categories are not mutually exclusive. Their different constraints favour different problems without uniquely determining the learning rule.

A feedforward neural network passes activity through a directed acyclic sequence of layers,An input produces an output without a persistent state feeding back into the computation. A dense multilayer perceptron can learn classification, regression or a cue-to-associate mapping when the supplied input contains the needed information. Nonlinear activation functions matter: composing only affine layers gives another affine map, so adding such layers would not create the same representational benefit. A fixed network can be expressive without being easy to train or sample-efficient.

Feedforward processing offers a useful model of an early sensory sweep and of learned mappings between populations. It does not imply that an anatomical sensory hierarchy lacks feedback, nor that a response can depend only on the current external stimulus: the inputs might include a remembered context supplied by another circuit. The model boundary must therefore be stated before interpreting an apparent feedforward computation biologically.

A convolutional neural network introduces spatial locality and weight sharing. For a stride-one layer on an appropriate grid,The same filter $K$ is applied at many positions. This reduces parameters and encodes a prior that a useful local feature can recur elsewhere. As an exact count, an $8\times 8$ single-channel input with four $3\times 3$ filters and valid stride-one convolution produces a $6\times 6\times 4$ output using $4(9+1)=40$ parameters. A fully connected layer from the same input to the same 144 output values uses $144(64+1)=9360$ parameters. The difference is a structural restriction, not evidence that the smaller network is always more accurate.

Away from boundary effects, translating an input translates the convolutional response. This is translation equivariance, not complete invariance. Pooling, strides and the final readout alter the transformation properties, and retaining location can be important for action. Hierarchical local features and expanding receptive fields resemble aspects of the ventral visual stream; exact copying of one numerical filter across all positions is an idealization of biological connectivity. Training can be supervised, self-supervised or reward-driven, so the architecture alone does not supply a developmental theory.

A recurrent neural network updates a state as new input arrives,The same current observation can then produce different outputs depending on history. This is useful for sequence prediction, working memory, control under partial observation and sequential inference. For an original scalar example, let $h_t=h_{t-1}/2+x_t$ with $h_0=0$. Sequences $(1,0)$ and $(0,0)$ have the same final input but final states $1/2$ and $0$. A feedforward map of only that final input cannot distinguish them. A feedforward map supplied with the complete two-step history could do so; recurrence supplies an economical state-update mechanism rather than a magical representational capability.

The classic context-copying recurrent simulations learned tasks including temporal XOR and prediction in artificial word sequences. Hidden representations reflected both past state and current task demands. These computational experiments demonstrate how useful categories and temporal information can emerge, but do not show that a biological circuit uses the same weights, training data or learning procedure.^[ref]

Recurrent learning is also harder to explain biologically. Backpropagation through time differentiates through repeated state updates and can train all recurrent parameters, but gradients can vanish or grow as they traverse many steps. Gating can help preserve useful information and regulate updates; it does not remove every credit-assignment problem. Activity and stability depend on the operating regime. Even a linear recurrence can fade when its gain is below one or grow without bound when its gain exceeds one, whereas nonlinear circuits can have more varied attractor dynamics.

Real neural circuits contain feedforward, lateral and feedback connections, delayed spikes, separate inhibitory and excitatory cells, and locally regulated plasticity. A feedforward model can approximate a computation over a chosen time interval; a recurrent model can account for refinement and state dependence over longer intervals. Neither is a complete cell-level description. Biological training signals must also be distinguished from an engineering method that produces useful responses.

Feedforward networks favour direct mappings, convolutional constraints favour reusable spatial features, and recurrence favours state-dependent computation over time. Their scientific value is assessed by predictions about representations, timing, behaviour and learning, with the architecture and its training assumptions tested separately.

In a two-person Nash bargaining problem, an agreement specifies a jointly feasible pair of payoffs $(u,v)$, measured in each player's own utility function. For a finite game, binding agreements can randomize jointly among action pairs, so the feasible payoff region $F$ is the convex hull of the pure-action payoff. This permits correlated joint actions; it is generally larger than the payoff region generated by independent mixed strategies. A disagreement point $d=(d_1,d_2)$ specifies what each player receives if negotiations fail. Assume a compact convex set of feasible agreements and at least one agreement strictly improving both disagreement payoffs.

A vector $(u^{\prime },v^{\prime })$ jointly dominates $(u,v)$ if $u^{\prime }\ge u$, $v^{\prime }\ge v$, and at least one inequality is strict. This is joint dominance of payoff vectors; strict improvement for both is unnecessary. A Pareto optimal agreement is one that has no feasible joint dominator. A jointly dominated agreement wastes a possible gain, but Pareto efficiency alone does not settle how gains should be divided. The negotiation set in two-person bargaining isIts individual-rationality constraints keep either player from accepting less than disagreement; its Pareto efficiency constraint rules out wasted opportunities. This negotiation set is distinct from objection-and-counterobjection bargaining sets for coalitional games.

The Nash arbitration procedure selects the Nash bargaining solution by maximizing gains relative to disagreement:The objective function is the Nash product. Essentiality makes its maximum positive; compactness gives attainment. On positive gains, its logarithm is $\log (u-d_1)+\log (v-d_2)$, whose Hessian is diagonal and negative definite. Thus strict concavity on the feasible convex set makes the maximizing payoff vector unique. Positive gain in either coordinate increases the product, so the solution is Pareto optimal.

The procedure respects feasibility, bargaining individual rationality, Pareto efficiency, bargaining symmetry, positive affine invariance in bargaining, and bargaining independence of irrelevant alternatives. In particular, replacing each player's utility by a separate positive affine rescaling multiplies the product by a positive constant; it does not compare one player's raw utility scale to the other's. Deleting other feasible agreements cannot change a unique maximizer that remains feasible. Symmetry under interchange of the players gives equal selected coordinates when the bargaining problem itself is symmetric.

These properties also explain why the product rule is distinguished. Normalize a positive-gain maximizer to $(1,1)$ and disagreement to $(0,0)$ by positive affine maps. The first-order inequality along a segment from $(1,1)$ to any feasible $(a,b)$ gives $a+b\le 2$. A sufficiently large symmetric triangle, bounded below in each coordinate and above by $a+b=2$, contains the normalized feasible region. Symmetry and Pareto efficiency select $(1,1)$ in that triangle. Independence of irrelevant alternatives then selects the same point in the original normalized region, and affine invariance transforms it back. This is the supporting triangle for Nash bargaining argument; the assumptions of convexity and a strict joint improvement are important. Without strict improvement, a zero product need not select a unique agreement.

For a finite game, a natural disagreement convention is each player's security level payoff:where $A,B$ are the two payoff matrices and $p,q$ are mixed strategies. Each player can independently guarantee at least its own security level. The maximin bargaining solution applies the Nash product rule using this $d$. In this convention, “maximin” determines the disagreement payoffs; it does not replace the arbitration objective function by $\min (u,v)$, which would depend improperly on interpersonal utility scales. The resulting agreement can strictly benefit both players relative to their guarantees, yet need not benefit both relative to a particular noncooperative Nash equilibrium.

For $1<s\le \sqrt{2}$, use centered tent-map period-doubling renormalization. LetThe image $T_s(J_s)=[1+s-s^2,1]$ lies to the right of $J_s$, with disjoint interiors, because $1+s-s^2\ge s-1$. It lies in the positive branch. Consequently,and its range $[-c,(s^2-1)c]$ is contained in $J_s$. The orientation-reversing affine map $h_s$ gives the exact topological conjugacyThus renormalization squares the slope and halves the return period. Since $s>1$, there is a least $n\ge 0$ for which $s^{2^n}>\sqrt{2}$. Minimality implies $s^{2^n}\le 2$, and all previous slopes are in the renormalizable range. Successive affine maps therefore conjugate the restriction of $T_s^{2^n}$ on a nested central interval to $T_{s^{2^n}}$.

By the preceding part, an iterate $T_{s^{2^n}}^m$ has a horseshoe for an interval map. Pull its two branch intervals and its range interval back through the composed conjugacy. They give a horseshoe for $T_s^{2^{n}m}$. ThereforeAt the endpoint $s=\sqrt{2}$, one renormalization gives the full slope-two tent map, so the argument includes that endpoint without assuming the strict inequality from part (a).

An invertible $4\times 4$ matrix $M$, modulo scalar multiples, acts linearly on homogeneous coordinates. In an affine chart its projective transformation has the formwhere the denominator must be nonzero for a finite image. The important nested groups are Euclidean motions, Euclidean similarities, invertible affine maps, and general projective transformations. Their defining preserved structures become progressively weaker.

A Euclidean motion has $x^{\prime }=Rx+b$ with $R^{T}R=I$. It preserves all distances and angles, hence lengths, areas and volumes. Proper motions have $\det R=1$ and preserve orientation as well; allowing reflections preserves unsigned measurements but can reverse signed ones. A Euclidean similarity has $x^{\prime }=sRx+b$ with $s>0$. It preserves angles and all ratios of lengths; lengths, areas and volumes scale by $s,s^2,s^3$. Thus rigid shape is preserved up to one overall scale.

An invertible affine map has $c=0$ and preserves the plane at infinity. It preserves incidence, parallelism, collinear ratios, affine combinations, and ratios of volumes. Absolute volume scales by $|\det A|$; the volume-preserving affine subgroup has $|\det A|=1$. Lengths and angles are not affine invariants. A general projective transformation preserves incidence, collinearity, concurrence, tangency, and the cross-ratio of four collinear points, but can move the plane at infinity. The cross-ratio, rather than a three-point affine ratio, survives arbitrary projective changes. For a homogeneous quadric hypersurface $X^{T}QX=0$, its transformed matrix is $M^{-T}Q{M}^{-1}$, so its rank and projective degeneracy are preserved.

For surface classes, rather than a fixed numerical radius or curvature, the consequences are:

For example, the affine stretch $(x,y,z)\mapsto (2x,y,z)$ changes a unit sphere to $x^{\prime 2}/4+y^{\prime 2}+z^{\prime 2}=1$ and a unit circular cylinder to $x^{\prime 2}/4+y^{\prime 2}=1$. A general conical surface written $P+tD(s)$ transforms affinely into $T(P)+tAD(s)$, so every generator still passes through a finite apex. A nonsingular elliptic paraboloid or hyperbolic paraboloid has quadratic part of rank two and a nonzero linear component in its null direction. An invertible affine map preserves that rank, inertia and nonzero null-direction coupling, so translation and linear coordinate changes again put it in elliptic or hyperbolic paraboloid form.

Under a genuinely projective change, these Euclidean classifications depend on which plane is designated as infinity. For the map $(x,y,z)\mapsto (x,y,z)/(1+\alpha z)$, a circular cylinder $x^2+y^2=1$ becomesa cone whose apex is finite. The inverse map sends that apex to infinity and produces the cylinder. Thus a cone is projectively invariant as a family of concurrent generators if an ideal apex is allowed, but finite-apex cones and cylinders are not separately invariant. Likewise a projective image of a sphere or either type of paraboloid remains a nonsingular quadric hypersurface, but need not retain its affine or metric type. The distinction between general cones and circular cones matters: circularity is a metric property and is not preserved by arbitrary affine changes.

A solid body transform is a rigid transformation: it preserves distances within the object. In three-dimensional coordinates it has the form $T(x)=Rx+b$, with translation $b\in {\mathbb{R}}^3$ and an orthogonal matrix $R$. For a proper physical rotation, the coefficient constraints areEquivalently the columns of $R$ are an orthonormal basis with positive orientation. A reflection also preserves distance but has $\det R=-1$ and is excluded when “solid-body motion” means a rotation and translation. There are three rotational and three translational degrees of freedom, not twelve independent matrix coefficients.

Computationally use the homogeneous coordinates representationThe last row is $(0,0,0,1)$; matrix multiplication composes transforms. Alternatively store a unit quaternion together with $b$, maintaining its unit norm. A transpose gives the rotational inverse: $T^{-1}(y)=R^T(y-b)$.

Write the cubic Bézier curve as $P(t)={\sum }_{i=0}^3{B}_i^3(t)p_i$, where $B_i^3(t)=\left(\genfrac{}{}{0ex}{}{3}{i}\right)(1-t{)}^{3-i}{t}^i$. The binomial theorem gives ${\sum }_i{B}_i^3(t)=1$. Transforming the controls producesThis proves pointwise equivariance, including the original parameter values; it is stronger than a statement that the two curves merely have the same shape.

Orthogonality was not used in the calculation. The identical proof applies to every affine map $T(x)=Ax+b$, including scales, shears and even singular affine maps. It applies to every representation $P(u)={\sum }_i{\varphi }_i(u)p_i$ with scalar, control-independent partition of unity basis functions: Bézier curves of every degree, B-splines, surfaces built on a tensor-product surface basis, triangular Bézier patches, and more general linear control-point representations. Positivity is not needed for affine equivariance of a geometric basis. For linear stationary subdivision matrices with row sums one, each refinement step commutes with the affine transformation; taking a convergent limit proves the corresponding assertion for subdivision curves and subdivision surfaces. Rules with geometry-dependent nonlinear weights require separate equivariance tests and are not covered automatically.

The affine class is the largest class that preserves every such Euclidean-control construction with unchanged basis weights, under the usual continuity assumption. In fact the degree-one case would forcefor all $x,y$ and $0\le t\le 1$. This segment identity, followed by continuity, forces $T$ to be affine. Nonlinear transforms such as perspective division generally fail it.

There is a further extension when the representation itself is enlarged: apply a projective transformation linearly to homogeneous controls $(w_i{p}_i,w_i)$, then dehomogenize the weighted sum. The transformed objects are rational Bézier curves or non-uniform rational B-splines, with transformed weights as well as transformed Euclidean controls. This works wherever the new denominator is nonzero. It does not assert projective invariance of ordinary polynomial Bézier curves with their old weights.

Let the univariate linear precision sites be ${\xi }_j,{\eta }_k$, meaningThen their Cartesian-product grid is a linear precision set for the tensor-product surface basis:Indeed, the first coordinate is $({\sum }_j{\xi }_j{\varphi }_j)({\sum }_k{\psi }_k)=u$, and the second is $({\sum }_j{\varphi }_j)({\sum }_k{\eta }_k{\psi }_k)=v$. More generally, take controls $P_{jk}=A+{\xi }_{j}B+{\eta }_{k}C$. The resulting parametric surface is exactlyThis proves linear precision of a geometric basis and affine map reproduction, including arbitrary changes of the embedding plane. In fact the products also reproduce the bilinear coordinate $uv$, since ${\sum }_{j,k}{\xi }_j{\eta }_k{\varphi }_j{\psi }_k=uv$; affine precision is the requested consequence.

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 printed diagram is a propagation subdivision mask: it shows the influence of one old vertex on several new vertices. Its entries do not all belong to a single averaging stencil. The old vertex is retained, and a new vertex is inserted at each incident face centre. Reading the contributions arriving at a target givesThus each new vertex-vertex averages its old value and its four edge neighbors, while each new face-vertex is the centroid of its four old corners. Both stencils are convex combinations, reproduce constants and commute with affine maps. The neighboring $1/8$ contributions go to old vertices; the diagonal $2/8$ contributions go to face centres. The propagation coefficients sum to two because one refinement doubles the number of lattice vertices, not because either stencil fails to sum to one.

For calculations, describe this quincunx subdivision usingThe refined square lattice is rotated by $45^{\circ }$ and its spacing is reduced by $\sqrt{2}$. In its integer coordinates, the one-step mask isIndeed, a unit step in these new coordinates is an old face-centre displacement, whereas a diagonal step reaches an old edge neighbor. The even parity class contains the central and four diagonal coefficients and sums to one; the odd class contains the four axial coefficients and also sums to one. This checks the two target stencils independently.

Choose coefficients using the local subdivision matrix, not just by copying a pleasant-looking regular stencil. Because the grids alternate, form the matrix $S_n$ for a complete two-step cycle around the valence-$n$ extraordinary subdivision vertex, retaining a large enough neighborhood that it maps into itself. The three local coefficients enter this matrix through the specified vertex and face rules.

First require constant reproduction and commutation with affine maps: every target stencil must sum to one, and the valence-four rules must reduce to the regular ones already found. A propagation mask need not itself sum to one. For example, with an old-vertex target rule $V^{\prime }=a_{n}V+c_n{\sum }_{j=1}^n{V}_j$, normalization requires $a_n+n{c}_n=1$; a face-centroid target rule separately has corner weights summing to one. If face weights depend on incident valences, impose their sum on each actual face, rather than incorrectly using a propagation-column normalization. Rotational and reflection symmetry around the vertex should preserve an isotropic treatment of its sectors. Nonnegative coefficients are desirable for convex hull bounds and stability, although they are not by themselves a smoothness proof.

For convergence, seek a simple eigenvalue one corresponding to the constant eigenvector, with all remaining eigenvalues of modulus below one. For a well-defined tangent plane, seek two independent, semisimple tangent modes with a common positive subdominant eigenvalue:The angular modes should be the first sine and cosine modes around the ring. On the regular lattice the full two-step tangent scale is $1/2$, which provides a useful consistency check. These requirements suppress persistent unwanted modes and ensure that generic first-order geometry is dominated by a two-dimensional tangent space.

Then check that the characteristic map of a subdivision surface built from those tangent eigenvectors is regular and injective on the punctured neighborhood. A dominant tangent pair together with a regular, nonfolding characteristic map is the crucial $C^1$ target; eigenvalues alone are insufficient. This check rules out folds or vanishing tangent area that a spectrum cannot detect. For reasonable curvature behavior, also try to keep second-order modes at or below ${\lambda }^2$ in modulus, with equality and appropriate mode structure when nonzero finite curvature is desired. Avoid negative or complex modes that produce visible alternating ripples, excessive shrinkage and strongly anisotropic shape response.

These are selection criteria, not a uniquely determined triple of coefficients. The disappearance of extraordinary faces after one step simplifies the subsequent local matrix, but the extraordinary vertex remains and its smoothness still needs these tests. In particular, the regular $C^4$ result cannot simply be assigned to arbitrary valence.

A nondegenerate distribution function $G$ is a max-stable distribution if, for every integer $r\ge 1$, there are $a_r>0$ and $b_r\in \mathbb{R}$ such thatEquivalently, the suitably centered and positively scaled sample maximum of $r$ independent and identically distributed random variables with law $G$ again has law $G$. The extremal types theorem states that every nondegenerate limiting law of normalized sample maxima is a max-stable distribution. Thus this property identifies all possible limiting types, although a particular starting distribution function need not admit any such limiting normalization.

The three standard types are the Gumbel distributionthe Fréchet distribution, with $\alpha >0$,and the negative Weibull distribution, with $\alpha >0$,They are max-stable distributions, as follows respectively by taking $(a_r,b_r)=(1,\log r)$, $(r^{1/\alpha },0)$, and $(r^{-1/\alpha },0)$. The necessary and sufficient classification is: $G$ is max-stable exactly when $G(x)=H((x-b)/a)$ for $a>0$, $b\in \mathbb{R}$, and one of these three types $H$. A positive affine map sends a max-stable distribution to another max-stable distribution.

For the requested threshold equivalence, set $p_n=1-F(u_n)$. By independence,If $n{p}_n\to \tau <\infty$, then $p_n\to 0$ and the expansion $\log (1-p)=-p+O(p^2)$ gives $n\log (1-p_n)\to -\tau$, since $n{p}_n^2=(n{p}_n)p_n\to 0$. Exponentiation proves the claimed limit. Conversely, if $(1-p_n{)}^n\to e^{-\tau }>0$, then $p_n\to 0$: any subsequence with $p_n\ge \delta >0$ would have its powers tending to zero. Taking logarithms now gives $-n\log (1-p_n)\to \tau$. Since $-\log (1-p)/p\to 1$, including the continuous extension at $p=0$, it follows that $n{p}_n\to \tau$. Hence

The exceedance count $S_n$ has the binomial distribution with parameters $n,p_n$. For $\tau >0$ and each fixed nonnegative integer $s$, its probability mass function satisfieswhere $(n{)}_s=n(n-1)\cdots (n-s+1)$ and $(n{)}_0=1$. Indeed $(n{)}_s/n^s\to 1$, $(n{p}_n{)}^s\to {\tau }^s$, and $(1-p_n{)}^{n-s}\to e^{-\tau }$. If $\tau =0$, the bound $\mathbb{P}(S_n\ge 1)\le \mathbb{E}{S}_n=n{p}_n\to 0$ gives the degenerate Poisson distribution at zero. Summing the finitely many terms proves, in both cases,This derives the needed instance of the Poisson limit theorem directly.

Finally fix $x$ with $G(x)>0$ and put $u_n=a_{n}x+b_n$. The assumed limit for the normalized sample maximum and the proved equivalence give $n{p}_n\to -\log G(x)$. The second-largest order statistic is at most $u_n$ exactly when at most one observation is strictly greater than $u_n$. This event identity holds even if observations have ties. Apply the preceding Poisson limit theorem with $k=1$ to obtainThe endpoint $G(x)=1$ corresponds to $\tau =0$ and is already included. This is the case $r=2$ of the exceedance count limit for extreme order statistics.

A quantitative form of Roth theorem on three-term arithmetic progressions is: there is an absolute constant $C_R$ such that, for $N\ge 3$, every $A\subseteq [N]$ with no nonconstant three-term arithmetic progression satisfiesAll logarithms below are natural. We prove the classical Roth bound for three-term progressions with an unoptimized $C_R=100$. The empty set is immediate; write $\delta =|A|/N>0$.

First establish a quantitative density increment. Suppose $N\ge 4\cdot 10^6{\delta }^{-4}$. Put $M=2N+1$, embed $I=[N]$ in $G={\mathbb{Z}}_M$, and extend all interval functions by zero. Let $a=1_A$, $u=\delta 1_I$ and $f=a-u$, the balanced subset indicator. DefineThe relation in the sum is modulo $M$. For interval elements its integer discrepancy has absolute value less than $M$, so it is precisely the integer relation. Thus $\Lambda (a,a,a)=|A|=\delta N$. The full interval count is the number of endpoint pairs of the same parity:Consequently, since $N\ge 4{\delta }^{-2}$,

Orthogonality of the additive characters givesBoth identities follow by expanding the sums and using ${\sum }_r{e}^{2\pi irt/M}=M$ for $t=0$ in $G$, and zero otherwise; the latter follows from a finite geometric series. Since $M$ is odd, $r\mapsto -2r$ permutes the frequencies. Telescope the difference asThe Cauchy-Schwarz inequality and the displayed Parseval identity on a finite group bound each term by $\delta N{\max }_r|\hat{f}(r)|$. Indeed, $\Vert a{\Vert }_2^2=\delta N$ and $\Vert u{\Vert }_2^2={\delta }^{2}N$, so every product of the two remaining L2 norms is at most $\delta N$. HenceThe zero coefficient vanishes because $\sum f=0$, so choose a nonzero frequency $\theta =r/M$ giving this bound.

Let $Q=\lfloor \sqrt{N}\rfloor$. The pigeonhole principle applied to the $Q+1$ fractional parts $0,\theta ,\dots ,Q\theta$ in $Q$ intervals gives an integer $1\le q\le Q$ with $\Vert q\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. Partition each residue class modulo $q$ in $[N]$ into consecutive arithmetic progressions of exactlyelements, leaving fewer than $L$ remainder points per residue. The total remainder $R_0$ has size at most $qL\le {\delta }^{2}N/1000$. The size hypothesis gives $L\ge {\delta }^2\sqrt{N}/2000$. On a full arithmetic progression $P$, the phase $e^{-2\pi i\theta x}$ varies from its value at the first point by at most $2\pi L/Q\le 4\pi {\delta }^2/1000$.

Let $F_P={\sum }_{x\in P}f(x)$. Replacing the phase by its first value on each full arithmetic progression and estimating the remainder using $|f|\le 1$ givesAlso $|{\sum }_P{F}_P|=|{\sum }_{R_0}f|\le {\delta }^{2}N/1000$. Therefore the sum of the positive $F_P$ isSince the total length of these arithmetic progressions is at most $N$, at least one has $F_P/|P|\ge {\delta }^2/64$. Thus the step just proved isAn affine map taking this arithmetic progression to $[|P|]$ preserves the absence of nonconstant three-term arithmetic progressions.

Now iterate. Write $N_j,{\delta }_j$ for successive lengths and subset densities, with $N_0=N$ and ${\delta }_0=\delta$. Since every subset density is at most one,Consequently $T=\lceil 65/\delta \rceil$ successful steps are impossible. On the other hand, subset densities never decrease, so with $B=\log (2000/{\delta }^2)$,Suppose $\delta \log \log N>100$. Since $T\le 66/\delta$,Let $D=\log (4\cdot 10^6{\delta }^{-4})$. We have $2B+D<31+8\log (1/\delta )\le 39/\delta <e^{54/\delta }$. Therefore every length through step $T$ satisfies $\log N_j>D$, and hence $N_j\ge 4\cdot 10^6{\delta }^{-4}\ge 4\cdot 10^6{\delta }_j^{-4}$. The density increment lemma remains applicable for all $T$ steps, contradicting the reciprocal-density bound.

Thus $\delta \log \log N\le 100$, proving the boxed theorem. The proof includes the Fourier analysis on a finite abelian group detection, conversion to an integer arithmetic progression, and the length bookkeeping that produces the double logarithm.

Let $T$ be an isometry, and set $S(x)=T(x)-T(0)$. Then $S(0)=0$, and preservation of distances gives $|S(x)|=|x|$. The polarization identity yieldsFor a standard orthonormal basis $e_1,e_2,e_3$, put $v_i=S(e_i)$. These three vectors are an orthonormal basis. Since $⟨S(x),v_i⟩=x_i$, we have $S(x)={\sum }_i{x}_i{v}_i=Qx$ for an orthogonal matrix $Q$. Thusan affine map.

For a finite isometry group $G$, take $c=|G{|}^{-1}{\sum }_{g\in G}g(0)$. An affine map preserves an affine average, so for any $h\in G$,The orbit barycentre is a common fixed point. This proves the fixed point of a finite Euclidean isometry group result.

Differentiate the first-order chain rule again, including derivatives of the coordinate coefficients. The second derivatives under a two-variable coordinate change areandThe last two terms account for derivatives of the coordinate functions; they vanish for an affine map. Smoothness justifies equality of the two mixed partial derivatives.

A quadrature node is a point at which the integrand is sampled by a quadrature rule. Under the affine map $x=(a+b)/2+(b-a)t/2$ from $[-1,1]$ to $[a,b]$, a reference quadrature node $t_i$ becomes $x_i=(a+b)/2+(b-a)t_i/2$; for ordinary numerical integration, the corresponding quadrature weight is multiplied by $(b-a)/2$.

For twice continuously differentiable coordinate functions $u,v$ and an outer scalar function $f$, apply the multivariable chain rule twice along an original coordinate $s$. The first three terms differentiate the outer function, while the last two differentiate the coordinate coefficients. They cannot be omitted for a nonlinear coordinate map. In matrix notation this is the Hessian matrix formula $H_{f\circ g}=J_g^T{H}_f{J}_g+f_u{H}_u+f_v{H}_v$ for $g=(u,v)$. The extra terms vanish for an affine map.

Two equally spaced families of perpendicular lines partitioning the Euclidean plane into congruent squares. A general affine map can turn this grid into parallelograms, or collapse directions if its linear part of an affine map is not injective.

Take the four-point setthe vertices of a polygon of a rectangle whose side lengths are four and two. Three choices of structure give three different symmetry groups on these same points.

As an unstructured set, $R$ has all $4!=24$ permutations as symmetries, forming the symmetric group $S_4$. If Euclidean distance is part of the data, the allowed maps are only the identity, a half-turn rotation, and the reflections across the two coordinate axes. They form a Klein four-group of group order four. To see that nothing is missing, fix the image of one vertex of a polygon: its three other distances, $2$, $4$, and $\sqrt{20}$, are distinct, so they uniquely determine the images of the remaining vertices.

Preserving affine structure permits more. The affine mapcycles all four points of $R$. It sends a horizontal side of length four to a vertical side of length two, so it is not an isometry. Yet it preserves the rectangle's vertex set and all affine combinations among those points.

Let $A=\mathrm{diag}(2,1)$ and let $r(x,y)=(-y,x)$ be the square's quarter-turn rotation. ThenConjugating every square symmetry by $A$ gives eight affine maps preserving $R$. This group isomorphism makes the affine symmetry group a dihedral group, although some of its maps do not preserve the original Euclidean distances. There are no further affine symmetries: an affine map preserves the common midpoint of the diagonals, so it must preserve opposite pairs. The image of one vertex has four choices and the image of an adjacent vertex has two; those choices determine the map through three noncollinear points.

ThusAn arbitrary permutation need not be an affine map. For example, exchanging the two top vertices while fixing the two bottom vertices sends the common diagonal midpoint to two different points, which no single affine map can do. The phrase "the symmetry of these points" becomes unambiguous only after stating which structure matters.

Vector graphics represent a picture by geometric objects and instructions for drawing them: positions, shapes, fills, boundary strokes and transformations. A circle can be stored as a centre and radius; a rectangle as a corner, width and height; a polygon as an ordered list of vertices. These geometric primitives describe whole objects rather than assigning a colour to every pixel. SVG provides elements for such basic shapes and for paths assembled from line segments and curves.^[ref]

The useful separation is between the stored geometry and the finite output. A circle of radius 2 remains the same geometric description whether rendered across twenty or two thousand output pixels. This is the sense in which vector graphics are resolution independent: increasing the output grid can evaluate the original geometry again. The resulting raster image still has finite spatial resolution, and numerical coordinates have finite precision. Enlarging a previously rendered raster image through interpolation instead works with its existing samples. Neither operation guarantees that arbitrarily thin details remain visible at every size.

An SVG path uses a current point and drawing commands. For example, M 1 4 L 5 4 L 3 1 Z moves to $(1,4)$, draws two line segments, then closes back to the starting point, giving a triangle. Uppercase commands use absolute coordinates; the corresponding lowercase commands use offsets from the current point. Thus M 1 4 l 4 0 l -2 -3 z describes the same triangle. The coordinates belong to the current user Cartesian coordinate system, not necessarily to output pixels.^[ref]

For a curved example, the path M 1 4 Q 3 0 5 4 Z uses one quadratic Bézier curve followed by a closing line segment. With control points $P_0=(1,4)$, $P_1=(3,0)$ and $P_2=(5,4)$, its curved boundary isThe endpoints are $P_0,P_2$, and $B(1/2)=(3,2)$; the interior control point $P_1$ is not a point on the curve. A fill paints the enclosed region, while a stroke paints a band around its boundary with a chosen width. One can use either or both: geometry and paint instructions are distinct.^[ref][ref]

The first illustration uses increasing $y$ downward, following the initial SVG coordinate convention. Its dashed control polygon guides the eye; it is not part of the filled path. Apply the affine mapThis combines horizontal scaling, a shear mapping and a translation. The transformed control points are $(4.5,5)$, $(5.5,1)$ and $(10.5,5)$, giving the path M 4.5 5 Q 5.5 1 10.5 5 Z. Its curved midpoint is $T(3,2)=(6.5,3)$. The affine equivariance of a geometric basis explains why transforming only the control points transforms the entire Bézier curve: its weights sum to one, so the translation is added exactly once. The enclosed area is ${\int }_0^{1}8t(1-t)\cdot 4dt=16/3$ before transformation and $|\det A|\cdot 16/3=8$ afterwards. These checks concern the filled region, excluding the width of any stroke.

An SVG viewBox specifies a rectangle in user coordinates to map into a display region. For example, viewBox="0 0 6 6" in a square viewport of 120 by 120 display units gives a scale of 20 display units per user unit; in a square viewport of 600 by 600 it gives 100. The path's control points need not change. For unequal proportions, preserveAspectRatio controls whether the mapping preserves proportions or stretches the axes separately. These display units need not correspond one for one to physical display pixels.^[ref][ref]

Rasterization converts the geometric drawing into a raster image on a chosen grid. Deciding whether each pixel centre lies inside a filled region is a simple rule, but a moving diagonal boundary can make entire pixels switch abruptly. Antialiasing reduces these sampling artifacts by accounting for a footprint around each sample, rather than treating every pixel as a single inside-or-outside decision. This connects vector graphics to raster sampling and reconstruction and aliasing; a finer grid and a better sampling rule solve different parts of the problem.

For an exact analytical model, fill the region $R=\{(x,y)\in [0,4{]}^2:y\le x+1/4\}$. For a square pixel footprint $S$, letHere ${\alpha }_S$ is geometric coverage, and $L$ is relative luminance for ideal opaque neutral shades, with $L_{\mathrm{fill}}=0$ and $L_{\mathrm{background}}=1$. The intersection and area determine how much of the footprint is covered. This is a specified area-average model, not a claim that every SVG renderer uses exact coverage. The SVG shape-rendering property supplies rendering hints and permits implementation tradeoffs, including disabling antialiasing for some choices.^[ref]

On the $4\times 4$ grid of unit squares, $S=[0,1]\times [0,1]$ has coverage ${\alpha }_S=1-(3/4{)}^2/2=23/32$, whereas the pixel centre $(1/2,1/2)$ lies inside $R$ and gives coverage 1 under the centre rule. The adjacent square $[0,1]\times [1,2]$ has coverage $1/32$ but its centre lies outside. The entire filled area is $16-(15/4{)}^2/2=287/32$. Summing exact coverage times cell area gives this value on both the $4\times 4$ and $16\times 16$ grids; the coarse centre rule instead gives 10. Coverage values are displayed after sRGB encoding of the modeled relative luminance. The thin coloured line is a geometry overlay, not an extra sampled stroke. Enlarging the middle panel by nearest-neighbor interpolation would repeat its sixteen values; re-rendering the geometry produces the 256 independently evaluated footprints in the right panel. Antialiasing reduces abrupt edges but cannot make a finite grid preserve every geometric detail.

The attractive feature of vector graphics is editability at the level of intent: move one control point to bend a boundary, change a circle's radius, or transform a whole diagram while keeping its parts aligned. Logos, technical diagrams and outline fonts benefit because their structure can be expressed with relatively few shapes and curves. A complicated photograph may require enormous geometric detail, so vector graphics do not imply a smaller file than raster graphics. Nor does an SVG container guarantee that every object is vector geometry: its image element can embed or reference a PNG raster image. Transforming that embedded raster image changes its placement and reconstruction, but does not recover missing original detail.^[ref]