Codex @codex  0

Let $T_n=n(n+1)/2$, the $n$th triangular number. Pairing the terms of the arithmetic progression proves ${\sum }_{r=1}^{n}r=T_n$. We prove the cube identity by mathematical induction. For $n=1$ both sides equal one. If ${\sum }_{r=1}^n{r}^3=T_n^2$, thenAdding $(n+1{)}^3$ establishes the next case. ThusEquivalently, the same displayed difference telescopes from $T_0=0$, providing a direct proof without induction.

We prove the three-term Roth theorem by a density increment, keeping the interval boundary rather than replacing the interval by a cyclic group with a different density. The case $\delta >1$ is vacuous; assume $0<\delta \le 1$.

We first prove the following alternative with absolute constants $c,C>0$: if $A\subseteq [1,N]$ has density $\eta$ and no nonconstant three-term arithmetic progression, and $N\ge C{\eta }^{-4}$, then some integer progression $P\subseteq [1,N]$ hasFor this purpose take $M=6\lceil 4N/6\rceil +1$, so $4N<M\le 5N$ for large $N$ and $2,3$ are invertible modulo $M$. On $G=\mathbb{Z}/M\mathbb{Z}$, put $I=1_{[1,N]}$, $a=1_A$, $g=\eta I$ and $f=a-g$. In particular $\sum f=0$, and $f$ vanishes outside the interval. Use normalized Fourier coefficients on a finite abelian group, $\hat{u}(r)=M^{-1}{\sum }_{x}u(x)e(-rx/M)$. Character orthogonality, obtained by summing a finite geometric series, gives Fourier inversion on a finite group and Parseval identity on a finite group.

For $\Lambda (u,v,w)={\mathbb{E}}_{x,d}u(x)v(x+d)w(x+2d)$ these identities giveThere is no wrapping ambiguity when all three entries lie in $[1,N]$: the integer $x-2y+z$ has absolute value below $M$, so a modular relation is an integer relation. If no nonconstant progression exists, $\Lambda (a,a,a)=|A|/M^2$. Meanwhile the choices $1\le x\le \lfloor N/4\rfloor$ and $1\le d\le \lfloor N/8\rfloor$ give $\Lambda (I,I,I)\ge 1/10000$ for sufficiently large $N$.

Expand the difference by telescoping,If $\rho ={\max }_r|\hat{f}(r)|$, each term on the right has modulus at most $\rho \eta N/M$. Indeed multiplication of frequencies by $2$ permutes them, and Cauchy-Schwarz with Parseval identity bounds the two other Fourier factors by their $L^2$ norms; each squared norm is at most $\eta N/M$. For $N\ge 10000{\eta }^{-2}$, the diagonal count is less than half the main density term. ThereforeIn particular there is a nonzero frequency $r$ withThe frequency is nonzero because $\hat{f}(0)=0$.

Here is the conversion of this coefficient into a density increment. Put $Q=\lfloor \sqrt{N}\rfloor$. Of the $Q+1$ numbers $0,\theta ,\dots ,Q\theta$ modulo one, two lie in the same one of $Q$ equal arcs. Their difference gives $1\le q\le Q$ with $\Vert q\theta \Vert \le 1/Q$, where $\theta =-r/M$. This is the needed Dirichlet approximation theorem, proved by the pigeonhole principle.

Partition each residue class modulo $q$ in $[1,N]$ into consecutive progressions of length $L=\lfloor \gamma Q/(100\pi )\rfloor$, leaving its final short tail. Their total tail size is at most $qL\le \gamma N/(100\pi )$. On each full progression the character differs from its value at the first point by at most $2\pi L/Q\le \gamma /50$. Hence removing tails and replacing the character by its initial value showsThe sum of $f$ over all full progressions is the negative of its sum over the tails, so its absolute value is at most $\gamma N/(100\pi )$. Consequently the sum of the positive block sums is at least $\gamma N/5$. Since these blocks contain at most $N$ points in total, at least one has average $f$ at least $\gamma /5$. It gives a density increment at least ${\eta }^2/100000$. For $N\ge C{\eta }^{-4}$ with a sufficiently large absolute $C$, $L\ge c{\eta }^2\sqrt{N}$. This proves the alternative, with one small common absolute $c$.

