Évènements

En informatique, les expressions aléatoires sont couramment utilisées pour analyser des algorithmes, que ce soit pour étudier leur complexité en moyenne, ou pour générer des benchmarks pour les tester expérimentalement. Généralement, ces approches considèrent les expressions en entrée comme des arbres purement syntaxiques, et font abstraction de leur sémantique, c’est-à-dire de l’objet mathématique représenté par l’expression.

Pourtant, deux expressions différentes peuvent être équivalentes (par exemple « 0*(x+y) » et « 0 » représentent la même expression, l’expression nulle). Ces phénomènes de redondances remettent-ils en question la pertinence de ces analyses et ces tests qui ne tiennent pas compte de la sémantique des expressions ?

Je présenterai comment la distribution uniforme sur les arbres syntaxiques d’expressions devient complètement dégénérée lorsqu’on commence à prendre en compte leur sémantique, dans le cas très simple mais courant où il existe un élément absorbant. Si le temps le permet, j’expliquerai pourquoi la distribution ABR laisse plus d’espoirs.

Il s’agit d’un travail effectué pendant ma thèse, en commun avec Cyril Nicaud et Pablo Rotondo.

Les journées SL2R « Théorie des Représentations et Analyse Harmonique » se tiendront à l’Université du Lorraine les jeudi 12 et vendredi 13 Mai 2020. Ce colloque tournant — entre les universités de Strasbourg, Lorraine, Luxembourg et Reims (=SL2R) — regroupe deux à trois fois par an les mathématiciens de ces quatre universités travaillant en théorie des représentations et en analyse harmonique.

Cette édition sera en l’honneur du Professeur Jacques Faraut, l’un des fondateurs du précurseur des journées SL2R : le séminaire Nancy-Strasbourg (organisé par P. Eymard – R. Takahashi de Nancy et J. Faraut – G. Schiffmann de Strasbourg).

Pour participer, merci de remplir le formulaire form et de l’envoyer à khalid.koufany@univ-lorraine.fr et wolfgang.bertram@univ-lorraine.fr

Le programme, les participants et toutes les informations pratiques sont à retrouver sur le site web de l’événement : http://khalid-koufany.perso.math.cnrs.fr/SL2R2022/index.html

We present a new elementary algorithm for computing $M(x) = \sum_{n \leq x} \mu(n),$ where $\mu(n)$ is the Möbius function. Our algorithm takes
\[\begin{aligned}
\mathrm{time} \ \ O_\epsilon\left(x^{\frac{3}{5}} (\log x)^{\frac{3}{5}+\epsilon} \right)
\ \ \mathrm{and}\ \ \mathrm{space} \ \ O\left(x^{\frac{3}{10}} (\log x)^{\frac{13}{10}}
\right)\end{aligned},\] which improves on existing combinatorial algorithms. While there is an analytic algorithm due to Lagarias-Odlyzko with computations based on the integrals of $\zeta(s)$ that only takes time $O(x^{1/2 + \epsilon})$, our algorithm has the advantage of being easier to implement. The new approach roughly amounts to analyzing the difference between a model that we obtain via Diophantine approximation and reality, and showing that it has a simple description in terms of congruence classes and segments. This simple description allows us to compute the difference quickly by means of a table lookup. This talk is based on joint work with Harald Andrés Helfgott.