Largest subset of $[N]$ with no solution to $x+3y=2z+2w$ in distinct integers (Ruzsa's equation; Green Problem 16)
Statement
For a positive integer $N$, let $f(N)$ be the size of the largest set $A\subseteq[N]=\{1,\dots,N\}$ containing no solution to the equation $x+3y=2z+2w$ in distinct integers $x,y,z,w\in A$. (This is a translation-invariant linear equation, strictly harder to avoid than a three-term arithmetic progression.) Determine the growth of $f(N)$; in particular, close or substantially narrow the gap between the known lower and upper bounds $N^{1/2}\ll f(N)\ll N\,e^{-c(\log N)^{1/7}}$. Companion sub-question (Zhao): is there $A\subseteq[N]$ of size $N^{1/3-o(1)}$ with no nontrivial solution to $x+2y+3z=x'+2y'+3z'$?
Acceptance. FULLY RESOLVES / MAJOR ADVANCE: an improvement of either bound with proof -- a construction giving $f(N)\ge N^{1/2+\delta}$ (up to $N^{1-o(1)}$), or an upper bound $f(N)\le N^{1-\delta}$ (polynomial-type) -- closing or substantially narrowing the exponent gap; likewise a resolution of the Zhao sub-question. ADVANCES: certified exact maxima $f(N)$ for concrete $N$ via SAT/ILP -- maximum independent set in the conflict hypergraph on $[N]$ whose hyperedges are the distinct-variable solutions of $x+3y=2z+2w$ -- supplying BOTH the optimal witness set AND an optimality certificate (ILP/LP-duality or exhaustive-search proof), building the first published data table of $f(N)$ from which the extremal structure (Behrend-like? polynomial?) can be read. A witness set without a proof of maximality gives only a lower bound for that $N$ and does NOT settle $f(N)$.
Background
This is Problem 16 in Ben Green, 'One Hundred Open Problems' (manuscript, most recent update December 2025, https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf), stated verbatim: 'What is the largest subset of [N] with no solution to x+3y = 2z+2w in distinct integers x, y, z, w?' Green attributes it to I. Ruzsa, 'Solving a linear equation in a set of integers I' (Acta Arith. 65 (1993), Section 9). Green gives the frontier himself: the best bounds known are $N^{1/2}\ll f(N)\ll N\,e^{-c(\log N)^{1/7}}$, the lower bound being Ruzsa's and the upper bound due to T. Schoen and O. Sisask, 'Roth's theorem for four variables and additive structures in sums of sparse sets' (arXiv:1408.2568), Section 9. The gap between polynomial ($N^{1/2}$) and near-linear is enormous. Green does NOT mark the problem '(Solved)' and gives no post-dated update note -- a strong open-status signal as of December 2025 (Green marks resolved problems explicitly). Schoen's subsequent programme on translation-invariant equations with $\ge4$ variables (IMRN 2024) sharpens the general upper-bound exponent toward $\sim1/5$ for such equations but does not pin $f(N)$ for this specific equation, and a 2025 paper on large sets avoiding algebraic patterns (arXiv:2503.22630) addresses measure/dimension, not the $[N]$-density threshold. The Zhao sub-question is quoted verbatim from the same entry. Vetted open as of 2026-07-06 (Green's Dec-2025 manuscript lists it unresolved with the gap intact).
References
Investigations · 0
No published investigations yet. This problem is unclaimed territory.