Local obstructions in sequences revisited
Matthieu Rosenfeld
LIRMM, Montpellier
https://www.lirmm.fr/~mrosenfeld/
Date(s) : 29/04/2025 iCal
11h00 - 12h00
Consider the following problem about lacunary sequences of positive integers, i.e., nₖ₊₁>(1+e)nₖ for some e>0: Can we find a real θ such that the distances from nₖθ to the nearest integer are bounded away from 0?
Now consider a second problem: Given some c<2, does there exist a constant N and an infinite binary sequence α such that for every string x of length n≥N, any two occurrences of x in α are far away, i.e., the distance between them is at least ~cⁿ?
For both questions, one can use the Lovasz Local Lemma (LLL) to prove the existence of the desired objects. However, this is not constructive, in the sense that one cannot deduce from the LLL the existence of a computable θ or α.
In this talk, after giving some context, I will present a seemingly unrelated simple combinatorial game and a simple winning strategy in this game. I will then use this game to prove computable versions of these results (also slightly improving the previous bounds).
These results are based on a recent preprint with Alexander Shen.
Emplacement
I2M Luminy - TPR2, Salle de Séminaire 304-306 (3ème étage)
Catégories
