Comparability sets in $[N]^3$ (Green Problem 88 / Gowers-Long)
Statement
For $x,y\in[N]^3=\{1,\dots,N\}^3$, call $x,y$ comparable if the difference $x-y$ has either two strictly positive coordinates or two strictly negative coordinates. Let $S\subseteq[N]^3$ have the property that every two distinct elements are comparable. Is $|S|\le N^{2-\delta}$ for some absolute $\delta>0$? Equivalently: bound the maximum independent set of the explicit graph on $[N]^3$ that joins $x,y$ whenever they are NOT comparable. A single 'layer' gives the trivial bound $|S|=O(N^2)$; the goal is to break $N^{2-\delta}$. Green also poses a symmetric modular version in $\mathbb{F}_p^3$: with six explicit 'comparability' classes forming a symmetric set $S$, if $A\subseteq\mathbb{F}_p^3$ has $A-A$ avoiding $S$, must $|A|\le p^{2-\delta}$?
Acceptance. ADVANCES: certified exact values of the maximum comparable-set size $\alpha(N)$ (with the extremal $S$ and an independent-set optimality certificate) for a range of small $N$, plus the fitted exponent and extremal structure; likewise for the $\mathbb{F}_p^3$ variant. ADVANCES: a rigorous sub-$N^2$ bound $|S|\le N^{2-\delta}$ (e.g. a weighted Delsarte-LP dual certificate breaking the spectral barrier), or a construction beating the naive single-layer lower bound. FULLY RESOLVES: a proof (or disproof) that $|S|\le N^{2-\delta}$ for some absolute $\delta>0$, correspondingly for the $\mathbb{F}_p^3$ version.
Background
Problem 88 in Ben Green, '100 Open Problems' (manuscript, most recent update December 2025), https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf; not marked '(Solved)'. The question is due to W. T. Gowers and J. Long, 'The length of an $s$-increasing sequence of $r$-tuples', arXiv:1609.08688 (Combin. Probab. Comput.), motivated by a question of Po-Shen Loh. Green calls it 'perhaps the most basic' of the Gowers-Long questions and notes it sits below the threshold where a spectral (Delsarte) bound applies. Frontier: the trivial upper bound is $O(N^2)$; for the STRONGER increasing hypothesis Gowers-Long improved the analogous bound (beating Loh's $N^2/\exp(\Omega(\log^* N))$), but that argument does NOT bound the merely-comparable case - so no sub-$N^{2-\delta}$ bound is known for this problem. Both the $[N]^3$ integer version and the $\mathbb{F}_p^3$ modular (Cayley-graph) version are maximum-independent-set on a fully explicit graph, ideal for exact ILP/SAT solvers at small $N,p$ and for spectral/LP-relaxation experiments; the $\mathbb{F}_p^3$ version's symmetry invites an eigenvalue / Fourier bound. Vetted open as of 2026-07-06 (high confidence; Green's Dec-2025 manuscript lists it unresolved).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Ben Green, 100 Open Problems (Dec 2025) - Problem 88 (Gowers-Long) | paper |
| REF-02 | Gowers & Long, The length of an s-increasing sequence of r-tuples | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.