Soit un ensemble fini E d'entiers tel que, pour tout nombre premier p, le nombre d'élément de E congrus à p-1 modulo p et celui d'éléments congrus à (p-1)/2 sont égaux.
Peut-on on en deduire d'autres propriétés sur E ou ses éléments ?
J'ai la sensation que oui vu que l'on peut construire un nombre de conditions infini pour un ensemble fini, mais je ne trouve pas...
Mis à part que tu dois exclure 2 des nombres premiers, je ne comprends pas cette dernière phrase.Envoyé par CollatzFan
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Il est vrai que dire que le nombre des entiers pairs est égal à lui-même n'apporte pas grand chose.
Les conditions sont
card (x dans E, x=3k+1) = card (x dans E, x=3k+2)
card (x dans E, x=5k+2) = card (x dans E, x=5k+4)
...
card (x dans E, x=pk+(p-1)/2) = card (x dans E, x=pk+p-1)
...
p pouvant prendre une infinité de valeurs et card(E) étant fini, en tant que mécanicien j'ai tendance à penser que le nombre de degré de liberté étant inferieur au nombre de contraintes à priori indépendantes, l'ensemble des solutions devrait être de dimension 0 par rapport l'ensemble des E possibles.
C'est cet ensemble de solution que j'essaie de caractériser.
Le nombre de contraintes n'est pas réellement infini. Si M est le max de l'ensemble, alors tous les premiers strictement supérieurs à 2M +1 n'interviennent pas.
Si j'ai bien compris l'énoncé, {1, 2, 4} est solution, non?
Cordialement,
Pour ma part, j'ai gardé 2 ce qui exclut les impairs. J'ai pu trouver {2,4} {6,12,24} (et donc {2,4,6,12,24}). Ce sont les seuls avec des nombres pairs dont le max est inférieur à 36. Cette recherche à la main ne m'a pas permis de trouver quelque chose d'un peu général par contre.
Non. Me suis gouré, même en excluant p=2.
Cdlt
il faut effectivement exclure p=2, la condition correspondante n'a pas de sens.
Il y a aussi des ensembles comme {7} ou {13}, bref {p} où p + 1 n'est pas premier et 2p + 1 non plus.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Et ben non : c'est une c*rie
Il me semble que les questions suivantes sont intéressantes :
Si A et B sont de tels ensembles en est-il de même de
- A inter B
- A union B
- A - B
- Est que pour tout sous-ensemble fini A de
, il existe un sous-ensemble fini B tel que A inclu dans B et B vérifie les conditions ; Existe-t-il un sous ensemble minimal vérifiant cela ?
Dernière modification par Médiat ; 16/07/2007 à 07h39.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Oui, mais à condition de considérer l'ensemble vide comme solution (ce qu'il est formellement).
C'est évident si l'ensemble vide est solution[*]Est que pour tout sous-ensemble fini A de
Cordialement,
Euh... Je ne vois pas en quoi dire que l'ensemble vide est solution (ce qu'il est) entraîne la stabilité par intersection, union, et différence, l'existence pour tout ensemble d'un sur-ensemble solution, et l'existence dans ce cas s'un sur-ensemble minimal.Oui, mais à condition de considérer l'ensemble vide comme solution (ce qu'il est formellement).
C'est évident si l'ensemble vide est solution
Désolé, mais je ne comprends pas, peux-tu développer ?
Je précise que par existence d'un sur-ensemble minimal, je veux bien dire l'existence d'un seul sur-ensemble ayant le plus petit cardinal, sinon cela n'a aucun intérêt.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Je ne voulais pas dire que c'était une condition suffisante, mais que c'était une condition nécessaire.
La stabilité est due à ce que le problème est en termes de cardinaux de sous-ensembles définis par une propriété. N'est-ce pas suffisant?
J'avais mal lu la question...Je précise que par existence d'un sur-ensemble minimal, je veux bien dire l'existence d'un seul sur-ensemble ayant le plus petit cardinal, sinon cela n'a aucun intérêt.
Cordialement,
J'avais bien compris cette partie là, c'est le "Oui" que je ne comprenais pas
Je ne crois pas (en fait je suis sur, le cardinal de l'union n'étant pas la somme des cardinaux).
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Mais pour l'union d'ensembles disjoints, oui.
A union B = (A - B) union (B-A) union (A inter B)
permet d'y arriver à partir des deux autres, et
A = (A inter B) union (A-B)
permet de tout dériver de A inter B.
Non?
Cordialement,
Edit: J'écris ça juste en passant, pas le temps de bien regarder. C'est peut-être une grosse connerie.
Si j'ai bien compris, tu dis que mes trois questions initiales (union, intersection, différence) se ramène à (union disjointe, intersection, différence) : je suis tout à fait d'accord.
Tu dis aussi que pour l'union disjointe, le résultat est trivial : je suis toujours d'accord.
Il reste l'intersection et la différence.
En fait c'est ma dernière question sur les sur-ensembles (en deux parties) qui me semble la plus importante.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
En notant Z l'ensemble des ensembles solutions, j'ai essayé de construire un élément de Z
Notons Ei, l'ensemble des entiers pour lesquels exactement i conditions (x = (p-1) (p) ou x=(p-1)/2 (p)) sont vérifiées
Dans un premier temps j'ai essayé de trouver des entiers Xi ne satisfaisant à aucune des conditions, soit E0.
Chaque sous-ensemble de E0 serait donc solution du problème, ainsi que chaque ensemble construit par union d'une solution avec un nombre quelconque d'élément de E0.
Malheureusement j'ai essayé tout les entiers jusqu'à 100000 et aucun n'est admissible.
E0 est-il l'ensemble vide ? peut-on le prouver ?
En considérant cette hypothèse,Z ne contient aucun singleton.
Peut-on construire une paire appartenant à Z ?
elle devrait être de la forme {x1,x2} tel que x1= (p-1)/2 (p) et x2= (p-1) (p), ces conditions devant être les seules vérifiées par x1 et x2 respectivement. Soit x1 et x2 appartenant à E1.
Jusqu'à 10000, les seuls éléments de E1 sont 1, 3, 15, 63 et 4095.
Chacun de ces entiers satisfait une condition du type x1=(p-1)/2 (p), les p étant tous différents.
Cette propriété est-elle généralisable ? peut-on le prouver ?
En considérant cette hypothèse, Z ne contient aucune paire.
Essayons un triplet de Z
A la combinatoire près, il devrait être de la forme {x1,x2,x3} avec x1 et x2 dans E1 et x3 dans E2
Sous l'hypothèse que tout élément de E1 verifie x= (p-1)/2 (p)
on doit donc avoir
x1 = (p-1)/2 (p)
x2 = (q-1)/2 (q)
x3 = (p-1) (p) = (q-1) (q) = (pq-1) (pq)
En essayant les différentes classes (pq-1) (pq) construites avec p et q isentifié dans E1, aucun élément (jusqu'à 100000 pour pq<100000 et les 5 premiers de chaque classe au-delà) n'appartient à E2
La encore il semblerait que l'on ne puisse constuire de triplet.
Je ne suis pas allé plus loin, mais je commence à me demander si Z ne serait pas reduit à l'ensemble vide...
Et pourtant l'ensemble {2, 4} proposé par homotopie fonctionne très bien, non ?
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
C'est vrai, j'ai betement considéré que pour une paire chacun des deux elements devait être dans E1, or pour {2,4} il sont dans E2.
De la même façon mon raisonnement est faux pour les triplets, il peuvent très bien être dans E2xE2xE3 et non dans E1xE1xE2
Merci
Et même ton ensemble
En effet : quel que soit le nombre premier impair
0 est par contre le seul.
existe-t-il un x tel que pour tout p x non congru à p-1 modulo p autrement dit existe-t-il un x tel que x+1 ne soit congru à p modulo p pour aucun p ou encore x+1 qui ne soit divisible par aucun p premier ?
existe-t-il y non nul tel que y ne soit divisble par aucun premier ?
La réponse est désormais évidente, non ?
Non car p=2 a été exclu. Donc cela ne marche pas pour 7 par exemple car 7+1=8=2^3. Par contre cela marche pour car 13+1=14=2x7, 13 congru à 7-1 modulo 7 mais n'a pas d'alter ego.
Par contre avec l'autre x congru à (p-1)/2 modulo p, le problème disparaît car y=2x+1 est impair donc divisble par un premier impair.
Par exemple {7} ne convient pas car 7 est congru à (5-1)/2 modulo 5 ainsi qu'à (3-1)/2 modulo 3 mais aucun élément n'est congru à 5-1=4 modulo 5 ni à 3-1=2 modulo 3 dans ce singleton.
E1, on a vu que pour tout x il existe p tel que x soit congru à (p-1)/2 modulo p.
Quand est-ce qu'il n'y a qu'un p, quand 2x+1=p^h pour un p premier impair (dès que x>=1)
On a alors, x=(p^h-1)/2 z et x+1=(p^h+1)/2 congru à aucun p premier impair donc (p^h+1)/2 est une puissance de 2 2^k.(dès que x>=1)
p^h+1=2^(k+1) p^h=2^(k+1)-1. on alors x=(p^h-1)/2=2^k-1 qui est dans E1.
Une recherche sur les puissances successives de 2 va alors très vite :
2-1=1 mais donne 0
4-1=3 OK et donne 4/2-1=1
8-1=7 OK et donne 8/2-1=3
16-1=15 non
32-1=31 OK et donne 32/2-1=15
64-1=63 non
...
là on se rappelle que 2^n-1 a une "chance" d'être premier que si n est premier, sinon on a par exemple 2^6-1=(2^2-1)(2^4+2^2+1).
Un 2^n-1 avec n non premier peut-il être une puissance d'un premier ?
Moins facile et je ne sais pas.
Par contre cela ne montre pas qu'il n'y a pas de paire (comme cela a déjà été remarqué)
Sinon, voilà comment j'ai procédé pour commencer à trouver quelques exemples d'éléments de Z :
6 congru à p-1 modulo p p divise 6+1=7 donc il faut un lien "type (7)" pour 6
6 congru à (p-1)/2 modulo p p divise 2x6+1=13 donc il faut un lien "type (5)" pour 6
12 ->un lien type (13) et un type (5)
24 ->un lien type (5) et un type (7)
Evidemment sur mon petit brouillon, les liens sont fléchés (on va de 6 vers 12 pour le type (5), de 12 vers 24 pour le type (5), de 24 vers 6 pour le type (7) etc on va toujours du congru (p-1)/2 au congru (p-1) modulo p)
J'ai imposé succesivement un maximum et j'ai regardé si on pouvait trouver un graphe fermé (tout le monde a quelqu'un avec qui partager un lien, ceci pour tous ses liens, et pour tous ceux dans le graphe, certains sont plus gourmands en liens exemple 34 (types (5)(7)(3)(23), certaines paires partagent parfois deux liens, certains comme max sont minables il leur faut tout de suite quelqu'un de plus grand ce qui limite très vite les recherches).
Je ne sais pas si cette idée est transposable à l'informatique (en tout cas pas par moi)
La question que je me pose moi est : les éléments de z sont-ils décomposables en sous-éléments fermés, exemple {2,4,6,12,24}={2,4}+{6,12,24} autrement dit dès qu'il y a du 2, son copain 4 est là aussi et se désolidarise des autres car à deux ils comblent leurs atomes crochus.
Si le résultat est trivial pour vous, vous pouvez expliquer pourquoi ? Car si pour un p premier, je note p(X)=card {x de X tel que x est congru à (p-1)/2 modulo p}-card{x de X tel que x est congru àp-1 modulo p}.
Il est clair que p (X U Y) =p(X)+p(Y) si X et Y sont disjoints.
Donc si p(A\B)=p(B\A)=-p(A inter B)=a non nul, on a
p(A)=p(B)=a-a=0 mais p(A U B)=a est non nul ainsi que p(A union disjointe B)=2a.
J'ai du mal à suivre. Pour l'union disjointe, ça semble direct, non?
C'est pour l'intersection que ça ne marche pas.
J'avais tout ramené à l'intersection, mais après réflexion, c'est l'intersection qui pose problème.
Cordialement,
Par ailleurs, j'ai l'impression que la question de la stabilité par intersection est équivalente à celle que tu poses à la fin de ton pénultième message à partir de celui-ci.
Cordialement,
Il semble que non.
Si n=ab, on a
Si
Or
...
on arrive à
Ainsi le pgcd de 2^a-1 et du second facteur est égal au pgcd de 2^a-1 et de b.
Désormais b =p premier, a=n/p non égal à 1 par hypothèse.
si p=2, on a 2^a-1 impair donc ce pgcd est trivial et aucun n de la forme n=2.truc ne convient.
si p=3, on doit avoir 3 qui divise 2^a-1 càd 2^a congru à 0 modulo 3, càd a est pair ainsi que n, les n3.truc ne conviennent pas.
pour p=5, il faut que a soit un multiple de 4.
pour p=7, on aboutit à a doit être un multiple de 3, mais si a est un multiple de 3, n aussi et on a vu qu'un tel n ne convient pas.
Et maintenant on a compris le truc, par l'absurde : soit p le plus petit premier divisant n, on a a=n/p>1 car n n'est pas premier. Et on doit avoir p qui divise 2^a-1 mais ceci implique que l'ordre a' de 2 dans (Z/pZ)* divise a, soit p' un premier diviseur de a' (existe car a>1) on p' divise a' donc divise (p-1) l'ordre du groupe (z/pZ)* (ou application du petit théorème de Fermat). En particulier on a p'<=p-1<p, or comme p' divise a', il divise aussi a et donc divise n. On a donc p' est un plus premier diviseur de n ce qui contredit la minimalité de p.
Les éléments de E0 sont donc de la forme
Oui, j'ai la même impression.
Tout le monde aura lu E1 bien sûr.Les éléments de E0 sont donc de la forme
Je vais reformuler : on appelle ensemble premier un ensemble vérifiant la prorpiété énoncée au 1er post modifié ensuite en excluant p=2 (P) tel que aucune de ses sous-parties ne vérifie la propriété. (Exemple : {2,4} {6,12,24}, ce serait bien d'en trouver d'autres
Comme quand X est inclus dans Y on a p(X)=p(Y)+p(Y\X) (ça au moins c'est évident), par récurrence sur le nombre d'éléments on voit assez facilement qu'un ensemble vérifiant P est union de sous-parties premières disjointes.
Question : cette décomposition est-elle unique (si on exclut l'ensemble vide de la même manière que l'on exclut 1 des décompositions en facteurs premiers chez les entiers) ?
Si c'est stable par intersection alors cette propriété est vérifiée : si (Ai) est une 1ère décomposition et si (Bj) en est une autre alors Ai=union sur les j des Ai inter Bj mais les Ai inter Bj sont vides ou égales à Ai par définition de premier, les Bj sont de plus disjoints, donc Ai=Ai inter Bj pour un certain qui lui même est inclus dans Bj qui est premier donc Ai inter Bj=Bj et ainsi Ai=Bj.
Si cette propriété est vraie alors c'est stable par intersection : A=union Ai les Ai étant premiers, A inter B=union sur i des Ai inter B mais ceux-ci sont vides ou égaux à Ai car B vériie (P), donc Ai est soit complètement à l'extérieur de B soit complètement inclus, A inter B est donc une union de certains Ai et vérifie donc (P).
Ooops, abus de langage, je voulais parler, et je crois que mmy aussi (par ma faute) de l'union d'ensembles disjoints.
L'union disjointe (la vraie) ne me semble pas avoir d'intérêt ici.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Merci a tous pour vos contributions.
En résumé, on a determiné E0={0} et on peut construire E1 (de façon bien plus élégante que le calcul brutal fait précedemment).
Si j'ai bien compris le dernier post d'homotypie tout élément de Z est l'union d'éléments minimaux disjoints, eux-même dans Z, et la question est de savoir si cette décomposition est unique.
L'analogie faite lors d'un post precedent avec les graphes m'interresse car cela me ramene a la problematique sous-jacente a cette question, à savoir la caractérisation de boucles éventuelles pour le problème de Collatz/Syracuse.
Avec une representation par graphe, chaque noeud étant concerné par une ou plusieurs relations
x=(p-1)/2 (p) --> y=(p-1) (p) on peut assigner un sens aux arètes en definissant par exemple arbitrairement x-->y sortant de x pour une congruence à (p-1)/2 modulo p et entrant en y par une congruence à p-1 modulo p.
Ainsi chaque élément de Z est un "paquet" de noeuds et d'arètes tel que en chaque noeud le nombre d'arètes entrantes soit égal au nombre d'arètes sortantes. Et un tel graphe doit pouvoir se decomposer en "boucles" unitaires (les ensembles premiers)
Si la disjonction des ensembles premiers est acquise alors un noeud ne peut apartenir a deux boucles différentes et cette décomosition est alors unique.
Affirmation faite un peu légérement sous l'effet de l'euphorie et sans preuve formelle
Pas nécessairement, certains nombres (c'est le cas pour tous les E(impair) mais aussi pour certains E(pair)) il n'y a pas égalité entre le nombre d'arêtes entrantes et le nombre d'arêtes sortantes (Maintenant il pourrait s'avérer que ces nombres ne font pas partie de "graphes" pour (P))
Sauf que ce ne sont pas nécessairement des boucles, cf remarque ci-avant il se peut d'ailleurs qu'un chemin ouvert (dans le sens il y a un début et une fin, donc des E(1)) satisfasse la condition (P).
Ce problème m'a l'air encore plus difficile que celui de Syracuse mais parfois les apparences sont trompeuses.
