Month: January 2020

bookmark_borderEisenstein’s Proof of Quadratic Reciprocity

Posted on by Shobhit Bhatnagar

In this post, we take a look at an interesting proof of the Quadratic Reciprocity theorem by Gotthold Eisenstein.

Definition: The Legendre symbol is a function \left(\frac{a}{p}\right) which takes the values \pm 1 depending on whether a is a quadratic residue modulo p. \left(\frac{a}{p}\right) = \begin{cases}0 \quad \text{if }p|a \\ 1 \quad \text{if }a\text{ is a quadratic residue modulo }p \\ -1 \quad \text{if }a\text{ is a quadratic non-residue modulo }p\end{cases} Theorem (Quadratic Reciprocity Law): If p and q are distinct odd primes, then the quadratic reciprocity theorem states that the congruences \begin{aligned} x^2 \equiv q \quad (\text{mod }p) \\ x^2 \equiv p \quad (\text{mod }q) \end{aligned} are both solvable or both unsolvable unless both p and q leave the the remainder 3 when divided by 4. Written symbolically, \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}

We will start by proving two important results about quadratic residues that will be useful later on.

Lemma 1: Let n\not\equiv 0 \;(\text{mod }p). Then n is a quadratic residue modulo p iff n^{\frac{p-1}{2}}\equiv 1 \; (\text{mod }p).

Proof: Fermat’s little theorem tells us that n^{p-1}\equiv 1 \;(\text{mod }p) whenever p \not| n. Since, n^{p-1}-1\equiv (n^{\frac{p-1}{2}}-1)(n^{\frac{p-1}{2}}+1)\equiv 0 \; (\text{mod }p) we have n^{\frac{p-1}{2}}\equiv \pm 1\; (\text{mod }p). Therefore, it suffices to prove that n is a quadratic residue modulo p if and only if n^{\frac{p-1}{2}}\equiv 1 \; (\text{mod }p).

Suppose that \left(\frac{n}{p} \right)=1. Then, there is an integer x such that n\equiv x^2 \; (\text{mod p}). Now, we have n^{\frac{p-1}{2}}\equiv x^{p-1} \equiv 1 \equiv \left(\frac{n}{p} \right) \; (\text{mod }p)

Conversely, assume that n^{\frac{p-1}{2}}\equiv 1 \; (\text{mod }p). Let g be a primitive root of p. Then, we have n\equiv g^k \; (\text{mod }p) for some integer k. Since n^{\frac{p-1}{2}}\equiv g^{\frac{k(p-1)}{2}} \equiv 1 \; (\text{mod }p), the order of g must divide the exponent \frac{k(p-1)}{2}. Therefore, p-1 | \frac{k(p-1)}{2} and thus k is an even integer. Let’s say k=2j for some integer j. Then, we have n \equiv g^k \equiv g^{2j} \equiv (g^j)^2 \; (\text{mod }p) This proves that n is a quadratic residue modulo p.

Lemma 2 (Gauss’s Lemma): For any odd prime p, let a be an integer that is co-prime to p. Consider the integers S = \left\{ a,\ 2a,\ 3a,\cdots, \frac{p-1}{2}a \right\} and their least positive residues modulo p. Let n be the number of these residues that are greater than p/2. Then \left(\frac{a}{p}\right)=(-1)^n

Proof: Since p\not | a, none of the integers in S are congruent to 0 and no two of them are congruent to each other modulo p. Let r_1, \cdots, r_m be the residues modulo p smaller than \frac{p}{2}, and let s_1, \cdots, s_n be the residues modulo p greater than \frac{p}{2}. Then m+n=\frac{p-1}{2} and the integers r_1, \cdots, r_m, p-s_1, \cdots , p-s_n are all positive and less than \frac{p}{2}. Now, we will prove that no two of these integers are equal. Suppose that for some choice of i and j we have p-s_i = r_j. We can choose integers u and v, with 1 \leq u,v \leq \frac{p-1}{2} and satisfying \begin{aligned} s_i &\equiv u a \; (\text{mod }p) \\ r_j &\equiv v a \; (\text{mod }p) \end{aligned} Now, we have s_i+r_j \equiv a(u+v) \equiv p \equiv 0 \; (\text{mod }p) This implies that u+v \equiv 0 \; (\text{mod }p). However, this is not possible because 1\leq u+v \leq p-1. Thus, we have proven that the numbers r_1,\cdots, r_m, p-s_1, \cdots p-s_n are simply a rearrangement of the integers 1,2,\cdots, \frac{p-1}{2}. Their product is equal to \left(\frac{p-1}{2} \right)!. Therefore, \begin{aligned} \left(\frac{p-1}{2}\right)! &= r_1 \cdots r_m (p-s_1)\cdots (p-s_n) \\ &\equiv (-1)^n r_1 \cdots r_m s_1\cdots s_n \; (\text{mod }p) \\ &\equiv (-1)^n a\cdot 2a\cdots \left(\frac{p-1}{2}\right)a \; (\text{mod }p) \\ &\equiv (-1)^n a^{\frac{p-1}{2}} \left( \frac{p-1}{2}\right)! \; (\text{mod }p) \end{aligned} The \left( \frac{p-1}{2}\right)! term can be cancelled from both sides as p\not| \left( \frac{p-1}{2}\right)! . In other words, we have a^{\frac{p-1}{2}}\equiv (-1)^n \; (\text{mod }p). This completes the proof of Gauss’s lemma.