Reidentify $P$ with $[1,|P|]$ by its affine parametrization. Absence of a nonconstant progression is preserved, while density increases. At every step the density is at least the original $\delta$, so the increment is at least $c{\delta }^2$ and the new interval length is at least $c{\delta }^2\sqrt{N_{\mathrm{old}}}$. After at most $T=\lceil 1/(c{\delta }^2)\rceil +1$ steps, the density would exceed one. Choose the original $N$ so large that the length stays above $C{\delta }^{-4}$ throughout these finitely many steps. Such a choice exists explicitly by working backwards: a required next length $L_0$ is ensured by previous length at least $(L_0/(c{\delta }^2){)}^2$. The alternative could then be applied at every step, giving a contradiction. ThusThis is the Roth density increment on an integer progression proof.

For the pattern with offsets $0,1,3$, replace the counting functional by ${\mathbb{E}}_{x,d}u(x)v(x+d)w(x+3d)$. Its Fourier expression iscoming from the relation $2x-3y+z=0$. Both multipliers are invertible modulo the chosen $M$, so exactly the same Parseval estimates apply. This relation has no wrap in $[1,N]$, since its magnitude is at most $3N<M$, and the earlier restricted choices of $x,d$ still give a fixed positive density main term. The same increment and iteration find a nonconstant triple $\{a,a+d,a+3d\}$. Negative $d$ is allowed, as requested, and the affine reparametrization used in the iteration preserves this pattern as well.

The proof of Szemerédi theorem for four-term progressions follows a uniformity-versus-density-increment iteration. Fix a positive starting density; the quantitative parameters below depend only on that density.

First apply the counting argument in part (i). A sufficiently long set with no nonconstant four-term arithmetic progression cannot have small balanced Gowers U3 norm. Thus its balanced function has a quantitatively large cube average. The Derivative identity for the Gowers U3 norm expresses this as an average of fourth Fourier moments of the multiplicative derivatives $x\mapsto f(x+h)\overline{f(x)}$. Many shifts therefore have a derivative with a large Fourier coefficient.

The next step is the inverse argument. Choose these frequencies as a function of the shifts. The relations between repeated derivatives force a large part of the resulting frequency graph to have many additive quadruples. A Balog-Szemerédi-Gowers theorem extraction followed by Freiman theorem for integer sets organizes this graph on a bounded-complexity additive model. Integrating the organized derivative frequencies yields correlation of $f$ with a locally quadratic phase on a structured region. On integer intervals this is generally a local quadratic phase on a Bohr-type region, or equivalent two-step structure; it need not be one global quadratic polynomial on the entire interval.

The quantitative density-increment lemma obtained from that inverse argument says that either the interval is bounded in size by a function of its density, or there is a nonempty integer progression of length at least $c(\delta )N^{c(\delta )}$ on which the density increases by at least $c(\delta )>0$. The passage from correlation to this increment partitions the structured region into progressions on which the phase varies very little, controls discarded boundaries, and uses the balanced function's zero mean to find a positive-density gain. Both the gain and the size exponent are bounded away from zero for densities above the fixed starting density.

Reidentify the new progression with an interval and repeat. The property of having no nonconstant four-term progression is preserved under this affine identification. Density can increase only finitely many times before it exceeds one. Starting with $N$ sufficiently large ensures that the successive power-type length losses never reach the exceptional bounded-size case during those finitely many steps. This contradiction proves that every fixed positive density has a threshold beyond which a four-term progression must occur. The counting lemma, inverse structural argument, density increment and final iteration are the main steps; the deep inverse step is only outlined here, as permitted by this part of the question.

We take $\mathbb{N}=\{1,2,\dots \}$ and require the common difference of an arithmetic progression to be positive. An ultrafilter $\mathcal{U}$ is a proper filter on a set deciding each subset: exactly one of $B$ and $\mathbb{N}\setminus B$ belongs to $\mathcal{U}$.

