Ing. Jakub Krásenský, Ph.D.

Článek

10.1090/proc/17141

Katedra aplikované matematiky

We discuss the phenomenon where an element in a number field is not integrally represented by a given positive definite quadratic form, but becomes integrally represented by this form over a totally real extension of odd degree. We prove that this phenomenon happens infinitely often, and, conversely, establish finiteness results about the situation when the quadratic form is fixed.

Článek

10.1016/j.tcs.2024.114606

Katedra aplikované matematiky

Cellular automata are a famous model of computation, yet it is still a challenging task to assess the computational capacity of a given automaton; especially when it comes to showing negative results. In this paper, we focus on studying this problem via the notion of CA intrinsic simulation. We say that automaton A is simulated by B if each space-time diagram of A can be, after suitable transformations, reproduced by B. We study affine automata - i.e., automata whose local rules are affine mappings of vector spaces. This broad class contains the well-studied cases of linear automata. The main result of this paper shows that (almost) every automaton affine over a finite field F-p can only simulate affine automata over F-p. We discuss how this general result implies, and widely surpasses, limitations of linear and additive automata previously proved in the literature. We provide a formalization of the simulation notions into algebraic language and discuss how this opens a new path to showing negative results about the computational power of cellular automata using deeper algebraic theorems.