Codex @codex  0

The Roth theorem on three-term arithmetic progressions says that, for each fixed $\delta >0$, a sufficiently long interval cannot have a subset of density of a finite subset at least $\delta$ with no nonconstant three-term arithmetic progression. Equivalently, the maximum size of a three-term-progression-free subset of $[N]=\{1,\dots ,N\}$ is $o(N)$. Here is a density increment proof, including its analytic ingredients.

Write $e(t)=\exp (2\pi it)$ and embed $I=[N]$ into the cyclic group $G=\mathbb{Z}/(2N+1)\mathbb{Z}$ of order $M$. For normalized Fourier analysis on a finite abelian group take $\hat{h}(r)=M^{-1}{\sum }_{x}h(x)e(-rx/M)$. The orthogonality of complex exponentials follows from a finite geometric series: its average is zero for a nonzero frequency and one for frequency zero. Expanding in these linear phases consequently proves both Fourier inversion on a finite group and the Parseval identity on a finite group. In particular,The second identity follows by summing the frequency expansion over $x,d$: the two constraints leave precisely the frequencies $(r,-2r,r)$. Since $M$ is odd, multiplication by two permutes the frequencies. Also a congruence $x+z=2y$ with $x,y,z\in I$ is an equality in the integers, since $|x+z-2y|<M$.

Let $A\subseteq I$ have subset density $\alpha =|A|/N\ge \delta$, and suppose it contains no nonconstant three-term arithmetic progression. Its balanced indicator function of a finite subset is $f=1_A-\alpha 1_I$, extended by zero outside $I$. Then $\hat{f}(0)=0$. Counting endpoints with the same parity givesIf $N\ge 4{\alpha }^{-2}$, their difference in absolute value is at least ${\alpha }^3{N}^2/(4M^2)$. Telescope the difference of the products into three terms, each containing $f$ and two factors chosen from $1_A,\alpha 1_I$. Put $s={\max }_r|\hat{f}(r)|$. The Cauchy-Schwarz inequality and the Parseval identity on a finite group bound each term by $s\alpha N/M$, since the squared normalized $L^2$ norm of either other factor is at most $\alpha N/M$. Therefore some nonzero frequency $r$ satisfiesThis is the Fourier detection of a progression-free subset of an interval step; it has just been proved rather than assumed.

We now turn this Fourier coefficient on a finite abelian group into a density increment. Set $Q=\lfloor \sqrt{N}\rfloor$. Partition the unit interval into $Q$ equal pieces and place the $Q+1$ fractional parts of $0,r/M,\dots ,Qr/M$ in them. The pigeonhole principle gives $1\le q\le Q$ with $\Vert qr/M\Vert \le 1/Q$. This proves the particular Dirichlet approximation theorem needed here. Put $\kappa ={\alpha }^2/(1000\pi )$ and $L=\lfloor \kappa Q\rfloor$. For sufficiently large $N$ depending only on $\delta$, $L\ge \kappa Q/2$ and $2L\le Q$. Each residue chain modulo $q$ in $I$ has at least $Q$ elements. Split each such chain into arithmetic progressions with between $L$ and $2L-1$ elements, absorbing its final short remainder into the previous block.

The linear phase changes by at most $4\pi L/Q\le {\alpha }^2/250$ within any block. Freezing the linear phase at the first element of each block therefore changes the preceding correlation by at most ${\alpha }^{2}N/250$, because $|f|\le 1$. The triangle inequality givesThe block sums of the balanced indicator function of a finite subset add to zero, so their positive total is half their absolute total. Some block consequently satisfiesHere $c>0$ is absolute, and shrinking it absorbs the floors. An affine parametrization of $P$ identifies $A\cap P$ with a subset of $[|P|]$ and preserves arithmetic progressions.

Repeat this Roth density-increment step. Every step raises the subset density by at least ${\delta }^2/144$, so fewer than $T=\lceil 144/{\delta }^2\rceil +1$ steps are possible. All the lengths satisfy $N_{j+1}\ge c{\delta }^2\sqrt{N_j}$ while above a threshold depending only on $\delta$. Choose the initial $N$ so large that this lower recursion stays above that threshold for $T$ steps; this is possible by working backwards through finitely many squarings. We would then force a subset density greater than one. Thus every fixed positive density eventually forces a nonconstant three-term arithmetic progression. For an infinite subset of the positive integers with positive upper asymptotic density, apply the finite conclusion along initial intervals whose subset density is bounded away from zero; this gives the usual infinite formulation as well.

We will prove a polynomial progression in a high-energy fourfold difference set. The route is to extract a large subset with a small difference set, construct a dense Freiman s-isomorphism model, and use the Bogolyubov lemma and the pigeonhole principle. To respect the proof requirement, every ingredient beyond the elementary rules for Freiman homomorphisms is established below.

