16
$\begingroup$

Caveat: I am not at all a number theorist, and I randomly came up with the following question while I was hiking. But I already asked two serious number theorists, and since they did not know the answer to my question, I decided to pose it here.

Let $c > 0$ be given. Suppose $a_1,a_2,a_3,\dots$ is a sequence of positive integers such that for all primes $p > c$, we have $a_i \equiv a_j \ (\text{mod}. p)$ if and only if $i \equiv j \ (\text{mod}. p)$. Does it follow that $(a_i)$ is an arithmetic progression, i.e. there are integers $a$ and $b$ such that $a_k = a + kb$?

$\endgroup$
  • $\begingroup$ A minor comment, but , since only the gaps count, you can adjust the indexing , weaken to non-negative, and assume $a_0=0$ then for $k > c$ we have that $a_k$ has all the prime factors of $k$ with the possible inclusion or exclusion of primes less than $c+1$ $\endgroup$ – Aaron Meyerowitz May 1 '17 at 0:56
  • $\begingroup$ The answer already given below, a next natural question is whether it would be enough to require the same conditions but, instead of all primes $>c$, only for some infinite set of primes. $\endgroup$ – მამუკა ჯიბლაძე May 1 '17 at 6:19
20
$\begingroup$

For each $n$, the differences $a_{n+1}-a_n$, $a_{n+2}-a_{n+1}$, and $a_{n+2}-a_n$ can only be divisible by powers of $2$ and primes less than or equal to $c$. Since $$ \frac{a_{n+2}-a_{n+1}}{a_{n+2}-a_n}+\frac{a_{n+1}-a_n}{a_{n+2}-a_n}=1, $$ this is a solution to the S-unit equation, where $S=\{2\}\cup\{p:p\leq c\}$. This means the sequence $x_n:=(a_{n+1}-a_n)/(a_{n+2}-a_n)$ can only take on finitely many values as $n$ varies.

Let $p$, $p'>c$ be distinct primes each not dividing the numerator of any of the finitely many distinct non-zero values of $x_n - x_{n'}$. Then the sequence $x_n$ has period dividing $p$ and $p'$, hence is constant. Say $x_n=k$ for all $n$. This implies $$a_{n+2}-a_{n+1}=\frac{1-k}{k}(a_{n+1}-a_n),$$ i.e. the differences $a_{n+1}-a_n$ form a geometric progression. Hence either $a_n$ is an arithmetic progression (if the common ratio $(1-k)/k$ is $1$), or $a_n$ has the form $$ a_n = bc^n+d, $$ with $b$, $c$, $d\in\mathbb{Z}$. The latter case cannot happen, as Fermat's Little Theorem would imply $a_{n+p-1}\equiv a_n\mod p$ for $p$ sufficiently large.

$\endgroup$
  • $\begingroup$ I thought I found a computational counterexample (haven't double checked), but a proof clearly beats that! $\endgroup$ – kodlu Apr 30 '17 at 23:59
  • 4
    $\begingroup$ It seems to me that the S-unit equation only implies that the fraction $(a_{n+2}-a_{n+1})/(a_{n+1}-a_n)$ takes finitely many values. But this is enough for your argument to go through. One just has to rule out sequences of the form $ab^n+c$. $\endgroup$ – Gjergji Zaimi May 1 '17 at 0:18
  • $\begingroup$ @GjergjiZaimi Yes, thank you. I amended the argument. $\endgroup$ – Julian Rosen May 1 '17 at 1:14

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.