En 2013, j'avais écrit cet article d'opinions au sujet de l'organisation de l'ultimate en France. Certaines choses ont évolué pour le mieux depuis (un match d'ultimate pour décider de la meilleure équipe d'ultimate en France) d'autres non. Aujourd'hui, en 2015, j'ai trois propositions à suggérer à la fédération française d'ultimate (FFDF) et je vais les décrire dans trois messages de blogue distincts au fur et à la mesure que je trouve le temps pour les rédiger. Ma première proposition concernait la mise à jour de la règle de bris d'égalité. Ma deuxième proposition concerne la restructuration du Championnat de France et c'est celle que je décris dans ce texte.

Il peut sembler naturel dans le vieux continent de structurer le Championnat de France d'ultimate en divisions (division I, II, III, régionales). C'est comme ça qu'ils font pour le soccer, alors pourquoi pas pour l'ultimate? Aussi, ça fait cool et respectable de dire que "je joue en division 1", car c'est comme ça pour le foot, le hand, le basket, etc. Mais, mes yeux de Québécois ont toujours de la difficulté à comprendre comment on peut avoir besoin de tant de divisions en France pour structurer à peine 2500 joueurs d'ultimate. Il y a 3300 joueurs à Montréal, près de 6000 au Québec, 30 000 au Canada et on ne fait pas un plat avec ça. À chaque année, il y a juste une équipe championne par catégorie (masculine, féminine, mixte, maître, junior) et n'importe quel club peut être champion du Québec comme du Canada à chaque année.

Un bon Championnat national se doit de...

Un bon Championnat du Canada, du Québec, des États-Unis, de la France ou de n'importe quel pays devrait s'assurer de rassembler les meilleures équipes du pays. Pourquoi? D'abord, parce qu'on ne choisit pas l'équipe championne d'un pays au hasard, on la choisie parmi les meilleures équipes. Mais surtout que c'est en jouant contre des bonnes équipes que les bonnes équipes deviennent très bonnes. C'est le niveau de jeu du top 10 au pays qui pousse la meilleure équipe à devenir encore meilleure sinon à être remplacée par une équipe meilleure. Pourquoi pensez-vous que Revolver sont si bons? Parce qu'ils font des beaux highlight real sur youtube? Non, simplement parce qu'ils ont pas le choix avec les équipes du top 10 américain qui veulent aussi être champions. Bref, le niveau de jeu d'un pays augmente en rassemblant les meilleures équipes au pays à son Championnat national.

Maintenant que nous sommes d'accord pour dire qu'un Championnat de France devrait rassembler les meilleures équipes pour élire l'équipe championne, vous comprennez pourquoi je n'aime pas le Championnat de France actuel séparé en divisions. La division 1 ne rassemble pas et ne rassemblera jamais les douze meilleurs clubs de France. Plusieurs indices le prouvent:

• Les clubs de la D2 qui monte en D1 sont meilleurs que plusieurs clubs de D1.
• Certains clubs de D1 sont en restructuration. Il sont en D1 grâce à de bonnes performances du passé et à de bons joueurs qui ont pris aujourd'hui leur retraite.

Je connais le niveau de jeu en France et je sais qu'un bon club d'athlètes peut atteindre le niveau top 10 de France en un ou deux ans d'entraînements. Pourquoi? Simplement parce que le sport n'est pas encore assez mature en France. 2500 joueurs en France, c'est rien. Monter de niveau parmi si peu de joueurs, ça se fait vite. Il faut donc que l'administration du championnat de France laisse plus de liberté de mouvement d'ascension (et de descente!) aux clubs. La D1 n'est pas encore assez forte pour que seulement deux clubs puissent y accéder par année. La limite de deux équipes, ce n'est pas une limite à l'accès à la D1, c'est une limite au développement du niveau de jeu de sa propre nation.

Avec les règles actuelles, un bon club d'athlètes remplis de potentiels prendra quatre années pour atteindre la D1 (remporter une division par année). Et si dix clubs essaient de faire la même chose en même temps (ce qui est très souhaitable!), alors ça deviendra complètement impossible. Au mieux, trois clubs parmi les dix auront atteint la D1 en cinq ans. Il y a beaucoup plus de chances que les clubs se découragent avant ou pire qu'ils perdent leurs meilleurs joueurs qui rejoindront un club déjà en D2 ou D1.