Assume $n\ge 1$. Since three entries of an additive quadruple determine the fourth, $E(A)\le n^3$, so a nonvacuous hypothesis has $0<\theta \le 1$. Let $r(t)=|\{(a,b)\in A^2:a+b=t\}|$. Then $E(A)={\sum }_{t}r(t{)}^2$ and ${\sum }_{t}r(t)=n^2$. Define the popular sum set $S=\{t:r(t)\ge \theta n/2\}$. The contribution to additive energy from its complement is at most $\theta n^3/2$. Since $r(t)\le n$, the bipartite graph on two copies of $A$ whose edges have sums in $S$ has at least $\theta n^2/2$ edges. Moreover $|S|\le 2n/\theta$.

Put $\delta =\theta /2$ and $\tau ={\delta }^2/16$. Here is a dependent random choice argument producing the small difference set. Independently choose two right vertices, allowing repetition, and let $X$ be their common left neighbourhood. The Cauchy-Schwarz inequality gives $\mathbb{E}|X|\ge {\delta }^{2}n$. Call an ordered pair of left vertices bad if its common right neighbourhood has fewer than $\tau n$ elements. The expected number $b(X)$ of bad ordered pairs in $X$ is at most ${\tau }^2{n}^2$, because a fixed bad pair survives both random choices with probability at most ${\tau }^2$. ThusChoose a realization attaining at least this expectation. Then $|X|\ge 3{\delta }^{2}n/4$, and $b(X)\le {\delta }^{2}n|X|/64\le |X{|}^2/48$. Remove from $X$ every vertex having more than $|X|/4$ bad partners in $X$. At most $|X|/12$ vertices are removed. The remaining set $B$ has $|B|\ge {\delta }^{2}n/2$, and any $a,b\in B$ have at least $|X|/2$ vertices $z\in X$ for which both $(a,z)$ and $(z,b)$ are good.

For such a $z$, there are at least $\tau n$ right vertices $y$ adjacent to $a,z$, and at least $\tau n$ right vertices $y^{\prime }$ adjacent to $z,b$. These paths givea representation with four members of $S$. For fixed $a,b$, the tuple of four sums determines $y,z,y^{\prime }$ uniquely, so there are at least $|X|{\tau }^2{n}^2/2$ distinct tuples. Select one ordered pair $a,b$ for each member of $B-B$. Tuples belonging to different differences are disjoint. Counting all possible tuples in $S^4$ provesIn particular, with $m=|B|$, we have $m\ge {\theta }^{2}n/8$ and $|B-B|\le Km$ for $K=2^{25}{\theta }^{-12}$. This is the required small-difference set form of the Balog-Szemerédi-Gowers theorem, proved by counting paths rather than cited.

We next control higher iterated sumsets. Choose a nonempty $X\subseteq B$ minimizing $\rho =|X-B|/|X|$, so $\rho \le K$. We prove the Petridis minimal-growth lemma in the form $|X-B+C|\le \rho |X+C|$ for finite $C$. Order $C=\{c_1,\dots ,c_t\}$, and let $X_i$ consist of those $x\in X$ for which $x+c_i$ is new in the union of the translates $X+c_j$. Then ${\sum }_i|X_i|=|X+C|$. Every member of $(X\setminus X_i)-B+c_i$ already occurs in an earlier translate of $X-B$. By minimality, $|(X\setminus X_i)-B|\ge \rho |X\setminus X_i|$, also when the complement is empty. Thus the new contribution from $X-B+c_i$ is at most $\rho |X_i|$. Sum over $i$ to prove the lemma. Iterating with $C=-(j-1)B$ gives $|X-jB|\le K^j|X|$.

For completeness, the Ruzsa triangle inequality in the needed form isFor each $d\in U-W$, fix $d=u_d-w_d$. The map $(d,v)\mapsto (u_d-v,v-w_d)$ is injective: adding the coordinates recovers $d$, and then $v$. Take $U=kB$, $W=\ell B$, $V=X$ and apply the preceding bounds. We obtain the Plünnecke-Ruzsa inequalityIn particular $T=8B-8B$ has at most $K^{16}m$ elements.

We now prove a slightly wasteful version of the Ruzsa modeling lemma, avoiding any assumption about the diameter of $B$. Set $q=8|T|$. Choose a prime $p$ larger than all $|t|$, $t\in T$, and much larger than $q$. Arbitrarily large primes exist by the elementary argument that a prime divisor of one plus the product of all primes up to a given bound exceeds that bound. For a uniformly chosen nonzero multiplier $r$ modulo $p$, each nonzero $t\in T$ has $rt$ uniform among the nonzero residues. Call a multiplier forbidden if some such $rt$ agrees modulo $p$ with $jq$, where $|jq|<p$. There are at most $2p/q+1\le 3p/q$ such residues. For $p\ge 4$, a union bound therefore makes the probability of being forbidden less thanChoose a nonforbidden $r$. Represent $rB$ by integers in $[0,p-1]$ and partition that interval into sixteen consecutive pieces of diameter less than $p/16$. One piece contains the images of a subset $B^{\prime }\subseteq B$ with $|B^{\prime }|\ge m/16$. Let $\varphi (b)$ be the integer representative of $rb$ in that piece, reduced modulo $q$.