We are now ready to prove the Quadratic reciprocity theorem.

Proof of the Quadratic Reciprocity Theorem:

Using the periodicity properties of \sin and Gauss’s lemma, it is easy to verify the following result:

Lemma: Let p and q be distinct odd primes and let A = \left\{ \alpha\in \mathbb{Z} | 1\leq \alpha \leq \frac{p-1}{2}\right\} be a half system modulo p. Then, \left(\frac{q}{p}\right) = \prod_{\alpha\in A}\frac{\sin\left(\frac{2\pi}{p}q\alpha\right)}{\sin\left(\frac{2\pi}{p}\alpha\right)} \quad\quad (1)

We start by examining the right hand side of equation (1). The addition theorem for trigonometric functions yields \sin 2\alpha = 2\sin\alpha\cos\alpha and \sin 3\alpha = \sin\alpha(3-4\sin^2\alpha). Induction shows that \sin q\alpha = \sin\alpha P(\sin\alpha) for all odd q\geq 1, where P\in \mathbb{Z}[X] is a polynomial of degree q-1 and highest coefficient (-4)^{\frac{q-1}{2}}. Thus there exist a_i \in \mathbb{Z} such that \begin{aligned}\frac{\sin qz}{\sin z} &= (-4)^{\frac{q-1}{2}} \left( (\sin z)^{q-1}+a_{q-2} (\sin z)^{q-2}+\cdots + a_0 \right) \\ &= (-4)^{\frac{q-1}{2}} \psi(X), \quad \text{where }X=\sin z\end{aligned} Since \phi(z)=\frac{\sin qz}{\sin z} is an even function, so is \psi(X), hence a_{q-2}=\cdots = a_1 = 0. Now \phi(z) has zeros \left\{ \pm \frac{2\pi}{q}\beta, \ 1\leq \beta \leq \frac{q-1}{2}\right\}. Since \psi is monic of degree q-1, we may write \psi(X) = \prod_{\beta\in B}\left(X^2-\sin^2\frac{2\pi\beta}{q} \right) where B=\left\{1,\cdots,\frac{q-1}{2} \right\} is a half system modulo q. Replacing X by \sin z, we get \frac{\sin qz}{\sin z} = (-4)^{\frac{q-1}{2}} \prod_{\beta\in B }\left( \sin^2z -\sin^2\frac{2\pi\beta}{q}\right) \quad \quad (2) Put z=\frac{2\pi\alpha}{p} in equation (2) and plug the result into equation (1). \begin{aligned} \left(\frac{q}{p}\right) &= \prod_{\alpha\in A} (-4)^{\frac{q-1}{2}} \prod_{\beta\in B} \left( \sin^2\frac{2\pi\alpha}{p} -\sin^2\frac{2\pi\beta}{q}\right)\\ &= (-4)^{\frac{q-1}{2} \frac{p-1}{2}} \prod_{\alpha\in A}\prod_{\beta\in B} \left( \sin^2\frac{2\pi\alpha}{p} -\sin^2\frac{2\pi\beta}{q}\right)\quad\quad (3) \end{aligned} Exchanging p and q on the right side of (3) give rise to factor of (-1)^{(p-1)(q-1)/4}. Therefore, \left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}\left(\frac{p}{q}\right) \tag{4} which is the quadratic reciprocity law.

References

  • Lemmermeyer, Franz. “Reciprocity Laws: From Euler to Eisenstein”. New York, Springer, 2000
  • Burton, David M. “Elementary Number Theory”. New Delhi, Tata McGraw-Hill Publishing Company Limited, May 1 2006

bookmark_borderSimplification of Incomplete Beta Functions

Posted on by Shobhit Bhatnagar

In this post, we will derive closed form solutions for two incomplete beta integrals. \begin{aligned} \int_0^1\frac{dx}{\sqrt{1-x}\sqrt[6]{9-x}\sqrt[3]x}&=\frac\pi{\sqrt3} \quad\quad (1)\\ \int_0^1\frac{dx}{\sqrt{1-x}\sqrt[4]x\sqrt[4]{2-x\sqrt3}} &= \frac{2\sqrt{2}\pi}{3\sqrt[8]{3}} \quad\quad (2) \end{aligned} These problems are from a math.stackexchange.com question posted by Vladimir Reshetnikov.

Alternate forms

