Harmonic morphisms to P_3 – examples

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph \Gamma_2=P_3.

The path graph P_3

If \Gamma_1 = (V_1, E_1) and \Gamma_2 = (V_2, E_2) are graphs then a map \phi:\Gamma_1\to \Gamma_2 (that is, \phi: V_1\cup E_1\to V_2\cup E_2) is a morphism provided

  1. if \phi sends an edge to an edge then the edges vertices must also map to each other: e=(v,w)\in E_1 and \phi(e)\in E_2 then \phi(e) is an edge in \Gamma_2 having vertices \phi(v)\in V_2 and \phi(w)\in V_2, where \phi(v)\not= \phi(w), and
  2. if \phi sends an edge to a vertex then the edges vertices must also map to that vertex: if e=(v,w)\in E_1 and \phi(e)\in V_2 then \phi(e) = \phi(v) = \phi(w).

As a non-example, if \Gamma_1 is a planar graph, if \Gamma_2 is its dual graph, and if \phi:\Gamma_1\to\Gamma_2 is the dual map V_1\to E_2 and E_1\to V_2, then \phi is not a morphism.

Given a map \phi_E : E_1 \rightarrow E_2 \cup V_2, an edge e_1 is called horizontal if \phi_E(e_1) \in E_2 and is called vertical if \phi_E(e_1) \in V_2. We say that a graph morphism \phi: \Gamma_1 \rightarrow \Gamma_2 is a graph homomorphism if \phi_E (E_1) \subset E_2. Thus, a graph morphism is a homomorphism if it has no vertical edges.

Suppose that \Gamma_2 has at least one edge. Let Star_{\Gamma_1}(v) denote the star subgraph centered at the vertex v. A graph morphism \phi : \Gamma_1 \to \Gamma_2 is called harmonic if for all vertices v \in V(\Gamma_1), the quantity
\mu_\phi(v,f)= |\phi^{-1}(f) \cap Star_{\Gamma_1}(v)|
(the number of edges in \Gamma_1 adjacent to v and mapping to the edge f in \Gamma_2) is independent of the choice of edge f in Star_{\Gamma_2}(\phi(v)).

An example of a harmonic morphism can be described in the plot below as follows: \phi:\Gamma_1\to \Gamma_2=P_3 sends the red vertices in \Gamma_1 to the red vertex of \Gamma_2=P_3, the green vertices in \Gamma_1 to the green vertex of \Gamma_2=P_3, and the white vertices in \Gamma_1 to the white vertex of \Gamma_2=P_3.

Example 1:

P3-C3-V

Example 2:
D3-2110

Example 3:
cyclic4-2101

Michael Reid’s Happy New Year Puzzles, 2018

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some New Year’s puzzles to help start out 2018.

1. Arrange the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 in the
expression a^b + c^d + e^f + g^h + i^j to make 2018.

2. (a) Express 2018 = p^q + r^s where p, q, r, s are primes.
(b) Express 2018 = p^q - r^s where p, q, r, s are primes.

3. (a) Is it possible to put the first 9 primes, 2, 3, 5, 7, 11, 13,
17, 19 and 23 into a 3×3 matrix that has determinant 2018?
(b) Is it possible to put the first 16 primes, 2, 3, 5, … , 53,
into a 4×4 matrix that has determinant 2018?

4. (a) Express 2018 = A / B using the fewest number of distinct
digits.
For example, the expression 7020622 / 3479 uses only seven
different digits. But it is possible to do better than this.
(b) Express 2018 = (A_1 \cdot A_2 \cdot ... \cdot A_m) / (B_1 \cdot B_2 \cdot ... \cdot B_n) using the fewest number of distinct digits.

Michael Reid’s Happy New Year Puzzle, 2017

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some interesting puzzles to start the New Year; hopefully they are not too easy!

1. Express 2017 as a quotient of palindromes.

2. (a) Are there two positive integers whose sum is 2017 and whose product
is a palindrome?
(b) Are there two positive integers whose difference is 2017 and whose
product is a palindrome?

3. Is there a positive integer n such that both 2017 + n and
2017 n are palindromes?

4. What is the smallest possible sum of the decimal digits of 2017 n ,
where n is …
(a) … a positive integer?
(b) … a prime number?
(c) … a palindrome?

5. Consider the following two operations on a positive integer:
(i) replace a string of consecutive digits by its square,
(ii) if a string of consecutive digits is a perfect cube,
replace the string by its cube root.

Neither the string being replaced, nor its replacement, may have
have “leading zeros”. For example, from 31416 , we may change it to
319616 , by squaring the 14 . From 71253 , we may change it to
753 by taking the cube root of 125 .

