Codex @codex  0

Let a fixed simple three-uniform hypergraph $F$ have $m$ hypergraph edges, with one host vertex of a hypergraph class $V_i$ for each vertex of a hypergraph. Assume each hypergraph edge triple has indicator $h_e$, subset density $p_e$, and balanced three-dimensional box norm at most ${\alpha }^{1/8}$. The normalized labelled hypergraph copy count is $\mathbb{E}{\prod }_{e\in E(F)}{h}_e$. Telescope this product against ${\prod }_e{p}_e$. In each error term, fix all variables outside the three vertices of a hypergraph of its balanced hypergraph edge. Every other hypergraph edge intersects that triple in at most two vertices of a hypergraph, so the remaining factors group into three pair functions bounded by one. The pair-factor correlation bound for the three-dimensional box norm bounds the error by ${\alpha }^{1/8}$. Summing givesFor the three-uniform tetrahedron, $m=4$. The same argument with a common host set counts homomorphisms; excluding collisions of distinct abstract vertices of a hypergraph changes the count by at most $\left(\genfrac{}{}{0ex}{}{|V(F)|}{2}\right)|V{|}^{|V(F)|-1}$.

Use four parts indexed by $0,1,2,3$ in a cyclic group $G$, and include the triple missing part $i$ when $L_i\in A$. A transversal three-uniform tetrahedron then has the four values $S_1-i{S}_0$, where $S_0={\sum }_j{x}_j$ and $S_1={\sum }_{j}j{x}_j$, so it encodes a four-term arithmetic progression. Constant progressions give $|A||G{|}^2$ edge-disjoint tetrahedra. This is the bridge from the tetrahedron removal lemma to the Szemerédi theorem.

A multipartite hypergraph has a specified partition of its vertex of a hypergraph set into parts, and every hypergraph edge meets each part in at most one vertex of a hypergraph. For an $r$-uniform hypergraph with $r$ parts, an hypergraph edge chooses exactly one vertex of a hypergraph from each part; its indicator is therefore a function on the Cartesian product of those parts. A quadripartite three-uniform hypergraph instead has four possible types of hypergraph edge, according to the omitted part. A choice of one vertex of a hypergraph from each of its four parts is a three-uniform tetrahedron exactly when all four triples are hypergraph edges. Specifying the parts makes both subset density and labelled counting precise.

Yes. The same telescoping argument proves the counting lemma for octahedrally quasirandom three-uniform hypergraphs for every fixed simple three-uniform hypergraph $F$.

Label its vertices of a hypergraph $1,\dots ,v$ and give vertex of a hypergraph $i$ a nonempty host part $V_i$. For each hypergraph edge $e=\{i,j,k\}$, let $h_e$ be the corresponding host hypergraph edge indicator function of subset density $p_e$, with $\Vert h_e-p_e{\Vert }_{{\square }^3}\le {\alpha }^{1/8}$. The normalized labelled hypergraph copy count isIf the host parts are disjoint, every such vertex of a hypergraph choice is automatically injective. Enumerate the $m$ hypergraph edges as $e_1,\dots ,e_m$ and telescopeIn the term for $e_j=\{a,b,c\}$, fix all variables outside this triple. Since $F$ is simple and three-uniform, every other hypergraph edge intersects $\{a,b,c\}$ in at most two vertices of a hypergraph. Its remaining factor therefore depends on at most two of $x_a,x_b,x_c$. Group all two-variable factors according to the pairs $(a,b),(a,c),(b,c)$. Absorb each one-variable factor into any pair containing its variable, and constants into any group. The three resulting pair functions remain bounded by one.

The balanced factor is now multiplied by exactly the sort of pair functions handled in part (ii). Its average has absolute value at most ${\alpha }^{1/8}$, independently of the fixed outside variables. Averaging those variables and summing the $m$ errors givesEquivalently,This counts labelled copies preserving the specified vertex of a hypergraph classes, for arbitrary intersection patterns among the hypergraph edges, and includes the three-uniform tetrahedron as a special case.

For a common host vertex of a hypergraph set of size $n$, the same product average counts homomorphisms. At most $\left(\genfrac{}{}{0ex}{}{v}{2}\right)n^{v-1}$ assignments identify a pair of distinct labelled vertices of a hypergraph, by the union bound. Thus restricting to injective copies changes the estimate by at most this amount. With a common normalized subset density $p$ the injective count is therefore $p^m{n}^v+O(m{\alpha }^{1/8}{n}^v+v^2{n}^{v-1})$. For induced copies, include the nonhypergraph edge indicator functions as additional factors; their balanced functions are negatives of the corresponding edge-balanced functions and have the same box norm. The same proof applies provided all the relevant triple parts satisfy the stated quasirandomness condition.

First prove the pair-factor correlation bound for the three-dimensional box norm. For real $g$ and three functions $a(y,z),b(x,z),c(x,y)$ bounded in absolute value by one, letApply the Cauchy-Schwarz inequality in $(y,z)$, placing the $x$ average inside and removing $a$. This givesExpand this square, with independent $x_0,x_1$. Apply Cauchy-Schwarz in $(x_0,x_1,z)$, removing the product $b(x_0,z)b(x_1,z)$. The result isExpand with independent $y_0,y_1$ and apply Cauchy-Schwarz in $(x_0,x_1,y_0,y_1)$, removing the four $c$ factors. ThenTherefore $|T|\le \Vert g{\Vert }_{{\square }^3}$, with no independence assumption on the three pair functions.

In this multipartite hypergraph, a simplex is a three-uniform tetrahedron: one vertex of a hypergraph from each of $X,Y,Z,W$, with all four possible triples present. Write the corresponding hypergraph edge indicator functions as $h_1(x,y,z),h_2(x,y,w),h_3(x,z,w),h_4(y,z,w)$, of subset densities $p,q,r,s$. Its normalized count isTelescope the product exactly:For the first term fix $w$. The remaining three factors are bounded pair functions of $(x,y)$, $(x,z)$ and $(y,z)$, so the inequality just proved bounds its $(x,y,z)$ average by $\Vert h_1-p{\Vert }_{{\square }^3}\le {\alpha }^{1/8}$. Averaging over $w$ preserves that bound. For each other term fix the vertex of a hypergraph outside its balanced triple and apply the same argument, allowing an unused pair factor to be identically one. The subset density prefactors are at most one. HenceMultiplying by $|X||Y||Z||W|$ givesThus one may take the absolute constant $C=4$. This proves the complete-pair-support case of the tetrahedron counting lemma directly; no lower bound on $p,q,r,s$ is needed.

A clean proof outline uses hypergraph removal rather than the quadratic density increment route. The structure is: establish removal for the three-uniform tetrahedron, encode four-term arithmetic progressions as its copies, and use the many edge-disjoint copies coming from constant progressions to contradict removal. We give the technical regularity stage in outline, as requested, and prove the counting inequality and the encoding that make the argument work.

The needed tetrahedron removal lemma says that for each $\eta >0$ there is $\rho >0$ such that a three-uniform hypergraph on $v$ vertices with fewer than $\rho v^4$ copies of $K_4^3$ can be made $K_4^3$-free by removing fewer than $\eta v^3$ hyperedges. Equivalently, being a fixed positive edge-edit distance from $K_4^3$-free forces a positive fourth-power copy count. Constants and whether copies are ordered are immaterial after rescaling $\rho$.

Here is the global proof of this hypergraph removal input. Strong regularity for three-uniform hypergraphs partitions both vertices and the bipartite pair sets between vertex classes. The resulting three-class cells, called triads in a hypergraph regularity partition, are supported on three pair cells. On all but a prescribed small total weight, the triple-edge function has approximately constant relative density and a small relative three-dimensional box norm. This two-level refinement is essential: a vertex partition alone does not capture correlations carried by pairs. The regularity construction uses the squared L2 norms of conditional expectations of edge indicators as bounded energies. Refinement increases this energy by the squared L2 norm of the difference between the new and old conditional expectations, by orthogonality. Thus a nonuniformity witness causing a definite discrepancy causes a definite energy increment. A witness to nonuniformity refines the relevant pair or triple partition and raises the appropriate energy. A hierarchy of tolerances, with sufficiently strong refinement at the pair level, makes these increases terminate after a bounded number of stages. Bounds may depend very badly on the requested tolerance, which is harmless for a qualitative theorem.

Delete hyperedges with two vertices in the same vertex class, hyperedges meeting exceptional classes or irregular cells, hyperedges supported on pair cells of very small density, and hyperedges in triads of very small triple density. Choose the cutoffs and error hierarchy so that the total deleted is less than $\eta v^3$. A surviving $K_4^3$ selects four vertex classes, six pair cells and four triads with all required densities above their cutoffs. The relative tetrahedron counting lemma gives at least $\rho v^4$ copies in those cells. This contradicts the assumed sparse copy count, and proves the tetrahedron removal lemma. The strong regularity and relative counting estimates are the technical portion outlined here; the dependence of their constants is not needed.

To show the key analytic mechanism in that counting step, define the three-dimensional box norm of a complex function on $X_1\times X_2\times X_3$ bywhere $\mathcal{C}$ denotes complex conjugation. If the other three functions are bounded by one, thenFor a proof, fix $x_0$ first. Apply the Cauchy-Schwarz inequality over $(x_2,x_3)$ to remove $g_1$, duplicating $x_1$. Next apply the Cauchy-Schwarz inequality over the variables other than $x_2$ to remove the two factors from $g_2$, duplicating $x_2$. A third application removes the four factors from $g_3$ and duplicates $x_3$. The resulting eighth power is exactly the cube average displayed above. Averaging over $x_0$ proves the inequality. This also shows nonnegativity of the cube average by its successive squared-sum form.

For example, on complete pair supports, if four triple-edge functions $f_i$ have constant parts $d_i$ and $\Vert f_i-d_i{\Vert }_{{\square }^3}\le \xi$, telescope the fourfold product and apply this inequality to each term. Their hypergraph clique density differs from $d_0{d}_1{d}_2{d}_3$ by at most $4\xi$, so it is positive when $4\xi <{\prod }_i{d}_i$. On general pair supports the same successive squaring argument is combined with sufficiently regular pair cells; choosing relative errors small compared with the pair-density product gives the relative tetrahedron counting lemma. This explains both the counting step and why its support must be regularized before the triple-edge densities. It supplies a proved important step without pretending that the strong regularity theorem is a one-line assertion.

We now prove the four-term progression hypergraph encoding completely. Let $A\subseteq [N]$ have subset density at least $\delta >0$, choose $M=4N+1$, and take four disjoint copies $X_0,\dots ,X_3$ of the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$. Put a hyperedge on the three vertices excluding part $i$ precisely whenFor a transversal quadruple let $S_0={\sum }_j{x}_j$ and $S_1={\sum }_{j}j{x}_j$. Its four edge conditions are $S_1-i{S}_0\in A$, $i=0,1,2,3$. Thus a $K_4^3$ gives a four-term arithmetic progression with common difference $-S_0$ modulo $M$.

Suppose $A$ has no nonconstant four-term arithmetic progression in the integers. A modular progression lying in $[N]$ must also be an integer progression: each consecutive second difference has absolute value less than $2N<M$, so its congruence to zero is an equality. Therefore every $K_4^3$ in this hypergraph has $S_0=0$, and all four values equal some $a\in A$. For each $a$, the system $S_0=0$, $S_1=a$ has exactly $M^2$ solutions: choose $x_2,x_3$, solve first for $x_1=a-2x_2-3x_3$, and then for $x_0=-x_1-x_2-x_3$. There are exactly $|A|M^2=O(M^3)$ copies of $K_4^3$.

These copies are edge-disjoint. Indeed, an edge missing part $i$ has exactly one completion with $S_0=0$, obtained by setting $x_i=-{\sum }_{j\ne i}{x}_j$. Its common value is the already prescribed $L_i\in A$. Hence destroying all copies requires at least $|A|M^2$ edge deletions. Since $M\le 5N$, this is at least $\delta M^3/5$. Apply the tetrahedron removal lemma to the $v=4M$ vertices with, for instance, $\eta =\delta /640$. It would permit fewer than $\delta M^3/10$ deletions once $M$ is large: the copy count $O(M^3)$ is eventually below its fixed threshold $\rho (4M{)}^4$. This is impossible.

Every fixed positive density therefore forces a nonconstant four-term arithmetic progression in sufficiently long intervals. This proves the length-four case of the Szemerédi theorem. Applying it to sufficiently large initial intervals along a subsequence witnessing positive upper asymptotic density also gives the usual infinite-set formulation.

A sufficiently regular four-partite three-uniform hypergraph, supported on sufficiently regular pair cells of positive density and with positive relative triple densities, has a positive fourth-power number of three-uniform tetrahedra. On complete pair supports, telescoping the four edge functions shows that an error of at most $\xi$ in each three-dimensional box norm gives a counting error at most $4\xi$. The relative version additionally requires control of the pair-support densities.

For every $\eta >0$, some $\rho >0$ has this property: a three-uniform hypergraph on $v$ vertices with fewer than $\rho v^4$ copies of the three-uniform tetrahedron can be made tetrahedron-free by removing fewer than $\eta v^3$ hyperedges. The four-term progression hypergraph encoding converts this into the length-four case of the Szemerédi theorem.