Patterns introuvables dans une suite

[invité576543]

Bonjour,

Sur un autre fil, non mathématique, on voit que certains pensent que si l'Univers est infini, toute situation imaginable va se trouver quelque part.

Cherchant des arguments contre, j'ai regardé de simples suites infinies de symboles pris dans un alphabet fini, que l'on peut penser comme le développement en -males d'un réel dans la base ad-hoc.

Or il est facile de construire des suites infinies telles qu'un pattern donné de longueur finie ne s'y trouve jamais. Il y a pleins d'exemples. Un, pour rester dans les maths, est donné par tous les éléments de l'ensemble de Cantor écrits en base 3: la séquence "1" (par exemple) n'y apparaît jamais.

Remarquons que la construction implique qu'un nombre infini de patterns de longueur finie sont introuvables: tous ceux qui ne contiennent pas le premier!

Maintenant, une suite étant donnée, je note n le plus petit cardinal d'un ensemble de patterns de longueur finie tel que tout pattern introuvable contienne l'un d'entre eux.

Première question, est-il possible d'avoir n fini quelconque? C'est vraisemblable, mais quelqu'un connaît-il un procédé constructif?

Deuxième question, la plus intéressante, est-il possible d'avoir n infini? Si oui, peut-on citer un cas ou une construction?

Cordialement,
-----

[Médiat]

Je ne suis pas certain d'avoir bien compris, mais si c'était le cas :
soit la suite 0101010101...
on n'y trouve pas le pattern 1001, mais pas non plus le pattern 10001 qui n'est pas réductible au premier, ni 100001 etc.
Si j'ai bien compris cela devrait répondre à ta question N° 2...

Pour la première question une piste : tu prends un nombre univers en base dix, et tu remplaces toutes le occurences de 01 par 22, et tu as un exemple avec n = 1 (il me semble en tous cas)

[invité576543]

Je ne suis pas certain d'avoir bien compris, mais si c'était le cas :
soit la suite 0101010101...

Aïe...

J'ai oublié de donner la conditions inverse, du genre (à préciser) que le nombre de patterns de longueur finie k et trouvables dans la suite, divisé par p^k, p étant le nombre de symboles, soit borné inférieurement par un nombre plus grand que 0. Ou un truc comme ça pour virer les répétitifs... (L'idée étant qu'il doit rester une infinité de patterns "quelconques".)

Pour la première question une piste : tu prends un nombre univers en base dix, et tu remplaces toutes le occurences de 01 par 22, et tu as un exemple avec n = 1 (il me semble en tous cas)

Effectivement, les nombres univers est une piste. Que connaît-on comme construction? En base dix, il y a 0,1234567891011121314151617181 920212223.... Quoi d'autre?

Cordialement,

[Médiat]

Bonjour mmy

Pour les nombres univers, non, je n'en connais pas d'autres, désolé.

Pour l'autre question, la suite 01001000100001 etc. n'est pas périodique,et l'on n'y trouve pas 1001001, ni 100010001, ni ...

Cordialement,

Médiat

[A voir en vidéo sur Futura]

[invité576543]

Pour le cas infini, on peut reformuler comme suit:

Pour une suite donnée, on note g(k) le nombre de patterns trouvables de longueur k. Construire une suite sur un alphabet fini de taille a telle que g(k)/a^k reste dans un intervalle [b, c] donné avec b>0 et c<1. Je ne sais pas si c'est suffisant pour n (tel que défini dans le premier message) infini (dans le cas d'un élément de l'ensemble de Cantor suffisamment "univers", on a g(k) = 2^k, donc g(k)/a^k = (2/3)^k qui tend vers 0 à l'infini).

Un nombre univers est tel que g(k) est uniformément égal à 1. Une suite répétitive est telle que g(k) bornée par la longueur du motif répété. (Réciproque? Si g(k) bornée que peut-on en conclure?)

Cordialement,

[invité576543]

Pour l'autre question, la suite 01001000100001 etc. n'est pas périodique,et l'on n'y trouve pas 1001001, ni 100010001, ni ...

OK, mais je ne pense pas qu'elle ne respecte pas une borne inférieure pour g(k), i.e., on y trouve pas une assez grande variété de patterns.

Et, oops, dans le message précédent ce que j'ai montré est que les éléments de l'ensemble de Cantor ne respecte pas non plus la condition de la borne inférieure.

Petit à petit je vais arriver à trouver un problème "bien posé", qui sait ? L'idée est de trouver une suite où on trouve une très grande variété de patterns, mais où il en manque une "aussi grande" variété.

