Arnoux-Rauzy-Poincaré sequences
26 février 2015 | Catégories: sage | View CommentsIn a recent article with Valérie Berthé [BL15], we provided a multidimensional continued fraction algorithm called Arnoux-Rauzy-Poincaré (ARP) to construct, given any vector \(v\in\mathbb{R}_+^3\), an infinite word \(w\in\{1,2,3\}^\mathbb{N}\) over a three-letter alphabet such that the frequencies of letters in \(w\) exists and are equal to \(v\) and such that the number of factors (i.e. finite block of consecutive letters) of length \(n\) appearing in \(w\) is linear and less than \(\frac{5}{2}n+1\). We also conjecture that for almost all \(v\) the contructed word describes a discrete path in the positive octant staying at a bounded distance from the euclidean line of direction \(v\).
In Sage, you can construct this word using the next version of my package slabbe-0.2 (not released yet, email me to press me to finish it). The one with frequencies of letters proportionnal to \((1, e, \pi)\) is:
sage: from slabbe.mcf import algo sage: D = algo.arp.substitutions() sage: it = algo.arp.coding_iterator((1,e,pi)) sage: w = words.s_adic(it, repeat(1), D) word: 1232323123233231232332312323123232312323...
The factor complexity is close to 2n+1 and the balance is often less or equal to three:
sage: w[:10000].number_of_factors(100) 202 sage: w[:100000].number_of_factors(1000) 2002 sage: w[:1000].balance() 3 sage: w[:2000].balance() 3
Note that bounded distance from the euclidean line almost surely was proven in [DHS2013] for Brun algorithm, another MCF algorithm.
Other approaches: Standard model and billiard sequences
Other approaches have been proposed to construct such discrete lines.
One of them is the standard model of Eric Andres [A03]. It is also equivalent to billiard sequences in the cube. It is well known that the factor complexity of billiard sequences is quadratic \(p(n)=n^2+n+1\) [AMST94]. Experimentally, we can verify this. We first create a billiard word of some given direction:
sage: from slabbe import BilliardCube sage: v = vector(RR, (1, e, pi)) sage: b = BilliardCube(v) sage: b Cubic billiard of direction (1.00000000000000, 2.71828182845905, 3.14159265358979) sage: w = b.to_word() sage: w word: 3231232323123233213232321323231233232132...
We create some prefixes of \(w\) that we represent internally as char*. The creation is slow because the implementation of billiard words in my optional package is in Python and is not that efficient:
sage: p3 = Word(w[:10^3], alphabet=[1,2,3], datatype='char') sage: p4 = Word(w[:10^4], alphabet=[1,2,3], datatype='char') # takes 3s sage: p5 = Word(w[:10^5], alphabet=[1,2,3], datatype='char') # takes 32s sage: p6 = Word(w[:10^6], alphabet=[1,2,3], datatype='char') # takes 5min 20s
We see below that exactly \(n^2+n+1\) factors of length \(n<20\) appears in the prefix of length 1000000 of \(w\):
sage: A = ['n'] + range(30) sage: c3 = ['p_(w[:10^3])(n)'] + map(p3.number_of_factors, range(30)) sage: c4 = ['p_(w[:10^4])(n)'] + map(p4.number_of_factors, range(30)) sage: c5 = ['p_(w[:10^5])(n)'] + map(p5.number_of_factors, range(30)) # takes 4s sage: c6 = ['p_(w[:10^6])(n)'] + map(p6.number_of_factors, range(30)) # takes 49s sage: ref = ['n^2+n+1'] + [n^2+n+1 for n in range(30)] sage: T = table(columns=[A,c3,c4,c5,c6,ref]) sage: T n p_(w[:10^3])(n) p_(w[:10^4])(n) p_(w[:10^5])(n) p_(w[:10^6])(n) n^2+n+1 +----+-----------------+-----------------+-----------------+-----------------+---------+ 0 1 1 1 1 1 1 3 3 3 3 3 2 7 7 7 7 7 3 13 13 13 13 13 4 21 21 21 21 21 5 31 31 31 31 31 6 43 43 43 43 43 7 52 55 56 57 57 8 63 69 71 73 73 9 74 85 88 91 91 10 87 103 107 111 111 11 100 123 128 133 133 12 115 145 151 157 157 13 130 169 176 183 183 14 144 195 203 211 211 15 160 223 232 241 241 16 176 253 263 273 273 17 192 285 296 307 307 18 208 319 331 343 343 19 224 355 368 381 381 20 239 392 407 421 421 21 254 430 448 463 463 22 268 470 491 507 507 23 282 510 536 553 553 24 296 552 583 601 601 25 310 596 632 651 651 26 324 642 683 703 703 27 335 687 734 757 757 28 345 734 787 813 813 29 355 783 842 871 871
Billiard sequences generate paths that are at a bounded distance from an euclidean line. This is equivalent to say that the balance is finite. The balance is defined as the supremum value of difference of the number of apparition of a letter in two factors of the same length. For billiard sequences, the balance is 2:
sage: p3.balance() 2 sage: p4.balance() # takes 2min 37s 2
Other approaches: Melançon and Reutenauer
Melançon and Reutenauer [MR13] also suggested a method that generalizes Christoffel words in higher dimension. The construction is based on the application of two substitutions generalizing the construction of sturmian sequences. Below we compute the factor complexity and the balance of some of their words over a three-letter alphabet.
On a three-letter alphabet, the two morphisms are:
sage: L = WordMorphism('1->1,2->13,3->2') sage: R = WordMorphism('1->13,2->2,3->3') sage: L WordMorphism: 1->1, 2->13, 3->2 sage: R WordMorphism: 1->13, 2->2, 3->3
Example 1: periodic case \(LRLRLRLRLR\dots\). In this example, the factor complexity seems to be around \(p(n)=2.76n\) and the balance is at least 28:
sage: from itertools import repeat, cycle sage: W = words.s_adic(cycle((L,R)),repeat('1')) sage: W word: 1213122121313121312212212131221213131213... sage: map(W[:10000].number_of_factors, [10,20,40,80]) [27, 54, 110, 221] sage: [27/10., 54/20., 110/40., 221/80.] [2.70000000000000, 2.70000000000000, 2.75000000000000, 2.76250000000000] sage: W[:1000].balance() # takes 1.6s 21 sage: W[:2000].balance() # takes 6.4s 28
Example 2: \(RLR^2LR^4LR^8LR^{16}LR^{32}LR^{64}LR^{128}\dots\) taken from the conclusion of their article. In this example, the factor complexity seems to be \(p(n)=3n\) and balance at least as high (=bad) as \(122\):
sage: W = words.s_adic([R,L,R,R,L,R,R,R,R,L]+[R]*8+[L]+[R]*16+[L]+[R]*32+[L]+[R]*64+[L]+[R]*128,'1') sage: W.length() 330312 sage: map(W.number_of_factors, [10, 20, 100, 200, 300, 1000]) [29, 57, 295, 595, 895, 2981] sage: [29/10., 57/20., 295/100., 595/200., 895/300., 2981/1000.] [2.90000000000000, 2.85000000000000, 2.95000000000000, 2.97500000000000, 2.98333333333333, 2.98100000000000] sage: W[:1000].balance() # takes 1.6s 122 sage: W[:2000].balance() # takes 6s 122
Example 3: some random ones. The complexity \(p(n)/n\) occillates between 2 and 3 for factors of length \(n=1000\) in prefixes of length 100000:
sage: for _ in range(10): ....: W = words.s_adic([choice((L,R)) for _ in range(50)],'1') ....: print W[:100000].number_of_factors(1000)/1000. 2.02700000000000 2.23600000000000 2.74000000000000 2.21500000000000 2.78700000000000 2.52700000000000 2.85700000000000 2.33300000000000 2.65500000000000 2.51800000000000
For ten randomly generated words, the balance goes from 6 to 27 which is much more than what is obtained for billiard words or by our approach:
sage: for _ in range(10): ....: W = words.s_adic([choice((L,R)) for _ in range(50)],'1') ....: print W[:1000].balance(), W[:2000].balance() 12 15 8 24 14 14 5 11 17 17 14 14 6 6 19 27 9 16 12 12
References
[BL15] | V. Berthé, S. Labbé, Factor Complexity of S-adic words generated by the Arnoux-Rauzy-Poincaré Algorithm, Advances in Applied Mathematics 63 (2015) 90-130. http://dx.doi.org/10.1016/j.aam.2014.11.001 |
[DHS2013] | Delecroix, Vincent, Tomás Hejda, and Wolfgang Steiner. “Balancedness of Arnoux-Rauzy and Brun Words.” In Combinatorics on Words, 119–31. Springer, 2013. http://link.springer.com/chapter/10.1007/978-3-642-40579-2_14. |
[A03] | E. Andres, Discrete linear objects in dimension n: the standard model, Graphical Models 65 (2003) 92-111. |
[AMST94] | P. Arnoux, C. Mauduit, I. Shiokawa, J. I. Tamura, Complexity of sequences defined by billiards in the cube, Bull. Soc. Math. France 122 (1994) 1-12. |
[MR13] | G. Melançon, C. Reutenauer, On a class of Lyndon words extending Christoffel words and related to a multidimensional continued fraction algorithm. J. Integer Seq. 16, No. 9, Article 13.9.7, 30 p., electronic only (2013). https://cs.uwaterloo.ca/journals/JIS/VOL16/Reutenauer/reut3.html |
Monsieur Coderre a raison de parler de la qualité des terrains... d'ultimate
27 janvier 2015 | Catégories: ultimate | View CommentsComme l'a annoncé Radio-Canada cette semaine, "le maire de Montréal, Denis Coderre, veut promouvoir le baseball. Pour ce faire, il annonce entre autres un investissement de 11 millions de dollars pour la réfection des terrains de balle municipaux, dont plusieurs sont en mauvais état". Cette nouvelle m'a fait réaliser plusieurs choses.
Premièrement, oui, on a le droit de considérer la qualité des terrains sur lesquels on pratique notre sport. Je ne m'étais jamais posé cette question toutes les soirées où j'ai pratiqué avec Méphisto les soirs de semaines sur les terrains secs, argileux et si mal drainés de l'Hôpital Douglas à Verdun. Je n'avais jamais remis en question la qualité des terrains au centre de l'anneau de l'Hippodrome à Montréal au milieu des années 2000 dans la ligue du mardi avec les Smileys. Un terrain où la pelouse ressemble étrangement à du sable dur et où le foin atteint les 30 cm de hauteur.
Deuxièmement, une ville peut financer des installations sportives. Ça non plus, je ne savais pas que ça se pouvait. Je croyais que la seule possibilité était que nous autres, joueurs et joueuses d'ultimate, paient comme l'Association d'ultimate de Montréal (AUM) l'a fait dans Rosemont en 2010 en investissant 50000$ pour retaper un terrain ou encore l'Association des joueuses et joueurs d'ultimate de Québec (AJJUQ) l'a fait dans les années 2000 en investissant elle aussi plusieurs milliers de dollars pour développer le Parc d'ultimate de Québec (PUQ) situé sous les lignes à haute tension de pilônes électriques d'Hydro-Québec (quoi de plus normal?). Sinon, je pensais que la seule façon de pratiquer mon sport était de trouver un terrain encerclé par les voies d'accès du pont Jacques-Cartier. L'avantage de ce terrain du parc Faubourg est qu'il est toujours libre, car personne n'a le goût d'être là. Et surtout, suivez le conseil de l'association en vous installant "le plus près possible du pont, car c'est de là que le terrain est le plus beau!".

