Problème de Znám
En théorie des nombres, le problème de Znám pose la question de déterminer les ensembles finis d'entiers strictement positifs ayant la propriété que tout élément de l'ensemble est un diviseur propre du produit des autres éléments de l'ensemble, plus 1. Le problème de Znám doit son nom au mathématicien slovaque Štefan Znám (1936–1993), qui le suggère en 1972, bien que d'autres mathématiciens envisagent des problèmes similaires à la même époque.
Les termes initiaux de la suite de Sylvester résolvent presque ce problème, sauf que le dernier terme choisi est égal à un plus le produit des autres, plutôt que d'être un véritable diviseur. Sun (1983) montre qu’il existe au moins une solution au (bon) problème de Znám pour tout . La solution de Sun est basée sur une récurrence similaire à celle de la suite de Sylvester, mais avec un ensemble de valeurs initiales différent.
Le problème du Znám est étroitement lié aux fractions égyptiennes. On sait qu’il n’existe qu’un nombre fini de solutions pour tout problème fixe . On ne sait pas s'il existe des solutions au problème de Znám en utilisant uniquement des nombres impairs, et plusieurs autres questions restent ouvertes.
Énoncé du problème
[modifier | modifier le code]Le problème de Znám pose la question de déterminer les ensembles finis d'entiers strictement positifs ayant la propriété que tout élément de l'ensemble est un diviseur propre du produit des autres éléments de l'ensemble, plus 1. En d'autres termes, étant donné , on demande quels ensembles d'entiers strictement positifs :sont tels que, pour tout , divise, sans lui être égal, le nombre :Un problème étroitement lié concerne les ensembles d'entiers pour lesquels tout entier de l'ensemble est un diviseur, mais pas nécessairement un diviseur propre, du produit des autres entiers de l'ensemble, plus 1. Ce problème ne semble pas avoir été nommé dans la littérature et sera appelé problème de Znám impropre. Toute solution au problème de Znám est également une solution au problème de Znám impropre, mais la réciproque n'est pas vraie.
Historique
[modifier | modifier le code]Le problème de Znám doit son nom au mathématicien slovaque Štefan Znám, qui le suggère en 1972. Barbeau (1971) a posé le problème impropre de Znám pour , et Mordell (1973), indépendamment de Znám, trouve toutes les solutions au problème impropre pour . Skula (1975) montre que le problème de Znám est insoluble pour , et crédite J. Janák d'avoir trouvé la solution pour [1].
Exemples
[modifier | modifier le code]La suite de Sylvester est une suite entière dont chaque terme est le produit des termes précédents plus 1. Les premiers termes de la suite sont 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 suite A000058 de l'OEIS.Les ensembles formés des premiers termes de la suite (tel que ) fournissent des solutions au problème de Znám impropre, mais pas au problème de Znám lui-même : tout élément de ces ensembles est un diviseur propre du produit des autres éléments plus 1, sauf le plus grand, qui est égal par définition au produit des autres plus 1[2].
est une solution au (bon) problème de Znám pour car :
est la seule autre solution pour .
Lien avec les fractions égyptiennes
[modifier | modifier le code]![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/32/Znam-2-3-11-23-31.svg/301px-Znam-2-3-11-23-31.svg.png)
On montre que toute solution au problème de Znám impropre est telle que les entiers sont deux à deux premiers entre eux. Or, notant le produit des , par définition, divise et divise pour donc divise . Le produit des divise donc , ce qui signifie que est un entier.
Par exemple, pour on a .
Autrement dit toute solution au problème impropre de Znám fournit une solution à l'équationoù ainsi que chaque est un entier strictement positif, et inversement, toute solution de ce type correspond à une solution du problème impropre de Znám. Cependant, toutes les solutions connues sont telles que , donc satisfont l'équation
Autrement dit, elles conduisent à une représentation en somme de fractions égyptiennes du nombre 1. Plusieurs des articles cités sur le problème de Znám étudient également les solutions à cette équation. Brenton & Hill (1988) décrivent une application de l'équation en topologie, à la classification des singularités sur des surfaces[2], et Domaratzki et al. (2005) décrivent une application à la théorie des automates finis non déterministes[3].
Nombre de solutions
[modifier | modifier le code]Le nombre de solutions au problème de Znám pour tout est fini, il est donc logique de dénombrer le nombre total de solutions pour chaque [4]. Sun (1983) montre qu’il existe au moins une solution au (bon) problème de Znám pour tout . La solution de Sun est basée sur une récurrence similaire à celle de la suite de Sylvester, mais avec des valeurs initiales différentes[5]. Le nombre de solutions pour les petites valeurs de , commençant à , forme la suite [6] :
Actuellement, on connait quelques solutions pour et , mais on ne sait pas combien de solutions restent à découvrir pour ces valeurs de . Cependant, il existe une infinité de solutions si n’est pas fixé : Cao & Jing (1998) montrent qu’il existe au moins 39 solutions pour tout , améliorant les résultats antérieurs prouvant l'existence de solutions [7] ; Sun & Cao (1988) supposent que le nombre de solutions croît de façon monotone avec [8].
On ne sait pas s'il existe des solutions au problème de Znám n'utilisant que des nombres impairs. À une exception près, toutes les solutions connues commencent par 2. Si tous les nombres d'une solution au problème de Znám ou au problème de Znám impropre sont premiers, leur produit est un nombre semi-parfait primaire [9] ; on ne sait pas s’il existe une infinité de solutions de ce type.
Voir aussi
[modifier | modifier le code]Références
[modifier | modifier le code]Notes
[modifier | modifier le code]Sources
[modifier | modifier le code]- G. E. J. Barbeau, « Problem 179 », Canadian Mathematical Bulletin, vol. 14, no 1, , p. 129.
- Lawrence Brenton et Richard Hill, « On the Diophantine equation and a class of homologically trivial complex surface singularities », Pacific Journal of Mathematics, vol. 133, no 1, , p. 41–67 (DOI 10.2140/pjm.1988.133.41
, MR 0936356, lire en ligne).
- Lawrence Brenton et Ana Vasiliu, « Znám's problem », Mathematics Magazine, vol. 75, no 1, , p. 3–11 (DOI 10.2307/3219178, JSTOR 3219178).
- William Butske, Lynda M. Jaje et Daniel R. Mayernik, « On the equation , pseudoperfect numbers, and perfectly weighted graphs », Mathematics of Computation, vol. 69, , p. 407–420 (DOI 10.1090/S0025-5718-99-01088-1
, MR 1648363, lire en ligne).
- Zhen Fu Cao et Cheng Ming Jing, « On the number of solutions of Znám's problem », J. Harbin Inst. Tech., vol. 30, no 1, , p. 46–49 (MR 1651784).
- Zhen Fu Cao, Rui Liu et Liang Rui Zhang, « On the equation and Znám's problem », Journal of Number Theory, vol. 27, no 2, , p. 206–211 (DOI 10.1016/0022-314X(87)90062-X, MR 0909837).
- Michael Domaratzki, Keith Ellul, Jeffrey Shallit et Ming-Wei Wang, « Non-uniqueness and radius of cyclic unary NFAs », International Journal of Foundations of Computer Science, vol. 16, no 5, , p. 883–896 (DOI 10.1142/S0129054105003352, MR 2174328, lire en ligne).
- Jaroslav Janák et Ladislav Skula, « On the integers for which », Math. Slovaca, vol. 28, no 3, , p. 305–310 (MR 0534998).
- L. J. Mordell, « Systems of congruences », Canadian Mathematical Bulletin, vol. 16, no 3, , p. 457–462 (DOI 10.4153/CMB-1973-077-3
, MR 0332650).
- Ladislav Skula, « On a problem of Znám », Acta Fac. Rerum Natur. Univ. Comenian. Math., vol. 32, , p. 87–90 (MR 0539862).
- Qi Sun, « On a problem of Š. Znám », Sichuan Daxue Xuebao, no 4, , p. 9–12 (MR 0750288).
- Qi Sun et Zhen Fu Cao, « On the equation and the number of solutions of Znám's problem », Northeastern Mathematics Journal, vol. 4, no 1, , p. 43–48 (MR 0970644).
Liens externes
[modifier | modifier le code]
- Primefan, « Solutions to Znám's Problem ».
- (en) Eric W. Weisstein, « Znám's Problem », sur MathWorld.