This is related to Sum of Fibonacci sequence evaluated at a Dirichlet character, but can be also be considered as a stand-alone.

I did an exhaustive search on non-principal (not necessarily primitive) Dirichlet characters $\chi$ of modulus $\leq 12$ such that $\chi(F_n)\in\{0,1\}$ to get a better understanding of the "bad" characters in the quoted question. None was found. Maybe more computing power can help here.

Q: Can you provide a non-principal Dirichlet character $\chi$ of moderately small modulus (such that it still can be handled by a human for the above purpose) such that $\chi(F_n)\in\{0,1\}$ for all Fibonacci numbers $F_n$, $n\in\mathbb{N}$.

Of course, I would also be interested in a primitive example, in negative results for certain moduli or in cleverer approaches to construct/find such an example.

  • $\begingroup$ Your link said "question", but it actually went to your answer, which seemed likely to be a mistake. I edited accordingly. If you wanted the link to go to your answer, then I apologise; please feel free to roll it back. $\endgroup$
    – LSpice
    May 4, 2021 at 17:44
  • $\begingroup$ I did a search using Pari/GP (this is easy because Dirichlet characters are already implemented). If my code is correct then there is no such character of modulus $\leq 2000$. Of course one can adapt the code to do some experiment, like what is the least $n$ such that $\chi(F_n) \neq 0,1$, for a given $\chi$. I can put the code in an answer if you think this is useful. $\endgroup$ May 4, 2021 at 18:02
  • 3
    $\begingroup$ For a modulus $N$, there is a Dirichlet character modulo $N$ with the desired property iff the Fibonacci number coprime to $N$ generate a proper subgroup of $(\mathbb Z/N\mathbb Z)^\times$, so this is a problem which isn't really about Dirichlet characters at all. I have verified Fibonacci numbers span the entire subgroup for $N\leq 3000$ (using a very inefficient algorithm; I'm sure one can do better) $\endgroup$
    – Wojowu
    May 4, 2021 at 18:10
  • 1
    $\begingroup$ Pari/GP can decompose $G = (\mathbb{Z}/N\mathbb{Z})^\times$ as a direct sum of cyclic groups, and compute the vector representation of a given $x \in G$. Then using Wojowu's remark, we need to check whether the $F_n$ generate $G$, and this can be done by computing the Hermite normal form. $\endgroup$ May 4, 2021 at 18:57
  • 5
    $\begingroup$ I implemented Wojowu's idea and this is vastly faster: if my code is correct, there is no such Dirichlet character for $N \leq 10^6$ (took 2min 30s). $\endgroup$ May 4, 2021 at 20:03


Your Answer

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