Troisièmement, de l'éclairage, ça existe. Dans l'article de Radio-Canada, "on parle notamment de mettre l'accent sur le drainage et l'éclairage". Le drainage, je ne peux pas en parler, car je n'ai jamais eu l'occasion de jouer sur un terrain drainé. Mais l'éclairage, ça je sais ce que c'est. Mais je n'avais pas pensé qu'on pouvait s'en servir pour utiliser un terrain d'ultimate en soirée. Comme c'est brillant! Je m'étais habitué à faire des pratiques d'ultimate écourtées de 30 minutes dans un parc au mois d'août juste avant les Championnats canadiens, car il ne faisait plus assez clair pour jouer sans se blesser. J'avais toujours trouvé géniale et naturelle la politique de temps de jeu maximum de l'AUM basée sur le coucher du soleil: au crépuscule, le match est terminé peu importe le pointage. L'heure du coucher du soleil est connue à l'avance par les deux capitaines selon des calculs de météo média et elle détermine l'heure de la fin du match à la minute près selon la date du match. Les matchs se terminent quand dans les autres sports?
Notons, il faut le dire, que le développement des installations sportives pour les autres sports (football, soccer, volley ball de plage) bénéficie aussi à l'ultimate. L'hiver, les Montréalais n'ont plus à faire 40 minutes de voiture pour jouer un match d'ultimate à 23h10 un mardi soir à Saint-Jean-sur-Richelieu. Depuis les 5 ou 6 dernières années, de nouveaux plateaux de soccer intérieur et dômes gonflés sur des terrains extérieur en synthétique ont vu le jour à Laval, à Longueuil, au campus Loyola de l'Université Concordia et au Stade Hébert (Crémazie et Viau). Cela a permis d'accueillir une forte croissance de la pratique de l'ultimate en hiver. Donc, ça oui, je le savais quand même un peu: les investissements en installations sportives faites pour d'autres sports profitent aussi à l'ultimate lorsque nous avons accès à ces plateaux. Il ne faut pas tenir cela pour acquis comme se le demandait récemment Philippe Thivierge. En France par exemple, le soccer s'approprie toutes les plages horaires et laisse des miettes à l'ultimate sinon rien.
Comme le baseball, l'ultimate connaît aussi une progression annuelle de 5 à 10% du nombre de participants pour un total de plus de 6000 joueurs et joueuses au Québec en 2014. Aussi, l'ultimate a l'avantage de rejoindre dans des proportions beaucoup plus équilibrées tant les femmes que les hommes, proportion que j'évaluerais à 40%-60% (à confirmer par la fédération). Finalement, l'ultimate possède déjà son équipe professionnelle d'ultimate, le Royal... dont le nom a peut-être été inspiré du baseball. Si je ne me trompe pas le Royal a déjà attiré plus de spectateurs que la plus petite foule de l'histoire des Expos (2134 personnes le 5 septembre 2002 selon cet article de RDS), c'est déjà ça!
Selon l'article de Radio-Canada, il y aurait 27000 joueurs de baseball dans la province. Soyons donc honnête et raisonnable dans nos demandes comme nous l'avons toujours été. Optons pour la répartition proportionnelle: \[ \frac{6000}{27000 + 6000} \times 11\,000\,000 $ = 2\,000\,000 $ \] Tout spécialiste de la négociation sera d'accord pour dire qu'une répartition proportionnelle est juste. Ainsi, soyons honnête et laissons 9 des 11 millions $ de l'investissement de Monsieur Coderre pour le baseball et conservons seulement ce que nous méritons, c'est-à-dire la différence de 2 millions $ pour faire des investissements sur l'île de Montréal pour construire des installations en bons états (terrains drainés, éclairés avec estrades) pour la pratique de l'ultimate.
Et vous, pensez-vous que l'ultimate mérite une attention de la part des municipalités comme le suggère la fin de l'article de La Presse sur le même sujet?
Échelles de points proposées pour la saison 2014-15 du CQU4
29 septembre 2014 | Catégories: ultimate | View CommentsLes points par tournois tels qu'ils sont depuis 2011:

Les points par tournois que je suggère d'utiliser pour la saison 2014-15:

Avec ces échelles de points, une équipe qui gagne un tournoi de la Série 666 obtient autant de points qu'une équipe finissant 12e dans un tournoi de la Série 1000. Pareillement, une équipe qui gagne un tournoi de la Série 333 obtient autant de points qu'une équipe finissant environ 12e dans un tournoi de Série 666.
Concrètement les tournois de la Série 666 seront payant pour les équipes du 16-32 voulant se tailler une place dans le top 16. Et les tournois de la Série 333 seront payant pour les équipes du 32-50 voulant se tailler une place dans le top 32.
Il y aura maintenant trois Séries, chaque série possédant au plus 4 tournois pour favoriser les rencontres entre équipes du même niveau.
Série 1000:
- Les tournois des grands centres (Montréal, Trois-Rivières, Sherbrooke, Québec)
- Movember, Bye Bye, Coup de Foudre (et le Mars Attaque ou non pour cette année?)
- Dans un complexe de gazon synthétique intérieur
- 6 ou 7 parties par équipe sur deux jours
- Les 100 premières équipes obtiennent des points
- L'équipe gagnante obtient 1000 points
- Trois équipes obtiennent 50 points pour l'esprit sportif
Série 666:
- Les tournois des régions plus élgoinées, possiblement dans des gymnases
- St-Jean-sur-Richelieu, Gatineau, Rimouski, Saguenay
- October Disk, Bonne année, La Flotte, La Virée
- Dans un complexe de gazon synthétique intérieur ou dans des gymnases
- 6 ou 7 parties par équipe sur deux jours
- Les 50 premières équipes obtiennent des points
- L'équipe gagnante obtient 666 points
- Trois équipes obtiennent 50 points pour l'esprit sportif
Série 333:
- Nouveaux tournois organisés à Terrebonne, Drumondville, Granby, Saint-Hyacinthe, etc.
- Ou encore tournois dans les grands centres comme Sherbrooke, Québec, Montréal ou Trois-Rivières.
- Il pourrait en avoir un ou deux cette année dans la perspective d'un nouveau tournoi par année.
- Dans un complexe de gazon synthétique intérieur ou dans des gymnases
- 4 à 7 parties par équipe sur un ou deux journées
- Les 24 premières équipes obtiennent des points
- L'équipe gagnante obtient 333 points
- Trois équipes obtiennent 50 points pour l'esprit sportif
- Les tournois de la Séries 333 pourront agir comme tournoi de qualification pour les tournois contingentés de la Série 1000. Par exemple, le top 8 d'un tournoi de la Série 333 pourraient obtenir un laisser-passer pour le Coup de Foudre.
La Série 333 comme tournois de qualification
Concrètement, je pense que ce serait intéressant de créer un tournoi de la Série 333 dès cette année dans les semaines précédents le Coup de Foudre. Ce tournoi pourrait être organisé à Sherbrooke ou ailleurs comme Granby ou une autre ville. Ensuite, s'il y a 48 places pour le Coup de Foudre, elles pourraient être réparties de la façon suivante: 32 équipes provenant grosso moddo du top 32 de la FQU ayant répondu aux critères de sélection, 8 équipes locales choisies par l'AUS, et 8 équipes qualifiées via le tournoi de la Série 333. Si le tournoi de la Série 333 n'est pas trop organisé à l'avance, cela permet de dévier les inscriptions en surplus du Coup de Foudre vers ce tournoi de qualification.
L'idée d'avoir des tournois de qualifications est, je pense, la direction vers laquelle nous devons aller pour désengorger les tournois de la Série 1000 ne pouvant accueillir plus d'une cinquantaine d'équipes et obligés de refuser une vingtaine d'équipes. C'est logique et utilisé dans les autres sports (surf, tennis par exemple).
Les tableaux pour avoir les chiffres exacts:
Position | Série 1000 | Série 666 | Série 333 |
1 | 1000 | 666 | 333 |
2 | 955 | 614 | 286 |
3 | 916 | 570 | 248 |
4 | 881 | 530 | 216 |
5 | 848 | 495 | 188 |
6 | 817 | 462 | 163 |
7 | 788 | 432 | 141 |
8 | 761 | 404 | 122 |
9 | 735 | 378 | 104 |
10 | 710 | 354 | 89 |
11 | 686 | 331 | 75 |
12 | 663 | 309 | 63 |
13 | 641 | 288 | 52 |
14 | 620 | 269 | 42 |
15 | 599 | 251 | 34 |
16 | 580 | 234 | 26 |
17 | 561 | 217 | 20 |
18 | 542 | 202 | 15 |
19 | 524 | 187 | 10 |
20 | 507 | 173 | 7 |
21 | 490 | 160 | 4 |
22 | 474 | 148 | 2 |
23 | 458 | 136 | 1 |
24 | 443 | 125 | 1 |
25 | 428 | 114 | 0 |
26 | 413 | 104 | 0 |
27 | 399 | 95 | 0 |
28 | 386 | 86 | 0 |
29 | 372 | 78 | 0 |
30 | 360 | 70 | 0 |
31 | 347 | 63 | 0 |
32 | 335 | 56 | 0 |
33 | 323 | 49 | 0 |
34 | 311 | 44 | 0 |
35 | 300 | 38 | 0 |
36 | 289 | 33 | 0 |
37 | 278 | 28 | 0 |
38 | 268 | 24 | 0 |
39 | 258 | 20 | 0 |
40 | 248 | 17 | 0 |
41 | 239 | 14 | 0 |
42 | 229 | 11 | 0 |
43 | 220 | 9 | 0 |
44 | 211 | 7 | 0 |
45 | 203 | 5 | 0 |
46 | 194 | 3 | 0 |
47 | 186 | 2 | 0 |
48 | 178 | 2 | 0 |
49 | 171 | 1 | 0 |
50 | 163 | 1 | 0 |
51 | 156 | 0 | 0 |
52 | 149 | 0 | 0 |
53 | 142 | 0 | 0 |
54 | 136 | 0 | 0 |
55 | 129 | 0 | 0 |
56 | 123 | 0 | 0 |
57 | 117 | 0 | 0 |
58 | 111 | 0 | 0 |
59 | 105 | 0 | 0 |
60 | 100 | 0 | 0 |
61 | 95 | 0 | 0 |
62 | 89 | 0 | 0 |
63 | 85 | 0 | 0 |
64 | 80 | 0 | 0 |
65 | 75 | 0 | 0 |
66 | 71 | 0 | 0 |
67 | 66 | 0 | 0 |
68 | 62 | 0 | 0 |
69 | 58 | 0 | 0 |
70 | 54 | 0 | 0 |
71 | 51 | 0 | 0 |
72 | 47 | 0 | 0 |
73 | 44 | 0 | 0 |
74 | 40 | 0 | 0 |
75 | 37 | 0 | 0 |
76 | 34 | 0 | 0 |
77 | 31 | 0 | 0 |
78 | 29 | 0 | 0 |
79 | 26 | 0 | 0 |
80 | 24 | 0 | 0 |
81 | 21 | 0 | 0 |
82 | 19 | 0 | 0 |
83 | 17 | 0 | 0 |
84 | 15 | 0 | 0 |
85 | 14 | 0 | 0 |
86 | 12 | 0 | 0 |
87 | 10 | 0 | 0 |
88 | 9 | 0 | 0 |
89 | 8 | 0 | 0 |
90 | 6 | 0 | 0 |
91 | 5 | 0 | 0 |
92 | 4 | 0 | 0 |
93 | 4 | 0 | 0 |
94 | 3 | 0 | 0 |
95 | 2 | 0 | 0 |
96 | 2 | 0 | 0 |
97 | 1 | 0 | 0 |
98 | 1 | 0 | 0 |
99 | 1 | 0 | 0 |
100 | 1 | 0 | 0 |
Abelian complexity of the Oldenburger sequence
27 septembre 2014 | Catégories: sage | View CommentsThe Oldenburger infinite sequence [O39] \[ K = 1221121221221121122121121221121121221221\ldots \] also known under the name of Kolakoski, is equal to its exponent trajectory. The exponent trajectory \(\Delta\) can be obtained by counting the lengths of blocks of consecutive and equal letters: \[ K = 1^12^21^22^11^12^21^12^21^22^11^22^21^12^11^22^11^12^21^22^11^22^11^12^21^12^21^22^11^12^21^12^11^22^11^22^21^12^21^2\ldots \] The sequence of exponents above gives the exponent trajectory of the Oldenburger sequence: \[ \Delta = 12211212212211211221211212\ldots \] which is equal to the original sequence \(K\). You can define this sequence in Sage:
sage: K = words.KolakoskiWord() sage: K word: 1221121221221121122121121221121121221221... sage: K.delta() # delta returns the exponent trajectory word: 1221121221221121122121121221121121221221...
There are a lot of open problem related to basic properties of that sequence. For example, we do not know if that sequence is recurrent, that is, all finite subword or factor (finite block of consecutive letters) always reappear. Also, it is still open to prove whether the density of 1 in that sequence is equal to \(1/2\).
In this blog post, I do some computations on its abelian complexity \(p_{ab}(n)\) defined as the number of distinct abelian vectors of subwords of length \(n\) in the sequence. The abelian vector \(\vec{w}\) of a word \(w\) counts the number of occurences of each letter: \[ w = 12211212212 \quad \mapsto \quad 1^5 2^7 \text{, abelianized} \quad \mapsto \quad \vec{w} = (5, 7) \text{, the abelian vector of } w \]
Here are the abelian vectors of subwords of length 10 and 20 in the prefix of length 100 of the Oldenburger sequence. The functions abelian_vectors and abelian_complexity are not in Sage as of now. Code is available at trac #17058 to be merged in Sage soon:
sage: prefix = words.KolakoskiWord()[:100] sage: prefix.abelian_vectors(10) {(4, 6), (5, 5), (6, 4)} sage: prefix.abelian_vectors(20) {(8, 12), (9, 11), (10, 10), (11, 9), (12, 8)}
Therefore, the prefix of length 100 has 3 vectors of subwords of length 10 and 5 vectors of subwords of length 20:
sage: p100.abelian_complexity(10) 3 sage: p100.abelian_complexity(20) 5
I import the OldenburgerSequence from my optional spkg because it is faster than the implementation in Sage:
sage: from slabbe import KolakoskiWord as OldenburgerSequence sage: Olden = OldenburgerSequence()
I count the number of abelian vectors of subwords of length 100 in the prefix of length \(2^{20}\) of the Oldenburger sequence:
sage: prefix = Olden[:2^20] sage: %time prefix.abelian_vectors(100) CPU times: user 3.48 s, sys: 66.9 ms, total: 3.54 s Wall time: 3.56 s {(47, 53), (48, 52), (49, 51), (50, 50), (51, 49), (52, 48), (53, 47)}
Number of abelian vectors of subwords of length less than 100 in the prefix of length \(2^{20}\) of the Oldenburger sequence:
sage: %time L100 = map(prefix.abelian_complexity, range(100)) CPU times: user 3min 20s, sys: 1.08 s, total: 3min 21s Wall time: 3min 23s sage: from collections import Counter sage: Counter(L100) Counter({5: 26, 6: 26, 4: 17, 7: 15, 3: 8, 8: 4, 2: 3, 1: 1})
Let's draw that:
sage: labels = ('Length of factors', 'Number of abelian vectors') sage: title = 'Abelian Complexity of the prefix of length $2^{20}$ of Oldenburger sequence' sage: list_plot(L100, color='green', plotjoined=True, axes_labels=labels, title=title)

