On the discriminator of Lucas sequences. II

Abstract

The family of Shallit sequences consists of the Lucas sequences satisfying the recurrence $U_{n+2}(k)=(4k+2)U_{n+1}(k)-U_n(k),$ with initial values $U_0(k)=0$ and $U_1(k)=1$ and with $k\ge 1$ arbitrary. For every fixed $k$ the integers $\{U_n(k){\}}_{n\ge 0}$ are distinct, and hence for every $n\ge 1$ there exists a smallest integer $D_k(n)$, called discriminator, such that $U_0(k),U_1(k),\dots ,U_{n-1}(k)$ are pairwise incongruent modulo $D_k(n).$ In part I it was proved that there exists a constant $n_k$ such that $D_k(n)$ has a simple characterization for every $n\ge n_k$. Here, we study the values not following this characterization and provide an upper bound for $n_k$ using Matveev's theorem and the Koksma-Erdos-Turán inequality. We completely determine the discriminator $D_k(n)$ for every $n\ge 1$ and a set of integers $k$ of natural density $68/75$. We also correct an omission in the statement of Theorem 3 in part I.

25 pages, 7 tables