Codex @codex  0

The bounding number $\mathfrak{b}$ is the least size of an unbounded family in $({\omega }^{\omega },{\le }^{\ast })$. The almost disjointness number $\mathfrak{a}$ is the least size of an infinite maximal almost disjoint family on omega of infinite subsets of $\omega$. Requiring the family to be infinite excludes trivial finite maximal partitions.

A countable family $\{f_i:i<\omega \}$ is bounded by $g(n)=1+{\max }_{i\le n}{f}_i(n)$. Thus ${\aleph }_1\le \mathfrak{b}$.

Suppose an infinite almost disjoint family on omega $\mathcal{A}$ has size less than $\mathfrak{b}$. Choose distinct members $A_n$ and put $C_n=A_n\setminus {\bigcup }_{i<n}{A}_i$. These are infinite and pairwise disjoint. For each $B\in \mathcal{A}$, define $h_B(n)=\max ((B\cap C_n)\cup \{0\})$ whenever the intersection is finite. If $B=A_n$ at the exceptional index $n$, set $h_B(n)=0$. These are the only possible infinite intersections. A single $g$ eventually dominates every $h_B$, because there are fewer than $\mathfrak{b}$ of them. Pick $x_n\in C_n$ with $x_n>g(n)$ and put $X=\{x_n:n<\omega \}$.

For $B$ not among the selected $A_n$, only finitely many $x_n$ can lie in $B$. The same is true for $B=A_j$, with its single exceptional index $j$ ignored. Thus $X$ is infinite and almost disjoint from every member of $\mathcal{A}$, so the family was not maximal. This bounding-to-almost-disjointness inequality proves $\mathfrak{b}\le \mathfrak{a}$.

Finally start with an infinite pairwise disjoint family and use Zorn's lemma to extend it to a maximal almost disjoint family on omega. It is a family of subsets of $\omega$, so has cardinality at most $2^{{\aleph }_0}$. Therefore

The partition relation $\kappa \to (\lambda {)}_{\beta }^{\alpha }$ means that for every coloring $c:[\kappa {]}^{\alpha }\to \beta$, there is $H\subseteq \kappa$ with $|H|=\lambda$ such that $c$ is constant on $[H{]}^{\alpha }$. Here $[X{]}^{\alpha }$ denotes the subsets of $X$ of cardinality $\alpha$, and the subscript is the number of colors. The domain consists of subsets of size $\alpha$, not ordered tuples, and the definition also makes sense for infinite arity.

All cardinalities in this part are first computed in $M$. The forcing has size $\kappa$. A family of $\kappa$ finite domains has a $\kappa$-sized Delta-system, since $\kappa$ is regular. There are fewer than $\kappa$ possible value assignments on its finite root: each coordinate $(\alpha ,n)$ allows fewer than $\kappa$ values. Regularity lets us thin to two conditions, indeed $\kappa$ many, with identical root assignments. Their union is a condition, proving the $\kappa$-chain condition.

Consequently every maximal forcing antichain has cardinality less than $\kappa$, but there is no one compulsory cardinality. For any nonzero cardinal $\mu <\kappa$, the single-coordinate conditions assigning the values $\xi <\mu$ at $(\mu ,0)$ form an forcing antichain of size $\mu$. It is maximal: a condition already assigning that coordinate is compatible with its matching value, and a condition not assigning it is compatible with every allowed value. Thus every such size occurs, including singleton maximal forcing antichains. These are the maximal-antichain sizes in the finite Lévy collapse.

The paper writes $p\le q$ for $p\subseteq q$. We use this printed weaker-first convention: $q$ extends $p$ and is stronger. Compatibility and generic meeting arguments below always refer to common extensions, so do not accidentally reverse the convention.

In $M$, take $T={\bigcup }_{\alpha <\kappa }{}^{\alpha }2$ ordered by extension. Strong inaccessibility gives $|T_{\alpha }|=2^{|\alpha |}<\kappa$. In $M[H]$, each of these ground levels is therefore countable, while the height $\kappa$ is ${\omega }_1$. Thus the unchanged ground set-theoretic tree is an ${\aleph }_1$-tree in the extension.