Cordialement,

[invité576543]

Suite à un message privé de Médiat, voilà une propriété intéressante, avec sa démonstration (qui est différente de l'approche de Médiat, et que j'espère néanmoins correcte).

Propriété: s'il existe k tel que g(k)<a^k, alors g(n)/aⁿ tend vers 0

Démo (tentative de):

Prenons les mots de longueur m>k, et découpons les en tranches de longueur k. Il y a telles tranches (en notant la partie entière avec la flêche vers le bas, \floor ne marche pas). Chaque tranche ne peut prendre qu'au plus a^k-1 valeurs, par hypothèse. Il y a donc au plus

mots trouvables de longueur m, soit mots, expression qui tend vers 0 quand m tend vers l'infini.

Le résultat est assez brutal et intéressant. Cela veut dire que soit on est en présence d'une série univers (g(k)=a^k pour tout k), soit le nombre de mots trouvables est négligeable, nul à un certain sens, devant le nombre de mots introuvables.

On est bien loin de l'idée que dans un machin infini on trouve tout le possible!

Cordialement,

[invité576543]

Je reprend mon petit monologue sur les suites "bordéliques mais pas trop", et je reformule le problème:

Pour une suite on note g(k) le nombre de mots trouvables de longueur k. Et n le plus petit cardinal d'un ensemble de mots de longueur finie tel que tout mot de longueur fini introuvable dans la suite contienne au moins un mot de l'ensemble.

La question est l'existence et la construction de suites telles que:

1) g(k) va plus vite que tout polynôme;

2) n infini

Il y a des suites respectant 1) avec n=1, c'est le cas de certains éléments de l'ensemble de Cantor écrits en base 3.

Les suites cycliques ne respectent pas 1) (g(k) a une asymptote), ni non plus les suites genre 01001000100001000001... (g(k) est dominée par un polynôme de degré 2).

L'intérêt "philosophique" des suites respectant 1) et 2) est qu'elles présentent un très grand nombre de mots distincts, mais en manquent un encore plus grand nombre!

Ce serait encore plus frappant si l'ensemble des réels avec de tels xmales pour une base donnée x était non dénombrable!

Cordialement,

[Médiat]

Bonjour,

Comme la suite 01001000100001000001... vérifie le point 2, je suppose que la question porte sur les suites vérifiant 1 et 2 ?

Cordialement

[invité576543]

Comme la suite 01001000100001000001... vérifie le point 2, je suppose que la question porte sur les suites vérifiant 1 et 2 ?

Oui, 1) et 2) !

Cdlt,

[Médiat]

Que penses-tu de la suite 0x0xx0xxx0xxxx0 ...
ou x est n'importe quelle lettre de l'alphabet sauf 0, pour un alphabet de taille > 2 ?

[invité576543]

Que penses-tu de la suite 0x0xx0xxx0xxxx0 ...
ou x est n'importe quelle lettre de l'alphabet sauf 0, pour un alphabet de taille > 2 ?

Effectivement, ça ne doit pas être trop dur de respecter 1), peut-être qu'il suffit de prendre un nombre "super-univers" sur l'alphabet moins {0} pour la suite obtenue en virant les 0.

(Avec super-univers voulant dire que tout mot de longueur fini est trouvable une infinité de fois dans la suite; c'est le cas de 01234567891011121314...)

Pour 2) ça à l'air de marcher aussi effectivement.

Cordialement,

[Médiat]

(Avec super-univers voulant dire que tout mot de longueur fini est trouvable une infinité de fois dans la suite; c'est le cas de 01234567891011121314...)

Alors Super-Univers = Univers (si tu trouves la suite [s1], il faut aussi [s1 || s] pour tout s fini)

Cordialement

[invité576543]

Alors Super-Univers = Univers (si tu trouves la suite [s1], il faut aussi [s1 || s] pour tout s fini)

Ouaip... Ca montre que ces temps-ci je ne cherche pas beaucoup à réfléchir à fond avant de poster. Pas grave, faut des vacances, un peu de roue libre, ça repose

Sinon, pour le fond du problème, il me semble que la messe est dite. Cette histoire de "infini => tout" c'est du n'importe quoi grande classe, y compris quand associé avec "la probabilité est non nulle, alors dans l'infini on le trouve". Ce n'est pas que j'en doutais, mais concocter de bons petits contre-exemples, ça aide...

Cordialement,