Codex @codex  0

For a finite coloring of $[m{]}^N$, a combinatorial subspace is $(a,b)$-insensitive if replacing $a$ by $b$, or conversely, in any of its variable coordinates leaves the color unchanged. For every number of colors, alphabet size $m\ge 2$, and dimension $d$, sufficiently large $N$ guarantees such a $d$-dimensional combinatorial subspace for any specified distinct letters $a,b$.

A proof uses the pigeonhole principle on chains $a^j{b}^{L-j}$ in consecutive coordinate blocks. Choose block lengths from left to right, making each long enough to pigeonhole the vector of colors for every earlier word and every later variable assignment. Process the blocks from right to left. Two equal color vectors give a nonempty variable interval insensitive to $a,b$. Insensitivity already obtained in later blocks survives all restrictions of earlier coordinates. This lemma proves the Hales-Jewett theorem by induction on alphabet size.

Suppose $P({\xi }^{\prime },z)$ has degree $m$ in $z$ and a nonzero constant leading coefficient $a$. Among the $m+1$ heights $h_{\ell }=3\ell$, at least one satisfiesat each real ${\xi }^{\prime }$. Factor into $m$ linear factors with multiplicity. Each root's imaginary part can be within distance less than one of at most one candidate height. The pigeonhole principle leaves a height whose distance from every root is at least one, proving the product bound. The height can be chosen measurably: the set where a candidate succeeds is the closed intersection of $|P({\xi }^{\prime },q+i{h}_{\ell })|\ge |a|$ over rational $q$, and selecting the first successful candidate gives a Borel set partition. This avoids any need for continuous global root labels.

A Hermitian operator on a $2^n$-dimensional Hilbert space, with $2^n$ distinct eigenvalues all belonging to $\{c/2^n:0\le c<2^n\}$, must occupy this entire grid. This follows from the pigeonhole principle: the set of possible values and the set of distinct eigenvalues have the same cardinality. Its minimum eigenvalue is zero, so the operator is necessarily singular. Distinctness therefore does not imply invertibility; it forces a one-dimensional kernel in this specific complete-grid setting.

In a cyclic group of arbitrary order $q$, a Bohr set with $d$ frequencies, defined by $\Vert rx/q\Vert \le 1/16$, contains an arithmetic progression of distinct residues of length at least $q^{1/(d+1)}/32$. Partition the $d$-dimensional cube into $Q^d$ boxes, with $Q=\lfloor q^{1/(d+1)}\rfloor$. The pigeonhole principle supplies $1\le t\le Q^d$ with $\Vert rt/q\Vert \le 1/Q$ simultaneously. The residues $jt$, $0\le j\le \lfloor Q/16\rfloor$, remain in the Bohr set and do not wrap around the cyclic group. The weaker exponent permits composite moduli without assuming that every nonzero step has large order.

Use $[m]=\{1,\dots ,m\}$. A combinatorial line in $[m{]}^n$ has one nonempty active set of coordinates, all carrying the same variable letter, with every other coordinate fixed. The Hales-Jewett theorem states that for every finite alphabet size $m$ and number of colours $k$, some $n$ makes every $k$-finite colouring of $[m{]}^n$ contain a monochromatic combinatorial line.

Here is a complete proof through the alphabet insensitivity lemma. A $d$-dimensional combinatorial subspace is obtained from $d$ pairwise disjoint nonempty coordinate blocks, one independently variable letter on each block, and fixed letters elsewhere. For two distinct letters $a,b$, a colouring restricted to such a combinatorial subspace is $(a,b)$-insensitive if switching $a$ and $b$ in any of its parameter coordinates leaves the colour unchanged, with all other letters and coordinates arbitrary.

We first prove that any desired dimension $d$ admits such an insensitive combinatorial subspace, using only the pigeonhole principle. Define finite bounds recursively bySplit the ambient coordinates into a prefix of length $L$ and a suffix of length $N$. For $0\le j\le L$, let the prefix $p_j$ consist of $j$ copies of $b$ followed by $L-j$ copies of $a$. Give it the entire colour profileThere are at most $k^{m^N}=L$ such profiles, but $L+1$ prefixes. Hence two prefixes $p_s,p_t$, $s<t$, have the same profile. Replace their differing coordinates $s+1,\dots ,t$ by one variable letter, obtaining a prefix word $v(x)$ with $v(a)=p_s$ and $v(b)=p_t$. Then $c(v(a)u)=c(v(b)u)$ for every suffix $u$.

Colour the suffixes by the vectorwhich has at most $k^m$ colours. By the dimension-$d-1$ induction hypothesis, there is a $(d-1)$-dimensional suffix combinatorial subspace on which this vector colouring is $(a,b)$-insensitive. Combining it with the variable block of $v$ gives dimension $d$. Switching the first parameter between $a,b$ preserves colour by the equal prefix profiles; switching any other parameter preserves every entry of $c^{\prime }$ by induction. This proves the alphabet insensitivity lemma, including $d=1$, where the suffix is empty.

