Kanter’s Zeta Function – Part 1: An Introduction with Python

Hello Friends.

This is Part 1 of a 2-part post. I’m going to try to keep things fun and relatively brief. Not too much rigor (please acquaint yourself with the phrase “can be easily shown”), but with enough explanation for the layperson to hopefully figure out what I’m saying if he/she so chooses.

Today I will be introducing a function on the natural numbers (ie, positive integers). I call it my Zeta function. Obviously, if at any point I’m talking about something and I lose you, feel free to look up whatever concept/term you are unfamiliar with. Here we go. For any positive integer x, we will describe:

ζ(x) The number of Abelian Groups, unique up to isomorphism, with x elements.

Ok, so our goal is to come up with a definition of ζ(x). For any of you who don’t know, or cannot remember what an Abelian Group is, I’ll just copy and paste from wikipedia:

An abelian group is a set, A, together with an operation • that combines any two elements and b to form another element denoted a • b. The symbol • is a general placeholder for a concretely given operation. To qualify as an abelian group, the set and operation, (A, •), must satisfy five requirements known as the abelian group axioms:

Closure
For all ab in A, the result of the operation a • b is also in A.
Associativity
For all ab and c in A, the equation (a • b) • c = a • (b • c) holds.
Identity element
There exists an element e in A, such that for all elements a in A, the equation e • a = a • e = a holds.
Inverse element
For each a in A, there exists an element b in A such that a • b = b • a = e, where e is the identity element.
Commutativity
For all ab in Aa • b = b • a.

A group in which the group operation is not commutative is called a “non-abelian group” or “non-commutative group”.

So a Finite Abelian Group is just an Abelian Group with a finite number of elements. Got it? Great. Now, our goal is to define ζ(x) in a way that allows us to study the function, using python. Now, recall that according to the Fundamental Theorem of Finitely Generated Abelian Groups (also from wikipedia):

The primary decomposition formulation states that every finitely generated abelian group G is isomorphic to a direct sum of primary cyclic groups and infinite cyclic groups. A primary cyclic group is one whose order is a power of a prime. That is, every finitely generated abelian group is isomorphic to a group of the form:

\mathbb {Z} ^{n}\oplus \mathbb {Z} _{q_{1}}\oplus \cdots \oplus \mathbb {Z} _{q_{t}},

where the rank n ≥ 0, and the numbers q1, …, qt are powers of (not necessarily distinct) prime numbers. In particular, G is finite if and only if n = 0. The values of nq1, …, qt are (up to rearranging the indices) uniquely determined by G.

Right now would be a good time to remind you that for any positive integer n, the group ℤn is just modular arithmetic where n is the modulus. From this theorem, it can easily be shown that every non-trivial finite abelian group can be expressed in the form:

p1k1\oplus \!\, · · · \oplus \!\, ℤpnkn

where the pi are primes (not necessarily distinct), and the ki are positive integers.

Let’s consider abelian groups with pn elements, where p is any prime, and n is a positive integer. Well, clearly, every such group can be expressed in the form:

pk1\oplus \!\,· · · \oplus \!\,pkm

where k1 + . . . + km = n

to make these expressions unique, we need only to add the rule that:

k1 ≥ . . . ≥km

Ok. so we now have a way to uniquely express every finite abelian group with pn elements, and, by extension, a way to uniquely express every finite abelian group with x elements for any integer x. Clearly, all we would need in order to do this is the prime factorization of x. We are now going to define a function called psi.

ψ(n) The number of abelian groups, unique up to isomorphism, with pn elements for any prime p

Notice that ψ(n) = ζ(pn) for any prime p. Clearly also, if we get a prime factorization for any positive integer x, that is,

x = p1k1 · · · pmkm, where each pi is a distinct prime, and each ki is a positive integer,

then ζ(x) = ψ(k1) · · · ψ(km).

Ok, so it looks like the key to cracking zeta is to crack psi. In order to do that, we’re going to think about psi visually.

Let’s use columns of red dots as a way to visually represent any abelian group with pn for any prime p. Ready? Let’s use, as an example:
p3 \oplus \!\,p2 and represent it like this:

z3xz2

