Area of the unit disk after a Möbius transformation

Posted on by John

Let f(z) = (az + b)/(cz + d) where Δ = ad − bc ≠ 1.

If f has no singularity inside the unit disk, i.e. if |d/c| > 1, then the image of the unit disk under f is another disk. What is the area of that disk?

The calculation is complicated, but the result turns out to be

Area = π |Δ|² / (|d|² − |c|²)².

Just as a sanity check, set c = 0 and d = 1. Then we multiply the disk by a and shift by b. The shift doesn’t change the area, and multiplying by a multiples the area by |a|², which is consistent with our result.

As another sanity check, note that the area is infinite if c = d, which is correct since there would be a singularity at z = −1.

Finally, here’s a third sanity check in the form of Python code.

from numpy import linspace, pi, exp

a, b, c, d = 9, 15j, 20, 25j
theory_r = abs(a*d - b*c)/(abs(d)**2 - abs(c)**2)
print("theory r:", theory_r)

t = linspace(0, 2*pi, 10000)
z = exp(1j*t)
w = (a*z + b)/(c*z + d)
approx_r = (max(w.real) - min(w.real))/2
print("approx r:", approx_r)

More triangle inequalities

Posted on by John

Yesterday I wrote about a triangle inequality discovered by Paul Erdős.

Let P be a point inside a triangle ABC. Let x, y, z be the distances from P to the vertices and let p, q, r, be the distances to the sides. Then Erdős’ inequality says

x + y + z ≥ 2(p + q + r).

Using the same notation, here are four more triangle inequalities discovered by Oppenheim [1].

  • px + qy + rz ≥ 2(qr + rp + pq)
  • yz + zx + xy ≥ 4(qr + rp + pq),
  • xyz ≥ 8pqr
  • 1/p+ 1/q + 1/r ≥ 2(1/x + 1/y + 1/z)

[1] A. Oppenheim. The Erdös Inequality and Other Inequalities for a Triangle. The American Mathematical Monthly. Vol. 68, No. 3 (Mar., 1961), pp. 226–230

Area of unit disk under a univalent function

Posted on by John

Let D be the unit disk in the complex plane and let f be a univalent function on D, meaning it is analytic and one-to-one on D.

There is a simple way to compute the area of f(D) from the coefficients in its power series.

If

f(z) = \sum_{n=0}^\infty c_n z^n

then

\text{area}\left(f(D)\right) = \int_D |f^\prime(z)|^2 \, dx \,dy = \pi \sum_{n=1}^\infty n |c_n|^2

The first equality follows from the change of variables theorem for functions of two variables and applying the Cauchy-Riemann equations to simplify the Jacobian. The second equality is a straight-forward calculation that you can work out in polar coordinates.

Application

Let’s apply this to what I called the minimalist Mandelbrot set the other day.

The orange disk has radius 1/4 and so its area is simply π/16.

Finding the area of the blue cardioid takes more work, but the theorem above makes it easy. The cardioid is the image of the set {α : |α| < ½} under the map f(z) = z − z². To apply the theorem above we need the domain to be the unit disk, not the unit disk times ½, so we define

f(z) = \frac{1}{2} z - \frac{1}{4} z^2

as a function on the unit disk. Now c1 = ½ and c2 = −¼ and so the area of f(D) = 3π/8.

I said in the earlier post that the minimalist Mandelbrot set makes up most of the Mandelbrot set. Now we can quantify that. The area of the minimalist Mandelbrot set is 7π/16 = 1.3744. The area of the Mandelbrot set is 1.5065, so the minimalist set shown above makes up over 91% of the total area.

Related posts

Random samples from a polygon

Posted on by John

Ted Dunning left a comment on my post on random sampling from a triangle saying you could extend this to sampling from a polygon by dividing the polygon into triangles, and selecting a triangle each time with probability proportional to the triangle’s area.

To illustrate this, let’s start with a irregular pentagon.

To pick a point inside, I used the centroid, the average of the vertices. Connecting the centroid to each of the vertices splits the pentagon into triangles. (Here I implicitly used the fact that this pentagon is convex. The centroid of a non-convex polygon could be outside the polygon.)

We can find the area of the triangles using Heron’s rule.

Here’s what we get for random samples.

A triangle inequality by Erdős

Posted on by John

Plane geometry has been studied since ancient times, and yet new results keep being discovered millennia later, including elegant results. It’s easy to come up with a new result by proving a complicated theorem that Euclid would not have cared about. It’s more impressive to come up with a new theorem that Euclid would have understood and found interesting.

Paul Erdős conjectured another triangle inequality in 1935 which was proved by Mordell and Barrow in 1937 [1].