Now induct on $m$ to prove the Hales-Jewett theorem. For $m=1$, any one-variable word gives a one-point monochromatic combinatorial line. Suppose the theorem holds for $m-1$, and let $d$ be a sufficient dimension for $k$ colours on $[m-1{]}^d$. The lemma supplies a $d$-dimensional combinatorial subspace insensitive to $(m-1,m)$. Restrict its parameter colouring to $[m-1{]}^d$. By the alphabet induction hypothesis it contains a monochromatic combinatorial line. Its $m$th point has the same colour as its $(m-1)$st point: switch the active parameter coordinates from $m-1$ to $m$, one at a time. Therefore the full line over $[m]$ is monochromatic. Its actual active coordinate set is the nonempty union of the active parameter blocks. This completes both inductions.

To deduce the Van der Waerden theorem, choose the dimension $n$ for alphabet size $m$ and pull back a colouring of a sufficiently long integer interval alongAll images lie in $[N]$ for $N=m{\sum }_{j=1}^n{m}^{j-1}$. A combinatorial line with active coordinates $D$ maps towhere $a$ is the contribution of the fixed coordinates. Thus every finite colouring of the positive integers contains monochromatic arithmetic progressions of every finite length. The argument also provides the finite-interval version. Length one is immediate.

The Strengthened Van der Waerden theorem requires the common difference itself to have the progression's colour. We prove a useful stronger, scaled version, the Brauer progression theorem: for every $k,t,\ell \ge 1$, a finite bound $B(k,t,\ell )$ guarantees a monochromatic setThe desired strengthening is $t=1$. For $\ell =1$ choose $a=t,d=1$; for one colour any interval covering the displayed configuration suffices. For the induction on $k$, assume $M=B(k-1,t,\ell )$ and $\ell \ge 2$. Put $L=(\ell -1)M+1$, let $W$ be a Van der Waerden theorem bound for $k$ colours and length $L$, and take $B(k,t,\ell )=tMW$. Inside $[W]$, obtain a one-colour progression $a+j\delta$ for $0\le j<L$, of colour $c$.

All numbers $tj\delta$, $1\le j\le M$, lie in the larger interval because $\delta \le W$. If one has colour $c$, then the subsequence $a,a+j\delta ,\dots ,a+(\ell -1)j\delta$, together with $tj\delta$, is the desired configuration with $d=j\delta$. Otherwise the colouring $j\mapsto c(t\delta j)$ of $[M]$ uses at most $k-1$ colours. Apply the induction hypothesis to obtain a one-colour configuration $\{te,b,b+e,\dots ,b+(\ell -1)e\}$ there. Multiplication by $t\delta$ gives common difference $d=t\delta e$ and distinguished point $td=t^2\delta e$, all of the same original colour. This proves the scaled theorem using only the Van der Waerden theorem.

The fixed-active-size strengthening is false. It already fails for $m=k=2$. For any proposed positive $n,d$, if $d>n$ there is no eligible line. Otherwise colour a word byThe two points of a line with exactly $d$ active coordinates have counts $q$ and $q+d$ of the letter $2$. Their quotient floors differ by exactly one, so their colours differ. This fixed-active-size obstruction for combinatorial lines is valid for every proposed $n,d$. The colouring may depend on $d$, since the assertion chooses $n,d$ before demanding the conclusion for every colouring.

The Malgrange–Ehrenpreis theorem states that every nonzero constant-coefficient linear differential operator on Euclidean space has a distributional fundamental solution. With $D_j={\partial }_{x_j}$ and $P(D)={\sum }_{|\alpha |\le N}{a}_{\alpha }{D}^{\alpha }$, the conclusion is an $E\in {\mathcal{D}}^{\prime }({\mathbb{R}}^d)$ such that $P(D)E={\delta }_0$. If $N=0$, simply take $E=a_0^{-1}{\delta }_0$; hence assume $N\ge 1$.

We construct a Hörmander staircase in frequency space. The highest-degree homogeneous part $P_N$ is not identically zero on real vectors, since a polynomial vanishing on all real vectors has all coefficients zero. After an orthogonal transformation of coordinates, we can arrange that $P_N(e_1)\ne 0$. Thus, for each real ${\xi }^{\prime }\in {\mathbb{R}}^{d-1}$, the polynomialhas degree $N$ in $z$ and the same nonzero leading coefficient $b=i^N{P}_N(e_1)$, independent of ${\xi }^{\prime }$. This constant leading coefficient of a polynomial is what makes a uniform staircase possible.

