Un concept que j'ai inventé (enfin j'espère), j'appelle ça la fragmentation unitaire

EtNonLesShills
Modifié (August 2023) dans Shtam
Soit $M = \{0;1\}^n$
Soit $F $ l'ensemble des fonctions $f$ de $M \times \{0;1\} \rightarrow \{0;1\}$ où
 il existe $k \leq n$ et $h: \{0;1\}^2 \rightarrow \{0;1\}$ tq $\forall (x,b)  \in M \times\{0;1\}: $ $f(x,b) = h(x_k,b)$.
Alors pour toutes fonctions $g$ de $M \rightarrow \{0;1\}$, il existe $f_1, f_2, \dots, f_m$ toutes dans $F$ telles que $g= f_1 \circ f_2 \circ\dots\circ f_m(Id,0)$,
avec la notation abusive $f_i \circ f_{i+1} (x,b) = f_i(x, f_{i+1}(x,b))$.
C'est plutôt sympa comme mode de représentation d'une fonction, ça peut être utile quelque part. On peut pousser la théorie plus loin en se restreignant à un sous-ensemble strict de $F$ et essayer alors de déterminer le m maximum sur ce sous-ensemble, ça mesure un peu la complexité maximale des fonctions de ce sous-ensemble. 

Réponses

  • Dom
    Dom
    Modifié (August 2023)
    Bonjour, 
    c’est illisible pour moi…
    Peux-tu rendre ton message plus propre en ce qui concerne les textes mathématiques ?
    Cordialement
    Dom
    [GRAND MERCI !]
  • Bonsoir
    Mis à part quelques coquilles à corriger, cela me fait étrangement penser à ce que l'on peut examiner dans le livre d'algèbre de Bourbaki, en bas de la page A I.81, et au début de la page A I.82. A quelques notations près, le procédé est bien connu depuis des décennies.
    Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
  • EtNonLesShills
    Modifié (August 2023)
    Bonsoir @Thierry Poma
    je ne vais pas vous mentir je n'ai jamais lu les Bourbaki :blush: et je n'arrive pas à  trouver le livre en ligne malheureusement.
    Poussent-ils l'étude à examiner les complexités de sous-ensemble de fonctions de Mx{0;1} -> {0;1} ou la complexité est définie comme  le maximum des cardinaux des tailles  des décompositions minimales des fonctions dans le sous-ensemble ?

    edit : j'avais trouve ça: http://sites.mathdoc.fr/archives-bourbaki/PDF/033_iecnr_040.pdf mais ça ne parle pas de ça au lieu dit peut être pcq  [parce que ?] ce n'est pas la version définitive.
  • EtNonLesShills : je ne dis pas que tu mens. Je vais essayer de revenir demain sur ce point.
    Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
  • EtNonLesShills
    Modifié (August 2023)
    Merci bien, à demain.
  • Positif
    Modifié (August 2023)
    @EtNonLesShills
    [*** modéré. Hors sujet. AD]
    ---> I believe in Chuu-supremacyhttps://www.youtube.com/watch?v=BVVfMFS3mgc <---
  • Thierry Poma
    Modifié (August 2023)
    EtNonLesShills : bonjour. Je rappelle que $M_n=\{0,\,1\}^n$ pour un entier naturel $n$ non nul. Tu écris (en ayant modifié légèrement ton texte) :
    Alors, pour toute fonction $g:M_n \rightarrow \{0;1\}$, il existe $f_1, f_2, \dots, f_m$, toutes dans $\mathcal{F}_n$, telles que $g= f_1 \circ f_2 \circ\dots\circ f_m(\mathrm{id},\,0)$
    Pour un entier naturel $n$ non nul, penses-tu que $u\circ{}v$ ait un sens pour des fonctions $u$ et $v$ appartenant à $\mathcal{F}_n$ que tu as défini ? Je rappelle que $\mathcal{F}_n$ est l'ensemble des applications définies sur $M_n\times\{0,\,1\}$ à valeurs dans $\{0,\,1\}$ vérifiant une propriété qui sera, elle aussi, à revoir intégralement. Veux-tu définir ce $\mathrm{id}$ que tu utilises ?
    Pourtant, je parviens à comprendre l'idée, vu que Bourbaki l'a déjà utilisée.
    Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
  • Cette "notation abusive" est expliquée supra : $f \circ g(x,b) = f(x, g(x,b))$.
  • @Math Coss : bonjour. Justement, il y a un moyen de s'affranchir de cette notation abusive inepte afin de donner un nouveau cadre de travail naturel. Je veux que l'auteur y réfléchisse.
    Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
  • EtNonLesShills
    Modifié (August 2023)
    Le théorème est malheureusement faux, une preuve de cela en dessous (c/c le pavé sur maths exange ici ça ne formate pas certaines parties).

    edit: errata 4h30
  • Magnéthorax
    Modifié (August 2023)
    Soit $F $ l'ensemble des fonctions $f$ de $M \times \{0;1\} \rightarrow \{0;1\}$ où il existe $k \leq n$ et $h: \{0;1\}^2 \rightarrow \{0;1\}$ tq $f(x,b) = h(x_k,b)$.
    Bonjour,
    x_k est la k-ème coordonnée de x ?
    Pourrais-tu utiliser des quantificateurs pour introduire x et b ?
  • EtNonLesShills
    Modifié (August 2023)
    Magnéthorax
    oui
    Thierry Poma a dit :
    @Math Coss : bonjour. Justement, il y a un moyen de s'affranchir de cette notation abusive inepte afin de donner un nouveau cadre de travail naturel. Je veux que l'auteur y réfléchisse.
    y a moyen comme toute notation abusive ça veut dire qu'au lieu de :
    $f_1\circ\dots\circ f_m(x,0)$ il faut écrire $f_1(x,\dots(x, f_m(x,0)))$.
    Jne l'ai pas fait dans la contre preuve car c'est un peu trop lourd.
    Par contre à partir du moment où les fonctions de décomposition (notées $F$ dans le post initial) ne touchent pas au mot $x$, je doute du caractère naturel.
  • EtNonLesShills
    Modifié (August 2023)
    J'ai oublié de le dire vu que pour moi ça coule de source, comme ça ne marche pas le but est alors évidemment de trouver un autre ensemble F de fonctions le plus petit possible rendant le théorème vrai.  
    Par contre  les fonctions de F doivent rester à valeur dans {0,1}, si vous autorisez à valeur dans {0,1}² le problème devient trivial vous écrivez sous forme normale disjonctive la fonction que vous voulez décomposer  et l'une des deux variables de {0;1}² stocke le fait que l'ensemble des disjonctions précédentes est vrai pendant que l'autre stocke si la disjonction qui est en train d'être analysée a déjà rencontré un terme vrai. Et avec ce principe on construit facilement un très petit ensemble F capable de décomposer toutes les fonctions.
     Je ne sais pas si je me fais comprendre mais bref les fonctions de F doivent être à valeur dans {0;1} pour que le problème soit un minimum intéressant.
  • EtNonLesShills
    Modifié (August 2023)
    Je suis en train  de finaliser la preuve pour le cas général, ça sera probablement prêt pour demain à moins que j'ai fait une erreur.
    3 points.
    1) Non il n'existe pas de petit F  pouvant générer toute les fonctions, c'est donc un non-résultat (du point de vue pratique).
    2) Toute fonctions pouvant être générée peut être générée  par moins de  2card(F)^3 compositions. C'est un vrai résultat du point de vu pratique, vu que cela dit que s'il existe un programme dans un certain ensemble (les fonctions générées par F) alors il existe un programme rapide faisant la même chose.
    3) La preuve porte en elle même la direction de la suite des travaux : une transformation du problème "envoie" le dit problème sur des matrices diagonales de Z/2Z, mais la résolution qui suit (et donc le résultat en 2) ) aurait très bien pu s'effectuer sur juste un ensemble de matrices simultanément diagonalisables de Z/2Z, la question se pose alors quels sont ces problèmes qui après transformations sont envoyés sur un ensemble de matrices simultanéments diagonalisables de Z/2Z ?
    [Comme tu sembles en difficulté avec les accents, préfère le verbe "engendrer" au verbe "générer". :) AD]

    un peu de retard quasi fini :)
  • EtNonLesShills
    Modifié (August 2023)
    tuturu

    c/c sur  stack exange

    n'hésiter pas a réfléchir au point 3 du dernier post, j'y ai un peu pense l'embêtant c'est que je ne sais pas si les résultat de diagonalisation connu sont vrais pour les matrices a coefficient dans Z/2Z. Par exemple la diagonalisation simultane si diagonalisable + commutativite, ca reste vrai ?
    (Z/2Z)^n peut il etre munis d'un "produit scalaire" rendant vrai le théorème spectral ?  bref

    erreta: precise F C H la ou c'etait  vrai et non mentionne
    errata: $card(\overline{F})+2$ a la place de n+2 dans la preuve du dernier theoreme  + je crois que je m'etais emmele dans mes c/c sur blocnote oups
Connectez-vous ou Inscrivez-vous pour répondre.