Let P be a point inside a triangle ABC. Let x, y, z be the distances from P to the vertices and let p, q, r, be the distances to the sides. Then

x + y + z ≥ 2(p + q + r)

with equality only if P is the center of an equilateral triangle [2]. In the figure above, the theorem says the dashed blue lines together are more than twice as long as the solid red lines.

How far apart are the left and right sides of the inequality? This was the motivation for the previous post on selecting random points from a triangle. I wanted to generate random points and compare the two sides of the Erdős-Mordell-Barrow inequality.

We can visualize the inequality by generating random points inside the triangle and plotting the points with a color that indicates the inequality gap, darker blue corresponding to a larger gap.

This shows the inequality is sharper in the middle of the triangle than near the vertices.

[1] Problem 3740, American Mathematical Monthly, 44 (1937) 252-254.

[2] You could interpret this as a theorem comparing barycentric and trilinear coordinates.

Randomly selecting points inside a triangle

Posted on by John

If you have a triangle with vertices A, B, and C, how would you generate random points inside the triangle ABC?

Barycentric coordinates

One idea would be to use barycentric coordinates.

  1. Generate random numbers α, β, and γ from the interval [0, 1].
  2. Normalize the points to have sum 1 by dividing each by their sum.
  3. Return αA + βB + γC.

This generates points inside the triangle, but not uniformly.

Accept-reject

Another idea is to use an accept-reject method. Draw a rectangle around the triangle, generate points in the square, and throw them away if they land outside the triangle.

An advantage to this method is that it obviously works because it doesn’t rely on anything subtle. Three cheers for brute force!

The method is fairly efficient; on average only half the points will be rejected.

A disadvantage to all accept-reject methods is that they have variable runtime, though this only matters in some applications.

Accept-flip

There is a clever variation on the accept-reject method. Create a parallelogram by attaching a flipped copy of the triangle. Now randomly sample from the parallelogram. Every sample point will either land inside the original triangle or in its flipped twin. If it landed in the original triangle, keep it. If it landed in the twin, flip it back over and use that point.

This is like an accept-reject method, except there’s no waste. Every point is kept, possibly after flipping.

You can find code for implementing this method on Stack Overflow.

Barycentric coordinates fixed

Felix left a note in the comments that the barycentric approach would work if you draw the random weights from an exponential distribution rather than a uniform distribution. That goes against my intuition. I thought about using a different distribution on the weights, but I didn’t work out what it would need to be, but I did not expect it to be exponential. Apparently it works. Here’s a proof by plot:

Related posts

A mental random number generator

Posted on by John

Man thinking of random numbers

George Marsaglia was a big name in random number generation. I’ve referred to his work multiple times here, most recently in this article from March on randomly generating points on a sphere. He is best remembered for his DIEHARD battery of tests for RNG quality. See, for example, this post.

I recently learned about a mental RNG that Marsaglia developed. It’s not great, but it’s pretty good for something that’s easy to mentally compute. The output is probably better than if you simply tried to make up random numbers; people are notoriously bad at doing that. Hillel Wayne explores Marsaglia’s method in detail here.

Here’s a summary the generator in Python.

state = 42 # Set the seed to any two digit number

def random_digit():
    tens = lambda n: n // 10
    ones = lambda n: n % 10
    global state
    state = tens(state) + 6*ones(state)
    return ones(state)

Related posts

New symbols in Unicode 17

Posted on by John

Unicode 17.0 was released yesterday. According to the announcement

This version adds 4,803 new characters, including four new scripts, eight new emoji characters, as well as many other characters and symbols, bringing the total of encoded characters to 159,801.

My primary interest in Unicode is for symbols. Here are some of the new symbols I found interesting.

Currency

There’s a new symbol for the Saudi Riyal (SAR): U+20C1. This may be the most important symbol added in version 17. The rest are relatively arcane.

The riyal symbol looks like the Chinese symbol 北 (U+5317) which means “north.” However, according to the Saudi Central Bank the SAR symbol is based on a calligraphic form of the Arabic word riyal (ريال).

Note that the SAR symbol has parallel horizontal-ish lines, as many currency symbols do.

New math symbol

There was only one math-like symbol introduced in Unicode 17, and that is U+2B96, EQUALS SIGN WITH INFINITY ABOVE. I’ve never seen this symbol used anywhere, nor could I find any standard uses in a search.

\stackrel{\infty}{=}

I made the image above with \stackrel{\infty}{=} in LaTeX. If you flip the image upside down you get a symbol that was already in Unicode, U+2BF9, which is used in chess notation. I don’t know whether the new symbol is also used in chess notation.

I suppose the new symbol could be used to denote that two things are asymptotically equal. This would be more suggestive than the currently standard notation of using a tilde.

Asteroid symbols

Several asteroids already had Unicode symbols: Ceres, Pallas, Juno, Vesta, and Chiron correspond to U+26B3 through U+26B7. Also, Proserpina, Astraea, Hygiea, Pholus, and Nessus have Unicode symbols U+2BD8 through U+2BDC.

In Unicode 17.0, a new list of asteroids have symbols: Hebe, Iris, Flora, Metis, Parthenope, Victoria, Egeria, Irene, Eunomia, Psyche, Thetis, Melpomene, Fortuna, Proserpina, Bellona, Amphitrite, Leukothea. These correspond to U+1CEC0 through U+1CED0.

Four of these asteroids have alternate symbols add in the new version of Unicode: Vesta, Astraea, Hygiea, Parthenope have alternate forms in U+1F777 through U+1F77A. These alternate forms are listed under alchemical symbols.

Incidentally, not only a Pallas and Vesta the names of asteroids, they’re also the names of elliptic curves I wrote about recently.

 

Mandelbrot and Fat Tails

Posted on by John

The Mandelbrot set is the set of complex numbers c such that iterations of

f(z) = z² + c

remain bounded. But how do you know an iteration will remain bounded? You know when it becomes unbounded—if |z| > 2 then the point isn’t coming back—but how do you know whether an iteration will never become unbounded? You don’t.

So in practice, software to draw Mandelbrot sets will iterate some maximum number of times, say 5000 times, and count a point as part of the set if it hasn’t diverged yet. And for the purposes of creating pretty graphics, that’s good enough. If you want to compute the area of the Mandelbrot set, that’s not good enough.

A reasonable thing to do is to look at the distribution of escape times. Then maybe you can say that if an iteration hasn’t escaped after N steps, there’s a probability less than ε that it will escape in the future, and make ε small enough to satisfy the accuracy of your calculation.

The distribution of escape times drops off really quickly at first, as demonstrated here. Unfortunately, after this initial rapid drop off, it settles into a slow decline typical of a fat-tailed distribution. This is not atypical: a fat-tailed distribution might initially drop off faster than a thin-tailed distribution, such as the comparison between a Cauchy and a normal distribution.

The plot above groups escape times into buckets of 1,000. It starts after the initial rapid decline and shows the fat-tailed region. This was based on 100,000,000 randomly generated values of c.

To estimate the probability of an iteration escaping after having remained bounded for N steps, you need to know the probability mass in the entire tail. So, dear reader, what is the sum of the areas in the bars not shown above and not calculated? It’s not like a normal-ish distribution when you can say with reasonable confidence that the mass after a certain point is negligible.

This matters because the maximum number of iterations is in the inner loop of any program to plot the Mandelbrot set or estimate its area. If 5,000 isn’t enough, then use 50,000 as the maximum, making the program run 10x longer. But what if 50,000 isn’t enough? OK, make it 100,000, doubling the runtime again, but is that enough?

Maybe there has been work on fitting a distribution to escape times, which would allow you to estimate the amount of probability mass in the tail. But I’m just naively hacking away at this for fun, not aware of literature in the area. I’ve looked for relevant papers, but haven’t found anything.

Bech32 encoding

Posted on by John

Bech32 is an algorithm for encoding binary data, specifically Bitcoin addresses, in a human-friendly way using a 32-character alphabet. The Bech32 alphabet includes lowercase letters and digits, removing the digit 1, and the letters b, i, and o.

The Bech32 alphabet design is similar to that for other coding schemes in that it seeks to remove letters that are visually similar. However, the order of the alphabet is unusual:

    qpzry9x8gf2tvdw0s3jn54khce6mua7l

I’ll explain the motivation for the ordering shortly. Here’s the same alphabet in conventional order, not the order used by Bech32:

    023456789acdefghjklmnpqrstuvwxyz

The Bech32 algorithm does more than represent 5-bit words as alphanumeric characters. The full algorithm is documented here. The algorithm is applied to the output of a RIPEMD-160 hash, and so the number of bits is a multiple of 5.

The Bech32 algorithm includes a BCH (Bose–Chaudhuri–Hocquenghem) checksum, and takes its name from this checksum.

Note that the BCH checksum is not a cryptographic hash; it’s an error correction code. It’s purpose is to catch mistakes, not to thwart malice. Contrast this with Base58check that uses part of a SHA256 hash. Base58check can detect errors, but it cannot correct errors.

I’ve had a surprisingly hard time finding the specifics of the BCH(n, d) code that Bech32 uses. Every source I’ve found either does not give values of n and d or gives different values. In any case, the order of the Bech32 alphabet was chosen so that mistakes humans are more like to make are more likely mistakes that BCH can detect and correct.

Related posts