9
$\begingroup$

This question gained no attention at Math SE.

Call a sequence of $k$ consecutive naturals squary if each one of them is divided by a square > 1. The Chinese Remainder theorem trivially guarantees us squary $k$-sequences for each $k$ (even with pre-defined divisors in a given order).

Denote by $f(k,n)$ the number of squary sequences $(x+1,x+2,...,x+k)$ contained in $[1,n]$. For $k$ fixed and $n\to\infty$, what is known about the asymptotics of $f(k,n)$?

It is easy to show that $f(1,n)\sim (1-\frac6{\pi^2})n $.

$\endgroup$
4
  • $\begingroup$ Possibly related: mathoverflow.net/questions/149194/… $\endgroup$
    – Wolfgang
    Dec 8, 2013 at 15:46
  • 2
    $\begingroup$ This answers the opposite: the density of runs of square-free integers has been worked out by L Mirsky, Note on an asymptotic formula connected with r-free integers. Quart. J. Math., Oxford Ser. 18, (1947). 178–182, (and some more related papers by Mirsky). I do not currently have access to the paper, but would hope that the same methods can be adapted to answer your question, maybe just by some combinatorial inclusion-exclusion. $\endgroup$ Dec 8, 2013 at 16:46
  • 6
    $\begingroup$ Christian Elsholtz's comment points to the solution. From Mirsky's work and inclusion exclusion one gets that $f(k,N) \sim C(k) N$ for a constant $C(k)>0$. For example $C(2)=1-12/\pi^2+\prod_p(1-2/p^2)=0.121...$. What's interesting is how $C(k)$ behaves with $k$: it seems to decay like $k^{-(c+o(1))k}$ for a suitable constant $c$. In other words the probability of finding $k$ consecutive non-squarefree numbers is much smaller than if they were independent. The $k^{-ck}$ feature also ties up with the $\log n/\log \log n$ behavior for the linked consecutive non-squarefree numbers question. $\endgroup$
    – Lucia
    Dec 8, 2013 at 22:15
  • $\begingroup$ @Lucia: I'm wondering if inclusion-exclusion can yield that from the opposite. Because that's the thing: I'd think the non-squarefree numbers must be "independent" for that. E.g. I am not sure that the heuristical argument "$C(2)N$ is the expected number of neighboring pairs when choosing $C(1)N$ equally distributed numbers among $\lbrace1,...,N\rbrace$" is OK. BTW, can you provide a closed form of $C(3)$? And how did you come up the interesting idea of a $k^{-ck}$ decay? A posteriori from the $\log n/\log \log n$ ?? In any case, I'd suggest you write all that as an answer. $\endgroup$
    – Wolfgang
    Dec 9, 2013 at 15:26

2 Answers 2

11
$\begingroup$

At the request of Wolfgang, I'll provide a few more details of my comment. Let $K=\{k_1,\ldots, k_{\ell}\}$ be any set of $\ell$ distinct natural numbers, and put $\nu(K,p)$ to be the number of distinct residue classes among the elements of $K$ taken $\pmod{p^2}$. Then Mirsky's result says that $$ \sum_{n\le x} \prod_{j=1}^{\ell}\mu(n+k_j)^2 \sim C_0(K) x $$ where $$ C_0(K) = \prod_{p} \Big(1 -\frac{\nu(K,p)}{p^2}\Big). $$ This is analogous to the Hardy-Littlewood conjecture for prime $k$-tuples, but much easier to prove. Mirsky worked out good error terms in the asymptotic formula above; many others have worked on precise asymptotic formulae in such problems, for example Heath-Brown looked at the special case when $K=\{1,2\}$ carefully.

The problem in question asks for $$ \sum_{n\le x} \prod_{j=1}^{k} (1-\mu(n+j)^2) $$ and expanding out the product we get that this is $$ \sum_{n\le x} \sum_{K \subset \{1,\ldots, k\}} (-1)^{|K|} \prod_{j\in K} \mu(n+j)^2, $$ which by Mirsky's result is $$ \sim x \sum_{K\subset \{1,\ldots, k\}} (-1)^{|K|} C_0(K) \sim C(k) x, $$ for a suitable constant $C(k)$.

