Groups of order 2023

Posted on by John

How many groups are there with 2023 elements?

There’s obviously at least one: Z2023, the integers mod 2023.

Now 2023 = 7 × 289 = 7 × 17 × 17 and so we could also look at

Z7 + Z17 + Z17

where + denotes direct sum. An element of this group has the form (a, b, c) and the sum

(a, b, c) + (a′, b′, c′)

is defined by

((a + a)′ mod 7, (b + b′) mod 17, (c + c)′ mod 17).

Is this a different group than Z2023? Are there any other groups of order 2023?

Let’s first restrict our attention to Abelian groups. The classification theorem for finite Abelian groups tells us that there are two Abelian groups of order 2023:

Z7 + Z289

and

Z7 + Z17 + Z17

But what about Z2023? There’s a theorem [1] that says

Zmn ≅ Zm + Zn

if and only if m and n are relatively prime. Since 7 and 289 are relatively prime, t

Z2023 ≅ Z7 + Z289.

The theorem also says that Z17 + Z17 is not isomorphic to Z289 and it follows that their direct sums with Z7 are not isomorphic.

So we’ve demonstrated two non-isomorphic Abelian groups of order 2023, and a classification theorem says these are the only Abelian groups. There are no non-Abelian groups of order 2023, though that’s harder to show, and so we’ve found all the Abelian groups with 2023 elements.

More group theory posts

[1] Sketch of proof. Let d be the greatest common divisor of m and n. If d > 1 then every element of Zm + Zn has order mn/d < mn and so Zm + Zn if cannot be isomorphic to Zmn. On the other hand, if d = 1, then Zm + Zn has an element of order mn and so is cyclic.

Sinc approximation to Bessel function

Posted on by John

The Bessel functions Jn for even n look something like the sinc function. How well can you approximate the former by sums of the latter? To make things concrete, we’ll approximate J2. Here’s a plot of J2.

J_2

And here’s a plot of sinc(x) = sin(πx)/πx.

sinc(x)

The sinc approximation for a function f(x) is given by

f(x) \approx \sum_{j=-n}^n f(jh) \, \text{sinc}\left(\frac{x - jh}{h}\right)

Sinc approximation can be remarkably accurate, nearly optimal in some sense.

The accuracy of the approximation increases as n gets larger and h gets smaller. We will fix n = 10. How should we pick h? The paper cited in this post suggests using

h = \frac{\pi}{2} \sqrt{\frac{1}{2n}} = 0.35124

Let’s try that and see what happens.

The approximation isn’t very good overall, though it’s excellent near 0.

Before making plots, I had a plausible argument for why the value of h suggested above might be optimal. I also had an argument for why a much larger value of h, something on the order of 8 might be optimal. Turns out both are wrong. You can get a good approximation over a larger range by choosing h around 2.6.

Related posts

Airport abbreviation origins

Posted on by John

It doesn’t take much imagination to understand why DEN is the IATA abbreviation for the Denver airport, but the abbreviation MCO for the Orlando airport is more of a head scratcher.

Here is a list of the busiest airports in the US along with a brief indication of the reason behind their abbreviations. Some require more explanation, given below.

  1. ATL Hartsfield–Jackson ATLanta International Airport
  2. LAX Los Angeles International Airport (*)
  3. ORD Chicago O’Hare International Airport, formerly ORchardD Field Airport
  4. DFW Dallas/Fort Worth International Airport
  5. DEN DENver International Airport
  6. JFK John F. Kennedy International Airport in New York
  7. SFO San FranciscO International Airport
  8. SEA SEAttle-Tacoma International Airport
  9. MCO Orlando International Airport, formerly McCOy Air Force Base
  10. LAS Harry Reid International Airport in LAS Vegas
  11. CLT CharLoTte-Douglas International Airport
  12. EWR NEWaRk Liberty International Airport (*)
  13. PHX PHoeniX Sky Harbor International Airport
  14. IAH George Bush Intercontinental Airport in Houston (*)
  15. MIA MIAmi International Airport
  16. BOS BOSton Logan International Airport
  17. MSP Minneapolis-Saint Paul International Airport
  18. DTW DeTroit Metropolitan Wayne County Airport
  19. FLL Fort Lauderdale-HoLLywood International Airport
  20. PHL PHiLadelphia International Airport
  21. LGA New York LaGuardia Airport
  22. BWI Baltimore/Washington International Airport
  23. SLC Salt Lake City International Airport
  24. SAN SAN Diego International Airport
  25. IAD Washington Dulles International Airport, named after John Foster Dulles (*)
  26. DCA Ronald Reagan Washington National Airport in Washington DC
  27. TPA TamPA International Airport
  28. MDW Chicago MiDWay International Airport