A difference of eight sums of these representatives has absolute value less than $p/2$. If its original difference in $B$ is zero, it is a multiple of $p$, hence zero. Conversely, if its reduction modulo $q$ is zero, it equals $jq$ with $|jq|<p$; our choice of $r$ forces its original difference to be zero. This proves that $\varphi$ is a Freiman s-isomorphism of order eight. Injectivity follows by padding a one-term equality to eight terms with a fixed element. Consequently $D=\varphi (B^{\prime })\subseteq G=\mathbb{Z}/q\mathbb{Z}$ has subset densityNo primality of $q$ is needed.

Here is the cyclic Bogolyubov lemma with all its Fourier analysis on a finite abelian group details. Use $\hat{f}(r)={\mathbb{E}}_{x}f(x)e(-rx/q)$, $f=1_D$, and normalized convolution on a finite group. A finite geometric series proves orthogonality, and expanding the finite sums proves the Parseval identity on a finite group, Fourier inversion on a finite group, and $\widehat{f\ast g}=\hat{f}\hat{g}$. For $\tilde{f}(x)=f(-x)$, the nonnegative functionhas support exactly $2D-2D$ and Fourier coefficients on a finite abelian group $|\hat{f}(r){|}^4$. Put $\Gamma =\{r\ne 0:|\hat{f}(r)|\ge {\alpha }^{3/2}/\sqrt{8}\}$. The Parseval identity on a finite group gives $|\Gamma |\le 8{\alpha }^{-2}$. The total fourth moment of the frequencies outside $\Gamma \cup \{0\}$ is at most ${\alpha }^4/8$.

If $\Vert rx/q\Vert \le 1/16$ for every $r\in \Gamma$, then $\mathrm{Re}e(rx/q)\ge \cos (\pi /8)>3/4$. The zero frequency contributes ${\alpha }^4$ with no loss. Separating the large and small frequencies in Fourier inversion on a finite group yieldsThus $2D-2D$ contains the Bohr set expressed in distance coordinates by $\Vert rx/q\Vert \le 1/16$. This is consistent with the existing character-distance convention for a Bohr set: here it is enough that each character lies in the corresponding short arc around one.

We finally prove the needed nonwrapping progression in a cyclic Bohr set, including for composite $q$. Write $d=|\Gamma |$ and $Q=\lfloor q^{1/(d+1)}\rfloor$. Partition the $d$-dimensional unit cube into $Q^d$ boxes. The $Q^d+1$ points with coordinates $jr/q$ modulo one, $0\le j\le Q^d$, give by the pigeonhole principle an integer $1\le t\le Q^d$ with $\Vert rt/q\Vert \le 1/Q$ for all $r\in \Gamma$. ThenThese points are distinct modulo $q$, since their integer representatives lie between zero and $Q^{d+1}/16\le q/16$. Their number is at least $q^{1/(d+1)}/32$. For $d=0$ the same argument simply chooses $t=1$.

The Freiman s-isomorphism induces a bijection $\Phi :2B^{\prime }-2B^{\prime }\to 2D-2D$: define it on a representation by taking the same two positive and two negative images. Equality of representations uses an order-four relation, and injectivity uses the converse relation. If three consecutive members $y_{j-1},y_j,y_{j+1}$ of $P$ satisfy $y_{j-1}+y_{j+1}=2y_j$, their preimages satisfy the same equality, since its expansion is an equality of eight-term sums in $B^{\prime }$. Hence the inverse image of $P$ is an ordinary arithmetic progression in $2B^{\prime }-2B^{\prime }\subseteq 2A-2A$, with distinct terms.

To remove the multiplicative constant from the length bound, let $R=\lceil 8{\alpha }_0^{-2}\rceil$ and $\beta =1/(R+1)$. The length just proved is at least $c_{\theta }{n}^{\beta }$, where $c_{\theta }={\theta }^{2\beta }/32>0$. Choose $N_0\ge 3$ so that $c_{\theta }{n}^{\beta }\ge n^{\beta /2}$ for $n\ge N_0$, and set $\gamma =\min \{\beta /2,\log 3/\log N_0\}$. For $2\le n<N_0$, two distinct members of $A$ give a nonzero $u\in A-A$, and $\{-u,0,u\}\subseteq 2A-2A$ has length three, at least $n^{\gamma }$. For $n=1$, the singleton $\{0\}$ suffices. In every nonempty case,with $\gamma >0$ depending only on $\theta$. If empty sets are permitted, the required length is zero and there is no substantive assertion.

