# Slowest-growing divisibility sequence?

There are divisibility sequences of the form $$\frac{p^k-1}{p-1}$$ which have the property that if $$a \mid b$$, then $$f(a) \mid f(b)$$, ensuring (among other things) that only prime indices of the sequence can possibly be prime. This form grows as $$2^n$$ with $$p=2$$.

You can find significantly slower growth with the Fibonacci sequence, where the $$n$$th term is $$\frac{\varphi^n-\psi^n}{\sqrt 5} \approx 1.6^n$$.

The slowest-growing form I know of is the recurrence relation defined by $$S_n = S_{n-1} -2 S_{n-2}$$ with $$S_0 = 0, S_1=1$$. I don't know the closed-form expression offhand, but I think it grows as something closer to $$1.4^n$$.

So my question is, are there known slower-growing non-trivial divisibility sequences? By trivial, I'm referring to $$\mathbb{N}$$ or similar. I would guess that you should be able to generate one with an exponent arbitrarily close to $$1$$, but that's just speculation. Better yet, of course, would be one with sub-exponential growth, but I wouldn't be surprised if that were impossible.

Loosely related question: it seems like every prime factor $$a$$ appearing in $$\frac{p^k-1}{p-1}$$ repeats with a period of $$a-1$$ (or one of its divisors) as $$k$$ varies, while every prime factor in Fibonacci-like recurrence relations repeats with a period of $$a-1$$, $$a$$, or $$a+1$$ (or divisors). Are there divisibility sequences where the factors have periods of e.g. $$a-2$$ or $$a+2$$? That is, anything other than $$a$$ or $$a\pm 1$$?

• How about $f(2^a3^b5^c\cdots):=2^{\min\{a,1\}}3^{\min\{b,1\}}\cdots$? Or does this still fit the notion of "trivial"? – Hagen von Eitzen Oct 27 '18 at 14:35
• Btw, $S_n=-i\alpha^n+i\overline \alpha^n=2\operatorname{Im}(\alpha^n)$ where $\alpha=\frac{1+i}{2}$, so that $S_n=O(\sqrt2^n)$. – Hagen von Eitzen Oct 27 '18 at 14:45

Let us consider a linear recurrence of order $$d$$, $$\tag1f(n)=a_1f(n-1)+\ldots + a_df(n-d)$$ where $$a_1,\ldots, a_d\in \Bbb Z$$ (with suitable start values $$f(0),\ldots, f(d-1)$$). As $$d=1$$ leads to constant $$f$$ or growth at least like $$2^n$$, we want to avoid that and assume henceforth that $$d\ge 2$$. Then the closed form is $$\tag2f(n):=c_1\lambda_1^n+\ldots+c_d\lambda_d^n,$$ where the $$\lambda_\nu$$ are the roots of the polynomial $$X^d-a_1X^{d-1}-\ldots -a_d$$ and the $$c_\nu$$ are determined by the inital values. (More precisely, if that polynomial has multiple roots, say $$\lambda$$ is a root of multiplicit $$k$$, then we have summands involving $$\lambda^n, n\lambda^n,n^2\lambda^n,\ldots,n^{k-1}\lambda^n$$ instead of $$k$$ instances of $$\lambda^n$$). It follows that $$n\mapsto f(bn)$$ has a similar closed form and thereby also follows a linear recurrence of order $$d$$.

In order to have a divisibilty sequence, we want $$f(bn)$$ to be a multiple of $$f(b)$$ for all $$n$$. In particular, $$f(0)$$ is a multiple of $$f(b)$$ for all $$b$$; if we want to exclude bounded $$f$$, this necessitates $$f(0)=0.$$ Then to have $$f(b)\mid f(bn)$$ for all $$n$$,

it is necessary and sufficient that $$f(2b),\ldots, f((d-1)b)$$ are multiple of $$f(b)$$.

This is trivially the case if $$d=2$$.

