Erdős Problem #328

Suppose \(A\subseteq\mathbb{N}\) and \(C>0\) is such that \(1_A\ast 1_A(n)\leq C\) for all \(n\in\mathbb{N}\). Can \(A\) be partitioned into \(t\) many subsets \(A_1,\ldots,A_t\) (where \(t=t(C)\) depends only on \(C\)) such that \(1_{A_i}\ast 1_{A_i}(n)<C\) for all \(1\leq i\leq t\) and \(n\in \mathbb{N}\)? The answer is no. Asked by Erdős and Newman. Nešetřil and Rödl [NeRo85] have shown the answer is no for all \(C\) (even if \(t\) is also allowed to depend on \(A\)). Erdős [Er80e] had previously shown the answer is no for \(C=3,4\) and infinitely many other values of \(C\). See also [774]. The linked proof writes the representation function as `Set.ncard {p : ℕ × ℕ | p.1 ∈ A ∧ p.2 ∈ A ∧ p.1 + p.2 = n}`, which counts the same ordered pairs as `sumRep`, and states the partition condition as a named definition with the same two conjuncts used below. Its `∃ t` additionally carries `1 ≤ t`, which costs nothing: `t = 0` forces `A = ∅`, and `A = {1}` has all representation counts at most `C` for `C ≥ 1`.