Hitting two targets: OO + group theory (pedagogy)

Kirby Urner urner at alumni.princeton.edu
Sat Mar 3 03:07:16 CET 2001


============== 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  





More information about the Python-list mailing list