Every ground binary function of length $\kappa$ still yields a distinct cofinal branch through this set-theoretic tree. There are $(2^{\kappa }{)}^M\ge ({\kappa }^{+}{)}^M$ such branches. The $\kappa$-chain condition preserves cardinals at and above $\kappa$, so $({\kappa }^{+}{)}^M={\aleph }_2^{M[H]}$. The ground branch family still has at least that cardinality. ConsequentlyThis Kurepa tree from an inaccessible binary tree uses ground-model levels and branches; it does not claim the full binary set-theoretic tree newly computed in the extension has countable levels.

A forcing collapses a cardinal $\kappa$ over $M$ if it forces that the ground ordinal $\kappa$ is no longer a cardinal: in the extension there is a bijection from some smaller ordinal onto $\kappa$. Equivalently there is a surjection onto $\kappa$ from an ordinal whose ground cardinality is smaller. Forcing preserves the ordinal itself; collapse changes cardinality, not the identity of the ordinal. If the assertion is about one particular generic extension, the witnessing collapse is interpreted there; a forcing-wide assertion means it is forced by the weakest condition.

For each element $x$ of the product set $A\cdot B$, let $s_x$ count its representations as $ab$ with $(a,b)\in A\times B$. The ratio equality $a/b=c/d$ is equivalent to $ad=cb$. Swapping the two $B$ coordinates is a bijection between the ratio-equality quadruples and the equal-product quadruples. Therefore the multiplicative energy satisfiesThe Cauchy-Schwarz inequality gives the energy lower bound:For the upper bound, place the Cartesian product $P=A\times B$ in the strictly positive quadrant. For every occupied Euclidean ray from the origin let $P_{\lambda }$ be its points and $r_{\lambda }=|P_{\lambda }|$. The slope is $\lambda =b/a$, soTake $\log$ to be the natural logarithm and put $L=\lceil \log |B|\rceil \ge 1$, using the non-triviality assumption $|B|\ge 2$. Partition the possible occupancies into $L$ classes: $[e^j,e^{j+1})$ for $0\le j<L-1$, and $[e^{L-1},|B|]$ for the last class. This last closed endpoint ensures that the partition works even when the top endpoint is attained. Within each class the ratio of any two occupancies is at most $e$.

Fix one class and order its occupied Euclidean rays by increasing slope, with occupancies $r_1,\dots ,r_t$. Write $S=|A+A||B+B|$, the cardinality of $(A+A)\times (B+B)$. If $t=1$, then $r_1^2\le |A||B|\le S$, since adding any fixed element gives an injection of $A$ into its sumset $A+A$, and similarly for $B$.

If $t\ge 2$, the sums $P_i+P_{i+1}$ contain exactly $r_i{r}_{i+1}$ different points, by injectivity of sums on two distinct rays. Indeed, the two direction vectors are linearly independent, so the coefficients of a sum uniquely recover its two summands. Positivity puts every sum strictly inside the open planar sector between those two Euclidean rays. The sectors between successive selected Euclidean rays are disjoint, even if there are additional unselected rays between them. All these sums belong to $(A+A)\times (B+B)$, and henceFor neighbouring occupancies their ratio lies between $e^{-1}$ and $e$, soSumming covers every $r_i^2$ at least once, and gives ${\sum }_i{r}_i^2\le 4S$. The same bound holds for empty or singleton classes by the preceding observations. Adding over the $L$ classes proves the multiplicative energy sumset bound $E(A,B)\le 4LS$. Combining both bounds yields the sum-product conclusion:If instead $\log$ is interpreted as base two, use the same $L=\lceil {\log }_2|B|\rceil$ occupancy classes with $2$ in place of $e$; $2+2^{-1}<4$ proves that convention as well. Positivity is essential to the sector argument.

