Ce billet est initialement paru sur le blog DMI (Divertissements mathématiques mais (surtout) informatiques)
August Ferdinand Möbius était un mathématicien du 19e siècle, célèbre entre autres pour son ruban, le ruban de Möbius, qui a la particularité de n’avoir qu’une seule face.

On lui doit cependant d’autres «inventions», dont la fonction de Möbius. Cette fonction, notée μ(n) est une fonction de l’ensemble des entiers naturels non nuls dans l’ensemble {−1,0,1}. Sa valeur dépend de la décomposition en facteurs premiers de n.

Un nombre premier est un nombre qui a exactement 2 diviseurs, 1 et lui même. Les 50 premiers nombres premiers sont :

(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229)

Les nombres plus grands que 2 qui ne sont pas premiers sont dits composés.

Le théorème fondamental de l’arithmétique indique que chaque nombre peut s’écrire comme le produit de nombres premiers. Cette décomposition, dite décomposition en facteurs premiers, est de plus unique.

Par exemple, 24 se décompose en : 2 × 2 × 2 × 3

Autre exemple, 9438 se décompose en 2 × 3 × 11 × 11 × 13

C’est cette décomposition qui permet de calcul les valeurs de la fonction de Möbius μ.

Si un des facteurs premiers apparaît plus d’une fois dans la décomposition de n, alors μ(n)=0. Les nombres pour lesquels μ(n)=0 sont donc exactement les nombres divisibles par le carré d’un nombre premier.

Les autres nombres n, pour lesquels μ(n)=±1 sont donc ceux pour lesquels chaque facteur premier n’apparaît qu’une fois dans la décomposition.

Si le nombre de facteurs premiers apparaissant dans la décomposition de n est pair, alors μ(n)=1. Si au contraire il est impair, μ(n)=−1.

Voici les premières valeurs de la fonction mu :

Le nombre 1 est un peu à part. Sa décomposition ne contient finalement aucun nombre premier, puisque 1 n’est lui-même pas premier. On considère donc que μ(1)=1

Les fonctions suivantes, écrites en Python, permettent de calculer la valeur de μ pour un nombre n donné. Pour calculer rapidement la décomposition, on utilise un fichier contenant des nombres premiers (primes.txt contient tous les nombres premiers jusqu’à 999 983). La fonction genprimes est un générateur qui permet d’égrener cette liste.

with open('primes.txt','r') as f:
    _v=f.readlines()
_v=[int(i) for i in _v]

def genprimes():
    for v in _v:
        yield v

def decomposition(n):
    ''' Renvoie la décomposition en facteurs
    premiers de n
    '''
    primes=genprimes()
    dec=[]
    while n>1:
        v=0
        p=next(primes)
        while n%p == 0:
            n, v = n//p, v+1
        if v>0:
            dec.append((p, v))
    return dec

def mu(n):
    ''' Calcule la valeur de la fonction de
    mobius en n
    '''
    dec=decomposition(n)
    for f in dec:
        if f[1] > 1:
            return 0
    if len(dec) % 2 == 0:
        return 1
    return -1

Nous allons utiliser cette fonction pour représenter graphiquement la fonction de Möbius, «à la Ulam».

Stanislaw Ulam, un autre mathématicien, est l’inventeur de la spirale qui porte son nom, sur laquelle chaque nombre entier est donc disposé en spirale (le 1 est au centre). Dans la spirale d’Ulam, chaque case de la spirale est colorée de manière différente selon la nature du nombre qui l’occupe. Ulam coloriait les cases contenant les nombres premiers.

De notre côté, nous allons colorier la spirale en utilisant 3 couleurs :

Voici la « spirale de Möbius » obtenue pour les 100 premiers entiers :

Spirale de Möbius

Spirale de Möbius

En omettant les nombres à l’intérieur des cases nous pouvons tracer des spirales plus grandes.

Spirale représentant les valeurs de la fonction de Möbius pour les 10 000 premiers nombres entiers

Spirale représentant les valeurs de la fonction de Möbius pour les 10 000 premiers nombres entiers

Spirale représentant les valeurs de la fonction de Möbius pour les 160 000 premiers nombres entiers

Spirale représentant les valeurs de la fonction de Möbius pour les 160 000 premiers nombres entiers