On October 26, 2023 at 14:00 EEST, Gabriel Istrate (University of Bucharest) will give a talk in the Logic Seminar.
Title: Conway’s Army Percolation
Abstract:
I am studying a probabilistic model inspired by the Conway’s Army game. In the classical version of this game, the lower half-plane of an infinite chessboard is filled with queens. A classical result by John Conway (1961) shows that it is impossible to move (in a finite number of steps) a piece to the fifth line.
Motivated by an analogy to percolation theory in mathematical physics, I am studying the situation where every square of the lower half-plane contains, independently with the same probability \(p \in [0,1]\), a piece (the classical case occurs when \(p=1\)). I’m aiming to obtain estimates for the following quantities: the probability of moving a piece to a specific square on line \(k\) (where \(k \leq 4\)); the maximum density of pieces that can be moved to squares on line \(k\) (again, where \(k \leq 4\)).
In this talk, based on work in progress, I shall present both rigorous results (based on probabilistic techniques) and experimental results (based on SAT solving and integer linear programming), providing estimates for the aforementioned quantities. One interesting aspect is that the method of proving impossibility in the classical case yields poor estimates in general. On the other hand, I have identified certain mathematical objects related to the generalized Riemann zeta functions, which I will use as pagoda functions. These objects yield better estimates.
I will briefly discuss transfinite, ordinal-based extensions.
The talk will take place physically at FMI (Academiei 14), Hall 214 “Google”.