# Quadratic reciprocity via generalized Fibonacci numbers?

This is a pet idea of mine which I thought I'd share. Fix a prime $q$ congruent to $1 \bmod 4$ and define a sequence $F_n$ by $F_0 = 0, F_1 = 1$, and

$\displaystyle F_{n+2} = F_{n+1} + \frac{q-1}{4} F_n.$

Then $F_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}$ where $\alpha, \beta$ are the two roots of $f(x) = x^2 - x - \frac{q-1}{4}$. When $q = 5$ we recover the ordinary Fibonacci numbers. The discriminant of $f(x)$ is $q$, so it splits $\bmod p$ if and only if $q$ is a quadratic residue $\bmod p$.

If $\left( \frac{q}{p} \right) = -1$, then the Frobenius morphism $x \mapsto x^p$ swaps $\alpha$ and $\beta$ (working over $\mathbb{F}_p$), hence $F_p \equiv -1 \bmod p$. And if $\left( \frac{q}{p} \right) = 1$, then the Frobenius morphism fixes $\alpha$ and $\beta$, hence $F_p \equiv 1 \bmod p$. In other words,

$\displaystyle F_p \equiv \left( \frac{q}{p} \right) \bmod p.$

Quadratic reciprocity in this case is equivalent to the statement that

$\displaystyle F_p \equiv \left( \frac{p}{q} \right) \bmod p.$

Question: Does anyone have any ideas about how to prove this directly, thereby proving quadratic reciprocity in the case that $q \equiv 1 \bmod 4$?

My pet approach is to think of $F_p$ as counting the number of ways to tile a row of length $p-1$ by tiles of size $1$ and $2$, where there is one type of tile of size $1$ and $\frac{q-1}{4}$ types of tiles of size $2$. The problem is that I don't see, say, an obvious action of the cyclic group $\mathbb{Z}/p\mathbb{Z}$ on this set. Any ideas?

-
@Q.Yuan: Hi did you look at this paper, this may contain what you need. projecteuclid.org/… – anonymous Aug 14 '10 at 21:02
@Chandru1: the paper doesn't seem to be relevant. – Qiaochu Yuan Aug 14 '10 at 21:48
do you have a path interpretation for F_n (like the one we now for q=5)? (maybe it would be easier to find Z/p-action there) – Grigory M Aug 14 '10 at 22:37
Yes; it comes from the tiling interpretation. F_n counts paths on the graph with adjacency matrix [[1 1][(q-1)/4 0]]. – Qiaochu Yuan Aug 15 '10 at 3:40
@Qiaochu Yuan: well, of course, but this one doesn't seem to be the "right" path interpretation, since it doesn't give the path graph of length 4 for q=5 (motivation: I don't like strange number (q-1)/4 — a path of length q-1 looks much better) – Grigory M Aug 15 '10 at 11:03

Let $\{\gamma_n\}^\infty_{n=0}$ be a given Lucas sequence defined by $\gamma_0=0$, $\gamma_1=1$, $\gamma_{n+1}=\lambda \gamma_n+\mu \gamma_{n-1}$, $n\geq 1$, $\lambda, \mu\in{\bf Z}$, and let $q$ be an odd prime such that $D=(\frac{-1}q)q=\lambda^2+4\mu$. Then the author proves that there is a unique formal power series $\Phi$ with integer coefficients and constant term zero such that (1) $\sum^\infty_{n=1}\gamma_n\Phi^n(t)/n=\sum^\infty_{n=1}(\frac nq)t^n/n$ holds, where $(\frac nq)$ is the Legendre symbol.
From this result follows the Gauss law of quadratic reciprocity in the following form: (2) $(\frac pq)=(\frac Dp)$, where $p$, $q$ are distinct odd primes and $D=(\frac{-1}q) q=\lambda^2+4\mu$.