We prove the Roth theorem on three-term arithmetic progressions by a density increment on an ordinary integer arithmetic progression. The required increment will be small, but depend only on the current subset density.

First establish the increment step. Suppose $A\subseteq [1,L]$ has subset density $\rho =|A|/L>0$ and no nonconstant three-term arithmetic progression. Put $M=4L+1$, regard $[1,L]$ as a subset $I$ of the cyclic group ${\mathbb{Z}}_M$, and set $f=1_A-\rho 1_I$. Then $\mathbb{E}f=0$ and $|f|\le 1$. Use the normalized Fourier coefficient on a finite abelian groupThe character orthogonality geometric-series identity ${\mathbb{E}}_x{e}^{2\pi irx/M}=1$ for $r=0$ and zero otherwise gives Fourier inversion on a finite group, Parseval identity on a finite group, andSince $M$ is odd, multiplication by two permutes its frequencies. If one argument is $f$ and the other two have absolute value at most one, Cauchy-Schwarz and the Parseval identity on a finite group give $|T|\le {\max }_r|\hat{f}(r)|$.

A modular arithmetic progression whose three entries lie in $I$ satisfies the corresponding integer equation: the absolute value of $x+z-2y$ is less than $2L<M$, so congruence to zero forces equality. Thus $T(1_A,1_A,1_A)=|A|/M^2\le 1/(16L)$, since only constant arithmetic progressions remain. Meanwhile, the choices $1\le x\le \lfloor L/2\rfloor$ and $0\le h\le \lfloor L/4\rfloor$ give at least $L^2/16$ arithmetic progressions in $I$ for $L\ge 8$. As $M\le 5L$, this gives $T(1_I,1_I,1_I)\ge 1/400$. Expand $1_A=\rho 1_I+f$. The seven terms other than the main term are each bounded by $\max |\hat{f}|$. For $L\ge 50{\rho }^{-3}$,Consequently a nonzero frequency $r$ obeys $|\hat{f}(r)|\ge \gamma$, where $\gamma ={\rho }^3/6000$. It is nonzero because $\hat{f}(0)=0$.

