Choux romanesco, Vache qui rit et intégrales curvilignes

On a Conjecture about Partitions

De combien de façons différentes peut-on écrire un nombre sous la forme d'une somme ? Prenons par exemple le nombre 4, on a les partitions suivantes :

4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1

On a alors 5 partitions différentes de l'entier 4. On écrit p(n) le nombre de partitions de l'entier n. Les premières valeurs sont les suivantes :

Pfff
p(1)=1, p(2)=2, p(3)=3 p(4)=5, p(5)=7, p(6)=11

On a ensuite p(7)=15, p(8)=22, p(9)=30, p(10)=42 etc.

On se retrouve donc avec une liste de nombres, les nombres-partitions : 1, 2, 3, 5, 7, 11, 15, 22...

 

Face à une telle suite de nombres, le mathématicien se pose systématiquement les mêmes questions :
- Quelle est sa série génératrice ? (la série génératrice d'une suite étant un est la fonction f(x)=u0+u1.x+u2.x2+u3.x3... ) Les fonctions génératrices sont merveilleuses pour les informaticiens désireux de faire des calculs toujours plus grand, et permettent de conjecturer et/ou démontrer des propriétés sur la suites.
- Où sont les nombres premiers ? On sait jamais, des fois que ça aide à casser l'hypothèse de Riemann ou à trouver de grands nombres premiers !...
- Où sont les nombres pairs ? et les impairs ? Le genre de questions réflexes qui ne peuvent qu'aboutir à des théorèmes qui vont aider ceux qui s'intéressent à la deuxième question.

...

Pour la première question, c'est Euler qui s'en est chargé, en démontrant la jolie formule suivante :

formule_partit

...

Pour la deuxième question, il se trouve que la suite possède son lot de nombres premiers : 2, 3, 5, 7, 11, 101, 17977, 10619863, 6620830889, 80630964769...

Le plus grand que l'on connaisse, c'est p(15118525), qui compte 4324 décimales (ce qui est peu par rapport aux 13 millions du plus grand connu). Y en a-t-il une infinité ? Impossible aujourd'hui de le savoir, mais la recherche avance.

...

Pour la troisième question, on en sait déjà un peu plus, depuis 1959 : Kolberg a démontré qu'il y a une infinité de nombres-partitions pairs et de nombres-partitions impairs. A vrai dire, on s'en doutait déjà pas mal !

Mais le plus important, c'est le théorème suivant :
Il existe C>0 tels que le nombre de p(n) pairs pour n<N est plus grand que ln(N)C. En écrivant ça plus mathématiquement :

formule_NS

Cette propriété est également vraie en remplaçant "pair" par "impair", et ce théorème est appelé "Théorème de Nicolas-Sárközy". Ce nom vient tout simplement du mathématicien français Jean-Louis Nicolas et du mathématicien hongrois András Sárközy qui ont conjointement signé la démonstration en 1995 !

Reste une question à résoudre : a-t-on environ autant de nombres-partitions pairs que d'impairs ? Les tests sont concluants (sur les 2000 premiers, 1012 sont impairs) cependant, la conjecture de Nicolas-Sárközy est ouverte !

canard
Brève du canard enchainé (quelqu'un a la date ?)

(Pour dire la vérité, cette conjecture porte plutôt le nom de "conjecture de Parkin et Shanks". Le nom "conjecture de Nicolas-Sarkozy" est l'œuvre du mathématicien Tunisien Ben Saïd, qui, faisant suite aux travaux du trio Nicolas-Sarkzy-Ruzsa, a intitulé son article On a Conjecture of Nicolas–Sárközy about Partitions)

Posté par El Jj à 23:57 - Commentaires [8] - Permalien [#]
Tags : ,

Commentaires sur On a Conjecture about Partitions

    Quelques coquilles...

    Bon, il y avait bien le Théorème de Napoléon, alors pourquoi pas la Conjecture de Ncolas-Sárközy?

    --

    Les coquilles:
    Dans les partitions de 6 (dans le tableau), il y a un 3+2+1 en trop, que devrait remplacer 3+3,

    dans la liste des valeurs sous le tableau, les valeurs 15,22,30,42 sont toutes attribuées à p(7).

    Posté par Robyn Slinger, 15 juin 2009 à 08:04 | | Répondre
  • (Ncolas = Nicolas)

    Posté par Robyn Slinger, 15 juin 2009 à 08:05 | | Répondre
  • Un algorithme ?

    Article sympa, sauf le nom de la conjecture ^^

    Je voudrais savoir si il existe un algorithme permettant de générer les partitions d'addition d'un nombre.

    Je veux dire une fonction qui renvoie {1,1,1},{2,1} et {3} pour le chiffre 3.

    Posté par Freedog, 15 juin 2009 à 09:31 | | Répondre
  • Algorithme ?

    @ Freedog : cela ne doit pas être trop compliqué à faire récursivement : pour calculer les partitions au rang n, il suffit de connaitre les partitions au rang n-1 et d'ajouter 1 à chacune; puis pour chaque partition de p{n-1}, ajouter 1 à chaque nombre, et éliminer les doublons au fur et à mesure .
    Allez, j'ai programmé vite fait ça en python :

    import copy
    def partition(n):
    list=[]
    if (n==1):
    list.append([1])
    return list
    list.append([n])
    list_previous=partition(n-1)
    for l in list_previous:
    list_increment=copy.deepcopy(l)
    list_increment.append(1)
    list_increment.sort()
    if not list_increment in list:
    list.append(list_increment)
    for i in xrange(len(l)):
    list_addition=copy.deepcopy(l)
    list_addition[i]=list_addition[i]+1
    list_addition.sort()
    if not list_addition in list:
    list.append(list_addition)


    return list

    l=partition(6)
    print l
    print len(l)

    cela renvoie dans ce cas :

    [[6], [1, 5], [1, 1, 4], [2, 4], [1, 1, 1, 3], [1, 2, 3], [3, 3], [1, 1, 1, 1, 2], [1, 1, 2, 2], [2, 2, 2], [1, 1, 1, 1, 1, 1]]
    11

    Posté par Tom Roud, 15 juin 2009 à 14:46 | | Répondre
  • Rhaaaa

    Le commentaire a complètement viré l'indentation cruciale en python sur l'algorithme que je donne plus haut !!!

    Posté par Tom Roud, 15 juin 2009 à 14:47 | | Répondre
  • Code

    Je l'ai mis sur mon site :
    http://tomroud.com/2009/06/15/procrastination-pythonesque/

    Posté par Tom Roud, 15 juin 2009 à 15:10 | | Répondre
  • Robyn Slinger > Pour une fois, j'ai une excuse : j'ai du retaper 3 fois l'article à cause de mon ordinateur un brin capricieux par temps chaud !

    Freedog > Pas mieux que la solution de Tom Roud ! Sinon, pour augmenter la vitesse de calcul, il existe l'algorithme de Zoghbi et Stojmenovic (http://wfr.tcl.tk/1504).

    Posté par El Jj, 15 juin 2009 à 15:58 | | Répondre
  • Merci

    Merci, je songeais à faire un truc avec des combinaisons. Mais ce que tu proposes à l'air mieux, en plus en python c'est pratique à tester.

    Félicitations et encore merci !

    Posté par Freedog, 15 juin 2009 à 16:50 | | Répondre
Nouveau commentaire
Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.