As noted in my comment it is now easy to see that $$ C(2) = 1- 2 \frac{6}{\pi^2} + C_0(\{1,2\}) = 1-\frac{12}{\pi^2}+ \prod_p \Big(1-\frac{2}{p^2}\Big). $$ Further $$ C(3) =1-\frac{18}{\pi^2} + 3 \prod_{p} \Big(1-\frac{2}{p^2} \Big) - \prod_p \Big(1-\frac{3}{p^2}\Big); $$ $$ C(4)=1-\frac{24}{\pi^2}+6\prod_p \Big(1-\frac{2}{p^2}\Big) -4\prod_p\Big(1-\frac{3}{p^2}\Big). $$ From $C(5)$ on, things will be more messy.

Added: In my comment to the question I noted that $C(k)$ seems to decay like $k^{-(c+o(1))k}$ for large $k$ and this is in keeping with the $\log n/\log \log n$ behavior in the related question on long gaps between square-free numbers. In this context, I recently came across a paper by Geoffrey Grimmett which proves that $C(k)=k^{-(6/\pi^2+o(1))k}$ as $k \to \infty$. The paper appeared in Math. Proc. Camb. Phil. Soc. in 1997, and the link is to a preprint from the author's homepage.

$\endgroup$
3
$\begingroup$

The original question is answered by Lucia. I was thinking on, what if $k$ depends on $n$? I'm interested on question whether $k = \frac{\log n}{\log\log n}$.

In related question (Consecutive non squarefree integers) we have seen that $f\left(\frac{\log n}{\log\log n},n\right) > 0$ infinitely often.

Now I prove that, for any $\varepsilon$ $$f\left(\frac{\log n}{\log\log n}, n\right) \geq n^{\frac{1}{2}- \varepsilon}$$ infinitely often.

For some $k$ and for some $\pi$ permutation of $\{k+1, k+2, \ldots ,p_k^2\}$ let the following congruence system: $$ \begin{array}{ccll} x_{\pi}& \equiv & k& \mod{p_k^2} \\ x_{\pi}& \equiv & k+1& \mod{p_{\pi(k+1)}^2} \\ & \colon & & \\ x_{\pi}& \equiv & p_k^2& \mod{p_{\pi(p_k^2)}^2} \end{array} $$

The system for any $\pi$ has a solution $x_{\pi}$ smaller than $\Pi_{i=k}^{p_k^2} p_i^2$, and $\{x_{\pi}-k, \ldots, x_{\pi}-p_k^2\}$ can not contain square-free numbers. If $\pi_1 \neq \pi_2$, then the difference between $x_{\pi_1}$ and $x_{\pi_2}$ is at least $p_k^2-k$, because in $\{x_{\pi}-k, \ldots, x_{\pi}-p_k^2\}$ exactly one integer is divisible by $p_i^2$ for $k\leq i \leq p_k^2$, and only $x_{\pi}-k$ is divisible by $p_k^2$, so the intervals $[x_{\pi_1}-p_k^2, x_{\pi_1}-k]$ and $[x_{\pi_2}-p_k^2, x_{\pi_2}-k]$ are not overlapping. From that, there are at least $(p_k^2-k-1)!$ disjoint intervals of size $p_k^2-k$.

So let $m = p_k^2 \sim k^2\log^2k$, there are $(m-o(m^{1/2}))!$ disjoint intervals of size $m-o(m^{1/2})$ which doesn't contain square-free integers until $\Pi_{i=1}^{m} p_i^2 \leq e^{2(1+\varepsilon)m\log m}$. By letting $m = \frac{\log n}{\log\log n}$, the Stirling formula gives the solution.

Remarks: With more carefully written the congruence system, the same holds for $\frac{\pi^2}{6}\frac{\log n}{\log\log n}$. I think this also motivate that, $\frac{\pi^2}{6}\frac{\log n}{\log\log n}$ is not the best lower bound, but the fact $f\left((1+\varepsilon)\frac{\pi^2}{6}\frac{\log n}{\log\log n},n\right) > 0$ happens infinitely often, is not known.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.