-
Notifications
You must be signed in to change notification settings - Fork 3
/
draft19.tex
19263 lines (15400 loc) · 747 KB
/
draft19.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%% LyX 2.3.6.1 created this file. For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[12pt,oneside,english]{amsbook}
\usepackage[garamond]{mathdesign}
\renewcommand{\sfdefault}{uop}
\usepackage{beramono}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{geometry}
\geometry{verbose,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in}
\usepackage{color}
\usepackage{babel}
\usepackage{array}
\usepackage{varioref}
\usepackage{float}
\usepackage{calc}
\usepackage{units}
\usepackage{mathtools}
\usepackage{multirow}
\usepackage{algorithm2e}
\usepackage{amsbsy}
\usepackage{amstext}
\usepackage{amsthm}
\usepackage{mathdots}
\usepackage{stmaryrd}
\makeindex
\usepackage{graphicx}
\usepackage{tablefootnote}
\usepackage[unicode=true,pdfusetitle,
bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true]
{hyperref}
\hypersetup{
linkcolor=darklinkcolor,urlcolor=darklinkcolor,citecolor=darkcitecolor,naturalnames=true,hypertexnames=false}
\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\numberwithin{section}{chapter}
\theoremstyle{plain}
\newtheorem*{thm*}{\protect\theoremname}
\usepackage{framed}
\newenvironment{sageinteraction}%
{\begin{center}\begin{minipage}[t]{0.8\columnwidth}%
%\definecolor{shadecolor}{rgb}{0.9,0.9,1.0}%
%\definecolor{shadecolor}{rgb}{0.734375,0.71875,0.5390625}%
%\definecolor{shadecolor}{rgb}{0.8156862745,0.807843,0.6823529}%
%\definecolor{shadecolor}{rgb}{0.854901960784314, 0.843137254901961, 0.745098039215686}
\definecolor{shadecolor}{rgb}{0.890196078431372, 0.882352941176471, 0.807843137254902}
\begin{shaded}}%
{\end{shaded}\end{minipage}\end{center}}
\newenvironment{lyxlist}[1]
{\begin{list}{}
{\settowidth{\labelwidth}{#1}
\setlength{\leftmargin}{\labelwidth}
\addtolength{\leftmargin}{\labelsep}
\renewcommand{\makelabel}[1]{##1\hfil}}}
{\end{list}}
\usepackage{framed}
\newenvironment{pseudocode}%
{\begin{center}\begin{minipage}[t]{0.8\columnwidth}%
\definecolor{shadecolor}{rgb}{0.9,0.9,1.0}
%\definecolor{shadecolor}{rgb}{0.734375,0.71875,0.5390625}%
\begin{shaded}}%
{\end{shaded}\end{minipage}\end{center}}
\newcommand\thmsname{\protect\theoremname}
\newcommand\nm@thmtype{theorem}
\theoremstyle{plain}
\newtheorem*{namedtheorem}{\thmsname}
\newenvironment{namedthm}[1][Undefined Theorem Name]{
\ifx{#1}{Undefined Theorem Name}\renewcommand\nm@thmtype{theorem*}
\else\renewcommand\thmsname{#1}\renewcommand\nm@thmtype{namedtheorem}
\fi
\begin{\nm@thmtype}}
{\end{\nm@thmtype}}
\theoremstyle{remark}
\newtheorem*{rem*}{\protect\remarkname}
\theoremstyle{definition}
\newtheorem*{defn*}{\protect\definitionname}
\theoremstyle{definition}
\newtheorem*{example*}{\protect\examplename}
\newcommand\keyboardpress[1]{{\texttt{\color{keyboardcolor}#1}}}
\newcommand\sageword[1]{{\texttt{\color{sagecolor}#1}}}
\newcommand\sageconstant[1]{{\texttt{\textit{\color{sagecolor}#1}}}}
\newcommand\boolconstant[1]{{\textit{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage[autoplay,autoresume,loop,draft]{animate}
\usepackage{textcomp}
\usepackage{mathtools}
\definecolor{darklinkcolor}{rgb}{0,0,0.7}
\definecolor{darkcitecolor}{rgb}{0.4,0,0}
\definecolor{greylabel}{rgb}{0.8,0.8,0.8}
\definecolor{softblue}{rgb}{0.3,0.6,0.8}
\definecolor{softgreen}{rgb}{0.3,0.6,0.5}
\definecolor{sagecolor}{rgb}{0.329411764705882, 0.321568627450980, 0.243137254901961}
%\definecolor{sagecolor}{rgb}{0.470588235294118, 0.458823529411765, 0.345098039215686}
%\definecolor{sagecolor}{rgb}{0.611764705882353, 0.600000000000000, 0.450980392156863}
%\definecolor{sagecolor}{rgb}{0.737254901960784, 0.721568627450980, 0.541176470588235}
%\definecolor{sagecolor}{rgb}{0.815686274509804, 0.807843137254902, 0.682352941176471}
%\definecolor{sagecolor}{rgb}{0.925490196078431, 0.921568627450980, 0.874509803921569}
\definecolor{sageerrorcolor}{rgb}{0.8,0,0}
\definecolor{keyboardcolor}{rgb}{0.3,0.3,0.3}
\newcommand\lacol{\color{greylabel}}
\newcommand\sageinput[1]{%
\hangindent=2.8em\texttt{\textcolor{blue}{sage:}}\texttt{\ #1}%
}
\newcommand\sagemoreinput[1]{%
\hangindent=2.8em\texttt{\textcolor{blue}{\ \ \ \ \ }}\texttt{\ #1}%
}
\newcommand\sageoutput[1]{%
\texttt{\textcolor{blue}{#1}}%
}
\newcommand\sageerror[1]{%
\texttt{\textcolor{sageerrorcolor}{#1}}%
}
\newcommand\sageindent{\texttt{\ \hspace{4em}}}
\newcommand\pseudocodestatement[1]{%
{\ #1}%
}
\newcommand\mex{\ensuremath{\mathrm{mex}}}
\def\online{online}
\def\deadtree{deadtree}
\def\onlineordeadtree{online}
%\def\onlineordeadtree{deadtree}
\makeatother
\providecommand{\definitionname}{Definition}
\providecommand{\examplename}{Example}
\providecommand{\remarkname}{Remark}
\providecommand{\theoremname}{Theorem}
\begin{document}
\title{Mathematical Explorations With Computer Algebra Technology\\
\includegraphics[width=3in]{graphics/mew_cats/mews_parabola_mouse}}
\author{John Harris,\\
Karen Kohl, and\\
John Perry,\\
all employed at the University of Southern Mississippi\\
(at least until the Provost's Office reads this debacle)}
\subjclass[2000]{97U30, 97N80}
\maketitle
\vfill{}
Copyright \textcopyright\ 2016\textendash 2021 John Harris, Karen
Kohl, and John Perry
Draft $2\cdot3^{2}$, June $\left(x+1\right)\left(x+5\right)$, where
$x$ is the meaning of life, the universe, and everything
\href{https://creativecommons.org/licenses/by-sa/4.0/}{License CC-BY-SA}
\tableofcontents{}
\chapter*{Acknowledgments}
The authors would like to thank:
\begin{itemize}
\item The Office of the Provost at the University of Southern Mississippi,
who in 2016 supported the creation of this work with a Summer Grant
for the Improvement for Instruction.
\item William Stein and various Sage developers and users for moral support
and occasional financial support to attend Sage Days workshops.
\item All the developers who have contributed to the Sage project, whether
directly or indirectly.
\item Amber Desrosiers and Candice Bardwell Mitchell suffered through an
early draft of this text, and found more typographical errors than
we care to admit.
\item Valerio de Angelis kindly pointed out a large number of typographical
errors, and suggested an improvement to a joke on infinite loops.
He also contributed a few of the labs in the Encyclopædia Laboratorica.
\item Two of us have spouses and children that deserve apologies more than
thanks, two of us have cats that deserve whatever it is that cats
deserve (everything?), and one of us has a bunny and a turtle, both
of which deserve more attention.
\end{itemize}
In addition:
\begin{itemize}
\item The image of Glenda, the Plan 9 Bunny on p.~\pageref{img: glenda}
was downloaded from \href{http://plan9.bell-labs.com/plan9/glenda.html}{Bell Labs' Plan 9 website}
and is used according to the terms given.
\item The image of Rabbit Island on p.~\pageref{img: rabbit island} was
taken by \href{https://flic.kr/p/otnhcN}{Kim Bui} and is used under
a specially-granted license (\href{https://creativecommons.org/licenses/by-sa/2.0/}{CC BY-SA 2.0}).
\end{itemize}
\chapter*{Preface}
\section*{Why did you write this text?}
The main goal of this text is to justify a partial summer salary extended
us by our employer's Provost, who doubtless will never err in this
fashion again.
\section*{No, really, why did you write this text?}
Our institution offers majors a class on problem solving with technology
titled, \emph{Mathematical Computation.} We don't find a text that
fits its unique character. We believe in the course and think it's
a good idea; many of the students who take it end up agreeing.\footnote{This agreement often occurs only after they experience an internship
or first job, but that counts!}
Originally the class used a textbook based on a different computer
algebra system, but for reasons listed below, we switched to Sage.
Sage's interface relies on Python, so we used a very good book on
Python programming for a while, but there's only so far a book on
Python programming will take you with Sage.
Hence this book. With any luck, the resulting text will spring up
like a fungus, here and there, impervious to eradication, until it
comes to dominate the landscape of mathematics education.
\section*{What instructional value does this text offer?}
We would like to think this book would be useful for any situation
where an individual is moving from ``high school'' mathematics,
in which we include basic calculus, to ``university'' mathematics,
which includes intermediate calculus and a lot of stuff besides. Many
of our students struggle with the transition from the primarily concrete,
computational mathematics they experienced in their youth, to the
increasingly abstract, theoretical mathematics they encounter in higher
mathematics.
Technology has become an indispensable aspect of most mathematics
education. The amount of computing power in today's cell phones is
several orders of magnitude more than home computers had in the authors'
childhood \textemdash{} and most families could not even \emph{afford}
a home computer. \textbf{\emph{Ours is a magical world,}} yet students
are often reluctant to \emph{play} in this world. If they don't know
how to solve a problem right away, they think something's wrong. We
can teach them about groups (say) and give them some examples, but
students are often too reluctant to explore the examples on their
own.
\section*{Why Sage?}
We prefer \href{https://www.sagemath.org/}{Sage} for a number of
reasons:
\begin{itemize}
\item Sage is ``free as in beer.'' The authors work at a university in
one of the nation's materially more modest states; while many computer
algebra systems' student editions are arguably affordable, they are
nevertheless a nontrivial addition to the high cost our students already
bear.
\item Sage is ``free as in speech.'' Instructors can show talented students
parts of the code, and encourage them to get involved. There are doubtless
a number of good undergraduate research projects that could lead to
contributions to the Sage codebase. Talented instructors can contribute
code in ways that improve Sage's use in education. For that matter,
two of us have shown that even talent\emph{less} instructors can contribute
code to Sage. Don't be shy: the community is supportive!
\item Sage's interface relies on \href{http://www.python.org/}{Python},
an industry-standard programming language in high demand among employers.
Teaching students Sage means that we teach them quite a bit of Python
as well, increasing their employment prospects.
\end{itemize}
\section*{Aren't there already some good references on Sage?}
Yes, and that's the point; they are \emph{references} for mathematicians
and students to learn \emph{Sage}. This text aims to help students
learn \emph{mathematics} via Sage. This puts it into a different niche,
which we hope will prove not only profitable,\footnote{Stop laughing.}
but also useful,\footnote{Really. Stop laughing.} both to read and
to edit.
\section*{How do \emph{you} typically use this text?}
No lab section is attached to the course at our institution, so we
tend to offer in-class lab days; proceed in some semblance of the
order provided here; and assign textbook questions, labs, and tests.
We use different labs, according to the instructor and the year. We
also modify the labs on occasion. Editing the labs to taste is advisable
in an age where a nontrivial number of students has learned that outsourcing
production to an online search engine provides pre-fabricated solutions
more quickly than their in-house computational engines. Even if you
don't modify any of them to taste, the large number of labs means
that the course can vary according to research interests or educational
taste.
If you harbor a particular hostility to your students, feel free to
contact the authors. We can indicate which labs have proven especially
difficult in practice.
\section*{Any last words?}
After five years of development, this text and its source were released
in 2021 on a public platform for dissemination.
\subsection*{Regarding errata}
Mathematical lore relates that a professor once set out to write a
textbook free from error. A reviewer of the resulting text observed
drily that the author did ``rather well: the first error appears
on page 9.''
Our goals are more modest: we promise only that any errors the reader
finds will range from the merely typographical to the outright mendacious.
\begin{itemize}
\item For errors typographical, we ask the reader to contact the maintainers.
If one of the authors' publication record is any kind of indicator,
the typographical corrections will have typographical errors. \emph{Caveat
lector.}
\item The errors of mendacity have the merit of sounding better than the
truth, so in the spirit of the times we decided to include them.\footnote{At least one outright mendacity is disclaimed as such, and the rationale
for the mendacity is explained.} We leave it to the reader to sort the wheat from the chaff, though
we assure the dedicated reader that there is more wheat than chaff.\footnote{Unless that claim, too, is mendacity.}
\end{itemize}
The reader interested in historical development of this text may wish
to visit
\begin{center}
\texttt{\href{http://www.math.usm.edu/dont_panic/}{www.math.usm.edu/dont\_panic/}}
\par\end{center}
\subsection*{Is there a hardcopy?}
No. There used to be, but color textbooks are expensive, and you lose
the experience of the animations embedded in the text. If you'd like
a hardcopy, feel free to print one, preferably using a color printer
on high-quality paper.
\part{Lessons}
\chapter{Background}
\begin{quotation}
A thing they had never needed before became a necessity. (Narrator,
\cite{TheGodsMustBeCrazy})
\end{quotation}
To explore the world of mathematics, you can't just read about it;
you have to \emph{engage} it. Some people are gifted with enough confidence
and/or aptitude that they take to this on their own; some were lucky
enough to be brought up well, and from their youth are accustomed
to engaging the world of mathematics.
Most are less lucky, and while they may find the wider world of mathematics
intriguing, they struggle to make their way through new and unfamiliar
territory. This text aims to encourage you to explore the world of
higher mathematics with the help of a computer algebra system, relying
on a particular system named Sage. We will encourage you to experiment
with problems and form conjectures about their solutions. Sometimes
we will encourage you to use the experimentation to formulate an explanation
as to why the conjecture is, in fact, true.
But to use computers effectively, you need to learn how to program.
\section*{Is this just another programming textbook?}
No.
\subsection*{Can you be more specific?}
Yes.
\subsection*{{[}Grumble.{]} Please go into some detail.}
This text is about \emph{mathematics,} which itself is about\emph{
solving} \emph{problems.} That's important enough to highlight, so
that even the skimmers will notice it.
\begin{center}
\textbf{\emph{Mathematics is a tool for solving problems.}}
\par\end{center}
\noindent In particular, we want to introduce you to ideas and techniques
of higher mathematics through problems that are arguably approached
best with a computer, because
\begin{itemize}
\item they are long;
\item they are repetitive or tedious; and/or
\item they require experimentation.
\end{itemize}
Computers require instructions, and a group of instructions is called
a \emph{\href{https://en.wikipedia.org/wiki/Computer_program}{program}.}\footnote{If you are reading this as an electronic document, then from time
to time you will notice text in a different color. If you click on
it, you will find it links through the internet to additional information,
very little of which is due to the authors of this text and, as such,
is probably much more reliable and useful. We hope you follow these
links and familiarize yourself with that information \textemdash{}
that's why we included it! \textemdash{} but strictly speaking it
isn't necessary.} So we do study \emph{programming,} but in reference to a specific
goal: namely, solving problems in mathematics. That makes this text
different from ``programming'' textbooks, which study programming
in reference to a different goal: namely, solving problems in computer
science. Again, that distinction is important enough to highlight,
so that even the skimmers will notice it.
\begin{center}
\textbf{\emph{We study programming in order to solve math problems.}}
\par\end{center}
\subsection*{Why program? If I wanted to write programs I'd major in computer
science.}
To start with, some problems are too tough to do by hand, so you \emph{have}
to use a computer. The purpose of this text is to start you down this
path \emph{without} turning you into a computer science major. It
will not only introduce you to some tools in a computer algebra system
that help you compute, it will encourage you to take steps along the
path of becoming a mathematical pioneer. To solve the problems we
present, you will need to stop at a particular feature just outside
your neighborhood and acquaint yourself with it a little more than
you might in the absence of our encouragement. In some cases, we will
even lead you back over land you traveled already and ask you to re-examine
something a little more carefully. In short, and in repetition, this
text is about exploring the world of higher mathematics, with a computer's
help.
On the one hand, computers don't understand human languages. Humans
are intuitive and poetic, resorting to figurative and abstract language.
Computers understand none of that; \href{https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_and_Switching_Circuits}{they really understand one thing only}:
\textbf{on} and \textbf{off}. Everything your cell phone, laptop,
or desktop does involves a clever arrangement of switches by human
beings who are well-trained in the art of directing electric current
to the right place at the right time.
On the other hand, most humans don't understand the computer's language
of \textbf{on} and \textbf{off}. Reducing every problem to these two
symbols has been extremely effective, but it's uncomfortable to humans
(if only because it's so \emph{tedious!}).
Learning to program gives you control over the computer's circuitry,
and allows you to work at a level that is much more comfortable. Even
the experts typically work with more abstract interfaces that are
themselves converted to \textbf{on} and \textbf{off} signals in several
stages. Learning to program also gives you a deeper understanding
of computer technology, and an appreciation for the amount of work
that goes into building this magical world we live in, where you can
speak into a little box in your hand and be heard by someone half
a world away.
\subsection*{What kinds of programming languages are there?}
\label{page: interpreted v. compiled languages}\index{language!interpreted v.~compiled v.~bytecode}Without
getting into too much detail, there are three types of computer programming
languages available today:
\begin{itemize}
\item In an \href{https://en.wikipedia.org/wiki/Interpreted_language}{interpreted programming language},
the computer reads a file that contains commands in the language.
It translates each symbol, and executes some sequence of commands
based on that symbol. (Here, ``symbol'' can include words as well
as numbers and abstract characters.) It then proceeds to the next
symbol, eventually forgetting its translation of the previous one.
Examples of interpreted languages include \href{https://en.wikipedia.org/wiki/BASIC}{BASIC},
\href{http://www.python.org/}{Python}, and the ``shell'' languages
of command-line prompts.
\item In a \href{https://en.wikipedia.org/wiki/Compiled_language}{compiled programming language},
the computer reads a file that contains commands in the language.
It translates each symbol, but instead of executing any commands,
it records the translation into \textbf{on} and \textbf{off} signals
and stores them in a new file, usually called an \emph{executable.}
(We write ``usually'' because it sometimes produces a \emph{library}
instead, depending on the programmer's request.) Examples of compiled
languages include \href{https://en.wikipedia.org/wiki/Fortran}{Fortran},
\href{https://en.wikipedia.org/wiki/C_(programming_language)}{C}/\href{https://en.wikipedia.org/wiki/C\%2B\%2B}{C++},
and \href{https://golang.org/}{Go}.
\end{itemize}
Before describing the third type of language, let's mention some advantages
and disadvantages of each type. Interpreted languages are by nature
typically much, much slower than compiled languages, because the computer
must re-translate each symbol, regardless of how many times it has
translated it before. (This is something of an oversimplification,
but neither is it that far from the truth.) On the other hand, interpreted
languages are typically much more interactive and flexible than compiled
languages, to the point that many users never write an actual program
for them, but merely issue one command at a time.
Similarly, the nature of compiled languages means that the precise
\textbf{on} and \textbf{off} signals are tied to a particular architecture,
one reason programs compiled to run on a Windows device won't run
on Macintosh or Linux. C++ developers have to re-compile each program
for a different architecture, and for many programs this becomes quite
difficult, especially if the program relies heavily on Windows' particular
graphical interface. As a result, interpreted languages can be much
more ``portable,'' which means you can simply copy them onto another
machine. Python programs are especially famous for their portability.
It's arguable that Microsoft Corporation's success is due primarily
to its brilliant and ubiquitous BASIC interpreter for home computers
of the late 70s and early 80s; it lives on today as Visual BASIC.
\begin{itemize}
\item \href{https://en.wikipedia.org/wiki/Bytecode}{Bytecode languages}
seek to straddle the gap between the two. In this case the computer
reads a file that contains commands in the language, and translates
each symbol, but not into the \textbf{on} and \textbf{off} signals
native to the computer's architecture. Rather, it translates them
into signals designed for an abstract computer called a \emph{virtual
machine,} then stores them into an executable or library that will
only work on computers that contain programs that understand the virtual
machine's signals. Notable bytecode languages include \href{https://en.wikipedia.org/wiki/UCSD_Pascal}{Pascal},\footnote{In its original incarnations, Pascal was translated to a similar idea
called P-code, later into bytecode proper.} \href{https://en.wikipedia.org/wiki/Java_(programming_language)}{Java},
and the .NET languages' \href{https://en.wikipedia.org/wiki/Common_Language_Runtime}{Common Language Runtime}.\footnote{Many interpreted languages are now compiled ``incrementally.'' They
save each command's interpretation, and as they progress during execution,
check to see whether each new command has already been interpreted.}
\end{itemize}
Because the executables and libraries are not in the computer's own
signals, bytecode languages are technically a special kind of interpreted
language, and their reliance on a virtual machine means they are theoretically
slower than compiled languages. In practice, the penalty is usually
quite small, because the virtual machine's signals are designed to
be translated very easily into an actual computer's signals. Modern
techniques make them so efficient that some bytecode languages frequently
outperform many compiled languages. Reliance on the abstract virtual
machine means bytecode languages are highly portable; we wrote above
that the executables work ``only'' on computers that contain programs
that understand the virtual machine's signals, but that also means
they run on ``any'' computer with a program that understands the
virtual machine's signals. Java's popularity \textemdash{} it once
seemed impossible to find a webpage without a Java applet \textemdash{}
was due to its ``Write Once, Run Anywhere'' philosophy, which depended
on its virtual machine capabilities.
\subsection*{Which of these language types do we use in this text?}
All of them, in fact.
The primary programming language in Sage is \emph{Python,} which we
listed above as an interpreted language. Sage and Python are not quite
the same, though; Sage programs will not work in plain, vanilla Python,
and some Python features are different in Sage.
You can sometimes compile Sage programs using a program \href{http://www.cython.org/}{Cython};
we cover that near the end of the text. However, ``Cythonized''
Sage will not stand on its own; you have to run it inside a Sage environment.
As you will learn below, Sage is actually assembled from a large number
of separate parts. Some of them are written with Java, which means
you are using a bytecode language, though you won't actually write
any Java programs.
\section*{What is this Sage thing you keep yapping about?}
Sage is a free, open-source computer algebra system.
\subsection*{What is a \textquotedblleft computer algebra system\textquotedblright ?}
Traditionally, there have been three major kinds of large-scale mathematical
software packages:
\begin{itemize}
\item \emph{Numerical computing systems} aim for fast computation, relying
typically on ``floating point'' numbers. We won't go into the details
right now, but you can think of floating point as a kind of ``accurate
estimation,'' similar to the use of significant digits in the sciences.
The science behind numerical computing is typically the province of
\emph{numerical analysis}. Almost everyone in the developed world
has used a numerical computing system at some point by turning to
a calculator. Numerical software packages include \href{http://www.mathworks.com/products/matlab/}{MATLAB}
and \href{http://www.gnu.org/software/octave/}{Octave}.
\item \emph{Statistical software packages} are a special kind of numerical
computing system that focus on special tools proper to statistical
analysis. Examples include \href{http://www.sas.com/}{SAS} and \href{https://www.r-project.org}{the R project}.
\item \emph{Computer algebra systems} aim for \emph{exact} computation,
even if this comes at the expense of the speed one associates with
numerical systems. Rather than manipulate approximate values, computer
algebra systems manipulate symbols that represent exact values: they
don't view $\pi$ as a decimal number but as a symbol with the properties
mathematics associates to it, and they allow us to manipulate expressions
that involve variables. Because of this, the science behind computer
algebra systems is called \emph{symbolic computation,} \emph{computer
algebra,} or \emph{computational algebra}. A few of the more expensive
calculators use symbolic computation, but typically one works with
a software package like \href{http://maxima.sourceforge.net/}{Maxima},
\href{http://www.maplesoft.com/}{Maple}, or Sage.
\end{itemize}
Why would one sacrifice exactness for the approximate values of a
numerical system? The main reason is \emph{speed!} By sacrificing
a small amount of precision, a numerical system can easily work with
both large and small numbers, vectors, and matrices, all without too
much trouble; it is not uncommon to work with hundreds or even thousands
of variables in a system of equations.
For example, what happens if you add the fractions $\nicefrac{1}{2}$,
$\nicefrac{1}{3}$, $\nicefrac{1}{5}$, and $\nicefrac{1}{7}$? Each
of them requires only two digits to write (numerator and denominator),
but the exact sum, $\nicefrac{247}{210}$, requires six digits \textemdash{}
a 300\% increase in size! If you turn to floating point numbers with
at most 4-digits, the sum becomes instead
\[
0.5000+0.3333+0.2000+0.1429=1.176.
\]
The sum is no larger than the original numbers. True, it's a \emph{little}
bit wrong, but the error is less than $\nicefrac{1}{500}$; that's
\emph{much} more accurate than most day-to-day tasks need.
The rapid growth in size is one reason people generally dislike fractions;
no one likes to work with objects whose complexity grows quickly.
In this case, what's true about people is true about computers, too;
if you work with a problem that requires division of integers in Sage,
you will almost certainly encounter a massive slowdown as the fractions
become complicated and, therefore, more difficult for the computer
to handle.
In that case, why would anyone bother with symbolic computation and
exact values? For many problems, the inaccuracies of floating point
computation makes it absolutely unsuitable. This is especially true
when \emph{division} is an inescapable part of the problem.
For example, suppose the computer has to divide by the 4-digit floating
point number $0.0001$. The resulting quotient grows very large. Yet
it's entirely possible that $0.0001$ is the result of a floating-point
error, and the correct value is actually~0. As you surely know by
know, division by~0 is \textbf{\emph{bad}}. Had the computer known
the value was~0, it wouldn't have divided at all! Problems where
this can occur often are called ``ill-conditioned,'' and numerical
analysts spend a lot of time trying to avoid them.
In some cases, however, you can't, so you resort to exact values.
This is especially true as one moves into more abstract mathematical
fields. Some people think ``abstract'' mathematics is ``useless''
mathematics, but they are quite mistaken: this text will introduce
you to several abstract mathematical objects whose very exactness
makes possible the extremely accurate and extremely secure communication
you achieve on the internet whenever you check your bank account or
buy from an online vendor.
\subsection*{What's special about Sage?}
Sage was ``started'' by \href{http://www.math.washington.edu/People/fac_individ.php?mathid=wstein}{William Stein},
a number theorist. He was frustrated with several drawbacks of the
computer algebra systems available at the time:
\emph{Commercial systems,} like Maple, don't allow the user to view
the code, much less modify it. In the software world, these systems
are called ``proprietary'', ``closed'', or ``unfree'' (by some
people). \emph{``Open'' or ``free'' systems} also existed, and
as the product of cutting-edge research, they were often better at
a particular task than the commercial packages. However, these packages
\emph{only} excel at one particular field of mathematics:
\begin{itemize}
\item for Calculus, you'd likely use Maxima;
\item for linear algebra, you'd likely use \href{http://linalg.org/}{Linbox};
\item for group theory, you'd likely use \href{http://www.gap-system.org}{GAP};
\item for number theory, you'd likely use \href{http://pari.math.u-bordeaux.fr/}{Pari};
\item for commutative algebra, you'd likely use \href{http://cocoa.dima.unige.it}{CoCoA},
\href{http://www.math.columbia.edu/~bayer/Macaulay/}{Macaulay}, or
\href{http://www.singular.uni-kl.de/}{Singular};
\end{itemize}
and so forth. Worse still, suppose you needed to transfer the result
of one package to another: after performing some number theory with
Pari, for instance, you might want to analyze the results using group
theory, in which case GAP would be the tool of choice. But there was
no easy way to copy the results from Pari into GAP.
Sage, then, was organized to bind these brilliant tools together into
one, relatively easy package. Additional features were programmed
in Sage proper, and in some cases, Sage has been the leader at solving
some problems. As a bonus, Sage's developers have made it possible
to interact with many proprietary packages through Sage, so that if
Maple has the fastest tools to solve some problem, and you own a copy,
you can get it done through Maple, then manipulate the result through
Sage.
\subsection*{Why the concern with \textquotedblleft free\textquotedblright{} software?}
In the world of software, the term ``free'' has two senses:
\begin{description}
\item [{Free~as~in~beer}] You don't have to pay for it.
\item [{Free~as~in~speech}] The code is open and viewable, rather than
``censored.''
\end{description}
Software can be ``free as in beer'' but not ``free as in speech;''
that is, it costs nothing, but you can't view the source code. Examples
include the numerous ``free'' programs you can download for a computer
or mobile phone.
There are important reasons a researcher or even an engineer should
be able to view and/or modify the code in a mathematical software
package:
\begin{itemize}
\item Good scientific practice requires reproducibility and verifiability.
But a researcher can't verify the results of a mathematical computation
if she can't check the way it was computed.
\item Any software package of significant size will have some mistakes,
called \emph{bugs}. If two software packages produce a different answer,
a researcher can't decide which one is correct if he can't view the
code and evaluate the algorithms.
\item Almost all mathematical research builds on previous work. The same
is true about software packages, and researchers often need to extend
a package with new features in order to accomplish some task. This
can be much more difficult to do properly if the researcher can't
view the code, let alone modify it.
\end{itemize}
For example, suppose a mathematician claimed to have a proof that
there are infinitely many primes. Most mathematicians would want to
see the proof; that's one way we learn from each other. (In some cases,
the proof is much more interesting than the theorem.) Indeed, you
can find this proof in many, many textbooks, because the Hellenic
mathematician \href{http://en.wikipedia.org/wiki/Euclid}{Euclid of Alexandria}
recorded what is considered one of the most beautiful proofs of this
fact over two thousand years ago\textit{ \cite[Book IX, Proposition 20]{EuclidsElements}}:
\begin{center}
\fbox{\begin{minipage}[t]{0.8\columnwidth}%
\begin{thm*}
There are infinitely many prime numbers.
\end{thm*}
\begin{proof}
Consider any finite, nonempty set of primes, $P=\left\{ p_{1},\ldots,p_{n}\right\} $.
Let $q=p_{1}\cdots p_{n}+1$. Since $q\neq1$, at least one prime
divides it, but the remainder of dividing $q$ by any $p\in P$ is~1,
so none of $P$'s primes divides it. So there must be some prime number
not listed in $P$. But $P$ is an \emph{arbitrary,} finite set of
primes, which means that \emph{no} finite set of primes can list all
of them. In other words, there are infinitely many prime numbers.
\end{proof}
%
\end{minipage}}
\par\end{center}
\noindent By exposing the proof plainly, Euclid makes it easy to verify
the result. He also makes it easy to question the argument: you might
wonder, for instance, how Euclid knows that at least one prime divides
any positive integer that is not~1. (As a matter of fact, he proves
that earlier on.)
Compare this to another famous theorem attributed to \href{http://en.wikipedia.org/wiki/Pierre_de_Fermat}{Pierre de Fermat},
a French jurist who studied mathematics as a hobby \textit{\cite[p. 61, Observatio Domini Petri de Fermat]{DiophantusArithmeticaFermat}}:
\begin{center}
\fbox{\begin{minipage}[t]{0.8\columnwidth}%
\begin{thm*}
If $n>2$, the equation $a^{n}+b^{n}=c^{n}$ has no solution with
integers $a,b,c\geq1$.
\end{thm*}
\begin{proof}
I have found a truly wonderful proof of this fact. This margin's smallness
will not contain it.
\end{proof}
%
\end{minipage}}
\par\end{center}
\noindent These two sentences set off a search for a proof that lasted
more than three centuries; \href{http://en.wikipedia.org/wiki/Andrew_Wiles}{Andrew Wiles}
found a proof in 1994, and to date there are no other proofs. Most
people agree that Fermat did not, in fact, have a proof, but we shouldn't
think ill of him: he never actually \emph{told} anyone he had a proof;
he merely wrote this comment down in the margin of a book. His son
published a copy of the book after Fermat's death, and included the
notes Fermat wrote in the margin.
To stretch the analogy further, suppose we were to claim the following:
\begin{center}
\fbox{\begin{minipage}[t]{0.8\columnwidth}%
\begin{thm*}
The number
\[
2^{n}-1
\]
is prime for $n=2,3,5,7,13,17,19,31,67,127,257$.
\end{thm*}
\begin{proof}
Trade secret.
\end{proof}
%
\end{minipage}}
\par\end{center}
\noindent You would be right to doubt our claim, for at least two
reasons: there is no \emph{easy} to way to verify it, and in fact
it is wrong! Yet this claim was made by a well-respected mathematician
named \href{http://en.wikipedia.org/wiki/Marin_Mersenne}{Marin Mersenne}~\cite{MersenneCogitata},
offered without proof, and was for some time generally accepted. You
will meet this claim again in a lab later on.
\subsection*{What are some advantages of Sage?}
As mentioned before, Sage makes it easy to experiment with mathematical
objects that you will use increasingly more in classes after this
one. Later classes will probably not require Sage explicitly, but
if you never use Sage again after this class, that would be like going
through a Statistics class and doing all the work by hand:\footnote{At least one of the authors actually tried this when he was in college.
In fact, Statistics was the one class that broke his resistance to
using a calculator. The calculator's ability to perform exact computation
of fractions impressed him; until then, he had only seen calculators
perform arithmetic with fractions via floating point.} \emph{WHY?!?}
Another advantage to Sage is that you interact with it through a Python
interface; programming in Sage is, to some extent, indistinguishable
from programming in Python. This confers the following benefits:
\begin{itemize}
\item Recall that Python is one of the more widespread interpreted languages.
\begin{itemize}
\item \href{https://www.python.org/jobs/}{Many employers want Python experience.}
Learning Sage well helps you learn Python, and helps make you more
employable.
\item Many packages are available to enhance Python, and work well with
Sage. Indeed, many such packages are already packaged with Sage.
\item As mentioned earlier, you can often speed up a program by ``Cythonizing''
it.
\end{itemize}
\item Python is a modern language, offering many ways to express an elegant
solution to a problem. By learning Sage, you are learning \emph{good}
programming practices.
\end{itemize}
Keep in mind that Python and Sage aren't the same thing, nor is either
a subset of the other. Sage commands do not work in plain Python,
and some Python commands don't work the same way in Sage that they
would in Python.
\section*{How do I get going with Sage?}
Probably the easiest way is to visit \href{http://cocalc.com/}{the CoCalc server at cocalc.com},
register for a free account, start a project, and create a Sage worksheet.
We strongly urge the reader to pony up the dough for a membership,
which at the time of this writing costs \$7/month and gives access
to faster, more reliable servers. You can use it for free, but for
various reasons, the free servers sometimes reset on you. (If you
are part of a class, however, ask the instructor if the department
has ponied up for a class package; the discount is substantial.) The
drawback to this approach is that you have to pay to get good service.
The advantage is that you always have a reasonably up-to-date version
of Sage at your fingertips, and you don't have to worry about a hardware
crash that wipes out all your data, because it's stored on servers
that rely on multiple backups and fallback mechanisms.
Another way to use Sage is via an online server that is not a CoCalc
server. This requires you to know somebody who knows somebody who\ldots{}
knows somebody who runs a server you can use. Quite a few institutions
do this, including the one that employs the authors; in fact, our
department maintains at least two such servers at the time of this
writing. The drawback to this approach is that you depend on the server's
maintainer to keep the software up-to-date and the data backed up.
Indeed, one of our department's servers runs a version of Sage that
is years out of date.
The last way to use Sage is from a copy on your own machine. You can
download it from \href{http://www.sagemath.org/}{www.sagemath.org}
and install it on your computer. (Look for the link to ``Downloads''.)
\begin{itemize}
\item If your machine runs Linux, this is a relatively simple process, though
you may have to install some packages through your package manager.
(In the past, we have had to install a system called \keyboardpress{m4}.
We don't remember what it is.) Binaries are available for some Linux
distributions; Ubuntu is typically one of these, and Fedora has been
from time to time. For the rest, you'll likely need to download the
Sage source and compile it on your computer. The good news is that
this is usually quite painless, as long as you have already installed
the required packages, and these are listed in the directions. The
bad news is that installing from source takes quite a long time, so
prepare for some hurry-up-and-wait.
\item If your machine runs OSX, try downloading a binary for your architecture.
You can try compiling from source, as with Linux, but in that case,
hope that Apple hasn't recently ``upgraded'' Xcode, because you
need Xcode to install Sage, and every major release of Xcode typically
breaks Sage in some way.\footnote{Sage is by no means the only software package that suffers this consequence.}
\item If your machine runs Windows, you are in the unusual position of having
to suffer what Linux and OSX users typically suffer: Sage doesn't
work natively on Windows, so you have to use it through a virtual
machine. This can be a little tedious to set up, but once you get
the hang of it, it works fine. The correct way to do this has changed
several times over the years, so we are reluctant to give more precise
advice than this. The good news is that instructions on installing
and running Sage will be available at the website.
\end{itemize}
Once you have one of these methods up and running, you start using
it!
\section*{Worksheet or command-line?}
There are two typical ways to use Sage: from a browser, in what's
called a \emph{Sage worksheet,} or from the command line. If you have
installed Sage to your machine, you can do both; see the section on
Command-line Sage to see how to start a Sage worksheet from the command
line.
\subsection*{Sage worksheets}
If you have access to Sage via a web browser (either CoCalc or another
online server) you will likely prefer to work with a Sage worksheet.
We recommend our students to start with Sage in this fashion, because
the worksheet provides a more user-friendly environment: it is easy
to review and re-execute commands, to add text for organization and
narrative, and further to save your entire session, then later reload
the work and the output. You can't do any of that with the command
line.
When you start a worksheet, you should see one of these two screens:
\begin{center}
\begin{tabular}{|c|}
\hline
\includegraphics[width=0.8\columnwidth]{graphics/screenshots/StartingWorksheetModeOwnServer}\tabularnewline
Independent server\tabularnewline
\hline
\end{tabular}
\par\end{center}
\begin{center}
\begin{tabular}{|c|}
\hline
\includegraphics[width=0.8\columnwidth]{graphics/screenshots/StartingWorksheetModeCoCalc}\tabularnewline
CoCalc\tabularnewline
\hline
\end{tabular}
\par\end{center}
\noindent You can (and should) change the title.
\begin{itemize}
\item In the independent server, you can do that at the beginning with the
``Rename worksheet'' dialog you see in the screenshot. You can do
it later by clicking on the title (in the upper left, currently ``Untitled'')
and the same dialog will pop up.
\item In CoCalc, you can do that by clicking on the circled \keyboardpress{i}
in the upper left and choosing ``Rename\ldots ''. A new screen
will appear, prompting you to rename the file. Make sure you keep
the \keyboardpress{.sagews} added at the end.
\end{itemize}
There are other options you can monkey with, but for now we'd recommend
you move on to the next chapter, since most of those options are of
small importance for our purposes. The ones we do need we'll discuss
in due course.
\subsection*{Command-line Sage}
If you choose to run Sage from the command line, you need to open
a \emph{shell}, also called \emph{a command-line prompt}. You will
see some sort of prompt, which can vary quite a bit; whenever we mean
a shell prompt we'll simply put a blue greater-than symbol: \textcolor{blue}{\keyboardpress{\textcolor{blue}{>}}}.
At the prompt, type \keyboardpress{sage}, press \keyboardpress{Enter},
then wait for Sage to start up. This might take a few seconds, but
eventually you will see something to this effect:
\begin{sageinteraction}
\texttt{\textcolor{blue}{>}}\texttt{ sage}
\noindent\fbox{\begin{minipage}[t]{1\columnwidth - 2\fboxsep - 2\fboxrule}%
\texttt{SageMath Version 6.7, Release Date: 2015-05-17}
\texttt{Type \textquotedbl notebook()\textquotedbl{} for the browser-based
notebook interface.}
\texttt{Type \textquotedbl help()\textquotedbl{} for help.}%
\end{minipage}}
\texttt{\textcolor{blue}{sage:}}\texttt{ \_}
\end{sageinteraction}
\noindent The underscore (\keyboardpress{\_}) might actually look
like a little box on your system. Once you see that, you're in good
shape for the next chapter. If you \emph{don't} see it, or if you
see some sort of error, you need to talk with your instructor or tech
support and see what went wrong.
If you'd like to run a Sage worksheet in a browser, but don't want
to run CoCalc and don't have access to another server, type \keyboardpress{notebook()}
and press \keyboardpress{Enter}. You will see a lot of messages,
for instance:
\begin{sageinteraction}
\texttt{\textcolor{blue}{sage:}}\texttt{ notebook()}
\texttt{The notebook files are stored in: sage\_notebook.sagenb}
\noindent\fbox{\begin{minipage}[t]{1\columnwidth - 2\fboxsep - 2\fboxrule}%
\texttt{Open your web browser to http://localhost:8080}%
\end{minipage}}
\texttt{Executing twistd -{}-pidfile=\textquotedbl sage\_notebook.sagenb/sagenb.pid\textquotedbl{}
-ny \textquotedbl sage\_notebook.sagenb/twistedconf.tac\textquotedbl}
\texttt{/Applications/sage-6.7-untouched/local/lib/python2.7/site-packages/}
\texttt{Crypto/Util/number.py:57: PowmInsecureWarning: Not using mpz\_powm\_sec. You
should rebuild using libgmp >= 5 to avoid timing attack vulnerability.}
\texttt{\_warn(\textquotedbl Not using mpz\_powm\_sec. You should
rebuild using libgmp >= 5 to avoid timing attack vulnerability.\textquotedbl ,
PowmInsecureWarning)}
\texttt{2016-05-27 14:30:49+0300 {[}-{]} Log opened.}
\texttt{2016-05-27 14:30:49+0300 {[}-{]} twistd 14.0.2 (/Applications/sage-6.7-untouched/local/bin/python
2.7.8) starting up.}
\texttt{2016-05-27 14:30:49+0300 {[}-{]} reactor class: twisted.internet.selectreactor.SelectReactor.}
\texttt{2016-05-27 14:30:49+0300 {[}-{]} QuietSite starting on 8080
2016-05-27 14:30:49+0300 {[}-{]} Starting factory <\_\_builtin\_\_.QuietSite
instance at 0x1181bb638>}
\end{sageinteraction}
\noindent For the most part, you \emph{do not} need to worry about
those messages.\footnote{Well, maybe the security warnings about \keyboardpress{libgmp}, if
you see them. I should look into that.} You don't even have to follow the directions to open your web browser
to that site; on many machines, the browser will open the webpage
automatically. Besides, it will take a few seconds for things to get
started, so sit back and relax a few seconds. If your browser doesn't
open, Don't Panic! Open it yourself and see if the web address \emph{your}
Sage advises works. If it does, you're in good shape for the next
chapter.
If it doesn't,\index{PANIC@\textcolor{red}{PANIC"!}}
\begin{center}
\textcolor{red}{\LARGE{}PANIC!}{\LARGE\par}
\par\end{center}