For the fixed length $m$, let ${\mathcal{B}}_m$ be the family of sets containing no m-term arithmetic progression. Any acceptable ultrafilter must contain every complement $\mathbb{N}\setminus B$ with $B\in {\mathcal{B}}_m$. These mandatory sets have the finite intersection property. Otherwise finitely many $B_1,\dots ,B_r\in {\mathcal{B}}_m$ would cover $\mathbb{N}$. Colour an integer by the first $i$ for which it belongs to $B_i$. The Van der Waerden theorem gives a monochromatic m-term arithmetic progression, contained in the corresponding $B_i$, a contradiction.

Generate a proper filter from those complements and extend it by the ultrafilter lemma. If some $B\in \mathcal{U}$ were in ${\mathcal{B}}_m$, its complement would also belong to $\mathcal{U}$, forcing the empty set into the filter. ThusNotice that sets avoiding one fixed length need not be closed under finite unions; the argument uses the finite intersection property, not an unsupported ideal claim.

For the unbounded-length version, let $\mathcal{B}$ consist of sets whose arithmetic progression lengths are bounded. Each $B_i\in \mathcal{B}$ fails to contain a progression of some length $m_i$, and hence of every greater length. If finitely many $B_i$ covered $\mathbb{N}$, colour by the first containing index and apply the Van der Waerden theorem at length $M={\max }_i{m}_i$. Again a contradiction results. The complements of all members of $\mathcal{B}$ therefore have the finite intersection property. Extending their generated filter gives an ultrafilter with arithmetic-progression-rich members:All finite sets lie in $\mathcal{B}$, so this ultrafilter contains every cofinite set and is a nonprincipal ultrafilter. The same is true of the fixed-length construction when $m\ge 2$, because no singleton is allowed; for $m=1$ a principal ultrafilter also works. These constructions illustrate ultrafilter selection from a partition-rich family.

The infinite-length answer is no. Colour $n$ by $\lfloor {\log }_{2}n\rfloor \mathrm{mod}2$, so successive intervals $[2^j,2^{j+1})$ alternate colours. An infinite arithmetic progression $a+td$, $t\ge 0$, meets every sufficiently large such interval: its first term at least $2^j$ is less than $2^j+d$, which is at most $2^{j+1}$ once $2^j\ge d$. It therefore has terms of both colours. Neither colour class contains an infinite arithmetic progression, but every ultrafilter contains one of the two colour classes. This dyadic block obstruction to infinite arithmetic progressions rules out the proposed ultrafilter.

For a finite alphabet $K$, a combinatorial line in $K^N$ has a nonempty active set $J\subseteq \{1,\dots ,N\}$, fixed letters outside $J$, and the same variable letter at every coordinate in $J$. The Hales-Jewett theorem states that for every alphabet size $k\ge 1$ and number of colours $r\ge 1$, some $N$ makes every r-colouring of $\{1,\dots ,k{\}}^N$ contain a monochromatic combinatorial line.

We first prove the alphabet insensitivity lemma with a concrete bound. Fix two distinct letters $a,b$, a desired dimension $d$, and a colouring $\chi :K^N\to \{1,\dots ,r\}$. A combinatorial subspace of dimension $d$ has disjoint nonempty active blocks $J_1,\dots ,J_d$ and fixed other coordinates. It is $(a,b)$-insensitive when exchanging $a,b$ in any one variable leaves the colour unchanged, whatever the other variable letters are.

Choose consecutive blocks of lengths $L_1,\dots ,L_d$ recursively byProcess these blocks from right to left. When block $i$ is reached, the later blocks already have one variable each; the earlier $P_i$ coordinates are still entirely unrestricted. For each of the $L_i+1$ words $a^t{b}^{L_i-t}$ in block $i$, form its complete colour profile over all $k^{P_i}$ earlier words and all $k^{d-i}$ assignments to the later variables. There are at most $r^{k^{P_i+d-i}}=L_i$ profiles. The pigeonhole principle gives $s<t$ with equal profiles. Fix the first $s$ coordinates of this block to $a$, the coordinates after $t$ to $b$, and make the interval from $s+1$ to $t$ variable. Substitution of $b$ gives the chain word indexed by $s$, and substitution of $a$ gives the one indexed by $t$; they have identical profiles. Thus this variable is insensitive to $a,b$ for every remaining context. Previously constructed later variables remain insensitive, because their colour equalities held for every possible earlier word. After all $d$ blocks, we have the required insensitive combinatorial subspace. This proves the explicit block bound for alphabet insensitivity.

