Month: June 2022

Phi Phi

Posted on by John

I was reading something this afternoon and ran across φ(φ(m)) and thought that was unusual. I often run across φ(m), the number of positive integers less than m and relative prime to m, but don’t often see Euler’s phi function iterated.

Application of φ∘φ

This section will give an example of a theorem where φ(φ(m)) comes up.

First of all, Euler’s theorem says that given an integer m > 1 and an integer g relatively prime to m, then

gφ(m) = 1 (mod m).

Now Euler’s theorem gives a value of t such that gt = 1 (mod m). It doesn’t say this is the smallest t, only that it’s a possible value of t. If φ(m) is the smallest such value of t, then g is called a primitive root mod m.

For example, let m = 10. Then φ(10) = 4, and so a primitive root mod 10 is a number g such that g4 = 1 mod 10, but gt is not congruent to 1 mod 10 for t = 1, 2, or 3. Now 3 is a primitive root mod 10 because 34 ends in 1, but 3, 3², and 3³ do not end in 1.

There are no primitive roots mod 12. A primitive root mod m has to be relatively prime to m [1], and so there are only four candidates: 1, 5, 7, and 11. Each of these is congruent to 1 mod 12 when squared, so for none of them is 4 = φ(12) the smallest exponent that gives a number congruent to 1.

Now we’re ready to state our theorem, Theorem 2.34 from The Joy of Factoring by Samuel Wagstaff, Jr.

An integer m > 1 has a primitive root if and only if m = 2, m = 4, m = pe , or m = 2pe, where p is an odd prime and e is a positive integer. If m has a primitive root, then it has exactly φ(φ(m)) of them in 1 ≤ g ≤ m.

This theorem could have told us that 10 has primitive roots and 12 doesn’t, and it could tell us that 10 has exactly φ(φ(m)) = 2 primitive roots. We found one of them, 3, and the other is 7.

Higher iterates

Let φ1(n) = φ(n) and φ2(n) = φ(φ(n)). In general, let φk be the function defined by iterating the phi function k times. If we apply φ to any integer enough times, we’ll get 1. For each n, let k(n) be the smallest value of k such that φk(n) = 1. Then Erdős et al proved that k(n) is between log(n)/log(3) and log(n)/log(2).

To illustrate this, let n = 20220630. The theorem above predicts we’ll have to apply φ between 16 and 25 times before we get to 1. The following code shows k(n) = 21.

    from sympy import totient

    n = 20220630
    k = 0

    while n > 1:
        n = totient(n)
        k += 1
 
    print(k)

Note that “totient” is another name for Euler’s φ function.

Related posts

[1] If g shares a factor bigger than 1 with m, then so does every positive power of g, and so no power of g is congruent to 1 mod m. In particular, gφ(m) cannot be 1.

Speculation on new SI prefixes

Posted on by John

The SI prefixes giga and tera were adopted in 1960. The prefixes exa and peta were adopted in 1975, and zetta and yotta were adopted in 1991. Following this 15-year cadence, we should have adopted a few more prefixes by now. If we ever do introduce new prefixes, what might they be?

The latest prefixes follow this pattern: the prefix for 103n is some form of the name for n in some language. The prefixes peta for 1015 and exa for 1018 come from the Greek names for five and six, and the prefixes zetta for 1021 and yotta 1024 are based on the Latin names for seven and eight. If we stick with this pattern, and stick with Latin, the prefix for 1027 should be novem or some variant, and the prefix for 1030 should be decem or some variant [1].

Maybe some day we’ll speak of novemabytes of data, or a calculation requiring novemaflops of computing. There’s not much need to speak of novemameters since the observable universe is about a yottameter across.

The mass of the sun is about 2 × 1033 grams. We could call that a couple undecimagrams. The mass of the Milky Way is about 3 × 1045 grams, or three quindedimagrams.

Related posts

[1] There’s no need for more prefixes; this post is just for fun.

NASA and conformal maps

Posted on by John

A couple years ago I wrote about how NASA was interested in regions bounded by curves of the form

\left| \frac{x}{A} \right|^\alpha + \left| \frac{y}{B} \right|^\beta = 1

For example, here’s a plot for A = 2, B = 1, α = 2.5 and β = 6.

That post mentioned a technical report from NASA that explains why these shapes are important in application, say for beams and bulkheads, and gives an algorithm for finding conformal maps of the unit disk to these shapes. These shapes are also used in graphic design, such as squircle buttons on iPhones.