(a) Starting from the number 2017 , what is the smallest number we
can reach with a sequence of these operations?
(b) What is the smallest number from which we can start, and reach
the number 2017 with a sequence of these operations?

6. Find a list of positive rational numbers, q_1 , q_2 , … , q_n
whose product is 1 , and whose sum is 2017 . Make your list as
short as possible.
Extra Credit: Prove that you have the shortest possible list.

Michael Reid’s Happy New Year Problems, 2020

Posted by permission of Michael Reid. Enjoy!

New Year’s Greetings!

Here are some fun puzzles to start the year.

1. Substitute the numbers 1, 2, … , 9 for the letters
a, b, … , i in the expression a^b + c^d + (e + f + g - h)^i
to get 2020.

2. Use the digits 1, 2, … , 9 in order, and any of the usual
arithmetic operations and parentheses to get a number that is
as close as possible to, but not exactly equal to 2020.

3. Express 2019/2020 as a sum of distinct Egyptian fractions,
i.e. 1 / n_1 + 1 / n_2 + ... + 1 / n_k for integers 0 < n_1 < n_2 < ...  n_k < 202049
(but 202049 is not square).

5. Make a 4×4 matrix of single-digit integers (0-9) with digits
2, 0, 2, 0 on the main diagonal, and having determinant 2020.
Is it possible to do it with a symmetric matrix?

If you liked this one, check out other puzzles ont this blog tagged with “Michael Reid”.

Differential equations and SageMath

The files below were on my teaching page when I was a college teacher. Since I retired, they disappeared. Samuel Lelièvre found an archived copy on the web, so I’m posting them here.

The files are licensed under the Attribution-ShareAlike Creative Commons license.

  1. Partial fractions handout, pdf
  2. Introduction to matrix determinants handout, pdf
  3. Impulse-response handout, pdf
  4. Introduction to ODEs, pdf
  5. Initial value problems, pdf
  6. Existence and uniqueness, pdf
  7. Euler’s method for numerically approximating solutions to DEs, pdf.
    Includes both 1st order DE case (with Euler and improved Euler) and higher order DE and systems of DEs cases, without improved Euler.
  8. Direction fields and isoclines, pdf
  9. 1st order ODEs, separable and linear cases, pdf
  10. A falling body problem in Newtonian mechanics, pdf
  11. A mixing problem, pdf
  12. Linear ODEs, I, pdf
  13. Linear ODEs, II, pdf
  14. Undetermined coefficients for non-homogeneous 2nd order constant coefficient ODEs, pdf
  15. Variation of parameters for non-homogeneous 2nd order constant coefficient ODEs, pdf.
  16. Annihilator method for non-homogeneous 2nd order constant coefficient ODEs, pdf.
    I found students preferred (the more-or-less equivalent) undetermined coefficient method, so didn’t put much effort into these notes.
  17. Springs, I, pdf
  18. Springs, II, pdf
  19. Springs, III, pdf
  20. LRC circuits, pdf
  21. Power series methods, I, pdf
  22. Power series methods, II, pdf
  23. Introduction to Laplace transform methods, I, pdf
  24. Introduction to Laplace transform methods, II, pdf
  25. Lanchester’s equations modeling the battle between two armies, pdf
  26. Row reduction/Gauss elimination method for systems of linear equations, pdf.
  27. Eigenvalue method for homogeneous constant coefficient 2×2 systems of 1st order ODEs, pdf.
  28. Variation of parameters for first order non-homogeneous linear constant coefficient systems of ODEs, pdf.
  29. Electrical networks using Laplace transforms, pdf
  30. Separation of variables and the Transport PDE, pdf
  31. Fourier series, pdf.
  32. one-dimensional heat equation using Fourier series, pdf.
  33. one-dimensional wave equation using Fourier series, pdf.
  34. one-dimensional Schroedinger’s wave equation for a “free particle in a box” using Fourier series, pdf.
  35. All these lectures collected as one pdf (216 pages).
    While licensed Attribution-ShareAlike CC, in the US this book is in the public domain, as it was written while I was a US federal government employee as part of my official duties. A warning – it has lots of typos. The latest version, written with Marshall Hampton, is a JHUP book, much more polished, available on amazon and the JHUP website. Google “Introduction to Differential Equations Using Sage”.

Course review: pdf

Love, War, and Zombies, pdf
This set of slides is of a lecture I would give if there was enough time towards the end of the semester

Integral Calculus and SageMath

Long ago, using LaTeX I assembled a book on Calculus II (integral calculus), based on notes of mine, Dale Hoffman (which was written in word), and William Stein. I ran out of energy to finish it and the source files mostly disappeared from my HD. Recently, Samuel Lelièvre found a copy of the pdf of this book on the internet (you can download it here). It’s licensed under a Creative Commons Attribution 3.0 United States License. You are free to print, use, mix or modify these materials as long as you credit the original authors.