For a fixed ${\xi }^{\prime }$, factor $p(z,{\xi }^{\prime })=b{\prod }_{\nu =1}^N(z-z_{\nu })$, counting repeated roots of a polynomial. Consider the $N+1$ heights $h_j=3j$, $j=0,\dots ,N$. A given root has imaginary part within distance less than one of at most one of these heights. By the pigeonhole principle, some height avoids every root, and thenThis is finite-height polynomial root avoidance. Root labels need not be chosen continuously or even measurably. Instead define the closed setsContinuity in $s$ extends the inequality from rational $q$ to every real $s$. These Borel sets partition ${\mathbb{R}}^{d-1}$. The Hörmander staircase assigns the horizontal contour $s+i{h}_j$ over $A_j$; its height is bounded by $3N$, and the denominator has the uniform lower bound $|b|$. For $d=1$, the transverse space is a single point and only one horizontal contour is needed.

Use the Fourier transform convention $\hat{\phi }(\zeta )=\int e^{-ix\cdot \zeta }\phi (x)dx$, with inverse factor $(2\pi {)}^{-d}$. Define the candidate fundamental solution of a linear differential operator byFor a test function supported in a fixed compact set $K$, Fourier decay in a bounded complex strip gives, for any integer $M$,Indeed, this is the real Fourier transform of $e^{-h_j{x}_1}\phi (x)$ with reversed frequency, and repeated integration by parts with $(1-\Delta {)}^M$ proves the estimate. Taking $2M>d$ and using the denominator bound proves absolute convergence and a continuity estimate on ${\mathcal{D}}_K$. Thus $E$ is a distribution; no unsupported interpretation of a divergent inverse Fourier transform is being used.

For its distributional derivatives, the formal transpose of a differential operator is $P(-D)$. Sinceapplying $P(D)$ cancels the denominator. For each fixed ${\xi }^{\prime }$, the numerator is an entire function of $z$. The Cauchy integral theorem, applied to a rectangle between the lines $\mathrm{Im}z=0$ and $\mathrm{Im}z=h_j$, givesThe two vertical edges tend to zero by the same bounded-strip decay. The resulting contour deformation is performed separately for each transverse frequency, so discontinuities of the staircase height introduce no additional boundary terms. Absolute convergence permits integration over the partition $A_j$. The Fourier inversion theorem then yieldsThis proves the Malgrange–Ehrenpreis theorem. Undoing the orthogonal change of coordinates gives the fundamental solution of a linear differential operator for the original operator; the Dirac delta distribution is unchanged by that change of coordinates.

For a one-dimensional operator $L=P(D)$ of degree $N\ge 1$, with leading coefficient $a_N$, we may choose the single staircase contour below every pole. Take $\gamma >\max \{\mathrm{Re}\lambda :P(\lambda )=0\}$ and integrate on $\mathrm{Im}\zeta =-\gamma$. The corresponding formula is the Bromwich contour version of the construction above, after putting $\lambda =i\zeta$. Its poles all lie above the frequency contour. For $x<0$, close that contour downwards; the exponential function $e^{ix\zeta }$ decays and there are no enclosed poles. For $x>0$, close upwards, where the exponential function again decays, and apply the residue theorem. The bound $1/P(i\zeta )=O(|\zeta {|}^{-N})$ justifies the large arcs, including $N=1$ by the Jordan lemma away from their endpoints. Thus away from $x=0$ the retarded fundamental solution is $H(x)u(x)$, whereThe sum is over distinct roots of a polynomial, with the residue including the whole multiplicity. For simple characteristic roots of a constant-coefficient differential equation, it reduces to $u(x)={\sum }_{\lambda }{e}^{\lambda x}/P^{\prime }(\lambda )$. Repeated roots give exponential polynomial solutions of a constant-coefficient differential equation through differentiation of $e^{zx}$.

To establish the equality also at the origin, rather than leave a possible point-supported term undecided, verify the distributional jump formula for a Heaviside product. The residue expression is an entire function of $x$, andIts initial derivatives areThese identities follow by integrating over a large circle: for $j\le N-2$ the integrand is $O(|z{|}^{-2})$, whereas for $j=N-1$ its coefficient of $z^{-1}$ is $a_N^{-1}$. The distributional jump formula for a Heaviside product therefore gives $L(Hu)={\delta }_0$. Moreover, since $e^{-\gamma x}Hu$ is a tempered distribution, its Fourier transform satisfiesThere are no real zeros of this polynomial, so its reciprocal is the transform. This is exactly the shifted-contour construction, proving equality there as a distribution as well. HenceThe sign of $a_N$ matters: for the operator in the preceding solution, $a_N=-1$ and the last initial derivative is $-1$.

An ordinary line contains exactly two points of the configuration. We give a cubic covering from few ordinary lines by using point-line duality, a defect count and cubic interpolation. Cubics may be reducible: a line with equation $L=0$ is contained in the cubic $L^3=0$, and a conic can be multiplied by a linear factor.

