aire du cercle

Je trouve qu'il y a moyen de faire parler la poudre avec ce problème, aussi en pièce jointe j'ai résumé de manière plus claire là où j'en suis.

S

ah, une réponse... merci mt-i.

Le document joint a plus de rigueur, (divisions par zéro...)
Pour b=d=0, j'ai fait un dessin puis un changement d'échelle et des habiles divisions euclidiennes (sourire).

Lorsque que d=0 et a, b, c strictement positifs, déjà je me sens pas trop armé, un peu démuni en fait.

des idées?

S

Je veux bien détailler mais je ne vois pas de généralisation.


je suis pas au top en matière de pdf.
il n'est pas exclu que je trompe des éléphants.
S

Bon, pour certaines personnes c'est la suite de Collatz, voire RH... pour ma part je bloque sur cette Q-mesure.

en pièce jointe, le calcul de l'aire d'un triangle rectangle particulier qui permet d'améliorer l'approximation de la Q-mesure du disque (et de me consoler dans mon "avancement" sur ce problème).
Je n'ai pas rédigé le paragraphe à propos de l'usage des symétries, la difficulté résidant dans l'obtention de formules.

S

Bien vu, Aléa !
Non seulement tu as tous les bons bouquins chez toi (moi aussi, j'en ai pas mal..), mais, en plus, toi, tu les connais par coeur (ce qui n'est pas mon cas, hélas...) !
Je joins un scan des pages concernées pour qu'on puisse voir de quoi il s'agit.

Non, pas d'idée. En l'absence d'idée, je me suis amusé à calculer numériquement la dérivée de Radon-Nykodym de cette mesure sur le carré. C'est ce truc là que tu cherches à intégrer sur le disque :

Merci remarque pour ces contributions, et aléa, Aleg pour l'apport plus théorique.

J'aimerais bien savoir, en fait quelles sont les pistes qui avaient été envisagées à l'époque par l'équipe de Quadrature. J'imagine que cela doit être bien moins élémentaire que mon approche.
Le problème est simple à comprendre, il y a une redoutable complexité dès que l'on creuse un peu, voilà pourquoi j'y réfléchis de temps à autre.

S

J'ai laissé tourner toute la journée et voici mon dernier mot : entre 0.6849312 et 0.6850051

Après j'arrête, c'est trop lent.

J'ai fait un script scilab qui part d'une liste de carrés avec leur mesure, teste s'ils sont à l'extérieur du disque, à l'intérieur du disque ou coupent le cercle. Dans le premier cas, on enlève la mesure du carré à l'estimation supérieure précédente et on jette le carré, dans le deuxième cas, on ajoute la mesure du carré à l'estimation inférieure précédente et on le jette, dans le troisième cas, on découpe le carré en 4 avec les mesures idoines et on le remet dans la liste. Si ça t'intéresse, je poste le code.

Le problème c'est que la boucle principale devient rapidement longue au fur et à mesure des itérations, et en scilab c'est pas bon les boucles. Il faudrait refaire ça dans un langage compilé, mais je ne sais pas faire.

Peut-être le mot aire est-il mal choisi ? C'est juste une mesure sur l'ensemble des carrés dyadiques construite de façon autosimilaire. On la définit directement sur les carrés à sommets dyadiques par la construction du découpage en 4 : un carré dyadique de mesure $m$ est découpé en 4 carrés dyadiques de mesures respectives $am$, $bm$, $cm$ et $dm$ en partant du coin supérieur gauche et en tournant dans le sens indirect (le grand carré de départ ayant une mesure de 1). Comme $a+b+c+d=1$, cette construction est additive sur les carrés dyadiques. On n'a pas besoin de faire appel aux derniers développements de la GF-théorie.

Maintenant, je n'avais pas réfléchi à la question et il me semblait qu'on avait affaire à une mesure borélienne, vu qu'on peut remplir tout ouvert de carrés dyadiques, mais finalement ce n'est pas si évident que ça. Il faudrait montrer que cette mesure s'étend de façon $\sigma$-additive aux réunions dénombrables de carrés dyadiques. Je ne vois pas pourquoi ce ne serait pas vrai, mais encore faut-il le faire. En tout cas, pour le disque, on doit pouvoir montrer (mais j'ai la flemme) que le nombre de carrés dyadiques qui coupent le cercle est suffisamment négligeable par rapport à celui de ceux qui ne le coupent pas, pour que la mesure du disque soit bien définie. En tout cas, c'est ce qui se passe numériquement.

Maintenant tu vas aussi pouvoir participer à la folie des petits carrés !