Table of Contents

0 Preface

1 The Integral
1.1 Area
1.2 Some applications of area
1.2.1 Total accumulation as “area”
1.2.2 Problems
1.3 Sigma notation and Riemann sums
1.3.1 Sums of areas of rectangles
1.3.2 Area under a curve: Riemann sums
1.3.3 Two special Riemann sums: lower and upper sums
1.3.4 Problems
1.3.5 The trapezoidal rule
1.3.6 Simpson’s rule and Sage
1.3.7 Trapezoidal vs. Simpson: Which Method Is Best?
1.4 The definite integral
1.4.1 The Fundamental Theorem of Calculus
1.4.2 Problems
1.4.3 Properties of the definite integral
1.4.4 Problems
1.5 Areas, integrals, and antiderivatives
1.5.1 Integrals, Antiderivatives, and Applications
1.5.2 Indefinite Integrals and net change
1.5.3 Physical Intuition
1.5.4 Problems
1.6 Substitution and Symmetry
1.6.1 The Substitution Rule
1.6.2 Substitution and definite integrals
1.6.3 Symmetry
1.6.4 Problems

2 Applications
2.1 Applications of the integral to area
2.1.1 Using integration to determine areas
2.2 Computing Volumes of Surfaces of Revolution
2.2.1 Disc method
2.2.2 Shell method
2.2.3 Problems
2.3 Average Values
2.3.1 Problems
2.4 Moments and centers of mass
2.4.1 Point Masses
2.4.2 Center of mass of a region in the plane
2.4.3 x-bar For A Region
2.4.4 y-bar For a Region
2.4.5 Theorems of Pappus
2.5 Arc lengths
2.5.1 2-D Arc length
2.5.2 3-D Arc length

3 Polar coordinates and trigonometric integrals
3.1 Polar Coordinates
3.2 Areas in Polar Coordinates
3.3 Complex Numbers
3.3.1 Polar Form
3.4 Complex Exponentials and Trigonometric Identities
3.4.1 Trigonometry and Complex Exponentials
3.5 Integrals of Trigonometric Functions
3.5.1 Some Remarks on Using Complex-Valued Functions

4 Integration techniques
4.1 Trigonometric Substitutions
4.2 Integration by Parts
4.2.1 More General Uses of Integration By Parts
4.3 Factoring Polynomials
4.4 Partial Fractions
4.5 Integration of Rational Functions Using Partial Fractions
4.6 Improper Integrals
4.6.1 Convergence, Divergence, and Comparison

5 Sequences and Series
5.1 Sequences
5.2 Series
5.3 The Integral and Comparison Tests
5.3.1 Estimating the Sum of a Series
5.4 Tests for Convergence
5.4.1 The Comparison Test
5.4.2 Absolute and Conditional Convergence
5.4.3 The Ratio Test
5.4.4 The Root Test
5.5 Power Series
5.5.1 Shift the Origin
5.5.2 Convergence of Power Series
5.6 Taylor Series
5.7 Applications of Taylor Series
5.7.1 Estimation of Taylor Series

6 Some Differential Equations
6.1 Separable Equations
6.2 Logistic Equation

7 Appendix: Integral tables

Questions about quadratic residues

Let P denote the set of all primes and, for p \in P, let (*/p) denote the Legendre quadratic residue symbol mod p. Let {\mathbb N}=\{1,2,\dots\} denote the set of natural numbers and let

L: {\mathbb N}\to \{-1,0,1\}^P,

denote the mapping L(n)=( (n/2), (n/3), (n/5), \dots), so the kth component of L(n) is L(n)_k=(n/p_k) where p_k denotes the kth prime in P. The following result is “well-known” (or, as the joke goes, it’s well-known to those who know it well:-).

Theorem: The restriction of L to the subset {\mathbb S} of square-free integers is an injection.

In fact, one can be a little more precise. Let P_{\leq M} denote the set of the first M primes, let {\mathbb S}_N denote the set of square-free integers \leq N, and let

L_M: {\mathbb N}\to \{-1,0,1\}^{P_M},

denote the mapping L_M(n)=( (n/2), (n/3), (n/5), \dots, (n/p_M)).

Theorem: For each N>1, there is an M=M(N)>1 such that the restriction of L_M to the subset {\mathbb S}_N is an injection.

I am no expert in this field, so perhaps the following question is known.

Question: Can one give an effective upper bound on M=M(N)>1 as a function of N>1?

I’ve done some computer computations using SageMath and it seems to me that

M=O(N)

(i.e., there is a linear bound) is possible. On the other hand, my computations were pretty limited, so that’s just a guess.