## What can we achieve with $$d=2$$?

First note that we can ignore the case of multiple roots when $$d=2$$: We have a double root $$\lambda_1=\lambda_2=\frac{a_2}2$$ iff $$a_1^2=-4a_2$$. If $$c_1\lambda^n+c_2n\lambda^n$$ is $$0$$ for $$n=0$$, we must have $$c_1=0$$, and in order to have unbounded $$f$$, we must have $$a_1\ge 2$$; we arrive either at a trivial solution of the form $$f(n)=c_2n$$ or at something that grows faster than the OP's $$S_n$$.

So we may assume different roots $$\lambda_{1,2}=\frac{a_1\pm\sqrt{a_1^2+4a_2}}{2}$$. If one of these is rational, then both are and in fact both are integers. This leads either to bounded $$f$$, or to $$f$$ growing at least like $$2^n$$. Hence $$\lambda_{1,2}$$ are irrational. From $$f(0)=0$$, we see $$c_1=-c_2$$ and conclude that the growth of $$(2)$$ is like $$\max\{|\lambda_1|,|\lambda_2|\}^n$$. But $$\max\{|\lambda_1|,|\lambda_2|\}\ge \sqrt{|\lambda_1\lambda_2|}=\sqrt{|a_2|}$$ and $$\max\{|\lambda_1|,|\lambda_2|\}\ge \frac{|lambda_1+\lambda_2|}2=\frac{|a_1|}2$$, so that in order to beat $$\sqrt 2^n$$, we need only consider $$a_2=\pm1$$ and $$|a_1|\le 2$$. The polynomials $$X^2+2X+1$$, $$X^2+X+1$$, $$X^2+1$$, $$X^2-X+1$$, $$X^2-2X+1$$, $$X^2-1$$ lead to roots of unity (sometimes double roots, which we excluded above), hence bounded $$f$$. The polynomials $$X^2\pm 2X-1$$ lead to growth like $$(1+\sqrt 2)^n$$, and the polynomials $$X^2\pm X-1$$ lead to Fibonacchi growth.

It follows that the OP's sequence $$S_n$$ is the slowest non-trivial order $$2$$ recurrence divisibility sequence. Upon closer inspection, $$f(n)=0f(n-1)+2f(n-2)$$ grows precisely as fast

## What if $$d>2$$?

With larger $$d$$, we could clearly bring $$\max\{|\lambda_\nu|\}$$ closer to $$1$$. However, according to our necessary criterion above, we need to ensure that $$f(2b)$$ is a multiple of $$f(b)$$ for all $$b$$ (and more if $$d>3$$). In general, this seems not easily achievable. However, the solution obtained by stretching $$\sqrt2^n$$ apart, $$f(n)=0f(n-1)+0f(n-2)+2f(n-3)$$ of course grows only like $$\sqrt[3]2^n$$, and similarly for higher orders.

• It is customary to define divisibility sequence in the context of sequences indexed by positive integers, thus avoiding the necessity of assuming $f(0) = 0$. – hardmath Sep 12 '20 at 17:17

The smallest growing divisibility sequence I could find which has the properties as $$(x^n-1)/(x-1)$$ has a growth rate of $$ρ^n$$ where $$ρ = 1.32472...$$ is the plastic constant and the only real solution to $$ρ^3-ρ-1=0$$. Thus, the $$n$$-th term of the sequence is of the form $$f(n) = (ρ^n-1)/(ρ-1)$$. The sequence is recursively defined by:

$$[f(1)=1, f(2)=7, f(3)=5, f(4)=11, f(5)=7, f(6)=8, f(7)=5]$$

$$f(n) = 2f(n-2) - 2f(n-4) + 2f(n-6) + f(n-7) - 2$$ for $$n=>7$$

The first $$20$$ terms are: $$1, 7, 5, 11, 7, 8, 5, 7, 11, 23, 35, 53, 64, 77, 85, 103, 133, 191, 275$$