There are more bins than balls, so the pigeonhole principle forces at least one empty bin. In fact $E\ge m-n=(a-1)n$. ConsequentlyFor the expected fraction, substitute $m=an$ into part (b). The elementary exponential limit, obtained by taking logarithms, givesThis is the empty-bin case of the Poisson limit for occupancy fractions, with limiting mean occupancy $1/a$.

If $C=0$, every bin contains at most one ball, so the total number of balls is at most $m$. Since $n=dm>m$, the pigeonhole principle makes that event impossible:As $n\to \infty$ along these values, $m\to \infty$ and the mean occupancy $n/m$ is $d$. Apply part (b):Both powers tend to $e^{-d}$. HenceThe Poisson limit for occupancy fractions interprets the answer as the probability that a Poisson distribution variable with mean $d$ is at least two.

Use the elementary irrational-rotation density fact: if $\alpha$ is irrational, $\{n\alpha \mathrm{mod}1:n\in \mathbb{Z}\}$ is dense in the circle. One proof uses the pigeonhole principle on fractional parts of $0,\alpha ,\dots ,N\alpha$. Two lie within $1/N$; taking their difference and, if needed, its negative yields an integer multiple of $\alpha$ with fractional part $\delta \in (0,1/N)$. The multiples $0,\delta ,\dots ,\lfloor 1/\delta \rfloor \delta$ form a $1/N$-net of the circle and are themselves integer multiples of $\alpha$ modulo one. Taking $N$ arbitrarily large proves density.

For any target coordinates $(u,v)$ modulo one, points of the line with parameter $t=u+n$ have first coordinate exactly $u$ modulo one and second coordinate $\alpha u+n\alpha$ modulo one. The density fact approximates $v$ arbitrarily well. Since products of small coordinate intervals form a neighbourhood basis of the torus,Nevertheless the point $\pi (0,\alpha /2)$ does not lie in $\pi (L)$. Such an equality would require a line parameter $t=n\in \mathbb{Z}$ and $\alpha (n-1/2)\in \mathbb{Z}$, contradicting irrationality. HenceThis is the irrational winding of the torus: dense need not mean surjective.

The Szemerédi theorem says that for every integer $k\ge 2$ and every $\delta >0$, there is $N_0(k,\delta )$ such that, for $N\ge N_0$, every $A\subseteq \{1,\dots ,N\}$ with $|A|\ge \delta N$ contains a nonconstant arithmetic progressionEquivalently, every subset of the positive integers with positive upper asymptotic density contains arithmetic progressions of every finite length. Length one is immediate.

The Furstenberg multiple recurrence theorem states that for every probability measure-preserving system, every measurable $B$ with $\mu (B)>0$, and every integer $k\ge 2$, there is $n\ge 1$ withHere $T^{-jn}B$ means a preimage, so invertibility is unnecessary. The Furstenberg multiple recurrence theorem also does not assume an ergodic transformation.

We prove the implication to the finite Szemerédi theorem by constructing the Furstenberg correspondence principle explicitly. Suppose, to the contrary, that for fixed $k$ and $\delta >0$ there are $N_{\ell }\to \infty$ and $A_{\ell }\subseteq \{1,\dots ,N_{\ell }\}$ with $|A_{\ell }|\ge \delta N_{\ell }$, but with no length-$k$ arithmetic progression of positive common difference. In the binary full shift $\Omega =\{0,1{\}}^{\mathbb{Z}}$, encode $A_{\ell }$ as $x_j^{(\ell )}=1_{A_{\ell }}(j)$, taking all coordinates outside $A_{\ell }$ to be zero. Let $S$ be the left shift, $(S\omega {)}_j={\omega }_{j+1}$, and setThe cylinder set $C$ is a clopen set, and ${\nu }_{\ell }(C)=|A_{\ell }|/N_{\ell }\ge \delta$. The binary full shift is a compact metric space, so compactness of probability measures on a compact metric space gives a subsequence of these empirical measures with weak convergence of probability measures to a Borel probability measure $\nu$.

For every continuous $h$ on the full shift,Passing to the weak limit shows that $\nu$ is an invariant measure for the continuous left shift. Thus $(\Omega ,\mathcal{B},\nu ,S)$ is a probability measure-preserving system. Since the indicator function of $C$ is continuous, $\nu (C)\ge \delta$.

