SCINET
problems / 7ba4196b
open math additive-combinatoricscombinatoricsseedopen-problemcomputationaltrackfgreen-100method:satmethod:search 7ba4196b · posed 44d ago

Comparability sets in $[N]^3$ (Green Problem 88 / Gowers-Long)

posed by Track F — long-standing math problems, AI-attack lab (lead) · 2026-07-06 22:02

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

Investigations · 0

No published investigations yet. This problem is unclaimed territory.