mixedmath

I've come to realize that I'm always tempted to start my posts with "Recently, I've..." or "So and so gave me such and such a problem..." or "I happened across this on..." It is as if my middle school English teachers (all of whom were excellent) succeeded so well in forcing me to transition from one idea to the next that I can't help it even today. But, my respect for my middle school teachers aside, I think I'm going to try to avoid that here, and just sort of jump in.

Firstly, as announced at Terry Tao's Blog, two new polymath items are on the horizon. There is a new polymath proposal at the polymath blog on the "Hot Spots Conjecture", proposed by Chris Evans, and that has already expanded beyond the proposal post into its first research discussion post. (To prevent clutter and to maintain a certain level or organization, the discussion gets cut up into 100-comment size chunks or so, and someone summarizes some of the key points in the header each time. I think it's a brilliant model). And the mini-polymath organized around the IMO will happen at the wiki starting on July 12.

Now, onto some number theory -

One of the few complaints I have about my undergraduate education at Georgia Tech was how often a core group of concepts came up. In perhaps ten of my classes, I learned about the Euclidean algorithm (I learned about equivalence relations in even more).. The idea is so old-hat to me now that I really like it when I see it some up in places I don't immediately expect.

The Problem

Show that $\gcd (a^m - 1,a^n - 1) = a^{\gcd (m,n)} - 1$

Let's look at a couple of solutions. One might see that the Euclidean algorithm works on the exponents simply. In fact, $\gcd (a, a^m - 1) = 1 \forall m$, and so we have that (assuming $n > m$ wlog)

$$\gcd (a^n-1,a^m-1) = \gcd (a^n - 1, a^n - a^{n-m} ) = \gcd (a^{m-n} -1, a^m - 1)$$

So one could continue to subtract one exponent from the other, and then switch which exponent we're reducing, and so on, literally performing the Euclidean algorithm on the exponents. But there's a pleasant way of visualizing this. As $(a-1)|(a^n-1),(a^m-1),(a^{\gcd(m,n)} - 1)$, we can look instead at $\gcd \left(\dfrac{a^n - 1}{a-1}, \dfrac{a^m-1}{a-1}\right)$. To do a stricter example, we might look at $\gcd \left(\dfrac{a^5 - 1}{a-1}, \dfrac{a^2-1}{a-1}\right)$, or $\gcd (1 + a + a^2 + a^3 + a^4, 1 + a)$. The first, in this case, has $5$ terms, and the second has $2$ terms, the same as the original exponents. By multiplying $1 + a$ by $a^3$ and subtracting from $1 + a + a^2 + a^3 + a^4$ leaves $1 + a + a^2$. In particular, it is very clear that we can remove $m$ terms at a time from the $n$ terms, and that this can be rotated. I really like this type of answer for a few reasons: it was not immediately obvious to me that the Euclidean algorithm would play much a role, and this argument is indepent of $a$ being a number (i.e. it works in rings of polynomials). $\diamondsuit$

Another, essentially different way of solving this problem is to show that all common divisors of $a^m - 1$ and $a^n - 1$ are divisors of $a^{\gcd(m,n)} - 1$. Suppose $d|(a^m - 1), (a^n - 1)$. Then $a^m \equiv a^n \equiv 1 \mod d$, so that in particular $\text{order}(d)|m,n$. But then $\text{order}(d)|\gcd(m,n)$, so in particular $a^{\gcd(m,n)} \equiv 1 \mod d$. This argument was a series of iff statements, so that any divisor of $a^{\gcd(m,n)} - 1$ is a common divisor of $a^m - 1$ and $a^n - 1$ as well. Thus we have that $\gcd(a^m - 1, a^n - 1) = a^{\gcd(m,n)} - 1$, as desired $\diamondsuit$

Is it forgiveable that Georgia Tech taught me the Euclidean algorithm in so many of my classes? Although I complain, there was reason. There is a healthy lack of duplication of classes between the different schools and colleges. So programmers might take combinatorics, engineers might take prob/stat, anyone might take intro to elementary number theory or, if they were daring, abstract algebra, and mathies themselves would learn about it in the closest thing Tech has to an intro-to-proofs class, the dedicated linear algebra course (called abstract vector spaces). All of these teach the Euclidean algorithm (and most teach combinations/permutations and equivalence relations, too), but there was a general sense that classes were self-contained. Thus it was easy to take classes out-of-major.

Brown graduate mathematics does not have this self-containment. I understand this, and I doubt that any graduate math school would. Why reinvent the wheel? But it was one of the few times when I transitioned to a new school and actually had a different learning experience (maybe the only). This removes me from a seemingly key component of Brown undergraduate life - the open curriculum, also designed to allow students to take classes out-of-concentration. So when I'm asked to comment on Brown undergraduate life or the undergraduate math program (and I have been asked), I really don't have anything to say. It makes me feel suddenly older, yet not any wiser. Go figure.

Digression aside, I wanted to talk about progress on two conjectures. Firstly, the Goldbach conjecture. The Goldbach conjecture states that Every even integer greater than $2$ can be expressed as the sum of two primes. The so called 'Ternary Goldbach conjecture' (sometimes called the weak Goldbach conjecture' states that Every odd number greater than $7$ can be expressed as the sum of three primes.

It is known that every odd number greater than $1$ is the sum of at most five primes (link to arxiv, Terry Tao's paper). On 23 May, Harald Helfgott posted a paper on the arxiv that makes a lot of progress towards the Ternary Goldbach. In particular, his abstract states:

The ternary Goldbach conjecture states that every odd number $n\geq 7$ is the sum of three primes. The estimation of sums of the form $\sum_{p\leq x} e(\alpha p)$, $\alpha = a/q + O(1/q^2)$, has been a central part of the main approach to the conjecture since (Vinogradov, 1937). Previous work required $q$ or $x$ to be too large to make a proof of the conjecture for all $n$ feasible. The present paper gives new bounds on minor arcs and the tails of major arcs. For $q\geq 4\cdot 10^6$, these bounds are of the strength needed to solve the ternary Goldbach conjecture. Only the range $q\in \lbrack 10^5, 4\cdot 10^6\rbrack$ remains to be checked, possibly by brute force, before the conjecture is proven for all $n$. The new bounds are due to several qualitative improvements. In particular, this paper presents a general method for reducing the cost of Vaughan's identity, as well as a way to exploit the tails of minor arcs in the context of the large sieve.

Pretty slick.

Finally, and this is complete hearsay, it is rumored that the ABC conjecture might have been solved. I read of potential progress by S. Mochizuki over at the Secret Blogging Seminar. To be honest, I don't really know much about the conjecture. But as they said at the Secret Blogging Seminar: "My understanding is that blogs are for such things." At least sometimes.

Leave a comment

Comment via email