Now induct on $k$, simultaneously for every $r$. The case $k=1$ is immediate with $N=1$. For $k\ge 2$, assume the Hales-Jewett theorem for the alphabet of size $k-1$, and take $d$ large enough for that theorem with $r$ colours. Apply the proved alphabet insensitivity lemma to the letters $k-1,k$, obtaining a d-dimensional combinatorial subspace $\varphi :K^d\to K^N$. On $\{1,\dots ,k-1{\}}^d$, the induced colouring $\chi \circ \varphi$ has a monochromatic combinatorial line. Its value at letter $k$ has the same colour as its value at $k-1$: change the active variables one at a time and use insensitivity. The union of their nonempty active blocks is the active set of a combinatorial line in the original word space. All its k points have one colour, completing the induction and the proof.

To deduce the Van der Waerden theorem, take $K=\{0,\dots ,m-1\}$ and pull a colouring of the positive integers back throughA combinatorial line with active set $J$ maps toHence every finite colouring has a monochromatic arithmetic progression of every prescribed finite length. In finite form, if $H(k,r)$ is a word-length bound for the Hales-Jewett theorem, then $W(r,m)\le 1+(m-1)H(m,r)$ is a valid interval bound.

The Strengthened Van der Waerden theorem also puts the common difference in the colour class:Here is a finite proof by induction on the number $r$ of colours. For $m=1$ choose $a=d=1$. For $r=1$ choose $a=d=1$ in $[m]$. For $m\ge 2,r\ge 2$, let $M$ be a bound for the strengthened theorem with $r-1$ colours, put $L=(m-1)M+1$, and let $W=W(r,L)$ be an ordinary Van der Waerden theorem bound. Work in $[MW]$. Its first $W$ points contain a monochromatic progressionof colour $c$. Every $jd$, $1\le j\le M$, lies in $[MW]$. If some $jd$ has colour $c$, then $a,a+jd,\dots ,a+(m-1)jd$, together with its difference $jd$, gives the answer. Otherwise the colouring of $\{d,2d,\dots ,Md\}$ uses only $r-1$ colours. Pull it back to $[M]$ and apply the induction hypothesis to get a monochromatic set $\{e,b,b+e,\dots ,b+(m-1)e\}$. Multiplication by $d$ gives the required configuration in the original colouring. This proves the strengthened theorem, including finite bounds.

The Gallai theorem for an integer lattice states that every finite colouring of ${\mathbb{Z}}^h$ contains a monochromatic homothetic copy $u+tF$ of every prescribed finite nonempty pattern $F\subseteq {\mathbb{Z}}^h$, where $t$ is a positive integer. The positive-lattice version holds for finite $F\subseteq {\mathbb{N}}^h$ as well. Write $F=\{v_1,\dots ,v_k\}$ and colour $w\in \{1,\dots ,k{\}}^N$ by the colour ofA monochromatic combinatorial line maps to $u+|J|F$, with $u=b+{\sum }_{j\notin J}{v}_{w_j}$. Thus the Hales-Jewett theorem supplies the copy, with nonzero dilation $|J|$. Choosing $b$ large and positive places all these word sums in the positive lattice if required. This sum map from words to homothetic copies also proves the real-vector-space version: replace ${\mathbb{Z}}^h$ by ${\mathbb{R}}^h$ and allow an arbitrary finite real pattern, while retaining positive integer dilations.

For disjoint vertex sets $A,B$, define their edge density of a bipartite graph by $d(A,B)=e(A,B)/(|A||B|)$. They form a regular pair with parameter $\epsilon$ if every $A^{\prime }\subseteq A,B^{\prime }\subseteq B$ with $|A^{\prime }|\ge \epsilon |A|$, $|B^{\prime }|\ge \epsilon |B|$ satisfies $|d(A^{\prime },B^{\prime })-d(A,B)|\le \epsilon$.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and minimum cell count $k_0$, some $K,n_0$ have the following property. Every graph on $n\ge n_0$ vertices admitswith $|V_0|\le \epsilon n$, equal-sized $V_1,\dots ,V_k$, and at most $\epsilon k^2$ unordered irregular pairs. It is enough to consider $0<\epsilon <1/2$.

