FORTH GO

If you look up any math term in Google, you likely get front page links to articles at Wikipedia and MathWorld. Both are usually very good, with the latter being more formal but having a Mathematica slant. (MathWorld is hosted by Wolfram Research, makers of Mathematica).

MathWorld has guest contributors but is otherwise closed content, unlike Wikipedia which is completely open. But as I found out last week, MathWorld does accommodate content suggestions. I completed the comment form twice for the Cuban Primes page, once for a typographical error and once for a factual error. I got a response noting the corrections a few days later. Not quite the turn-around of Wikipedia corrections, but still functional.

I can confirm the errors were fixed, though now I see the last modification time stamp wasn’t updated …

Fermat’s Last Theorem may have already been proved, but the proof is so dense amateurs like myself still foolishly search for a simple proof. My latest foray was centered around a trigonometric mappings.

That is, start with aⁿ + bⁿ = cⁿ, divide through by cⁿ and then map the resulting equation to the trig identity sin² x + cos² x = 1. So (a/c)ⁿ maps to sin² x and (b/c)ⁿ maps to cos² x, which means we need to find an angle x that sin^2/n x and cos^2/n x are both rational. If so, then we can raise them both to the nth power to get the trig identity and multiply through by the Least Common Multiple of the demoninators to get a solution to Fermat’s equation.

So we actually need to prove that sin^2/n x and cos^2/n x cannot be both rational for a given x, except for trivial cases like x = 0. That’s about as far as I got, but the presentation has a nice feature in that it suggests that n = 1 and n = 2 are special since those are the only values when 2/n is an integer. Likewise, they are the only values of n for which Fermat’s equation has non-trivial solutions. Also the trivial solutions to Fermat’s equation, a = 0 and b = 0, correspond nicely to the trivial solutions in the trig representation where x is 0 or Ï€/2.

I tried a Taylor expansion of sin^2/n x and cos^2/n x, but I couldn’t expand them at 0 since the exponents would result divisions in by 0. I expanded around Ï€/4, which has the nice property of sin Ï€/4 = cos Ï€/4 = sqrt(1/2). Still nothing obvious panned out. Simplifying infinite series is not a specialty of mine.

I was hoping to reduce each series to the form U ± V, where at least one of U or V can be proved irrational. In that case, I could prove that U + V and U - V couldn’t both be rational. If both U + V and U - V were rational, then their sum (2U) and their difference (2V) would be rational.

I recently saw a Simpsons episode where Bart and Lisa go on a field trip. The teacher pairs up students to use the buddy system to make sure know one gets left behind. Bart and Lisa are buddies and they both get lost. On the bus to return to school, the teacher asks, “is anyone missing their buddy?” Since Bart and Lisa are both missing, they get left behind, and a big deal is made later about the failure of the buddy system, previously believed to be infallible.

So that got me wondering, what modifications would have to be made to the buddy system to make sure no subset of the members got left behind? What’s the minimum number of buddies each member would have to have for a given population size? Some kind of hypercube of connections?

I think the solution is simpler than that: a chain system. That is, line everybody up and each person is responsible to remember the person before them and the person after them. Everyone except the first and last members has two buddies each. That gives N-1 links with mostly 2 links per member compared to the buddy system, which has N/2 links for exactly 1 buddy per member. Plus, the chain system works for odd numbers of members, unlike the buddy system.

Every so often I like to waste a lot of time trying to solve some practically impossible math problem, like finding a simple proof to Fermat’s Last Theorem or proving Goldbach’s Conjecture. These days I’m trying to find a quick way to factor numbers by using graphs to gain insights. (Unlike the other problems, solving this one would put me in an interesting dilemma about how to publish the solution.)

Trial division is the most basic technique for factoring numbers. You just go through candidate factors, dividing each one into the number to be factored and getting a yes/no for each candidate. My thought was to look at the result of the division (not just yes/no) and use that to decide how far to skip ahead for selecting the next candidate. The first graph shows trial divisions of the number 3341287, which is the product of two primes, 2087 and 1601. The candidate factors start at the square root of n and increase along the horizontal axis. The remainders are on the vertical axis.

You can definitely see patterns in the remainders, and it turns out the points lie on “concentric” quadratic curves. The equations for the curves are all of the form: x^2 - m*x + n, for some integer m. We can factor the quadratic into (x-a)(x-b) where n=ab and m=a+b, but that doesn’t help since n=ab is what we’re trying to solve in the first place. However, since each curve covers multiple points, we can reduce our work by iterating over m and solving each quadratic instead of iterating over each x. Unfortunately successive curves cover fewer and fewer factors, and soon it doesn’t help at all.

We might also try to solve the general quadratic. Using the quadratic formula we end up with something of the format k^2-n under the radical (where 2k=m), which means all we have to do is find a k that makes the square root an integer, or in other words an integer solution to k^2 - n = p^2, or k^2 - p^2 = n, or (k-p)(k+p) = n, but then we’re back where we started trying to factor n.

The second graph is the same as the first, but with a wider domain of x. Other interesting quadratics start to appear. In all graphs the red line represents y=x.

The technique of using the quadratics to skip candidates is basically the same as Fermat’s factorization method, except with a graphically inspired derivation. Fermat started where I ended, noticing that any odd number could be written as (k-p)(k+p) and then trying to find solutions by starting k at the square root of n and checking if each k^2 - n is a perfect square.

The last graph shows the remainders for the x values corresponding to the Fermat trial divisors. I think each “Fermat point” represents a quadratic curve from above, using the point with the maximum remainder (or 0 remainder). The green line is at y=n/x, and I’m not sure why all the non-trivial Fermat remainders are above it.

So iterating through quadratics is really the same as Fermat’s method, and we haven’t gained anything, but what about the patterns in the Fermat remainders themselves? Looks like there are some quadratics there as well and maybe we can use the same idea to reduce the number of Fermat points we examine. I’ve found that the quadratics are generally of the form x^2 - a/b * x + n/b, where b has been a small integer in my tests. I haven’t gone much further — there needs to be a way of iterating through these quadratics with confidence of convering all the candidate factors. Then again, even if only most of the candidates are covered, there’s some chance of finding a factor quicker.

At best, any attempt to use those quadratics will surely also be duplicating optimizations that have already be made to Fermat’s method. For instance, there is a method of re-centering the search by multiplying n by some number to offset the problem of diminishing returns once you get far from the “center”, and that sounds a lot like using the quadratics that have another center point.