The inverse buzz

Permutations on ℤ/nℤ

2010-09-20T17:38:00.000+08:00

Prescript: Okay, I suck at keeping to schedules. But you should already know that.

Here we'll be considering ℤ/nℤ, which is just the integers modulo n in a sense. Let a permutation function be a bijective function ℤ/nℤ→ℤ/nℤ. Here's the question: for which values of n can we find permutation functions f and g such that f+g is also a permutation function?

This isn't actually as hard as it seems. I've seen the method to solve this problem before (to solve rather unrelated problems). But anyway, here goes a complete solution. Consider first n=1. This isn't very interesting; trivially, there's only one permutation function, and that plus itself gives itself. Depending on whether f and g have to be distinct, the answer can be either yes or no.

For odd n ≥ 3 a proof by construction is easy. Let f(x)=x (which is trivially a permutation) and g(x)=x+1 (again also trivially a permutation). (f+g)(x)=2x+1 is then also a permutation since division by 2 is defined when n is odd. (If f=g is allowed, then the proof can be made slightly simpler by letting f(x)=g(x)=x.)

For even n, attempting to use a proof by construction with linear functions will fail. Give it some thought. This turns out to be because it isn't actually possible. Consider the sum of values of an arbitrary permutation function (linear or not); by nature of it being a permutation this is equal to (n(n+1)/2)=(n/2). This is a necessary but not sufficient condition to be a permutation. With two permutation functions, their sum would have a sum of values of 2(n/2)=0, implying that (f+g) is not a permutation function.

That wasn't too hard, right? Now consider a generalisation of this into arbitrary rings; is it still so easy to solve? (In particular, I have a feeling that the method used for even n won't work, but I'm lazy to work out the details.)

Meta: No posts for August, how sad

2010-08-23T20:40:00.000+08:00

Exactly what it says on the tin.

In related news, I got gold for SMO Open. Not a spectacular score (43/75), but yeah.

Also: I might do a post early September to make up for the lack of posts this month, although again there are no guarantees. (Yes, this implies I have an idea on what to write about. I do have a draft post on linear recurrences now, but it's really crappy. It's been a half-written draft for 30 days already, and I'm not sure whether it's something I want to write about.) There's been plenty of other maths-unrelated things I've been doing recently.

I'm just going to dump ideas here anyway; if you feel like doing research on these then by all means do so. First, the continued fractions of integer multiples of a constant (again, except just one transcendental number this time). Second, coquaternions (which are interestingly enough isomorphic to the 2×2 matrices). Third, overkill methods of solving simple problems.

The problem with the third is that it's hard to find examples that really bring out the essence of overkill. What I want is where there are no unnecessary steps, but involves unnecessarily complicated techniques to solve where simple (and obvious) ones suffice.

(This blog post open for discussion, although I strongly doubt anybody's still reading, with the ridiculously long hiatus and stuff.)

The sawtooth function, smoothing functions, Fourier series

2010-07-05T04:50:00.000+08:00

In this post we'll (just me actually, but that's an unimportant subtlety) consider Gibbs phenomenon in a sawtooth function; specifically, x→(((x+π) mod 2π)−π)/2, equivalently, x→x/2 over (−π,π). The Fourier series for this is

which is, thankfully, very simple. (There's actually selection bias here since I'm specifically choosing functions with simple Fourier series.) So, anyway, the partial sums of this series converges pointwise to the sawtooth function, except at the jump discontinuities. However, if you check the Wikipedia article Sawtooth wave, or more specifically, if you carefully look at the animation (File:Synthesis sawtooth.gif), notice that the overshoot just before the discontinuity doesn't tend to 0. This is explained by the Gibbs phenomenon.

Well, now that I linked that Wikipedia article, there isn't much else for me to elaborate on, except by examples. So I got my graphing program of choice (still KmPlot) and did some graphs.

Dark blue is the sawtooth itself, brown/dark red is 5 terms of the series, green is 10 terms. Pink and purple are smoothed versions (with 5 terms each), which do not experience any overshooting, asymptotically.