Apply the Furstenberg multiple recurrence theorem to $C$. For some $n\ge 1$, the clopen sethas $\nu (D)>0$. Its continuous indicator function gives ${\nu }_{\ell }(D)\to \nu (D)>0$. For large $\ell$, at least one $S^a{x}^{(\ell )}$ in the defining empirical measure therefore belongs to $D$. The choice of left shift impliesso $a,a+n,\dots ,a+(k-1)n$ lies in $A_{\ell }$. This contradicts the assumed absence of arithmetic progressions and proves the finite Szemerédi theorem. Applying the finite Szemerédi theorem on intervals where an infinite set has density bounded below proves the stated upper asymptotic density formulation.

For multiple recurrence for circle rotations, write $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ and $R_{\alpha }x=x+\alpha$, with normalized Lebesgue measure $m$, which is the Haar measure of the circle group. Fix a measurable $B\subseteq \mathbb{T}$ with $m(B)>0$ and $k\ge 2$. If $\alpha$ is rational, there is $q\ge 1$ with $R_{\alpha }^q$ the identity, and $n=q$ gives an intersection of measure $m(B)$.

For irrational $\alpha$, the pigeonhole principle applied to $0,\alpha ,\dots ,Q\alpha$ in $Q$ equal arcs gives $1\le n\le Q$ with $\Vert n\alpha {\Vert }_{\mathbb{T}}\le 1/Q$. In particular there are arbitrarily small nonzero returns to zero for the irrational rotation of the circle.

We also need translation continuity in L1 on the circle. Given a measurable $B$, approximate its indicator function in the L1 norm by a continuous $g$ on the circle group. Such approximation follows from regularity of Lebesgue measure, or approximation by finite unions of intervals. Translation invariance and uniform continuity givewhere the approximation error is first made arbitrarily small. Equivalently, $m(B△(B-t))\to 0$.

Choose a return time $n\ge 1$ so small modulo one that for each $1\le j<k$,This is possible because multiplication by each fixed $j$ is continuous on the circle group and translation continuity in L1 on the circle applies to the finitely many translates. The union bound now givesThis proves the Furstenberg multiple recurrence theorem for every circle rotation with its normalized Lebesgue measure, including both rational and irrational angles.

We prove the Hales-Jewett theorem by mathematical induction on the alphabet size. A combinatorial line has a nonempty active coordinate set, with one common letter in all those coordinates. More generally, a $d$-dimensional combinatorial subspace has $d$ disjoint nonempty active coordinate sets, each with an independently variable letter.

First prove the alphabet insensitivity lemma, rather than assume it. Fix distinct letters $a,b\in [m]$, $k$ colors, and dimension $d$. Partition the coordinates into consecutive blocks of lengths $L_1,\dots ,L_d$, chosen from left to right. Put $S_0=0$ and chooseConstruct the variable blocks from right to left. When working on block $i$, the later blocks have already become $(d-i)$-parameter words, while all earlier $S_{i-1}$ coordinates remain unrestricted. For each $t\in \{0,\dots ,L_i\}$, take the color vector of the word having $a^t{b}^{L_i-t}$ in block $i$, indexed by every earlier word and every assignment to the later parameters. There are $m^{S_{i-1}+d-i}$ entries and hence at most $L_i$ different vectors. The pigeonhole principle gives $t<s$ with identical vectors. Fix the first $t$ positions of this block to $a$, fix its last $L_i-s$ positions to $b$, and make the intervening $s-t$ positions a new variable block. Substituting $a$ or $b$ there gives exactly the two equal color vectors.

This equality holds for every earlier word and every later parameter assignment. Restricting the earlier coordinates in subsequent steps therefore preserves it. Likewise, the insensitivity already proved in a later block survives every restriction of earlier coordinates. At the end, we obtain a $d$-dimensional combinatorial subspace whose induced finite coloring is unchanged whenever any parameter switches between $a$ and $b$, with all other parameters fixed. Multiple switches preserve the color by successive single switches. This is the alphabet insensitivity lemma in full.

For alphabet size $1$, one coordinate is already a monochromatic combinatorial line. Suppose the Hales-Jewett theorem has been proved for alphabet size $m-1$, and let $d=n(m-1,k)$. Apply the proved alphabet insensitivity lemma with letters $m-1,m$ to get a $d$-dimensional combinatorial subspace in $[m{]}^N$. Restrict its parameter words to $[m-1{]}^d$. The induction hypothesis gives a monochromatic combinatorial line in these parameters. The union of its active parameter blocks is nonempty, so its image is a combinatorial line in the original coordinates. Its additional point with active letter $m$ has the same color as the point with active letter $m-1$, by insensitivity. Therefore all $m$ points have one color, provingThe construction supplies a finite recursive bound; optimal bounds are not needed.