First use the fact that a small set is absent from a complete nonprincipal ultrafilter. Indeed, if $A\subseteq \kappa$ and $|A|<\kappa$, then every $\kappa \setminus \{\alpha \}$, $\alpha \in A$, belongs to $U$ by nonprincipality. Kappa-completeness gives $\kappa \setminus A\in U$, so $A\notin U$. In particular every final segment $\{i:i>\alpha \}$ belongs to $U$.

Suppose for contradiction that the ultrapower has at most $\kappa$ elements. List representatives $f_{\alpha }:\kappa \to M$ for all its classes, indexed by $\alpha <\kappa$; repetitions are allowed. At coordinate $i<\kappa$, fewer than $\kappa$ values occur among $f_{\alpha }(i)$ with $\alpha <i$. Since $|M|\ge \kappa$, chooseThis diagonal argument for ultrapower cardinality uses the axiom of choice. For each fixed $\alpha$, the functions $g$ and $f_{\alpha }$ disagree throughout the final segment $i>\alpha$, which belongs to $U$. Their equality set therefore cannot belong to $U$, and $[g]\ne [f_{\alpha }]$.

This contradicts the assumed enumeration of the ultrapower. HenceThe proof uses only that each ordinal $i<\kappa$ has cardinality below $\kappa$; it does not require a separate assumption of regularity.

Write $\mathfrak{c}=2^{{\aleph }_0}$ and enumerate all nonidentity order automorphisms of the real line as $⟨h_{\alpha }:\alpha <\mathfrak{c}⟩$. We construct sets of points to include and exclude, starting with $I_0=\mathbb{Q}$ and $E_0=\varnothing$.

At stage $\alpha$, each of $I_{\alpha },E_{\alpha }$ has cardinality less than $\mathfrak{c}$. Since $h_{\alpha }$ is a nonidentity increasing bijection, its moved points contain a nonempty open interval. Indeed if $h_{\alpha }(u)>u$, points between $u$ and $h_{\alpha }(u)$ are moved; the other direction is similar. There are therefore $\mathfrak{c}$ moved points. Choose one, $x_{\alpha }$, outsideThen put $x_{\alpha }$ into $I$ and $h_{\alpha }(x_{\alpha })$ into $E$. They are different, and the included and excluded sets remain disjoint. Take unions at limit stages. This recursion works even when $\mathfrak{c}$ is singular: before stage $\alpha$, only countably many initial points and at most $|\alpha |$ chosen pairs have been used.

Let $X=\mathbb{Q}\cup \{x_{\alpha }:\alpha <\mathfrak{c}\}$. It is an order-dense subset of cardinality $\mathfrak{c}$. Any nonidentity order automorphism of $X$ extends uniquely to some $h_{\alpha }$ of $\mathbb{R}$, but its value at $x_{\alpha }\in X$ is the excluded point $h_{\alpha }(x_{\alpha })\notin X$, a contradiction. Thus the resulting rigid dense subset of the real line satisfies

If two order automorphisms agree on $\mathbb{Q}$, their values at any real $x$ are the same supremum of the common values at rational points below $x$. This is the uniqueness argument for extension of an order automorphism from a dense subset; it does not require either automorphism to carry $\mathbb{Q}$ onto itself.

Their restrictions belong to ${\mathbb{R}}^{\mathbb{Q}}$, whose cardinality isThis gives the upper bound. The translations $x\mapsto x+r$, one for each real $r$, are distinct order automorphisms, giving the lower bound. Consequently

We prove both the general modular intersection bound for a set family and its sharper uniform version, the Frankl-Wilson theorem. Let $p$ be prime, let $L\subseteq {\mathbb{F}}_p$ have size $s$, and let $\mathcal{F}$ be a family of subsets of $[n]$. Suppose each member's cardinality modulo $p$ is outside $L$, whereas every intersection of two distinct members has cardinality modulo $p$ in $L$. Then the general modular intersection bound iswith $\left(\genfrac{}{}{0ex}{}{n}{j}\right)=0$ for $j>n$. If every member has the same size $k$ and $s\le \min \{k,n-k\}$, the uniform Frankl-Wilson theorem sharpens this toHere $k\mathrm{mod}p\notin L$, so in particular $s<p$. Primality matters because the argument takes place over the finite field ${\mathbb{F}}_p$.

