University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Algebra SeminarExport this event to calendar

Wednesday, October 28, 2020 — 2:00 PM EDT

Seda Albayrak, Department of Pure Mathematics, University of Waterloo

"A refinement of Christol’s theorem"

Christol's theorem is one of the fundamental results in the theory of finite-state automata. It says that a formal power series $F(x)=\sum_n a_n x^n$ with coefficients in a finite field $\mathbb{F}_q$, $q$ a power of a prime $p$, is algebraic over the field of rational functions $\mathbb{F}_q(x)$ if and only if the sequence $\{a_n\}$ is $p$-automatic. The support of an algebraic power series, i.e.the set of $n$ for which $a_n\neq 0$, is an automatic subset of $\mathbb{N}$. There is a dichotomy for automatic sets that says automatic sets are either sparse, having at most ${\rm O}((\log \, n)^d)$ elements of size at most $n$ for some $d\ge 1$ and all $n$; or they are non-sparse, have at least $n^{\alpha}$ elements of size at most $n$ for some positive number $\alpha$ and all $n$ sufficiently large. In a joint work with Jason Bell, we characterize algebraic power series with sparse support, giving a refinement of Christol’s theorem. In fact we are able to prove our result in a more general setting, that is for generalized power series, studied and characterized by Kedlaya.

Zoom meeting: https://us02web.zoom.us/j/81125421802?pwd=c3NaZmNRVnJKMkk0U0hLZXpVNTBtQT09

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
  1. 2020 (93)
    1. November (12)
    2. October (4)
    3. September (3)
    4. August (1)
    5. July (5)
    6. June (1)
    7. May (3)
    8. March (16)
    9. February (26)
    10. January (22)
  2. 2019 (199)
    1. December (7)
    2. November (26)
    3. October (19)
    4. September (13)
    5. August (7)
    6. July (12)
    7. June (18)
    8. May (22)
    9. April (11)
    10. March (25)
    11. February (17)
    12. January (22)
  3. 2018 (212)
  4. 2017 (281)
  5. 2016 (335)
  6. 2015 (211)
  7. 2014 (235)
  8. 2013 (251)
  9. 2012 (135)