[Edu-sig] Hitting two targets: OO + group theory (pedagogy)
Kirby Urner
urner@alumni.princeton.edu
Fri, 02 Mar 2001 18:07:25 -0800
============== OREGON CURRICULUM NETWORK =====================
RE: HITTING TWO TARGETS: OO + MATH TOPIC
OO + POLYHEDRA
In earlier writings, I've discussed how object-oriented (OO)
syntax might be melded with math notations with regard to
polyhedra.[see links] A Polyhedron superclass, subclassed
as Tetrahedron, Octahedron etc., would demonstrate the concepts
of class hierarchy and instantiated selves, or objects.
Many intro-to-OO books use already flatlander shapes
(superclass: shape; subclasses: triangle, circle, square...).
However the Polyhedron case is mathematically more interesting
and takes better advantage of the computer's graphical display
capabilities. Rotation, translation and scaling may be
implemented using matrices, or we might swap in quaternions
to accomplish rotation, or we might develop use some other
Clifford Algebra ala Hestenes et al.
OO + GROUP THEORY
More recently, I've been looking to group theory as another
paradigm case for hitting two targets with one stone: OO
concepts and number-theoretic math concepts. Each set of
concepts helps to reinforce the other, thereby bootstrapping
students into a synergetic mindset which sets the stage for
elaboration both in programming and in abstract mathematics.
Whereas this might at first sound like a college level
approach, my contention is that newcomers to programming will
leap-frog those who cut their teeth in the hay day of
procedural programming -- which doesn't mean the procedural
approach has gone out of style, only that it's no longer
relevant to consider the object-oriented as "advanced", with
mastery of earlier forms a prerequisite. Functional programming
methods will also make their debut earlier in a student's
career.
And group theory has always been accessible at a variety of
levels. It makes sense to start phasing in some of these
concepts early, so that later plantings of these ideas find
fertile ground.
PYTHON AS INTRO LANGUAGE
The computer language of choice in these explorations is
Python. We want a language which is interactive at the command
line, like Logo, such that programmed methods may be accessed
and combined on the fly, with the screen itself serving as a
principal site for i/o. Whereas we'll want the option to read
in text files for processing, there should be no demand on
students to compile standalone executables which must either
support their own GUI for interactivity, or rely on command
line arguments pointing to files containing the raw data of
interest.
ISETL, DrScheme, APL and others share these positive features
with Python and there's no stipulation here that only Python is
the appropriate vehicle for these kinds of activities (given
the OO focus, some of these others do not lend themselves to
hitting our double-target) -- only that this author has found
the Python environment highly congenial for this kind of
undertaking.
Let's define our sandbox to be groups of relative primes less
than a particular prime modulus n. These are groups under
multiplication, where a*b is defined as (a*b) mod n. In
Python, the mod operator is %, such that a%b returns the
remainder a (mod b).
SYNTAX BASICS
The primitive built-in function pow() takes a mininum of two
arguments a,b such that pow(a,b) = a^b (or a**b in Python,
as exponentiation is signified with a double-asterisk). The
optional 3rd argument provides a modulus, such that pow(a,b,n)
= (a**b) mod n. This 3-argument form of pow() is internally
optimized such that the modulus is used to reduce the product
as powering proceeds -- far more efficient than applying the
syntax (a**b)%n, which can take indefinitely longer to complete
for large numbers.
Where object-oriented syntax shines in this application is
when we go to define multiplication. We're able to override
the meaning of * (multiplication operator) in such a way
that operator.mul will likewise behave consistently, i.e. will
respect the definition we provide for multiplication. This
is done be defining __mul__ in the class definition. Similar
overriding is done with respect to ** and pow(), by defining
__pow__, and for relational operators <, >, and ==, by
defining __lt__, __gt__, and __eq__ respectively.
I won't go into a full-blown dissection of source code here,
but rather will conclude with an interactive command line
session which gives the flavor of the final result. In class,
or over the web (if a distance learning opportunity), students
would be boning up on Python and some of the basics of group
theory via supplementary materials. Some of the preliminary
prototypical writing is available in draft form on math-learn,
an egroup focussed on K-12 math education, with emphasis on the
middle school years. [see links below]
Further forays into group theory + Python may be found in the
'For further reading' section of my intro page on cryptography.
COMMAND LINE INTERFACE (CLI)
Here's from the Python command line:
>>> from groups import *
>>> residues17 = factory(17) # make objects using coprimes of 17
>>> residues17 # display as list of integers
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
>>> table(residues17) # generate a multiplication table
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
----------------------------------------------------
1| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2| 2 4 6 8 10 12 14 16 1 3 5 7 9 11 13 15
3| 3 6 9 12 15 1 4 7 10 13 16 2 5 8 11 14
4| 4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13
5| 5 10 15 3 8 13 1 6 11 16 4 9 14 2 7 12
6| 6 12 1 7 13 2 8 14 3 9 15 4 10 16 5 11
7| 7 14 4 11 1 8 15 5 12 2 9 16 6 13 3 10
8| 8 16 7 15 6 14 5 13 4 12 3 11 2 10 1 9
9| 9 1 10 2 11 3 12 4 13 5 14 6 15 7 16 8
10| 10 3 13 6 16 9 2 12 5 15 8 1 11 4 14 7
11| 11 5 16 10 4 15 9 3 14 8 2 13 7 1 12 6
12| 12 7 2 14 9 4 16 11 6 1 13 8 3 15 10 5
13| 13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4
14| 14 11 8 5 2 16 13 10 7 4 1 15 12 9 6 3
15| 15 13 11 9 7 5 3 1 16 14 12 10 8 6 4 2
16| 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
>>> a = residues17[7] # select a = specific object
>>> a
8
>>> a.inv() # compute a's inverse
15
>>> a*a.inv() # a * a^-1 = 1
1
>>> powers(residues17) # compute g to successive powers
1 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2 = [1, 2, 4, 8, 16, 15, 13, 9, 1, 2, 4, 8, 16, 15, 13, 9]
3 = [1, 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6]
4 = [1, 4, 16, 13, 1, 4, 16, 13, 1, 4, 16, 13, 1, 4, 16, 13]
5 = [1, 5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3, 15, 7]
6 = [1, 6, 2, 12, 4, 7, 8, 14, 16, 11, 15, 5, 13, 10, 9, 3]
7 = [1, 7, 15, 3, 4, 11, 9, 12, 16, 10, 2, 14, 13, 6, 8, 5]
8 = [1, 8, 13, 2, 16, 9, 4, 15, 1, 8, 13, 2, 16, 9, 4, 15]
9 = [1, 9, 13, 15, 16, 8, 4, 2, 1, 9, 13, 15, 16, 8, 4, 2]
10 = [1, 10, 15, 14, 4, 6, 9, 5, 16, 7, 2, 3, 13, 11, 8, 12]
11 = [1, 11, 2, 5, 4, 10, 8, 3, 16, 6, 15, 12, 13, 7, 9, 14]
12 = [1, 12, 8, 11, 13, 3, 2, 7, 16, 5, 9, 6, 4, 14, 15, 10]
13 = [1, 13, 16, 4, 1, 13, 16, 4, 1, 13, 16, 4, 1, 13, 16, 4]
14 = [1, 14, 9, 7, 13, 12, 15, 6, 16, 3, 8, 10, 4, 5, 2, 11]
15 = [1, 15, 4, 9, 16, 2, 13, 8, 1, 15, 4, 9, 16, 2, 13, 8]
16 = [1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16]
>>> b = residues17[12] # pick a g the period < totient
>>> b
13
>>> sg = subgroup(b) # generate the subgroup using b
>>> sg
[1, 13, 16, 4]
>>> table(sg) # generate the multiplication table
1 4 13 16
----------------
1| 1 4 13 16
4| 4 16 1 13
13| 13 1 16 4
16| 16 13 4 1
The source code I'm using is here:
http://www.inetarena.com/~pdx4d/ocn/python/groups_draft1.html
Links:
OO + Polyhedron: http://www.inetarena.com/~pdx4d/ocn/oop.html
also: http://www.inetarena.com/~pdx4d/ocn/trends2000.html
See bottom of http://www.inetarena.com/~pdx4d/ocn/overcome.html
for links to the math-learn postings (these were rough drafts --
a better version for the web is in the works)
Also see: http://www.inetarena.com/~pdx4d/ocn/clubhouse.html
============== OREGON CURRICULUM NETWORK =====================
By Kirby Urner, 4D Solutions, Portland, Oregon, USA