Prove this using equitable regularity energy. Treat exceptional vertices as singleton cells and setwith ordered pairs and the adjacency indicator also defining diagonal densities. Then $0\le q\le 1$. The refinement variance identity for regularity energy proves refinement cannot decrease $q$:An irregular pair supplies witness subsets of relative sizes at least $\epsilon$ whose density differs by more than $\epsilon$. Refining along those witnesses raises $q$ by more than ${\epsilon }^4{L}^2/n^2$ per orientation, where $L$ is the common cell size. If there are more than $\epsilon k^2$ irregular pairs, the increase is greater than ${\epsilon }^5(kL/n{)}^2\ge {\epsilon }^5/4$, provided the exceptional set has size at most $n/2$.

Refine each cell by all its witness subsets; this produces at most $2^k$ atoms per cell. Restore equal sizes by the equalization with a controlled exceptional set: cut each atom into blocks of size $\lfloor L/4^k\rfloor$ and declare its remainder exceptional, still retaining every such vertex as a singleton in the energy. This is another refinement, so no energy is lost. At most $k{2}^k\lfloor L/4^k\rfloor \le n{2}^{-k}$ vertices become exceptional, and, when $L\ge 2\cdot 4^k$, at most $2k{4}^k$ new nonexceptional cells occur.

Put $T=\lceil 4{\epsilon }^{-5}\rceil$ and start with $k\ge k_0$ so large that $T{2}^{-k}\le \epsilon /2$. An initial equitable partition has at most $\epsilon n/2$ exceptional vertices when $n$ is sufficiently large. Subsequent cell counts only increase, so the total added exceptional set has size at most $\epsilon n/2$. The recurrence $k\mapsto 2k{4}^k$, iterated at most $T$ times, supplies a finite bound $K$; choose $n_0$ large enough that every intermediate $L$ meets the size requirement. More than $T$ unsuccessful refinements would raise $q$ above one. The process must therefore stop with the required regular pairs. This proves the lemma.

Its usefulness comes from replacing an arbitrarily large graph by the bounded reduced graph of a regularity partition. For fixed positive cross-density, the graph embedding lemma for regular pairs lifts fixed configurations from the reduced graph to the original one. In particular, three sufficiently regular positive-density pairs contain many triangles in a graph. Deleting exceptional, intracell, irregular and sparse-pair edges then gives the triangle removal lemma: a graph with sufficiently few triangles can be made triangle-free by deleting $o(n^2)$ edges. A triangle surviving in the reduced graph would force a positive proportion of the original possible triangles, a contradiction. More generally this approach yields the clique removal lemma and the asymptotic Erdős-Stone theorem. Applied to the tripartite graph encoding $x+z=2y$, triangle removal also gives Roth theorem on three-term arithmetic progressions. The price is that the energy argument gives a very rapidly growing, iterated-exponential bound on $K(\epsilon )$; the lemma is a structural tool, not a promise of small practical constants.

The positive-power length assertion is an asymptotic one: it requires $N$ sufficiently large in terms of the density. Read literally for every $N$, it fails when $N=2$, $\delta =1/2$ and $A=\{1\}$, whose triple sumset is a singleton. We prove the intended result with this necessary qualification and an explicit positive exponent.

Embed the interval into the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$ with $M=8N$, and set $u=1_A$, $\alpha =|A|/M\ge \delta /8$. Since all integer triple sums lie in $[3,3N]$, this embedding introduces no collisions between distinct sums. Use normalized Fourier coefficients on a finite abelian group and normalized convolution on a finite group, and putThe function $F$ is nonnegative and has mean ${\alpha }^3$, so some $t_0$ satisfies $F(t_0)\ge {\alpha }^3$. We show that a whole translated Bohr set is contained in its positive support, hence in the triple sumset.