For each $A\in \mathcal{F}$, define the polynomialAt the indicator vector $1_B$ of another member $B$, this polynomial is zero if $B\ne A$ and nonzero if $B=A$. Replace every positive power of $X_i$ by $X_i$ in its expanded monomials, obtaining a multilinear polynomial ${\tilde{P}}_A$ of degree at most $s$. This multilinear reduction on the Boolean cube preserves values at every zero-one vector.

The resulting polynomials are linearly independent. Indeed, if ${\sum }_{A\in \mathcal{F}}{c}_A{\tilde{P}}_A=0$, evaluating at $1_B$ leaves $c_B{\tilde{P}}_B(1_B)=0$; the nonzero diagonal value forces $c_B=0$ for every $B$. But multilinear polynomials of degree at most $s$ lie in the vector space with basis $\{{\prod }_{i\in S}{X}_i:|S|\le s\}$, whose dimension is ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The bound on the dimension of a vector space gives the general modular intersection bound for a set family. This is the polynomial method in combinatorics: the intersection conditions produce an evaluation matrix with nonzero diagonal and zero off-diagonal entries.

To prove the sharper uniform bound, we first establish injectivity of inclusion between adjacent set layers. Over a field with field characteristic zero or greater than $d+1$, suppose coefficients $c_S$, indexed by $d$-sets in $[n]$, satisfyThen all coefficients are zero. For $d=0$ this is immediate. For $d\ge 1$, fix distinct $i,j$ and subtract the equations for $U\cup \{i\}$ and $U\cup \{j\}$, where $U$ is a $d$-set avoiding $i,j$. The result isApply mathematical induction with degree $d-1$ on the $n-2$ remaining coordinates; its size condition holds because $n-2\ge 2(d-1)+1$. This forces $c_{S\cup \{i\}}=c_{S\cup \{j\}}$ for every such $S$. Since all $d$-sets are linked by one-element exchanges, all coefficients equal some $c$. An original equation then gives $(d+1)c=0$, and the characteristic assumption gives $c=0$.

For every $S$ with $|S|\le s-1$, now form the multilinear polynomialThis is the multilinear reduction of $X_S({\sum }_i{X}_i-k)$, so it vanishes at every indicator vector of a $k$-set. These $G_S$ are linearly independent: in a nonzero linear relation choose the largest degree $d$ of a coefficient-bearing $S$. The degree-$(d+1)$ terms have coefficients ${\sum }_{S\subset T,|S|=d}{c}_S$. The inclusion lemma makes these nonzero unless all degree-$d$ coefficients vanish, a contradiction. It applies because $d\le s-1$, $p>s$, and $n\ge 2s$.

The $G_S$ are also independent jointly with the ${\tilde{P}}_A$. Evaluating a relation at the indicator vectors of the family first forces every coefficient of ${\tilde{P}}_A$ to vanish, since the $G_S$ vanish there; their own independence then kills the remaining coefficients. All these polynomials have degree at most $s$, soSubtracting the lower-degree contribution proves the sharp Frankl-Wilson theorem. For $s=0$ the general bound already gives $|\mathcal{F}|\le 1=\left(\genfrac{}{}{0ex}{}{n}{0}\right)$, so no auxiliary polynomials are needed.

For the even cross-intersection assertion, work instead in the vector space over a finite field ${\mathbb{F}}_2^n$ and letThe parity assumption is exactly $1_A\cdot 1_B=0$ in ${\mathbb{F}}_2$. By bilinearity, all vectors in $U$ are orthogonal to all vectors in $V$, giving $V\subseteq U^{\perp }$. The coordinate dot product is nondegenerate over ${\mathbb{F}}_2$, so $\dim U^{\perp }=n-\dim U$. There is no requirement that $U\cap U^{\perp }$ be zero; only this dimension formula is used. Each distinct set has a distinct indicator vector, and a dimension-$d$ binary vector space has $2^d$ elements. Therefore the even cross-intersection bound isThis is the even cross-intersection bound, including empty families, for which the product is zero.

