--- title: Catalan Conjectures Reading Notes date: 2021-08-25 --- Tags: #projects/notes/reading #projects/notes/seminars # Catalan Website: [Link to book]() ## Last Time - The Diophantine equation $x^p-y^q = 1$ with $p, q\geq 2$ has only one 4-tuple solution: \[ (\pm 3)^2 - 2^3 = 1 .\] - Used Mihăilescu's work from 2000-2003 to take care of odd prime cases. Leaves some cases: - $p=2$ with $q$ arbitrary, - $q=2$ with $p$ arbitrary, - Reduced to elementary number theory! ## Today - Today: the families \[ x^2 - y^q = 1 && x^p - y^2 = 1 .\] - Idea: prove - $q=2$ and $p\geq 2$ arbitrary, - $p=2$ and $q\geq 5$ arbitrary. - Next time: $p=2, q=3$ in Chapter 4. Note $x^2 = y^3+1$ is an elliptic curve! Find solutions using descent (Raemeon!) - Notation: - $\ord_p(x)$: the $p\dash$adic valuation of $x$. - $R^2$ for $R$ a ring: the set of squares in the ring (not the product!) - More generally: $R^p$ for the set of $p$th powers ### Preliminaries :::{.lemma title="UFD Power Lemma"} In $R$ a UFD, if $\gens{a, b} = \gens{1}$ and $ab = c^n \implies a = u_a r^n, b= u_b s^n$ for some units $u_a, u_b$ and $r,s \in R$. ::: :::{.example title="?"} Proof omitted, example has essential idea: - $a = 2^8 3^4$, - $b = 5^2 7^6$ - $c^2 = ab$, so $n=2$ Then write \[ c^2 = ab = 2^8 3^4 5^2 7^6 = (2^4 3^2 5 7^3)^2 = (2^4 3^2)^2 (5 7^3)^2 \da r^2 s^2 .\] Notes: - $n$ had to divide every exponent - For this, need coprimality: $n$ divided every exponent in the factorization of $c^2$, but this can go wrong by just splitting up a power: - $a= 2^8 3^4 5$ - $b = 5 7^6$ ::: :::{.lemma title="Parity divisibility lemma"} $1+i$ divides $a+bi$ in $\ZZ[i] \iff a,b$ have the same parity. ::: :::{.proof title="of lemma"} \envlist - Use that $N(1+i) \divides N(\alpha) \iff (1+i)\divides \alpha$ - $\impliedby$: Clear from properties of norm - $\implies$: Expand $a+bi = (1+i)(c + di)$ and solve a $2\times 2$ system. - So $2\divides a^2 + b^2$, forcing them to have the same parity. ::: :::{.lemma title="Exc 2.5"} Extend \[ \ord_2:\ZZ&\to \ZZ_{\geq 0} \leadsto \ord_2:\QQ\to \ZZ_{\geq 0} \\ \\ \ord_2(x/y) &= \ord_2(x) - \ord_2(y) \\ \ord_2(0) &= \infty .\] Properties: \[ \ord_2(xy)&= \ord_2(x) + \ord_2(y) \\ \ord_2(x+y) &\geq \min(\ord_2(x), \ord_2(y)) && \text{equality iff } \ord_2(x) \neq \ord_2(y) .\] ::: :::{.lemma title="Exc 3.2, GCD $q\dash$division lemma"} For $q$ prime, $x,y\in \ZZ$ distinct with $\gcd(x, y) = 1$, \[ \gcd\qty{ {x^q - y^q \over x-y}, x-y } \divides q .\] Note: useful because \[ x^q - y^q = (x-y)\qty{x^q - y^q \over x-y} .\] ::: ### Ch 2: $q=2$ \[ x^p - y^2 = 1 .\] ![](Projects/0000%20Talks/Archive/Catalan/figures/2021-09-10_01-16-59.png) ![](Projects/0000%20Talks/Archive/Catalan/figures/2021-09-10_01-18-12.png) ![](Projects/0000%20Talks/Archive/Catalan/figures/2021-09-10_01-18-33.png) - Proof idea: a 2-adic argument, use properties of $\ZZ[i]$. :::{.proposition title="2.1: V.A. Lebesgue, 1850"} The Diophantine equation \[ x^p- y^2 = 1 \] has no solutions for $p\geq 2$ and $x, y\in \ZZ_{\neq 0}$. ::: > Note: not Henri Lebesgue, of integral fame, late 1800s. Instead: Victor-Amédée Lebesgue, early 1880s. Simplified $n=4,5,7$ cases of Fermat's last theorem. - Take $x, y$ nonzero solutions, so $x^p = y^2 + 1$. :::{.claim} Can assume $p$ is odd. ::: :::{.proof title="of claim"} \envlist - If not, suppose $p$ is even. - Factor \[ (x^{p\over 2} - y)(x^{p\over 2} + y) = 1 \implies x^{p\over 2} \pm y = 1 ,\] where they both have to have the same sign. - Subtract equations: \[ x^{p\over 2} + y &= \pm 1\\ x^{p\over 2} - y &= \pm 1 \\ \hline \\ y-(-y) &= 0 \implies 2y = 0 \implies y=0 ,\] - But we assumed $y\neq 0$. $\contradiction$ ::: :::{.claim} $x, y$ have opposite parity. ::: :::{.proof title="?"} \envlist - Reduce $\mod 2$. - $y$ even $\implies y = 0 \mod 2 \implies y^2 = 0\mod 2 \implies x^p = y^2 + 1 = 1 \mod 2 \implies x$ odd - $y$ odd $\implies y = 1 \mod 2 \implies y^2 = 1\mod 2 \implies x^p = y^2 + 1 = 1 + 1 = 2 = 0 \mod 2 \implies x$ even. ::: :::{.claim} $y$ is even, $x$ is odd. ::: :::{.proof title="of claim"} \envlist - Consider \[ x^p = y^2 + 1 \mod 4 .\] - Consider all squares in $\ZZ/4$: \[ \ZZ/4 = \ts{0,1,2,3} &\implies (\ZZ/4)^2 = \ts{0,1,4,9} = \ts{0,1,0,1} = \ts{0, 1} \\ &\implies y^2 = 0, 1\mod 4 .\] - Toward a contradiction, suppose $y$ is odd (implicitly: $x$ is even) - $y^2$ odd $\implies y^2 = 1,3 \mod 4 \implies y^2 = 1 \mod 4$ since the only squares mod 4 are 0, 1. - Then $x^p = y^2 + 1 = 2\mod 4$. - $x$ even $\implies x^n = 0 \mod 4$ for any $n \geq 2$. - Why: $x$ even $\implies x=0, 2 \mod 4 \implies x^2 = 0^2, 2^2 = 0 \mod 4$, etc. - Now have $x^p = 2$ and $x^p = 0 \mod 4$. $\contradiction$ ::: :::{.claim} $\gcd(1+iy, 1-iy) = 1 \in \ZZ[i]$. ::: :::{.proof title="?"} \envlist - Check that $d\divides 1+iy \implies N(d) \divides 2$ so $N(d) = \pm 1,2$. - $N(d) = 1 \iff d$ is a unit - $N(d) = 2 \iff a^2 + b^2 = 2 \implies a=b=1$ - $1+i \notdivides 1 \pm i y$ since $1, y$ have different parities, using that $y$ is even. ::: - Since $p$ is odd, $U(\ZZ[i]) = \ts{\pm 1, \pm i}$ are all $p$th powers: - $(\pm 1)^p = \pm 1$ - $i^p = \pm i \implies (-i)^p = -i^p = \mp i$. - Factor \[ x^p = y^2 + 1 &= (1+iy)(1-iy) \in (\ZZ[i])^p .\] Continuing the proof, use that $(1\pm iy)$ are coprime to apply UFD power lemma: \[ x^p = y^2 + 1 = (1+iy)(1-iy) &\in (\ZZ[i])^p \\ \implies 1 + iy &\in (\ZZ[i])^p && \text{by UFD lemma} \\ \implies 1 + iy &= c^p,\, \exists c\in \ZZ[i] .\] :::{.claim} $c + \bar{c} = \pm 2$, and thus $c = \pm(1 + bi) \in 1 + i\ZZ$. ::: :::{.proof title="?"} Check \[ c^p + \bar{c}^p = c^p + \bar{c^p} = (1+iy) + (1-iy) = 2 ,\] - Use that \[ z^n - w^n &= (z-w)\sum_{k=0}^{n-1} z^kw^{n-k} \\ &= (z^{n-1} + z^{n-2}w + \cdots + w^{n-1}) \\ \\ \implies z^n + w^n &= z^n - (-w)^n && \text{for $n$ odd} \\ &= (z+w)\sum_{k=0}^{n-1} z^k(-w)^{n-k} \\ &= (z^{n-1} - z^{n-2}w + \cdots + w^{n-1}) && \text{since $n-1$ is even} .\] - Take $z= c^p, w=\bar{c}^p$: \[ 2 = c^p + \bar{c}^p &= (c+\bar c)(c^{p-1} - c^{p-2} \bar c + \cdots + \bar{c}^{p-1}) \\ \\ &\implies c+\bar c\divides 2 \in \ZZ \\ &\implies c+\bar c = \pm 2 \quad \text{ since } c + \bar{c} \text{ is even} .\] - Write $c = b'+ bi, \bar c= b' - bi$, then \[ & \pm 2 = c + \bar c = 2b' \\ &\implies b' = \pm 1 \\ &\implies c = \pm(1 + bi) .\] ::: :::{.claim} Since $y$ is even, $c = \pm(1 + bi)$ is not divisible by $1+i$. ::: :::{.proof title="of claim"} Now WTS: $(1+i) \notdivides c$. - Toward a contradiction: if so, \[ 1+i &\divides c \\ \implies 1+i &\divides c^p = 1 + iy \\ \iff 1 &\equiv y \mod 2 && \text{by parity divisibility lemma}\\ \iff y &\text{ is odd} && \contradiction .\] ::: :::{.remark} Now \[ y \text{ even } &\implies (1+i)\notdivides c = \pm(1 + bi) \\ &\iff 1 \not\equiv b \mod 2 \quad \text{by parity divisibility lemma} \\ &\iff b \text{ is even} \\ &\implies c\in 1 + 2i\ZZ .\] - Now reduce $\mod 8$ to conclude that we take $+2$ in the following equation: \[ \pm 2 = c^p + \bar{c}^p &= (1+bi)^p + (1-bi)^p \\ \implies \pm 2 &\equiv (1+bi)^p + (1-bi)^p \mod 8\ZZ[i] .\] - Take binomial expansion of this expression to find a relation among the binomial coefficients ${p\choose k}$: \[ {p \choose 2}(bi)^2 + {p\choose 4}(bi)^4 + \cdots + {p\choose p-1} (bi)^{p-1} = 0 .\] ::: :::{.claim} The leading term has the (strictly) **lowest** 2-adic valuation: \[ S\da \sum s_k \da \ord_2\qty{ {p\choose k}(bi)^k } > \ord_2\qty{ {p\choose 2} (bi)^2 } ,\] also implying that all of the pairs $(\ord_2(s_1), \ord_2(s_k))$ are distinct. Thus \[ \ord_2(S) = \min \ord_2(s_k) = \ord_2(s_1) \] ::: :::{.remark} \envlist - Why this finishes the proof: use that $\ord_2(a + b) \geq \min(\ord_2(a), \ord_2(b))$ with equality when $\ord_2(a)\neq \ord_2(b)$ are distinct. - Note $S=0$, now apply above repeatedly to $s_1, s_k$ to get \[ \ord_2(s_1) = \ord_2(S) = \ord_2(0) = 0\\ \implies \ord_2\qty{ {p\choose 2} (bi)^2 } = \ord_2\qty{{b^2p! \over 2(p-2)!} } = 0 \\ \implies b=0 \quad \text{since $b$ is even} ,\] - Then \[ c = 1+bi = 1+0i = 1 \\ \implies c=1 \\ \\ 1 = c^p = 1+iy \\ \implies y=0 .\] - This contradicts $y\in \ZZ_{\neq 0}$ and finishes the entire proof. ::: :::{.proof title="?"} \envlist - WTS: $\ord(s_k/s_2) = \ord(s_k) - \ord(s_2) > 0$. \[ \ord\qty{s_k\over s_2} &\da \ord_2\qty{ {p\choose k} {p\choose 2}\inv (bi)^{k-2} }\\ &= \ord_2\qty{ {p-2\choose k-2}\qty{2 (bi)^{k-2} \over k(k-1)} }\\ &= \ord_2\qty{{p-2 \choose k-2}} + \ord_2\qty{2(bi)^{k-2}} - \ord_2(k(k-1)) \\ &> 0 ,\] - Use that - Binomial coefficients are integers $\geq 1$ - $b$ is even, - $f(k) \da {\log(k) \over k-1}\searrow 0$, since $f'(k) < 0$ everywhere, - $f(2) = \log(2) \implies \log(2) > {\log k \over k- 1}$ - Then for any even $k\geq 4$, \[ \ord_2( 2(bi)^{k-2} ) &\geq k-1 \\ &{\color{red}>} {\log k \over \log 2} \\ &\geq \ord_2(k) \\ &= \ord_2(k(k-1)) \quad \text{since $k-1$ is odd}\\ \implies &\ord_2(2(bi)^{k-2}) - \ord_2(k(k-1)) > 0 .\] ::: ### Ch. 3: $p=2$ \[ x^2 - y^q = 1 .\] ![](Projects/0000%20Talks/Archive/Catalan/figures/2021-09-10_01-14-53.png) ![](Projects/0000%20Talks/Archive/Catalan/figures/2021-09-10_01-15-04.png) ![](Projects/0000%20Talks/Archive/Catalan/figures/2021-09-10_01-15-14.png) ![](Projects/0000%20Talks/Archive/Catalan/figures/2021-09-10_01-15-31.png) - Proof due to Chao, 1965, adapted by Chein. - Idea: for $q \geq 5$, we'll show $x^2-y^q=1$ has no solutions $x, y\in \ZZ_{\neq 0}$. - Toward a contradiction, we'll suppose such solutions exist. - Lemmas will give - $x\equiv 0\mod q$ - $x \equiv \pm 3 \mod q$ - But since $q > 3$, this is absurd. :::{.lemma title="3.1"} For $q\geq 3 \in \ZZ$ an odd *integer* and $x^2-y^q=1$, we have 1. For some coprime $a, b$ with $\gcd(2a, b) = 1$, - $x-1 = 2^{q-1} a^q$ - $x+1 = 2b^q$ - $y=2ab$ 2. $y\geq 2^{q-1}-2$. ::: ### Lemma 3.2 :::{.lemma title="3.2"} For $q\geq 3 \in \ZZ$ an odd *prime* and $x^2-y^q=1$ for $x,y\in \ZZ_{\neq 0}$, \[ x\equiv 0 \mod q .\] ::: - By contradiction: suppose \[ x^2 = y^q + 1 && x,y\neq 0, x\not\equiv 0 \mod q .\] We'll contradict $y\neq 0$. - Write \[ x^2 = y^q + 1 = (y+1)\qty{ y^q + 1 \over y+1} ,\] noting typo in book. :::{.claim title="Exercise 3.2"} \[ d \da \gcd\qty{ y+1, \qty{ y^q + 1 \over y+1} } \implies d\divides q \implies d \in \ts{1, q} .\] ::: - Then $d\divides x^2$ but $x\not\equiv 0\mod q \implies d\neq q \implies d=1$. :::{.claim title="Exercise 2.3"} \[ y+1, \qty{ y^q + 1 \over y+1} \in \pm1 \cdot \ZZ^2 .\] ::: :::{.remark} \envlist - $y^q + 1 = x^2 \in \ZZ^2 \implies y\geq 0$ using that $q$ is odd. - If $y\leq -1$ then $y^q\leq -1 \implies y^q+1=x^2\leq -1, \contradiction$. - $y\geq 0 \implies y+1 >0$ and ${y^q + 1\over y+1}>0$. - $y+1>0$ and $y+1\in \pm1 \ZZ^2 \implies y+1 \in +1\ZZ^2 \implies y+1 = u^2$ for some $u\in \ZZ_{\neq 0}$. - Consider solutions to \[ f(X, Y) \da X^2 -yY^2 = 1 .\] - Contains $(u, 1)$ since $u^2-y\cdot 1 = 1$ - Contains $(x, y^{q-1\over 2})$ since $x^2 - y^q = 1$. - $y\neq 0\implies y\geq 1$ is positive - $y=u^2 -1 \geq 1$ is not a square (exercise) $\implies f$ is a **Pell equation**: ![$x^2-ny^2=1$ where $n$ is a nonsquare](Projects/0000%20Talks/Archive/Catalan/figures/2021-09-09_23-31-05.png) - $y\not\in \ZZ^2 \implies \QQ[\sqrt y]/\QQ$ is quadratic and $\ZZ[\sqrt y] \leq \ZZ_K$ is a subring of its ring of integers - Note: $R \da \ZZ[\sqrt y]$ will be the ambient ring for the rest, with $\ZZ\dash$basis $\ts{1, \sqrt y}$. - Exercise: $U(\ZZ[\sqrt y]) = \gens{-1. \eps \da u + \sqrt y}$ are generators of its unit group, treat them as a $\ZZ\dash$basis. - Thus \[ x + y^{q-1\over 2}\sqrt{y} = \pm(u + \sqrt y)^m,\quad \exists m\in \ZZ .\] - After possibly changing the sign of $u$, we can assume $m\geq 0$: \[ (u + \sqrt y) \cdot -(-u + \sqrt y) = -(u^2 + y) = u^2 - y = 1 \\ \implies (u + \sqrt y)\inv = -(-u + \sqrt y) .\] - Reduce equation mod $y\ZZ[\sqrt y]$: \[ x + {\color{red} y^{q-1\over 2}\sqrt{y} } &\equiv \pm(u + \sqrt y)^m \mod yR \\ \implies x &\equiv \pm(u + \sqrt y)^m \mod yR \\ &\equiv \pm \sum_{k=0}^m {m\choose k}u^{m-k} (\sqrt y)^k \\ &\equiv \pm\qty{ u^m + {m\choose 1} u^{m-1}y^{1\over 2} + {m\choose 2}u^{m-2} y^1 + {\color{red} {m\choose 3}u^{m-3}y^{3\over 2} + \cdots} } \\ &\equiv \pm(u^m + mu^{m-1} y^{1\over 2}) \\ \implies x &\equiv \pm(u^m + mu^{m-1} \sqrt y) \mod yR .\] - Now equate coefficients: \[ mu^{m-1} \equiv 0 \mod yR \implies y\divides mu^{m-1} .\] ::: :::{.claim} $y$ is even and $u$ is odd, since $y+1 = u^2$. ::: - Proof: omitted. :::{.remark} \envlist - Given this, since $y \divides mu^{m-1}$ with $y$ even and $u$ odd, $u^{\ell}$ is odd for all $\ell$, **so $m$ must be even.** - $m$ even $\implies$ this is legal: \[ x + y^{q-1\over 2}\sqrt y &= \pm (u + \sqrt y)^m \\ &= \pm\qty{\qty{u + \sqrt y}^2}^{m\over 2} \\ &= \pm \qty{u^2 + y + 2u\sqrt y }^{m\over 2} \\ \\ \implies x + y^{q-1\over 2}\sqrt y &\equiv \pm \qty{ {\color{red} u^2} + y + {\color{red} 2u\sqrt y} }^{m\over 2} \mod uR \\ &\equiv \pm y^{m\over 2} \\ \\ \implies x + y^{q-1\over 2}\sqrt y &\equiv \pm y^{m\over 2} + 0\sqrt y \mod uR \\ \implies u\divides y^{q-1\over 2} .\] - Now use $y+1 = u^2 \implies d\da \gcd(u, y) = 1$ - Why: $d\divides y$ and $d\divides u$ implies $d\divides u^2$ and $d\divides u^2-y = 1$. - Then $u\divides y^{q-1\over 2}$ and $\gcd(u, y ) = 1 \implies u = \pm 1$. - Finish proof: \[ y+1 = u^2 = (\pm 1)^2 = 1 \implies y=0, \contradiction .\] ::: ### Lemma 3.3 :::{.lemma title="3.3"} For $q\geq 3 \in \ZZ$ an odd *prime* and $x^2-y^q=1$, \[ x\equiv \pm 3 \mod q .\] ::: - Trivial if $q=3$ since $\pm 3 \equiv 0\mod 3$ (applying previous lemma), so assume $q\geq 5$. :::{.lemma title="3.1"} Up to switching $x$ and $-x$, \[ x-1 &= 2^{q-1} a^q\\ x+1 &= 2 b^q\\ y &= 2ab \\ \gcd(a, b) = 1 &= \gcd(2a, b) .\] ::: Proof omitted. - Use lemma to write \[ (b^q)^2 - (2a)^q &= \qty{x+1\over 2}^2 - 2(x-1) \\ &= \qty{x^2 + 2x +1 - 8(x-1)\over 4} \\ &= \qty{x-3\over 2}^2 .\] - Rewrite the LHS: \[ (b^q)^2 - (2a)^q = (b^2 - 2a)\qty{ (b^2)^q - (2a)^q \over b^2 - 2a } \da \alpha_1 \alpha_2 .\] - By the GCD $q\dash$division lemma (Exc. 3.2), \[ d\da \gcd( \alpha_1, \alpha_2)\divides q \implies d\in \ts{1, q} .\] :::{.claim} \[ d=q .\] ::: :::{.remark} Claim finishes the proof: - $q\divides d \implies q\divides \alpha_1$ and $q\divides \alpha_2$ - $\implies q\divides \alpha_1 \alpha_2 = \qty{x-3\over 2}^2$ - $\implies q\divides {x-3\over 2} \implies x\equiv 3 \mod q$. ::: Proof of claim that $d=q$: - Know $d\in \ts{1, q}$ so toward a contradiction suppose $d=1$ (we'll contradict this) - Then $\alpha_1 \alpha_2\in \ZZ^2\implies \alpha_1, \alpha_2 \in \pm \ZZ^2$ (by previous lemma) - Know \[ (b^2)^q - (2a)^q = \qty{x-3\over 2}^2 &\in +1\cdot \ZZ^2 \\ \implies (b^2)^q &\geq (2a)^q \\ \implies b^2 &\geq 2a \\ \implies \alpha_1, \alpha_2 &> 0 .\] - Also know $\alpha_1 = b^2-2a \in +1 \cdot \ZZ$ is a positive square - $y\neq 0, y=2ab \implies a\neq 0$. - Write $b^2 - 2a = c^2$ where $c^2\neq 0$ since $a\neq 0$. - Now a contradiction: $\abs{a}\geq \abs{b}$ and $\abs{a} < \abs{b}$. :::{.claim} \[ \abs{a} \geq \abs{b} .\] ::: :::{.proof title="of claim"} \envlist - Closest squares to $b^2$ are $(b\pm 1)^2$, and \[ \abs{(b\pm 1)^2 - b^2} &= \abs{ b^2 \pm 2b + 1 - b^2} \\ &= \abs{ 1 \pm 2b} \\ &\geq 2\abs{b} - \abs{1} .\] - Write $c^2 = b^2 - 2a$, then since $(b\pm 1)$ is the *closest* square: \[ \abs{c^2 - b^2} \geq \abs{ (b\pm 1)^2 - b^2}\geq 2\abs{b} -1 \\ \implies \abs{c^2 - b^2} = \abs{ (b^2 - 2a) - b^2} = \abs{2a} \geq 2\abs{b}-1 \\ \implies 2\abs{a} \geq 2\abs{b} - 1 \\ \implies \abs{a} \geq \abs{b} ,\] since we're dealing with integers. ::: :::{.claim} \[ \abs{a} < \abs{b} .\] ::: :::{.proof title="of claim"} \envlist - Recall from lemma that $x+1 = 2b^q$ - Use $q\geq 5, q-1\geq 4, \abs x \geq 2$ to write \[ \abs{a}^q &= {\abs {x-1} \over w^{q-1}} \\ &\leq {\abs{x-1} \over 2^4} \\ &< {\abs{x-1} \over 2} \\ &= {\abs{2b^q} \over 2} \\ &= \abs{b}^q ,\] then take $q$th roots. ::: This conclude the proof! $\contradiction$.