\documentclass{amsart} \usepackage[left=2cm, right=2cm]{geometry} \usepackage[utf8]{inputenc} \usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox} \usepackage{blindtext} \usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref} \usepackage{tikz,tikz-cd} \usepackage{cleveref} \usepackage{xcolor} \usepackage{array} \usepackage[style=alphabetic,sorting=nyt, maxnames=4]{biblatex} % \usepackage[style=authoryear, maxnames=4]{biblatex} \renewbibmacro{in:}{} % \addbibresource{biblio.bib} \addbibresource{CommonBiblio20240922.bib} \tikzset{pullback/.style={minimum size=1.2ex,path picture={ \draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);% }}} \usetikzlibrary{calc} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[subsection] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{todo}[theorem]{Todo} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{fact}[theorem]{Fact} \newtheorem{claim}{Claim}[theorem] \crefname{claim}{Claim}{Claims} \renewcommand{\theclaim}{\thetheorem.\alph{claim}} \theoremstyle{definition} \newtheorem{example}[theorem]{Example} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \newtheorem{notation}[theorem]{Notation} \newtheorem{puzzle}[theorem]{Puzzle} \newtheorem{question}[theorem]{Question} \newtheorem{idea}[theorem]{Idea} \newcommand{\dq}[1]{``#1"} \newcommand{\memo}[1]{\textcolor{red}{memo: #1}} % \newcommand{\invmemo}[1]{\textcolor{blue}{memo: #1}} \newcommand{\invmemo}[1]{} \newcommand{\horamemo}[1]{\textcolor{green!70!black}{hora: #1}} \newcommand{\para}[1]{\paragraph{\textbf{#1}}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\D}{\mathcal{D}} \newcommand{\E}{\mathcal{E}} \newcommand{\F}{\mathbb{F}} \renewcommand{\L}{\mathcal{L}} \newcommand{\id}{\mathrm{id}} \newcommand{\op}{\mathrm{op}} \newcommand{\ob}{\mathrm{ob}} \newcommand{\Set}{\mathbf{Set}} \newcommand{\sSet}{\mathbf{sSet}} \newcommand{\FinSet}{\mathbf{FinSet}} \newcommand{\PSh}{\mathbf{PSh}} \newcommand{\Sh}{\mathbf{Sh}} \newcommand{\Cont}{\mathbf{Cont}} \newcommand{\Func}[2]{[#1,#2]} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\demph}[1]{\textit{#1}} \font\maljapanese=dmjhira at 2.5ex \newcommand{\yo}{\textrm{\!\maljapanese\char"48}} \newcommand{\Pow}{\mathcal{P}} \newcommand{\A}{\Sigma} \newcommand{\MA}{\Sigma^{\ast}} \newcommand{\SA}{\Sigma^{{>}0}} \newcommand{\PW}{\mathsf{PWord}} \newcommand{\X}{\mathcal{X}} \newcommand{\PZ}{\hat{\Z}} \newcommand{\Frob}{\mathrm{Frob}} \newcommand{\Li}{\mathrm{Li}} \newcommand{\Pf}{\mathfrak{p}} \title{Notes on primitive words} \author{Ryuya Hora} \address{Graduate School of Mathematical Sciences, University of Tokyo, Tokyo, Japan} \email{hora@ms.u-tokyo.ac.jp} \date{\today} \subjclass[2020]{} \keywords{h} \begin{document} \begin{abstract} This note aims to list up some analogies between primitive words and the Galois theory of finite fields. This is just a personal note, which is not intended to be published. \end{abstract} \maketitle \href{https://chatgpt.com/share/68ad8c7e-00e0-8000-b752-9228615cc843}{[AI-survey]} \tableofcontents In this note, $\A$ denotes a fixed set of alphabet, and $\MA$ denotes the monoid of all words and concatenation. Let $\SA$ denote the set of all words with positive length, i.e., $\MA = \SA\sqcup \{\epsilon\}$. Let $\PW$ \section{A categorical (or geometric) description of primitive words} For a non-negative integer $n\in \N$, the set of all $n$-words $\A^n$ admits a canonical $\Z/n\Z$-action defined by \[ (a_0, a_1, \dots , a_{n-1})*k = (a_k, a_{k+1}, \dots , a_{k+n-1}), \] where the indices are considered as elements of $\Z/n\Z$. We call it \demph{the cyclic action}. \begin{remark} From categorical point of view, this is nothing other than the cofree $\Z/n\Z$-action on the set $\A$. In other words, this is the image of $\A$ via the direct image of the canonical point of the topos $\PSh(\Z/n\Z)$. Gathering them, we obtain a canonical continuous $\PZ$-action on a (discrete) set $\MA$. A more canonical way to consider it is \begin{enumerate} \item Consider the topos $\PSh(\Z)$. \item The cofree $\Z$-action on the set $\A$ is $\Z \times \A^\Z \to \A^\Z$. \item Consider the hyperconnected geometric morphism $h\colon \PSh(\Z) \to \Cont(\PZ)$ induced by $\Z \to \PZ$ (cf. \cite{hora2024quotient}). \item $h_* (\A^\Z)$ is the set of all cyclic infinite sequences. There is a canonical map $\MA \to h_*({\A^{\Z}})$ \end{enumerate} \end{remark} \begin{definition} A word $w\in \MA$ is called \demph{primitive} if the stabilizer of the $\Z/n\Z$-action at $w\in \A^n$ is trivial. \end{definition} \begin{theorem}[the universality of primitive words] The $\PZ$-set $\PW$ is the cofree $\PZ$-set generated by the alphabet $\A$. In other words, for any continuous $\PZ$-set $\X=(X, \mu)$, we have \[ \Cont(\PZ) (\X, \PW) \cong \Set(X, \A). \] \end{theorem} \begin{question} For each prime power $q$, we consider $\A=\F_q$. Then we have \[ \text{primitive $\A=\F_q$words with length $n$} =\text{algebraic numbers over $\F_q$ whose degree is $n$}. \] Can this be witnessed by a $\PZ$-action isomorphism? In other words, is there a function $\phi \colon \overline{\F_q} \to \F_q$ such that the map \[ x \mapsto \{\phi(\Frob^k(x))\}_{k\in \Z} \] is a bijection from $\overline{\F_q}$ to the set of cyclic infinite sequence of $\F_q$? \memo{Yes, Yugo Takanashi, due to normal basis theorem} \memo{I still don't know if it can be an internal group iso between $\overline{\F_p} \cong \text{the cofree $\PZ$-set generated by } \F_p$} \href{https://www.sciencedirect.com/science/article/pii/1385725885900095}{[Normal basis for infinite Galois extension]} \end{question} \section{The dirichlet series and Riemann zeta} It is well known that every word (with positive length) can be uniquely written as a power of a primitive word. This fact can be decategorified to the Möbius inversion formula \begin{align*} |\A|^n &= \sum_{d|n} a_d,\\ a_d &= \sum_{d|n} \mu\left(\frac{n}{d}\right) |\A|^n \end{align*} % \[ % |\A|^n = \sum_{d|n} a_d, % \] where $a_n$ denotes the number of primitive words with length $n$. Let $a_n(z)$ denote the polynomial \[ a_n(z) \coloneqq \sum_{d|n} \mu\left(\frac{n}{d}\right) z^n \in \C[z] \] so that $a_n(|\A|)$ is the number of primitive $\A$-words with length $n$. \begin{definition} The \demph{Dirichlet generating function of primitive words} is defined to be \[ \Pf_z(s) = \sum_{n=1}^\infty \frac{a_n(z)}{n^s} \] as an element of the ring $\C[z][1/n^s\mid n\geq 1]$. \end{definition} The first few terms look like \[ \Pf_{z}(s) = \frac{z}{1^s}+ \frac{z^2 -z}{2^s}+ \frac{z^3 -z}{3^s}+ \frac{z^4 -z^2}{4^s}+ \frac{z^5 -z}{5^s}+ \frac{z^6 -z^3-z^2+z}{6^s} +\cdots \] \begin{remark}[Pointed out by Yuhi Kamio] For a power of prime $q$, the series $\Pf_q(s)$ coincides with the Dirichlet generating function of \[ \#\{x\in \overline{\F_q}\mid \text{the algebraic degree of $x$ is $n$}\}. \] Is it just coincidence that $\mathrm{Gal}(\F_p) \cong \PZ$? \end{remark} \memo{By replacing $|\A$ with $z$, the set $\A$ was obscured. In some sense, Promitive word conjecture "without explicit $\A$"can be naturally formulated in terms of nominal sets, or the Schanuel topos. In this case, the natural problem would be: is there a nominal CFG that generates the nominal $PW$? This might be ideally formulated as the $\Sh(\FinSet_{\mathrm{mono}}, \lnot\lnot)$-relative topos of $\PZ$-actions.} Following convention, we write $\Li_s(z)$ for the polylogarithm \[ \Li_s(z) = \sum_{n=1}^\infty \frac{z^n}{n^s}, \] and write $\zeta(s)$ for the Riemann zeta function \[ \zeta(s)= \sum_{n=1}^\infty \frac{1}{n^s}. \] \begin{proposition} The Dirichlet generating function of primitive words (formally defined in the ring $\C[z][1/n^s\mid n\geq 1]$) is given by \[ \Pf_{z}(s) = \frac{\Li_{s}(z)}{\zeta(s)}. \] \end{proposition} \begin{proof} This follows since the Möbius inversion is rephrased as follows: \[ \sum_{n=1}^\infty \frac{z^n}{n^s} = \left(\sum_{n=1}^\infty \frac{a_n(z)}{n^s}\right) \left ( \sum_{n=1}^\infty \frac{1}{n^s}\right). \] \end{proof} \begin{remark} By abuse of analytic continuation, let us say something like "The sum of all positive integers is $-\frac{1}{12}$." When $s=0$, the value $\Pf_{z}(0)$ formally looks like ``the number of all primitive $\A$-words with $|\A|=z$." In the usual sense, it should be infinite unless $z=1$. However, by naively calculating $\Li_0(z)=z+z^2+z^3\cdots= \frac{z}{1-z}$ and $\zeta(0)= -\frac{1}{2}$, we obtain \[ \Pf_z(0) \overset{?}{=} \frac{\frac{z}{1-z}}{-\frac{1}{2}}=\frac{2z}{z-1}. \] So, we would say ``The number of primitive words for the alphabet $a,b,c,d$ is $\frac{8}{3}$" \end{remark} \subsection*{Acknowledgement} I would like to thank Yuhi Kamio for pointing out that the number of primitive words coincides with the number of algebriac number over $\F_q$ with degree $n$. I am also grateful to Yugo Takanashi for pointing out the connection with Normal Basis Theorem. I extend my gratitude to Yutaro Mikami. % The first-named author would like to thank his supervisor Ryu Hasegawa for helpful discussions and suggestions. % He was supported by JSPS KAKENHI Grant Number JP24KJ0837 and FoPM, WINGS Program, the University of Tokyo. \printbibliography \end{document}