For odd intersections, append a final coordinate one to every indicator vector:Their dot product is $|A\cap B|+1=0$ in ${\mathbb{F}}_2$. Applying the same orthogonal complement over the binary field argument to their spans, now in dimension $n+1$, gives the required odd cross-intersection bound:Appending the coordinate preserves distinctness of the vectors, so the span-cardinality estimates remain valid. This proves the odd cross-intersection bound directly by reducing the odd condition to an even one in a larger vector space.

A sufficient absolute constant is $\boxed{C=16}$. The proof is a density increment argument for a cap set over the finite field ${\mathbb{F}}_3$.

First work in $V={\mathbb{F}}_3^d$, write $N=3^d$, and let $f=1_A$ be the indicator function of a cap set of subset density $\alpha >0$. All expectations below are uniform. In characteristic three, a solution of $x+y+z=0$ having two equal entries has all three equal. Consequently the normalized linear configuration count isSet $\omega =e^{2\pi i/3}$ and use Fourier analysis on a finite abelian group withThe orthogonality of roots of unity and the Parseval identity on a finite group giveIf $N{\alpha }^2\ge 2$, then $\alpha <1$ for a cap set andThus some nonzero finite abelian Fourier coefficient has magnitude at least ${\alpha }^2/2$.

For this $\xi$, let ${\alpha }_j$ be the subset density of $A$ on the affine subspace $\{x:\xi \cdot x=j\}$, for $j=0,1,2$. These three affine subspaces have equal cardinality, andAmong three directions separated by $2\pi /3$, one makes an angle at most $\pi /3$ with any given complex number. Hence ${\max }_j({\alpha }_j-\alpha )\ge |\hat{f}(\xi )|$. Restricting to that hyperplane gives the hyperplane density increment for cap setsTranslate the affine subspace to its underlying vector space. This preserves the cap set property: translating a triple by $t$ changes its sum by $3t=0$. The same argument can therefore be iterated.

For completeness, the density increment iteration gives an explicit uniform bound. If $n<16$, the hypothesis $\alpha \ge 16/n$ is impossible. Suppose $n\ge 16$ and a cap set has ${\alpha }_0\ge 16/n$. For every integer $0\le t\le \lfloor n/2\rfloor$, its remaining dimension is at least $n/2$, and its current subset density is at least $16/n$. ThusThe last inequality holds at $n=16$ and remains true as $n$ increases: the successive ratio of $3^{n/2}/n^2$ is $\sqrt{3}(n/(n+1){)}^2>1$ for $n\ge 16$. At each step, as long as the subset density remains at most one,After $L=\lfloor n/2\rfloor$ steps this would implya contradiction. The endpoint $\alpha =1$ already contradicts the cap set property in positive dimension. This proves the claimed existence of three distinct points and the Meshulam bound for cap sets.

Use uniform expectations on the two nonempty parts, and equip their function spaces with the inner product $⟨u,v⟩=\mathbb{E}\overline{u}v$. Let $H=G-\gamma$ andSince the bipartite graph is a biregular graph, both row and column averages of $H$ vanish. The normalized adjacency operator of a bipartite graph therefore splits into the map between constant functions, of singular value $\gamma$, and $T_H$ between their orthogonal complements.

There is no singular value larger than $\gamma$. Indeed, for $\gamma >0$, the Cauchy-Schwarz inequality givesAveraging in $x$ uses the constant column degree and gives $\Vert {\theta }_{G}v{\Vert }_2\le \gamma \Vert v{\Vert }_2$. For $\gamma =0$ every operator is zero. Thus the second singular value isIf one part has a single vertex, missing singular values are interpreted as zero; the biregular graph then has $H=0$.

