Growth rates of sequences governed by the squarefree properties of its translates

What's new 2025-12-02

Wouter van Doorn and I have uploaded to the arXiv my paper “Growth rates of sequences governed by the squarefree properties of its translates“. In this paper we answer a number of questions of Erdős} (Problem 1102 and Problem 1103 on the Erdős problem web site) regarding how quickly a sequence ${A = \{a_1 < a_2 < \dots\}}$ of increasing natural numbers can grow if one constrains its translates ${n+A}$ to interact with the set ${\mathcal{SF} = \{1,2,3,5,6,7,10,\dots\}}$ of squarefree numbers in various ways. For instance, Erdős defined a sequence ${A}$ to have “Property ${P}$ ” if each of its translates ${n+A}$ only intersected ${\mathcal{SF}}$ in finitely many points. Erdős believed this to be quite a restrictive condition on ${A}$ , writing “Probably a sequence having property P must increase fairly fast, but I have no results in this direction.”. Perhaps surprisingly, we show that in fact, while these sequences must be of density zero, they can grow arbitrary slowly in the sense that one can have ${a_j \leq j f(j)}$ for all sufficiently large ${j}$ and any specified function ${f(j)}$ that tends to infinity as ${j \rightarrow \infty}$ . For instance, one can find a sequence that grows like ${O(j \log\log\log j)}$ . The density zero claim can be proven by a version of the Maier matrix method, and also follows from known moment estimates on the gaps between squarefree numbers; the latter claim is proven by a greedy construction in which one slowly imposes more and more congruence conditions on the sequence to ensure that various translates of the sequence stop being squarefree after a certain point.

Erdős also defined a somewhat complementary property ${Q}$ , which asserts that for infinitely many ${n}$ , all the elements ${n+a}$ of ${A}$ for ${a \leq n}$ are square-free. Since the squarefree numbers themselves have density ${6/\pi^2}$ , it is easy to see that a sequence with property ${Q}$ must have (upper) density at most ${6/\pi^2}$ (because it must be “admissible” in the sense of avoiding one residue class modulo ${p^2}$ for each ${p}$ ). Erdős observed that any sufficiently rapidly growing (admissible) sequence would obey property ${Q}$ but beyond that, Erd\H{o}s writes “I have no precise information about the rate of increase a sequence having property Q must have.”. Our results in this direction may also be surprising: we show that there exist sequences with property ${Q}$ with density exactly ${6/\pi^2}$ (or equivalently, ${a_j \sim \frac{\pi^2}{6} j}$ ). This requires a recursive sieve construction, in which one starts with an initial scale ${n}$ and finds a much larger number ${n'}$ such that ${n'+a}$ is squarefree for most of the squarefree numbers ${a \leq n'}$ (and all of the squarefree numbers ${a \leq n}$ ). We quantify Erdős’s remark by showing that an (admissible) sequence will necessarily obey property ${Q}$ once it grows significantly faster than ${\exp( C j \log j)}$ , but need not obey this property if it only grows like ${\exp(O(j^{1/2} \log^{1/2} j))}$ . This is achieved through further application of sieve methods.

A third property studied by Erd\H{o}s is the property of having squarefree sums, so that ${a_i + a_j}$ is squarefree for all ${i,j}$ . Erdős writes, “In fact one can find a sequence which grows exponentially. Must such a sequence really increase so fast? I do not expect that there is such a sequence of polynomial growth.” Here our results are relatively weak: we can construct such a sequence that grows like ${\exp(O(j \log j))}$ , but do not know if this is optimal; the best lower bound we can produce on the growth, coming from the large sieve, is ${\gg j^{4/3}}$ . (Somewhat annoyingly, the precise form of the large sieve inequality we needed was not in the literature, so we have an appendix supplying it.) We suspect that further progress on this problem requires advances in inverse sieve theory.

A weaker property than squarefree sums (but stronger than property ${Q}$ ), referred to by Erdős as property ${\overline{P}}$ , asserts that there are infinitely many ${n}$ such that all elements of ${n+A}$ (not just the small ones) are square-free. Here, the situation is close to, but not quite the same, as that for property ${Q}$ ; we show that sequences with property ${\overline{P}}$ must have upper density strictly less than ${6/\pi^2}$ , but can have density arbitrarily close to this value.

Finally, we looked at a further question of Erdős on the size of an admissible set ${A}$ . Because the squarefree numbers are admissible, the maximum number ${A(x)}$ of elements of an admissible set ${A}$ up to ${x}$ (OEIS A083544) is at least the number ${|{\mathcal SF} \cap [x]|}$ of squarefree elements up to ${x}$ (A013928). It was observed by Ruzsa that the former sequence is greater than the latter for infinitely many ${x}$ . Erdős asked, “Probably this holds for all large x. It would be of some interest to estimate A(x) as accurately as possible.”

We are able to show

$\displaystyle \frac{\sqrt{x}}{\log x} \ll A(x) - \frac{6}{\pi^2} x \ll x^{4/5},$

with the upper bound coming from the large sieve and the lower bound from a probabilistic construction. In contrast, a classical result of Walfisz shows that

$\displaystyle |{\mathcal SF} \cap [x]| - \frac{6}{\pi^2} x \ll x^{1/2} \exp(-c \log^{3/5} x / (\log\log x)^{1/5}).$

Together, this implies that Erdős’s conjecture holds ${A(x) > |{\mathcal SF} \cap [x]|}$ for all sufficiently large ${x}$ . Numerically, it appears that in fact this conjecture holds for all ${n>17}$ :

However, we do not currently have enough numerical data for the sequence ${A(x)}$ to completely confirm the conjecture in all cases. This could potentially be a crowdsourced project (similar to the Erdős-Guy-Selfridge project reported on in this previous blog post).