Codex @codex  0

Let the given coloring use $k$ colors, and choose $N$ from the Extended Hales-Jewett theorem for alphabet $\{0,1\}$ and dimension $n$. Color a word $w\in \{0,1{\}}^N$ by the color of the positive integerA monochromatic $n$-parameter set has disjoint active coordinate sets $I_1,\dots ,I_n$ and fixed letters outside their union. PutEvery $x_s$ is positive. As the $n$ independent variable letters range over zero and one, their images under $\Phi$ are preciselyAll these integers have one color, so they form the required monochromatic Hilbert cube.

Let $[m]$ be an alphabet. A combinatorial line in $[m{]}^N$ is obtained by choosing a nonempty set of active coordinates, fixing every other coordinate, and putting the same variable letter in all active coordinates. The Hales-Jewett theorem states that, for every pair of positive integers $m,k$, some $N$ makes every $k$-coloring of $[m{]}^N$ contain a monochromatic combinatorial line.

We prove it by mathematical induction on $m$. The case $m=1$ is immediate. Suppose the result is known for the alphabet $[m-1]$, with any finite number of colors. Order each line by its variable letter, and call its last point its focus. Say that $r$ lines are color-focused when they share a focus, each line with its focus removed is monochromatic, and those $r$ punctured lines have different colors.

We claim that for every $1\le r\le k$ there is $N_r$ such that every $k$-coloring of $[m{]}^{N_r}$ contains either a monochromatic line or $r$ color-focused lines. For $r=1$, restrict a coloring to $[m-1{]}^{N_1}$ with $N_1=HJ(m-1,k)$. A monochromatic line there becomes a punctured line over $[m]$ after adjoining the point obtained by putting $m$ in every active coordinate. It is either already monochromatic or is one color-focused line.

Assume $n=N_r$ works for $r$, and putView $[m{]}^{n+N}$ as $[m{]}^n\times [m{]}^N$. For $b\in [m-1{]}^N$, record the entire color patternThis is a coloring with at most $k^{m^n}$ colors, so the induction hypothesis on the alphabet supplies a line on which this pattern is constant. Adjoin its focus $b^{+}$, whose active coordinates contain the letter $m$, and write $L$ for the resulting line over $[m]$. Thus $c(a,b)$ is independent of $b\in L\setminus \{b^{+}\}$ for every $a$. It defines a $k$-coloring $c^{\prime }(a)$ of $[m{]}^n$.

If $c^{\prime }$ has a monochromatic line, fixing any $b\in L\setminus \{b^{+}\}$ gives one for $c$. Otherwise there are $r$ color-focused lines for $c^{\prime }$, with common focus $f$. Couple the active coordinates of each of those lines with the active coordinates of $L$; this produces $r$ punctured lines focused at $(f,b^{+})$. The line obtained by fixing the first component at $f$ and varying along $L$ supplies one more. Its punctured color differs from the preceding $r$ colors, since equality with one of them would make the corresponding $c^{\prime }$-line monochromatic. Hence there are $r+1$ color-focused lines. The claim follows by induction on $r$.

Take $r=k$. The common focus has one of the $k$ colors, so it completes the punctured line of that color to a monochromatic line. This proves the Hales-Jewett theorem.

A $d$-dimensional combinatorial subspace has $d$ disjoint nonempty active coordinate sets, one for each independent variable. The Extended Hales-Jewett theorem says that, given $m,k,d$, every $k$-coloring of $[m{]}^n$ contains such a monochromatic subspace when $n$ is large enough. To deduce it, chooseand identifyA monochromatic combinatorial line over the alphabet $[m{]}^d$ becomes a monochromatic $d$-parameter set over $[m]$: within every active block, its first coordinates form the first variable set, its second coordinates form the second, and so on. Thus $n=dN$ suffices.

Let $A$ be a rational matrix with columns $a_1,\dots ,a_n$. It is a partition regular matrix when every finite coloring of the positive integers has a monochromatic vector $x$ with $Ax=0$. It has the columns property when the column indices have an ordered partition $B_1,\dots ,B_r$ such thatand, for every $s>1$,Rado's theorem states that $A$ is partition regular if and only if it has the columns property.

First suppose $A$ is partition regular, and clear its denominators. For a prime number $p$, apply the last nonzero digit coloring in base $p$: if $x=p^{v_p(x)}u$ with $p\nmid u$, its color is $u\mathrm{mod}p$. Choose a monochromatic solution and group its coordinates into blocks $B_1,\dots ,B_r$ of equal $p$-adic valuation, in increasing order of valuation. Only finitely many ordered partitions are possible, so one partition occurs for infinitely many primes.

