Partitions and Large Cosets

Affine Subspaces from a Finite Partition

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A partition ${\mathbb{F}}_2^n=A_1\sqcup\cdots\sqcup A_K$ assigns exactly one class to each vector; empty classes do not affect the question. For each fixed $K$, seek a bound $C(K)$ independent of $n$ such that some $A_i+A_i$ contains $x+V$ with $\operatorname{codim}V\leq C(K)$. The index and the affine subspace may depend on the partition. [S1] [S2]

Statement recorded in the supplied source.

Suppose that $\mathbb{F}_2^n$ is partitioned into sets $A_1, \dots, A_K$. Does $2A_i$ contain a coset of codimension $O_K(1)$ for some $i$? [S1]

Short English statement

In every bounded-colour partition of a binary vector space, must the sumset of one colour class contain an affine subspace of bounded codimension?

Research attempt

Provenance and scope.

This individual attempt was generated by GPT-6 Astra Ultra on 1 October 2026. The method was to derive explicit partial results and test the first proposed extension adversarially. The original statement and sources below are retained. No claim of mathematical novelty or complete solution is made.

Formal target and source check.

Let $V={\mathbb{F}}_2^n$ be partitioned into $K$ sets $A_1,\ldots,A_K$. Empty classes are harmless. The target is a coset in some $2A_i$ whose codimension is bounded in terms of $K$ alone. The maintained primary list treats the three-colour case as a genuine open instance. We prove the complete two-colour case, analyse its exact stabiliser mechanism, and show why neither choosing a largest class nor passing through arbitrary covers supplies the missing induction.

Two colours: a complete argument.

If one class has more than half the points, its double sumset is all of $V$: for every $t$, two translates of that class have total size greater than $|V|$, so they intersect and represent $t$ as a sum. The only remaining two-colour case has $|A_1|=|A_2|=|V|/2$. Fix $A=A_1$. If $2A=V$ the conclusion holds. Otherwise choose $t\notin2A$. Disjointness of $A$ and $A+t$, together with half density, forces $A+t=A_2$.

Let $H=\{h\in V:A+h=A\}$. This is a subspace: zero stabilises $A$, and two successive stabilising translations add to another one. Every missing sum $s\notin2A$ satisfies $A+s=A_2=A+t$, so $s+t\in H$. Conversely if $s+t\in H$, then $A+s=A+t=A_2$, hence $s\notin2A$. Thus the full missing-sum set is the single coset $t+H$. As $t\notin H$, there is a linear functional $\ell$ with $\ell(H)=0$ and $\ell(t)=1$. Its kernel is a hyperplane contained in $2A$. Hence two colours always suffice with codimension at most one. This is sharp for the partition into the two cosets of a hyperplane.

What the exact description adds.

In the equal-size case, $A_2=A+t$ implies $2A_2=2A$, because $t+t=0$. Thus both colour classes have the same double sumset, and their common complement, when nonempty, is an affine subspace. This is stronger than merely finding one hyperplane. It explains why a simple two-colour obstruction cannot exist: the missing sums are forced into a single coset that a hyperplane can avoid. The proof does not require $A$ itself to be a coset; its stabiliser may be very small, in which case the missing-sum set is correspondingly small.

The covering implication and the failed converse shortcut.

Suppose $A+S=V$ with $|S|=K$. Selecting, for each point, one covering translate partitions $V$ into $K$ pieces $C_s\subset A+s$. Each satisfies $2C_s\subset2A$, since the translation disappears upon doubling. Thus a positive answer to the partition question gives a positive answer to the additive-complement question. The converse is not obtained by taking the largest colour class: a set of density at least $1/K$ need not have a complement of size bounded by $K$ or by any fixed function of its density through the elementary greedy argument. The elementary probabilistic covering bound is $O(Kn)$, which depends on dimension and is too large for the desired conclusion.

Nor can one merge $A_2$ and $A_3$, apply the two-colour theorem, and then split the resulting sumset. If $B=A_2\cup A_3$, then \[ 2B=2A_2\cup(A_2+A_3)\cup2A_3. \] A large subspace inside this union may lie mainly in the mixed sumset $A_2+A_3$. The two-colour proof gives no control eliminating that middle term. This is a precise obstacle to induction on the number of colours, not simply a missing bookkeeping detail.

A necessary lower scale for any quantitative answer.

Let $H$ have codimension $m$ and partition $V$ into its $2^m$ cosets. For every class $a+H$, its double sumset equals $H$. Every affine subspace contained in that double sumset has dimension at most $n-m$. Thus when $K=2^m$, a universal codimension bound must be at least $m=\log_2K$. Extra empty classes allow the same obstruction for larger colour budgets. This lower bound is compatible with the qualitative conjecture and does not show that logarithmic dependence is sufficient.

Verification and status.

For $K=1$, the whole space is already the unique class. For $n=1$, the balanced two-colour argument gives the zero subspace, of codimension one, exactly as required. The missing-sum identity uses only equality of the two class sizes and characteristic two; extending it to unequal densities below one half would be false. The checked outcome is the full two-colour theorem, the exact balanced-case structure, and the covering reduction with its quantitative dependence preserved. The first unresolved case remains $K=3$, where neither the complement identity nor the merging argument supplies the necessary monochromatic double sumset.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 114 (GREEN-026), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 B. Green, 100 Open Problems, Problem 53, version. https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf. The author-hosted document was inspected on 27 September 2026; the archive’s local code is not a problem-number locator in this paper.