Note that these shapes are not rounded rectangles in the sense of a rectangles modified only at the corners. No segment of the sides is perfectly flat. The curvature smoothly decreases as you move away from the corners rather than abruptly jumping to 0 as it does in a rectangle rounded only at the corners. Maybe you could call these shapes continuously rounded rectangles.

Conformal maps

Conformal maps are important because they can map simple regions to more complicated regions in way that locally preserves angles. NASA might want to solve a partial differential equation on a shape such as the one above, say to calculate the stress in a cross section of a beam, and use conformal mapping to transfer the equation to a disk where the calculations are easier.

Coefficients

The NASA report includes a Fortran program that computes the coefficients for a power series representation of the conformal map. All the even coefficients are zero by reasons of symmetry.

Coefficients are reported to four decimal places. The closer the image is to a circle, i.e. the closer α and β are to 2 and the closer A is to B, the fewer non-zero coefficients the transformation has. You could think of the number of non-zero coefficients as a measure how hard the transformation has to work to transform the disk into the desired region.

There are interesting patterns in the coefficients that I would not have noticed if I had not had to type the coefficients into a script for the example below. Maybe some day I’ll look more into that.

Conformal map example

The following example uses A = 2, B = 1, and α = β = 5.

We start with the following disk with polar coordinate lines drawn.

And here is the image of the disk under the conformal map giving by the coefficients in the NASA report.

Note that the inner most circles from the domain are mapped into near circles, but as you move outward the circles are distorted more, approaching the shape of the boundary of the range.This is because in the limit, analytic functions map disks to disks. So a tiny circle around the origin will always map to an approximate circle, regardless the target region.

Note also that although the circles and lines of the domain are warped in the range, they warp in such a way that they still intersect at right angles. This is the essence of a conformal map.

Inverse map

The NASA report only gives a way to compute the transformation from the disk to the target region. Typically you need to be able to move both ways, disk to target and target to disk. However, since the transformation is given by a power series, computing the inverse transformation is a problem that has been solved in general. This post gives an explanation and an example.

Related posts

Transformations of Olympic rings

Posted on by John

The previous post gave the details of how Möbius transformations

m(z) = (az + b)/(cz + d)

transform circles. The image of a circle under a Möbius transformation is either a line or a circle, and in our examples the image will always be a circle.

We start with an approximation of the Olympic rings

 

 

and then apply various transformations.

First we apply (z + 9)/(z + 10):

 

This transformation doesn’t distort the rings too much because the rings are far from the singularity at z = −10. The blue ring is distorted the most because it’s closest to the singularity.

Next we apply (iz + 7)/(z + 8).  Now we’ve moved the singularity a little bit closer, and we caused some rotation by using i as the coefficient of z in the numerator.

 

 

Finally, let’s pick a transformation with its singularity inside the green circle, (z + 4)/(z − 3 + i).

 

 

Now we see a lot of distortion. The blue and gold rings that were outside the green ring are brought inside. The complex plane is turned inside-out because of the singularity.

As before, the black and red rings still intersect the green ring. But what you can’t tell from the graph is that the portion of these rings that was inside has been turned outside and vice versa.

Related posts

Circles and lines under a Möbius transformation

Posted on by John

This post will revisit a previous post in more detail. I’ve written before about how Möbius transformations map circles and lines to circles and lines. In this post I’d like to explore how you’d calculate which circle or line a given circle or line goes to. Given an equation of a line or circle, what is the equation of its image?

Circles to circles

A while back I wrote a post called Circles to Circles, demonstrating how Möbius transformations map circles and lines to circles and lines. If you think of a line as a degenerate circle, a circle of infinite radius, then you could simply say Möbius transformations map circles to circles.

For example I showed in that post that the transformation

m(z) = (z + 2)/(3z + 4)

maps these circles

to these circles

and that these lines

go to these circles

Circle or line image

Given the equation of a circle or a line, how would you know whether its image is a circle or a line?

A Möbius transformation

m(z) = (az + b) / (cz + d)

has a singularity at z = –d/c. If a line or curve goes through the point –d/c then its image is a line. Otherwise the image is a circle.

If the line or curve does go through –d/c, so that the image is a line, it’s easy to find an equation of the line. Pick two points, z1 and z2 on the original curve or line. Let w1 – m(z1) and w2 – m(z2). Then find the equation of a line through w1 and w2. For example, a parametric form is

w1 + t(w2 – w1)

for all real t.