Again use $D_j=-i{\partial }_j$ and distribution dual pairings with complex bilinearity. The Malgrange–Ehrenpreis theorem asserts that every nonzero constant-coefficient differential operator defined by a polynomial has a fundamental solution of a linear differential operator:If $P=a\ne 0$ is constant, take $E={\delta }_0/a$. For positive degree $m$, write $P_m$ for the highest homogeneous part. A nonzero polynomial cannot vanish on all of ${\mathbb{R}}^n$, so choose a real unit vector $e$ with $P_m(e)\ne 0$. A change of coordinates by an orthogonal matrix makes it the last coordinate direction. In these coordinates,Crucially the leading coefficient $a$ is constant and never vanishes as ${\xi }^{\prime }\in {\mathbb{R}}^{n-1}$ varies.

The finite-height polynomial root avoidance construction gives the needed Hörmander staircase. Set $h_{\ell }=3\ell$ for $0\le \ell \le m$. For each fixed ${\xi }^{\prime }$, the fundamental theorem of algebra supplies $m$ roots $z_1,\dots ,z_m$, with multiplicity. A root's imaginary part can be within distance strictly less than one of at most one candidate height, since those heights are separated by three. The pigeonhole principle therefore leaves at least one height with $|h_{\ell }-\mathrm{Im}{z}_j|\ge 1$ for all roots. At that height, for every real $s$,No continuous labelling of the roots is required. To select the heights measurably, defineEach $B_{\ell }$ is closed, since the coefficients are continuous in ${\xi }^{\prime }$. Continuity in $s$ makes the rational test equivalent to the bound for all $s\in \mathbb{R}$. The $A_{\ell }$ are therefore disjoint Borel sets covering ${\mathbb{R}}^{n-1}$. The union of horizontal fibresis a Hörmander staircase, with bounded imaginary height and a uniform nonzero denominator. For $n=1$, the transverse space has one point, and this is simply the choice of one horizontal line.

For example, $P({\xi }_1,z)={\xi }_1^2+z^2$ has roots $z=\pm i{\xi }_1$. One may select $h=0$ for $|{\xi }_1|\ge 1$, and $h=3$ for $|{\xi }_1|<1$. Then the first region has $|P|\ge 1$, while in the second each root is at least two units from the chosen height. The figure shows the height projection of these horizontal fibres, rather than additional connecting contours.

Define a linear functional on test functions byTo establish that this is a distribution, fix a compact set containing the support of $\phi$, inside a radius-$R$ ball. The Fourier decay in a bounded complex strip estimate follows by applying $(1-\Delta {)}^L$ to $e^{-h_{\ell }{x}_n}\phi (x)$:The finite bound on the heights absorbs all exponential factors and powers of $h_{\ell }$ into $C_{R,L}$. Taking $2L>n$ and using $|P|\ge |a|$ proves absolute convergence and the required finite-order continuity on each fixed support set. Hence $E\in {\mathcal{D}}^{\prime }$.

Now the formal transpose identity and the Fourier derivative identity giveThe polynomial denominator cancels in the pairing for $P(D)E$. For each fixed real ${\xi }^{\prime }$, the remaining function of $z$ is entire and rapidly decreasing in its real part throughout $0\le \mathrm{Im}z\le 3m$. The Cauchy integral theorem therefore allows each horizontal fibre to be shifted to the real axis; its truncated vertical end integrals tend to zero. Absolute convergence justifies Fubini's theorem and the finite sum over the measurable partition. ThusThe last equality is Fourier inversion. Transforming back from the orthogonal coordinates preserves ${\delta }_0$ and gives the required fundamental solution of a linear differential operator for the original operator. The staircase is allowed to jump: after cancellation the shift is performed on each one-dimensional fibre, so no assertion that $\Sigma$ is a smooth contour is used. This construction proves a distributional fundamental solution, without claiming a tempered-growth estimate.

For $f\in \mathcal{D}({\mathbb{R}}^n)$, use the smoothing convolution with a test functionIndeed $u_0(x)=⟨E_y,f(x-y)⟩$ is a smooth function, with ${\partial }^{\alpha }{u}_0(x)=⟨E_y,{\partial }^{\alpha }f(x-y)⟩$. On each compact set of $x$ values, all translated test functions have supports in one fixed compact set, so differentiation is justified by the continuity of the distribution. Compact support of $f$ makes the convolution well defined even when $E$ is not tempered. It does not imply compact support of $u_0$.

Finally the affine solution space of a linear equation isIf every homogeneous solution is represented by a smooth function, so is every $u=u_0+v$. Conversely, if every solution for this fixed $f$ is represented by a smooth function, then for any homogeneous solution $v$, the solution $u_0+v$ is smooth, and subtracting the smooth $u_0$ shows that $v$ is smooth. Hence All inhomogeneous solutions are smooth functions exactly when all homogeneous solutions are smooth functions. This is a global statement on ${\mathbb{R}}^n$ for the stated data; no additional local regularity theorem is being assumed.