It seems to grow something like \(\log(n)\). Let's now consider subwords of length \(2^n\) for \(0\leq n\leq 12\) in the same prefix of length \(2^{20}\):
sage: %time L20 = [(2^n, prefix.abelian_complexity(2^n)) for n in range(20)] CPU times: user 41 s, sys: 239 ms, total: 41.2 s Wall time: 41.5 s sage: L20 [(1, 2), (2, 3), (4, 3), (8, 3), (16, 3), (32, 5), (64, 5), (128, 9), (256, 9), (512, 13), (1024, 17), (2048, 22), (4096, 27), (8192, 40), (16384, 46), (32768, 67), (65536, 81), (131072, 85), (262144, 90), (524288, 104)]
I now look at subwords of length \(2^n\) for \(0\leq n\leq 23\) in the longer prefix of length \(2^{24}\):
sage: prefix = Olden[:2^24] sage: %time L24 = [(2^n, prefix.abelian_complexity(2^n)) for n in range(24)] CPU times: user 20min 47s, sys: 13.5 s, total: 21min Wall time: 20min 13s sage: L24 [(1, 2), (2, 3), (4, 3), (8, 3), (16, 3), (32, 5), (64, 5), (128, 9), (256, 9), (512, 13), (1024, 17), (2048, 23), (4096, 33), (8192, 46), (16384, 58), (32768, 74), (65536, 98), (131072, 134), (262144, 165), (524288, 229), (1048576, 302), (2097152, 371), (4194304, 304), (8388608, 329)]
The next graph gather all of the above computations:
sage: G = Graphics() sage: legend = 'in the prefix of length 2^{}' sage: G += list_plot(L24, plotjoined=True, thickness=4, color='blue', legend_label=legend.format(24)) sage: G += list_plot(L20, plotjoined=True, thickness=4, color='red', legend_label=legend.format(20)) sage: G += list_plot(L100, plotjoined=True, thickness=4, color='green', legend_label=legend.format(20)) sage: labels = ('Length of factors', 'Number of abelian vectors') sage: title = 'Abelian complexity of Oldenburger sequence' sage: G.show(scale=('semilogx', 2), axes_labels=labels, title=title)

