Abstract :
[en] THE BINOMIAL COEFFICIENT of two words counts occurrences of one as a
scattered subword of the other. This dissertation studies how these multiplicities
encode order.
For binary words, chambers of affine hyperplane arrangements correspond
bijectively to abelian, 3/2-binomial, 2-binomial, and finer quasi-binomial classes.
We obtain canonical representatives and enumeration formulas; class sizes are
coefficients of Gaussian binomial polynomials.
For generalized Thue–Morse words over m letters, we determine the
k-binomial complexity at every length for all k ≥ 2 and establish eventual periodicity
with period mk, proving a conjecture of Lü, Chen, Wen, and Wu. We also
develop an intermediate 3/2-binomial equivalence over ordered alphabets, compute
its complexity for several classical families, and characterize boundedness
by C-balance for some constant C.
We extend binomial coefficients recursively to multidimensional arrays, preserving
the main identities, and define complexity functions for rectangular factors.
For the binary two-dimensional Thue–Morse array, we obtain exact formulas
and eventual periodicity in both coordinates. For generalized Thue–Morse
arrays over m ≥ 3 letters, the (k,2)-binomial complexity, for k ≥ 2, agrees with a
periodic function on a set of shapes of natural density one, yet is not eventually
periodic in either coordinate on any cofinal quadrant.
In a fixed component of a regular language of polynomial growth, binomial
queries are polynomials in the loop exponents. We solve reconstruction for reduced
two-loop presentations and give, for any number of loops, a decidable sufficient
condition by quantifier elimination over the reals.
[fr] LE COEFFICIENT BINOMIAL de deux mots dénombre les occurrences de l’un
comme sous-mot épars de l’autre. Cette thèse étudie la manière dont ces
multiplicités encodent l’ordre des lettres.
Pour les mots binaires, les chambres d’arrangements d’hyperplans affines
sont en bijection avec les classes d’équivalence abélienne, 3/2-binomiale et
2-binomiale, ainsi qu’avec des classes quasi-binomiales plus fines. Nous obtenons
des représentants canoniques et des formules de dénombrement; les
cardinalités des classes sont des coefficients de polynômes binomiaux gaussiens.
Pour les mots de Thue–Morse généralisés sur un alphabet à m lettres, nous déterminons
la complexité k-binomiale pour toute longueur et tout k ≥ 2, et établissons
sa périodicité ultime de période mk, démontrant ainsi une conjecture de Lü,
Chen, Wen et Wu. Nous développons également une équivalence intermédiaire,
l’équivalence 3/2-binomiale, sur les alphabets ordonnés. Nous calculons la complexité
correspondante pour plusieurs familles classiques et montrons que cette
complexité est bornée si et seulement si le mot considéré est C-équilibré pour
une certaine constante C.
Nous étendons récursivement les coefficients binomiaux aux tableaux multidimensionnels,
en préservant leurs principales identités, et définissons des fonctions
de complexité pour les facteurs rectangulaires. Pour le tableau de Thue–
Morse binaire bidimensionnel, nous obtenons des formules exactes et établissons
la périodicité ultime suivant chacune des deux coordonnées. Pour les tableaux
de Thue–Morse généralisés sur un alphabet à m ≥ 3 lettres, la complexité
(k,2)-binomiale, pour k ≥ 2, coïncide avec une fonction périodique sur un ensemble
de formats rectangulaires de densité naturelle 1, mais n’est ultimement
périodique suivant aucune des deux coordonnées sur aucun quadrant cofinal.
Dans une composante fixée d’un langage régulier à croissance polynomiale,
les requêtes binomiales s’expriment comme des polynômes en les exposants des
boucles. Nous résolvons le problème de reconstruction pour les présentations à
deux boucles sous forme réduite et donnons, pour un nombre quelconque de
boucles, une condition suffisante décidable par élimination des quantificateurs
sur les réels.
Jury member :
FOKKINK, Robbert; Delft University of Technology > Delft Institute of Applied Mathematics (DIAM) > Applied Probability
DRMOTA, Michael; TU Wien > Institute of Discrete Mathematics and Geometry > Research Unit of Combinatorics and Algorithms
PIN, Jean-Éric; CNRS - Centre National de la Recherche Scientifique > Institut de Recherche en Informatique Fondamentale (IRIF)