We turn this coefficient into a local increase. Let $Q=\lfloor \sqrt{L}\rfloor$. Partition the unit circle into $Q$ equal intervals and consider the $Q+1$ points $jr/M$, $0\le j\le Q$, modulo one. Two occupy the same interval, yielding an integer $1\le q\le Q$ with $\Vert qr/M{\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. Set $\ell =\lfloor \gamma Q/200\rfloor$. If $L$ exceeds a sufficiently large absolute multiple of ${\rho }^{-6}$, then $\ell \ge 1$ and each residue-class arithmetic progression of step $q$ in $[1,L]$ has at least $\ell$ terms. Partition each into pieces of lengths between $\ell$ and $2\ell$, distributing the final remainder among the pieces.

On each such arithmetic progression $P$, the character of a finite abelian group $\chi (x)=e^{-2\pi irx/M}$ differs from its value at the first point by at most $4\pi \ell /Q<\gamma /4$. Write $s_P={\sum }_{x\in P}f(x)$. Thereforeso ${\sum }_P|s_P|\ge 3\gamma L/4$. But ${\sum }_P{s}_P={\sum }_{I}f=0$, and hence the sum of the positive $s_P$ is at least $3\gamma L/8$. Some piece must consequently satisfy $s_P/|P|\ge \gamma /4$. On that piece,Also, once $\gamma Q\ge 400$, $|P|\ge \ell \ge \gamma \sqrt{L}/800$. This proves the one-frequency density increment on an integer interval: for absolute constants $c,C>0$, if $L\ge C{\rho }^{-6}$, there is a arithmetic progression $P\subseteq [1,L]$ of length at least $c{\rho }^3\sqrt{L}$ on which the subset density rises by at least $c{\rho }^3$. For example one may decrease $c$ to $10^{-7}$ and choose $C$ large enough for the displayed elementary inequalities.

Now fix $0<\delta \le 1$ and suppose the required conclusion fails. On each new arithmetic progression, identify its points in order with $[1,L^{\prime }]$. This affine identification preserves all integer arithmetic progressions, so its copy of $A\cap P$ is still progression-free. All densities remain at least $\delta$. Put $\epsilon =c{\delta }^3$, $H=C{\delta }^{-6}$, and choose an integer $t>1/\epsilon$. Every increment raises the subset density by at least $\epsilon$ and changes the length by $L_{j+1}\ge \epsilon \sqrt{L_j}$. Iterating the latter inequality givesChoose $N>(H/{\epsilon }^2{)}^{2^t}$. Then every length up to step $t$ exceeds $H$, so every increment is available. After $t$ increments the subset density exceeds one, a contradiction. ThusFor $\delta >1$ there are no sets satisfying the subset density assumption. The argument above proves the substantive case without invoking the theorem being asked for.

Let $U=G\bigsqcup \bar{G}$, with the two copies of the graph vertex set distinguished. In $G⊠\bar{G}$, the diagonal pairs $(v,v)$ form an independent set of size $n$: for $v\ne w$, their adjacency cannot hold in both a graph and its complement graph. There is another such diagonal set in $\bar{G}⊠G$. These two types lie in different components of $U^{⊠2}$, so their set union is independent. Thuswhich proves the printed bound.

A stronger complement-pair capacity gain will make the strict inequality transparent. In words of length $2m$, choose a pattern of $m$ coordinates from $G$ and $m$ from $\bar{G}$. Match the $i$th coordinate of the first type with the $i$th of the second type, and put the same graph vertex label in each pair. This gives $n^m$ independent words for each pattern: if two label tuples differ, their differing pair has a nonedge in one of the two complementary graphs. Codes belonging to distinct patterns are mutually nonadjacent, since some coordinate lies in different components of the disjoint set union. ConsequentlyThe inequalities $4^m/(2m+1)\le \left(\genfrac{}{}{0ex}{}{2m}{m}\right)\le 4^m$ show that its $2m$th root tends to two. ThereforeThis strengthens, rather than changes, the bound requested in the PDF.

For a polynomial representation of a graph over a field $F$, choose points $a_v\in F^r$ and polynomials $f_v\in M$, where $M\subseteq F[z_1,\dots ,z_r]$ is a finite-dimensional vector space, such thatNo condition is imposed at adjacent pairs. To bound a strong power, put its polynomials in disjoint variable blocks:They lie in a polynomial space canonically identified with $M^{\otimes m}$, of dimension $({\dim }_{F}M{)}^m$. For an independent set of words, evaluation of their polynomials at their associated point tuples is a diagonal matrix with nonzero diagonal: distinct words have a nonedge coordinate, which supplies a zero factor. The polynomials in that independent set are therefore linearly independent, since evaluating any linear relation at each tuple forces its corresponding coefficient to be zero. HenceThis is the polynomial form of the Haemers rank bound, proved here by evaluations and tensor products rather than assumed.

For an explicit counterexample, let the graph vertices of $G$ be the five-element subsets of $[20]$. Join distinct $A,B$ exactly when $|A\cap B|$ is odd. There are $n=\left(\genfrac{}{}{0ex}{}{20}{5}\right)=15504$ graph vertices. Over ${\mathbb{F}}_2$, take $a_B=1_B$ andAt the diagonal $f_A(a_A)=5=1$ in the field. At a distinct nonedge the set intersection is even, so $f_A(a_B)=0$. These polynomials lie in the twenty-dimensional space spanned by $z_1,\dots ,z_{20}$, proving $c(G)\le 20$.

Represent the complement graph over ${\mathbb{F}}_3$, using the same indicator vectors andIts evaluation at $a_B$ is $\left(\genfrac{}{}{0ex}{}{|A\cap B|}{2}\right)$. The diagonal value is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10=1$ modulo three. Distinct nonedges of $\bar{G}$ are edges of $G$, so the set intersection size is one or three. Their evaluations are respectively zero and $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3=0$ modulo three. The polynomials belong to the space spanned by the squarefree quadratic monomials $z_i{z}_j$, $i<j$, of dimension $\left(\genfrac{}{}{0ex}{}{20}{2}\right)=190$. Therefore $c(\bar{G})\le 190$.

The graph capacity inequalities are real-number bounds regardless of which field supplies the polynomial representation of a graph. Combining them with the stronger set union lower bound givessince $4\cdot 15504=62016>210^2=44100$. This proves nonadditivity of Shannon capacity for the graph just defined, with both individual upper bounds calculated explicitly.

All graphs here are finite and simple. For the strong graph product $G⊠H$, two distinct graph vertex pairs are adjacent if in each coordinate the entries are equal or adjacent. Use $G^{⊠m}$ for its strong graph power; the exam's $G^m$ means this product power, not the distance-based graph power. The Shannon capacity of a graph iswhere $\alpha$ is the independence number. Products of independent sets are independent, so $a_{r+s}\ge a_r{a}_s$ for $a_m=\alpha (G^{⊠m})$. To see why the limit exists, fix $r$ and write $m=qr+s$, $0\le s<r$. Then $a_m\ge a_r^q$, using $a_s\ge 1$ and $a_0=1$, so ${\mathrm{liminf}}_m(\log a_m)/m\ge (\log a_r)/r$. Take the supremum over $r$; the reverse upper bound holds termwise. This proves the required form of Fekete lemma. For the empty graph on no graph vertices one sets graph capacity zero separately.

Associativity of the strong product givesAn orthonormal representation of a graph assigns a real unit vector $u_v$ to each graph vertex, with $u_v\perp u_w$ whenever distinct graph vertices $v,w$ are nonadjacent. Adjacent graph vertices need not receive orthogonal vectors. A handle is a unit vector $h$. The handle formulation of the Lovász theta function iswith a zero denominator giving infinity. Representations may use any finite-dimensional Euclidean space. This is the usual Lovász number in its orthonormal-representation formulation.

For an independent set $I$, the vectors $u_v$, $v\in I$, are mutually orthonormal. Directly,If $T={\max }_v|h\cdot u_v{|}^{-2}$ is finite, every summand is at least $1/T$, giving $|I|\le T$. For a strong power, use the vectors and handleTheir norms are one. Nonadjacency of two distinct words means a coordinate has distinct nonadjacent entries, so the corresponding tensor inner product has a zero factor. The handle inner products satisfyApplying the preceding calculation gives $\alpha (G^{⊠m})\le T^m$. Taking roots, then the infimum over representations and handles, provesThis is the tensor-product capacity bound from an orthonormal representation, and the displayed projection calculation supplies Bessel inequality explicitly.

For $C_5$, label graph vertices by $\mathbb{Z}/5\mathbb{Z}$, with edges at differences $\pm 1$. The five wordsare independent in its strong square: a difference $\pm 1$ in the first coordinate produces a nonedge difference $\pm 2$ in the second, while a first-coordinate difference $\pm 2$ is already a nonedge. Hence $c(C_5)\ge \sqrt{5}$.

For the matching upper bound set $\rho =1/\sqrt{5}$, $h=(0,0,1)$, andEach vector is unit. For a nonedge, the angle difference is $\pm 4\pi /5$, andbecause $\cos (4\pi /5)=-(1+\sqrt{5})/4$ and $\rho =1/\sqrt{5}$. Thus these vectors form an orthonormal representation. The handle has $|h\cdot u_j{|}^2=\rho$, giving $\vartheta (C_5)\le 1/\rho =\sqrt{5}$. Together the two bounds prove the pentagon capacity code result