A linear growth in the above graphics with logarithmic \(x\) abcisse would mean a growth in \(\log(n)\). After those experimentations, my hypothesis is that the abelian complexity of the Oldenburger sequence grows like \(\log(n)^2\).
References
[O39] | Oldenburger, Rufus (1939). "Exponent trajectories in symbolic dynamics". Transactions of the American Mathematical Society 46: 453–466. doi:10.2307/1989933 |
Projections de croissance du CQU4
14 septembre 2014 | Catégories: ultimate | View CommentsVoici quelques dessins de l'évolution du Circuit québécois d'ultimate 4 contre 4 (CQU4).
Croissance de la participation aux tournois
Le premier ci-bas montre le nombre de participations à chaque tournoi de la saison. C'est un dessin que j'avais déjà fait et que j'ai simplement mis à jour. Pendant la saison 2013-2014, il y a eu un total de 427 participations aux tournois du CQU4. La croissance est de 30 à 60 participations de plus par années. On peut donc imaginer qu'il y aura plus de 500 participations dans le circuit d'ici deux à trois ans si la tendance se maintient.

Croissance en hauteur vs largeur
Il y deux façons d'accueillir de nouvelles équipes:
- créer de nouveaux tournois (croissance en largeur),
- augmenter la taille des tournois existants (croissance en hauteur).
On a été plutôt négligeant sur la croissance en largeur avec la création d'un seul nouveau tournoi au cours des cinq dernières années (de 7 tournois en 2008-2009, il y en avait que 8 en 2013-2014). Par contre, augmenter la taille des tournois existants, ça on sait faire. Inspiré par le Mars Attaque qui grandit en repoussant toutes les limites, nous avons assis la croissance des cinq dernières années en acceptant toujours plus d'équipes dans les tournois. Alors qu'il y avait en moyenne 30 équipes par tournois en 2008-2009, il y en avait 50 la saison dernière. Le dessin suivant illustre la croissance des deux façons:

Les données ayant permis de faire les graphes ci-haut sont dans le tableau ci-bas:
Année | FEN | BB | CdF | MA | LF | LV | MO | OD | BA | Somme | Nombre de tournois | Moyenne |
---|---|---|---|---|---|---|---|---|---|---|---|---|
2000-01 | 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 1 | 7.0 |
2001-02 | 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 10 | 1 | 10.0 |
2002-03 | 13 | 10 | 10 | 10 | 0 | 0 | 0 | 0 | 0 | 43 | 4 | 10.8 |
2003-04 | 10 | 10 | 15 | 14 | 0 | 0 | 0 | 0 | 0 | 49 | 4 | 12.3 |
2004-05 | 10 | 12 | 15 | 15 | 24 | 0 | 0 | 0 | 0 | 76 | 5 | 15.2 |
2005-06 | 15 | 24 | 16 | 30 | 20 | 0 | 0 | 0 | 0 | 105 | 5 | 21.0 |
2006-07 | 18 | 36 | 28 | 24 | 24 | 0 | 0 | 0 | 0 | 130 | 5 | 26.0 |
2007-08 | 15 | 36 | 42 | 28 | 30 | 0 | 0 | 0 | 0 | 151 | 5 | 30.2 |
2008-09 | 14 | 36 | 44 | 58 | 32 | 16 | 7 | 0 | 0 | 207 | 7 | 29.5 |
2009-10 | 18 | 36 | 44 | 73 | 32 | 11 | 24 | 0 | 0 | 238 | 7 | 34.0 |
2010-11 | 15 | 52 | 44 | 88 | 32 | 9 | 40 | 16 | 0 | 296 | 8 | 37.0 |
2011-12 | 16 | 52 | 48 | 104 | 27 | 0 | 48 | 16 | 29 | 340 | 8 | 42.5 |
2012-13 | 16 | 52 | 48 | 115 | 21 | 0 | 58 | 19 | 34 | 363 | 8 | 45.3 |
2013-14 | 0 | 56 | 52 | 120 | 20 | 8 | 64 | 36 | 44 | 400 | 8 | 50.0 |
Le problème est qu'une moyenne de 50 équipes par tournoi semble être une limite physique associé à la capacité d'accueil d'un plateau de soccer intérieur (divisé en 9 terrains). Ça ne semble pas être un problème à Québec où l'AJJUQ parvient à louer un deuxième puis un troisième plateau et atteindre les 27 terrains. Mais peut-on faire la même chose dans toutes les villes du Québec? Par exemple à Sherbrooke où je ne sais pas s'il existe un deuxième plateau de soccer intérieur?
Il faut l'admettre, la croissance en hauteur atteindra sa limite. Soit on l'a déjà atteinte, soit on l'atteindra cette année, soit ce sera l'année prochaine. Mais, dans tous les cas, on l'atteindra. La seule solution à ce moment-là sera de croître en largeur en créant de nouveaux tournois. Et plus on attend, plus le déficit à rattraper sera grand. À mon avis, il faudrait qu'il y ait un nouveau tournoi par année pour accueillir la croissance moyenne annuelle de 30 à 60 participations à un tournoi vue dans le premier graphique ci-haut. Or, on a cinq années de non croissance à rattraper... Je suggère de commencer dès maintenant!
Croissance de l'adhésion au CQU4
Le graphique suivant illustre le nombre d'équipes participant à 1, 2 ou à 3 tournois ou plus. Dans le CQU4, un grand nombre d'équipe participent à un seul tournoi. C'est très encourageant, car cela signifie qu'il y a une place dans le CQU4 pour l'initiation à la compétition et pour la participation à un tournoi local. Depuis toujours, une quinzaine d'équipes participent à deux tournois. Ce sont des équipes entre deux qui participeront peut-être à trois tournois l'année suivante qui sait? Il faudrait faire plus d'investigation à leur sujet...
Puis, un nombre de plus en plus grand en font trois ou plus. Une équipe qui fait 3 tournois ou plus est une équipe qui a adhéré au CQU4 et qui désire probablement se hisser parmi les 32 meilleures équipes au Québec. Pendant trois ans de 2011 à 2013, une cinquantaine d'équipe participaient à au moins 3 tournois. Puis, l'année dernière, il y a eu une forte progression avec près de 70 équipes participant à 3 tournois ou plus. Notez aussi qu'en moyenne les équipes participant à plus de 3 tournois participent à 4 tournois (voir plus bas pour les chiffres).