The discrepancy in (i) is exactly $\mathbb{E}H{1}_A{1}_B$. Its supremum over $A,B$ is the cut norm $\delta =\Vert H{\Vert }_{\mathrm{cut}}$. To pass from this bound to arbitrary bounded real-valued functions, use the positive and negative parts and the identity $u_{+}(x)={\int }_0^M{1}_{\{u(x)>t\}}dt$ for $|u|\le M$. Applying this separately to both factors givesHere $N$ is a bound on $v$, unrelated to any cardinality.

If $s>0$, take real unit left singular vector $u$ and right singular vector $v$ with $T_{H}v=su$ and $T_H^{\ast }u=sv$. The Cauchy-Schwarz inequality and $|H|\le 1$ imply $\Vert u{\Vert }_{\infty },\Vert v{\Vert }_{\infty }\le 1/s$. HenceThis proves (i)$\Rightarrow$(iii), with a constant independent of both part sizes. The case $s=0$ satisfies the same conclusion immediately.

Write $\mathfrak{c}=2^{{\aleph }_0}$. Its cofinality is ${\aleph }_1$, so choose a strictly increasing sequence of infinite cardinal numbers $({\kappa }_{\xi }{)}_{\xi <{\omega }_1}$ below $\mathfrak{c}$ with supremum $\mathfrak{c}$. Such a sequence is obtained by refining a cofinal sequence and choosing larger cardinals recursively; $\mathfrak{c}$ is a singular cardinal, hence a limit cardinal.

By the axiom of choice, fix a bijection $b:\mathfrak{c}\to \mathbb{R}$. SetEvery $A_{\xi }$ is infinite, $|A_{\xi }|={\kappa }_{\xi }<\mathfrak{c}$, and distinct indices give distinct cardinalities. The cofinality of the sequence ensuresThus $|\mathcal{A}|={\aleph }_1$. Pairwise different sizes means different sizes for distinct members; without that qualification the parenthetical condition would contradict the case $A=B$.

The Freiling theorem givesFirst assume the Continuum hypothesis and fix a well-order $(r_{\alpha }{)}_{\alpha <{\omega }_1}$ of the real numbers. Define $f(r_{\alpha })=\{r_{\beta }:\beta \le \alpha \}$. Each value is countable. For any pair, one index is at most the other, so at least one of $x\in f(y)$ or $y\in f(x)$ holds. The same holds for $x=y$, since $x\in f(x)$. This violates the Freiling axiom of symmetry.

Conversely, assume $|\mathbb{R}|>{\aleph }_1$ and let $f$ assign a countable set to each real. Choose $X\subseteq \mathbb{R}$ of cardinality ${\aleph }_1$. By infinite cardinal arithmetic,Choose $y$ outside this union. Since $f(y)$ is countable and $X$ is uncountable, choose $x\in X\setminus f(y)$. Then $y\notin f(x)$ and $x\notin f(y)$, with $x\ne y$. This proves the Freiling axiom of symmetry and completes both implications.

The cardinal bound for an increasing chain of countable sets is $\boxed{|X|\le {\aleph }_1}$. If $X$ is countable, there is nothing to prove. Otherwise choose $Y\subseteq X$ with $|Y|={\aleph }_1$, and for every $y\in Y$ choose an index $i(y)$ such that $y\in X_{i(y)}$.

For any $i\in I$, its countable $X_i$ cannot contain all of $Y$, so choose $y\in Y\setminus X_i$. Since $I$ is a linear order, comparison of $i$ and $i(y)$ forces $i<i(y)$: the other direction would imply $y\in X_i$. Therefore $X_i\subseteq X_{i(y)}$. The selected family is cofinal among the original sets, andBy infinite cardinal arithmetic, this union of ${\aleph }_1$ countable sets has cardinality at most ${\aleph }_1$. No well-order or cofinality assumption on $I$ was used; a linear increasing union of countable sets has the same bound even for an arbitrary linear index order.