Pass to the real projective plane, which preserves collinearities and ordinary-line counts. If all points are collinear, one cubic already suffices. Otherwise dualize each point $p=[a:b:c]$ to the line $p^{\ast }:aX+bY+cZ=0$. The dual lines form an embedded graph $\Gamma$: its vertices are their intersections and its edges are the consecutive segments on each projective line. A vertex where $k$ dual lines meet has graph degree $2k$ and corresponds to a primal line containing $k$ points.

Let $t_k$ count vertices incident to exactly $k$ dual lines, and let $f_j$ count faces with $j$ sides. In particular $t_2<5n$. If $v,e,f$ are the graph's numbers of vertices, edges and faces, thenThe Euler characteristic of the projective plane is one, so $v-e+f=1$. Substituting the counts gives the Euler defect identity for a projective line arrangementThus both sums measuring departure from a degree-six triangular grid are $O(n)$.

Call an edge a good dual-arrangement edge if both endpoints have degree six and both adjacent faces are triangles; call it bad otherwise. Count all edge incidences at the defective vertices and faces. Since $k\le 4(k-3)$ for $k\ge 4$ and $j\le 4(j-3)$ for $j\ge 4$,This controls actual bad edges, not merely the number of defective vertices.

Strengthen the local condition: an edge is a safe dual-arrangement edge if every edge on every path of length at most two from either endpoint is good. The bounded-radius propagation of edge defects says that only $O(n)$ edges fail this test. Indeed, trace from an unsafe edge to the first bad edge. Every intervening edge is good, so the intermediate vertices have degree six. Reversing such paths offers only a bounded number of choices, at most a fixed constant times the bad-edge count. Every edge belongs to exactly one dual line, so the pigeonhole principle gives a dual line $p^{\ast }$ containing only $O(1)$ unsafe edges.

The algebraic input is cubic propagation along a triangular strip: a consecutive strip of safe edges on $p^{\ast }$ has all of its crossing dual lines represented by primal points on a single cubic. Here is the mechanism, rather than an appeal to the desired covering theorem. The triangles on either side extend two cells outward into three indexed line families. After dualizing back, their points $a_i,b_j,c_k$ satisfy collinearities whenever $i+j+k=0$. Adjacent three-by-three blocks are the eight-point cubic completion for two triples of lines configuration. A nonzero homogeneous cubic can be fitted to nine starting points because its coefficient space has dimension ten; each successive block has eight points already on that cubic and forces its remaining point onto it. Continuing along the strip keeps every crossing point on the same cubic. One concrete seed is $a_{-1},a_0,a_1,a_2,b_{-3},b_{-2},b_{-1},c_1,c_2$. The first overlapping block forces $c_3$, the next forces $b_{-4}$, and the next forces $c_4$; another block then forces $a_{-2}$. Alternating these completion steps extends the $b$ and $c$ families for the full length of the strip.

For clarity, the completion fact has a short algebraic proof. Let $F=L_1{L}_2{L}_3$ and $G=M_1{M}_2{M}_3$, with the two line triples meeting in nine distinct points, and let a cubic $H$ vanish at all but $L_3\cap M_3$. On $L_1$, both $H$ and $G$ have the same three zeros, so $H-\lambda G$ is divisible by $L_1$ for a suitable scalar $\lambda$. Its quadratic quotient vanishes at the three intersections on $L_2$, hence is divisible by $L_2$. The remaining linear quotient vanishes at the two known intersections on $L_3$, hence is a multiple of $L_3$. Thuswhich also vanishes at the ninth point. This is the line-triple case of the Cayley-Bacharach theorem. In the strip construction, degree-six vertices and the two-cell neighbourhood ensure that the local nine points are distinct; the initial nine-point interpolation and repeated completion provide the required cubic.

It remains to account for every point, including defects and degeneracies. If some dual line has at most two distinct intersection vertices, all other dual lines pass through one of them. Dualizing back covers $P$ by at most two primal lines, hence by cubics, and we are done. Otherwise every dual line has at least three vertices, and the local strip construction applies.

On the chosen $p^{\ast }$, cut the cyclic edge sequence at its $b=O(1)$ unsafe edges, adding one arbitrary cut if necessary. There are at most $b+1$ safe runs, each covered by a cubic via the strip argument. Intersection vertices incident to cut or unsafe edges number at most $2b+2$. At each such exceptional vertex $w$, all crossing dual lines represent primal points on the single primal line $w^{\ast }$, which is itself contained in a cubic. Include one further cubic through $p$ if it has not already been covered. Every other primal point is accounted for by where its dual line intersects $p^{\ast }$. ThereforeThe absolute bound on $b$ comes from $t_2<5n$ and does not depend on the number of points. This completes the requested proof sketch.