On peut donc se demander à quoi pensent ces 70 équipes en ce moment. Ce sont des équipes qui voudront encore cette année participer au CQU4 dans le but de se qualifier pour le CCQU4. Le problème est que les tournois du Grand Chelem sont saturés et qu'il n'y aura pas assez de place pour eux.
Les chiffres ayant permis de construire le graphique précédent sont ci-bas. On compte le nombre d'équipes selon le nombre de tournois participés. En 2006-07, 35 équipes avaient participé à 1 tournoi, 7 équipes avaient participé à 2 tournois, 9 équipes avaient participé à 3 tournois, etc.
Année | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Total |
---|---|---|---|---|---|---|---|---|
2006-07 | 35 | 7 | 9 | 9 | 0 | 0 | 0 | 60 |
2007-08 | 26 | 10 | 10 | 15 | 0 | 0 | 0 | 61 |
2008-09 | 48 | 13 | 14 | 12 | 9 | 0 | 0 | 96 |
2009-10 | 60 | 13 | 16 | 15 | 7 | 1 | 0 | 112 |
2010-11 | 60 | 9 | 11 | 26 | 10 | 4 | 0 | 120 |
2011-12 | 85 | 16 | 12 | 22 | 16 | 2 | 1 | 154 |
2012-13 | 89 | 16 | 9 | 25 | 15 | 3 | 1 | 158 |
2013-14 | 86 | 15 | 16 | 28 | 16 | 7 | 0 | 168 |
Ce que je pense des récentes modifications annoncées par la FQU
Plusieurs modifications ont été annoncées récemment par la FQU pour la saison 2014-2015. Voici quelques commentaires en vrac:
- Je déplore qu'il n'y ait pas de nouveaux tournois encore une fois cette année. À quand un tournoi à Lanaudière (FUL)? Drumondville? Granby? Alma? Victoriaville? À quand un tournoi de Série C (200 points) à Montréal? Québec? Trois-Rivières? Sherbrooke?
- Le pointage des tournois de Série B n'a pas été modifié. Il devrait y avoir des échelles pour 200, 400, 600, 800 et 1000 points données à l'équipe gagnante. De plus, les tournois de Série B devraient donner plus de points pour alléger la pression sur les tournois du Grand Chelem.
- Je n'aime pas tellement la décision de sortir le Mars Attaque du CQU4. À l'heure où on se demande comment accueillir les 100 prochaines participations qui viendront pour les trois prochaines années, on enlève un tournoi qui donnait des points à 120 équipes dans le CQU4. Je pense qu'on cherche vraiment à déplaire à toutes les équipes qui ne parviendront pas à atteindre les objectifs qu'ils s'étaient fixés.
- Je crois que le fait de sortir le Mars Attaque du CQU4 freinera sa croissance. Cette année, les équipes iront par habitude. Mais, selon moi, dans les prochaines années, ils auront du mal à avoir autant d'équipes que les années passées. Toute la pression sera mise sur le nouveau "dernier" tournoi du CQU4: le Coup de Foudre. Les équipes qui auront fait un seul tournoi voudront absolument se qualifier pour le Coup de Foudre. Aussi, les équipes qui voudront corriger un précdent mauvais résultat parmi le Movember et le Bye Bye vondront aussi participer au Coup de Foudre. Finalement toutes les équipes vondront participer au Coup de Foudre, car ce sera la dernière chance pour améliorer son classement et possiblement se qualifier pour le CCQU4. On peut imaginer que 70 à 90 équipes voudront participer au Coup de Foudre. Mais combien y aura-t-il de places?
- En fait, je pense que le CQU4 a toujours été plus valorisé que le CCQU4 lui-même. Plusieurs ont souvent trouvé que le CCQU4 était trop tard en avril, etc. Pour cette raison la FQU a décidé de le déplacer au Mars Attaque et donc de compter seulement 2 tournois plutôt que 3 dans la saison. Je pense qu'il existe d'autres solutions à ce problème telle que faire le CCQU4 dehors au mois d'avril ou simplemenent annuler le CCQU4. L'équipe championne est celle qui termine première au classement. Et on utilise le classement du CQU4 pour qualifier les équipes pour le Championnat canadien. Ce n'est pas nécessaire que les équipes passent par le CCQU4 pour aller aux championnats canadiens. On pourrait décider que le top 5 du CQU4 vont aux championnats canadiens et que le 6-32 vont aux championnats québécois organisé en mème temps que les championnats canadiens.
- Je pense qu'un classement du CQU4 en comptant les trois meilleurs résultats est plus authentique que si on compte que les deux meilleurs résultats. Il y a peut-être des surprises à prévoir de ce côté. On verra. J'ai pensé au système d'échelle de pointage en fonction de trois tournois. J'ai fait plusieurs simulations et tout qui me garrantissent que ça marche bien pour trois tournois. Mais, si ça avait été deux tournois seulement, je l'aurais probablement fait l'échelle différement. En comptant deux tournois, il faut que l'échelle dégringole moins vite pour permettre aux équipes de dépasser les autres (il leur reste juste une chance pour les dépasser). En comparaison, au tennis (ATP et WTA ranking) l'échelle dégringole très très très vite. C'est OK, car on compte les 18 meilleurs résultats et il te reste donc une chance de dépasser Serena Williams si elle gagne le premier tournoi. Mais si on en compte que deux, il ne faudrait pas que Serena soit assurée d'être classée dans le top 8 juste parce qu'elle a fait une finale tsé...
« Previous Page -- Next Page »