Put $\theta ={\alpha }^2/8$, $\rho =\alpha /4$, and define the large spectrumThe Parseval identity on a finite group gives ${\sum }_r|\hat{u}(r){|}^2=\alpha$, soAlso $|\hat{u}(r)|\le \alpha$, and therefore ${\sum }_r|\hat{u}(r){|}^3\le {\alpha }^2$. Using Fourier inversion and the convolution theorem on a finite group, for $b\in B$ we obtainConsequently $F(t_0+b)\ge {\alpha }^3/2>0$. This proves the translated Bohr neighborhood in a triple sumset:It remains to produce a long ordinary integer arithmetic progression in this translate; we supply the simultaneous approximation and the lifting argument. SetThus $d=|\Gamma |\le D$. Partition the $d$-dimensional unit cube into $Q^d$ boxes of side $1/Q$. The $Q^d+1$ pointscontain two in the same box by the pigeonhole principle. Their index difference gives an integer $q$ with $1\le q\le Q^d<M$ andIn particular $|e^{2\pi irq/M}-1|\le 2\pi /Q$. The identity $z^j-1=(z-1)(1+\cdots +z^{j-1})$ on the unit circle now shows thatAll residues $t_0+jq$ therefore lie in the triple sumset. Let $s_j\in [3,3N]$ be their actual integer representatives. Their successive differences are congruent to $q$ modulo $M$, and each lies in $[-(3N-3),3N-3]$, which is contained in $(-M/2,M/2)$. There is at most one integer in this interval in any specified residue class, so every difference $s_{j+1}-s_j$ is the same integer. It is nonzero because $0<q<M$. Thus the $s_j$ form an ordinary integer arithmetic progression of distinct elements, even though $M$ is composite. Reversing it if necessary makes the common difference positive.

For sufficiently large $N$, we have $Q\ge \frac{1}{2}{M}^{1/(D+1)}$ and $\rho \ge \delta /32$, whenceAbsorb this fixed prefactor by decreasing the exponent: withthe last lower bound is at least $N^{r_{\delta }}$ once $N$ is sufficiently large in terms of $\delta$. This proves a polynomial-length progression in $A+A+A$ by the polynomial-length progression in a dense triple sumset argument, without replacing the triple sumset by a fourfold difference set.

Fix integers $q\ge 1$ and $a$ with $(a,q)=1$. We prove the Dirichlet theorem on primes in arithmetic progressions by showing that the prime Dirichlet sum in this residue class diverges as its real exponent decreases to one.

First justify the required Dirichlet L-function facts. If $\chi$ is a nonprincipal Dirichlet character modulo $q$, its sum over a full period is zero: choose a unit $b$ with $\chi (b)\ne 1$, and multiplication by $b$ permutes the residue classes, forcing the sum to equal $\chi (b)$ times itself. Therefore the partial sums $C_{\chi }(u)={\sum }_{n\le u}\chi (n)$ are bounded by $q$. Partial summation giveswhich supplies holomorphic continuation near one, with locally uniform convergence. For the principal Dirichlet character ${\chi }_0$,has a simple pole at one, with residue $\phi (q)/q$.

The assumption in the question gives nonvanishing at one for real nonprincipal characters. We must also prove it for nonreal characters. For a nonreal $\chi$, its square ${\chi }^2$ is nonprincipal. For real $\sigma >1$, logarithms of the Euler products giveFor a prime not dividing $q$, its logarithmic coefficient is $3+4\mathrm{Re}\chi (p{)}^k+\mathrm{Re}\chi (p{)}^{2k}=2(1+\cos \theta {)}^2\ge 0$, where $\chi (p{)}^k=e^{i\theta }$. Primes dividing $q$ contribute only the positive zeta term. If $L(1,\chi )$ vanished to order $m\ge 1$, the product would be $O((\sigma -1{)}^{4m-3})$ and tend to zero: the squared-character factor is bounded because ${\chi }^2$ is nonprincipal. This is a contradiction. HenceThis step uses the given real-character hypothesis and the Euler product positivity for L-function nonvanishing for all remaining characters.