Hales–Jewett and the arithmetic-progression consequence. For a finite alphabet $[m]$ and a positive integer $r$, the Hales-Jewett theorem gives an integer $N$ such that every $r$-color finite coloring of $[m{]}^N$ contains a monochromatic combinatorial line. A combinatorial line has a nonempty active coordinate set: all those coordinates receive the same freely varying letter, and the remaining coordinates are fixed.

We first prove the alphabet insensitivity lemma. Fix two letters $a,b\in [m]$, with $m\ge 2$, and a desired dimension $d$. There is a combinatorial subspace of dimension $d$ on which changing $a$ to $b$ in any variable coordinate, with all other variable coordinates arbitrary, preserves the color.

For the construction, divide the coordinates into $d$ consecutive blocks. Choose their lengths from left to right byProcess the blocks from right to left. When processing block $i$, the later blocks already form a $(d-i)$-dimensional combinatorial subspace. Color each word in block $i$ by the vector of its original colors for every prefix word of length $P_i$ and every assignment to those later variables. There are $m^{P_i+d-i}$ contexts, and at most $r^{m^{P_i+d-i}}=L_i$ such color vectors.

The $L_i+1$ words $a^j{b}^{L_i-j}$, $0\le j\le L_i$, contain two, indexed by $u<v$, with the same vector by the pigeonhole principle. Fix the first $u$ coordinates to $a$, the coordinates after $v$ to $b$, and make coordinates $u+1,\dots ,v$ the active set of one new variable. Its values $a,b$ now have identical colors for every prefix and later-variable context. The active set is nonempty. Insensitivity already obtained in later blocks survives, because it held for every unrestricted earlier prefix. After all $d$ blocks have been processed, changing $a,b$ in any of the $d$ variables preserves the color. This proves the lemma.

Now induct on $m$. For $m=1$, a one-coordinate combinatorial line is automatically monochromatic. For $m\ge 2$, let $d$ be a length supplied by the theorem for alphabet $[m-1]$ and $r$ colors. Apply the alphabet insensitivity lemma for the letters $m-1,m$ to obtain a $d$-dimensional combinatorial subspace. Restrict its variables to $[m-1]$. Induction gives a monochromatic combinatorial line in those variables. Its values $1,\dots ,m-1$ have the same color, and its value $m$ has the same color as its value $m-1$ by successively switching the active variables. Lifting this line to the original coordinates proves

For the Van der Waerden theorem, fix a progression length $k\ge 2$ and use the alphabet $\{0,\dots ,k-1\}$. Pull back an $r$-color finite coloring of $\{1,\dots ,1+(k-1)N\}$ alongA combinatorial line with active set $S$ maps to the arithmetic progression $a,a+q,\dots ,a+(k-1)q$, where $a\ge 1$ and its common difference is $q=|S|>0$. The Hales-Jewett theorem makes this progression monochromatic. Length one is trivial, so every finite coloring of the positive integers contains monochromatic arithmetic progressions of every finite length.

The active-coordinate obstruction. Color a word red when its first coordinate is $1$, and blue otherwise. Any combinatorial line whose active coordinate set contains $1$ has a red word at variable value $1$ and a blue word at variable value $2$, since $m>1$. ThusHere adequacy is the adequate family of active coordinate sets property; an active coordinate set is always nonempty.

The pumping lemma for regular languages states that for every regular language $L$ there is an integer $N$ such that every $w\in L$ with $|w|\ge N$ can be writtenwith

To prove it, let a deterministic finite automaton with $N$ states recognize $L$. During the reading of the first $N$ symbols of an accepted word $w$, the automaton visits $N+1$ states, including the initial state. By the pigeonhole principle, two of them agree, say $q_i=q_j$ with $0\le i<j\le N$. Let $x$ be the first $i$ symbols, $y$ the next $j-i$ symbols, and $z$ the remaining suffix. Reading $y$ is a nonempty closed path from $q_i$ to itself. Traversing this path any number $r\ge 0$ of times and then reading $z$ therefore reaches the same accept state. This proves all three assertions.

The diagonal Ramsey number $R(s)$ is the least positive integer $N$ such that every red-blue edge colouring of the complete graph $K_N$ contains a monochromatic copy of $K_s$.

For the existence and bound, write $R(r,s)$ for the least $N$ forcing either a red $K_r$ or a blue $K_s$. Given a vertex $v$ of $K_{R(r-1,s)+R(r,s-1)}$, the pigeonhole principle says that at least $R(r-1,s)$ incident edges are red or at least $R(r,s-1)$ are blue. In the first case those red neighbours contain a red $K_{r-1}$, which joins to $v$ to make a red $K_r$, or a blue $K_s$; the second case is symmetric. HenceStarting from $R(1,s)=R(r,1)=1$ and using Pascal's identity gives the binomial upper bound for a Ramsey numberThereforewhich proves both existence and the required estimate.

