1
$\begingroup$

Given a nonnegative integer $d$, what is the length $L$ of longest squarefree arithmetic progression with difference $d$?

Conjecture: $L = p^2 - 1$, where $p$ is the smallest prime not dividing $d$.

It is easy to see that $L \leq p^2 - 1$ (consider the progressions $(n, n+d, ... , n+p^2\cdot d)$ modulo $p^2$). For all $d<=200$ and for many other values of $d$ I have checked that the inequality is in fact an equality.

For example, if $d = 30030 = 2\cdot3\cdot5\cdot7\cdot11\cdot13$, then $p = 17$ and the progression with difference $d$ starting at $n=108349$ and having length $p^2-1 = 288$ consists of squarefree numbers.The "framing" numbers of this sequence, $n-d = 17^2\cdot271$ and $n+288\cdot d=17^2\cdot30301$, both contain the square of $p$. Also,there is no squarefree arithmetic progression for this $d$ starting at a smaller $n$.

Can one prove or disprove my conjecture?

$\endgroup$
1
$\begingroup$

I believe this is correct, though I can't close a hole proving that it is at least $p^2-1$.

To show it is at most $p^2-1$, note that $d$ is coprime to $p^2$. The elements of the series will cycle through all the residues $\bmod p^2$. You will hit a number equivalent to $0 \bmod p^2$ every $p^2$ numbers, so the longest run without one will be $p^2-1$.

For any finite set of primes $p_i$ we can show there is a run of $p^2-1$ numbers not divisible by the square of any of them. We might as well take $p_1=p$. We can then use the Chinese Remainder Theorem to solve the equations $n \equiv d \pmod {p_i^2}$ simultaneously. The numbers $n,n+d,n+2d \ldots n+(p^2-1)d$ will not be divisible by the square of any of them. I don't see how to extend this to infinite sets of primes.

$\endgroup$
  • $\begingroup$ Thank you for your answer! But I do not understand the argument: If, for example, I have $d=3$, then $p=2$ and $L=p^2-1=3$. A solution for $n\equiv d$ ($\mod q^2$) for all primes $q$ is $n=3$, but $(3,6,9)$ is not squarefree. (The smallest $n$ in this case is $n=7$: The progression $(7, 10, 13)$ is squarefree.) $\endgroup$ – Anny One Apr 5 at 11:36
  • $\begingroup$ I did not say that any progression of $p^1-1$ is squarefree, just that you could find one. You need to start with a number equivalent to $d \pmod {p^2}$ for every prime dividing $d$, but you also need to miss the squares of other primes. My worry about infinite sets of primes is exactly that. Maybe every sequence of length $d$ hits one of them or another. I doubt it ever does, but I couldn't prove it. $\endgroup$ – Ross Millikan Apr 5 at 13:28
1
$\begingroup$

I did find a proof for the above conjecture.

There is a theorem about tuples of the form $(n+l_1, n+l_2,\ldots,n+l_s)$ which when specialized to $l_i=i\cdot d$ for $i=0,\ldots,p^2-1$ says that for large $n$ the percentage of squarefree tuples among them is about $P=\Pi_q(1-u(q)/q^2)$, where $u(q)=1$ if $q$ divides $d$ and $u(q)=p^2-1$ otherwise. This includes the existence of such tuples! The proof is via sieve methods.

I would still be interested in having a more direct proof.

The above theorem seems to have been first proved by the Indian mathematician S. Pillai (On the set of square free numbers, Jour. Indian Math. Soc., New series, II (1936), 116-118).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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