we-solve (beta)

Math-525 · mathematics · Combinatorics

Largest Coset in 2A

Status Open · unsolvedmath.comLLM status Open unverified

Statement

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.

For $A\subseteq{\mathbb{F}}_2^n$, $2A=A+A$. An affine subspace $x+V$ contains $2^{\dim V}$ elements. The extremal quantity can be recorded as \[L(n,m)=\min_{|A|=m}\max_{x+V\subseteq A+A}2^{\dim V},\qquad\alpha=m/2^n.\] Only attainable integer sizes $m$ are used. Determine sharp guarantees for $L(n,m)$ as a function of the density and dimension. [S1] [S2]

Statement recorded in the supplied source.
Suppose that $A \subset \mathbb{F}_2^n$ has density $\alpha$. What is the largest size of coset guaranteed to be contained in $2A$? [S1]

Short English statement

Given only the density of a set over the two-element field, how large an affine subspace must its pairwise sumset contain?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-525-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-525

The Largest Affine Subspace Forced in a Double Sumset

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.

For $A\subseteq{\mathbb{F}}_2^n$, $2A=A+A$. An affine subspace $x+V$ contains $2^{\dim V}$ elements. The extremal quantity can be recorded as \[L(n,m)=\min_{|A|=m}\max_{x+V\subseteq A+A}2^{\dim V},\qquad\alpha=m/2^n.\] Only attainable integer sizes $m$ are used. Determine sharp guarantees for $L(n,m)$ as a function of the density and dimension. [S1] [S2]

Statement recorded in the supplied source.
Suppose that $A \subset \mathbb{F}_2^n$ has density $\alpha$. What is the largest size of coset guaranteed to be contained in $2A$? [S1]

Short English statement

Given only the density of a set over the two-element field, how large an affine subspace must its pairwise sumset contain?

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 context.
For a set $A\subset{\mathbb{F}}_2^n$ of density $\alpha$, determine the largest affine subspace that must lie in $2A=A+A$. A coset is an affine subspace, so translations must be included in upper obstructions. The primary problem list warns that two summands can have substantially less structure than four. We examine a concrete Hamming-ball family, calculate its double sumset exactly, and prove its maximum possible affine dimension rather than only ruling out linear subspaces through zero.
Exact double sumsets of Hamming balls.
Let $|x|$ denote the number of nonzero coordinates of $x$, and let $B_r=\{x:|x|\leq r\}$, with $0\leq2r\leq n$. For $x,y\in B_r$, the support of $x+y$ is contained in the union of the two supports, so $|x+y|\leq2r$. Conversely, if $|z|\leq2r$, partition its support into two disjoint pieces of sizes at most $r$. The indicator vectors of those pieces lie in $B_r$ and sum to $z$. Hence \[ B_r+B_r=B_{2r}. \] The equality is exact, including all boundary cases, and uses the allowance of repeated summands only for the zero vector if desired. Its cardinality is $\sum_{j=0}^{2r}\binom nj$; density of the original ball is $2^{-n}\sum_{j=0}^r\binom nj$.
A pivot-coordinate lemma for affine subspaces.
Every affine subspace of dimension $d$ in ${\mathbb{F}}_2^n$ contains a vector of Hamming weight at least $d$. To prove this, write it as $a+W$, choose a basis for $W$, and form the $d\times n$ matrix of basis vectors. Rank $d$ supplies $d$ linearly independent columns. Projection of $W$ onto those coordinate positions is then a bijection onto ${\mathbb{F}}_2^d$. Projection of $a+W$ is likewise a bijection, since translation is a bijection. There is therefore a point whose selected $d$ coordinates all equal one. Its total weight is at least $d$, as claimed.

If $a+W\subset B_{2r}$, the lemma gives $\dim W\leq2r$. Conversely the coordinate subspace supported on any fixed $2r$ coordinates has dimension $2r$ and lies in $B_{2r}$. We have proved an exact answer for this family: \[ \max\{\dim W:a+W\subset B_r+B_r\}=2r. \] The translation in the pivot argument is important: a proof only about a basis of $W$ would not control a coset avoiding the origin.

Constant-density examples with growing codimension loss.
Take even $n$, write $m=n/2$, and choose $r=m-\lfloor\sqrt n\rfloor$. The density of $B_r$ stays bounded below by an absolute positive constant as $n$ tends to infinity. Here is enough detail to verify that assertion without assuming concentration in the wrong tail. Consider integers $j$ between $m-2\lfloor\sqrt n\rfloor$ and $m-\lfloor\sqrt n\rfloor$. There are order $\sqrt n$ such integers. Stirling's formula gives $\binom n m\asymp2^n/\sqrt n$. Moreover \[ \frac{\binom n{m-k}}{\binom n m} =\prod_{i=0}^{k-1}\frac{m-i}{m+i+1} \] is bounded below by an absolute positive constant for $k\leq2\sqrt n$ and sufficiently large $n$. Indeed, the logarithm of each factor is at least $-C(i+1)/n$ in this range, and summing gives at least $-C'k^2/n\geq-C''$. Summing over the stated interval yields an absolute positive lower bound for the binomial probability.

On the other hand, the exact affine dimension in $2B_r$ is $n-2\lfloor\sqrt n\rfloor$. Thus even a fixed positive density does not force an affine subspace of bounded codimension in the double sumset. If one wants exactly a chosen smaller density, pass to an arbitrary subset of the ball of the required cardinality; its double sumset is contained in $2B_r$, so the same upper obstruction persists. This last monotonicity step avoids silently changing a fixed-density formulation to a varying-density one.

Verification and remaining task.
The companion script computes exact binomial densities and exact predicted maximal affine dimensions at $n=16,64,256$, obtaining dimensions $8,48,224$. These are checks of the proved formula, not exhaustive searches through affine subspaces. At $r=0$ the maximum dimension is zero; at $2r=n$ it is $n$, both correctly. The work gives a fully explicit obstruction and an exact extremal calculation within a natural family. It does not determine the best guaranteed dimension for all sets of a given density, or show that these balls are globally extremal. The unresolved step is a matching universal lower bound or a stronger family of upper obstructions for the full two-sumset question.

Sources

Go to contribution →