The continuum hypothesis holds. Let $A$ be the assumed Lusin set of cardinality $\mathfrak{c}=2^{{\aleph }_0}$. If $\mathfrak{c}>{\aleph }_1$, choose $B\subseteq A$ with $|B|={\aleph }_1$. The size assumption makes $B$ a meagre set, but then $A\cap B=B$ is uncountable, contradicting the Lusin set property. ThusOne can also use (d) directly: well-order $A$ in type $\mathfrak{c}$. Each proper initial segment has size below $\mathfrak{c}$, so is meagre and consequently countable, since it is a subset of the Lusin set. These initial segments form a linear increasing union of countable sets equal to $A$. The bound in (d) gives $\mathfrak{c}\le {\aleph }_1$.

A witness to failure of the Axiom of power set is $\boxed{{\omega }_1\in H_{{\omega }_2}}$. Every subset $A\subseteq {\omega }_1$ belongs to $H_{{\omega }_2}$, since its transitive closure has cardinality at most ${\aleph }_1$. If some $p\in H_{{\omega }_2}$ were the internal power set of ${\omega }_1$, transitivity and bounded subsethood would force $p$ to contain every ambient subset of ${\omega }_1$, and only those subsets. Thus it would be the full $\mathcal{P}({\omega }_1)$.

By the Cantor theorem,Its transitive closure contains all its members, so $|\mathrm{tc}(\{p\})|\ge |p|\ge {\aleph }_2$. This contradicts $p\in H_{{\omega }_2}$. ThereforeThe power-set failure in hereditarily small sets needs no assumption about the Continuum hypothesis.

Work in positive dimension $n\ge 1$. A cap set has no distinct zero-sum triple. Over the finite field ${\mathbb{F}}_3$, if two elements of a zero-sum triple agree then all three agree, since $2=-1$. Thus a zero-sum triple in a cap set must be diagonal. We prove the Ellenberg–Gijswijt cap-set bound by the polynomial method in combinatorics, keeping the exponential constant explicit and removing the fixed prefactor.

First prove the needed slice rank of a diagonal tensor over any field. The slice rank of a three-variable tensor is the least number of terms in a decomposition of the forms $a(x)b(y,z)$, $c(y)d(x,z)$, and $e(z)h(x,y)$. A diagonal tensor on a set of cardinality $m$, with every diagonal entry nonzero, has slice rank at most $m$ by one slice for each entry. For the reverse inequality, suppose a decomposition has $r$ slices in the $x$ direction, $s$ in the $y$ direction, and $t$ in the $z$ direction, with $r+s+t<m$. LetThe rank-nullity theorem gives $\dim W\ge m-r$. The maximum-support vector in a finite-dimensional subspace lemma supplies $u\in W$ with at least $m-r$ nonzero coordinates: choose $u$ of maximum support of a vector; restriction $W\to F^{\mathrm{supp}u}$ must be injective, or adding a nonzero kernel of a linear map element would strictly enlarge that support of a vector. This argument is valid over finite fields, without any assumption that a generic vector avoids all coordinate hyperplanes.

Contract the proposed tensor decomposition in $x$ against $u$. The diagonal tensor becomes a diagonal matrix of matrix rank at least $m-r$. All $x$ slices vanish. Each remaining $y$ or $z$ slice becomes a matrix of matrix rank at most one, so subadditivity of matrix rank gives matrix rank at most $s+t<m-r$, a contradiction. Therefore the slice rank of a diagonal tensor is exactly $m$.

Now, for a cap set $A\subseteq {\mathbb{F}}_3^n$, consider the polynomialEach factor is one when its argument is zero and zero otherwise, because the two nonzero elements of ${\mathbb{F}}_3$ have square one. Thus $P$ is the indicator function of $x+y+z=0$. Restricted to $A^3$, it is a diagonal tensor with every diagonal entry one, and its slice rank is $|A|$.

Every monomial in the expansion has individual exponents at most two and total polynomial degree at most $2n$. Consequently at least one of its $x$, $y$, or $z$ blocks has polynomial degree at most $\lfloor 2n/3\rfloor$. Assign each monomial to one such block, breaking ties in a fixed way, and collect assigned terms by the monomial in that block. Each collection is a slice. Ifthere are at most $m_n$ slices in each direction. Thus $|A|\le 3m_n$.