Ah et bien pourtant, je ne suis pas géomètre, ni de naissance, ni de formation...

La question reste : l'objet que l'on considère est-il une mesure ? J'inverse le dessin en partant du coin inférieur gauche et en tournant dans le sens direct. La premier carré est $\overline C_{1}=[0,1]^2$. Après $i$ subdivisions, on a obtenu $4^{i}$ carrés fermés $\overline C_{i}^j$ de côté $2^{-i}$. Je note $S_{i}=\{S_{i}^j, j=1,\ldots,4^{i}\}$ l'ensemble des coins inférieurs gauches de ces carrés avec une certaine numérotation. Chaque carré est affecté d'une \og\ mesure \fg\ selon l'algorithme de découpage, notée $m_{i}^j$. On numérote de telle sorte que $m_{i}^j=m_{i+1}^{4j-3}+m_{i+1}^{4j-2}+m_{i+1}^{4j-1}+m_{i+1}^{4j}$, c'est-à-dire que $S_{i+1}^{4j-3}, S_{i+1}^{4j-2}, S_{i+1}^{4j-1}$ et $S_{i+1}^{4j}$ sont les quatre coins inférieurs gauches des carrés issus de celui basé sur $S_{i}^j$. Pour aller avec, je note $(a_{-3},a_{-2},a_{-1},a_{0})=(a,b,c,d)$ de sorte que $m_{i+1}^{4j-l}=a_{-l}m_{i}^j$. Une estimation grossière immédiate est que $(\min\{a_{-l}\})^i\le m_{i}^j\le
(\max\{a_{-l}\})^i$, mais la distribution précise des $m_{i}^j$ dans le carré est sauvage, dépendant des développements dyadiques des coordonnées du coin.

Soit maintenant la forme linéaire sur $C^0(\overline C_{1})$, $f\mapsto L_{i}(f)=\sum_{j=1}^{4^{i}}f(S_{i}^j)m_{i}^j$. Il me semble que pour tout $k\ge i$, $|L_{i}(f)-L_{k}(f)|\le \omega_{f}(2^{-i})$ où $\omega_{f}$ est le module de continuité de $f$, en raison de l'additivité du passage d'un découpage aux suivants. La suite $L_{i}(f)$ est de Cauchy, elle converge vers un certain $L(f)$. Il est clair que $L$ est linéaire, continue, positive, donc par le théorème de Riesz, il existe une mesure de Radon $\mu$ sur $C_{1}$ telle que $L(f)=\int_{\overline C_{1}}f(x)\,d\mu$. Reste à voir ce que vaut $\mu$ sur les carrés dyadiques. Or si $f=1$ sur un carré dyadique $\overline C_{i}^j$ avec $0\le f\le 1$, alors pour tout $k\ge i$, $L_{k}(f)\ge m_{i}^j$. Par conséquent, $\mu(\overline C_{i}^j)\ge m_{i}^j$. Maintenant, si $f$ est à support dans $C_{i}^{j}$ ouvert, alors pour tout $k\ge i$, $L_{k}(f)\le m_{i}^j$. Par conséquent, $\int_{C_{i}^{j}}f\,d\mu\le m_{i}^j$ pour de tels $f$. Donc $\mu(C_{i}^{j})\le m_{i}^j$.

Là il y a une difficulté : implicitement l'algorithme de découpage ne charge pas les côtés intérieurs qui apparaissent. Est-ce que c'est le cas de la mesure $\mu$ ? Je pense que oui, mais je ne sais le montrer que si $\max\{a_{-l}\}<1/2$ en prenant des bandes dyadiques de part et d'autre d'un tel côté et en estimant grossièrement la contribution de $L_{k}(f)$ dans ces bandes pour $k$ assez grand. (Bon, je n'ai pas écrit le détail, parce que c'est casse-pieds, mais \c ca devrait aller). Dans ce cas, on obtiendrait donc $\mu(\overline C_{i}^{j})=\mu(C_{i}^{j})= m_{i}^j$.

Pour un carré ayant un ou deux côtés sur le bord de $\overline C_{1}$, \c ca marche pareil puisqu'on peut prendre une fonction qui vaut $1$ dessus. Par contre, la mesure $\mu$ pourrait charger ces côtés.

En résumé, c'est un peu lourdingue, mais au moins si $\max\{a_{-l}\}<1/2$, on a bien affaire à une mesure de Radon. Ouf. J'espère qu'il y a plus simple !

Juste pour vérifier que j'ai bien compris la question:

*Il ya 4 ensembles de carré? Rouge, Vert, Bleu, Orange