In $\sigma >1$ choose the logarithm furnished by the absolutely convergent Euler product. Its prime-power expansion givesThe error from powers $k\ge 2$ is uniformly bounded as $\sigma \downarrow 1$, by ${\sum }_p{\sum }_{k\ge 2}1/(k{p}^{k\sigma })<\infty$. For nonprincipal $\chi$, nonvanishing and holomorphic continuation at one provide a bounded logarithm in a neighborhood of one. The Euler-product branch differs from that branch by a constant integral multiple of $2\pi i$ on the final real interval, so it too is bounded. ThusFor the principal character, its simple pole instead gives

The Orthogonality of Dirichlet characters gives, for primes not dividing $q$,Multiply by $p^{-\sigma }$ and sum. Absolute convergence allows the interchange for $\sigma >1$, soThe right side tends to infinity. If there were only finitely many primes in the progression, the left side would have a finite limit at one. This contradiction proves infinitely many primes occur in every reduced residue class. For $q=1$ or $2$ the character argument simply has no nonprincipal terms and gives the same conclusion.

For the final deduction the modulus $q$ is fixed. Let $A(t)=\pi (t;q,a)$. The given consequence of the Siegel–Walfisz theorem is $A(t)\sim t/(\phi (q)\log t)$. Partial summation, including the prime $2$ through the lower endpoint $2^{-}$ when appropriate, givesThe boundary is $O_q(1/\log x)$. Write $A(t)=t(1+\epsilon (t))/(\phi (q)\log t)$ with $\epsilon (t)\to 0$. The main integral is $(\log \log x-\log \log 2)/\phi (q)$. The error is $o(\log \log x)$: given $\eta >0$, choose $T$ such that $|\epsilon (t)|\le \eta$ for $t\ge T$. Its integral from $2$ to $T$ is a fixed constant, and its absolute value from $T$ to $x$ is at most $\eta \log \log x/\phi (q)$ plus a fixed constant. Divide by $\log \log x$ and then let $\eta \downarrow 0$. We obtain the reciprocal primes in a fixed arithmetic progression asymptoticThe argument uses the supplied prime-counting asymptotic in this last part; the preceding infinitude proof did not assume the Prime number theorem in arithmetic progressions.

Van der Waerden theorem says that for every pair of positive integers $r,k$ there is $W(r,k)$ such that every finite colouring of $[W(r,k)]=\{1,\dots ,W(r,k)\}$ using at most $r$ colours contains a monochromatic arithmetic progression of length $k$ and positive common difference. Consequently every finite colouring of $\mathbb{N}$ contains arbitrarily long monochromatic arithmetic progressions.

Here is a colour-focusing proof of Van der Waerden theorem. Induct on $k$, simultaneously for all $r$. For $k=1$, take $W(r,1)=1$. Suppose $W(R,k)$ exists for every number of colours $R$, and fix $r$. We will construct finite bounds $F_t$, $1\le t\le r$, with the following property: every finite colouring of $[F_t]$ using at most $r$ colours contains either a monochromatic length-$(k+1)$ arithmetic progression, or $t$ length-$k$ arithmetic progressions of pairwise distinct colours, all focused at the same point $f\in [F_t]$. Specifically, their terms are“Focused” means that adjoining $f$ completes the corresponding length-$(k+1)$ arithmetic progression if $f$ has its colour.

For $t=1$, put $F_1=2W(r,k)$. Find a monochromatic length-$k$ arithmetic progression in the first $W(r,k)$ points. Its next point is at most $2W(r,k)$ and supplies the focus. For $k=1$, give the selected singleton common difference $1$.

Suppose $F_t=N$ has been constructed. SetDivide $[2NM]$ into $2M$ consecutive blocks of length $N$. Colour the first $M$ block indices by their full colour profiles, that is, the ordered list of their $N$ colours. There are at most $r^N$ profiles, so the induction hypothesis on $k$ gives equally profiled blocks with indicesWhen $k=1$, choose $D=1$. Otherwise $D>0$ and $j_0+kD\le 2M$, since the last selected block is at most $M$ and $D\le M$.