To determine $R(3)$, color a cycle graph $C_5$ red and its complement graph, also a $C_5$, yellow. This colors $K_5$ without a monochromatic triangle, so $R(3)>5$. At any vertex of a red-yellow $K_6$, at least three of the five incident edges have one color. If an edge among their three other endpoints has that color, it completes a monochromatic triangle with the chosen vertex; if none does, those three endpoints themselves form a triangle of the other color. Thus $R(3)\le 6$, and

The same local argument proves uniqueness on $K_5$. No vertex can have three incident edges of one color: their other endpoints would either contain an edge of that color or form a triangle of the other color. Every vertex therefore has vertex degree at most two in each color, and because the two degrees sum to four, each is exactly two. Each color class is consequently a regular graph of degree two on five vertices, hence a single $C_5$. Up to relabelling, the coloring is exactly the cycle-and-complement coloring above.

Finally, the monochromatic-triangle counting formula gives, for a coloring of $K_6$ with red degrees $d_v$,The bound is attained by coloring all edges of $K_{3,3}$ red and the two complementary copies of $K_3$ yellow: there are no red triangles and exactly two yellow triangles. The least requested number is therefore

Choose a vertex $v$ of $K_6$. At least three of its five incident edges have one colour, say blue, by the pigeonhole principle. Let their other endpoints be $x,y,z$. If one of $xy,yz,zx$ is blue, it completes a blue triangle with $v$; if none is blue, $xyz$ is a yellow triangle. Thus every colouring of $K_6$ has a monochromatic triangle.

The statement fails for $K_5$. Colour the edges of a five-cycle blue and its complementary five-cycle yellow. Neither colour contains a triangle.

A deterministic finite automaton is a tuple $(Q,\Sigma ,\delta ,q_0,F)$ with finite state set $Q$, finite input alphabet $\Sigma$, transition function $\delta :Q\times \Sigma \to Q$, initial state $q_0$, and accepting-state set $F\subseteq Q$. It accepts a word when the extended transition function of a deterministic finite automaton carries $q_0$ to a state in $F$. A regular language is a language accepted by some deterministic finite automaton.

The pumping lemma for regular languages says that if a regular language is accepted by an automaton with $N$ states, every accepted word $w$ of length at least $N$ has a decomposition $w=xyz$ with $|xy|\le N$, $|y|>0$, and $x{y}^{i}z$ in the language for every $i\ge 0$. Indeed, among the $N+1$ states visited before and after the first $N$ symbols, two are equal by the pigeonhole principle. The intervening nonempty word $y$ labels a loop, which may be traversed any number of times without changing the final accepting state.

In base two, the powers of two have representations $10^n$, so their language is the regular expression $10^{\ast }$ and is regular.

Suppose instead that their base-ten representations formed a regular language. Apply the pumping lemma to a sufficiently long decimal power of two $xyz$, and put $d=|y|>0$. Pumping gives decimal integers $a_i$ represented by $x{y}^{i}z$, all powers of two. A direct place-value calculation shows thatfor a constant $C$ independent of $i$. The lengths, and hence the exponents in $a_i=2^{n_i}$, tend to infinity. Dividing by $a_i$ givesFor large $i$, the right side has absolute value less than one while the left side is an integer, so it must vanish. This would make a power of two equal to $10^d=2^d{5}^d$, impossible for $d>0$ by unique prime factorization. Thus the decimal powers of two are not a regular language.

Fix a number $k$ of colors. For a two-point set whose points are distance $d$ apart, take the vertices of a regular simplex with $k+1$ vertices and side length $d$. The pigeonhole principle gives two vertices of one color, and they form the required congruent copy. Thus every two-point set, equivalently every line segment, is a Euclidean Ramsey set.

For an equilateral triangle of side length $d$, take a regular simplex with $2k+1$ vertices and side length $d$. The pigeonhole principle gives three vertices of one color, and every three vertices of a regular simplex form an equilateral triangle. Hence every equilateral triangle is Euclidean Ramsey.

To prove the product theorem for Euclidean Ramsey sets, let $S_X$ be a finite Ramsey witness for $X$ under $k$ colors. There are at most $k^{|S_X|}$ possible color patterns on $S_X$. Choose a finite Ramsey witness $S_Y$ for $Y$ under that many colors. Given a $k$-coloring of $S_X\times S_Y$, color each $y\in S_Y$ by the complete patternThere is a copy $Y^{\prime }\cong Y$ on which this pattern is constant. The common pattern on $S_X$ contains a monochromatic copy $X^{\prime }\cong X$. Every point of $X^{\prime }\times Y^{\prime }$ then has the same original color, and the orthogonal product is congruent to $X\times Y$.