Get it? Given ℤpk1 \oplus \!\, . . .  \oplus \!\, ℤpkn , we can represent this group with a sequence of n columns of red dots, where, from left to right, the j-th column is kj dots tall. And remember, we can guarantee that these visual representations are unique up to isomorphism by saying that kj ≥ kj+1 for all j

We are going to introduce here yet another function. I call it gamma. Here’s how it works:

γk(n) = The number of abelian groups with pn elements for any prime p of which the largest cyclic subgroup is of order pk.

In other words γk(n) = the number of ways to combine n dots into columns as described above, where the tallest (leftmost) column contains k dots. If you have not figured it out by now, let me tell you right now that:

This can be a lot to think about in terms of equations, so let’s use the visualizations from earlier. Let’s look at visualizations of the abelian groups with p5 elements:

psi5

We can see from the above example that ψ(5) = 7 and we can see γk(5) for each k. Rather than give a long-winded explanation of how to calculate gamma, I am just going to introduce the basic python code to calculate gamma and psi, and then if you look at it long enough, I think you will be able to reverse engineer my thought process. Ready?

def gamma(k,n):
   if k==1:
      return 1
   elif k==n:
      return 1
   else:
      y = 0
      for x in range(1,min(n-k+1,k+1)):
         y+=gamma(x,n-k)
      return y

def psi(n):
   y=0
   for k in range(1,n+1):
      y+=gamma(k,n)
   return y

(Note how gamma is defined recursively here. This can really slow things down if we’re calculating psi for large enough numbers, or if we’re repeatedly calculating psi on large data sets, so don’t get carried away! Try to keep things under 100 for now. You really won’t need anything higher than that. In my next post, we will modify the code to make it run faster, but for now let’s just keep things simple readable).

Now we can calculate gamma and psi for any numbers we might need. Cool! We’re almost there! Recall that:

if we get a prime factorization for any positive integer x, that is,

x = p1k1 · · · pmkm, where each pi is a distinct prime, and each ki is a positive integer,

then ζ(x) = ψ(k1) · · · ψ(km).

Therefore, with psi defined, all we need now in order to calculate zeta for any x is the prime factorization for x. And in order to get the prime factorization for x, we’ll need to generate primes. Really, we could always just get a list of primes off the internet, but what’s the fun in that? Here’s some (sloppy) code I wrote to generate primes and get prime factorizations:

def primegenerator(ceil):
    t=6
    primes=[2,3,5]
    while t<=ceil:
        z=0
        a=0
        k=primes[a]
        y=(t**(0.5)+1)
        h=len(primes)-1
        while k < y:
            if t%primes[a] == 0:
                z+=1
                k=y+1
            else:
                a+=1
                k=primes[a]
        if z==0:
            primes.append(t)
        t+=1
    return primes
def primefactorizer(x):
    guesses = primegenerator(x**.5)
    primedict = {}
    def factor(p, n):
        if not(p in primedict):
            primedict[p]=1
        else:
            primedict[p]+=1
    for p in guesses:
        while num % p == 0:
            factor(p, x)
            x = int(x/p)
        if x == 1:
            return primedict
    if x != 1:
        primedict[x] = 1
    return primedict

(Notice that primefactorizer calls primegenerator. Notice also that primegenerator returns a list of primes, and that primefactorizer returns a dictionary where the keys are the pi and the values are the ki from the prime factorization)

And with that, we can define Kanter’s Zeta Function:

def zeta(x):
    b = 1
    for a in primefactorizer(x):
        b*=psi(primefactorizer(x)[a])
    return b

(I always thought it would be cool to name something after myself. Children are expensive and they only last, what, 80 years? Functions are free and they last forever.)

There you have it. We can now easily calculate the number of Abelian Groups with x elements for any positive integer x. Wow! That’s SoOoOoOo COOOOOL! And with that we conclude Part 1.

In Part 2, we will modify much of the code written here in order to make it run more efficiently, so that we can study the behavior of Kanter’s Zeta Function on a somewhat large data set. In particular, the question that drives Part 2 will be the following: If we let {ak} be an infinite sequence, where ak = zeta(k), and let:

be the k-th partial sum of the series

is this series Cesàro Summable?

Part 2 coming soon.

One thought on “Kanter’s Zeta Function – Part 1: An Introduction with Python

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s