Möbius Function

The code used on this page is availible here.

I was kindly sent some unpublished code (related to Möbius function) by Franz Lehner with permission to merge this with my own poset related code described here.

These are my notes related to the code written by Franz.

The Möbius function can be applied to any type that factorises

As an example take the factors of 12.

An arrow means 'has factor'.

I have drawn two arrows from 4 to 2 just to emphasise that 4 is 2 squared, but of course a poset has, at most, one arrow between nodes.

factorisation of 12

So here is the code to generate a poset for this:

(1) -> FP := FinitePoset(NNI)

   (1)  FinitePoset(NonNegativeInteger)
                                                                   Type: Type
(2) -> carrier:List(NNI) := [1,2,3,4,6,12]

   (2)  [1,2,3,4,6,12]
                                               Type: List(NonNegativeInteger)
(3) -> (x:NNI,y:NNI):Boolean +-> ((x rem y) < 1)

   Function declaration isaFactor : (NonNegativeInteger,
      NonNegativeInteger) -> Boolean has been added to workspace.
                                                                   Type: Void
(4) -> pset1  := finitePoset(carrier,isaFactor)$FP
 
   Compiling function isaFactor with type (NonNegativeInteger,
      NonNegativeInteger) -> Boolean 

        +true   true   true   true   true   true+
        |                                       |
        |false  true   false  true   true   true|
        |                                       |
        |false  false  true   false  true   true|
   (4)  |                                       |
        |false  false  false  true   false  true|
        |                                       |
        |false  false  false  false  true   true|
        |                                       |
        +false  false  false  false  false  true+
                                        Type: FinitePoset(NonNegativeInteger)

Incidence Algebra

At the moment my (Martin Baker) poset code uses an adjacency matrix for the Rep of a poset (with entries being boolean values - so an adjacency array). See FinitePoset code here.

For the Incidence Algebra the entries can be any ring such as integer. For Zeta function the values are limited to 0 and 1 which can be easily mapped to false and true.

Franz Lehner originally used the name IncidenceMatrix for this. I changed the name because it tends to be used for matrix where: rows are vertices and columns are edges as described here. So I changed the name IncidenceMatrix to IncidenceAlgebra.

An incidence algebra is an algebra over a field with convolution as its product. This can be defined in terms of a finite poset as follows:

If P is a finite poset then the incidence algebra is:

I(P) = { α : P × P->ℜ| α(x,y) = 0 if not x ≤ y}

This has the following operations:

So addition and scalar multipication are the same as the axioms for vector algebra and convolution is similar to matrix product.

Zeta Function

An entry of 1 means relation is true and 0 means it is not.

ζ(x,y) = { 0 if not x ≤ y }
1 if x ≤ y

The zeta function produces a matrix [multipication table with only 0 and 1]

(5) -> z := zetaMatrix(pset1)

         +1  1  1  1  1  1+
         |                |
         |0  1  0  1  1  1|
         |                |
         |0  0  1  0  1  1|
   (5)  [|                |,[1,2,3,4,6,12]]
         |0  0  0  1  0  1|
         |                |
         |0  0  0  0  1  1|
         |                |
         +0  0  0  0  0  1+
                           Type: IncidenceAlgebra(Integer,NonNegativeInteger)

Now try generating zeta matrix again but this time we put carrier set in a different order:

(6) -> jumble:List(NNI) := [12,2,3,1,6,4]
 

   (6)  [12,2,3,1,6,4]
                                               Type: List(NonNegativeInteger)
(7) -> pset2  := finitePoset(jumble,isaFactor)$FP
 

        +true  false  false  false  false  false+
        |                                       |
        |true  true   false  false  true   true |
        |                                       |
        |true  false  true   false  true   false|
   (7)  |                                       |
        |true  true   true   true   true   true |
        |                                       |
        |true  false  false  false  true   false|
        |                                       |
        +true  false  false  false  false  true +
                                        Type: FinitePoset(NonNegativeInteger)
(8) -> zetaMatrix(pset2)
 

         +1  1  1  1  1  1+
         |                |
         |0  1  0  1  0  1|
         |                |
         |0  0  1  1  1  1|
   (8)  [|                |,[1,3,2,6,4,12]]
         |0  0  0  1  0  1|
         |                |
         |0  0  0  0  1  1|
         |                |
         +0  0  0  0  0  1+
                           Type: IncidenceAlgebra(Integer,NonNegativeInteger)
We can see that our carrier set has been reordered. It is not exactly in the same order as before, 2,3 have been reversed and 4,6 have been reversed. However both of these are compatable with the topological ordering because we could take either the left or the right branch on the diagram first. graph

Möbius Function

As explained on Wikipedia here, the value of the Möbius function is −1, 0 or 1 depending on the factorization of n into prime factors:

  • Möbius(n) = 1 if n is a square-free positive integer with an even number of prime factors.
  • Möbius(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
  • Möbius(n) = 0 if n has a squared prime factor.

The first few values are given in the table here:

So, how does this relate to the matrix?

1 1
2 -1
3 -1
4 0
5 -1
6 1
7 -1
8 0
9 0
10 1
11 -1
12 0
moebius function

μ = ζ-1

The Möbius function is the inverse of the zeta function.

This gives the axiom:

δ(x,y) = (μ * ζ)(x,y) = Σz∈(x,y)μ(x,z) ζ(z,y)= Σz∈(x,y)μ(x,z)

μ(y) = { 1 if y = 0 }
z<yμ(z) if y < 0

Now generate Möbius matrix:

(9) -> m := moebius(pset1)
 

         +1  - 1  - 1   0    1    0 +
         |                          |
         |0   1    0   - 1  - 1   1 |
         |                          |
         |0   0    1    0   - 1   0 |
   (9)  [|                          |,[1,2,3,4,6,12]]
         |0   0    0    1    0   - 1|
         |                          |
         |0   0    0    0    1   - 1|
         |                          |
         +0   0    0    0    0    1 +
                           Type: IncidenceAlgebra(Integer,NonNegativeInteger)
(10) -> z*m
 

          +1  0  0  0  0  0+
          |                |
          |0  1  0  0  0  0|
          |                |
          |0  0  1  0  0  0|
   (10)  [|                |,[1,2,3,4,6,12]]
          |0  0  0  1  0  0|
          |                |
          |0  0  0  0  1  0|
          |                |
          +0  0  0  0  0  1+
                           Type: IncidenceAlgebra(Integer,NonNegativeInteger)

As we can see in (line 10) the zeta multipied by the Möbius matrix produces the unit (delta) matrix.

Cover Matrix

Returns all elements covered by x arithmetics

The covering relation is determined as follows.

Since the possible covers of an element come later in the list, it suffices to let y run over the rest of the list. Moreover, any y ≥ x is a cover unless some predecessor lies in between.

Now generate cover matrix:

(11) -> coverMatrix(pset1)
 

          +0  1  1  0  0  0+
          |                |
          |0  0  0  1  1  0|
          |                |
          |0  0  0  0  1  0|
   (11)  [|                |,[1,2,3,4,6,12]]
          |0  0  0  0  0  1|
          |                |
          |0  0  0  0  0  1|
          |                |
          +0  0  0  0  0  0+
                           Type: IncidenceAlgebra(Integer,NonNegativeInteger)

metadata block
see also:
Correspondence about this page

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2023 Martin John Baker - All rights reserved - privacy policy.