En fait, je fais la prédiction suivante. Si la FFDF persiste à conserver la structure actuelle, je prédis que dans cinq ans, la D2 sera plus compétitive que le 5 à 12 de la D1. Et que dans dix ans la D2 sera une division plus compétitive que la D1. Bien sûr, un certain équilibrage se fera avec le temps avec les bons joueurs de D2 qui quitteront leur club pour rejoindre des clubs de D1, mais la division 1 elle-même sera loin d'atteindre son plein potentiel de développement.

Ma proposition: Un championnat de France qui rassemble les meilleures équipes de France

Il faut agir avant qu'il ne soit trop tard (honnêtement, il se fait déjà tard, mais on ne peut pas changer le passé). Je regrette de ne pas avoir été plus explicite dans mon article de 2013. Aujourd'hui, je prends le temps d'expliquer du mieux que je peux comment on peut remettre le Championnat de France sur pied dès l'an 2016. Il faut agir, il faut effacer les divisions actuelles et faire en sorte que le Championnat de France rassemble les meilleures clubs de France du moment à chaque année.

Des sections, cinq régions, une nation

Pour ce faire, je suggère de procéder comme au Canada ou aux États-Unis: diviser le pays en régions et choisir les meilleures équipes de chaque région pour participer au championnat national. Au printemps 2016, le calendrier pourrait avoir l'air de ceci:

• Mars 2016: Championnats de sections pour se qualifier aux Championnats de régions (si nécessaire pour les grandes régions).
• Avril 2016: Championnats de régions, les meilleures équipes de chaque région.
• Mai 2016: Championnat de France, les seize meilleures équipes au pays.

Pour ce faire, j'ai divisé la France en cinq régions de la façon ci-bas. Je me suis plus ou moins inspiré des gares de Paris qui déservent les régions de la France.

Pour simplifier, je fais la suite en considérant la catégorie masculine, mais le même exercice pourrait être fait avec la catégorie mixte, féminine et maître. Sur la carte, j'ai marqué d'un point rouge les départements qui possèdent un club ayant une équipe masculine en D1 ou en D2. Les clubs en question sont les suivants:

Plus précisément, voici les clubs de D1 et de D2 appartenant à chacune des cinq régions. Dans ce format, j'avais choisi de diviser Paris (75) en deux. Donc Révo font partie de Paris Nord et Ah O Puc font partie de Paris Sud.

Dans le tableau ci-bas, j'indique exactement les départements pour chaque région. Certains département n'ont pas de club enregistré auprès de la FFDF.

Sélection des meilleurs clubs de chaque région

Je suggère d'organiser un championnat de France qui rassemble les 16 meilleures équipes de la France. Les 16 places sont allouées de trois façons:

• représentativité des régions (2 places par région, total 10)
• force des régions (chaque équipe du top 4 de l'année précédente donne une place à sa région)
• taille des régions (les deux régions les plus nombreuses en nombre de clubs obtiennent une place)

Par exemple, on pourrait obtenir le calcul suivant pour chacune des régions. J'ai utilisé le top 4 actuel (Iznogood, Sun, Tchac, 33 Tours) pour illustrer les régions qui obtiendraient les 4 places de force.

Les 16 équipes qui participeraient aux Championnats de France en mai 2016 seraient donc les 3 meilleurs clubs de la région Montparnasse Sud, les 3 meilleurs clubs de la région Montparnasse Nord, les 3 meilleurs clubs de la région Gare de Lyon, les 3 meilleurs clubs de la région Paris Nord puis les 4 meilleurs clubs de la région Paris Sud. Les cinq tournois régionaux auraient lieu en avril 2016. Pour les régions avec beaucoup de clubs, le championnat régionnal serait précédé de quelques championnats de section, chaque régions étant elle-même divisée en sections comme c'est le cas pour les Championnats américains d'ultimate. Au Canada, le pays est divisé en 6 régions (malgré qu'il y ait 10 provinces et 3 territoires). Et les régions ne sont pas divisées en section.

Selon moi, ce format favoriserait le développement des meilleures équipes de France, car on n'aurait pas le choix de jouer à son meilleur pour être champion. Les équipes de niveau régionnal actuel seraient encore plus motivées par la possibilité d'accéder au Championnat national. Cela pousserait les équipes meilleures à rester meilleures ou sinon à être remplacées (et tant mieux dans ce cas!).

C'est parce que je crois au développement de l'ultimate compétitif en France que j'ai mis tout ce temps à écrire ce texte. Et vous y croyez-vous? Ensemble tout est possible!

En 2013, j'avais écrit cet article d'opinions au sujet de l'organisation de l'ultimate en France. Certaines choses ont évolué pour le mieux depuis (un match d'ultimate pour décider de la meilleure équipe d'ultimate en France) d'autres non. Aujourd'hui, en 2015, j'ai trois propositions à suggérer à la fédération française d'ultimate (FFDF) et je vais les décrire dans trois messages de blogue distincts au fur et à la mesure que je trouve le temps pour les rédiger. Ma première proposition concerne la mise à jour de la règle de bris d'égalité dans les tournois à ronde où chaque équipe joue contre chaque équipe de son groupe.

La règle de bris d'égalité dans les classements utilisée par la FFDF doit être corrigée. Il peut sembler normal d'utiliser le différentiel global pour briser une égalité. C'est ce qui est utilisé dans les longues saisons de soccer en Europe et aussi en Amérique pour briser les égalités au hockey (bien que le nombre de victoire compte avant les points pour et points contre). Mais cette règle de bris d'égalité est mésadaptée pour les tournois à la ronde où on joue un seul match contre chaque équipe. En effet, (1) cela ne produit pas le classement optimal, (2) cela ouvre la porte à la tricherie et (3) cela crée des effets indésirables.

Par exemple, lors du Championnat de France indoor Division 1 du 7-8 février 2015, les résultats finaux ont été les suivants:

Iznogood, Sun et Magic Disc ont terminé toutes les trois avec une fiche de 3 victoires et 2 défaites. Pour briser l'égalité de ces trois équipes, la règle de bris d'égalité se base le différentiel des équipes. On obtient donc que Iznogood est la 2e meilleure équipe de France, Sun 3e et Magic Disc 4e.

Possiblité de tricherie

Selon moi, c'est une erreur de comparer ces trois équipes en utilisant le différentiel de tous les matchs de pools qui ont été joués, car cela mène avec forte probabilité à des injustices et ouvre aussi la porte à la tricherie (je ne dis pas qu'il y en a, mais je dis que la méthode actuelle le permet). Par exemple, imaginons que Iznogood, Sun et Magic Disc sont vraiment des équipes très égales et qu'ils ont donc joué des matchs avec quelques points d'écart seulement. Le fait de briser l'égalité de ces trois équipes en considérant tous les matchs donnent beaucoup trop d'importance à des matchs qui n'avaient aucune importance:

Iznogood   13 - 5 Tsunami
Sun        11 - 8 Tsunami
Magic Disc 12 - 7 Tsunami

Ces matchs donnent beaucoup de pouvoir à l'équipe Tsunami pour briser une égalité qui ne la regarde pas. En effet, Tsumani peut décider de tricher en jouant mal contre Iznogood et en donnant leur meilleur contre le Sun et Magic Disc pour permettre à Iznogood de finir meilleur dans le classement final de la FFDF. Bien sûr, je ne pense pas que Tsunami a triché, mais comment savoir si elle a joué de façon constante dans ces trois matchs ? En fait je pense que c'est impossible de jouer au même niveau tout le temps, car dans un tournoi, on s'améliore de match en match et Tsunami le samedi matin et Tsunami le dimanche après-midi, ce n'est pas la même équipe quoi qu'on fasse. Justement notez que le match Iznogood-Tsunami a été joué le samedi matin et on peut très bien imaginer que Tsunami aurait pu faire un peu moins d'erreur si ce n'était pas leur premier match du tournoi.

Un classement optimal

Moi je dis que les matchs joués contre Tsunami, Sesquidistus ou les Tchac ne doivent pas être considérés pour briser l'égalité entre Iznogood, Sun et Magic Disc. Pour briser l'égalité de la manière la plus logique et pour éviter les injustices, il faut éviter de considérer l'information superflue. Il faut se limiter à l'information essentielle et plutôt considérer les trois matchs qui ont eu lieu entre ces trois équipes et seulement ceux-ci:

Iznogood 7 - 10 Magic Disc
Iznogood 11 - 8 Sun
Sun      8 - 7  Magic Disc

En considérant seulement ces trois matchs, il faut d'abord regarder qui a la meilleure fiche?

Iznogood     1-1
Sun          1-1
Magic Disc   1-1

Mathématiquement, il aurait été possible que ces trois équipes aient des fiches 2-0, 1-1 et 0-2 même si elles avaient la même fiche dans le pool complet. Cela aurait permis de briser l'égalité, mais dans ce cas-ci, ce n'est pas suffisant. Il faut donc continuer l'analyse et considérer le différentiel seulement pour les matchs entre les trois équipes. On obtient:

Magic Disc +2
Iznogood   +0
Sun        -2

Nous pouvons donc conclure que Magic Disc a connu une injustice en 2015, car la FFDF les ont classé en 4e position alors que Magic Disc a vraiment été la 2e meilleure équipe de France en indoor pour la saison 2015.

Dans cet exemple, la règle de bris d'égalité a permis de décider qui est la 2e meilleure équipe en France. Mais, dans d'autres cas, elle décidera du fait qu'une équipe monte ou descende de division ou pire du Champion de France. Peut-être que cela s'est déjà produit dans le passé ou sinon ça se produira si on ne corrige rien.

Autres effets indésirables

D'autres effets indésirables sont aussi créés par la règle de bris d'égalité actuellement utilisée par la FFDF. En effet, un effet indésirable est d'enlever toute l'importance qu'un match important peu avoir. Inutile de préciser qu'un match important est un effet désirable, car il force les deux équipes à se préparer et à donner leur meilleur pour le gagner ce qui permet d'augmenter le niveau de jeu de ces deux équipes et à plus long terme d'augmenter le niveau de jeu de toutes les équipes en France ce qui doit être un objectif de la FFDF.

Cet effet indésirable s'est produit pas plus tard que samedi dernier lors de la deuxième phase du Championnat de France de division 1.

Considérons le top 3 du pool B:

Dans ce cas-ci, la règle de bris d'égalité de la FFDF est en accord (un hasard il faut dire) avec celle que je propose, car UV a gagné contre FU 17 - 11 ce qui est l'information suffisante pour briser l'égalité entre les deux équipes. L'effet indésirable s'est plutôt produit avant la fin des matchs. Plus particulièrement, avant le dernier match de pool entre FU et Iznogood, la fiche des deux équipes était la suivante:

Toute l'importance de ce dernier match de pool pour les deux équipes a été sublimé par la règle de bris d'égalité, car Iznogood avait un différentiel impossible à rattraper. En utilisant une bonne règle de bris d'égalité, FU aurait été plus que motivé de gagner ce dernier match, car alors la fiche des deux équipes aurait été de 4-1. Et dans le cas d'une égalité impliquant deux équipes, on doit simplement regarder qui a gagné le match impliquant les deux équipes. Autrement dit, FU avait la première place entre leurs mains. Il suffisait qu'il gagne ce dernier match. À la place, nous avons joué un match sans importance.

Ce que je suggère

En fait, ce n'est pas moi qui dit tout ça, de telles règles de bris d'égalité sont utilisées aux États-Unis, au Canada et au Québec depuis 20 ans dans l'organisation des tournois d'ultimate. Par exemple, la règle de bris d'égalité que j'avais ajouté aux Règlements du jeu de l'ultimate 4 contre 4 en 2008 alors que j'étais président de la Fédération québécoise d'ultimate est ci-bas. C'est la règle de bris d'égalité que je suggère d'utiliser en France.

[Extrait des Règlements du jeu de l'ultimate 4 contre 4 de la FQU]

"BRIS D’ÉGALITÉ

Si une égalité persiste au classement, les règles suivantes de bris d'égalité seront utilisées.

1. Une règle de bris d'égalité s'applique à toutes les équipes qui sont égales.

1.a. Si, après l'application d'une règle, toutes les équipes sont encore égales, la règle suivante est appliquée.

1.b. Si toutes les équipes ne sont pas encore égales, mais qu'un ou plusieurs sous-groupes d'équipes sont à égalité, on sépare les équipes en groupes et on revient à la règle 2 avec chacun des groupes individuellement.

2. Fiche de Victoires-Défaites en considérant les matchs entre les équipes concernées.

3. Différentiel points pour - points contre, en considérant les matchs entre les équipes concernées.

4. Points pour, en considérant les matchs entre les équipes concernées.

5. Points contre, en considérant les matchs entre les équipes concernées.

6. Différentiel points pour - points contre, en considérant toutes les parties.

7. Points pour, en considérant tous les adversaires communs.

8. Points contre, en considérant tous les adversaires communs.

9. Tirage au sort."

Comment faire évoluer les choses en France?

N'hésitez pas à entrer en contact avec moi si vous savez comment faire pour changer les choses dans l'organisation de l'ultimate en France. C'est plus difficile pour moi d'améliorer les choses en France qu'au Québec, car je n'ai pas les contacts nécessaires. Je ne sais pas à qui en discuter. Je ne sais pas qui convaincre. Je ne sais pas s'il faut passer par la base (les clubs) ou le haut (la fédé). En fait, je pense qu'il faut passer par les deux, mais je connais ni l'un ni l'autre.

Et deux autres rues:

Les Règlements du jeu de l’ultimate 4 contre 4 adoptés pour la première fois en 2007 et dont la dernière version a été adoptée en 2012 indiquent que la profondeur de la zone de buts pour l'ultimate 4 contre 4 au Québec est de 3 mètres. La version de 2007 indiquait 2.5 mètres et suite aux procédures de reconnaissance de la Fédération québécoise d'ultimate par le Ministère en 2011, on était passé à 3 mètres.

Trois mètres, c'est petit, mais remarquons que c'est plus que la grandeur de n'importe quel être humain. En théorie, cela signifie notamment que personne (pas même Kevin Groulx) ne peut toucher simultanément à la ligne de fond avec ses pieds et à la ligne de buts avec ses mains. En théorie, 3 mètres, c'est la hauteur d'un éléphant. Mais la réalité ne correspond pas toujours à la théorie...

En réalité, les zones de buts dans le CQU4 et dans les ligues québécoises de 4 contre 4 sont très souvent trop peu profondes et parfois même moins que 2 mètres. On peut se demander pourquoi est-ce qu'on place toujours les cônes à la mauvaise distance? Mais, ce n'est pas la question que je vais considérer dans ce message. Je vais plutôt m'intéresser à la question suivante:

Pourquoi faudrait-il placer les cônes à une distance de 3 mètres?

J'y vois deux raisons.

Raison 1 (pour l'offensive). Lorsque la zone a une profondeur de 2 mètres seulement, elle est essentiellement unidimensionnelle (gauche-droite), car un défenseur placé dans un coin de la zone bloque toute la profondeur de la zone. Les tracés sont donc unidimensionnels: un traceur va attaquer un coin puis se diriger vers l'autre coin. Lorsque la zone a une profondeur de 3 mètres, un défenseur ne peut plus bloquer toute la profondeur de la zone. Le défenseur doit faire un choix. Protéger le "fond" ou protéger le "proche". Cela offre une nouvelle dimension aux tracés possibles de l'attaquant. Cela offre une nouvelle dimension aux feintes que le lanceur peut faire. Bref, cela permet de développer chez les joueurs et joueuses du Québec une attaque deux-dimensionnelle de la zone des buts ce qui peut être très utile l'été venu lorsqu'on joue à 7 contre 7 avec des zones de buts qui comporte aussi cette deuxième dimension de profondeur.

Raison 2 (pour la défensive). Depuis plusieurs années, on joue avec des zones d'environ 2 mètres de profondeur. En tant que défenseur ayant joué beaucoup dans le CQU4, j'ai développé des aptitudes pour marquer un traceur attaquant la zone des buts. Je connais les tracés typiques, je sais ce que je dois protéger, ce que je peux laisser et à quelle distance et où je dois me placer en tout temps pour bien protéger la zone de buts de 2 mètres de profond. Toutefois, toutes ces aptitudes sont encore une fois unidimensionnelles. En jouant dans le CQU4 ces dernières années, je n'ai pas développé la deuxième dimension de mon positionnement défensif en tenant compte de la profondeur de la zone de buts, car la zone des buts n'était toujours profonde que de 2 mètres. Je crois qu'il faudrait placer les cônes à 3 mètres pour développer chez les joueurs et joueuses du Québec une défensive deux-dimensionnelle qui connaîtrait les tracés typiques utilisant la profondeur de la zone des buts. Je pense que ces aptitudes ainsi développées seraient très utiles l'été venu dans le contexte de la défense d'une zone des buts qui admet clairement un aspect deux-dimensionnel.

In 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