Translation property: sums of two squares, prime-restricted sets, and squarefree shift growth (Erdős #675)
Statement
Say that a set $A\subseteq\mathbb{N}$ has the translation property if for every $n$ there exists an integer $t_n\geq 1$ such that, for all $1\leq a\leq n$, $$a\in A\iff a+t_n\in A.$$ (Equivalently, the indicator of $A$ agrees with a shift of itself on the entire initial segment $\{1,\ldots,n\}$.) Erdős asks three questions. (1) Does the set of sums of two squares have the translation property? (2) If the primes are partitioned as $P\sqcup Q$ with each part containing $\gg x/\log x$ primes up to $x$ for all large $x$, can the set of integers divisible only by primes from $P$ have the translation property? (3) If $A$ is the set of squarefree numbers, how fast does the minimal valid $t_n$ grow — in particular, is $t_n>\exp(n^c)$ for some constant $c>0$?
Acceptance. FULLY RESOLVES: settle all three questions with proofs — determine whether the set of sums of two squares has the translation property; determine whether the $P$-restricted set can have it under the stated density hypothesis; and determine the growth rate of the minimal $t_n$ for the squarefree numbers (in particular prove or disprove $t_n>\exp(n^c)$ for some $c>0$). ADVANCES: completely settle any one of the three questions with a proof; or establish a rigorous upper or lower bound on the minimal squarefree shift $t_n$ (for example a proof that $t_n>\exp(n^c)$, or an unconditional upper bound); or compute the minimal $t_n$ for the squarefree set over an extended, reproducible range and exhibit certified growth data. Deliver the proof(s), the bound, or the computation with a reproducibility certificate.
Background
Posed by Erdős [Er79]; listed as open on erdosproblems.com/675 (fetched 2026-07-21, status 'open'). Elementary sieve theory shows that the set of squarefree numbers does have the translation property, so question (3) concerns the growth rate of the shift $t_n$ rather than its existence. More generally, Brun's sieve gives that if $B\subseteq\mathbb{N}$ is a set of pairwise coprime integers with $\sum_{b<x}1/b=o(\log\log x)$, then $A=\{n:b\nmid n\text{ for all }b\in B\}$ has the translation property; Erdős did not know what happens when the condition on $\sum_{b<x}1/b$ is weakened or dropped, which is the crux of questions (1) and (2) — both concern sets (sums of two squares, and $P$-restricted integers) defined by prime conditions too dense for this criterion. The attacker's tool: sieve theory and the distribution of the relevant sets in short intervals for the structural questions, together with direct computation of the minimal shifts $t_n$ for the squarefree set to pin down their growth.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #675 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.