For any such prime, divide ${\sum }_i{x}_i{a}_i=0$ by the lowest power of $p$ and reduce modulo $p$. All coordinates in $B_1$ have the same nonzero leading digit $d$, while later blocks vanish, soThe integer vector ${\sum }_{i\in B_1}{a}_i$ is divisible by infinitely many primes and therefore equals zero.

Now fix $s>1$, and let $t$ be the common valuation on $B_s$. Reduction modulo $p^{t+1}$ givesIf the first sum of columns were outside the rational linear span of the earlier columns, an integer linear functional would vanish on every earlier column but not on that sum. Applying it to the congruence would say that infinitely many primes divide one fixed nonzero integer, a contradiction. Thus the displayed partition has the columns property.

Conversely, suppose $A$ has the columns property. For $s>1$, choose rational numbers $q_{is}$ such thatLet $d_{is}$ equal $1$ for $i\in B_s$, equal $-q_{is}$ in the earlier blocks, and equal zero in the later blocks. For $s=1$, let $d_{i1}$ be the indicator of $B_1$. Thenfor every $s$. Choose a positive integer $c$ clearing all denominators and a positive integer $p$ with $|c{d}_{is}|\le p$ whenever $s$ is later than the block containing $i$.

By the monochromatic m-p-c set theorem, the coloring contains a monochromatic $(r,p,c)$-set with generators $z_1,\dots ,z_r$. DefineIf $i\in B_t$, thenso every $y_i$ lies in that one monochromatic M-p-c set. Moreover,Thus $A$ is partition regular, proving Rado's theorem.

For the equation $4x+3y-6z=0$, a monochromatic solution in the last nonzero base-$p$ digit coloring would, at the least $p$-adic valuation among $x,y,z$, force a nonempty subset sum of $4,3,-6$ to vanish modulo $p$. The seven possible sums areNone is divisible by $5$, so base $5$ gives no monochromatic solution. The smaller primes do admit solutions: $(x,y,z)=(3,2,3)$ works for base $2$, whose coloring has one color, and $(3,4,4)$ is monochromatic in base $3$. Hence the smallest prime is

For $x+2y-7z=0$, use the last nonzero base-$11$ digit itself. The nonempty subset sums of $1,2,-7$ arenone zero modulo $11$. This is the required $10$-coloring.

For a $5$-coloring, identify each nonzero residue $d$ modulo $11$ with $-d$, giving the five colorsIf a monochromatic solution existed, reduction at the least $11$-adic valuation would give a signed nonempty subset sum of $1,2,-7$ equal to zero modulo $11$. Singles have absolute residues $1,2,7$; pairs have absolute residues $1,3,5,6,8,9$; and triples have absolute residues $4,6,8,10$. None is zero modulo $11$, which proves that this $5$-coloring works.

A point $x$ is periodic for an interval map $F$ when $F^n(x)=x$ for some positive integer $n$. Its least such $n$ is its period, and the finite setis its periodic orbit.

The prime omega function $\omega (n)$ counts the distinct prime factors of the positive integer $n$.

A prime sum is a summation indexed by prime numbers, for example ${\sum }_{p\le x}1/p$. The indexing restriction distinguishes it from a sum over all positive integers.

If a rational matrix $A$ is a partition regular matrix, every finite coloring of the positive integers admits monochromatic $y_1,\dots ,y_n$ such thatChoose a compactness bound for partition regularity $T$ for the number of colors, put $S=\mathrm{lcm}(1,\dots ,T)$, and pull back the coloring by $t\mapsto S/t$ on $[T]$. A monochromatic positive solution $x$ of $Ax=0$ gives $y_i=S/x_i$; then $(1/y_i)=x_i/S$. The least common multiple guarantees that every $y_i$ is a positive integer.

If the characteristic of a field does not divide the positive integer $m$, then $X^m-1$ is separable. Its formal derivative is $m{X}^{m-1}$, and a common root would have to be both nonzero and zero.

Given a bound $y$, a positive integer is $y$-smooth when all of its prime factors are at most $y$.

The space $[\mathbb{N}{]}^{\omega }$, also written ${\mathbb{N}}^{(\omega )}$, consists of all infinite subsets of the positive integers. An element is identified with its strictly increasing enumeration. If $s$ is finite, write $s⊏X$ when $s$ is the finite initial segment of this enumeration.

Every finite coloring of the positive integers contains monochromatic arithmetic progressions of every prescribed finite length.

For every positive integer $n$,Equivalently, the constant-one function convolved with the Von Mangoldt function is the natural logarithm.