The Los Angeles airport was originally abbreviated LA. When airports switched to 3-letter abbreviations in 1930, an X was added simply to pad LA to three letters.

In the United States, the initial letter N is reserved for the Navy, and so Newark airport is EWR rather than NEW. The initial letters W and K are also reserved to avoid confusion with radio stations, and initial Q is reserved to avoid confusion with Q codes.

Dulles was originally DIA, but was changed to IAD to avoid confusion with DCA.

Houston’s largest airport, IAH, has an awkward name because the name HOU was already assigned to the older Hobby Airport.

Related posts

Photo by Ronny Siegel from Pexels

Visually symmetric words

Posted on by John

I recently ran into the following comic strip online:

[Update: Thanks to Bryan Cantanzaro for letting me know via the comments that the image above was created by Hannah Hillam. The version I found had had her copyright information edited out. I will replace the image above with a legitimate version shortly.]

[Update 2: I’m not sure this is a Hannah Hillam cartoon per se; I haven’t found the exact source. Hannah Hillam makes a template available to let people put their own words in the format above, and the template does not contain a copyright notice. Maybe someone besides her make the cartoon above. The fact that the words are not hand drawn suggests this is the case. If you know who created the image please let me know and I will gladly credit them. ]

The comic is unsettling because it points out that a palindrome is a symmetric sequence of characters, which is not the same as a visually symmetric sequence.

What words are symmetric in the sense that “()()” is symmetric, i.e. visually symmetric rather than a symmetric sequence of characters?

The question isn’t well defined without some assumptions. Visual symmetry depends on whether characters are written in lower case or upper case, and it depends on the choice of font.

Let’s look at upper case first. I will assume the following letters are symmetric: A, H, I, M, O, T, U, V, W, X, and Y. Then the following words are symmetric: A, AHA, HAH, HUH, I, MAAM, MUM, TAT, TIT, TOOT, TOT, TUT, WOW.

For lower case, I will assume the following letters are symmetric: i, l, m, o, u, v, w, x, y. And I will assume b and d are mirror images, as well as p and q.

With these assumptions, the following words are symmetric: bid, bud, dib, doob, dub, ulu, wow.

An ulu, according to dictionary.com, is “a knife with a broad, nearly semicircular blade joined to a short haft at a right angle to the unsharpened side: a traditional tool of Inuit or Yupik women.”

Related posts

Pascal’s triangle mod row number

Posted on by John

Almost all binomial coefficients are divisible by their row number.

This is a theorem from [1]. What does it mean?

If you iterate through Pascal’s triangle, left-to-right and top-to-bottom, noting which entries C(m, k) are divisible by m, the proportion approaches 1 in the limit.

The author proves that the ratio converges to 1, but doesn’t say anything about the rate at which it approaches 1. By writing a little Python script we can observe how the ratio approaches 1.

First, let’s create a generator that will let us walk through Pascal’s triangle.

    def pascal():
        m, k = 0, 0
        while True:
            yield (m, k)
            k += 1
            if k > m:
                m += 1
                k = 0

We can use this generator to illustrate Pascal’s triangle mod row number.

    from math import comb

    p = pascal()
    m, k = next(p)
    while m < 10:
        ch = "*"
        if m > 0 and comb(m, k) % m == 0:
            ch = "0"
        print(ch, end="")
        if m == k:
            print()
        m, k = next(p)

