# Differential calculus using Sagemath

Granville’s classic text book Elements of the Differential and Integral Calculus fell into the public domain and then much of it (but not all, at the time of this writing) was scanned into wikisource primarily by R. J. Hall. Granville’s entire book contains material on differential, integral, and even multivariable calculus. The material in the subset here is restricted to differential calculus topics, though contains some material which might properly belong to an elementary differential geometry course. The above-mentioned wikisource document uses mathml and latex and some Greek letter fonts.

In particular, the existence of this document owes itself primarily to three great open source projects: TeX/LaTeX, Wikipedia, and Sagemath (http://www.sagemath.org). Some material from Sean Mauch’s public domain text on Applied Mathematics, was also included.

The current latex document is due to David Joyner, who is responsible for re-formatting, editing for readability, the correction (or introduction) of typos from the scanned version, and any extra material added (for example, the hyperlinked cross references, and the Sagemath material). Please email corrections to wdjoyner@gmail.com.

Acknowledgements: I thank the following readers for reporting typos: Mario Pernici, Jacob Hicks.

Now available from amazon.com for \$20 (not including shipping).

# Discrete Fourier transforms using Sagemath

Here are some Sagemath examples for DFTs, DCTs, and DST’s. You can try copying and pasting them into the Sagemath cloud, for example.

The Sagemath dft command applies to a sequence S indexed by a set J computes the un-normalized DFT: (in Python)

[sum([S[i]*chi(zeta**(i*j)) for i in J]) for j in J]Here are some examples which explain the syntax:

sage: J = range(6)
sage: A = [ZZ(1) for i in J]
sage: s = IndexedSequence(A,J)
sage: s.dft(lambda x:x^2)
Indexed sequence: [6, 0, 0, 6, 0, 0]
indexed by [0, 1, 2, 3, 4, 5]
sage: s.dft()
Indexed sequence: [6, 0, 0, 0, 0, 0]
indexed by [0, 1, 2, 3, 4, 5]
sage: G = SymmetricGroup(3)
sage: J = G.conjugacy_classes_representatives()
sage: s = IndexedSequence([1,2,3],J) # 1,2,3 are the values of a class fcn on G
sage: s.dft()   # the "scalar-valued Fourier transform" of this class fcn
Indexed sequence: [8, 2, 2]
indexed by [(), (1,2), (1,2,3)]
sage: J = AbelianGroup(2,[2,3],names='ab')
sage: s = IndexedSequence([1,2,3,4,5,6],J)
sage: s.dft()   # the precision of output is somewhat random and arch. dependent.
Indexed sequence: [21.0000000000000, -2.99999999999997 - 1.73205080756885*I, -2.99999999999999 + 1.73205080756888*I, -9.00000000000000 + 0.0000000000000485744257349999*I, -0.00000000000000976996261670137 - 0.0000000000000159872115546022*I, -0.00000000000000621724893790087 - 0.0000000000000106581410364015*I]
indexed by Multiplicative Abelian Group isomorphic to C2 x C3
sage: J = CyclicPermutationGroup(6)
sage: s = IndexedSequence([1,2,3,4,5,6],J)
sage: s.dft()   # the precision of output is somewhat random and arch. dependent.
Indexed sequence: [21.0000000000000, -2.99999999999997 - 1.73205080756885*I, -2.99999999999999 + 1.73205080756888*I, -9.00000000000000 + 0.0000000000000485744257349999*I, -0.00000000000000976996261670137 - 0.0000000000000159872115546022*I, -0.00000000000000621724893790087 - 0.0000000000000106581410364015*I]
indexed by Cyclic group of order 6 as a permutation group
sage: p = 7; J = range(p); A = [kronecker_symbol(j,p) for j in J]
age: s = IndexedSequence(A,J)
sage: Fs = s.dft()
sage: c = Fs.list()[1]; [x/c for x in Fs.list()]; s.list()
[0, 1, 1, -1, 1, -1, -1]
[0, 1, 1, -1, 1, -1, -1]

The DFT of the values of the quadratic residue symbol is itself, up to a constant factor (denoted c on the last line above).

Here is a 2nd example:

sage: J = range(5)
sage: A = [ZZ(1) for i in J]
sage: s = IndexedSequence(A,J)
sage: fs = s.dft(); fs
Indexed sequence: [5, 0, 0, 0, 0]
indexed by [0, 1, 2, 3, 4]
sage: it = fs.idft(); it
Indexed sequence: [1, 1, 1, 1, 1]
indexed by [0, 1, 2, 3, 4]
age: it == s
True
sage: t = IndexedSequence(B,J)
sage: s.convolution(t)
[1, 2, 3, 4, 5, 4, 3, 2, 1]

Here is a 3rd example:

sage: J = range(5)
sage: A = [exp(-2*pi*i*I/5) for i in J]
sage: s = IndexedSequence(A,J)
sage: s.dct()    # discrete cosine
Indexed sequence: [2.50000000000011 + 0.00000000000000582867087928207*I, 2.50000000000011 + 0.00000000000000582867087928207*I, 2.50000000000011 + 0.00000000000000582867087928207*I, 2.50000000000011 + 0.00000000000000582867087928207*I, 2.50000000000011 + 0.00000000000000582867087928207*I]
indexed by [0, 1, 2, 3, 4]
sage: s.dst()        # discrete sine
Indexed sequence: [0.0000000000000171529457304586 - 2.49999999999915*I, 0.0000000000000171529457304586 - 2.49999999999915*I, 0.0000000000000171529457304586 - 2.49999999999915*I, 0.0000000000000171529457304586 - 2.49999999999915*I, 0.0000000000000171529457304586 - 2.49999999999915*I]
indexed by [0, 1, 2, 3, 4]

Here is a 4th example:

sage: I = range(3)
sage: A = [ZZ(i^2)+1 for i in I]
sage: s = IndexedSequence(A,I)
sage: P1 = s.plot()
sage: P2 = s.plot_histogram()

P1 and P2 are displayed below:

The plot of P1

The plot of P2

# Remarks on mathematical research, according to Ira Glass

Ira Glass, of This American Life (http://www.thisamericanlife.org/), did an interview where he talked at length about writing news stories. They are here (links are to short youtube videos):

1. Ira Glass on Storytelling, part 1 of 4
2. Ira Glass on Storytelling, part 2 of 4
3. Ira Glass on Storytelling, part 3 of 4
4. Ira Glass on Storytelling, part 4 of 4

I thought a lot of what he said was based on general principles which applied to mathematical research as well. Here is perhaps what he would have said if he was talking about mathematics, sometimes with direct quotes from his interview:

There are two building blocks to a idea for a paper

1.  The problem or question. This is sometimes an issue in the intersection of two fields or a question of why some object of interest behaves the way you think it does, based on an example you know.
2. The revelation. This might be a key example or technique that will hopefully reveal the answer to your question.

You can have a great question, but if they don’t turn out to have any useful techniques or examples to work with, your idea is uninteresting. Conversely you can have a significant revelation with a fantastically powerful method, but if the problem or examples themselves are uninteresting, again you’ve got a weak idea.

You have to set aside just as much time looking for good ideas as you do producing them. In other words, the work of thinking up a good idea to write about is as much work and time as writing it up.

Not enough gets said about the importance of abandoning crap.

Most of your research ideas are going to be crap. That’s okay because the only way you can surface great ideas is by going through a lot of crappy ones. The only reason you want to be doing this is to make something memorable and special.

“The thing I’d like to say to you with all my heart is that most everybody I know who does interesting creative work went through a phase of years where with their good taste, they could tell what they were doing wasn’t as good as they wanted it to be … it didn’t have that special thing they wanted it to have … Everybody goes through that phase … and the most important thing you can do is do a lot of work.”

Ira Glass.

# Examples of graph-theoretic harmonic morphisms using Sage

In the case of simple graphs (without multiple edges or loops), a map $f$ between graphs $\Gamma_2 = (V_2,E_2)$ and $\Gamma_1 = (V_1, E_1)$ can be uniquely defined by specifying where the vertices of $\Gamma_2$ go. If $n_2 = |V_2|$ and $n_1 = |V_1|$ then this is a list of length $n_2$ consisting of elements taken from the $n_1$ vertices in $V_1$.

Let’s look at an example.

Example: Let $\Gamma_2$ denote the cube graph in ${\mathbb{R}}^3$ and let $\Gamma_1$ denote the “cube graph” (actually the unit square) in ${\mathbb{R}}^2$.

This is the 3-diml cube graph $\Gamma_2$ in Sagemath

The cycle graph $\Gamma_1$ on 4 vertices (also called the cube graph in 2-dims, created using Sagemath.

We define a map $f:\Gamma_2\to \Gamma_1$ by

f = [[‘000’, ‘001’, ‘010’, ‘011’, ‘100’, ‘101’, ‘110’, ‘111’], [“00”, “00”, “01”, “01”, “10”, “10”, “11”, “11”]].

Definition: For any vertex $v$ of a graph $\Gamma$, we define the star $St_\Gamma(v)$ to be a subgraph of $\Gamma$ induced by the edges incident to $v$. A map $f : \Gamma_2 \to \Gamma_1$ is called harmonic if for all vertices $v' \in V(\Gamma_2)$, the quantity

$|\phi^{-1}(e) \cap St_{\Gamma_2}(v')|$

is independent of the choice of edge $e$ in $St_{\Gamma_1}(\phi(v'))$.

Here is Python code in Sagemath which tests if a function is harmonic:

def is_harmonic_graph_morphism(Gamma1, Gamma2, f, verbose = False):
"""
Returns True if f defines a graph-theoretic mapping
from Gamma2 to Gamma1 that is harmonic, and False otherwise.

Suppose Gamma2 has n vertices. A morphism
f: Gamma2 -> Gamma1
is represented by a pair of lists [L2, L1],
where L2 is the list of all n vertices of Gamma2,
and L1 is the list of length n of the vertices
in Gamma1 that form the corresponding image under
the map f.

EXAMPLES:
sage: Gamma2 = graphs.CubeGraph(2)
sage: Gamma1 = Gamma2.subgraph(vertices = ['00', '01'], edges = [('00', '01')])
sage: f = [['00', '01', '10', '11'], ['00', '01', '00', '01']]
sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
True
sage: Gamma2 = graphs.CubeGraph(3)
sage: Gamma1 = graphs.TetrahedralGraph()
sage: f = [['000', '001', '010', '011', '100', '101', '110', '111'], [0, 1, 2, 3, 3, 2, 1, 0]]
sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
True
sage: Gamma2 = graphs.CubeGraph(3)
sage: Gamma1 = graphs.CubeGraph(2)
sage: f = [['000', '001', '010', '011', '100', '101', '110', '111'], ["00", "00", "01", "01", "10", "10", "11", "11"]]
sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
True
sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f, verbose=True)
This [, ]] passes the check: ['000', [1, 1]]
This [, ]] passes the check: ['001', [1, 1]]
This [, ]] passes the check: ['010', [1, 1]]
This [, ]] passes the check: ['011', [1, 1]]
This [, ]] passes the check: ['100', [1, 1]]
This [, ]] passes the check: ['101', [1, 1]]
This [, ]] passes the check: ['110', [1, 1]]
This [, ]] passes the check: ['111', [1, 1]]
True
sage: Gamma2 = graphs.TetrahedralGraph()
sage: Gamma1 = graphs.CycleGraph(3)
sage: f = [[0,1,2,3],[0,1,2,0]]
sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
False
sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f, verbose=True)
This [, ]] passes the check: [0, [1, 1]]
This [, ]] fails the check: [1, [2, 1]]
This [, ]] fails the check: [2, [2, 1]]
False

"""
V1 = Gamma1.vertices()
n1 = len(V1)
V2 = Gamma2.vertices()
n2 = len(V2)
E1 = Gamma1.edges()
m1 = len(E1)
E2 = Gamma2.edges()
m2 = len(E2)
edges_in_common = []
for v2 in V2:
w = image_of_vertex_under_graph_morphism(Gamma1, Gamma2, f, v2)
str1 = star_subgraph(Gamma1, w)
Ew = str1.edges()
str2 = star_subgraph(Gamma2, v2)
Ev2 = str2.edges()
sizes = []
for e in Ew:
finv_e = preimage_of_edge_under_graph_morphism(Gamma1, Gamma2, f, e)
L = [x for x in finv_e if x in Ev2]
sizes.append(len(L))
#print v2,e,L
edges_in_common.append([v2, sizes])
ans = True
for x in edges_in_common:
sizes = x[1]
S = Set(sizes)
if S.cardinality()>1:
ans = False
if verbose and ans==False:
print "This [, ]] fails the check:", x
if verbose and ans==True:
print "This [, ]] passes the check:", x
return ans



For further details (e.g., code to

star_subgraph