The first smoothed one (pink) was obtained by calculating the mean of the first five partial sums; this is equivalent to using the Fejér kernel instead of the Dirichlet kernel (direct summation). The most obvious drawback is that near discontinuities the convergence properties are worse, but the most apparent advantage is that convergence sufficiently distant from discontinuities is faster. (This is immediately visible for conditionally convergent Fourier series, but it's true provided that the function is not infinitely differentiable, and that the Fourier series also converges almost everywhere.) When considering least squares though, the disadvantage outweighs the advantage. Another equivalent (and more conveniently generalisable) way of stating this is that, with n terms, the first term has weight 1, second term 1−1/n, third 1−2/n, and so on until the nth term 1/n.

This gives two possible generalisations. One is to take the means iteratively. This one doesn't have a nice closed form, so I didn't bother. Another is to use (1−k/n)^a, which is the purple graph, with a=2. This was, like the previous one, with 5 terms.

Note that the Euler transform (and more generally the binomial transform), which I covered a few times before can be represented as a smoothing function; specifically, for the Euler transform the multipliers are the partial sums of binomial coefficients in reverse order. Among other things, for this particular sawtooth function, using 5 terms of the Euler transform increased convergence rates near zeroes a lot, compared to the other two smoothing functions. This can actually be explained by the Euler transform minimising the difference in derivatives. (This isn't included in the graph because I only thought of this after uploading the plot, and I can't be bothered to upload it again.)

The first smoothing function is "general-purpose", with nothing exceptional. The second oscillates less than the first (in an objective sense; the purple graph only has inflection points at the zeroes and the discontinuities), but also converges somewhat slower. (It's actually asymptotically the same for fixed a and n→∞; it just needs a few more terms to "catch up" for larger a.) The third converges as well as the first near the discontinuities and much faster far away from discontinuities, but in areas that aren't too near or too far the convergence is worse than the other two, and also seems to still exhibit Gibbs phenomenon, although I haven't verified this yet.

PS: notice the scale on the graph. Distances on the x-axis are about twice those on the y-axis. "about", because I didn't measure the exact ratio of the plot dimensions, but it should be accurate to within a percent.

PPS: This post is actually quite horribly written. Must be the sleep deprivation.

Happy last day of June

2010-06-30T19:52:00.000+08:00

I haven't been as productive as I intended to be. So far this year I managed a total of 12 posts not labelled "meta"; 3 for April, 1 for March, and 2 for the rest. Possibly 3 for June, but that's pretty unlikely. I've tried to keep the content here restricted to pure maths, but when I really have nothing better to put I just use filler in the form of computation-related issues. I've done that a few times so far.

Anyway, I'm currently reading the MIT OCW maths stuff. It's okay, but a bit over my level. I think I'll just keep reading.

SMO Open (round 2, 2010 version)

2010-06-26T15:11:00.002+08:00

Because it's so gratifying to be first, even when I didn't manage to do all the questions. (It was more egregious last year.) Below are the questions.

Let CD be a chord of a circle Γ₁ and AB a diameter of Γ₁ perpendicular to CD at N with AN > NB. A circle Γ₂ centred at C with radius CN intersects Γ₁ at points P and Q. The line PQ intersects CD at M and AC at K; and the extension of NK meets Γ₂ at L. Prove that PQ is perpendicular to AL.
Let a_n, b_n, n = 1, 2, … be two sequences of integers defined by a₁ = 1, b₁ = 0 and for n ≥ 1,
a_n+1 = 7a_n + 12b_n + 6
b_n+1 = 4a_n + 7b_n + 3.
Prove that a_n² is the difference of two consecutive cubes.
Suppose that a₁,…,a₁₅ are prime numbers forming an arithmetic progression with common difference d > 0. If a₁₅, prove that d > 30000.
Let n be a positive integer. Find the smallest positive integer k with the property that for any colouring f the squares of a 2n × k chessboard with n colours, there are 2 columns and 2 rows such that the 4 squares in their intersections have the same colour.
Let p be a prime number and let x, y, z be positive integers so that 0 < x < y < z < p. Suppose that x³, y³ and z³ have the same remainder when divided by p, show that x² + y² + z² is divisible by x + y + z.

Like before, 5 questions. This is only the second time I'm participating in the Open section, so conclusions may be rusty, but it seems that the first question is always about geometry, and the last about number theory, involving three variables.

Anyway, I only managed to solve 2, 3 and 5. 2 was incredibly easy, involving just induction (although it took me some time to see the relation); 3 was a number theory textbook example. My method of solving 5 was to first establish some basic facts about cube roots modulo a prime, such as the numbers, except for 0, having 3 cube roots each. I used primitive roots, which are hopefully fine. (I didn't bother proving the existence of primitive roots modulo primes, which might be a problem.) With that, x+y+z is necessarily either p or 2p; by then showing that the remainder on division has both 2 and p as factors (I did these steps separately) the remainder must be 0.

Iterated functions that converge slowly

2010-06-07T18:11:00.001+08:00

This is somewhat related to the sine map I was talking about a few months ago. Here I'm only concerned with nonnegative real numbers, and where the fixed point is at 0. (There may be other fixed points, but I'm not concerned with those, especially since they're not real and positive.) The specific function I'm talking about is of the form f(x)=x−x^1+β, where β is a positive number.

Notice that we can actually let f(x) be like x−x^1+β+O(x^1+γ) where γ>β for x~0, without changing much, since the basic iterative behaviour only depends on the secondary term. (Of course, explaining the whole iterative behaviour will use all terms, but that's not what I'm concerned with here.) Starting from a positive number, by iteratively applying f, it will converge to 0.

But first, a notational convenience is helpful. fⁿ(x) refers to applying f n times on x, not the nth power of f(x).

We have a basic (and rather obvious result); x−fⁿ(x)~nx^1+β, when n is a constant. By ignoring the "constant" requirement of n and trying to solve this asymptotic expression to be equal to x in terms of n (equivalent to the equation fⁿ(x)~0), we get n≈x^−β.

Note that it's impossible for repeated application of f to reach 0, although it does reach arbitrarily close. At this point I couldn't quite figure out what was going on, so I resorted to computation, which seems to show that f^{x^−β}(x)/x is a constant, which seems good enough. It seems fair to generalise this a bit more to get that f^{αx^−β}(x)/x is also a constant, where α is a constant.

And it turns out that there's actually a simple form for the constant in terms of α and β, which I've not been able to prove. (I got it by subbing in values for α, β and x, extrapolating, and checking with other values of α and β.) Because it's the main result of this post, it'll be rendered in LaTeX just to show how important it is. Yeah. (That's actually a lie. The main reason is that it's not easy to have text below text in HTML, as needed for the limit, although I could just have used subscript, but that looks less nice.)

By letting β be 2 and α be suitably scaled, this result applies for sine as well, which is nice. Note also that this still applies even when α is negative (i.e., taking the inverse function instead), provided that α>−1/β. So this also gives results for arcsine and hyperbolic sine, which are equal up to the secondary term. Not that this solves any of the problems in the earlier blog post about the sine map, although it's interesting regardless.

Postscript/update: I didn't think this would be important, but if αx^−β is not an integer then just take the nearest integer, or generalise function iteration to nonintegers. Either works, since in the limit this value tends to infinity, unless α is 0, where the result is trivial. Also, one mistyped word fixed.

The no-loop problem (hypercube graphs)

2010-05-18T19:52:00.001+08:00

I did some reading on graph theory. So now, I can actually state the problem in a more terminologically appropriate manner. The no-loop problem is about finding the number of vertices in the largest (in the sense of having the most vertices) induced subgraphs with no cycles of given graphs. Not that the previous description wasn't accurate, just that it was a bit wordy.

Anyway, back to topic. The hypercube graphs, also denoted Q_n, is an interesting case, because there are some trivial results that can be derived very easily, and also because it's particularly convenient to program. (Using the z-order allows induced subgraphs of Q₁ to Q₅ to be conveniently packed into a 32-bit integer type.) One particular result is that the number of vertices that need to be removed for Q_n must be at least double that for Q_n−1 for n>0. This is obvious from the inductive definition of the hypercube graphs.

Another obvious result is that removing vertices of a certain parity leaves half the number of vertices, and no edges at all, implying that the no-loop number for Q_n is at most 2ⁿ⁻¹. Now put these two obvious results together to get the not-so-obvious result that the ratio of removed vertices to the total number of vertices tends to some constant. I suspect this ratio is 1/2, but I don't have sufficient numerical data to back me up for that. Showing that it never reaches 1/2 is of course, again, trivial.

And on numerical data. In the last post about the NLP on this blog, I mentioned that the no-loop number for Q₅ was between 12 and 14 (inclusive). Now, with the aid of a program, I managed to brute-force out all 12-removed and 13-removed induced subgraphs of Q₅, showing that all of these have some cycle. Oh, and by the way, while the no-loop number for the 4-cube graph is 6, there are only 8 ways to remove 6 vertices from Q₄ removing all cycles, and these 8 ways are all rotations of each other in 4-space. That was a bit unexpected.

There are other things we can conjecture. For the 2-cube, 3-cube, 4-cube, 5-cube graphs, restricting the removal of vertices to those of the same parity does not increase the no-loop number. Assuming this, checking that the no-loop number for the 5-cube graph is 14 is almost trivial.

Something to note about the hypercube graphs is, by dividing the graph into two smaller hypercube graphs, if the two smaller graphs have exactly the same pattern of vertices removed (and are in the same orientation), and if these partitions have at least one edge, there must be a cycle. This isn't really useful except for counting the number of ways to remove vertices such that there are no cycles.

And counts. There are 32 ways to remove 3 vertices from a 3-cube graph (2 ignoring symmetry), 64 to remove 4 from a 3-cube graph, 8 to remove 6 from a 4-cube graph, 1008 to remove 7 from a 4-cube graph, 4090 to remove 8 from a 4-cube graph, and 1952 to remove 14 from a 5-cube graph.

I'm going to extend my program to handle the 6-cube, 7-cube and 8-cube graphs soon. Expect those results soon.

PS: I searched OEIS for 0,1,3,6,14, and none of those results correspond to this sequence. Dropping the 0 gave a lot of candidates though.

Update: the values for the 4-cube, 7/8-removed and for the 5-cube are suspect. I recently ran a brute force check, which somehow gave the number of ways to remove 14 from Q₅ as 2160 instead of 1952. It's in fact probably an error in my code; when I first tried to do the brute force test the program crashed. I could switch from C to another programming language with better memory checking, but the downside will be greatly reduced speed. Among other issues I spotted were that symmetries of the hypercube "destroyed", according to my program, the no-loop property, which is obviously absurd.

The imaginary continued fraction (redux)

2010-05-16T18:27:00.000+08:00

First I'll direct you to a post I wrote plenty of months ago, The imaginary continued fraction again. Oh wow, that was unexpected. You probably already know what this is about.

Anyway, note that we can rewrite the recurrence relation as a Möbius transformation, from whence we can rewrite as a matrix. More specifically, the recurrence relation is x→(2x−1)/(x+2), with the corresponding matrix [2,-1;1,2]. But then from here we realise that this is actually the matrix representation of the complex number 2−i. Oh my, that was mindboggling. We got from a continued fraction to a recurrence to a matrix to a complex number. We can actually go one step further; taking the argument of that gives −arctan(1/2).

Anyway, since composing the Möbius transformations is isomorphic to multiplying the matrices (ignoring constant scalar multipliers) which is isomorphic to multiplying the complex numbers (again ignoring constant real multipliers) which is isomorphic to adding the angles modulo 2π, essentially what we've done is to reduce it into a problem of whether there is some positive integer power of 2−i that is purely real. Of course, given that arctan(1/2) is not a rational multiple of π, this is obviously impossible.

PS: This post was originally going to be longer, with more interesting details, but I got lazy. Actually more like I rage quit because the hostel proxy cut me off arbitrarily before Firefox crashed while I was writing the original version of this post, causing Blogger's autosave to fail and my text to be gone. I'm not going to blame Firefox; if you follow my main blog you should know that I use nightly builds, which are inherently prone to crashing.

Sample range over the uniform distribution

2010-04-21T16:51:00.000+08:00

Let's say we have a uniform distribution (which for simplicity purposes we'll take to be the standard uniform distribution U(0,1)), and we take n samples from this distribution. How is the sample range (the maximum value minus the minimum) distributed?

I couldn't find an obvious answer for this, so I did a simulation (with a high-quality pseudorandom number generator) for some n, applied some of my intuition, and compared the results. The numbers were close, so I'm probably right. It's actually a beta distribution, dependent on n (obviously). Exactly why it is the beta distribution isn't clear from the description of the beta distribution in either Wikipedia or MathWorld. (In other words, it's probably just due to coincidence.)

More precisely, it's a special case of the beta distribution. For n samples, the distribution of the sample range is B(n−1,2). Equivalently, the pdf is λx.n(n−1)(1−x)xⁿ⁻² over [0,1]. The cdf is easily obtained from integrating that.

Written in that form, it's pretty clear how my reasoning went. The first two points can be anywhere, and the pdf for the special case n=2 is obviously 1−x. The remaining n−2 points must go inside the range, which happens with probability xⁿ⁻². Taking these two events as independent, we can multiply them together to get the distribution.

Interesting is that when n=3, the distribution is symmetric about ½. There's no obvious intuitive explanation for this. At least none that I can think of.

Quite surprisingly I didn't manage to find any info about this on Wikipedia. That said, I just checked MathWorld, and found the answer. Which just serves to confirm that my intuition was correct. And also to show that checking sites other than Wikipedia is occasionally beneficial.

Oh my, it's April

2010-04-21T16:18:00.000+08:00

Surprisingly many posts this month. That is all. Actually, no. For the past few months I've been more-or-less struggling to get a proper post up every month. I find it's quite annoying if I write a post but only let it publish when it's a new month, because in cases where I get sudden surges of inspiration readers will have to wait, and by that time I might have forgotten about certain aspects or details, meaning that I won't be able to appropriately respond to comments.

And comments… all the recent ones were spam. Oh wow, what a surprise. In all honesty, I didn't expect the comment policy to affect anything. Actually I was lying. I was hoping it would change things a bit. Nothing changed.

Anyway, back to topic. One side effect of posting as and when I get ideas is that there might occasionally be months without any posts. You have been informed. I'll try to keep up, but I can't promise anything. I might write more about having a post queue on my main blog if I feel like. Or maybe not. I feel like sleeping right now.

An integral for γ

2010-04-16T14:33:00.001+08:00

This was quite unexpected. This came up when I was fiddling around with the log integral. I can't figure out why this is the case; if I'm not wrong this provides a/an (inefficient) formula to compute γ if we use the Laurent series expansions of the terms about x=1 and integrate term by term. The reciprocal terms will cancel out, so this makes stuff particularly convenient. That said though, I'm not exactly sure that the expansion for 1/ln(x) is suited for computation.

Update: seems like I missed it by a bit. It's actually quite obvious; taking the series expansion of li(x) and subtracting ln(x−1) (then combining the log terms and expanding) leaves the series as γ+O(x−1), as x→1.

Iterated cubic (exam question)

2010-04-15T01:29:00.000+08:00

This is from a 2008 maths exam paper. The question:

The graph of y=h(x) intersects the graph of y=h^-1(x) at x=2 and x=3. Given that h(x)=x³+ax+b, find the values of a and b.

I was still stuck on that question until a few hours ago. Don't question. The first step is quite obvious; basically what we're looking for is a fixed point of h∘h. Then from there we can determine the trivial solution corresponding to 2 and 3 being fixed points of h, which gives a=−18 and b=30. This was the solution that the question setter wanted. However, it's not too hard to see that if we let (2,3) be a period 2 cycle (i.e. h(2)=3 and h(3)=2), this also gives a solution a=−20 and b=35. From there it's not obvious that these two are the only solutions; in fact, there are three other solutions.

My first attempt during the exam was to expand out everything. Needless to say, this wasn't a good idea. My second attempt was the trivial solution, and I thought some more and got the second solution. And actually it's a trick question; the function h has two relative extrema for these two solutions and are not invertible over [2,3]. Bet you didn't see that coming. Oh, and by the way calculators weren't allowed for that part of the exam, so graphing it would have been impractical.

Some time back I tried to resolve the equation into two equations of second degree in a and b, but I probably made a mistake somewhere, since there are 5 solutions and conics intersect at at most 4 real points, and that the not-so-trivial solution wasn't among the solutions of the conic intersections. (At the time of trying that method, I only realised the latter. Checking never hurts.)

Now, 2010. I try again. First we'll need a lemma. (Actually not really, while it helps to demonstrate why one particular step works it's not actually necessary to proceed with getting the answers.) For any polynomial function P, P(P(x))−x is divisible by P(x)−x, in the sense that (P(P(x))−x)/(P(x)−x) is also a polynomial. This is quite simple to prove, and becomes obvious with a few moments of thought. You can probably see where this is going. Notice that if you expand h(h(x)) you get a third degree equation in a and b; that's rather intractable by itself, so we look to factoring it.

So since h(h(2))−2=0, we can (for now) reject the trivial solution, to get (h(h(2))−2)/(h(2)−2)=0, or expanding it, (I don't feel like using HTML anymore to render equations)

and likewise for (h(h(3))−3)/(h(3)−3),
.

Hey look! We have two conics, and we can pretty easily solve them for the intersection. However, because I'm lazy (to make a program to do that or to do that by hand), let's try a different approach. Taking the second equation and subtracting the first, we get another conic, where the b² term vanishes. This allows us to conveniently rewrite b in terms of a (without involving square roots).

Substitute that into the first equation, expand everything, and ignore the denominator. This gives a quartic equation in a.

At this point it seems like we might as well just use the quartic formula to solve it, but that's a severe waste of effort. The reason is obvious: we already have one of the roots, a=−20. Dividing out gives the cubic polynomial a³+62a²+1221a+7677. And here we're stuck, this equation cannot be factored into integer polynomials any more. That obviously doesn't mean that there aren't any more solutions; by visual inspection this guarantees the existence of three more solutions. I'm not going to put the closed forms for these values, that's too tedious.

The three other solutions are, in order of decreasing a, (first value is a, second is b)
-13.880638929428884792166930157925, 15.617929496135482197651068093891;
-18.980733400749410862968110883025, 25.090971561771816085322956864739;
-29.138627669821704344864958959050, 54.291098942092701717025975041370.
(Values rounded to 30 decimal places.)

And finally, I solved this problem. Finally.

Composing Möbius transformations to obtain constants

2010-03-30T00:08:00.000+08:00

Möbius transformations take a complex number to another complex number; what I'm concerned here is more about those taking rationals to rationals; converging to some irrational number. What we're going for now is to get a convenient way to express certain irrational numbers of interest as an infinite sequence of Möbius transformations. It'd be useful to know more about Möbius transformations; with a bit of thinking it's not too hard to show that the transformation z→(az+b)/(cz+d) is equivalent to left-multiplying the vertical matrix (z;1) by (a,b;c,d).

A certain property of matrices makes this particularly useful: matrix multiplication is associative. In other words, we can group up the terms and apply multiple terms at once. Or that we don't have to apply them in order, which is actually an extremely useful thing, because sometimes the standard order starts from the infinite tail, which is obviously impossible to work with directly.

An example of a constant that can be easily represented is √2, where the continued fraction [1;2] leads to the simple representation as (λx.1+1/x)(λx.2+1/x)(λx.2+1/x)(λx.2+1/x)…(2), or, writing as a matrix product,

Note that using (2;1) for the last matrix isn't really necessary; choosing any constant would work.

One nice thing about this representation is that it leads to a simple algorithm for converting into any integer base greater than 1, under the assumption that arbitrary-precision arithmetic is used. For instance, using Python, I managed to write an unobfuscated program to calculate √2 to arbitrarily many digits in 20 lines. The basic method of converting representations is given in Unbounded Spigot Algorithms for the Digits of Pi.

Obviously the paper linked above focuses more on π, since, well, it's part of the title. There Gosper's fast series (with term ratio 2/27) was used to provide a fast digit churning algorithm. Apart from that, though, the basic factorial-over-odd-double-factorial series (term ratio 1/2) and Lambert's continued fraction were also considered. Note that in such situations Ramanujan's formula and the Chudnovskys' formula aren't useful since they involve a square root multiplier.

Of course, if we just want to calculate √2, the Babylonian method is likely the fastest. That said, though, it's possible to chain an infinite sequence of transformations that converge to √2; by converting to matrix form and squaring repeatedly, the result is effectively the same as the Babylonian method.

I'm currently thinking about this idea applied to other continued fractions; of interest are other square roots and maybe e.

Complex sine map (again)

2010-02-25T21:04:00.004+08:00

I made a simple plot of the complex sine map as described in the previous post, black/dark areas probably converge, white/light areas probably diverge. It's more than 1 MB large, so I'm not going to include it directly here, just a link. Get it here. (The x axis goes from −4 to 4, y axis from −8 to 0.) I say probably because the superexponential growth means that it quickly becomes impractical to check whether a particular point converges or diverges. It's not too hard to see that there are points with arbitrarily large imaginary parts that converge to zero.

Other things we can note from the plot is that the plot is periodic with period π, which is quite obvious if you think about it for a while. There are also other lines with easily proven convergence, such as π/2 + yi for real y. (Same for other odd multiples of π/2.) Just like the main line (y=0) has these vertical lines sticking out, these vertical lines themselves have lines sticking out, although these lines are bent, and apparently have x=nπ as asymptotes; what these means is that merely by straying slightly from the imaginary axis the point could possibly converge.

Note that as I mentioned above, the plot is not fully accurate, like some other software plotting similar things (such as the Mandelbrot set), the limitation is in that the software can only run a finite number of iterations (48 here) before having to decide whether a particular point converges or diverges. There's also another limitation here not present in Mandelbrot set renderers; specifically that overflow occurs at around 1.8⋅10³⁰⁸, so any point that hits that value will be considered to have diverged, even though it might still converge to 0 later. There's also only 53 bits of precision, or about 16 significant figures, which means that once this threshold is reached the computation of sine and cosine becomes completely useless, because the next representable number can have very different sine/cosine values. (Damn, I could write a full post about the difficulty of high precision computation!) The effect of this (and the above paragraph) is that the plot could be completely irrelevant.

Oh, and in case it wasn't obvious enough, the plot looks like a fractal. In fact it should be, as should be evident from the second paragraph above. Exactly what the fractal should look like though, is a different matter. The dimension of the fractal is… I don't know. Even from the lines-branching out simplification, the ratio changes, and it's not an exact correspondence.

PS: Crappy followup to a crappy post. Meh.

Update: I found this video The Iterated Sin Fractal. The video is basically just the same thing as my plot, but with less noise and some panning.

Update: typo fixed.

Complex sine map

2010-02-24T12:22:00.003+08:00

Some time back I was thinking about the sine map, where it maps a number to its sine, or x↦sin(x). It's not too hard to see that starting from any real number 0 is eventually reached. For the sake of filler, I shall present my argument. Without loss of generality, let x be a positive real number. For all possible x, x>sin(x), so taking the sine reduces the magnitude. From here it isn't hard to see that all real numbers must converge to 0 under this map. Of course, the rate of convergence is very slow, and obviously sublinear. (The derivative around the fixed point is about 1, which means a damn slow convergence or divergence in general.) That's not actually what I'm concerned with in this post.

What I actually want to know is when the sine map is applied to the complex numbers. Here by a similar argument it can be shown that all imaginary numbers (other than 0) must diverge to infinity, and do so superexponentially. (It grows like tetration, but I don't know of an adverb form for that.) But what about all the other numbers? After all, the complex plane isn't just two lines. Well, that's a problem. I haven't managed to show there are any points that converge or diverge other than the real and imaginary numbers. (Here by "and" I mean a union, not conjunction. Stupid language.) While some points with small imaginary parts appear to converge, there's no guarantee that the imaginary part won't grow fast enough to diverge (to infinity or otherwise). Likewise, for large imaginary parts, there's no guarantee the real part won't be sufficiently close to an odd multiple of π/2 to bring the imaginary part close to zero.

One thing to note is that the map is not injective; by definition values differing by a multiple of 2π will map to the same value. Each iterate compresses the complex plane into a 2π by ∞ strip and then blowing it up to the fill the plane again; the question is whether this compression will result in a single point, or multiple points, or an infinite set of points (and with what dimension in this case).

Not so similar to the sine map is the cosine map. The cosine map has a fixed point at 0.739…, unlike the sine map. Real numbers converge there after some time, approximately linearly. As for anything else, I'm not sure. The nonzeroness of the fixed point makes things weird.

I'll probably be running a simulation of this sometime soon.

There's another type of sine map, x↦Csin(πx), applying to just the real numbers over [0,1], which is mostly unrelated. I'm not really interested in this, so I'm not elaborating further.

PS: Hiatus broken, with a rather crappy post that this is. Meh.

Update: Fixed an error in my reasoning in the 3rd paragraph.

Matrix magnitude

2010-01-17T16:43:00.003+08:00

There was something I wondered. Given a square matrix X, can we define the size of X, s(X), in a way that is useful? The determinant is an early candidate, that unfortunately fails the test, because some singular matrices are not nilpotent and have increasing powers tend to infinity, but have determinant zero. Basically, what we want is something like this. Let s(X) be a nonnegative number c such that, firstly, for all ε>0, the matrix (X/(c+ε))ⁿ has every entry tending to 0 as n→∞, while, secondly, for all 0<ε<c, the matrix (X/(c−ε))ⁿ has some entry that does not tend to 0.

Note that for nilpotent matrices the above definition of s gives the size as 0, because if c≠0 then the second condition does not hold. Also, I've not shown that this necessarily gives a result for the size; there might be pathological matrices for which the size can only be defined as being two numbers c and d such that 0≤c≤d and (X/(d+ε))ⁿ tends to 0 (for ε>0) and (X/(c−ε))ⁿ not tending to 0 (for 0<ε<c), for the smallest d−c possible. If I'm not wrong, this is the most pathological things can get. For this we can let d be the upper size and c be the lower size. (When just size is mentioned it is assumed that the upper and lower sizes are the same.)

Some basic facts. For a matrix (over the real numbers), the upper size is bounded above by the magnitude of the largest (in the sense of largest magnitude, not in the sense of most positive) element in the matrix, multiplied by the width. This is quite easy to see, although it's not straight away obvious. Let A be an n×n matrix where every entry is 1. It's then pretty obvious that s(A)=n. From this, take the absolute value of every entry in a matrix, then notice that replacement of entries by larger entries only increases the size. (Alternatively, for a slightly tighter bound, use the maximum of the row and column absolute-value sums.)

There are some other things we can note. When the lower size is 0, this means that the entries decay faster than exponentially… which is only possible when the matrix is nilpotent, or in other words, a size of 0 is equivalent to nilpotency. Also, this size measure is linear, in that s(xA)=xs(A) for all matrices A and positive real numbers x. The identity matrix has size 1, as expected, and s(xI)=x.

So far we've covered some simple cases: matrices where every entry is the same, nilpotent matrices, and identity matrices. Time to cover even more, because I can't figure out this stuff for non-simple cases. We have lower and upper triangular matrices, where I'll only consider upper triangular matrices because they're equivalent under transposition. The size of an n×n upper triangular matrix U is probably the largest value on the diagonal. (Note: I'm not very sure whether this is correct.) Contrast this with the determinant, which is the product of all the values on the diagonal. When the diagonal values are all 1, observe that the value in the top-right corner grows like a polynomial of degree at most n−1, and the size and determinant are both 1.

For n×n matrices where all the nondiagonal entries are the same and nonnegative and the diagonal entries are the same and nonnegative, let a diagonal entry be a and a nondiagonal entry be b. The size is then a+(n−1)b, or equivalently, the row/column sum. This isn't quite correct when a or b is allowed to be negative.

Time to handle slightly less trivial stuff. We now have A a 2×2 matrix over the reals. How would we find s(A)? I haven't figured out the closed form yet, although there are some simple special case results. (Due to me not feeling like using TeX for these matrices, I'll show them inline. The format shouldn't be too hard to understand.)
s([[a,c][0,b]]) = s([[a,0][c,b]]) = max(|a|,|b|)
s([[1,1][1,0]]) = (1+√5)/2=φ
s([[1,2][3,4]]) = (5+√33)/2
s([[1,3][5,7]]) = 4+√24
s([[2,3][5,7]]) = (9+√85)/2
The second one is an obvious consequence by relation to the Fibonacci numbers. It seems that for 2×2 matrices the size is always a quadratic irrational; more precisely, a quadratic PV number. Is this correct?

Update: I was obviously wrong about the PV number part; by simply taking a sufficiently large multiple the matrix sizes are no longer PV numbers. And while I'm very sure about the quadratic irrationality part, I haven't found a proof yet. Might we similarly expect that n×n matrices have sizes that are roots of degree-n polynomials? How is this polynomial related to the matrix?

Reverse decomposition of waveforms

2010-01-17T02:46:00.001+08:00

The basic idea behind this is like this. Basically, given a periodic function f (with no undefined points except at jump discontinuities), it can be decomposed into a series of sine functions. Specifically, what we want to consider here is the sawtooth wave, which admits a very simple decomposition. First, definitions.

Let f be the sawtooth function over the real numbers as defined by f(x)=π⋅(⌊x/(2π)⌋−x/(2π)+1/2). With the use of a Fourier transform, this decomposes f into
,
which is very apparently simple. This explains the π and 2π scaling factors in the original definition.

Now we invert this expression, to decompose a sine wave into sawtooth waves. We could either do this manually, expanding term by term via sin(x)=f(x)−sin(2x)/2−…, or by a (provably equivalent) Möbius inversion, which gives the almost-as-simple expression of sin in terms of f:

It's quite interesting to see how this version of sine converges as terms are added, at least if you have no life (like me). If you're lazy, basically it's like noise that hugs the sine wave closer as terms are added, except that (for n terms used) when M(n)=0 (or by some other similar condition), the amount of noise near multiples of 2π seems to be exceptionally small.

The nice (or not-so-nice) part about this is that because the sawtooth function I defined is not continuous, the convergence of this inverted decomposition is quite slow; an alternative explanation is that the coefficients μ(k)/k tend to 0 slowly, and do not form an absolutely convergent series. This is (probably) the source of the aforementioned apparent noise.

We could do this to other waves; of particular interest would be more well-behaved waves that have no discontinuities. An example would be the similar triangle wave, where we'll just define from the sine decomposition,
.

Notice that this function is uniformly convergent, because the coefficients form an absolutely convergent series. If you bother to actually plot this up to a finite number of terms, note that the area around the extrema seems to have exceptionally poor convergence compared to the rest of the function; I think this is because the derivative there tends to 0, yet the left and right limits are of opposite sign. (And then there's stuff like the Gibbs phenomenon, which makes things worse in cases like this.) Anyway. This expression isn't as easy to invert as the sawtooth one. The Möbius inversion doesn't work here, which is hardly encouraging. So here we'll take the naive approach and expand continuously. My quick check fails to reveal any possibly correct formula for the coefficients. The first few are (for the odd numbers, starting at 1) 1, 1, −1, 1, 0, …, with some coefficients appearing to have magnitude greater than 1. (That, I have not verified; while it seems correct I might have made a mistake in my calculations.)

Regardless, of course, me not knowing the existence of a simple closed form does not mean that such a closed form does not exist. Plotting sin in terms of g for finite number of terms is similarly interesting, although the reduced amount of noise (due to uniform convergence) makes it less visually appealing.

Update: one typo fixed ('an' → 'and').

Meta: comment policy

2009-12-25T20:06:00.007+08:00

I need to keep things in check. So here's the official comment policy.

Comments should not include links to sites irrelevant to the post.
Real names should be used for posting.
Comments may be freely deleted at my will.
Comments should be in English. Simplified Chinese is also fine, but any other language will be ignored (and deleted).
You agree that all content in the comments may be used under any of the Creative Commons licences and may be used by me without any copyright restrictions, unless the copyright of the content belongs to an other entity in which case this is affected by point A.1 below.

By commenting on any of the posts in this blog you agree to all of these points. (Including the ones below.)

Addendum A (2009/12/26):

You also agree that either you own all the copyright to the content in the comment you want to post or the content is available under a free Creative Commons licence or is in the public domain or is otherwise permissively licensed. (The "permissively" part is at my discretion; it basically includes licences such as the revised BSD licence.)
Directly using line breaks should be avoided; use the XHTML tag instead.

Point 5 has also been revised in accordance to point 6 A.1. Also, yes, I know there is a loophole here that can be used to prevent me from using the content without copyright restrictions. By transferring the copyright to another entity, a commenter can then post the content covered by point 6 A.1 and not point 5. This comment policy is not retroactive; the few comments previously posted are not subject to these. Point 7 A.2 is a also a pain in the ass because Blogger automatically converts line breaks to and not , representing an inconsistency between some default templates (which use XHTML), the HTML post interface (which also uses the XHTML ) and the comment posting interface (which uses HTML).

Update: I'm fiddling around with the XHTML and CSS to make the numbering correct; for now the numberings for the lists are completely screwed up, but the content should still be readable.

Update: I give up on fixing the numbering; the CSS spec doesn't make much sense. Lettering the addendum/addenda. Also, fixed an ambiguous point in A.1.

A proof of Fermat's Little Theorem

2009-12-25T19:58:00.001+08:00

(Prescript: Mind you, this isn't about the Last Theorem, which is much harder.)

There's a simple proof of the Little Theorem based on combinatorics. Theorem: Let p be an aribtrary prime number. Then for all integer a, a^p≡a (mod p).

Let S be the set of strings over an alphabet {0,1,…a−1} of length p. The cardinality of S is then a^p. Define a cyclic shift of m, m in 0 to p−1, over a string s∈S, as the last m letters concatenated to the first p−m letters.

The only strings that are fixed points of nonzero cyclic shifts are those with only 1 distinct letter from the alphabet, since p is prime. Consequently, excluding those a strings from S, the cyclic shift operation becomes a group operation with period p for every element; this means that p|(a^p−a), completing the proof.

Okay, granted, this isn't the nicest proof, but to my knowledge it is original. I don't think this proof can be modified to prove Euler's theorem, unlike some other proofs of the Little Theorem.

Update: ninja'd by 53 years. It's even the first proof in Wikipedia's list. There's a chance I might have seen read the linked Wikipedia article (and also this proof) before, although I can't objectively claim either way. Looking at the bright side, at least I didn't get ninja'd by someone like Euler right?

On squarefree numbers (again)

2009-12-13T00:48:00.003+08:00

I made a plot of the function Q(x)−x/ζ(2) as described in the previous post. Here the bounding functions are ±2√x.

Some observations to make. We know that the first definition of Q(x) I gave in the previous post (as the sum of the absolute values of the Möbius function over the positive integers) is actually (a specific case of) the Dirichlet series ∑_k(|μ(k)|⋅k^−s) cut off at x terms. This can be transformed into something involving the zeros of the ζ function, where by assuming the Riemann hypothesis a better result for the error term than O(x^1/2) can be obtained. Wikipedia mentions that the current best bound, assuming the RH, is O(x^17/54+ε), just under the cube root. One of the references cited in Wikipedia also mentions that there is a known (unconditional, iirc) lower bound, specifically Ω_±(x^1/4), or in other words not o(x^1/4).

An implication of the upper bound of the difference is that it is o(√x), if the RH is true. In other words, taking the graph, even if the bounding functions (blue and green) are downscaled by any factor, the pink function will eventually remain trapped by the two bounds from some point on (assuming RH).

PS: ~~I will update this post properly; battery with few minutes left.~~ Update: done.

PPS: The graph might not be fully accurate. The values of μ were computed by hand, since the program (KmPlot) doesn't do number theoretic functions. The first time I plotted it I left out two non-zero values.

Update: fixed two mistakes.

Asymptotic form for the quantity of squarefree integers

2009-12-01T03:06:00.002+08:00

I found this (the stuff below) in the book An Introduction to the Theory of Numbers (G. H. Hardy and E. M. Wright, page 269), and I modified it slightly. In particular, while the book only gave asymptotic bounds, I will provide obvious hard bounds. ("obvious" in the sense that if the derivation was done with this in consideration the bounds are quite trivial to obtain.)

Let Q(x) be defined (for non-negative x) as the number of squarefree integers less than or equal to x. (Using an alternative notation, Q=∑|μ|.) Let y be an arbitrary positive number not less than 1. Then by some magical argument (I don't quite get the wording in the original, although overall it still makes sense),
.

Now perform a Möbius inversion to obtain Q(y²) in terms of a sum of λk.⌊y²/k²⌋. This gives
,
where the real fun begins. We see a floor here, so we temporarily remove it by defining another function α(y²)=∑_k≤y[μ(k)(⌊y²/k²⌋−y²/k²)], so we now have
.

Notice the ∑_k≤y[μ(k)/k²] in there, which is the same as the sum representing 1/ζ(z) at z=2, except with the tail cut off. This can be rewritten as 1/ζ(2)−∑_k>y[μ(k)/k²]. Bounding the absolute value of this tail approximatively is not difficult, and can be done by just taking the absolute value. This gives the bounding interval as (1/ζ(2)−1/y , 1/ζ(2)+1/y).

As for α(y²), note that, for all real z, z−⌊z⌋ is bounded within [0,1). So, by just taking the absolute value, we have that |α(y²)|≤Q(y)≤y. With this in place, we can give the final asymptotic bounds as

(where the plus-minus sign should be taken as meaning a range, not a choice of two options). From here, substituting x=y² gives the final form
.

Note that this isn't the tightest bound on the constant multiplier even without much further analysis; by application of this result to the earlier bound for α, the multiplier can be reduced to 1+6/π², at the expense of having an extra term and lesser elegance. Also note that the range is an open interval; if x is positive, then the upper and lower bounds are never reached, as can be seen from either the derivation itself or the transcendence of π. (The bounds can only be exactly reached when x=0.)

Also, note that this derivation is easily modified to cover the cubefree, etc. numbers instead of the squarefree ones.

Breaking RSA, factoring integers

2009-11-23T17:47:00.001+08:00

Prescript: this post does not contain any effective method of breaking RSA.

Just for the sake of filler, let's review what RSA is about. Basically, given two large-ish primes p and q (that aren't too close to each other), the encryption of a plaintext number/message P, C, is given by C = (P^e mod pq) where e is the encryption exponent, chosen to be not-too-small, and also coprime to φ(pq). Decryption is then P = (C^1/e mod pq) where 1/e is the multiplicative inverse modulo φ(pq).

Now let's see the fundamental assumptions behind the unbreakability of RSA. The most obvious premise is that φ(pq) = pq+1−(p+q) cannot be easily obtained from just pq, or equivalently that p+q is in some aspect independent from pq. Note that that's not actually necessary to break RSA; the key assumption is that without knowledge of p or q (except of course of their product), taking roots modulo pq is difficult. Unless C happens to be a perfect eth power in the integers, this is impractical, and is at least (I think) as hard as factorisation. (I'm not very sure on this part.)

So let's just focus on the former assumption. It's actually as hard as factorisation, despite only asking for the sum of the factors and not the individual factors themselves. The reason for this is quite simple (although it somehow eluded me for quite some time): through substitution, a simple quadratic equation can be formed, whose two roots are exactly the two primes p and q (the order isn't important here). (Note that this quadratic equation can be solved in polynomial time.)

In fact, let's focus on finding p+q given pq, but in small prime moduli m. (We can assume that these moduli are smaller than p and q, so they will be coprime. If they're not, then factorisation can be done in polynomial time anyway.) Modulo 2, there isn't much to cover, since pq is always 1 and p+q is always 0. Modulo 3, p+q has two solutions if pq is 1, one solution when pq is 2.

Let's skip ahead a bit. If you check for yourself, when pq is a quadratic residue, then there are (m+1)/2 solutions, and when pq isn't, there are (m−1)/2 solutions. Let's just go hypothetical for a while. If supposing there is exactly one solution, then by the Chinese remainder theorem this is easily solved, using O(log pq) moduli, in polynomial time and by extension also polynomial space.

Anyway, let's assume we proceed with this method, for moduli m_i, i being a natural number, we have the ith stage of sieving removing approximately half of the possible choices for p+q. Even in the worst case, at least 1/3 of the possible choices are sieved away, so this requires Θ(log pq) stages of sieving to solve. Unfortunately, this approach is doomed to failure. Each stage of sieving effectively takes Θ(pq) time, which is already exponential, and worse than the general number field sieve, which is subexponential. This method also requires pq memory to store the sieve results, which is in itself way too much and also very unrealistic for realistically large p and q (300+ digits each).

However, if we somehow had some kind of machine with at least pq memory, and could do one stage of sieving in O(m_i) time, then the approach becomes feasible, and in fact doable in polynomial time, but with exponential space. This is clearly impossible on classical systems (e.g. Turing machines).

Given that factorisation is in NP, and suspected not to be in P, we think factorisation won't be solved (in the sense that a polynomial-time algorithm is found), at least for a long time. Of course, factorisation isn't believed to be NP-complete; if it isn't, then it might be in P. On the other hand, if it is NP-complete, then we have some reason to believe that P=NP, meaning that it might still be in P anyway. In other words, we don't have any concrete results on this yet.

Density of Gaussian primes redux

2009-11-06T15:19:00.000+08:00

I just did a Google search on the density, and it turns out that, once again, I had the wrong insight on solving this problem. (See second link.) In fact the correct solution is quite simple. Consider a quarter-disk of radius x in the quarter plane z: arg(z) ∈ [0,π/2]. We can actually already start counting the primes via a simple number theoretic theorem about the sums of two squares: that every prime congruent to 1 modulo 4 can be represented as the sum of two squares in exactly one way (or 8 if you count swapping the terms and the signs). So we'll actually count the number exactly now.

The 3-mod-4 primes on the real/imaginary lines shouldn't be double-counted since they're on the boundaries, so for the appearance on both the real/imaginary lines I count both as just one. This gives π₃(x) primes there. (π₁ and π₃ refer to the prime-counting functions on primes in residue classes 1 and 3 respectively.) We'll also make 1+i a special case, since it corresponds to the natural prime 2, the only even prime. Those remaining are then the number of 1-mod-4 primes less than x², which corresponds to 2π₁(x²) Gaussian primes. Adding these three terms give 1+π₃(x)+2π₁(x²).

We shall now cast our wand of asymptotics. That gives ~x²/(2lnx). Similarly, for the quarter-disk of radius √2x, ~x²/ln x. Performing the same scaling trick that we did in the last post, this gives the same value: π(x,x) ~ (2/π)x²/ln x, and from that we see that our initial heuristic turns out to be correct.

It would be nice if we had some kind of error analysis, but we don't quite know how much bias there is for primes to be 1-mod-4 over 3-mod-4 or vice versa, so no analysis here, sorry.

Density of Gaussian primes (heuristics)

2009-11-06T01:58:00.004+08:00

Heuristic: let the density of primes in the sum-of-two-squares integers (i.e. those that have even powers of primes congruent to 3 modulo 4 in the prime factorisation) be asymptotically proportional to (i.e. big theta of) that of integers in general, i.e. inversely proportional to the log. This heuristic is actually quite crazy. It's not obvious, and I can't quite justify much; it might not even be true! (This is the case for heuristics in general actually.)

So given that assumption, it's time to find the multiplier. Modulo 2, the squares are evenly distributed among 0 and 1, and so are the sums of two squares, so no multiplier here. Modulo 3, the squares go in residue class 0 at 1/3, residue class 1 at 2/3, so the sums go in residue class 0 at 1/9, implying a 8/9 chance of being coprime to 3 instead of 2/3, so the current multiplier considering modulo 6 is 4/3. For modulo 5, the chances of being divisible 5 is 9/25, being coprime is 16/25, differing from the expected 20/25, introducing another multiplier 4/5. The closed form for this actually depends on quadratic residue stuff; this is left as an exercise for the reader (you).

And then multiplying all these multipliers gives 4/π. Let that be K. (So we can avoid having π refer to both the constant and the function.) Note that K is only assuming the initial heuristic; it is not a heuristic itself if the initial heuristic is valid. (Well, inasmuch as the fact that the density of the primes tends to zero.)

Thus, we can roughly approximate π(x,y), which we define as the number of Gaussian primes with non-negative real/imaginary parts, with real part less than x and imaginary part less than y. Since we're only concerned with asymptotics here it doesn't matter if we use "less than" or "not greater than", or "non-negative" versus "positive", since they contribute a insignificant proportion by themselves. In fact I'm only going to consider when x=y, or in other words a square in the complex plane. I'll also ignore edge cases where the real/imaginary part is equal to zero. We shall now perform a double integration on this density. Direct integration is not exactly easily usable, since there is no closed form for the integrand (integrating in either variable), so we consider two related areas: the quarter-disk contained inside the square, and the quarter-disk containing the squares, both of which can be integrated quite easily via change of variables. Using asymptotics (and after scaling so the areas match), they are both Kx²/(2 ln x), so we can conclude that, heuristically, π(x,x) ~ (K/2) x²/ln x. Again, assuming that heuristic, it's not hard to prove that π(x,y) ~ K xy/ln(x²+y²). (Note that so far only one heuristic has been used: the one set out at the start.)

From my calculations (done in C, not Mathematica, you insensitive clod!), π(1200,1200)=137253, corresponding with a value of K≈1.352, which isn't exactly close to 4/π≈1.273, until you realise that I swindled a few times in the asymptotics by ignoring large (but still relatively insignificant) error terms; it's probably the case that accurate computation of the value would require very large numbers, or even that the heuristic is false.

Update [10:55]: Fixed some stuff.

A generalised exponential function (part 2)

2009-11-05T15:45:00.003+08:00

Actually, come to think of it, the solutions can't actually be too hard. The obvious thing about such generalised exponentials is that they solve a particular (and quite simple) differential equation: f⁽ⁿ⁾ = f (where the bracketed superscript denotes an n-fold differentiation). There's also another class of solution generators^[1] to this differential equation, and for some reason I didn't quite think of them earlier. They're e^δ_n where δ_n is any nth root of unity.

It turns out that via a very simple trick these two classes of solutions can be related. Recall that the sum of nth roots of unity equals 0 when n>1, and also that taking the set of nontrivial roots of unity (i.e. all the roots except for 1), and taking each element to the power of an integer coprime to n gives you back the same set. With those in mind, we have a preliminary result: a closed form for exp_0,n.

Via differentiation of the Taylor series definition of exp_m,n, we find that (exp_m,n)′=exp_m−1,n, where m−1 really means m−1 modulo n. So we differentiate the above series, and we get, in turn, closed-forms for exp_n−1,n, exp_n−2,n, et cetera all the way to exp_1,n. The closed forms for these are similarly simple, except the exponentials are weighted by some root of unity first. This gives a general solution:

In case anybody forgot, in the first post about this I specifically asked for real transformations. Taking complex powers almost seems cheating, until you remember that complex numbers have both real parts and imaginary parts, and exponentiating to complex powers can be considered as converting them to sines and cosines. The end result involves a series (still going from 0 to n−1) with the sine/cosine of a sine multiplied by something else, which isn't very nice, but is interesting in its own right, in that when x is real the complicated imaginary part miraculously cancels out.

[1] I say generators, because any summation of any multiples of them will also solve the differential equation. This also provides a simple proof that these n generators are independent (although clearly also very closely related), in the sense that no sum of multiples of n−1 of them can generate the other one.

Math Overflow

2009-10-26T22:55:00.002+08:00

No, I haven't been lagging behind in the mathematics blogging community about the existence of this question-answering tool. (Okay maybe I was a bit slow because I came to know it from Terence Tao's blog, and he claims that he reported the info late.)

Regarding the generalised exponential functions I posted 2 days ago, I posted a question on MO. I've gotten a single answer, although it seems a bit unsatisfactory. (I asked for real transformations, precisely because I thought the complex ones would make the problem too easy to solve. Not that DFTs are simple to understand, but still.)

A generalised exponential function

2009-10-24T22:31:00.004+08:00

I was thinking about this for the past few days. Consider the Taylor series for e^x, then the ones for e^−x and e^ix. For the second we can rewrite it as cosh(x)−sinh(x), and the third as cos(x)+isin(x). Noting that the hyperbolic sine/cosine's Taylor series is actually all positive, being complementary terms to that of the exponential function, sine and cosine could similarly be split into two functions each. This presents a generalisation. (n denotes an arbitrary positive integer, m denotes an integer between 0 and n−1, inclusive. m and n may also be called the residue and modulus respectively.)

With that, sin = exp_1,4 − exp_3,4, cos = exp_0,4 − exp_2,4, sinh = exp_1,2, cosh = exp_0,2. The original motivation for this was to have a way of easily expressing e^δx where δ is an arbitrary integer root of unity. We just saw uses for them where δ⁴=1. Unfortunately, not having a closed form for these in general we can't quite use them for anything. Now letting δ here be a complex cube root of 1, we have some kind of a closed form for exp_m,3, except not really. Using the obvious result, we have

which is as far as we go. We don't have any results on exp_0,3, nor any individual results on exp_1,3 or exp_2,3, so this trivial one is kind of moot. A question: can exp_m,n be expressed in terms of real transformations (i.e. without invoking complex numbers) on generalised exponentials with smaller modulus for sufficiently large n?

Update: a quick search on arXiv gave one somewhat related paper, except it focuses on a different (and somewhat more trivial) generalisation of the exponential, trigonometric and hyperbolic functions.

Regarding the integer square root

2009-10-19T12:56:00.003+08:00

For notational convenience I'll follow the notation used in Wikipedia in the article "Integer square root". In fact, I shall offer a very trivial proof of one of the claims in the article (which is currently with a "[citation needed]").

The claim is that, given the approximations x_k and x_k+1 generated with the Babylonian method to √n whereby x_k−x_k+1<1, ⌊x_k+1⌋=⌊√n⌋. First, a preliminary result (which is easily demonstrated). With ε being the relative error of x to √k, we have that ε_n+1=ε_k²/(2(1+ε_k)), provided that ε_k is positive. (This is easily checked.) Completing the square, we get (ε_k−ε_k+1)²=ε_k+1²+2ε_k+1=(ε_k+1+1)²−1. Using the inequality x_k−x_k+1<1, we get (⁠ε_k+1+1)²<1+1/n. Taking square root, ε_k+1<√1+1/n.

The rest of the proof goes by contradiction. Suppose that ⌊x_k+1⌋>⌊√n⌋. Then ε_k+1≥n^−½(1−(n^½−⌊n^½⌋)). Now we'll need some bounds on ⌊n^½⌋; the obvious (n^½−1,n^½] does not suffice. Given that n is an integer, ⌊n^½⌋∈[(n+1)^½−1,n^½]. After some simplification, ε_k+1≥√1+1/n, which is a contradiction! The claim is then shown to be true. Given that this is the tightest possible bound on ε_k+1 without any other knowledge of n, this shows that 1 is the largest possible stopping criterion.

Transcendental multiples

2009-10-01T19:58:00.005+08:00

I shall now make the conjecture in one of my earlier posts weaker (applying only to transcendentals and not irrationals in general), and phrased more rigorously.

Definition of continued fraction convergents: the continued fraction chopped off at some point. For any positive number x, the continued fraction convergents are denoted as x_i for i in ℕ with x₁=⌊x⌋. (For the purposes of stating this conjecture the edge case of x being rational and thus having a finite continued fraction is impossible and so this case is ignored here.)

Conjecture: Given a transcendental number x and a positive rational number q, the sequences x_i and (qx)_i/q will agree on infinitely many terms. More strongly, the number N of terms in (qx)_i/q that also appear in x_i for i in the range 1 to n exceeds Kn for some positive number K for sufficiently large n. Stronger yet, that this value of K is 1 for almost all (transcendental) values of x.

Note that the conjecture could be weakened to just allowing q to be a positive integer; this formulation turns out to be equivalent by a simple argument. Also note that the first one says that N=O(n), the second that N=Θ(n), the third that N~n. Note that if x is allowed to be a quadratic irrational, then K might not be 1; the earlier post I mentioned has an example (involving φ and 2φ/3).

Calculating η (again)

2009-09-30T01:55:00.006+08:00

These few days I've been thinking about how to calculate values of the η function efficiently on my calculator so that only the last 4 or so significant figures are off. This is, as I've mentioned in an earlier post, easily attained when |s−1| is within a circle of radius 1.5 centred at the origin, by using the Laurent series of ζ and just 12 of the Stieltjes constants, for Re(s)>4 by taking one step of the Euler transform (note that the Euler transform itself is the limit when infinitely many steps are taken), and adding around 50 terms, which is actually quite fast. This leaves huge gaps though. The rest of the domain of the function is calculated by use of a full Euler transform, which is unfortunately very slow. I think it's the way I implemented it, but regardless, it's still quite slow. The worst part is that even though η doesn't converge too slowly on (2.5,4), it converges too fast for the Euler transform to converge fast.

What a headache. For now, if the Euler transform has to be used, and Re(s)>0, I'm adding 20 terms together before using the Euler transform on the rest of the terms; this doesn't help much, but it's still a nice improvement. But, we can do better! We'll need to notice a few things. First, the one-step transform on the η series causes η(s) to converge at roughly the same speed as η(s+1) (but slightly slower in that the hidden constant of the error term has a larger value), so by taking a 7-step transform we can make η(s) converge like η(s+7), which allows sufficiently fast convergence over Re(s) in [0,4]. Of course, the extra steps aren't free; as mentioned in brackets above, they will converge a few digits behind η(s+7), and it requires computation of 7 extra terms. Then again, if fifty terms can be done quite fast, seven should be no problem.

Moreover, by using a 7-step transform instead of a 1-step transform for Re(s)>0, the convergence should be significantly improved even outside the original intended range of [2.5,4]. I'll try these out when I recharge my AAA batteries.

PS: While checking the value of η(2) = π²/12 with Google, I found a pretty "interesting" site. It's actually quite lame and indicates that the author uses a calculation system with insufficient precision, and can't think for shit's sake. Also seems like he doesn't know about continued fractions, the integral test. And like a cheapskate, he includes "Grampa's Series" attributed to himself in addendum #12. Yeah, that Grampa's Series from the Y E O Adrian book (which has an average rating of 3 on Amazon, right in the middle of the scale). Hold on, I'm not supposed to be ranting about stuff in zznq. Oh well then.

Riemann hypothesis simplified

2009-09-27T13:34:00.006+08:00

Most of my target audience already know what the RH is. But, just for fun, I shall attempt to describe the Riemann hypothesis in a manner that is easily understandable. First, a definition of the complex numbers. I'm going to skip this part; most books on popular mathematics involving complex numbers would probably do a much better job of explaining them than I can. Also, the Wikipedia article is quite helpful, but is a bit heavy for the not-so-inclined. Now about complex exponentiation. The core of the Riemann hypothesis in the original formulation involves real numbers taken to complex numbers. Now, hold on, how can a complex power be taken? We'll now have to define exponentiation. Again, check Wikipedia. I'm not going to detract from the real content here.

Now on to the real stuff. We'll define the Dirichlet eta function η, but restricted to the input having positive real part. The most convenient way to do this is, of course, to use the series expansion. It's equation 2 in this scan. (The rest of the scanned page is irrelevant to current discussion.) So anyway. The infinite sum converges exactly when the real part of the argument is greater than zero. (When the real part is exactly zero (and the imaginary part is not), summing the terms is like performing a two-dimensional random walk. Definitely not convergent.) There are infinitely many values of s for which η(s)=0; there are the so-called trivial values that occur regularly on the line Re(z)=1, and the so-called nontrivial zeroes that are not on that line. Basically what the RH asserts is that all these nontrivial zeroes happen to be on another straight line, Re(z)=½. That's all there is to the Riemann hypothesis in a more classic explanation.

I do not deny that there are many other ways to state the Riemann hypothesis; some of them are significantly simpler (to understand, not necessarily solve), but they don't quite capture the essence of the original and how it relates to prime numbers. And I must also note that this isn't the original either. The original involves complex (in both senses) calculus, and is quite difficult to comprehend. The formulation I presented here is easily shown to be equivalent though. Of course, if the RH turns out to be false, it's all a sham, but at least we have another way of looking at things.

Quick description of the RSA encryption algorithm

2009-09-22T21:37:00.007+08:00

Mathematical algorithms typically operate on numbers, integers specifically, and in the case of encryption larger numbers mean larger possible security. Breaking up strings into numbers isn't particularly hard, and is pretty obvious once you have the right insight. RSA works on the difficulty on factoring large integers. Note that this is not necessarily the theoretical security of RSA; it has not been proven that breaking RSA is as hard as factoring integers, although for now that's the easiest method.

a^φ(n) ≡ 1 (mod n), for all a such that gcd(a,n) = 1

Euler's theorem will be important here. In particular, for the RSA algorithm, we'll take n to be a product of two large primes p and q. Note that proving that arbitrary large numbers are primes is quite difficult (even though this is in P time), so it's allowed for the numbers to be probable primes. The number n is public, while p and q are kept secret. With that in place, note that φ(n)=(p−1)(q−1). The encryption key is then a number e coprime to φ(n), or in other words, coprime to both (p−1) and (q−1).

So, how is encryption done? Basically, given a plaintext number P (note caps) in ℤ/nℤ, take C≡P^e (mod n). These sequences of numbers are then sent as a message. Notice that 0 and 1 are fixed points of the exponentiation function; by the fact that e was chosen to be coprime to φ(n), these are the only fixed points. The algorithm could be strengthened slightly by using values in the range 2 to n−1 instead of from 0 to n−1, which avoids these pathological cases where the decryption is trivial. Notice that the encryption key e is public; anybody who wants to send a message to you encrypts it using your encryption key.

Now that encryption is covered, how is decryption done? In other words, how do you take the e^th root of the number C? The answer lies in Euler's theorem, by finding a number d such that d·e ≡ 1 (mod φ(n)). There are simple algorithms to calculate d from e and φ(n) quite quickly, under the assumption that e is coprime to φ(n). Utilising this with Euler's theorem, and some basic arithmetic, C^d = P^d·e = P^k·φ(n)+1 for some value of k. Factoring the P out, C^d = P·P^k·φ(n) ≡ P·1^k = P (mod n). Note that while for P = 0, even though Euler's theorem doesn't apply, the result is still correct, since 0 is a fixed point of the power function, and P = C = 0.

What provides the security then? Couldn't an attacker just follow the same procedure to get the value of d? Yeah, attackers can't. Notice that the only known way to efficiently calculate d is through the two prime factors of n, p and q, which are not public. Hence, for now at least, to compute d requires factoring the large integer n, which is, again for now, difficult to do quickly. Technical stuff: factoring numbers is probably hard (not in polynomial time), but the results of the factorisation can be checked relatively quickly (in polynomial time), so factoring numbers is NP-hard. This effectively hinges on the P not being equivalent to NP, which is (the negated version of) one of the Clay Millennium problems.

Update: For some weird reason I neglected the fact that n has two non-trivial factors. Even taking that into account, according to Wikipedia (and some common sense), by using the Chinese remainder theorem, the above equation still holds. Of course, it's not likely that a factor of n is encountered, and if it were it could be used to factor n. The only number not coprime to n that might appear with any high probability is 0, which should not even be used. Also, Wikipedia has more info about RSA. That my working was so similar to the version in Wikipedia was completely coincidental; I wasn't referring to the article while I was typing this post, and I had not read that article before writing this post.

Continuous factorial

2009-09-07T16:48:00.005+08:00

I was thinking for a while. Notice that the factorial function is quite discrete in nature, although the analytic counterpart (the gamma function) isn't. The reason I say it's discrete is because, in effect, it multiplies integers going up. Think the triangle numbers, but multiplying instead of adding. If we smooth out the process and ignore some terms, we get the function mapping to half the square numbers instead of the triangle numbers. This is integration.

We could in fact apply the same idea to the factorial function. Basically, instead of writing factorial as a product, write it as an exponentiated sum: (using the incredibly convenient summation operator I introduced in Summing polynomials multiplied by an alternating factor)

So now, instead of using summation, use integration, and get (using ? instead of !)

after some simplification. Note that for the lower limit of integration use 0, since 0 is more convenient than 1 here.

Just a random idea; note that this function can be expressed in terms of (a finite number of) the elementary functions, unlike Γ (or Π if you don't like Legendre), which requires an integral. Also note the similarity with Stirling's approximation formula.

Proof of the PNT ((not) coming soon)

2009-09-06T13:15:00.001+08:00

Shaun Lee had provided a proof outline of the PNT (as you should know by now) around 2 weeks ago. There were some serious gaps in the proof, but I'll fix them. In fact, I am now. For now, I've completed the first parts of the proof; also, when I'm done, I'm scanning it, because doing it with TeX is just too inconvenient. The proof is mostly basic calculus and algebra. While the use of calculus does disqualify the proof for counting as elementary, it's still quite easy to follow. It's probably also the simplest possible proof of the PNT using little complex analysis. (The elementary proof by Selberg is quite difficult to follow; there were some times a little bit of basic calculus was used as well, such as to prove the existence of γ, although these statements are provable without calculus, albeit with some difficulty.)

Update: while thinking of how to make the last part work, it turned out that it assumes that the limit of π(x)ln(x)/x exists as x tends to infinity; basically what Chebyshev was stuck on 150 years back. Dang.

Computation of constants (redux)

2009-09-03T22:41:00.002+08:00

… where m=n(n+1)/2. (Ramanujan's expansion of the harmonic series.) It's pretty cool. And from here I shall describe a method by which more digits of γ may be obtained from less in a somewhat iterative manner. Starting from a crude (but reasonable) estimate like 0.57721566, the first correction term (12m)⁻¹ may be "deduced", as can the next term (120m²)⁻¹ by using 10 terms. This gives the error bound in terms of m⁻³, where we assume that the Ramanujan expansion works in integer powers of m of alternating sign. (It does.) The third term however, can seem like a pain in the behind, depending on whether you use m or 2m for calculations. The first time I tried this out I used 2m; this gives 4/315 as the coefficient, which is not conveniently recognisable. Of course, if using computational aids to do this, the precision should be as high as is sane; round-off errors creep in very fast.

There are other complications. The most obvious is that the above expansion (like many other useful ones for γ not involving the zeta function) is just an asymptotic expression; take up to that many terms and the error is at most the next (for sufficiently large values), but for a fixed value for n the terms eventually oscillate and become bigger instead of smaller. Also, the coefficients tend to be non-unit fractions in the long run, and in fact grow arbitrarily large, so continued fractions (or something of that sort) have to be used to solve for them. And also considering that the later terms could have a significant effect on the digits produced by earlier terms (due to large coefficients), arbitrarily large numbers of terms have to be used to get high accuracy.

Of course, as I hinted above (and in the title) this applies to all asymptotic expansions with alternating sign, although this should be the most useful use case. The only other important alternating asymptotic expansion I know is that for the gamma function (coincidence), where accurate results for integers can be obtained by taking the factorisation by using Legendre's factorial formula (which doesn't seem to have a name attached).

On polynomial interpolation

2009-08-30T11:50:00.003+08:00

(Note: functions mentioned by themselves are italicised, but are otherwise not italicised.)

Suppose you have a function f defined over a range, where values at some points are known. If supposing that the values f(x₀), f(x₁) and f(x₂) are known for x₀, x₁, x₂, then a quadratic function g may be used to interpolate that (this is done easily). Taking f−g, we now have a function that is known to have three zeros. Factoring that out gives a modified interpolating polynomial that is of degree three less than the original (unknown) interpolating polynomial, and this can be solved more readily. After the modified interpolating polynomial is found, we can add g to that, to give an interpolating polynomial for the original function f.

Of course, the Lagrange form of the interpolating polynomial can be used when the data points are those of x and f(x), but this is not always the case. Occasionally the data points can be x and f′(x), whereby using the Lagrange form is impossible. In this case huge systems of linear equations have to be solved; although reducing the degree by a constant number doesn't help much, it does make life that bit easier.

The key downside to this method is that it gives polynomials in a weird form (not that the Lagrange form isn't weird). An example would be a function defined as such: f(0)=f(2/3)=0, f(1/2)=1/2, f(1)=f(1/3)=1, f′(1/3)=f′(2/3)=0. Here I used g(x) = x (for the points 0, 1/2 and 1). From there I found that the system is overdetermined (since I was looking for a quintic, and this had 7 givens), and solved it to get the polynomial f(x)=x[1−9(x−1)⁠(2x−1)(9x²−9x+1)]. (Note: I didn't use a CAS for this, and did this all on paper, so it might be wrong.) I haven't bothered to expand it; it should be quite pointless to do so, since this is a demonstration of the generated polynomial.

I also note that this method could be applied to more than just 3 points; perhaps it could be iterated, a la divide and conquer? Maybe such a procedure will lead to something similar to the Lagrange form.

Zeta zero map

2009-08-27T00:17:00.001+08:00

(Er, not map as in transformation.)

X-Ray of Riemann zeta-function by J. Arias-de-Reyna.

One series for one

2009-08-25T20:24:00.001+08:00

It's quite trivial actually. I derived it from the Euler-transformed Leibniz series (factorial over odd double factorial), although there should be an easier way to derive it.

PS: It's not one month since the last post.

Coin flips: expected probabilities

2009-07-31T21:12:00.001+08:00

Say you have a coin that can only land heads or tails. Let the probability of landing heads be p, then tails 1−p. By the principle of indifference, every probability is equally likely; i.e. the probability distribution graph shows a value of 1 in the range (0,1). (Note: open interval.)

So, assuming a fixed number of flips n is played out, and h of them heads. Then the expected probability of the coin coming up heads is (h+1)/(n+2).
This is actually dependent on how the flips are played out. Supposing that the number of flips is variable and stops on the first head. I haven't figured out what the formula for this is, but it's probably not as simple. There are also other models, such as stopping at heads with a fixed probability. More complicated models are likely to follow h/n more closely.

Of course, the above is interesting. It completely throws out statistical sampling with small samples. For example, supposing that with 100 coin flips all come up heads. This implies that there is a 1 in 102 chance that tails will come out next, although textbook statistical analysis methods give a probability of zero.

More details: The expected probability is
,
where f(x) is the probability of the event (the specified chain of heads/tails) happening if p = x. In the above example, flipping the coin a fixed number of times, this gives

where the above proposition of E(p) = (h+1)/(n+2) can be verified. Note that the binomial coefficient cancels itself out in this particular case, thus not affecting the result. Specifically, we can treat f as being f:x→x^h(1−x)^n−h without loss of generality. I haven't yet bothered figuring out how the integrals work out in the other scenarios mentioned above.

Meta: template update

2009-07-30T23:43:00.000+08:00

So, because I'm expecting most of you readers to have a horizontal screen resolution of at least 950 pixels, I've tweaked the blog template slightly to expand the main content area by 200 pixels horizontally, which allows for far more convenient reading and enjoyment of mathematical insights! (Best read with an excited tone.)

PS: Don't expect much content to appear over the next few days.

The mathematical truth

2009-07-29T21:15:00.000+08:00

This post will be just about mathematics, with quite little actual mathematical content. It's not like I haven't done such a post before, just that I haven't done it on this (or my other) blog before. So here goes. (Warning wall of text.) Mathematics is a rather interesting subject. The key idea about mathematics is abstraction. Let's have an example. Numbers aren't by themselves physical objects, and hence they can't be touched, or anything like that. In this sense, they're abstract entities. Negative numbers were probably harder to comprehend than positive numbers, especially since the positive numbers can be quantified (typically using (delicious) fruits), but the negative numbers… Have you seen a negative fruit before? Most probably not, since they are rather difficult to make. (It's probably the case that the only sane way to interpret the previous sentence is to invoke the matter-antimatter antisymmetry, which isn't even exact but heck.)

Mathematics can occasionally be hard to comprehend initially, as with negative numbers. I've never had this problem though, since I've been exposed to complex numbers before I turned ten. After the integers we have the non-integers. These, well, aren't too difficult to comprehend, since we could measure non-integral lengths with a ruler (which is, by definition, cool), and most of us have rulers. Even if you don't, the concept of division is easily demonstrated with origami, and I'm sure you would have some paper. Or maybe pie, or pizza. And of course, there's a theorem that is just waiting to be mentioned: the pizza theorem. Given a pizza (modelled by a cylinder) of radius z and thickness a, what's the volume? pi zz a! The joke's not mine though. There's really a legitimate pizza theorem though, and it's different from this one. But I digress.

Then there's the concept of infinity. What would infinity plus one be? No, not that brotherhood. This actually depends on what kind of infinity you're referring to. "Oh, great. So you're telling me there are multiple types of infinity?" Well, yes. And they're different. There are infinite cardinals and infinite ordinals, and they behave differently. I don't quite bother myself with these most of the time though. There's another thing that some people (like ancient Greeks) can't comprehend, and that is that adding up infinitely many numbers can give a finite sum. Maybe you've pondered on this before, maybe not. Consider a line segment that's a meter long. Cut it in half, and halve one of those halves, and so on ad infinitum. What's the total length of the other line segments apart from the smallest ones? Half plus a quarter plus an eighth plus a sixteenth and so on part of a meter, and that turns out to be exactly one meter, since there is no smallest line segment.

Oh, but that might be trivial stuff. At least relative to what I'll be covering in the next few sentences. The concept of convergence is basically that a sequence of numbers eventually get as close to a specific limit as you want and always stays at least as close from then on. Wikipedia has more about this, and more precise too. So maybe for a while we can ignore convergence. Then we have divergence. Of course, there are infinite sums that well, don't end up at a specific value. There are effectively three ways divergent series can go. One is to head off to infinity, or negative infinity, another is to oscillate around zero with increasing amplitude, so it simultaneously goes off to positive and negative infinity, and the last is to have the value constantly changing without getting arbitrarily close to any specific value and staying as close from then. That was quite a mouthful. For example, 1 − 3 + 5 − 7 + …, which contains all the odd numbers, and alternating between positive and negative, is divergent. The second kind of divergence I specified above, specifically. But so what? We can still meaningfully assign a "sum" to that series, and that'd be zero. There have been rules formulated for manipulating divergent series, such as regularity, linearity and stability. Of course, sometimes even these rules are too strict, and they are ignored where it makes sense to.

Of course, there's worse than divergent series. They're infinite series that seem like they'd converge, but only if you add the terms up in a specific order. Add them up in a different order, and BAM! You get a different sum! A classic example is the alternating harmonic series, 1/1 − 1/2 + 1/3 − 1/4 + …, which adds up to ln 2 = 0.693147… (slowly, but it works; you'd need around a million terms to get close though). However, taking only the positive terms or only the negative terms give a rather bleak result: they're both divergent (of the first kind mentioned above, going to infinity). What this means is that you can make it any value you want. Say you want it to equal 1. Take as many terms as is necessary to bring the sum above 1 (1/1 + 1/3), then subtract as is necessary to bring the sum below 1 (1/1 + 1/3 − 1/2), then add (1/1 + 1/3 − 1/2 + 1/5), and subtract (1/1 + 1/3 − 1/2 + 1/5 − 1/4), rinse and repeat to give 1/1 + 1/3 − 1/2 + 1/5 − 1/4 + 1/7 + 1/9 − 1/6 + 1/11 + 1/13 − 1/8 + 1/15 + …. Because the individual terms themselves go to zero, this series eventually gets as close to 1 as you want, and stays at least as close as that from some point on. (Note that there is not much pattern in the signs above; this is because a certain number called e is irrational, i.e. cannot be expressed as a fraction.) So what, 0.693147… is equal to 1, and the whole of mathematics is shattered? Not quite. You see, this kind of series where you must add the terms in the correct order are called conditionally convergent series, and the other garden-variety kind of convergent series are called absolutely convergent series. You can check Wikipedia for more information.

So in the last three paragraphs we covered infinite sums. We could do with slightly less heavy stuff. That might be logic, and the basis of mathematical rigour. You see, mathematics is an exact science, and mathematical rigour is extremely important. Hundreds of years back there was this guy called Pierre de Fermat, who came up with this "theorem": there is no way two positive integers exponentiated to some integer power can equal another integer exponentiated to the same power, if that power is greater than two. Of course, he didn't fully justify it; he merely proved the case when the power is four. But there are more integers greater than two than that. There's 3, 5, 6, 7, 8, 9, et cetera; he didn't cover those. It took hundreds of years for this theorem to actually be proven, by this guy called Andrew Wiles (along with some other people whose names I've forgotten) in the 1990s. This guy set down the exact reasons why this theorem is always correct. Fermat probably only had a gut feel for it; historical evidence indicates that he probably didn't have a proof for his own theorem. In fact, Wile's proof involves many recent mathematical innovations (and is also very long), and these were most likely not available to Fermat.

Such "theorems" that were originally derived from intuition are called conjectures. They could be true, we most likely think so, but if someone shows that it's false, we can accept it. There were originally seven conjectures chosen by the Clay Mathematics Institute that had a 1000000 USD prize for each proof as to whether the conjectures were true, and of which one have been solved, although the eccentric who solved it declined the million-dollar prize. This leaves six conjectures, and some of them are highly critical to current mathematical knowledge. The two that I know a bit of are the Riemann hypothesis (which is actually a conjecture as mentioned) and the P=NP conjecture. The former would reveal insights into a certain class of positive integers called the primes (these numbers have exactly two factors: 1 and themselves), the latter would demonstrate that there is a way to write integers as a product of primes efficiently. Of course, these aren't the only results of these conjectures. As things stand, there are many (some say more than 500) mathematical proofs that rely on the truth of the Riemann hypothesis. Mathematicians normally avoid such conditional proofs, and this only shows the confidence mathematicians have in the truth of the Riemann hypothesis. If it happens that the Riemann hypothesis is shown to be false, all of these proofs are automatically invalidated. That's how mathematical proofs work. If any foundation is shattered, the whole building collapses. It could be the case that there is another way to get to the result, and that is the beauty of mathematics. You could fail, but you can always come back up.

There's a very nice analogy to how proofs work. Say you have two banks of the river, with the opposite bank being quite far away. There are stones on which you can walk (yeah I fail geography, but this is only for illustration) and basically every mathematical theorem is a stone. It's only by stepping on a stone that you can verify that there's really a stone there; if there's not, you get stuck on the previous stone. The idea of a mathematical proof is to verify whether there's a stone at a particular place, and it's only by stepping on earlier verified-to-exist stones can one show that there is a stone there. Conditional proofs assume that there is some stone somewhere that can be used, but if it turns out that that stone doesn't exist, you fall through the gap. Of course, there are subtleties. There are infinitely many theorems, and an arbitrary statement cannot be proven in finite time. And that, of course, was a proven mathematical statement. Interesting that maths can demonstrate what maths cannot do eh?

There's a lot more I could write about, but I'm tired now. Maybe there'll be a part 2, maybe not. This kind of writing is not what I'm used to anyway.

Continuation of the harmonic numbers

2009-07-28T07:34:00.001+08:00

I'm going to standardise on the notation here. H₁ = 1, H₂ = 3/2, and yeah you get it. Cue image!

Note that this converges for all non-negative real numbers, and probably also all complex numbers with Re(n)>0, although I've not verified that yet. This most definitely wouldn't be the first attempt at a continuation of the harmonic numbers, since Euler had done it already, hundreds of years ago. His idea was to convert it into an integral. Cue image again! Nah, just kidding. I'm lazy. Basically he integrated (1−tⁿ)/(1−t) with respect to t over the range (0,1). In this case the denominator would divide perfectly into the numerator if n is an integer, giving a geometric progression, which when integrated quite obviously gives the harmonic numbers. This representation is actually quite useless. How about this?

This converges for all complex numbers. It's better! But whatever. It's not as elegant.

Update: changed the first equation for elegance.

This is not, and neither is that

2009-07-22T00:44:00.002+08:00

You might be wondering why I take over two hours just to make the previous post. Well, maybe not, but I'll be assuming you are. First, I had already done a huge portion of the algebra aided with a CAS; however, I had made two mistakes. First was, as in the last post, that I substituted 2^k instead of 2^k+1 as the multiplicative factor. This one I found out and rectified after the post went online, so it didn't quite harm. The second one was one I thought I committed, but did not. I mistakenly thought I forgot to change a variable, when in fact I did, and wasted quite a bit of time on my CAS getting it right, only to figure out it was right all along. (Even taking into account the multiplicative factor error.)

Well, of course, that wasn't the only reason. Another was markup. As I mentioned in my regular blog, I mostly blog from the HTML editor, and not the WYSIWYG one. The advantage is fine-grained control, the disadvantage is that it's extremely tedious. The above example of "2^k+1" has 2<var>k</var>+1 as the markup. One particular expression used 136 characters, and roughly the same number of bytes. (If using Firefox, select the blog post and view selection source.) For the minus sign I did not use the hyphen-dash as a replacement. I used the Unicode minus sign: "−" U+2212. Of course, for "π" I similarly used U+03C0, for ellipsis U+2026, summation symbol U+2211 (contrast Σ and ∑, capital sigma and summation respectively), right-pointing arrow "→" U+2192, multiplication sign "×" U+00D7. This takes quite a bit of time, if you don't realise. I hadn't memorised (at that time) the codepoint for the minus sign, so every time I used it I either used − or from copying an earlier mention.

Yes, I know that's inefficient, but I'm overly pedantic at times. Why not use Symbol for the Greek characters? For one, I'm using the HTML editor; I won't know what letters map to what. For another I don't even have that stupid shitty Microsoft-ish font. For yet another, this isn't semantic markup. For another one that's more from a pragmatic standpoint, using this method saves no space. (Well of course, Greek characters were quite sparse anyway.)

Summing polynomials multiplied by an alternating factor

2009-07-18T19:50:00.012+08:00

Prescript: if you're a pedant, feel free to substitute "we" for "I" below (since I'm the only one here). (I do not have split personalities, unlike Ian.)

First, to get things straight. We'll define an operator ∑ which is applied to a function that is defined on the positive integers, with
.

We won't be covering Faulhaber's formula here; doing so would only serve to distract. (We will use it though.) Instead, we'll directly cover the summation. As in the title, we'll have a polynomial p, with non-zero degree, and a multiplier A:n→−cos(πn). In particular, we'll let p be a power of it's argument: p:n→n^k for some positive integer k. (The original assumption of having p an arbitrary polynomial can be recovered by adding up the powers.)

With that, we have that ∑p is another polynomial (of degree k+1, which can be obtained through Faulhaber's formula), and that [∑(A×p)](n) = [∑p](n)−2^k+1[∑p](⌊n/2⌋), when n is a positive integer. Clearly, neither of these forms will converge as n tends to infinity. However, we can still proceed from here. (Somewhat.) In particular, when k = 0 (which we explicitly disallowed earlier) we have Grandi's series (which cannot be summed by the method as described further below).

How now? Actually, we may note that infinity is simultaneously even and odd (roughly speaking), so ⌊n/2⌋ (with n being infinity) is simultaneously n/2 and (n−1)/2. (We're sticking with n being an integer.) We may then let these be applied by the polynomial ∑p, and equate and solve. As an example, let's have k = 4. Then the summation ∑p:n→n(n+1)(2n+1)(3n²+3n−1)/30 (as may be verified with Faulhaber's formula). Then after some algebra, this gives n ∈ {0,−1,−φ,φ−1}. (Note that φ is the golden ratio.) Letting the set be applied by ∑(A×p) (assuming the 2|n form; not that it matters since they're equal) gives 0 for all four of these. Therefore, the infinite sum, by some metric, should be 0. (Note that ∑(A×p) in this case is ∑(A×p):n→A(n)×n(n+1)(n²+n−1)/60 .)

If the above looks familiar, let's recall the Dirichlet eta function, expressed as a summation. (It's the second equation in the Wikipedia article "Dirichlet eta function".) If we substitute in a negative integer value for s, we get exactly what we described here! In fact, since η(−4) = 0, the above example turns out to be correct.

We suppose that the method as described above would contain among its solutions (if more than one) the actual value as defined by the Dirichlet eta function; however, we have not yet shown mathematically that this is the case. As an aside, let's have another example (a simple one this time), with k = 1. The partial sums are (starting with index 1) 1, −1, 2, −2, … , leading to a particularly simple expression for the partial sum ∑(A×p). In particular, the cases when the argument is even or odd are both linear, intersecting at one point and therefore leaving one solution, and that single solution is η(−1) = 1/4. More information about the particular case η(−1) may be found at the Wikipedia article "1 − 2 + 3 − 4 + · · ·".

Getting back to the issue of summing general polynomials multiplied by A, the above technique requires modification in order to work. In particular, since p is no longer necessarily a monomial, the expansion factor 2^k+1 (where k is the degree of p) needs to have smaller correction terms. However, a similar idea may be used. Noting that taking ∑(A×p) at positive even values provides a polynomial of degree equalling the degree of p, as does taking it at odd values, although these polynomials may differ, a similar process of equation and solution may be used to obtain an "infinite sum" of sorts.

PS: This post has the dubious glory of being the post I took longest to write (roughly 134 minutes), on all of my blogs. Runner-ups would be the rant about the web (roughly 60 minutes) and the rant about Safari (roughly 50 minutes).

Update: I fixed an error (mistakenly using 2^k instead of 2^k+1). This removes some weirdness I couldn't explain. I also added the last paragraph (before the postscript). This makes the total post time far longer. (And taking into account the time I spent way before I wrote this post thinking about a raw form of this method… it'd be very long indeed.)

SMO Open (round 2)

2009-07-04T17:55:00.005+08:00

So, as you may, or may not have gathered, earlier today was the SMO Open special round. I managed to do one question (only ☹), and have since solved another one. (It was already mostly solved then; just that I figured out the last step on my way home.) So here be the questions; first on the Internets! (Note that for question 2 I snipped the definition of a palindromic number.)

Let O be the center of the circle inscribed in a rhombus ABCD. Points E, F, G, H are chosen on sides AB, BC, CD and DA respectively so that EF and GH are tangent to the inscribed circle. Show that EH and FG are parallel.
Prove that the arithmetic progression 18, 37, … contains infinitely many palindromic numbers.
For k a positive integer, define A_n for n = 1, 2, … , by

Prove that A_n is an integer for all n ≥ 1, and A_n is odd if and only if n ≡ 1 or 2 (mod 4).
Find the largest constant C such that

for all positive real numbers x₁, … , x₄ such that
Find all integers x, y and z with 2 ≤ x ≤ y ≤ z such that
xy ≡ 1 (mod z)
xz ≡ 1 (mod y)
yz ≡ 1 (mod x)

The question I managed to do was 2, the one I mostly did was 5. For 2, I used two palindromic numbers 201000 000000 000102 and 320000 000000 000023 to generate a/an (countable) infinity of palindromic numbers congruent to −1 modulo 19. (The former is in residue class 0, latter in class 18.) For 5, I first showed (tried to show actually) that x = 2 (the missing crucial step), then from there, y = 3 and z = 5.

PS: the "[insert formula here later]" means that it'll take some time for the formulae to appear, because I'm thinking about how to use texvc locally. This postscript will be struckthrough when I'm getting around to it. (Also, hope that Blogger works with image uploading now.) Fixed, images added; even though Blogger image uploading is still broken.

Conditional convergence of the summation expansion of the reciprocal zeta function

2009-07-01T00:31:00.009+08:00

Well, the summation expansion of the reciprocal zeta function (as above) is a bit weird. For example, when s tends to 1, we have the LHS tending to 0 (which is trivially obtained from the Laurent series for ζ), but as for the RHS… it's a bit weird. When s=1, the RHS converges, but only conditionally. If you attempt to expand it (without substituting s=1), you get something like this:

(Note that I use P to denote the prime zeta function, summing over the primes instead of all natural numbers.) This is interesting, because if you ignore the non-primary terms, you get e^−P(s), which tends to 0 as s tends to 1. In other words, this somewhat of a good heuristic, at least when s is close to 1.

Note: in above equation ("1−P(s)+…") the P(s) comes from taking one prime number, the P(s)²/2 comes from taking two primes and ignoring the order, P(s)³/6 from taking three primes and ignoring order, et cetera. The other terms come from correction of terms with duplicate primes (eg 1/(2×2)) (and also the inclusion-exclusion principle).

Just a meta post

2009-06-28T00:35:00.003+08:00

I realise there was a 31 day break between the previous two posts; I'm sorry about that, but sometimes I just don't think of anything new.

Occasionally I receive external stimulus. For today, that'd be the SMO Senior section Special round. The most interesting question should probably be question 2, which asks for an ordered pair of positive integers (m,n) such that 3 × 2^m + 1 = n². With epic skill, I split the problem into two parts, m even and m odd, and solved with continued fractions … almost. I needed the continued fractions for √3 and √3/2 (in retrospect √6 would also have worked), which I evaluated to 7 terms each. The problem now is to find all the convergents that have a denominator that is a power of 2, and I only managed to prove that for √3, sadly. Of course, my working contained something like a_{p_2^x−2}, which was quite hard to read, especially considering I changed it quite a bit in-place, making it rather messy.

Courtesy of Ramanujan

2009-06-26T23:58:00.007+08:00

π here refers to the prime counting function, and μ refers to the Möbius function. The first equality was derived by Ramanujan (slightly changed by me for faster (and more predictable) convergence) and the second contains the error term, which is valid when n = ω(ln x). (And of course I derived the error term. I don't rip everything off.)

I really don't get how a step function can be differentiated. And for that matter, evaluating that to 150 terms gave π'(4) ≈ 0.4066596… with the upper bound of the error being a miserable 0.0033333…. My version converges faster, but clearly, it's not quite fast anyway. The Möbius function is quite difficult to handle.

Note: the original version had x^1/r instead of x^1/r−1, which had the benefit of elegance, but converges much slower.

Linear to quadratic

2009-05-25T21:46:00.008+08:00

Unlike in most previous posts, this equation has no conceivable uses. At least, none that I can think of. Here, as in three posts back, δ refers to the binary digit sum.

I wasn't actually intending to find a faster converging series; I was really hoping to find a closed form, but I couldn't find one. At least quadratic convergence is comforting.

Update: ~~the equation is wrong. It should be twice the summation on the right side. I'll try to bother to update the image.~~ Fixed!

Central binomial coefficients

2009-05-16T15:55:00.005+08:00

That less-than with tilde sign basically means "less than and tends asymptotically to". I'd almost have marked this as trivial, since this inequality is easily obtained with Stirling's approximation formula, but the approximation formula itself is not very easy to prove. It's relatively trivial to get less tight (and not asymptotically equal) bounds, such as a lower bound of 4ⁿ/(2n+1) (this is used in a proof of Bertrand's postulate), and an upper bound of 4ⁿ.

Of course, with a bit of rearrangement, we have an approximation for √nπ. Admittedly, it's not very good, or useful, but it is interesting. For example, with n=3, we have √3π≈64/20=3.2, which is not bad for such a small n. But here, with just one iteration of the Babylonian method, starting with 3, a much better approximation is obtained, because 3 and π are quite close to each other.

Log and 3-smooth numbers

2009-05-12T17:27:00.004+08:00

With the work on sorting algorithms recently, as mentioned on my main blog, I suddenly came up with a strange realisation. First, it's very easy to get the asymptotic formula for the number of 3-smooth numbers under n, this is about 0.657(log n)² (iirc). The way I got this was the obvious method of generating 3-smooth numbers by hand: start with powers of two, then 3·2^m, then 9·2^m, and so on. The result is a "triangle", width log₂n and height log₃n. Multiply and simplify.

The next realisation I got is that if you try to get the 3-smooth numbers in order from this method, you'll notice that you'll be alternating between two different diagonal lines most of the time. I believe these represent the continued fraction convergents (and possibly semiconvergents) of (log 3)/(log 2). And, time for obvious result that dawned on me during the Chinese exam: the ratio between consecutive 3-smooth numbers tends to 1. This was partially unexpected, because of the low density of 3-smooth numbers.

Footnote: A003586 3-smooth numbers.

Eta and binary digit sum

2009-05-07T17:21:00.004+08:00

(From Borwein and Borwein 1992 "Strange series and high precision fraud".)

where δ(n) is the binary digit sum of n.

Too Old For This

2009-05-07T15:48:00.003+08:00

And I'm fifteen.

(Image from xkcd, comic 447 "Too Old For This Shit". CC BY-NC 2.5.)

Irreversible simple 1D cellular automata

2009-04-29T18:29:00.004+08:00

(Note: simple 1D CA refers to the 1D CA where a new cell is generated from the corresponding old one and the old one's direct neighbours, and where each cell has exactly two states. This gives 2↑2↑3=256 different such CA.)

Which of the 256 are reversible, and which aren't? For one, the obvious 85 and 170 are reversible, and the obvious 0 and 255 aren't. Rule 45 is not reversible if you allow infinite patterns (which is actually required since 45 is an odd rule), since there are three infinite patterns leading to the all filled cells pattern (all blank and alternating). (This also covers 30 other odd rules, excluding the aforementioned 255.)

This leaves 221 rules, 126 even and 95 odd. Really encouraging. Yeah.

As a side note: maybe we should only consider the even rules; the odd ones misbehave, making analysis a bit difficult.

Permutation period

2009-04-29T18:24:00.003+08:00

From the depths of my mind: Consider a permutation of a fixed number of objects. Let the period of the permutation be defined as the number of times the permutation needs to be applied to the identity permutation to get back the identity. Then the period is a factor of the total number of permutations possible.

Yeah, that's trivial after some thought, but it does seem a bit deep at first glance.

2D random walk observation

2009-04-25T14:44:00.003+08:00

Some years back, when my trigonometry skills were still rather weak, I figured out that the root-mean-square distance of a two-dimensional random walk is the square root of the number of steps taken, if we assume that each step is of length 1. Turns out that my method of derivation is rather similar to the one on MathWorld. (I think I had the benefit of hindsight though.)

Of course, I haven't figured out what the mean distance is yet.

PS: the only step that actually requires trigo is the sin² x + cos² x = 1 identity.

Just another meta post

2009-04-22T21:12:00.002+08:00

I'm reaching a block, not getting any new discoveries. I did recently write a post about mathematics over at my sister's blog though, which you can check for yourself because I'm lazy to link, and I don't want to hyperinflate her page rank. Actually, that post covers an introduction to divergent series, so it's not that trivial.

Also, I think I'll be writing for the Singapore Mathematical Society essay competition thingy. Or maybe not. I'm not sure. Also, (astronomy) ⊂ (physics), more like applied maths than pure maths. So maybe not. I'm not sure.

Negative half power

2009-04-18T09:54:00.006+08:00

It needs no explanation. It's neat though. I can't believe I didn't simplify it to the rightmost form earlier.

Anyway, you may verify the results of the previous posts with this easily. Except the one with sublinear convergence. For that one, you also need to prove that it converges at all, which is not difficult, with the help of Stirling's approximation formula.

Well, anyway, too many digressions. The key idea here, as in the previous two posts, is to find a neat and useful formula for √2. I've already mentioned the possibility of using a=1/8, and it provides a linear convergence rate of slightly more than 0.9 digits per term. There're much better ones that can be obtained with the other Pell numbers, but they're not very efficient for calculation on binary machines. So I found that a=−7×2^-15 also gives a neat result, with (1+a)^-½=(128/181)√2, with a convergence rate of slightly more than 11 digits for 3 terms. These formulas allow for calculation without high-precision floats, and can be implemented with just bignums.

Update: fixed one grammar error lol.

Square root of two

2009-04-16T19:49:00.005+08:00

Er, it turns out that, if you try to use the binomial transform on a binomial series, you just get another one. I realised that. Anyway, I was checking with other values of (1+a)^-½, and it seems that a=1/8 is a good choice. Coincidentally, the numerator is 9, which is a square, so it factors out. I think I can prove that of all the odd powers of two, 8 is the only one one less than a square.

Anyway, this also provides a simple spigot algorithm, similar to those used for BBP-type formulas, but there have been better times. (Note that this does not qualify as a BBP-type formula because it does not have a polynomial numerator and denominator.)

PS: If you're really desperate to calculate √2, just use the obvious method: use the Babylonian method to calculate it. It works, and it works well, because it converges quadratically.

Reciprocal of Pythagoras' constant

2009-04-15T23:12:00.003+08:00

This one is just trivial, but anyways, here you go:

In case you can't figure it out… I just applied the binomial theorem to (1+1)^-½. As such, it has effectively sublinear convergence, as you may confirm with the ratio test. Not my fault. I was too occupied with other matters to transform it.

Another meta post

2009-04-11T21:51:00.003+08:00

Performing some vanity searches (whoops couldn't resist), it seems that this blog comes up 12th when searching for "zznq". Cool. Also, Google Webmaster Tools tell me that my site is the second site on the search result for "odd cubes" that actually involves the idea (2n+1)³. Neat.

Well, it turns out that lots of the searches have nothing to do with the mathematical content here. I'm pretty sure Google has some work to do on ~~Pigeon~~PageRank.

Anyway, the recent American Scientist has a column about displaying mathematical formulas in the web, mentioning MathML, TeX, and HTML. For this blog, I'm going to consistently use TeX and HTML only, and the former only when HTML is not adequate for the situation, since MathML is a pain to use, and especially so with that weird redraw-resize bug on Gecko, and complete lack of appearance in WebKit (like I care) and IE (ditto). (It would've worked in Opera, except I removed it before anybody tested it.)

Equidistribution about a circle

2009-04-09T20:36:00.005+08:00

Problem: There are 26 letters in the English alphabet. Find a way to arrange 26 sets of the alphabet around a circle such that all 676 pairs appear exactly once.

Generalisation: There is an alphabet A with n letters. Find a way to arrange n sets of A around a circle such that all n² strings of length 2 in A appear exactly once.

I only have solutions for n<4. For n=2 the answer is a trivial 0,0,1,1, for n=3 the answer could be a less trivial 0,1,2,0,0,2,2,1,1 or 0,0,1,1,0,2,2,1,2. (There are others, but they're effectively equivalent.)

I wrote a small program using a genetic algorithm in an attempt to solve it yesterday. It kept getting stuck in a local maximum. Damn. However, I think I'm on the way to a breakthrough. (watch this space)

Update: I realise that the proper term for my algorithm is "simulated annealing". Also, I've tweaked the mutation routine to be less aggressive, and it now hits a higher local maximum. Not 100% yet though.

Loop removal

2009-04-07T18:40:00.003+08:00

I've actually been thinking whether this information really belongs here, since it's a bit more like applied maths than pure maths, but heck. Anyway, an introduction to the no-loop problem, posed by Douglas. In it's most original form, you started out with an m×n rectangular grid, and the no-loop number is the minimum number of cells that need to be removed so that there are no loops that can be formed from orthogonal connections. In a less primitive form, it involves graphs, and the no-loop number is now the number of vertices that need to be removed so that there are no cycles. The no-loop problem then asks what the no-loop number is, for a certain graph or m×n rectangular grid. Douglas also mentioned a variant on the rectangular grid version earlier this year, removing dominoes (adjacent cells) instead of single cells, but I won't cover this here now. I've written quite a bit of stuff already before this blog was started, you can see them here, and here. (Note that the second link might die soon.)

The n×n squares have been pretty extensively checked for correctness, and so are the 6×n grids. I've reviewed the 6×6 proof more than thrice, 7×7 proof twice, and 8×8 proof twice, so they're almost definitely right. The current big question is what the asymptotic removal density is. (If you're so dense (no pun intended), the removal density refers to the no-loop number divided by the total number of cells.) I've conjectured that it's 1/3, having found 3 ways to fill the grid, loopless, at that density. However, it almost seems wrong, in that the currently known limit is for the 15×15, at 0.2977… removal density, significantly less than 1/3=0.3333…. If you can find a tile that tiles loopless at a density lower than 1/3, I salute you. It's not trivial, if it exists. Also, bonus reward if you can show that that isn't optimal, and extra bonus if you show whether the asymptotic removal density is irrational.

Another issue I'm currently tackling is also the exact removal density, at least for some values of m in m×n. I've only managed to do this for m∈{1, 2, 3, 4, 6}, and was trying to work it out for m=5. m=7 or 9 seems out of reach for now, and m=8 looks barely possible.

As for the graph generalisation, I haven't done much work on it, having focused solely on the rectangular grids. However, do note that I have proven that the four-dimensional hypercube graph needs 6 vertices removed, and that the five-dimensional hypercube graph needs somewhere between 12 and 14 (inclusive). The former proven by showing equivalence of upper and lower bounds, latter, well, duh. Anyone can do better with a 13 or 12 upper bound?

Unprovability

2009-04-05T18:12:00.004+08:00

Suppose we have some conjecture that there is no integer (or, set of integers, same really) satisfying some specified condition. There are many conjectures that (used to) fall under this condition, such as Fermat's Last Theorem. Now, suppose that someone demonstrates an attempt at a proof that this is unprovable. We can now demonstrate that that someone's proof is wrong.

We may have the assumption that the conditions ~~are computable~~ can be computed in finite time, so we can iterate, and check over each of the integers, since ℤ is enumerable. In other words, either a counterexample to the conjecture exists, in which case it will eventually be found, or it doesn't.

Now, suppose the conjecture is unprovable. We have that a counterexample exists, or doesn't. If it exists, by the above paragraph, we can find it. If we can find it, then the conjecture is false. However, since the conjecture is unprovable, it cannot also be false, since we would have just proven it false, thus rendering it not unprovable. Therefore, there is no counterexample. The lack of a counterexample directly implies the truth in the conjecture, thereby also showing that the conjecture is not unprovable. Hence, the original supposition is false, and the conjecture is provable.

Of course, this doesn't quite apply to things like the axiom of choice, since it's definitely true that the definition of "set" cannot be completely defined.

Well, then, is it possible to prove that it's impossible to prove whether a conjecture is provable or not? My brain can't handle this kind of nested statements very well, so I shall leave it as is.

Update: Note that, in the first paragraph, I originally meant finite set of integers, although it works either way. Just a clarification.

Sum of eta of even divided by even power of two

2009-04-04T19:16:00.004+08:00

And, so the analogous series was found. This one does not involve divergent series at all in the proof, but it does involve Leibniz's series. This one also converges at a linear 2 bits per term rate. Of course, you have to be insane to use this to calculate π.

Yet another meta post

2009-04-04T10:07:00.003+08:00

Because of WebKit bug 24919 (filed by, guess who?), the blog title will not become inverted when hovered on WebKit, and by extension in Chrome or Safari. Obstinate people. So, I'd suppose, borders on inlines are a stupid idea as well, but you implemented it anyway? Typical double standards.

Anyway, from yesterday's experience, it seems that scanning isn't as tough as it was before, since I managed to get these two scans in less than 10 minutes. Or maybe last time I didn't notice the glaringly obvious "Scan" button fast enough. So, if I've done some cool stuff on paper (during English class), I might scan them, because typing them would be a duplication of effort.

Scanned notes

2009-04-03T20:57:00.005+08:00

This is based on day-before-yesterday's elegant series about eta. Note that the error term, as mentioned in the first proper paragraph, is completely wrong. See the note in the margin. ~~Also, on page 2, I realise that (8) is not very clear. I'll update this post with a TeX version soon.~~ Actually, it's clearer than expected. (That's not a lame excuse.)

Sum of eta of odd divided by odd power of two

2009-04-02T12:29:00.005+08:00

It's elegant. I don't have a rigorous proof of this yet; the current one involves manipulating Grandi's series, which clearly does not converge. I found this formula entirely by chance, so don't ask me to find one for even etas, not because I won't, but because I can't.

Also, this formula converges at 2 bits per term. In case you were wondering.

Update: this actually provides an inefficient and inaccurate way to calculate odd etas, by substituting in the values for the previous odd etas, and 1 for the subsequent etas. It works, but is slow, inaccurate, and bootstrapping. Wait. It's not bootstrapping. Attempting to bootstrap will give values of 1 for the etas. Yup. Also, it might be possible to find an analogous series involving the even etas.

Calculating ζ, η, λ

2009-03-31T00:18:00.005+08:00

Er, no, that's not some half-baked attempt at l33t. You clearly haven't been reading this blog enough if you thought so. Links, to Wikipedia: ζ, η, λ (whoops no Wikipedia article on lambda).

Basically, the easiest way is to just add, term-by-term. Easy, fast to implement, but slow in computing, unless Re(s) is large, and you don't want a lot of accuracy. However, if you insist on doing so, note that calculating η then scaling to either the ζ or λ is the fastest. There is also the problem that you can only do this for Re(s)>0.

Well, there's another slightly less easy way. Use an Euler transform. No other constant splitting value will work better than the default ½, so leave it as that. Using the transform on either the ζ or λ is useless at best, so, as above, use η, and scale accordingly. This also has the advantage that, since the Euler transform is actually Cesàro summation in disguise (not quite actually), this method of computing η always converges. Another advantage is that the convergence is linear, at one bit a term. (Well, faster than term-by-term adding which is asymptotically 0 bits a term.) Yet another advantage is that the values at negative integers can be obtained exactly, since from some point on subsequent terms become zero. (Note: this is only the case if your arithmetic system supports arbitrary precision fractions.)

But there's a snag! When Re(s) is large, the first few terms in the normal expansion decrease quickly, so the Euler transform becomes far less effective at that range. The easiest fix is to first add enough terms so that the transform becomes effective, or failing so, defect to the first method mentioned above.

Then there's yet another method, this time applying to the ζ. The Laurent series can be used when s is close to 1, since it converges quickly, with the Stieltjes constants decreasing fast, and with a factorial reciprocal multiplier. However, this is of limited use when the desired accuracy is large, since the constants have to be known beforehand to a similar accuracy.

Well, what about λ? I haven't got a clue how that might be summed directly and efficiently. Leave a comment if you have one.

Double factorials to the arctangent

2009-03-30T16:54:00.005+08:00

It's the same as the one on Wikipedia, just that this one uses double factorials and is hence more elegant. If you substitute x=1/√3 you get the formula the second post before, and if you substitute x=1 you get the factorial-over-odd-double-factorial series.

You might have inferred that I have not fully digested Gosper's paper since the techniques used are so shallow. Let me tell you something. You're right. I'm still trying to understand it.

Oh, and also note that since arctan is odd, the expression above evaluated at x=0 is a removable singularity.

PS: In case you didn't get it, this is just the binomial transform.

Representing integers

2009-03-29T23:50:00.002+08:00

This information would be relevant here as well. And because I'm too lazy to copy and paste the entire text I typed hours ago, I provide a link. Also, for those who read this blog, but have absolutely no knowledge of the existence of the other, well, now you know. (Do such people even exist?)

Also, as an afterthought. Perhaps the iteration of iteration of iteration could be continued indefinitely, to give and super-iteration of sorts, then that iterated over itself to give the super-iteration of super-iterations, and then again, ad infinitum. A bit like the situation of ordinals, with ω, ε₀, as described in page 274 of The Book of Numbers (Conway and Guy 1996).

From factorials to π (again)

2009-03-27T20:44:00.003+08:00

A slight variation of the previous version, and also converges at twice the rate, at two bits per term. Similarly obtained from a series transformation, this time of the Taylor series of arctan(1/√3). Note that this uses √3, so it isn't so easy to use. (Note however that √3 can be obtained to high precision quickly with the Babylonian method.)

I'm going to assume that this has already been discovered; it is, after all, a simple transformation. I'll upload the formula for the general arctan(x) sometime soon.

Sum of alternating reciprocals of odd cubes

2009-03-24T16:41:00.006+08:00

The first infinite sum is π²/8, the second is π/4, and multiplying them pairing off the terms actually does give the correct answer π³/32. Partial credits to Shaun Lee for providing inspiration, from attempts to prove that the resultant sum is π³/32, which neither of us have proven yet. Note that Gosper's Acceleration of Series notes this in page 41. (Actually that's the 42nd page of the PDF file.)

Update: I happened to find an exercise asking the reader to derive the value of β(3) (and yes, it's the Dirichlet beta function). Look at this PDF file, page 902 (22nd page). Note that I have next to no understanding of how Fourier series work. (I didn't read the whole thing.) Also, that has similar exercises for deriving ζ(2), ζ(4), η(2), η(4), and some others. And, to top it off, no answers.

But this one is!

2009-03-23T00:18:00.003+08:00

Post titles, when not on the individual post pages, now link to the individual post pages (finally), and the ~~post~~ blog title becomes inverted when hovered. All with a little bit of magic.

The first change will be sent upstream to my test blog (which you can access from the correct profile page) and the second, well, it's pretty specific to this one, so that won't be sent upstream.

Er, yeah, that's about it.

Update: brain damage influence corrected.

Not quite a meta post

2009-03-20T14:06:00.003+08:00

Sometimes, it doesn't harm the littlest bit to do some research. Yet, it always harms me greatly that mathematicians earlier have already beaten me to it. This paper by Gosper provides quite useful and interesting information, apart from the fact that the font and quality is horrible, on the transformation of series to make them converge faster.

Also, MIT AI Lab is was cool.

Update: I just realised that the AI lab got merged to form the CSAIL years ago. Whoops.

Yet another series for the natural logarithm (again)

2009-03-18T16:08:00.008+08:00

This one is exactly the same as the previous one when n is a positive integer. Now here's the question. Does this equality still hold if n is allowed to be an arbitrary positive number?

Update: If you look carefully, notice that each term is positive (when n is irrational; if n is rational then there are 0s as well). Now let n=ℯ, and add 6 terms. It exceeds 1. So it doesn't hold for all non-negative real numbers.

Yet another series for the natural logarithm

2009-03-17T21:47:00.005+08:00

Discovered by Shaun Lee some weeks ago, unearthed from my memory moments ago. ~~It's not trivial to prove.~~

Update: doh! Ninja'd.

Irrational multiples

2009-03-16T11:24:00.007+08:00

Consider a irrational number x>0 and a rational number q>0. Is it true that the continued fraction convergents of x and qx agree from some point on?

For example, consider π and 2π. (The x and q here equal π and 2, respectively.) The third convergent for π is 333/106, and the fifth convergent for 2π is 333/53. These are considered to agree, since (333/53)/2 = 333/106. Similarly, the fourth convergent for π is 355/113, and the sixth for 2π is 710/113. The next pair of convergents agree as well, but the eighth convergent of 2π agrees not with the sixth, but the eighth of π.

I'm guessing that the answer is no, but I'm not sure.

Update: seems that x=φ and q=2/3 is a counterexample. The convergents of 2φ/3 ([1;12,1,2,2,2,1]) skips some terms of that of φ, but is otherwise the same.

Update update: Actually, they aren't "otherwise the same". Stopping just at the first of three twos lead to a fraction that has neither numerator nor denominator as Fibonacci numbers. I should have noticed this earlier.

Observation about 1d random walks

2009-03-13T00:37:00.003+08:00

Let d_n be the mean distance from the origin of a one-dimensional random walk with n steps. Then it seems that d_2n−1=d_2n. Does not comprehend. (Note, as an example, that d₁=d₂=1.)

Note that I ever posted a question involving 1d random walks in LChat, where it asked for the denominator of d₁₀₀ after simplification. The answer is 2⁹⁵, by the way.

But they do!

2009-03-10T19:10:00.003+08:00

I've stopped using FireMath to display formulas. I gave up on MathML altogether. The formulas are now generated with TeX, or just plain text.

I've changed the blog template. I've not yet decided to use the unfixable Layouts, so it'll remain like this for quite long. I'll be applying workarounds here (unlike my test blog), which will not break even if Gecko becomes compatible. There are few changes between the two templates, things like the favicon is most easily noted. That one uses a transparent PNG, this an expression that evaluates to negative one. There was too little space; I'd have added a "=−1" if favicons could be larger. In fact, the current e^iπ one is barely understandable.

From factorials to π

2009-03-10T15:58:00.005+08:00

I got that from the Leibniz formula for π, through some non-rigorous manipulation of the terms. It does give a correct result though, as does a similar manipulation of the alternating harmonic series. In these two cases the transformed series converge faster. Note that the transform when applied to the alternating harmonic series yields the linearly-converging BBP-type formula for ln 2.

Got any other ways to derive this series? Or have I (and Shaun) been beaten to by another mathematician?

Update: I just realised that Euler beat us to it: [1] [2] Also see Shaun's comment.

Update: Ouch. Screw this.

The imaginary continued fraction again

2009-03-04T08:43:00.006+08:00

Basically, that can be rewritten into a recurrence relation. u₀=2, u_n+1=2-5/(2+u_n).

So, does it eventually reach 2 again?

It's provable that if it ever enters into a cycle it must include 2, since the recurrence is bijective excluding, of course, the values 2 and -2. The fraction seems to exhibit irregular behaviour. From my calculations, it seems that near the 60th term the value hits over 100. This actually seems to "correct" the values into remaining in that range.

Hmm.

So they don't

2009-02-28T17:57:00.003+08:00

Hmm. I shouldn't post meta topics so often, but yeah. When I'm done with the green-on-black style this blog will use it.

Also, check out the MathML equation in the previous post! I'm currently using 2 workarounds for errors I don't know how to fix. First, is the font colour/background. I can't fix the MathML version itself to use white as the font colour, since if I do so then the independent display ("Show Only This Frame") is screwed, since most people use white as the background colour.

Second, is the size. As you can tell (from viewing the source), the object element uses CSS width and height to control it, because if they're not included the dimensions of the object will use default values, which are not suitable. Unfortunately, my hard-coded values assume that either of the Vera or DejaVu fonts are being used, which isn't always true. Additionally, forcing a redraw can make the dimensions change.

A big problem is that using FireMath to generate formulas and equations isn't the most friendly thing to do. (But it certainly is easier than using a text editor.)

Imaginary continued fraction

2009-02-27T19:32:00.012+08:00

(Originally introduced by the mathematishaun.)

Basically, if you try to work out that continued fraction, you'll notice that it cycles between three values, placing undefineds in between cycles. It never hits ±i.

Expanding on Shaun's ideas a bit, I generalised it to x²−n² from his x²−1. Then the final continued fraction becomes n−[(n²+1)/(2n−)][(n²+1)/(2n−)]… (I apologise for not being able to use the proper notation here, but this should be good enough.)

Substitute in n=2. See that it doesn't cycle between a small set of values anymore! I'm going to take a guess and claim that this continued fraction doesn't repeat its values. Does it mean that it now converges? Of course not! If you see the values, you can notice something. It starts out at 2, then goes lower until it hits below some threshold (which I haven't bothered to figure out), then changes sign and becomes positive again, then decreasing, and …

I reckon the same happens with all other integer values of n>1.

Speaking of which, there's a simple proof that if you solve a continued fraction with only real numbers and end up with a non-real number, it means that the continued fraction doesn't converge. The proof is self-explanatory.

Factorial of a square divided by the factorial of the square's square root to the power of the square's square root

2009-02-26T22:00:00.006+08:00

Clearly, words are confusing. Single-line programming language-style expressions are also confusing ((n^2)!/(n!^(n+1))), but comprehensible if you have some kind of programming experience. Something better would be n²! / n!ⁿ⁺¹, but it still isn't fully aesthetically pleasing. Heck, good enough.

Basically, try to prove that that expression is an integer for all non-negative integer n. There's a trivial way, but that's not what we're looking for.

The trivial way is (avert your eyes for non-spoiler) to consider the number of ways you can put n-squared items into n unordered lists of n unordered items each. (Unordered means that the order doesn't matter.)

The cheating way is to realise that it's on OEIS, A057599, so it must consist of only integers.

Well, if you found that too easy, try the generalisation (m×n)! / [m!ⁿ n!], m and n are non-negative integers. The trivial solution is the same, in fact. But the in-depth, interesting solution… It could be the same as the special case m=n, it could be different.

Note: it's trivial to prove that n²! / nⁿ⁺¹ is integer for integer n, and is coprime to n iff n is prime, 0 or 1. I'm not sure whether this could aid the proof, but it's some food for thought. In fact, if n has at least two non-trival factors, then n²! / n²ⁿ⁺³ is also integer. (But this is merely trivia, and of no real importance.)

Buffalo do not buffalo buffalo

2009-02-26T21:52:00.003+08:00

So, by request of Shaun Lee, I have made this a mathematics outlet, for free flow of mathematical thoughts. However, occasionally, there will be posts about the blog itself (like this one), and these will have a 'meta' label. (Amusingly enough, my two other "main" blogs don't use labels at all.) Additionally, these posts will have some kind of a weird and completely irrelevant post title. (No, it's not steganographic.)

Well, the lack of some kind of mathematical expression display in Blogger is frustrating (look at earlier post, the half power is barely visible). No TeX (which I haven't learnt how to use yet), and no MathML (ditto). Seems like a vicious cycle. From what I heard Wordpress has support for TeX, but I'm not sure I want to switch, and I'm not even sure that's true.

π approximations

2009-02-24T18:14:00.003+08:00

π can be approximated using many methods. This post doesn't cover quickly converging methods, just good approximations of interest.

A nice one is (2143/22)^1/4 = π − 1.007×10^-9, first reported by Ramanujan (perhaps; I could be wrong). It can be checked from the continued fraction of π⁴, [97; 2, 2, 3, 1, 16539, … ]. (It stops at the 1, by the way.) The fourth root also helps to "mask out" errors slightly.

Another one is x+x^½ = π + 4.813×10^-5, where x=9/5. This one can also be verified from the continued fraction for the solution of x+x^½ = π in x, [1; 1, 3, 1, 1139, … ].

In fact, this idea applies to the convergent 355/113 of π itself, with the next term in the continued fraction being 292 (next fraction being 103993/33102). The spike isn't so drastic here, but it happens sufficiently late to be rather striking.

Another similar case is the Babylonian 3.8(29)(44)₆₀, a truncation which serves as a good approximation since the next (sexagesimal) digit is 0. This trick wouldn't quite work in decimal until relatively late: position 44, with a doubled '9' (… 1693993751 …). (But when you come to the Feynman point the situation changes slightly.)

I haven't personally found any nice approximations yet; these were taken from the Wikipedia article Numerical approximations of π.

π

2009-02-23T22:22:00.003+08:00

Procedure:

Start with the number 2.
Find the first occurrence of the number's decimal representation in the decimal digits of π. For multi-digit sequences take the position number of the first digit of the multi-digit sequence. (The first one appears at position 1, ie, counting from one.)
Now repeat procedure with the position number.

With 2 we have this chain: 2 → 6 → 7 → 13 → 110 → 174 → 155 → 314 → …

Nice coincidence eh?

This is, that is not

2009-02-19T20:51:00.001+08:00

Well, depending on your font the letter 'q' may or may not look like an inverted 'b'. Well, it is the case for the DejaVu fonts (as well as the base Vera fonts), so the 'zznq' should look like 'buzz' rotated by pi.

Currently on the madness that be around me. The insanity is crippling me. Not that it matters.

Oh, and I was relatively surprised that zznq.blogspot.com wasn't already taken. That was pretty cool actually.

Time to commence hacking.

Now say, what kind of content should be here? Leave a comment, post your thoughts.