This produces the following.

    *
    00
    *0*
    *00*
    *0*0*
    *0000*
    *0***0*
    *000000*
    *0*0*0*0*
    *00*00*00*

The theorem says that as we keep going, the proportion of 0’s in a diagram like the one above approaches 1.

Now let’s plot the proportion of zeros as we traverse Pascal’s triangle mod row number.

    N = 1000
    x = np.zeros(N)
    p = pascal()
    for n in range(N):
        m, k = next(p)
        if m > 0 and comb(m, k) % m == 0:
            x[n] = 1
    y = np.arange(N)
    plt.plot(y, x.cumsum()/y)
    plt.show()

Here’s what we get.

The ratio doesn’t seem to be converging to 1. If I had to guess, I might say it’s converging to 0.7 by looking at this plot. But if we go further out and switch to a log scale it seems more plausible that the sequence is converging to 1, albeit very slowly.

[1] Heiko Harborth. Divisibility of Binomial Coefficients by Their Row Number. The American Mathematical Monthly, Jan. 1977, Vol. 84, No. 1, pp. 35–37.

Chebyshev series for sine

Posted on by John

In last week’s post on polynomial approximations for sine, I showed that the polynomial based on Chebyshev series was much better than a couple alternatives. I calculated a few terms of the Chebyshev series for sin(πx) but didn’t include the calculations in that blog post. I calculated the series coefficients numerically, but this post will show how to calculate the coefficients analytically.

Generalities

The Chebyshev series for a function f(x) on [-1, 1] is given by

f(x) = \frac{a_0}{2} + \sum_{n=1}^\infty a_n T_n(x)

where Tn(x) is the nth Chebyshev polynomial of the first kind. The coefficients are given by

a_n = \frac{2}{\pi} \int_{-1}^1 \frac{f(x) \,T_n(x)}{\sqrt{1-x^2}} \, dx

One way of defining the polynomials Tn(x) is

T_n(\cos\theta) = \cos(n \theta)

and so the change of variables x = cos θ lets us conclude

a_n = \frac{2}{\pi} \int_0^\pi f(\cos \theta) \cos n\theta \, d\theta

Series for sin(πx)

Now for our particular function, f(x) = sin(πx), we know by symmetry that the coefficients with even subscripts will be zero. This is because sine is an odd function, and Tn is an even function when n is even,

Using equation 10.9.2 here we can prove that if n = 2k+1 then

a_n = (-1)^k 2 J_n(\pi)

where Jn is the nth Bessel function of the first kind.

(The preceding sentence was the conclusion to a fair amount of fumbling around on my part. As is often the case in mathematics, the length of the write-up is unrelated to the length of the discovery process.)

Related posts

Solar Day vs Sidereal Day

Posted on by John

How long does it take the earth to complete one rotation on its axis? The answer depends on your frame of reference. A solar day is the time it takes for the sun to appear at the same position in the sky. A sidereal day is the time it takes for a distant star to appear in the same position. These are not the same.

This post will illustrate the difference between a solar day and a sidereal day. To make things a little simpler, assume the earth has a perfectly circular orbit around the sun, and that the earth’s axis of rotation is perpendicular to the orbital plane, i.e. there is no axial tilt.

Sidereal day

Imagine an astronomer Alice observing our solar system from the vantage point of a distant star. How distant? We’ll show below that it doesn’t make much difference, but we’ll assume for now that she is “infinitely” far away, which means “far enough away that we don’t have to worry about exactly how far.”

The time it takes for Alice to observe one rotation of the earth on its axis is 1 sidereal day = 24 sidereal hours. We will suppose that from Alice’s perspective it takes 360 (sidereal) days for the earth to orbit the sun.

Here comes the sun

Let’s set the origin of our coordinate system at the sun. Assume that at time t = 0 the earth is located at (1, 0) and that an observer Bob is at the bottom of a deep well on the equator looking up at the sun. The time between Bob’s observations of the sun is one solar day.

