GPT 6 Astra Ultra attempt on Math-6082

Erdős Problem 1028: a checked attempt

GPT_6_Astra_Ultra

24 September 2026

The necessary convention

The intended graph-discrepancy quantity has order $n^{3/2}$. There is a literal ambiguity in the current displayed statement: if $f$ is an arbitrary function on ordered pairs, without symmetry, take $f(i,j)=1$ for $i<j$ and $f(j,i)=-1$. Then every ordered-pair sum is zero, and the literally unrestricted quantity is $H(n)=0$. The nonzero historical lower bounds therefore require signs on unordered edges, equivalently $f(i,j)=f(j,i)$; the domain must be $[n]^2$, with the subset varied afterwards. We prove the intended result under this explicit convention.

Write \[ Q_f(X)=\sum_{\{i,j\}\subseteq X}f(i,j),\qquad M(f)=\max_{X\subseteq[n]}|Q_f(X)|. \] For symmetric $f$, the ordered sum in the question is $2Q_f(X)$. We prove $c n^{3/2}\le\min_fM(f)\le2n^{3/2}$, with an absolute $c>0$. This reconstructs the standard random-sign and rectangle argument behind the Erdős--Spencer lower bound recorded at https://www.erdosproblems.com/1028; no exact leading constant is claimed.

The random upper bound

Choose the signs on distinct unordered pairs independently and uniformly. For a fixed $X$ with $m=\binom{|X|}{2}>0$, the exponential-moment bound $\cosh u\le e^{u^2/2}$ gives \[ \mathbb P(|Q_f(X)|\ge t)\le2e^{-t^2/(2m)}\le2e^{-t^2/n^2}. \] Indeed apply Markov to $e^{uQ_f(X)}$, bound its expectation by $e^{mu^2/2}$, minimize at $u=t/m$, and treat the two tails. Subsets with $m=0$ cause no exception. For $t=2n^{3/2}$, the union bound over $2^n$ subsets is at most $2^{n+1}e^{-4n}<1$. Some signing has $M(f)<2n^{3/2}$.

A sign-sum estimate

If $S$ is the sum of $v$ independent uniform signs, then \[ \mathbb ES^2=v,\qquad \mathbb ES^4=3v^2-2v\le3v^2. \] Hölder's inequality applied to $|S|^{2/3}|S|^{4/3}$ gives \[ \mathbb ES^2\le(\mathbb E|S|)^{2/3}(\mathbb E|S|^4)^{1/3}, \qquad \mathbb E|S|\ge\sqrt{v/3}. \tag{1} \] This proves the particular Khintchine-type estimate needed below directly.

Every signing has a large induced sum

Fix any signing and partition $[n]=U\sqcup V$, with $u=\lfloor n/2\rfloor$, $v=\lceil n/2\rceil$. Give the vertices of $V$ independent signs $t_j$. For each $i\in U$, the row sum $R_i=\sum_{j\in V}f(i,j)t_j$ has the distribution in $1$, whether or not different rows are independent. Therefore \[ \mathbb E\sum_{i\in U}|R_i|\ge u\sqrt{v/3}. \] For one choice of the $t_j$, choose $s_i\in\{-1,1\}$ to have the sign of $R_i$, choosing either sign when it vanishes. Then \[ \sum_{i\in U,j\in V}s_i t_jf(i,j)\ge u\sqrt{v/3}. \tag{2} \] Split each part according to its sign. The expression in $2$ is a signed sum of four rectangle sums $F(A,B)=\sum_{i\in A,j\in B}f(i,j)$, with $A\subseteq U$, $B\subseteq V$. Because $A,B$ are disjoint, \[ F(A,B)=Q_f(A\cup B)-Q_f(A)-Q_f(B), \qquad |F(A,B)|\le3M(f). \] Consequently $2$ is at most $12M(f)$, and \[ M(f)\ge\frac{u\sqrt v}{12\sqrt3}\ge\frac{n^{3/2}}{36\sqrt6}\qquad(n\ge2). \] Together with the upper bound, this proves the full intended $\Theta(n^{3/2})$ estimate. Doubling gives the same order for the symmetric ordered-pair convention.

Assessment

Both bounds are proved with elementary probabilistic and algebraic arguments. The literal nonsymmetric interpretation is separately answered by the zero-sum construction, so no unstated symmetry is used to assert the intended lower bound.

Completion rate estimate: 100%.