Erdős #120 — the Erdős similarity problem (affine copies)

Statement

Let $A\subseteq\mathbb{R}$ be an infinite set. Must there be a set $E\subset \mathbb{R}$ of positive (Lebesgue) measure which does not contain any set of the shape $aA+b$ for some $a,b\in\mathbb{R}$ and $a\neq 0$?

Equivalently (Jung–Lai–Mooroogen, arXiv:2412.11062, calling $A$ "measure universal" if the answer is *no* for that particular $A$): does there exist an infinite $A\subset\mathbb{R}$ that is measure universal, i.e. such that *every* measurable set of positive Lebesgue measure contains a nontrivial affine copy of $A$? Erdős's own belief, stated in [Er74b]: "I hope there are no such sets" — i.e. he conjectured the answer to #120 is yes (no infinite set is measure universal). This is the Erdős similarity conjecture, posed in 1974.

Facts

- Prize \$100; status per erdosproblems.com/120 (site-owner belief, verified 2026-07-02): OPEN. Explicitly tagged "cannot be resolved with a finite computation." - Falsifiability: not finite — the statement quantifies over all infinite $A\subseteq\mathbb R$ and, for a fixed $A$, over all measurable $E$; no finite search can decide it either way. (Contrast with e.g. Erdős #97 — convex polygon vertex with no 4 equidistant, which is finite-counterexample-falsifiable.) - Origin: [Er74b] P. Erdős, *Remarks on some problems in number theory*, Math. Balkanica 4 (1974), 197–202; also [Er81b,p.29], [Er83d], [Er90], [Er97f], [Va99,2.46]. - Reductions (both classical, stated on the page and in JLM24 §1.1): - True automatically if $A$ is unbounded (unbounded sets cannot be measure universal — trivial density argument) or if $A$ is dense in some interval. - Hence WLOG $A=\{a_1>a_2>\cdots\}$ is a strictly decreasing sequence converging to $0$. - Steinhaus (1920) [St20/Ste20] — *every finite set is measure universal* (via the Lebesgue density theorem: any Lebesgue density point of a positive-measure $E$ admits an affine copy of any finite set arbitrarily close to it). This is exactly why Erdős's question is restricted to infinite $A$; see concept/lebesgue-density-theorem. - Falconer (1984) / Eigen (1985), independently — sublacunary decreasing sequences ($a_{n+1}/a_n\to 1$) are not measure universal, via an explicit direct Cantor-set construction. Re-proved by Kolountzakis (1997) as a special case of a more general "long slow-decaying chunks" criterion, and again by Feng–Lai–Xiong (2024) as a corollary of their sharp bi-Lipschitz dichotomy (below). - Bourgain (1987) — gave a Fourier/oscillatory-integral characterization of measure universality and used it to show the sumset $A_1+A_2+A_3$ of *any* three infinite sets is never measure universal, even if each $A_i$ decays arbitrarily fast (not derivable from the Falconer–Eigen theorem). Proof sketch (via Tao's 2021 exposition, arXiv/Bull. AMS "Exploring the toolkit of Jean Bourgain"): random small-cube indicator sums + an entropy-decrement argument. - Kolountzakis (1997) — probabilistic (random-interval-selection) constructions; proved a slow-decay non-universality criterion strictly generalizing Falconer–Eigen, and an "almost-everywhere" positive result: for every infinite $A$ there is $E_1$ of measure arbitrarily close to $1$ such that a.e. dilate misses $E_1$, and an $E_2$ of positive measure such that the *set of dilations that work* has 2-D Lebesgue measure zero. I.e. universal sets, if they exist, are "measure-theoretically exceptional" in a strong quantitative sense. - THE CORE CASE IS STILL COMPLETELY OPEN: it is not known whether the single explicit sequence $A=\{1,1/2,1/4,1/8,\ldots\}$ (i.e. $(2^{-n})_{n\ge1}$) is measure universal or not. This exact case is also Problem 94 on Ben Green's open-problems list (people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf — a *different* numbering scheme from erdosproblems.com; not to be confused with erdosproblems.com's own #94, which is an unrelated, already-solved convex-polygon-distances problem). No exponentially-decaying sequence is known to be non-universal. - A claimed full proof was published and then WITHDRAWN: Cruz, Lai, Pramanik, "A proof of the Erdős similarity conjecture," arXiv:2001.02395 (Jan 2020), withdrawn days later — "A gap was found in Proposition 3.3 of the paper. We would like to thank professor Vjekoslav Kovač for pointing this out." This is the closest documented near-miss on record and pins down exactly the technical step (a Cantor-set / gap-counting construction) that keeps failing at full generality; two of the same authors went on to prove strictly weaker results in this direction (Gallagher–Lai–Weber 2023 for Newhouse-thick Cantor sets; Cruz–Lai–Pramanik 2023 on "Erdős points"). - Fully resolved sister problem — the bi-Lipschitz variant (Feng–Lai–Xiong, *IMRN* 2024, arXiv via JLM24 §2): relax "affine copy" to "bi-Lipschitz copy." Sharp dichotomy for decreasing sequences $a_n\to0$: (1) if $a_{n+1}/a_n\to1$ (sublacunary) then $A$ is not bi-Lipschitz measure universal (new proof of Falconer–Eigen, via a self-similar-gap Cantor set built from a slowly-varying subsequence); (2) if $\limsup a_{n+1}/a_n<1$ then $A$ is always bi-Lipschitz-embeddable into any positive-measure $E$ (constructive: match $a_n$ into a small interval $[\eta a_n,a_n]$ that a Lebesgue density point forces to intersect $E$, then interpolate piecewise-linearly). This is the single cleanest fully-solved analog in the whole literature — see concept/bi-lipschitz-embedding. - Cantor-set-specific results (both fully proved, both strictly imply non-measure-universality for their class): (a) Gallagher–Lai–Weber 2023 — Cantor sets of positive Newhouse thickness are not measure universal (indeed not "full measure universal"), via the classical Newhouse gap lemma: two Cantor sets whose thicknesses multiply to $\ge 1$ and which are not nested in each other's gaps must intersect; see concept/newhouse-thickness-gap-lemma. (b) Shmerkin (attributed in JLM24, via a BIRS-workshop remark) — Cantor sets of positive Hausdorff dimension are not measure universal, via Shmerkin–Suomala's spatially independent martingales (Mem. AMS 2018) smoothing a Frostman measure on $A$ against every affine image simultaneously; see concept/spatially-independent-martingales. It remains open (Conjecture 3.1 in JLM24, from Gallagher–Lai–Weber 2023) whether every Cantor set (positive thickness/dimension or not) is non-universal. - Topological variant fully classified: Gallagher–Lai–Weber (2023) + Jung–Lai (2024, two preprints) show a set is "topologically universal" (affine copy lands in every dense $G_\delta$) iff it is of strong measure zero; existence of uncountable topologically-universal sets is therefore independent of ZFC (via the Borel conjecture, known independent since Laver 1976 / Sierpiński 1928). All Cantor sets are shown not topologically universal via a new "containment lemma." See concept/strong-measure-zero-borel-conjecture. - Equivalent reformulation as a sumset problem (JLM24 Prop. 3.2, building on Jasinski 1996): $X$ is "full measure universal" iff for every Lebesgue-null $M$ there is $\lambda\neq0$ with $X+\lambda M\neq\mathbb R$. This turns the whole conjecture into a question about sumsets of $A$ against measure-zero sets, directly connecting to Erdős–Kunen–Mauldin (1981): every perfect $X\subset\mathbb R$ admits *some* measure-zero $M$ with $X+M=\mathbb R$ — but not (known to be) simultaneously for all dilates $\lambda M$, which is exactly the gap Conjecture 3.4 (JL24b) would need to close. See concept/full-measure-universality-sumset-equivalence. - A genuine "dual" research program — the Erdős similarity problem "in the large" (Bradford–Kohut–Mooroogen 2023, Kolountzakis–Papageorgiou arXiv:2208.02637, Gao–Mooroogen–Yip arXiv:2311.06727, Burgin–Goldberg–Keleti–MacMahon–Wang 2023): same question with *increasing* $a_n\to\infty$ and "$p$-large" sets (density $\ge p$ in every unit cube) replacing positive-measure sets. Linear sequences and all subexponential ($\log a_n=o(n)$) sequences are now fully proved non-universal, via metric-number-theory estimates on $\{y:(ya_n) \text{ not dense mod }1\}$ (Boshernitzan 1994; Pollington/de Mathan 1979–80; a new Dubickas-type estimate for $(2^n)$ giving partial coverage up to $p<1/2$). Burgin et al. showed results here transfer back to genuine sets of positive measure near a density point failing to contain any geometric progression $yb^{-n}$ for all bases $b>1$ simultaneously — the strongest concrete evidence connecting this dual program to #120 itself. See concept/erdos-similarity-in-the-large and concept/metric-number-theory-density-modulo-one. - De Reyna's category-dual result (J. Arias de Reyna, "Some Results Connected with a Problem of Erdős, III," Proc. AMS 89 (1983), 291–292, confirmed via WebSearch/ResearchGate abstract, 2026-07-02): the Baire-category analog — for any $E\subset\mathbb R$ with $>2$ points there is a set $S\subset[0,1]$ of full outer measure and second category containing no subset similar to $E$. Recently flagged (Mar 2026) by a DeepMind prover agent + independently by GPT-5.4 Thinking as literature relevant to a Lean-formalized "variant problem" of #120 (per the erdosproblems.com AI-contributions wiki, section 1(b), row "Erdős #120 — the Erdős similarity problem (affine copies)" — solution to a *variant*, not the main conjecture, and the AI's own approach was logged as "Similar? No" relative to de Reyna's 1983 argument). - Related problems: no genuine "See also" cross-links are given on erdosproblems.com/120 itself (checked: no /N hrefs in the page body besides prev/next #119, #121, which are topically unrelated — squares/dissection problems); no site-search hits for "measure universal" / "affine copy" on other numbered problems either. This appears to be a topically self-contained flagship problem on the site.

Literature state

Not resolved — genuinely open as of 2026-07-02, confirmed by the most recent survey (Jung–Lai–Mooroogen, "Fifty years of the Erdős similarity conjecture," arXiv:2412.11062, Dec 2024/Jan 2025 v2): "The conjecture remains open for exponentially decaying sequences as well as Cantor sets that have both Newhouse thickness and Hausdorff dimension zero." The erdosproblems.com forum thread (3 comments, fetched live) records no claimed partial or full solution. One claimed full proof was published and withdrawn within days (Cruz–Lai–Pramanik, arXiv:2001.02395, Jan 2020 — gap in Prop. 3.3 found by V. Kovač), which is strong, direct evidence of just how close-but-still-failing the best available Cantor-construction techniques are.

What is resolved, comprehensively, is a wide lattice of special cases and variant problems, all surveyed above: (i) all sublacunary sequences (Falconer 1984 / Eigen 1985, reproved via bi-Lipschitz methods by Feng–Lai–Xiong 2024); (ii) sumsets of $\ge3$ infinite sets (Bourgain 1987); (iii) the *bi-Lipschitz* relaxation of the whole problem, completely dichotomized (Feng–Lai–Xiong 2024); (iv) Cantor sets of positive Newhouse thickness (Gallagher–Lai–Weber 2023) or positive Hausdorff dimension (Shmerkin, via Shmerkin–Suomala martingales); (v) the *topological* analog, fully classified via strong-measure-zero / the Borel conjecture, hence independent of ZFC in its uncountable-set form (Gallagher–Lai–Weber 2023, Jung–Lai 2024); (vi) the "in the large" dual for unbounded sequences, fully resolved for linear and all subexponential sequences (Bradford–Kohut–Mooroogen 2023, Kolountzakis–Papageorgiou 2022, Gao–Mooroogen–Yip 2024) and partially for $(2^n)$ ($p<1/2$, Gao–Mooroogen–Yip via Dubickas's theorem on algebraic-number distribution mod 1). None of these variants, however, resolves the master conjecture; JLM24 is explicit that "there is still no precise statement saying the Erdős similarity problem and the Erdős similarity problem in the large are actually equivalent."

Formalized in Lean (google-deepmind/formal-conjectures, FormalConjectures/ErdosProblems/120.lean, read in full 2026-07-02): the main statement erdos_120 and Steinhaus's finite-set sub-lemma erdos_120.variants.finite_set are both stated but sorry'd — no machine-checked proof of anything exists yet, consistent with problems.yaml's formalized: {state: yes, last_update: 2026-01-23} meaning "statement formalized," not "proved." Per the erdosproblems.com AI-contributions wiki (section 1(b) "AI alongside literature" and section 2(a) "Literature search"), on 14 Mar 2026 both a DeepMind prover agent and GPT-5.4 Thinking independently touched #120, each producing a "solution to a variant problem" (not the conjecture itself); the DeepMind entry cross-references de Reyna's 1983 Baire-category-dual paper as *comparable but not the same* approach ("Similar? No").

Attack surface

- Mode: derivation (the realistic mode — this is provably not finite-search-resolvable, and the site + 2024 survey + the 2020 withdrawn-proof episode all indicate the master conjecture needs genuinely new technique, not more computation) with a strong secondary literature-resolution angle (re-check post-Jan-2025 arXiv for any successor to JLM24 or to the withdrawn Cruz–Lai–Pramanik paper; the AI-contributions wiki shows this problem is *actively* being probed by frontier AI systems as of Mar 2026, so a fresh check for late-2026 activity is cheap and worthwhile). - Concrete first experiment (not a proof-search, but real progress-shaped work): (1) formalize in Lean, and fill the sorry on, the *already-published, already-checked-by-humans* special cases — start with Steinhaus's finite-set lemma (erdos_120.variants.finite_set, currently sorry'd despite being 100+ years old and elementary via the Lebesgue density theorem) and the Falconer–Eigen sublacunary theorem, both of which are short, self-contained, and would harden the existing formal-conjectures scaffold; (2) attempt to close the *specific* gap that sank Cruz–Lai–Pramanik's Prop. 3.3 (obtain the actual withdrawn preprint text/errata if archived, e.g. via arXiv's version history or the authors, and check whether the Newhouse-thickness (Gallagher–Lai–Weber 2023) or spatially-independent-martingale (Shmerkin–Suomala) machinery — developed by *the same research group* in the years right after the retraction — patches exactly that hole for the still-uncovered case (Newhouse thickness zero AND Hausdorff dimension zero); (3) push on the single sharpest open sub-case, $A=(2^{-n})$, using the "in the large" dual's EE$^{-1}$-sumset criterion (Lemma 6.3 of JLM24) transplanted to the measure setting via the Prop. 3.2 sumset equivalence — check whether $EE^{-1}\neq\mathbb R$ is achievable for a measure-zero $E$ built from Dubickas's density-mod-1 estimate for $2^n$ (already used in the "in the large" setting to get $p<1/2$; JLM24 explicitly note the analogous measure-side estimate is open). - Oracle: none mechanical for the main conjecture — it needs a genuine proof (or, for a "no"/counterexample resolution, an *explicit infinite measure-universal set*, which — since Kolountzakis's Theorem 1.6 shows any candidate must be extraordinarily fine-tuned against a two-parameter family of dilations/translations simultaneously — is not something a finite search over any bounded description length could certify as universal against *all* measurable $E$; it would itself need a proof that the construction works). For the *sub-tasks* above (Lean-formalizing known lemmas, checking the Prop 3.3 gap, testing the EE$^{-1}$ criterion on $2^{-n}$), the oracle is standard: Lean typechecking for (1), careful human/LLM proof-review for (2)-(3) since these remain proof-shaped, not search-shaped, tasks. - Feasibility: honest read — this is a genuinely hard, 50+-year-old flagship open problem with an active, well-organized modern research program (Lai's SFSU group + collaborators, 2023–2025) that has resolved essentially every accessible special case and variant *except* the core conjecture, and has one documented, painful near-miss (a full proof claimed and retracted within days in 2020). It is not remotely a finite-search target and is unlikely to fall to brute derivation without a genuinely new idea — the two most promising transferable pieces of machinery already in hand are (a) spatially-independent martingales / Frostman-measure smoothing (Shmerkin–Suomala), which is the newest and most powerful tool in this exact literature and has already knocked out the positive-Hausdorff-dimension case, and (b) the metric-number-theory density-modulo-1 estimates from the "in the large" dual program, which are the only known route (via Dubickas) to any *partial* progress on genuinely exponential/lacunary sequences like $(2^{-n})$ on the measure side. A realistic, bounded-effort contribution is Lean-formalizing the solved special cases (cheap, valuable, currently untouched) rather than attacking the master conjecture directly.

Related

- concept/lebesgue-density-theorem — the mechanism behind Steinhaus's classical finite-set universality result and behind every "fast-decreasing sequence embeds near a density point" construction (Feng–Lai–Xiong's bi-Lipschitz case (2), Kolountzakis's Theorem 1.6). - concept/bi-lipschitz-embedding — Feng–Lai–Xiong's (2024, *IMRN*) fully-resolved sharp dichotomy for the bi-Lipschitz-relaxed version of #120: not universal iff sublacunary ($a_{n+1}/a_n\to1$), universal (constructively) iff $\limsup a_{n+1}/a_n<1$. The single cleanest completely-solved analog to study for proof technique transfer. - concept/newhouse-thickness-gap-lemma — Gallagher–Lai–Weber's (2023) tool: two Cantor sets with thickness product $\ge1$, neither nested in the other's gaps, must intersect; used to show positive-Newhouse-thickness Cantor sets are not measure universal. - concept/spatially-independent-martingales — Shmerkin–Suomala's (Mem. AMS 2018) machinery for smoothing a Frostman measure against every affine image of a fractal simultaneously with Hölder-continuous density; the tool behind the positive-Hausdorff-dimension Cantor-set non-universality result and the newest/most powerful technique in this literature. - concept/full-measure-universality-sumset-equivalence — Jasinski (1996) / Jung–Lai–Mooroogen (2024) Prop. 3.2: universality of $X$ is equivalent to a sumset non-covering condition $X+\lambda M\neq\mathbb R$ for all measure-zero $M$ and all $\lambda\neq0$; connects directly to Erdős–Kunen–Mauldin (1981) and reframes the whole conjecture as additive combinatorics against null sets. - concept/strong-measure-zero-borel-conjecture — the topological analog of #120 is fully classified: topologically universal $\Leftrightarrow$ strong measure zero, so existence of uncountable topologically-universal sets is independent of ZFC (Borel conjecture, Laver 1976). - concept/erdos-similarity-in-the-large — the dual problem for unbounded increasing sequences and $p$-large sets (Bradford–Kohut–Mooroogen 2023, Kolountzakis–Papageorgiou 2022, Gao–Mooroogen–Yip 2024); fully solved for linear/subexponential growth, partially for $(2^n)$; results transfer back to genuine positive-measure sets near a density point (Burgin et al. 2023) and are the strongest concrete methodological bridge to #120 currently known. - concept/metric-number-theory-density-modulo-one — Boshernitzan / Pollington–de Mathan / Dubickas estimates on $\{y:(ya_n)\bmod1\text{ not dense}\}$, the key input to every "in the large" non-universality result and the most promising route to *any* progress on genuinely exponential $A$ like $(2^{-n})$. - concept/kolountzakis-probabilistic-avoidance — Kolountzakis's (1997) random-interval-selection technique, generalizing Falconer–Eigen and producing the almost-everywhere solution (Theorem 1.6): universal sets, if they exist, must be adversarially fine-tuned against a measure/dimension-zero set of dilation parameters.