Reciprocal of a circle

Posted on by John

Let C be a circle in the complex plane with center c and radius r. Assume C does not pass through the origin.

Let f(z) = 1/z. Then f(C) is also a circle. We will derive the center and radius of f(C) in this post.

***

Our circle C is the set of points z satisfying

|z - c|^2 = (z - c)\overline{(z - c)} = (z - c)(\overline{z} - \overline{c}) = r^2

Define w = 1/z and substitute 1/w for z above.

A little algebra shows

(r^2 - |c|^2) w\overline{w} + cw + \overline{c}\overline{w} = 1

and a little more shows

\left(w + \frac{\overline{c}}{r^2 - |c|^2} \right)\left(\overline{w} + \frac{c}{r^2 - |c|^2} \right) = \frac{r^2}{(r^2 - |c|^2)^2}

This is the equation of a circle with center

\frac{\overline{c}}{|c|^2 - r^2}

and radius

\frac{r}{\left|\,|c|^2 - r^2\,\right|}

As a way to check the derivation above, here’s some Python code for making circles and taking their reciprocal.

    import numpy as np
    import matplotlib.pyplot as plt

    theta = np.linspace(0, 2*np.pi, 1000)

    # plot image of circle of radius r centered at c
    def plot(c, r):
        cc = np.conj(c)
        d = r**2 - c*cc
        print("Expected center: ", -cc/d)
        print("Expected radius: ", r/abs(d))
        u = np.exp(1j * theta) # unit circle
        w = 1/(r*u + c)
        print("Actual radius:", (max(w.real) - min(w.real))/2)
        plt.plot(w.real, w.imag)
        plt.gca().set_aspect("equal") 
        plt.show()

    plot(1 + 2j, 3)
    plot(0.5, 0.2)
    plot(1j, 0.5)

Computing zeta at even numbers

Posted on by John

Last year I wrote several posts about computing ζ(3) where ζ is the Riemann zeta function. For example, this post.

It happens that ζ can be evaluated in closed form at positive even arguments, but there’s still a lot of mystery about zeta at positive odd arguments.

There’s a way to derive ζ(2n) using contour integration. But you don’t need to be clever about constructing contours if you start from the following result which is derived using contour integration.

Suppose f is analytic except for poles at zk and that the sum

\sum_{n \ne z_k} f(n)

converges, where the sum is over all integer n except poles of f. Then the sum can be computed from residues at the poles:

\sum_{n \ne z_k} f(n) = -\sum_{k} \text{Res}\left( f(z) \pi \cot \pi z; z_k \right)

Here Res stands for “residue.” The residue of a function g(z) at z0 is defined as the coefficient c−1 of (z – z0)−1 in the Laurent series for g. Equivalently,

c_{-1} = \lim_{z\to z_0} (z - z_0) g(z)

This means we can evaluate infinite sums by taking a limit that may be a simple application of L’Hôpital’s rule.

The theorem above could be used to calculate a lot more than values of the Riemann zeta function by choosing various functions f, but for our purposes f(z) will be z−2m for some positive integer m.

\zeta(2m) = \sum_{n=1}^\infty \frac{1}{n^{2m}} = \frac{1}{2} \sum_{\stackrel{n=-\infty}{n\ne 0} }^\infty \frac{1}{n^{2m}} = -\frac{1}{2}\,\text{Res}\left( \frac{\pi \cot \pi z}{z^{2m}}; 0 \right )

Why can’t this same trick be used for evaluating the Riemann zeta function at odd integer arguments? The second equality above fails. For even powers of n, the sum over the positive integers is half the sum over all integers. For odd powers, the sum over all integers is zero.

If we write out the Laurent series for π cot πz then we can read off the residues of π cot πz/z2m.

\pi \cot \pi z = \frac{1}{z}-\frac{\pi ^2 z}{3}-\frac{\pi ^4 z^3}{45}-\frac{2 \pi ^6 z^5}{945} - \cdots

When we divide by z² the coefficient of z becomes the coefficient of z−1, i.e. the residue. This residue is -π²/3, and so negative one half of this is π²/6, i.e. ζ(2) = π²/6.

The same line of reasoning shows that ζ(4) = π4/90 and ζ(6) = π6/945.

Finding the values of ζ(2m) in general is no harder than finding the power series for cotangent, which is not trivial but not insurmountable either. See this post.

The final result is that

\zeta(2m) = (-1)^{m-1} 2^{2m-1} \pi^{2m} \frac{B_{2m}}{(2m)!}