The low-degree monomial count for the cap-set bound follows directly from a weighted sum. Each exponent vector counted by $m_n$ satisfies $1\le 2^{2n/3-{\sum }_i{a}_i}$, soThis supplies its own elementary exponential estimate; no unstated probabilistic estimate is required. Since ${\theta }^3=343/16<27$, we have $\theta <3$, but $|A|\le 3{\theta }^n$ alone would leave a fixed prefactor.

Use Cartesian powers of cap sets to remove that prefactor. The $k$-fold Cartesian product $A^k\subseteq {\mathbb{F}}_3^{nk}$ is still a cap set: in each block, a zero-sum triple of its elements must have all three entries equal. Hence $|A{|}^k\le 3{\theta }^{nk}$. Taking $k$th roots and letting $k$ tend to infinity proves the removal of an exponential prefactor by Cartesian powers:The strict middle inequality follows by cubing: $343/16<(14/5{)}^3$. We can therefore takeFor every $n\ge 1$, a set with $|A|\ge C^n$ cannot be a cap set, and hence contains the required distinct triple. If zero dimension were included, the singleton ${\mathbb{F}}_3^0$ would be another small-case exception; positive dimension is the convention used here.

Zorn lemma states that a partially ordered set in which every chain in a partially ordered set has an upper bound has a maximal element. Include the empty chain in a partially ordered set, so the hypotheses imply that the set $P$ is nonempty. Suppose there were no maximal element. Every chain in a partially ordered set $C$ has an upper bound $u$, and some $v>u$; therefore the set of elements strictly above every member of $C$ is nonempty. The axiom of choice selects one such element $f(C)$ for each chain in a partially ordered set (and an element of $P$ when $C$ is empty).

By Hartogs theorem, there is an ordinal $\kappa$ which does not inject into $P$. Transfinite recursion defines $x_{\alpha }=f(\{x_{\beta }:\beta <\alpha \})$ for all $\alpha <\kappa$: previous elements form a strictly increasing chain in a partially ordered set, including at limit ordinal stages. All $x_{\alpha }$ are distinct, giving the forbidden injection. This proves Zorn lemma; the choice of $f$ is the use of the axiom of choice.

Apply Zorn lemma to linearly independent subsets of $\mathbb{R}$ over $\mathbb{Q}$, ordered by inclusion. A union along a chain in a partially ordered set is linearly independent because each finite linear relation occurs in one member of that chain in a partially ordered set. A maximal independent set spans $\mathbb{R}$, since a vector outside its span could be adjoined. Thus $\mathbb{R}$ has a Hamel basis over $\mathbb{Q}$.

For a finite basis, the Steinitz exchange lemma proves equality of basis sizes. This also rules out an infinite basis when a finite spanning set exists: write each member of the finite spanning set using finitely many elements of another basis; their finite union spans, and independence leaves no other basis elements. If a basis $B$ is infinite with cardinality $\lambda$, the finite-support description of every vector and countability of $\mathbb{Q}$ giveHere infinite cardinal arithmetic uses the axiom of choice. Thus any infinite basis has cardinality $|V|$, proving all bases have the same cardinality. The zero space has its unique empty basis.

We use the abacus divisible-hook correspondence in its multiset form: the hook lengths of $\lambda$ that are divisible by $p$, divided by $p$, form exactly the disjoint union of the multisets of hook lengths of the components of its quotient of a partition for modulus $p$.

Iterating this correspondence gives, for every $r\ge 1$,as multisets. Each Young diagram has one hook for every cell, so the cardinality of the right-hand side is $|T^Q(\lambda {)}_r|$, the sum of the component sizes.

For any positive integer $h$, its P-adic valuation is the number of positive $r$ for which $p^r\mid h$. Summing this identity over hooks and interchanging the finite sums provesThusThe sums are finite because hook lengths are bounded by $|\lambda |$, and the total size at each level of the quotient tower of a partition decreases by at least a factor $p$ until it reaches zero.