WORReLL'23

Abstract: Given positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$, the Sum of Square Roots problem (SSR) is the computational problem of checking if $$\sqrt{a_1} + \sqrt{a_2} + \dots + \sqrt{a_n} > \sqrt{b_1} + \sqrt{b_2} + \dots + \sqrt{b_m}.$$ It is an essential primitive in Computational Geometry where efficient algorithms for several geometric problems are known relative to SSR. However the best-known complexity upper bound for SSR is in the Counting Hierarchy (CH), and no non-trivial lower bounds are known. Over the last two decades, SSR-hardness has emerged as a useful tool to capture the “numerical hardness” of problems, especially in Game Theory and Verification. In this talk, I will introduce a variant of SSR and show efficient “non-uniform” algorithms for this problem.

Slides: 🗎

Abstract: We investigate some recent results on injectivity for Quantum Finite Automata. We call a QFA injective if the acceptance probability of every input word is unique. We show the undecidability of this problem by using tools and results from linear algebra, quaternions, number theory, and in particular rational polynomial pairing functions. We note a huge disparity in the number of required states to show undecidability depending on whether the initial state vector is rational or real algebraic. We will draw parallels with interesting questions for other matrix theoretic problems, and introduce some new research directions and open problems.

Slides: 🗎

Abstract: In this lecture we revisit recursive sequences from the view point of numeration systems and their associated dynamical systems. Linear recurrences allow indeed the definition of numerations for both integers and real numbers. We focus on the so-called finiteness property which means that the set of elements having a finite expansion forms a ring, and on its numerous applications in arithmetics, aperiodic order, fractal geometry etc.

Slides: 🗎

Abstract: I will talk about the following geometric puzzle. Take a random point (“grasshopper”) from a set $L$ (“lawn”, on the plane or on the sphere) and move it by a fixed distance in a random direction, once. How do you choose the shape of $L$, assuming a fixed area, so as to maximise the probability that the reached point is also in the set $L$?

Surprisingly, in 2D the disc (circle) is known to be sub-optimal. In a spherical version of the problem, motivated by quantum information theory, the hemispherical lawn is or is not optimal, depending on the length of the jump: whether it is a rational or irrational multiple of $\pi$, and if rational, then on the numerator in lowest terms.

Joint work with Olga Goulko, Adrian Kent, and Mike Paterson.

Abstract: Let $( T_n )_{n} \in \mathbb{Z}$ be the Tribonacci numbers. Marques and Lengyel (2014) obtained a formula relating the $2$-adic valuation of $T_n$ with the $2$-adic valuation of a linear function of $n$ (which might be constant) according to the residue class of $n$ modulo $32$ and optimistically conjectured that a similar formula holds true for every prime $p$. In the first part of the talk, we will see that their conjecture was indeed far too optimistic; in particular, it fails for all but seven primes below $600$. Along the way, we are led to consider a certain twisted rational zero of a linearly recurrent sequence. We prove that non-degenerate linearly recurrent sequences have only finitely many such twisted rational zeros, which may be seen as an extension of the Skolem–Mahler–Lech theorem. While our method is, in general, not effective, in some cases we can compute all such twisted rational zeros. In particular, returning to the Tribonacci sequence we show that its only twisted rational zeros are the integral ones $-17,-4,-1,0$ together with the rational non-integral ones $1/3$ and $-5/3$.

This is joint work with Y. Bilu, J. Nieuwveld, J. Ouaknine and J. Worrell.

Slides: 🗎

Abstract: The Skolem Problem asks to determine whether a given integer linear recurrence sequence (such as the Fibonacci numbers) has a zero term. This problem, whose decidability has been open for many decades, arises across a wide range of topics in computer science, including loop termination, probabilistic model checking, weighted automata theory, and dynamical systems, amongst many others. Recently, a new line of attack to the Skolem Problem was initiated via the notion of a Universal Skolem Set: a set S of positive integers such that it is decidable whether a given linear recurrence sequence has a zero in S. I will present an overview of this approach.

This is joint work with Florian Luca, James Maynard, Armand Noubissie, and James Worrell.

Slides: 🗎

Abstract: Proving positivity of sequences that are defined by recurrences is very hard. Even when restricted to the seemingly simple class of sequences defined by linear recurrences with constant coefficients (C-finite sequences), decidability of the positivity problem is only known for orders up to five.

On the other hand, some computer algebra methods are able to tackle this problem. Obviously, they do not succeed with all types of input and even though correctness can be proven, termination is typically an issue. In this talk, we will give an overview on this topic, present some available methods and show cases where algorithmic proofs actually succeeded.

Abstract: A large number of naturally defined matrix problems are still unanswered, despite the long history of matrix theory. In this presentation, I will discuss a number of challenging computational problems for matrix semigroups and their connections to matrix equations, iterative maps and linear recurrence sequences. Some of these problems are still unsolved but at the same time identified as reference points in the algorithmic analysis of reachability problems. The cornerstones of these reachability problems are in the synergy of the questions in mathematics and computer science: computability, automata theory, matrix theory, combinatorics, abstract algebra, number theory, etc. The main objective of future research is in developing new concepts and methods combining symbolic and numerical techniques as well as unifying the results in automata, computability, number and matrix theories.

Abstract: This talk is on the Membership problem for rational-valued hypergeometric sequences. Such sequences $\langle u_n \rangle_{n=0}^{\infty}$ satisfies a first-order linear recurrence relation with polynomial coefficients; that is, a recurrence of the form $f(n)u_n = g(n)u_{n-1}$ where $f,g \in \mathbb{Z}[x]$. The Membership Problem asks, given a hypergeometric sequence $\langle u_n \rangle_{n=0}^{\infty}$ and a target value $t\in \mathbb{Q}$, determine whether $t$ occurs in the sequence. We give hints on recent decidability results of the Membership Problem under the assumption that either (i) $f$ and $g$ have distinct splitting fields, (ii) $f$ and $g$ split totally over $\mathbb{Q}$, and (iii) $f$ and $g$ are monic polynomials that both split over a quadratic extension of $\mathbb{Q}$.

This talk is based on two papers appearing in ISSAC'22 and ISSAC'23, and are in collaboration with George Kenison, Amaury Pouly, Klara Nosan, and James Worrell.