Constructive Picard

Posted on by John

The previous post concerned the function

h(z) = exp(-1/(1 – z² )).

We said that the function is badly behaved near -1 and 1. How badly?

The function has essential singularities at -1 and 1. This means that not only does h blow up near these points, it blows up spectacularly.

Picard’s theorem says that if a meromorphic function f has an essential singularity at z0, then near z0 the function takes on every value in the complex plane infinitely often. That’s almost true: Picard’s theorem says f can miss one point.

Suppose we take a little disk around 1 and a complex number w. Then Picard’s theorem says that there are infinitely many solutions to the equation

h(z) = w

inside the disk, except possibly for one value of w. Since the exponential function is never 0, we know that 0 is the one value h cannot take on. So for any non-zero w, we can find an infinite number of solutions to the equation above.

OK, so let’s actually do it. Let’s pick a w and look for solutions. Today’s June 24, so let’s pick w = 6 + 24i. We want to find solutions to

exp(-1/(1 – z²)) = 6 + 24i.

Taking the log of both sides, we need to find values of z such that

-1/(1 – z²) = log(6 + 24i)

This step should make you anxious. You can’t just take logarithms of complex numbers willy nilly. Which value of the logarithm do you mean? If we pick the wrong logarithm values, will we still get solutions to our equation?

Let’s back up and say what we mean by a logarithm of a complex number. For a non-zero complex number z, a logarithm of z is a number w such that exp(w) = z. Now if z is real, there is one real solution w, hence we can say the logarithm in the context of real analysis. But since

exp(w + 2πin) = exp(w)

for any integer n, we can add a multiple of 2πi to any complex logarithm value to get another.

Now let’s go back and pick a particular logarithm of 6 + 24i. We’ll use the “principal branch” of the logarithm, the single-valued function that extends the real logarithm with a branch cut along the negative real axis. This branch is often denoted Log with a capital L. We have

Log(6 + 24i) = 3.20837 + 1.32582i.

When we take the logarithm of both sides of the equation

exp(-1/(1 – z²)) = 6 + 24i.

we get an infinite sequence of values on both sides:

2πin – 1/(1 – z²) = 2πim + Log(6 + 24i)

for integers n and m. For each fixed value of n and m the equation above is a quadratic equation in z and so we can solve it for z.

Just to make an arbitrary choice, set n = 20 and m = 22. We can then ask Mathematica to take solve for z.

    NSolve[40 Pi I - 1/(1 - z^2) == 44 Pi I Log[6 + 24 I], z]

This gives two solutions:

z = -0.99932 + 0.00118143i

and

z = 0.99932 – 0.00118143i.

In hindsight, of course one root is the negative of the other, because h is an even function.

Now we don’t need n and m in

2πin – 1/(1 – z²) = 2πim + Log(6 + 24i)

because we can consolidate the move 2πim to the left side and call n – m the new n. Or to put it another way, we might as well let m = 0.

So our solutions all have the form

2πin – Log(6 + 24i) = 1/(1 – z²)

z² = 1 + 1/(Log(6 + 24i) – 2πin).

The larger n gets, the closer z gets to 1. So this shows constructive what Picard said would happen: we have a sequence of solutions converging to 1, so no matter how small a neighborhood we take around 1, we have infinitely many solutions in that neighborhood, i.e. h(z) = 6 + 24i infinitely often.

No analytic bump

Posted on by John

The word “smooth” in mathematics usually means infinitely differentiable. Occasionally the word is used to mean a function has as many derivatives as necessary, but without being specific about how many derivatives that is.

A function is analytic if it has a convergent power series representation at every point of its domain. An analytic function is infinitely differentiable, but surprisingly the converse is not true.

Suppose we took a bump function as described in the previous post, say over the interval [−1, 1]. Such a function would be infinitely differentiable at 1, positive to the left of 1 and zero to the right. Let’s compute the power series centered at 1. All the derivatives are zero at 1, so all the power series coefficients are 0, so the power series sums to 0. The bump function is positive on the left side of 1 but the power series is not.

When does the power series of an infinitely differentiable function converge to that function? More on this subtle question here.

Now suppose we forge ahead and try to construct an analytic bump function. What goes wrong? Do we get something that is almost analytic?

Let’s follow the construction of the previous post, starting with

f(x) = exp(x).

Then

g(x) = 1 /f(1/x) = exp(−1/x)

and

