Quadratic Reciprocity via Lucas Polynomials

In this post, I’d like to explain a proof of the Law of Quadratic Reciprocity based on properties of Lucas polynomials. (There are over 300 known proofs of the Law of Quadratic Reciprocity in the literature, but to the best of my knowledge this one is new!)

In order to keep this post as self-contained as possible, at the end I will provide proofs of the two main results (Euler’s criterion and the Fundamental Theorem of Symmetric Polynomials) which are used without proof in the body of the post.

Lucas polynomials

The sequence of Lucas polynomials is defined by $L_0(x)=2$ , $L_1(x)=x$ , and $L_n(x)=xL_{n-1}(x)+L_{n-2}(x)$ for $n \geq 2.$

The next few terms in the sequence are $L_2(x)=x^2+2, L_3(x)=x^3+3x, L_4(x)=x^4 + 4x^2 + 2$ , and $L_5(x)=x^5+5x^3+5x$ .

By induction, the degree of $L_n(x)$ is equal to $n$ . The integers $L_n(1)$ are the Lucas numbers, which are natural “companions” to the Fibonacci numbers (see, e.g., this blog post).

The polynomials $H_n(x)$

It’s easy to see that for $n$ odd, $L_n(x)$ is divisible by $x$ and $L_n(x)/x$ has only even-power terms. Thus $L_n(x)/x = H_n(x^2)$ for some monic integer polynomial $H_n(x)$ of degree $(n-1)/2$ . We will be particularly interested in the polynomials $H_p(x)$ for $p$ prime.

If $n$ is even (resp. odd), a simple induction shows that the constant term (resp. the coefficient of $x$ ) in $L_n(x)$ is equal to $n$ . In particular, for $n$ odd we have $H_n(0)=n$ .

Continue reading →

The Sign of the Quadratic Gauss Sum and Quadratic Reciprocity

Today marks the birthday of Karl Friedrich Gauss , the “Prince of Mathematicians”, who was born on April 30, 1777. In honor of Gauss’s 238th birthday, I thought I would blog about one of Gauss’s favorite theorems — the Law of Quadratic Reciprocity — and its relation to the sign of the quadratic Gauss sum, which we will determine using the Discrete Fourier Transform. Our exposition mostly follows this paper by Ram Murty. Regarding the sign of the quadratic Gauss sum, Gauss conjectured the correct answer in his diary in May 1801, but it took more than four years until he was able to find a proof in August 1805. Gauss wrote to his friend W. Olbers that seldom had a week passed for four years that he had not tried in vain to prove his conjecture. Then:

Finally, two days ago, I succeeded – not on account of my hard efforts, but by the grace of the Lord. Like a sudden flash of lightning, the riddle was solved. I am unable to say what was the conducting thread that connected what I previously knew with what made my success possible.

Continue reading →

Quadratic reciprocity and Zolotarev’s Lemma

I want to explain a beautiful proof of the Law of Quadratic Reciprocity from c. 1874 due to Egor Ivanovich Zolotarev (1847-1878). Some time ago I reformulated Zolotarev’s argument (as presented here) in terms of dealing cards and I posted a little note about it on my web page. After reading my write-up (which was unfortunately opaque in a couple of spots), Jerry Shurman was inspired to rework the argument and he came up with this elegant formulation which I think may be a “proof from the book”. The following exposition is my own take on Jerry’s argument. The proof requires some basic facts about permutations, all of which are proved in this handout.

Let $m$ and $n$ be odd relatively prime positive integers. You have a stack of $mn$ playing cards numbered 0 through $mn-1$ and you want to deal them onto the table in an $m \times n$ rectangular array. Consider the following three ways of doing this: