← notes-on-primitive-words
FirstVersion.tex
\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}