The equations (1) and (2) can be expressed in terms of the incomplete beta function using some elementary hypergeometric identities. This makes our problems equivalent to proving that \begin{aligned} B\left(\frac{1}{9};\frac{1}{6},\frac{1}{3}\right) &= \frac{\sqrt{3}}{2^{\frac{4}{3}}\pi}\Gamma\left(\frac{1}{3}\right)^3 \quad\quad (3)\\ B\left(\frac{\sqrt{3}}{2};\frac{1}{4},\frac{1}{4}\right) &= \frac{2}{3\sqrt{\pi}}\Gamma\left(\frac{1}{4}\right)^2 \quad\quad (4) \end{aligned} Proof of (3) B\left(\frac{1}{9};\frac{1}{6},\frac{1}{3}\right) = \int_0^{\frac{1}{9}}x^{-\frac{5}{6}}\left( 1-x\right)^{-\frac{2}{3}} dx Substitute x=\frac{y^3}{1+y^3} in the above integral to get B\left(\frac{1}{9};\frac{1}{6},\frac{1}{3}\right) =3\int_0^{\frac{1}{2}}\frac{1}{\sqrt{y+y^4}}dy We can now transform this integral into a beta integral using the substitution y=\frac{1-z}{2+z}. B\left(\frac{1}{9};\frac{1}{6},\frac{1}{3}\right) =3\int_0^1\frac{1}{\sqrt{1-z^3}}dz = B\left( \frac{1}{3},\frac{1}{2}\right)=\frac{\sqrt{3}}{2^{\frac{4}{3}}\pi}\Gamma\left(\frac{1}{3}\right)^3 This proves equations (1) and (3).

Proof of (4)

The proof of integrals (2) and (4) is more involved. Using the substitution x=\frac{4t^2}{1+4t^2}, the integral transforms into the Weierstrass form: B\left(\frac{\sqrt{3}}{2};\frac{1}{4},\frac{1}{4}\right) =\int_0^{\frac{\sqrt{3}}{2}}x^{-\frac{3}{4}}(1-x)^{-\frac{3}{4}}dx=2\sqrt{2} \int_0^\alpha \frac{dt}{\sqrt{4t^3+t}} where \alpha=\frac{\sqrt{3+2\sqrt{3}}}{2}. Let \wp(z) denote the Weierstrass Elliptic function with invariants g_2=-1 and g_3=0. \wp(z) satisfies the differential equation: \wp'(z)^2=4\wp(z)^3+\wp(z) The half periods are \omega_1=\frac{1+i}{4}L and \omega_2=\frac{-1+i}{4}L where L=\frac{1}{\sqrt{2\pi}}\Gamma\left(\frac{1}{4}\right)^2 is the Lemniscate constant. Now, we can express our integral as follows: B\left(\frac{\sqrt{3}}{2};\frac{1}{4},\frac{1}{4}\right) =2\sqrt{2}\left(\wp^{-1}(0)-\wp^{-1}(\alpha) \right)Note that\int_0^\infty \frac{dt}{\sqrt{4t^3+t}}=\frac{1}{2\sqrt{2\pi}}\Gamma\left(\frac{1}{4}\right)^2=\frac{L}{2} Therefore, \wp^{-1}(0)=\frac{L}{2}. To prove the claim we only need to prove that \wp\left(\frac{L}{6}\right)=\alpha. Using the addition theorem of \wp(z) and the fact that \wp\left(\frac{L}{2}\right)=0 we get: \begin{aligned} \wp\left(\frac{L}{6}\right) &= \wp\left(\frac{L}{2}-\frac{L}{3}\right)\\ &= \frac{1}{4}\left(\frac{\wp'\left(\frac{L}{3}\right)}{\wp\left(\frac{L}{3}\right)} \right)^2-\wp\left(\frac{L}{3}\right) \\ &= \frac{4\wp\left( \frac{L}{3}\right)^3+\wp\left(\frac{L}{3}\right)}{4\wp\left(\frac{L}{3}\right)^2}-\wp\left(\frac{L}{3}\right)\\ &= \frac{1}{4\wp\left(\frac{L}{3}\right)}\quad\quad\quad (5) \end{aligned} On the other hand, by the duplication theorem: \begin{aligned} \wp\left(\frac{L}{3}\right)&= \frac{1}{4}\frac{\left(6\wp\left(\frac{L}{6}\right)^2+\frac{1}{2}\right)^2}{4\wp\left(\frac{L}{6}\right)^3+\wp\left(\frac{L}{6}\right)}-2\wp\left(\frac{L}{6}\right)\quad\quad\quad ({6}) \end{aligned} Combine equations (5) and (6) to get: \frac{1+4\wp\left(\frac{L}{6}\right)^2}{\left(6\wp\left(\frac{L}{6}\right)^2+\frac{1}{2} \right)^2-32\wp\left(\frac{L}{6}\right)^4-8\wp\left(\frac{L}{6}\right)^2}=1 \\ \implies 16\wp\left(\frac{L}{6}\right)^4-24\wp\left(\frac{L}{6}\right)^2-3=0 Since \wp\left( \frac{L}{6}\right) is positive, we conclude that \wp\left(\frac{L}{6}\right)=\frac{\sqrt{3+2\sqrt{3}}}{2} This completes our proof of equation (4) and (2).