*Dans un ensemble de, par exemple Rouge, un carré est subdivisé en 4 carrés, dont celui en haut à gauche est aussi Rouge[edit: ah bah non, effectivement, ah bah si peut-être oulalala je sais pasbon disons qu'il y a 4 catégories, mais sans les caractériser]?

*Tout carré d'un même de ces ensembles a-t-il une mesure proportionnelle au carré de son côté?

Si oui, il semble qu'il suffise de diviser le disque en question en 4 zones et d'additionner les mesures de chaque zone.

Et les zones seraient difficiles à visualiser?

En tout cas, elles sont boréliennes, ça c'est pas vraiment le problème.

?

Edit: Non, je délire, il n'existe pas 4 catégories!

Oui Christophe C, c'est bien le problème.

Je vais revenir à l'idée que j'avais au départ, à savoir coder les carrés maximaux, c'est à dire un carré dyadique totalement inclus dans le disque mais dont le parent n'a pas cette propriété (ce que faisait remarque dans son algorithme je crois) par des nombres écrits en base 4, et voir si il y a une propriété sur cette liste de nombres.
(ça fait un bail que j'ai pas programmé...)

S

Ah bon??? bah merci

On peut peut-être tenter une récurrence invalide:

Un carré est dans la catégorie t si t est le reste de la division par 4 de i-j, où i est la catégorie de son père et j est sa place dans son père.

J'initialise pas.

Veuillons que à même catégorie, même proportion (si on ramène le côté à 1)

u,v,w,z

Il est en plus demandé, par exemple, à un père de catégorie 2 d'avoir une mesure égale à la proportion p suivante dans un carré de même côté.

il est de catégorie 2, donc il occupe la proportion w et

4w=aw+bz+cu+dv

s'il était de catégorie 0, la proportion qu'il occupe serait:

4u=au+bv+cw+dz

Héla, par ailleurs, on doit avoir: u+v+w+z=1 donc ca fait 5 équations, grrrrr

Ah mais non!!!!!

si on trouve une solution, comme 4u+4v+4w+4z=4(a+b+c+d), ça peut marcher...

Mmmm, je ne me rappelle plus trop ce que j'avais fait à l'époque sur ce problème intriguant, mais il m'avait de prime abord semblé intuitivement évident que l'objet mesure additive sur les réunions finies de cubes dyadiques était la trace d'une mesure de Borel, de façon à pouvoir donner un sens à la mesure du disque.

Puis en y réfléchissant, je me suis aperçu que ce n'était pas si clair que ça (alors que ça l'était plus ou moins en dimension 1), mais je ne sais plus trop pourquoi. Ne connaissant pas le bouquin de Flaconer cité par egoroff, j'ai essayé un truc à la main à base d'intégrale de Riemann et de théorème de représentation de Riesz, sans parvenir à conclure dans tous les cas. En fait, j'ai dû + ou - montrer qu'il y a bien une mesure de Radon associée à l'intégrale de Riemann naturelle, mais je n'étais pas sûr qu'elle coïncide avec la mesure additive de départ sur les carrés dyadiques, si un des coefficients est plus grand que 1/2. Le problème étant d'être sûr que la mesure ne charge pas les côtés des carrés dyadiques... bon bref.

En tout cas, numériquement, tout se passe comme si le disque est mesurable, au moins jusqu'à ce que la patience d'attendre le résultat finisse à manquer. Car c'était très lent.

Je n'ai pas plus avancé que ça. Je crois que samok espère une formule analytique pour l'aire du disque en fonction de a, b, c et d, mais je n'y crois pas trop pour ma part (sans que cela ne veule dire quoi que ce soit dans un sens ou dans l'autre).

Sinon, egoroff, oui j'avais aussi pensé à l'aspect IFS, mais il n'est pas du tout aléatoire, puisqu'on sait exactement quels carrés vont se retrouver multipliés par a, etc. Le problème dans cette interprétation, c'est que devient le disque que l'on cherche à mesurer ? Un truc infâme, me semble-t-il.

Je suis d'accord que la mesure du disque est invariante par permutation des coefficients (ça a déjà dû être mentionné page précédente qqpart). Mais je ne vois pas du tout ce que tu entends par équation ci-dessus. Suivant les valeurs des coefficients, la mesure se concentre plus ou moins en certains endroits du carré, elle n'est pas du tout uniforme. La mesure de carrés d'une même catégorie (si je comprends bien ce que tu veux dire par là) dépend d'où il se trouve dans le carré, par l'intermédiaire de toute son ascendance. Donc je ne vois pas comment tu peux raisonner en proportion de surface occupée. Mais ceci dit, continue ! Tu es peut-être sur un truc.

