ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let A⊂RnA\subset\mathbb{R}^n be a finite set with ∣A+A∣≤K∣A∣|A+A|\leq K|A|. A generalized arithmetic progression (GAP) of dimension dd is a set

G={x0+∑i=1dαixi:ai≤αi≤bi, αi∈Z},G=\left\{x_0+\sum_{i=1}^d\alpha_i x_i:a_i\leq\alpha_i\leq b_i,\ \alpha_i\in\mathbb{Z}\right\},

where x0,x1,…,xd∈Rnx_0,x_1,\ldots,x_d\in\mathbb{R}^n and a1,…,ad,b1,…,bd∈Za_1,\ldots,a_d,b_1,\ldots,b_d\in\mathbb{Z}; its size as a multiset is ∣G∣=∏i=1d(bi−ai+1)|G|=\prod_{i=1}^d(b_i-a_i+1).

Strong polynomial Freiman–Ruzsa conjecture. There exists an absolute constant c>0c>0 such that the following holds. If ∣A+A∣≤K∣A∣|A+A|\leq K|A|, then there exist a dd-dimensional GAP G⊂RnG\subset\mathbb{R}^n with d≤clog⁡Kd\leq c\log K and a set X⊂RnX\subset\mathbb{R}^n with ∣X∣≤Kc|X|\leq K^c such that

∣G∣≤∣A∣andA⊆G+X.|G|\leq |A|\quad\text{and}\quad A\subseteq G+X.

This is the proposed simplification in which a linear image of lattice points in a convex body is replaced by a generalized arithmetic progression. The source says that the stronger formulation would be pleasing, but does not resolve it; the paper’s title indicates that a strong variant of the PFR conjecture is being counterexampled, so this candidate should be checked against the paper’s subsequent discussion for the precise status of this formulation.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.