Twenty four (sidereal) hours later, the earth is located at (cos 1°, sin 1°) and Bob’s well is parallel to the x-axis, but not looking directly at the sun. He will be looking at the sun a few minutes later when the earth’s rotation brings the sun into view.

Just how long will Bob have to wait to see the sun again? About 4 minutes, because the sun is 1° away from his line of sight, and he needs the earth to turn 1°, which takes 24/360 hours, or 4 minutes. This is not exactly correct though, because the earth has moved in its orbit during that 4 minutes.

So a solar day is about 4 minutes longer than the time it takes for the earth to rotate on its axis (from Alice’s perspective). Even though we’ve made several simplifying assumptions, our estimate only differs from the exact value by about 4 seconds.

Equations

Let the distance from the center of the earth to the sun be 1 and the radius of the earth be ε. Let t be time in (sidereal) days. The position of the center of the earth as a function of time will be

(cos t°, sin t°)

and Bob’s position is

(cos t° − ε cos 360t° , sin t° − ε sin 360t°).

Bob sees the sun at time t = 0. When will he see the sun next? When the slope of the line from the center of the earth to his position equals the slope of the line from the sun to the center of the earth, i.e.

tan t° = tan 360t°

The value of ε doesn’t matter.

There are two solutions to this equation, one when Bob is facing the sun and another when he is on the opposite side of the earth from the sun. We know t ≈ 1 and the solution near 1 is on the correct side of the sun, i.e.

t = 1.002786 days = 1 day + 4.011142 minutes.

Distant stars

Now let’s imagine at that time t = 0, while Bob is looking up at the sun, on the opposite side of the earth Charlie at the bottom of another well looking up a star a distance R away, located at (R+1, 0).

Charlie’s position as a function of t is

(cos t° + ε cos 360t° , sin t° + ε sin 360t°).

When will Charlie see his star next? When the line from the center of the earth through his position has the same slope as the line from Charlie to the star. This happens when

tan 360t° = sin t° / R,

the right side above being the tangent of the angle at R of a right triangle with base on the x-axis and hypotenuse running from the star to Charlie. As R goes to infinity, the right side goes to 0, and the solutions for t are integer numbers of days.

Charlie will see the star at time slightly less than 1, so let t = 1 − x. So we need to solve

tan 360(1-x)° = − tan x° = − sin (1-x)°/R.

Using the approximation sin θ ≈ θ ≈ tan θ for small angles θ (in radians) we have

-2πx ≈ −2π(1-x)/(360R)

and so

x = 1/(360R + 1).

Now R is very large. For the nearest star, Proxima Centauri, R is about 270,000 AU. So x is on the order of 10-8 or smaller. This is why it doesn’t matter which star Alice is located near: a sidereal day is essentially the same whatever distant star you use as your reference point.

Coding theory posts

Posted on by John

Here are some posts I’ve written that fall under the general heading of coding theory. Although coding theory can overlap with secret codes, it’s more concerned with things like Morse code, Reed-Solomon codes, and Unicode.

Radio related

Algebraic coding theory

Text encoding

Top posts of 2022

Posted on by John

These were the most popular posts on my site this year.

#10: How is portable radio possible? The length of an antenna is typically 1/2 or 1/4 of the length of the radio wave it’s designed to receive. How does an AM radio not need an antenna as long as a football field? See also Mathematics of radio.

#9: How to memorize the ASCII table Using landmarks, mnemonics, and the major memory system

#8: Org-mode as a lightweight notebook Emacs org-mode works like a Jupyter notebook, but is much simpler and much more transparent.

#7: Computing VIN checksums Python code to carry out a checksum for vehicle identification numbers

#6: The Chicken McNugget Monoid Finding the largest number of chicken nuggets you cannot buy.

#5: Phone tones in musical notation What is says on the tin.

#4: What use is mental math? Even though computers are cheap and ubiquitous, it’s useful to be about to quick, rough calculations in your head.

#3: Logarithms yearning to be free Theorems that have logarithmic special cases

#2: Hiragana, Katakana, and Unicode Japanese writing systems and how they map to Unicode

#1: Why a slide rule works Not how, but why. See also the post on circular slide rules.