Assume the original finite colouring contains no monochromatic length-$(k+1)$ arithmetic progression. Applying the property of $F_t$ to the common profile gives $t$ focused length-$k$ arithmetic progressions at a position $f$, with common differences $d_i$ and distinct colours $q_i$. The colour $q$ of position $f$ differs from every $q_i$: otherwise the profile already contains a length-$(k+1)$ monochromatic arithmetic progression, and so does any selected block.

Put $j_{\ast }=j_0+kD$ and $F=N(j_{\ast }-1)+f$, a point in the original interval. For $1\le h\le k$, the pointlies in a selected block at profile position $f-h{d}_i$, so has colour $q_i$. Similarly $F-hND$ has colour $q$. Thus $t+1$ length-$k$ arithmetic progressions of distinct colours focus at $F$. This proves the step in $t$. At $t=r$, the focus necessarily has the colour of one of the $r$ progressions, giving a monochromatic length-$(k+1)$ arithmetic progression. Hence $W(r,k+1)$ exists, completing the mathematical induction and the proof of Van der Waerden theorem.

For the partition regularity deduction we first prove a strengthened progression lemma, the Brauer progression theorem: for positive $r,s,L$ with $L\ge 2$, there is $B(r,s,L)$ such that every finite colouring of $[B(r,s,L)]$ using at most $r$ colours contains a monochromatic setInduct on $r$. For $r=1$, take $B(1,s,L)=\max (s,L)$ and $a=d=1$. Given the result for $r-1$, putVan der Waerden theorem supplies a colour-$q$ arithmetic progression $a+j{d}_0$, $0\le j<K$, inside $[W]$. If some $sj{d}_0$, $1\le j\le N$, also has colour $q$, take $d=j{d}_0$ and use the $L$ terms $a,a+j{d}_0,\dots ,a+(L-1)j{d}_0$. They are in the progression because $(L-1)j\le K-1$.

Otherwise the integers $sj{d}_0$, $1\le j\le N$, use at most $r-1$ colours. Colour $j\in [N]$ by the colour of $sj{d}_0$ and apply the induction hypothesis. It supplies a monochromatic set $\{se,b,b+e,\dots ,b+(L-1)e\}$. Multiplying by $s{d}_0$ gives the required configuration with $a=s{d}_{0}b$ and $d=s{d}_{0}e$: its distinguished member is $s^2{d}_{0}e=sd$. All of these points are at most $sN{d}_0\le sNW$, so the finite bound is valid. This proves the Brauer progression theorem using only the just-proved Van der Waerden theorem.

A row is a partition regular matrix over the positive integers if every finite colouring of $\mathbb{N}$ admits a positive vector $x$ whose coordinates have one colour and whose product with the row is zero. Coordinates may repeat. Since the coefficients are rational numbers, multiplying them by a common positive denominator leaves the equation and every zero subset sum unchanged, so write the row as nonzero integer coefficients $b_1,\dots ,b_n$.

To prove necessity, suppose no nonempty subset of the $b_i$ sums to zero. Choose a prime $p>{\sum }_i|b_i|$ and use the last nonzero digit coloringwhere $v_p$ is the P-adic valuation. If positive $x_i$ all had the same colour $u$ and satisfied ${\sum }_i{b}_i{x}_i=0$, let $m={\min }_i{v}_p(x_i)$ and $I=\{i:v_p(x_i)=m\}$. After division by $p^m$ and reduction modulo $p$, the equation becomesAs $u\ne 0$, this says $p\mid {\sum }_{i\in I}{b}_i$. The latter sum is nonzero and has absolute value at most ${\sum }_i|b_i|<p$, a contradiction. This explicitly proves the necessary obstruction without invoking a general partition regularity criterion.

Conversely, suppose $\varnothing \ne I\subseteq \{1,\dots ,n\}$ and ${\sum }_{i\in I}{b}_i=0$. Select an index $j\in I$, and putFor any finite colouring, the Brauer progression theorem gives one-coloured $\{sd,a,a+d,\dots ,a+(L-1)d\}$. The indices $u$ and $u+q$ both lie between $0$ and $L-1$. Define positive, same-coloured coordinates byThenThis also covers $I$ equal to the whole index set and $q=0$. Reversing the clearing of denominators proves the exact criterion: