gpt 6 astra ultra attempt on Math-498

Ruzsa-Szemeredi $6,3$ Extremal-Order Problem

Definitions and mathematical statement

A simple three-uniform hypergraph on an $n$-element vertex set has distinct three-element subsets as edges. Define \[ f(n,6,3)=\max\{|E(H)|:\ |V(H)|=n, \ \forall U\subseteq V(H),\ |U|\le6, \ \#\{e\in E(H):e\subseteq U\}\le2\}. \] Determine its asymptotic order as $n\to\infty$, meaning matching upper and lower bounds on the actual extremal scale, rather than merely a quadratic-order exclusion. The condition forbids any three edges whose union has at most six vertices; it applies to all such configurations, not just a visually triangular arrangement. No multiplicities are allowed among edges.

Formulation and concept references: [S1].

Short English statement

How many triples can a large vertex set support when no collection of at most six vertices contains three of them?

Research attempt

Scope, source audit, and attack plan.

This attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. The target is the actual extremal scale of $f(n,6,3)$, including its subpolynomial factor. Establishing only $n^{2-o(1)}\leq f(n,6,3)=o(n^2)$ does not answer it. The introduction of Gowers--Janzer [S1] records those classical bounds and the triangle interpretation. The 2025 paper at [S2] proves a power saving with a larger forbidden vertex parameter; its Theorem 1.3 concerns $f(n,e+\lfloor\log_2 e\rfloor+38,e)$. Substituting $e=3$ does not give an upper bound of order $n^{2-\varepsilon}$ for the present problem. Such a bound would contradict the construction below. No matching-order theorem for the present parameter pair was located in the consulted sources.

The proof track first removes nonlinearity exactly, then examines a spectral obstruction to pseudorandomness in the associated graph. The construction track tests an arithmetic family against all forbidden three-edge patterns. The familiar progression-free construction is included with a complete verification to calibrate possible upper bounds; it is not a claim of a new extremal construction. The remaining issue is quantitative global structure, rather than detecting one local triangular pattern.

Lemma 494.1: an exact decomposition, including the non-linear edges.

Let $L(n)$ be the maximum number of edges in a linear $(6,3)$-free three-uniform hypergraph on $n$ vertices; linear means that different edges intersect in at most one vertex. Put $L(0)=L(1)=L(2)=0$. Then \begin{equation}\label{wsref-0-61-34-39-34-3a-64-65-63-6f-6d-70-6f-73-69-74-69-6f-6e} f(n,6,3)=\max_{0\leq k\leq\lfloor n/4\rfloor} \left(2k+L(n-4k)\right). \end{equation} In particular $L(n)\leq f(n,6,3)\leq L(n)+n/2$.

Proof. Suppose two distinct edges $e_1,e_2$ share two vertices. Their union $W$ has four vertices. Any third edge meeting $W$ would have union of size at most $4+3-1=6$ with the first two edges, which is forbidden. Thus these two edges form an isolated component on exactly four vertices. Every such component is disjoint from every other one. After removing its $k$ four-vertex components of this kind, the hypergraph has $n-4k$ vertices and is linear. This proves the upper bound in (a494:decomposition).

Conversely, take a linear admissible hypergraph on $n-4k$ vertices and adjoin $k$ disjoint copies of the two triples $\{1,2,3\}$ and $\{1,2,4\}$. Three edges in the old component remain admissible. Three edges meeting more than one component either include two edges whose union has at least four vertices and a disjoint triple, or are three disjoint triples. Their union therefore has at least seven vertices. A new four-vertex component has only two edges. The union is admissible, proving the other inequality. Finally $L(n-4k)\leq L(n)$ by adjoining isolated vertices, and $2k\leq n/2$.$\square$

This reduction avoids a tempting but false preliminary assertion that every admissible hypergraph is linear. The two triples just displayed are an explicit counterexample to that assertion. Linearity is obtained after a controlled loss, and the exact formula records that loss.

Lemma 494.2: the triangle model is equivalent after that reduction.

The quantity $L(n)$ equals the maximum number of triangles in an $n$-vertex simple graph in which every edge belongs to exactly one triangle. Isolated vertices are allowed.

Proof. Replace each hyperedge of a linear admissible hypergraph by its three pairs, producing a graph $G$. Each pair occurs in exactly one of the designated triangles. Suppose $abc$ is another triangle. The hyperedges containing $ab,bc,ca$ must be distinct: if one contained two of these pairs, it would be the triple $abc$, and uniqueness of pairs would force all three designated hyperedges to be this same triple. The three distinct hyperedges have union inside $\{a,b,c\}$ plus their three remaining vertices, a forbidden set of size at most six. There are no extra triangles.

For the converse, take the triangles of such a graph as hyperedges. They are linear because an edge of the graph cannot lie in two triangles. For three distinct linear triples, inclusion--exclusion gives \[ |e_1\cup e_2\cup e_3| =9-\sum_{i<j}|e_i\cap e_j|+|e_1\cap e_2\cap e_3|. \] The union has at most six vertices only if all three pairwise intersections are singletons and the triple intersection is empty. The three intersection vertices are then distinct and form an additional graph triangle. Each of its edges is already in one of the three original triangles, a contradiction. This proves both directions.$\square$

If the graph has $m$ triangles, it has exactly $3m$ edges. Therefore $m\leq\binom n2/3$. Every vertex neighborhood induces a perfect matching: each neighbor $u$ of $v$ is paired with the unique third vertex of the triangle containing $uv$, and any further adjacency within the neighborhood would put $uv$ in another triangle. In particular all degrees are even. These local facts will be used as checks, not as a substitute for the global extremal estimate.

Construction track: a fully checked arithmetic family.

Let $A\subseteq\{1,\ldots,N\}$ have no nonconstant three-term arithmetic progression. Use three disjoint labelled vertex classes \[ X=\{1,\ldots,N\},\quad Y=\{1,\ldots,2N\},\quad Z=\{1,\ldots,3N\}, \] and for every $(x,a)\in X\times A$ insert the triple \begin{equation}\label{wsref-0-61-34-39-34-3a-61-72-69-74-68-6d-65-74-69-63} (x,x+a,x+2a)\in X\times Y\times Z. \end{equation} The labels distinguish the classes even when integer values agree. There are exactly $N|A|$ distinct triples on $6N$ vertices. Any two coordinates determine $x$ and $a$, so the hypergraph is linear.

To check the forbidden configuration condition without assuming that it is already a triangular one, consider the shadow graph from Lemma 494.2. Every triangle must use one vertex from each class. Its three pair edges imply that \[ a=y-x\in A,\qquad b=z-y\in A,\qquad c=(z-x)/2\in A. \] Hence $a+b=2c$. Progression-freeness implies $a=b=c$, and the triangle is one of (a494:arithmetic). Each pair is in just one such triangle. Lemma 494.2 now checks every collection of three hyperedges, including degenerate intersection patterns. We have proved the exact finite bound \begin{equation}\label{wsref-0-61-34-39-34-3a-72-33} f(6N,6,3)\geq L(6N)\geq N r_3(N), \end{equation} where $r_3(N)$ is the largest size of a progression-free subset of $[N]$. This is a lower bound; the argument supplies no reverse inequality comparing arbitrary admissible hypergraphs with subsets of an interval.

Here is an explicit version of the geometric digit construction behind a large $A$. For integers $k,d\geq2$, partition $\{0,\ldots,k-1\}^d$ by the value of $\sum_i v_i^2$. One fiber $V$ has \[ |V|\geq\frac{k^d}{d(k-1)^2+1}. \] On a fixed sphere, $u+w=2v$ implies $u=v=w$: expanding the squared norms gives $\|u-w\|^2=0$. Map the fiber into integers by \[ v\longmapsto 1+\sum_{i=0}^{d-1}v_i(2k)^i. \] Its values lie in $[1,(2k)^d]$. In an equation between the sum of two such values and twice a third, all digit sums are at most $2k-2<2k$. There are no carries, so equality of integers gives equality of digit vectors. The image is therefore progression-free. In particular, writing $N_0=(2k)^d$, \begin{equation}\label{wsref-0-61-34-39-34-3a-64-69-67-69-74-62-6f-75-6e-64} \frac{|A|}{N_0}\geq \frac{2^{-d}}{d(k-1)^2+1}. \end{equation}

For arbitrary sufficiently large $N$, put $d=\lfloor\sqrt{\log N}\rfloor$ and $k=\lfloor N^{1/d}/2\rfloor$. Then $(2k)^d\leq N$ and, for large $N$, $k\geq N^{1/d}/3$. Consequently \[ |A|\geq\frac{N3^{-d}}{dN^{2/d}+1} \geq N\exp(-C\sqrt{\log N}) \] for an absolute $C$. All logarithms here are natural. Using $N=\lfloor n/6\rfloor$ and adding isolated vertices yields \begin{equation}\label{wsref-0-61-34-39-34-3a-6c-6f-77-65-72} f(n,6,3)\geq n^2\exp(-C'\sqrt{\log n}) \end{equation} for all sufficiently large $n$. The exponent loss is $o(\log n)$, so any proposed upper bound $O(n^{2-\varepsilon})$ with fixed $\varepsilon>0$ fails this stress test. Constants may change between displays.

Proof track: why qualitative removal does not determine the scale.

The triangle removal lemma asserts that for every $\eta>0$ there is $\delta(\eta)>0$ such that a graph with at most $\delta(\eta)n^3$ triangles can be made triangle-free by deleting at most $\eta n^2$ edges. This is the external theorem used here; [E1] is a primary proof. In the graph of Lemma 494.2, exactly $m$ deletions are necessary and sufficient: the $m$ triangles are edge-disjoint, and deleting one edge from each kills all of them.

Fix $\varepsilon>0$. If $m\geq\varepsilon n^2$, use removal with $\eta=\varepsilon/2$. Since $m\leq n^2/6$, we have $m/n^3\leq1/(6n)<\delta(\varepsilon/2)$ for sufficiently large $n$. Removal would require at most $\varepsilon n^2/2<m$ deletions, a contradiction. Thus $L(n)=o(n^2)$, and Lemma 494.1 gives the same for $f(n,6,3)$. This recovers a classical conclusion, not the requested matching asymptotic estimate.

The quantitative dependence has not vanished. If $\alpha=m/n^2>0$, the same reasoning only forces \[ \delta(\alpha/2)<\alpha/n \] with the convention using a non-strict triangle threshold. To turn this into a proposed bound on $\alpha$, one must supply and invert an actual function $\delta$. Replacing it by a polynomial without proof would be especially damaging: this would conflict with the family (a494:lower). The procedure cannot simply infer the desired rate from the fact that a positive $\delta$ exists.

Lemma 494.3: dense triangle systems force a large secondary eigenvalue.

Let $G$ have $n\geq2$ vertices, every edge in exactly one triangle, and $m>0$ triangles. Let $\lambda_1\geq\cdots\geq\lambda_n$ be the real eigenvalues of its adjacency matrix, and set $\Lambda=\max_{2\leq i\leq n}|\lambda_i|$. Then \begin{equation}\label{wsref-0-61-34-39-34-3a-73-70-65-63-74-72-61-6c} \Lambda\geq\frac{36m^2}{n^3}-1. \end{equation}

Proof. An adjacency matrix has $\operatorname{tr}(A^2)=2|E(G)|=6m$ and $\operatorname{tr}(A^3)=6\#K_3(G)=6m$, by counting closed walks of length two and three. Its largest eigenvalue is at least the average degree, by the Rayleigh quotient at the all-ones vector: $\lambda_1\geq6m/n$. For $i\geq2$, $\lambda_i^3\geq-\Lambda\lambda_i^2$. Consequently \[ 6m=\sum_i\lambda_i^3 \geq\lambda_1^3-\Lambda\sum_{i\geq2}\lambda_i^2 \geq\lambda_1^3-6m\Lambda. \] Divide by $6m$ and use the Rayleigh bound.$\square$

For $m=\alpha n^2$, this gives $\Lambda\geq36\alpha^2 n-1$. In particular a hypothetical dense family with every nonprincipal eigenvalue $o(n)$ is impossible. This is a structural restriction with an elementary proof, but it is consistent with the arithmetic construction: the latter is highly structured and its density tends to zero. The estimate does not yield a contradiction for a slowly decreasing $\alpha(n)$.

A contemplated next step was to use a large eigenvector to find a denser induced subsystem and iterate. Here is the first missing assertion: a spectral cut must retain enough whole triangles, with a quantitatively controlled density gain, to repeat the argument. A cut can retain edges whose unique completing vertex was discarded. Those edges must then be removed; their number is not controlled by (a494:spectral). A density increment for graph edges by itself is insufficient. No such uniform triangle-preserving increment is proved in this attempt.

Finite verification and adversarial checks.

The companion Python script exhaustively checks the inclusion--exclusion criterion on 56,155 linear three-edge configurations using vertex sets of size at most nine. It also tests all 260 progression-free subsets of $[N]$ for $1\leq N\leq8$, constructs their hypergraphs, checks pair uniqueness, and explicitly checks the union of every three edges. One test is $N=8$, $A=\{1,2,4,5\}$, giving 32 triples on 48 available vertices. Four small sphere constructions are checked separately for progression-freeness. These computations test implementations of the proved lemmas; they do not approximate the unknown extremal order.

Three boundary errors were specifically excluded. The union condition is "at most six", so non-linear degeneracies cannot be omitted. Empty vertex classes or extra isolated vertices do not change admissibility. Finally, integer division by two in the shadow construction is legitimate because an $XZ$ edge supplies an actual integer step in $A$; replacing the interval by an even cyclic group would invalidate the pair-uniqueness argument.

Outcome and next concrete targets.

UNRESOLVED. The independently checked work gives the exact non-linear decomposition, the graph equivalence, a fully verified progression-free family, and the spectral inequality (a494:spectral). It reproduces the known broad bounds without matching their subpolynomial factors. No new extremal-order theorem is claimed. The first gap in the pursued upper-bound route is the triangle-preserving density-increment statement described above.

Further work could quantify the loss of triangles under spectral cuts, test such a bound against the digit constructions, and seek a decomposition whose parts preserve unique triangle completion. The construction route would instead need larger progression-free or non-arithmetic systems on the same vertex budget. Even matching (a494:lower) on a logarithmic exponent scale would require a proof; it would not automatically identify the extremal function up to constant factors.

Sources

• S1 Gowers and Janzer, Generalizations of the Ruzsa-Szemeredi and rainbow Turan problems for cliques $2020$. https://arxiv.org/html/2003.02754. Formulation source.
• S2 Status source for Ruzsa-Szemeredi $6,3$ Extremal-Order Problem. https://people.math.ethz.ch/~sudakovb/Brown-Erdos-Sos-power-saving.pdf. Further reference; not a proof endorsement.
• E1 Jacob Fox, A new proof of the graph removal lemma, Annals of Mathematics 174 $2011$, 561--579. https://annals.math.princeton.edu/2011/174-1/p17. https://arxiv.org/abs/1006.1300. Primary source for the removal theorem; consulted 27 September 2026.