# Sum of Fibonacci sequence evaluated at a Dirichlet character

Let $$F_n$$ be the Fibonacci sequence and $$\chi$$ a non-principal primitive Dirichlet character. Does there exist $$n$$ such that $$\chi(F_n) \neq 0,1$$?

One way to prove this would be to obtain non-trivial bounds for sums of the shape $$\sum_{n \leq x} \chi(F_n)$$.

It is foreseeable that there could be some "bad" Dirichlet characters where one does not obtain the result, so I'm very happy to ignore finitely many Dirichlet characters of any given order (say).

More generally, I'd like to know a version of this where $$F_n$$ is replaced by an arbitrary Lucas sequence.

• This cannot hold for an arbitrary Lucas sequence, since the Pell numbers (0,1 then $x_{n+1}=2x_n+x_{n-1}$) only take on the values $0,1,2\pmod{4}$, and so the non-principal character modulo 4 is only $0,1$ on this sequence. Oct 23, 2020 at 10:11
• Hi Thomas. Thanks for the great example. But still it seems like you have highlighted a "bad" Dirichlet character; do you know any examples for which one needs to exclude infinitely many Dirichlet characters of fixed order? Oct 23, 2020 at 10:14
• Not at all (and indeed I'd bet on that version being true, since I'd imagine that the only thing that can go wrong is due to 'law of small numbers' phenomena). I just wanted to provide an easy example to show that the very strong statement (i.e. for all Lucas sequences and all characters) is false. Oct 23, 2020 at 10:16
• Of course now I type it I realise that I didn't even need to go that far, since we can just break it for trivial reasons for any fixed modulo $m$ say by choosing $0,m$ then $x_{n+1}=mx_n+mx_{n-1}$. But perhaps the Pell numbers modulo 4 are still worth noting as a 'not completely trivial' example. Oct 23, 2020 at 10:19

The question is not new. In April 2014 I conjectured that for any prime $$p>3$$ there is a positive Fibonacci number $$F_n such that $$\left(\frac{F_n}p\right)=-1$$, where $$(-)$$ is the Legendre symbol. See http://oeis.org/A241568 for related data. Moreover, in Section 2 of a published paper available from http://maths.nju.edu.cn/~zwsun/195g.pdf, I gave some heuristic arguments to support this, and also presented some similar conjectures for Lucas numbers.
• Your conjecture imposes the assumption that the Fibonacci number is "small" (namely $F_n < p/2$), which I am not imposing. Is this equivalent to my question? Oct 23, 2020 at 11:12
• Fibonacci numbers modulo an odd prime are periodic. If $0<F_n<p/2$ and $\chi(a)=\left(\frac ap\right)$, then surely $\chi(F_n)\not=0,1$ if $F_n$ is a quadratic nonresidue modulo $p$. If $\chi$ is the Legendre symbol $\left(\frac{\cdot}p\right)$, then my conjecture is even stronger than a positive answer to your question for $\chi$. Oct 23, 2020 at 11:22
• Yes I understand that your conjecture is stronger than my question, which is exactly why I asked my comment. I want something which is weaker than you conjecture, so my question may be hopefully easier to answer. Why do you impose the condition $F_n < p/2$ anyway? It looks fairly artificial. Oct 23, 2020 at 11:34
• Fibonacci numbers grow exponentially. There are only $O(\log p)$ Fibonacci numbers below $p$. My original purpose is to find a quadratic nonresidue mod $p$ quickly. Oct 23, 2020 at 12:38
This is a partial answer. Let $$\chi$$ be a Dirichlet character of modulus $$k$$. Let $$\alpha(k)$$ denote the rank of apparition of $$k$$, that is the smallest index $$n$$ (larger than zero) such that $$k|\mathcal{F}_n$$. If $$\alpha(k) \text{ is odd}$$ and $$\chi(-1)\not=1$$ then $$\chi(\mathcal{F}_{\alpha(k)-1}) \not\in \{0,1\}.$$ Proof. We assume $$\chi(\mathcal{F}_{\alpha(k)-1})=0$$. The definition of the Fibonacci numbers implies $$\begin{array}{c|ccccccc} n & \ldots & \alpha(k)-3 & \alpha(k)-2 & \alpha(k)-1 & \alpha(k) & \alpha(k) + 1 & \alpha(k)+2 \\ \hline \mathcal{F}_n \mod k & \ldots & 2 \mathcal{F}_{\alpha(k)-1} & - \mathcal{F}_{\alpha(k)-1} & \mathcal{F}_{\alpha(k)-1} & 0 & \mathcal{F}_{\alpha(k)-1}& \ldots \end{array}$$ that the whole sequence $$\chi(\mathcal{F}_n)$$ is $$0$$, which is a contradiction. To exclude the other case, we assume $$\chi(\mathcal{F}_{\alpha(k)-1})=1$$. Since, by extending the above table all the way down to $$n=1$$, $$\mathcal{F}_{\alpha(k)-1}^2 \equiv (-1)^{\alpha(k)} \mod k$$ we have by assumption $$\mathcal{F}_{\alpha(k)-1}^2 \equiv -1 \mod k$$. If we now apply the character we get $$1=\chi(\mathcal{F}_{\alpha(k)-1})^2 = \chi(-1)\not=1$$, a contradiction.
If the modulus $$k$$ of the character is prime the above is true without any restriction on $$\alpha(k)$$. In that situation either $$\mathcal{F}_{\alpha(k)-1}= -1$$ or $$\mathcal{F}_{\alpha(k)-2}= -1$$.