The sequence of Lucas polynomials is defined by , , and for

The next few terms in the sequence are , and .

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

The polynomials

It’s easy to see that for odd, is divisible by and has only even-power terms. Thus for some monic integer polynomial of degree . We will be particularly interested in the polynomials for prime.

If is even (resp. odd), a simple induction shows that the constant term (resp. the coefficient of ) in is equal to . In particular, for odd we have .

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.

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 and be odd relatively prime positive integers. You have a stack of playing cards numbered 0 through and you want to deal them onto the table in an rectangular array. Consider the following three ways of doing this:

Row deal () : Deal the cards into rows, going left to right and top to bottom.