h(x) = g(1 + x) g(1 − x) = exp(1/(1 − x²))

In Mathematica,

    h[x_] := If[Abs[x] < 1, Exp[-1/(1 - x^2)], 0]

Now let’s look at h from several perspectives. Along the real axis, everything is fine.

    Plot[h[x], {x, -1.1, 1.1}]

The function seems to drop to zero abruptly so that it might not be smooth, but zooming in a little reassures us that the function is indeed smooth.

    Plot[h[x], {x, -1.1, -0.9}, PlotRange -> All]

What if we plot h as a complex function?

Now things don’t look so smooth. The swirls of color near -1 and 1 show that the phase is changing violently. Also, the light color in the unit circle compared to the dark color outside suggests the phase jumps when we cross the unit circle rather than smoothly transitioning to zero.

Let’s see what happens to the magnitude of h as we cut across the square above diagonally.

    Plot[Abs[h[z I + z]], {z, -1, 1}]

Definitely not smooth. Not even continuous.

Let’s see what happens if we add a dimension to our plot, using |h(z)| as height.

    ComplexPlot3D[h[z], {z, -1.1 - 1.1 I, 1.1 + 1.1 I}]

So a lot is happening at ±1. Let’s turn this plot around to look at it from a different perspective.

Our function has essential singularities at ±1 when we look at it in the complex plane. Along the real axis everything looks fine, but when we look at it from the complex plane we see that the function is very badly behaved.

Before we go, let’s go back and look at the example from the previous post, a bump function that is six derivatives along the real axis. What would it look like extended to the complex plane?

    h2[z_] := If[Abs[z] < 1, (1 + z)^7 (1 - z)^7, 0]
    ComplexPlot3D[h2[z], {z, -1.1 - 1.1 I, 1.1 + 1.1 I}]

This gives us

Here’s the same plot viewed from a different angle.

Bump functions

Posted on by John

A bump function is a smooth (i.e. infinitely differentiable) function that is positive on some open interval (a, b) and zero outside that interval. I mentioned bump functions a few weeks ago and discussed how they could be used to prevent clicks in radio transmissions.

Today I ran into a twitter thread that gave a more general construction of bump functions that I’d seen before. The thread concludes with this:

You can create bump functions by this recipe:

    1. Take any f(x) growing faster than polynomial (e.g. exp)
    2. Define g(x) = 1 / f(1/x)
    3. Let h(x) = g(1+x) g(1−x).
    4. Zero out x∉(−1,1)
    5. Scale, shift, etc

In this post I’ll give a quick asymptotic proof that the construction above works.

Let a positive integer n be given and define g(x) to be zero for negative x. We’ll show that if f grows faster than xn. then g is n times differentiable at 0.

As x → ∞, f(x) is eventually bounded below by a function growing faster than xn. And so as x → 0, f(1/x) grows faster than xn and 1/f(1/x) goes to zero faster than xn, and so its nth derivative is zero.

It follows that g(1 + x) is n times differentiable at −1 and g(1 − x) is n times differentiable at 1. So h is n times differentiable at −1 and 1. The function h is positive on the open interval (−1, 1)  and zero outside. Our choice of n was arbitrary, so h is infinitely differentiable, and so h is a bump function. We could shift and scale h to make it a bump function on any other finite interval.

Discussion

When I was a student, I would have called this kind of proof hand waving. I’d want to see every inequality made explicit: there exists some M > 0 such that for x > M …. Now I find arguments like the one above easier to follow and more convincing. I imagine if a lecturer gives a proof with all the inequalities spelled out, he or she is probably thinking about something like the proof above and expanding the asymptotic argument on the fly.

Note that a slightly more general theorem falls out of the proof. Our goal was to show if f grows faster than every polynomial, then g and h are infinitely differentiable. But along the way we proved, for example, that if f eventually grows like x7 then g and h are six-times differentiable.

In fact, let’s look at the case f(x) = x7.

    f[x_] := x^7
    g[x_] := If[x > 0, 1/ f[1/x], 0]
    h[x_] := g[x + 1] g[1 - x]
    Plot[h[x], {x, -1.5, 1.5}]

This produces the following plot.

Just looking at the plot, h looks smooth; it’s plausible that it has six derivatives. It appears h is zero outside [−1, 1] and h is positive over at least part of [−1, 1]. If you look at the Mathematica code you can convince yourself that h really is positive on the entire interval open interval (−1, 1), though it is very small as it approaches either end.

Related posts