Ben, quand tu te reliras demain, tu verras que tu ne communiques pas, là...:S

Si je comprends bien, ce que tu décris au début c'est l'algorithme du "coin toss" pour engendrer l'attracteur d'un IFS ?

Je ne voyais pas l'IFS de samok comme ça : j'envoyais le carré de départ sur quatre carrés de côtés respectifs $\sqrt a$, etc. en conservant par exemple le milieu comme sommet commun. Mais ça détruit complètement le cercle. Dans ton cas, l'attracteur est juste le carré lui-même et le choix aléatoire est celui de quel quart on prend, avec probas respectives $a$ etc. Je ne suis pas sûr qu'il y ait un rapport direct avec le problème de départ.

Je devais vouloir dire un truc dans le genre suivant (ce qui ne préjuge pas de sa pertinence):


On exprime plutôt les mesures des carrés dyadiques en fonction de leur surface

Donc, étant donné C un carré dyadique, on note p(C) le nombre sa mesure/sa surface.

Soit C un carré, et $c_0..c_3$ ses 4 fils, énumérés dans le sens des aiguilles d'une montre.

le problème exige que $4p(C)=ap(c_0)+..+dp(c_3)$

Soient u,v,w,z 4 nombres compris entre 0 et 1 tels que:

4u=au+bv+cw+dz
4v=av+bw+cz+du
4w=aw+bz+cu+dv
4z=az+bu+cv+dw


avec a+b+c+d=1 donnés dès le départ et donc u+v+w+z=1

On partitionne les carrés dyadiques en 4 ensembles $E_0..E_4$ tels que:

(rien n'indique que ce soit possible)

Les carrés dans $E_0$ ont leur fils $c_0$ dans $E_0$.
Les carrés dans $E_1$ ont leur fils $c_1$ dans $E_0$.
Les carrés dans $E_2$ ont leur fils $c_2$ dans $E_0$.
Les carrés dans $E_3$ ont leur fils $c_3$ dans $E_0$.
Les carrés dans $E_0$ ont leur fils $c_1$ dans $E_1$.
Les carrés dans $E_1$ ont leur fils $c_2$ dans $E_1$.
....

Les carrés dans $E_0$ ont leur fils $c_1$ dans $E_2$.
...


Autrement dit, un carré dans $E_i$ a son fils $c_j$ dans $E_{j-i modulo 4}$

Décrétons que pour tout carré $c$ dans $E_0$: $p(c)=u$;
Décrétons que pour tout carré $c$ dans $E_1$: $p(c)=v$;
Décrétons que pour tout carré $c$ dans $E_2$: $p(c)=w$;
Décrétons que pour tout carré $c$ dans $E_3$: $p(c)=z$;

Quels sont les conditions du problème qui m'empèchent d'y croire (je veux dire: qui entrent en contradiction avec cette hypothèse)?

Remarque : en effet, il s'agit de l'algo pour engendrer l'attracteur ; sauf qu'au lieu de regarder simplement les points qui seront visités, on s'intéresse de plus à la distribution statistique des points obtenus. Le mesure de proba correspondante vérifie la même équation d'autosimilarité que celle de samok donc c'est la même mesure. Du coup on peut poser la question autrement : quelle est la proba de tomber dans le cercle ? Il y a peut-être même un peu d'ergodicité là-dedans : quelle est la proportion asymptotique de temps passé dans le cercle par une orbite ? Bon cela dit je ne suis pas sûr que ça apporte quelquechose...

Oui c'est ça ! Au niveau théorique je pense que ça apporte plus de complications qu'autre chose mais numériquement ça donne une alternative pour estimer la mesure du disque (Monte Carlo, miam miam).

Ouah trop beau ! Je vais essayer de faire de même tout seul comme un grand mais bon il y a des chances que je craque, à ce moment-là tu m'enverras ton code dis ?

C'est vrai qu'il ne reste plus qu'à mettre un test dans la boucle pour compter le nombre de passages dans le cercle et voir si ça converge vers le 0,66... qu'avec les carrés.

Ah c'est super. Normalement la vitesse de convergence est en $\frac{1}{\sqrt{n}}$ donc effectivement pas terrible du tout. Enfin deux chiffres significatifs c'est déjà pas mal je suppose.

Merci beaucoup, à vrai dire je m'attendais à plus horrible que ça. Je vais le décortiquer et puis essayer de le laisser tourneravec un gros itermax (mais j'ai souvent des problèmes de stacksize). En plus je vois quelles lignes intervertir si je veux dessiner tous les points, ça se voit que je fais des progrès en programmation