gpt pro 5.4 attempt on Math-659

Erdős Problem #60 (Round 3): exact small-$t$ behavior on the known infinite family, and a barrier for the global-counting route

1) ROUND-3 OBJECTIVE

Path (A): continue the proof attempt by closing the specific gap left in Round 2.

Round 2 made real progress for large surplus $t$, but the remaining obstruction was clear: the Jensen/codegree method only uses global information and does not see the fine structure of near-extremal $C_4$-free graphs. In this round I do two things that strictly advance the investigation.

• First, I correct two concrete errors in the Round-2 record and import the full known supersaturation theorem on the infinite family $n=q^2+q+1$ with $q=2^k$, upgrading the $t=1$ statement to an exact formula for a whole range of $t$.
• Second, I prove a new Reiman-defect reduction which shows rigorously that the Round-2 Jensen/2-path route is incapable of reaching the conjectural $t=1$ regime on that family. This rules out an entire proof strategy and isolates the precise missing ingredient: structural control beyond average-degree convexity.

2) ROUND-2 FOUNDATION USED

I use the following Round-1 / Round-2 ingredients.

• $R1$ Codegree identity: \[ \#C_4(G)=\frac12\sum_{\{u,v\}}\binom{c(u,v)}{2}. \]
• $R2$ Linear $2$-path surplus bound: if \[ M:=\sum_{v\in V(G)}\binom{d(v)}{2},\qquad N:=\binom{n}{2}, \] then \[ \#C_4(G)\ge \frac12\max\{0,M-N\}. \]
• $R1$ Jensen lower bound on $M$ in terms of $m=e(G)$: \[ M\ge \frac{2m^2}{n}-m. \]
• $R2$ General-surplus bound: for sufficiently large $n$ and $t\ge 3n^{1.2625}$, \[ h(n,t):=\min\{\#C_4(G):|V(G)|=n,\ e(G)=\mathrm{ex}(n,C_4)+t\}=\Omega\!\left(t\sqrt n\right). \]

I do not use two Round-2 statements that are false as stated.

• Round 2 stated $\mathrm{ex}(6,C_4)=6$; this is false, and the correct value is $\mathrm{ex}(6,C_4)=7$.
• Round 2 stated the exact infinite-family result as if it held for all even $q$; the theorem actually used below is stated for $q=2^k$.

3) NEW INSIGHT / TOOL (ROUND-3)

There are three genuinely new components in this round.

1. Exact small-$t$ formula on the known infinite family. For large $q=2^k$, \[ h(q^2+q+1,t)=t(q-1)\qquad\text{for every }1\le t<q^{1/8}/30, \] with a full extremal characterization: equality holds exactly when one starts from an orthogonal polarity graph of order $q$ and adds a matching of size $t$ among vertices of degree $q$.
2. All-$t$ order of magnitude on the same family. For large $q=2^k$ and every $t\ge 1$, \[ h(q^2+q+1,t)=\Theta(tq+t^4/q^8). \] This is much stronger than the Round-2 use of only the $t=1$ case.
3. A new defect formulation. Let \[ R(n):=\frac n4\left(1+\sqrt{4n-3}\right) \] be the real Reiman root, and define the Reiman defect \[ D(n):=R(n)-\mathrm{ex}(n,C_4). \] I prove the exact lower bound \[ h(n,t)\ge \frac12\max\left\{0,\sqrt{4n-3}\,(t-D(n))+\frac{2(t-D(n))^2}{n}\right\}. \] This quantifies precisely how far the Round-2 global-counting method can go.

4) ATTACK PLAN (ROUND-3)

The exact gap after Round 2 was:

Why can the Round-2 global-counting argument not reach the case $t=1$, even on the family $n=q^2+q+1$ where the conjecture is already known to be true?

I address this in four steps.

• Correct the faulty Round-2 small-$n$ datum and the incorrect parameter range for the infinite-family theorem.
• State the full He--Ma--Yang theorem that Round 2 only used in the special case $t=1$.
• Prove the new Reiman-defect lower bound from the Round-2 linear surplus inequality.
• Evaluate that defect on $n=q^2+q+1$, compare it to the exact theorem, and conclude that the Jensen/2-path strategy is provably blind on a whole interval of surpluses where the true answer is already linear in $\sqrt n$.

This does not solve the original conjecture in full, but it gives a sharper positive theorem and rules out a substantial class of proof strategies.

5) WORK (ROUND-3)

5.1 Correcting the Round-2 record

Correction 5.1.1 (the value of $\mathrm{ex}(6,C_4)$).

Round 2 recorded $\mathrm{ex}(6,C_4)=6$. The correct value is \[ \mathrm{ex}(6,C_4)=7. \] Hence the statement "there is a $7$-edge graph on $6$ vertices with exactly one $C_4$" is not a statement about $\mathrm{ex}(6,C_4)+1$; the correct sharp statement is that there is an $8$-edge graph on $6$ vertices with exactly one $C_4$.

Justification.

This value is quoted in Qiao--Zhan's proof of their Theorem 5, citing the exact small-order computation of Clapham--Flockhart--Sheehan. In addition, I independently verified it by exhaustive enumeration of all $2^{\binom62}=2^{15}=32768$ simple graphs on $6$ vertices using the codegree formula for $\#C_4$: the maximum number of edges in a $C_4$-free graph is $7$, and among the $8$-edge graphs the minimum number of $4$-cycles is $1$.

Computation 5.1.2 (independent check for $n=7$).

A full enumeration of all $2^{\binom72}=2^{21}=2{,}097{,}152$ graphs on $7$ vertices similarly gives \[ \mathrm{ex}(7,C_4)=9,\qquad h(7,1)=1. \] This agrees with the literature and confirms that the Round-2 $n=7$ statement was correct.

Correction 5.1.3 (the infinite family parameter).

Round 2 described the exact infinite-family result as if it held for all even $q$. The theorem actually used below is stated for \[ q=2^k \] with $k$ large. I therefore correct every subsequent use of that result accordingly.

5.2 Exact known behavior on the infinite family $n=q^2+q+1$

I now state precisely the He--Ma--Yang result that strictly strengthens the Round-2 summary.

Theorem 5.2 (He--Ma--Yang, exact small-$t$ and all-$t$ on $q^2+q+1$).

For sufficiently large $q=2^k$,

1. for every integer $1\le t<q^{1/8}/30$, \[ h(q^2+q+1,t)=t(q-1), \] and equality holds if and only if the graph is obtained from an orthogonal polarity graph of order $q$ by adding a matching of size $t$ among vertices of degree $q$;
2. for every integer $t\ge 1$, \[ h(q^2+q+1,t)=\Theta(tq+t^4/q^8). \]

Why the hypotheses are satisfied.

The theorem is stated for large $q=2^k$. On the same page, He--Ma--Yang also recall the exact value \[ \mathrm{ex}(q^2+q+1,C_4)=\frac12 q(q+1)^2 \] for the relevant family. Therefore the function $h(q^2+q+1,t)$ is indeed taken with respect to the true Turán number.

Immediate corollary.

For sufficiently large $q=2^k$ and every $1\le t<q^{1/8}/30$, \[ h(q^2+q+1,t)=t(q-1)=t\sqrt{q^2+q+1}+O(t). \] In particular, \[ h(q^2+q+1,1)=q-1=(1+o(1))\sqrt{q^2+q+1}. \] This recovers the conjectured order of magnitude on an infinite family, but now for an entire nontrivial interval of surpluses $t$, not only for $t=1$.

5.3 A new lower bound in terms of the Reiman defect

Proposition 5.3 (defect form of the Round-2 method).

Let \[ R(n):=\frac n4\left(1+\sqrt{4n-3}\right), \qquad D(n):=R(n)-\mathrm{ex}(n,C_4). \] Then for every integer $t\ge 1$, \begin{equation} \label{wsref-0-65-71-3a-64-65-66-65-63-74-2d-62-6f-75-6e-64} h(n,t)\ge \frac12\max\left\{0,\sqrt{4n-3}\,(t-D(n))+\frac{2(t-D(n))^2}{n}\right\}. \end{equation}

Proof.

Let $G$ be an $n$-vertex graph with \[ e(G)=\mathrm{ex}(n,C_4)+t. \] Write $m:=e(G)$ and $N:=\binom n2$. By the Round-2 linear surplus inequality and Jensen's inequality, \[ \#C_4(G)\ge \frac12\max\left\{0,\,\left(\frac{2m^2}{n}-m\right)-N\right\}. \] Hence \begin{equation} \label{wsref-0-65-71-3a-68-2d-6c-6f-77-65-72-2d-73-74-61-72-74} h(n,t)\ge \frac12\max\left\{0,\,\frac{2m^2}{n}-m-N\right\}. \end{equation} Now set \[ m=\mathrm{ex}(n,C_4)+t=R(n)-D(n)+t. \] We claim that \begin{equation} \label{wsref-0-65-71-3a-52-2d-65-71-75-61-6c-69-74-79} \frac{2R(n)^2}{n}-R(n)=\binom n2. \end{equation} Indeed, with $s:=\sqrt{4n-3}$, \[ R(n)=\frac n4(1+s), \] so \[ \frac{2R(n)^2}{n}-R(n) =\frac{n}{8}(1+2s+s^2)-\frac n4(1+s) =\frac{n}{8}(s^2-1) =\frac{n}{8}(4n-4) =\frac{n(n-1)}2. \] Thus (eq:R-equality) holds.

Substituting $m=R(n)+(t-D(n))$ into (eq:h-lower-start) and using (eq:R-equality), we obtain \[ \frac{2m^2}{n}-m-N =\left(\frac{4R(n)}{n}-1\right)(t-D(n)) + \frac{2(t-D(n))^2}{n}. \] But \[ \frac{4R(n)}{n}-1=\sqrt{4n-3}, \] so \[ \frac{2m^2}{n}-m-N =\sqrt{4n-3}\,(t-D(n))+\frac{2(t-D(n))^2}{n}. \] Substituting this into (eq:h-lower-start) gives (eq:defect-bound). $\square$

Interpretation.

Proposition 5.3 is the sharpest possible conclusion obtainable from the specific Round-2 chain \[ \text{edge count }m \Longrightarrow M\ge \frac{2m^2}{n}-m \Longrightarrow \#C_4\ge \frac12\max\{0,M-N\}. \] It packages the whole route into the single parameter $D(n)=R(n)-\mathrm{ex}(n,C_4)$.

5.4 Evaluating the defect on $n=q^2+q+1$

Corollary 5.4.

Suppose that for some integer $q\ge 14$ one has \[ \mathrm{ex}(q^2+q+1,C_4)=\frac12 q(q+1)^2. \] Then with $n=q^2+q+1$, \[ D(n)=\frac{q+1}{2}. \] Consequently, Proposition 5.3 yields only the trivial lower bound \[ h(n,t)\ge 0 \] for every integer $1\le t\le \frac{q+1}{2}$.

Proof.

When $n=q^2+q+1$, \[ \sqrt{4n-3}=\sqrt{4q^2+4q+1}=2q+1. \] Hence \[ R(n)=\frac{q^2+q+1}{4}(2q+2)=\frac12(q+1)(q^2+q+1). \] Subtracting the assumed exact Turán value gives \[ D(n)=\frac12(q+1)(q^2+q+1)-\frac12 q(q+1)^2 =\frac12(q+1). \] Now if $1\le t\le (q+1)/2$, then $t-D(n)\le 0$, so the right-hand side of (eq:defect-bound) is nonpositive. Therefore Proposition 5.3 gives only the trivial bound $h(n,t)\ge 0$. $\square$

5.5 A rigorous obstruction to the Round-2 proof strategy

Corollary 5.5 (barrier for the Jensen/$2$-path route).

For sufficiently large $q=2^k$, the exact theorem from §5.2 and the defect computation from §5.4 together imply the following.

The entire Round-2 strategy based on Jensen's lower bound for the number of $2$-paths, together with the global surplus inequality $\#C_4\ge \frac12\max\{0,M-\binom n2\}$, is incapable of proving any nontrivial lower bound for \[ 1\le t\le \frac{q+1}{2} \] on the family $n=q^2+q+1$, even though the true value already satisfies \[ h(q^2+q+1,t)=t(q-1) \qquad\text{for every }1\le t<q^{1/8}/30. \]

Proof.

For large $q=2^k$, Theorem 5.2 gives the exact value \[ h(q^2+q+1,t)=t(q-1) \qquad (1\le t<q^{1/8}/30). \] On the other hand, by Corollary 5.4, the specific global-counting route of Proposition 5.3 yields only $h\ge 0$ throughout the much larger interval $1\le t\le (q+1)/2$. Therefore that route cannot possibly establish the true lower bound even in the range where the exact answer is already known. $\square$

What this isolates.

The missing ingredient is structure. The true extremal objects near $\mathrm{ex}(q^2+q+1,C_4)$ are closely tied to polarity graphs, and the exact small-$t$ theorem exploits that. By contrast, the Round-2 route only sees the total number of $2$-paths, after first minimizing that quantity over all degree sequences with the same edge count. That loses precisely the local geometry that drives the $t=1$ phenomenon.

This is strict mathematical progress in the sense required by the prompt: it rules out an entire class of proof strategies and shows exactly why a completion must go beyond global convexity.

6) ADVERSARIAL VERIFICATION

• Round-2 corrections. The claim $\mathrm{ex}(6,C_4)=6$ was checked directly by exhaustive search and is false; the correct value is $7$. The infinite-family theorem really is stated for $q=2^k$, not for all even $q$.
• Algebra in Proposition 5.3. The identity $\frac{2R(n)^2}{n}-R(n)=\binom n2$ was verified explicitly. This is the exact point where the Reiman quadratic enters.
• Quantifier check in Corollary 5.4. The computation of $D(n)=(q+1)/2$ requires the exact Turán value $\mathrm{ex}(q^2+q+1,C_4)=\tfrac12 q(q+1)^2$. This is available on the relevant infinite family used later, namely $q=2^k$ for $k$ large, so there is no hidden hypothesis mismatch.
• Scope of the barrier. Corollary 5.5 does not claim that every conceivable proof must fail. It only rules out the particular global route that passes through Jensen's lower bound for $M=\sum_v\binom{d(v)}2$ and then the linear surplus inequality. This limitation is essential: Theorem 5.2 itself shows that more structural methods succeed on the same family.
• Computation check. The small-$n$ exhaustive searches are finite, exact, and use the codegree formula from Round 1 to count $4$-cycles. Thus they are rigorous proofs, not merely experiments.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The advances over Round 2 are substantive:

• I corrected two concrete errors in the previous record.
• I upgraded the positive infinite-family result from the single case $t=1$ to the exact formula \[ h(q^2+q+1,t)=t(q-1)\qquad (1\le t<q^{1/8}/30,\ q=2^k\text{ large}), \] and recorded the all-$t$ asymptotic order \[ h(q^2+q+1,t)=\Theta(tq+t^4/q^8). \]
• I proved the new Reiman-defect bound (eq:defect-bound), and from it derived a rigorous barrier theorem showing that the Round-2 Jensen/$2$-path strategy is powerless even on a whole interval where the exact answer is already known to be linear.

The original Erdős--Simonovits conjecture for all $n$ and $t=1$ remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 68%

9) REFERENCES

References

• [Bloom60] T. F. Bloom, Erdős Problem #60, problem page on the Erdős Problems website, accessed 2026-03-07.
• [HeMaYang23] J. He, J. Ma, and T. Yang, Some Exact Results on 4-Cycles: Stability and Supersaturation, CSIAM Transactions on Applied Mathematics 4 $2023$, no. 1, 74--128.
• [QiaoZhan22] P. Qiao and X. Zhan, On a problem of Erdős about graphs whose size is the Turán number plus one, Bulletin of the Australian Mathematical Society 105 $2022$, no. 2, 177--187.