%% if you are submitting an initial manuscript then you should have submission as an option here %% if you are submitting a revised manuscript then you should have revision as an option here %% otherwise options taken by the article class will be accepted \documentclass[finalversion]{FPSAC2023} \articlenumber{46} %% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc %% note that the class file already loads {amsmath, amsthm, amssymb} \usepackage{tikz-cd} \newtheorem{theorem}{Theorem} \newtheorem{claim}{Claim} \newtheorem{defn}{Definition} \newtheorem{lem}{Lemma} \newtheorem{proposition}{Proposition} \newtheorem{corollary}{Corollary} \newtheorem{example}{Example} \newtheorem{defs}{Definitions} \newtheorem{remark}{Remark} \newtheorem{conj}{Conjecture} \newtheorem{ques}{Question} \newcommand{\ssty}{\scriptstyle} \newcommand{\w}{\omega} \newcommand{\sr}{\stackrel} \newcommand{\ov}{\overline} \newcommand{\ga}{\gamma} \newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\si}{\sigma} \newcommand{\la}{\lambda} \newcommand{\eps}{\varepsilon} \newcommand{\CC}{\mathbb{C}} % complex numbers \newcommand{\RR}{\mathbb{R}} % real numbers \newcommand{\QQ}{\mathbb{Q}} % rational numbers \newcommand{\NN}{\mathbb{N}} % nonnegative integers \newcommand{\PP}{\mathbb{P}} % positive integers \newcommand{\ZZ}{\mathbb{Z}} % integers \newcommand{\id}{\operatorname{id}} % identity map \newcommand{\kk}{\mathbf{k}} % our base ring \newcommand{\QSym}{\operatorname{QSym}} \newcommand{\std}{\operatorname{std}} \newcommand{\rank}{\operatorname{rank}} \newcommand{\Des}{\operatorname{Des}} \newcommand{\Odd}{\operatorname{Odd}} \newcommand{\Comp}{\operatorname{Comp}} \newcommand{\Peak}{\operatorname{Peak}} % For shuffle product symbol \makeatletter \providecommand*{\shuffle}{% \mathbin{\mathpalette\shuffle@{}}% } \newcommand*{\shuffle@}[2]{% % #1: math style % #2: unused \sbox0{$#1\vcenter{}$}% \kern .15\ht0 % side bearing \rlap{\vrule height .25\ht0 depth 0pt width 2.5\ht0}% \raise.1\ht0\hbox to 2.5\ht0{% \vrule height 1.75\ht0 depth -.1\ht0 width .17\ht0 % \hfill \vrule height 1.75\ht0 depth -.1\ht0 width .17\ht0 % \hfill \vrule height 1.75\ht0 depth -.1\ht0 width .17\ht0 % }% \kern .15\ht0 % side bearing } \makeatother %% define your title in the usual way \title[Extended peaks]{The algebra of extended peaks} %% define your authors in the usual way %% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details \author[D. Grinberg \and E.A. Vassilieva]{Darij Grinberg\thanks{\href{mailto:darijgrinberg@gmail.com}{darijgrinberg@gmail.com}.}\addressmark{1} \and Ekaterina A. Vassilieva\thanks{\href{mailto:katya@lix.polytechnique.fr}{katya@lix.polytechnique.fr}.}\addressmark{2}} %% put the date of submission here \received{\today} %% leave this blank until submitting a revised version %\revised{} %% put your English abstract here, or comment this out if you don't have one yet %% please don't use custom commands in your abstract / resume, as these will be displayed online %% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year) \abstract{Building up on our previous works regarding $q$-deformed $P$-partitions, we introduce a new family of subalgebras for the ring of quasisymmetric functions. Each of these subalgebras admits as a basis a $q$-analogue to Gessel's fundamental quasisymmetric functions where $q$ is equal to a complex root of unity. Interestingly, the basis elements are indexed by sets corresponding to an intermediary statistic between peak and descent sets of permutations that we call extended peak.} %% put your French abstract here, or comment this out if you don't have one \resume{En nous appuyant sur nos travaux précédents concernant les $P$-partitions $q$-déformées, nous introduisons une nouvelle famille de sous-algèbres pour l'anneau des fonctions quasi-symétriques. Chacune de ces sous-algèbres admet comme base un $q$-analogue aux fonctions quasisymétriques fondamentales de Gessel où $q$ est égal à une racine complexe de l'unité. Il est notable que les éléments de base sont indexés par des ensembles correspondant à une statistique intermédiaire entre les ensembles de pics et de descentes des permutations que nous appelons pic étendu.} %% put your keywords here, or comment this out if you don't have them yet \keywords{Quasisymmetric functions, descent set, peak set.} %% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier %% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text %% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex %% but you can use bibtex if you want \usepackage[backend=bibtex]{biblatex} \addbibresource{biblio.bib} %% note the \printbibliography command at the end of the file which goes with these biblatex commands \begin{document} \maketitle %% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In \cite{GriVas22}, we show that a $q$-deformation of the generating functions for $P$-partitions leads to a unified framework between classical and enriched $P$-partitions. In particular, we introduce our $q$-fundamental quasisymmetric functions that interpolate between I. Gessel's fundamental (\cite{Ges84}, $q=0$) and J. Stembridge's peak (\cite{Ste97}, $q=1$) quasisymmetric functions. When $q$ is not a root of unity, $q$-fundamentals are a basis of $\QSym$, the ring of quasisymmetric functions, and are indexed by descent sets of permutations. If $q=1$, they span the subalgebra of $\QSym$ named the algebra of peaks. The relevant basis elements are those indexed by peak sets. As it turns out, using other complex roots of unity for $q$, we are able to build new intermediate subalgebras between the algebra of peaks and $\QSym$, the basis of which are $q$-fundamentals indexed by a new permutation statistic that lies between peak and descent sets. We call this statistic the extended peak set and the corresponding subalgebras of quasisymmetric functions the algebra of extended peaks. We begin with the required definitions and results from \cite{GriVas22}. Then we introduce and prove the new results regarding the algebra of extended peaks. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Permutation statistics} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $\PP$ be the set of positive integers. For $m, n \in \PP$, write $[m,n] = \{m, m+1, \dots, n\}$ and simply $[n] = \{1, 2, \dots, n\}$. We denote $S_n$ the symmetric group on $[n]$. Given $\pi \in S_n$, define its \emph{descent set} $$\Des(\pi)= \{1\leq i\leq n-1| \pi(i)>\pi(i+1)\} \subset [n-1]$$ and its \emph{peak set} $$\Peak(\pi) = \{2\leq i\leq n-1| \pi(i-1)<\pi(i)>\pi(i+1)\}.$$ The peak set of a permutation is said to be \emph{peak-lacunar}, i.e. it neither contains $1$ nor contains two consecutive integers. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Enriched $P$-partitions and $q$-deformed generating functions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{sec : poset} We recall the main definitions regarding weighted posets, enriched $P$-partitions and their $q$-deformed generating functions. The reader is referred to \cite{Ges84, GriVas21, GriVas22, Sta01, Ste97} for more details. \begin{defn}[Labelled weighted poset, \cite{GriVas21}] A \emph{labelled weighted poset} is a triple $P = ([n],<_P,\epsilon)$ where $([n], <_P)$ is a \emph{labelled poset}, i.e., an arbitrary partial order $ <_P$ on the set $[n]$ and $\epsilon : [n]\longrightarrow \PP$ is a map (called the \emph{weight function}). \end{defn} \noindent Each node of a labelled weighted poset is marked with its label and weight (\cref{fig : poset}). % \begin{figure}[htbp] \begin{center} \begin{tikzcd}[row sep = small] & & {2,\ \epsilon(2) = 5} & & & & \\ {3,\ \epsilon(3) = 2} \arrow[rru,very thick] & & & & {1,\ \epsilon(1) = 1} \arrow[llu,very thick] \arrow[rr,very thick] & & {4,\ \epsilon(4) = 2} \\ & & {5,\ \epsilon(5)=2} \arrow[llu,very thick] \arrow[rru,very thick] & & & & \end{tikzcd} \end{center} \caption{A $5$-vertex labelled weighted poset. Arrows show the covering relations.} \label{fig : poset} \end{figure} % \begin{defn}[Enriched $P$-partition, \cite{Ste97}]\label{def : enriched} Let $\PP^{\pm}$ be the set of positive and negative integers totally ordered by $-1<1<-2<2<-3<3<\dots$. We embed $\PP$ into $\PP^{\pm}$ and let $-\PP \subseteq \PP^{\pm}$ be the set of all $-n$ for $n \in \PP$. Given a labelled weighted poset $P = ([n],<_P,\epsilon)$, an \emph{enriched $P$-partition} is a map $f: [n]\longrightarrow \PP^{\pm} $ that satisfies the two following conditions: \begin{itemize} \item[(i)] If $i <_P j$ and $i < j$, then $f(i) < f(j)$ or $f(i) = f(j) \in \PP$. \item[(ii)] If $i <_P j$ and $i>j$, then $f(i) < f(j)$ or $f(i) = f(j) \in -\PP$. \end{itemize} We let $\mathcal{L}_{\PP^{\pm}}(P)$ denote the set of enriched $P$-partitions. \end{defn} \begin{defn}[$q$-Deformed generating function, \cite{GriVas22}] Consider the set of indeterminates $X = \left\{x_1,x_2,x_3,\ldots\right\}$, the ring $\CC \left[\left[ X \right]\right]$ of formal power series on $X$ where $\CC$ is the set of complex numbers, and let $q \in \CC$ be an additional parameter. Given a labelled weighted poset $([n], <_P, \epsilon)$, define its generating function $\Gamma^{(q)}([n], <_P, \epsilon) \in \CC \left[\left[ X \right]\right]$ as \begin{equation*} \label{eq : weightGamma} \Gamma^{(q)}([n], <_P, \epsilon) = \sum_{f\in\mathcal{L}_{\PP^\pm}([n],<_{P}, \epsilon)} \prod_{1\leq i\leq n}q^{[f(i)<0]}x_{|f(i)|}^{\epsilon(i)}, \end{equation*} where $[f(i)<0] = 1$ if $f(i)<0$ and $0$ otherwise. \end{defn} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Enriched $q$-monomial and $q$-fundamental quasisymmetric functions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We state without proofs the required definitions and propositions from \cite{GriVas22}. The main building block of this previous work is the $q$-deformed generating function for enriched $P$-partitions on labelled weighted chains that we call \emph{universal quasisymmetric functions}. \begin{defn}[Universal quasisymmetric functions] Given a \emph{composition}, i.e. a sequence of positive integers $\alpha = (\alpha_1, \alpha_2, \ldots, \alpha_n)$ with $n$ entries, and a permutation $\pi=\pi_1\dots\pi_n$ of $S_n$, we let $P_{\pi,\alpha} = ([n],<_\pi,\alpha)$ be the labelled weighted poset on the set $[n]$, where the order relation $<_\pi$ is such that $\pi_i <_\pi \pi_j$ if and only if $i < j$ and where $\alpha$ is the weight function sending the vertex labelled $\pi_i$ to $\alpha_i$ (see \cref{fig : monomial}). Define the \emph{$q$-universal quasisymmetric function} \begin{equation*} U^{(q)}_{\pi,\alpha} = \Gamma^{(q)}([n],<_\pi, \alpha). \end{equation*} \begin{figure}[htbp] \begin{center} \begin{tikzcd}[row sep = small] {\pi_1,\ \alpha_1} \arrow[r, very thick] & {\pi_2,\ \alpha_2} \arrow[r, very thick] & \cdots\cdots\cdots \arrow[r, very thick] & {\pi_n,\ \alpha_n} \end{tikzcd} \end{center} \caption{The labelled weighted poset $P_{\pi,\alpha}$.} \label{fig : monomial} \end{figure} \end{defn} \noindent Universal quasisymmetric functions belong to the subalgebra of $\CC \left[\left[ X \right]\right]$ called the ring of \emph{quasisymmetric functions ($\QSym$)}, i.e. for any strictly increasing sequence of indices $i_1 < i_2 <\cdots< i_p$ the coefficient of $x_1^{k_1}x_2^{k_2}\cdots x_p^{k_p}$ is equal to the coefficient of $x_{i_1}^{k_1}x_{i_2}^{k_2}\cdots x_{i_p}^{k_p}$. They are directly connected to classical bases of $\QSym$, as $L_{\pi}= U^{(0)}_{\pi,[1^n]}$ (resp. $K_{\pi}= U^{(1)}_{\pi,[1^n]}$) is the Gessel's \emph{fundamental} (\cite{Ges84}) (resp. Stembridge's \emph{peak}, \cite{Ste97}) quasisymmetric function indexed by $\pi$. (As usual, $1^n$ denotes $n$ consecutive $1$'s: $1,1,\ldots,1$.) Moreover, if we let $id_{n} = 1~2\dots n $ and $\overline{id_{n}} = n~n-1\dots 1$, then $U^{0}_{\overline{id_{n}},\alpha} = M_\al$ is the \emph{monomial} (\cite{Ges84}), $U^{(0)}_{id_{n},\alpha} = E_\al$ the \emph{essential} (\cite{Hof15}) and $U^{(1)}_{id_{n},\alpha} = \eta_\al$ the \emph{enriched monomial} (\cite{Hsi07, GriVas21}) quasisymmetric functions indexed by $\al$. Moreover universal quasisymmetric functions satisfy the explicit expression \begin{equation} U_{\pi,\alpha}^{(q)}=\sum_{\substack{i_{1}\leq i_{2}\leq \dots\leq i_{n};\\j\in\Peak(\pi)\Rightarrow i_{j-1} p-1 = 1$. \end{example} % % \begin{remark}[Permutation statistics] Extended peak sets look like an intermediary statistic between peak and descent sets. Any peak set is a $1$-extended peak set, and any descent set on permutations of $n$ elements is a $p$-extended peak set for $p\geq n$. Moreover, given a permutation $\pi$ in $S_n$ and an integer $p \geq 1$, we can define ${\Peak}_p(\pi)$ as \begin{align*} {\Peak}_p(\pi) = \{i \in \Des(\pi) | i \leq p - 1 \mbox{ or } \exists \; 1 \leq j \leq p \mbox{ such that } i-j \notin \Des(\pi)\}. \end{align*} On the one hand, $\Peak(\pi) = {\Peak}_1(\pi) \subseteq {\Peak}_p(\pi) \subseteq \Des(\pi)$. On the other hand, ${\Peak}_p(\pi) \subseteq_p [n-1]$. For instance let $\pi = 54163287$. We have ${\Peak}_1(\pi) = \Peak(\pi) = \{4,7\} \subseteq {\Peak}_2(\pi) = \{1,4,5,7\} \subseteq {\Peak}_3(\pi) = \{1,2,4,5,7\} = \Des(\pi)$. \end{remark} % We count the number of extended peak sets. % \begin{proposition} Let $n,p \in \PP$. Define $s^{(p)}_n$ to be the number of $p$-extended peak sets on $n$ elements. Extend the definition with $s^{(p)}_0 = 0$ for all positive $p$. One has \begin{equation} s^{(p)}_n = \begin{cases} 2^{n-1}\; \mbox{ if } \; n \leq p,\\ \sum_{k=0}^{p} s^{(p)}_{n-k-1} = \sum_{k=1}^{p+1} s^{(p)}_{n-k}\; \mbox{ if } \; n > p.\\ \end{cases} \end{equation} \end{proposition} % % \begin{proof} The result is immediate for $n \leq p$. For $n>p$, there is a bijection between $p$-extended peak sets on $n$ elements and the union of $p$-extended peak sets on $n-1-k$ elements for $k \in [0,p]$. Indeed, given a set $I \subseteq_p [n-1]$, define $k \leq p$ as the integer such that $[n-k, n-1]$ is the maximum sequence of consecutive integers in $I$ containing $n-1$. If $n-1 \notin I$ we define $k=0$ and assume $[n, n-1] = \emptyset$. We map $I$ to the unique element $J \subseteq_p [n-k-2]$ such that $I = J \cup [n-k, n-1]$. This mapping is clearly one-to-one and the result follows. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Extended peak quasisymmetric functions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent We proceed with the definition of the relevant subfamilies of $q$-fundamentals. % \begin{defn}[Extended-peak quasisymmetric functions] \label{def.extended_peak_qsym} Let $n, p \in \PP$, and let $\rho_p$ denote the root of unity $\rho_p = e^{-i\pi (p-1)/(p+1)}$. Thus, $\rho_1 = 1$, $\rho_2 = e^{-i\pi/3}$, $\rho_3 = e^{-i\pi/2},\dots$. Note that $-\rho_p$ is a primitive $p+1$-th root of unity, i.e., $(-\rho_p)^{p+1}=1$ but $(-\rho_p)^j \neq 1$ for $1\leq j < p+1$. Given a subset $I\subseteq [n-1]$, we define the $p$-extended peak quasisymmetric function indexed by $I$ \begin{equation} L^p_{n, I} = L^{(\rho_p)}_{n, I}. \end{equation} Define $\mathcal{P}^p \subseteq \QSym$ to be the subalgebra of $\QSym$ spanned by $(L^p_{n, I})_{n\geq0, I\subseteq[n-1]}$, and let $\mathcal{P}^p_n \subseteq \QSym_n$ be its subspace composed of quasisymmetric functions of degree $n$ (that is, the vector space spanned by $(L^p_{n, I})_{I\subseteq[n-1]}$). We call $\mathcal{P}^p$ the \emph{algebra of $p$-extended peaks}. \end{defn} % We remark that $\mathcal{P}^p$ is actually a Hopf subalgebra of $\QSym$ (by \cref{rmk : coproduct}). \cref{def.extended_peak_qsym} gives extended peak functions over all subsets. However, we know from \cref{thm : basis} that they do not span $\QSym$. As a result, for all $p \in \PP$, the family $(L^p_{n, I})_{n\geq0, I\subseteq[n-1]}$ is not linearly independent and some indices are redundant. We characterise these set indices. First, for $n, p \in \PP$, if a set $I$ is not a $p$-extended peak set, then $L^p_{n, I}$ may be expressed in terms of other $p$-extended peak quasisymmetric functions. % \begin{theorem}[Extended peak functions over sets that are not $p$-extended peaks] \label{thm.non_valid_sets} Let $n, p \in \PP$ with $n \geq p+1$. Let $i$ be an integer such that $0 \leq i \leq n - 1 -p$, and $J \subseteq [n-1]$ be a subset that satisfies $[i+1,i+p+1] \cap J = \emptyset$ and $i \in J \cup \{0\}$. Then, the set $ [i+1,i+p] \cup J \nsubseteq_p [n-1]$ as it contains either a sequence of $p+1$ consecutive elements or the sequence $[1,p]$. Notice further that any set that is not a $p$-extended peak set may be written as such. We have the equality \begin{equation*} \sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}L^p_{n, I \cup J} = 0. \end{equation*} \end{theorem} % Secondly, we can compute explicitly the dimension of $\mathcal{P}^p_n$ for $n, p \in \PP$. % \begin{theorem}[Subspaces dimension] \label{thm.dimension} Let $n, p \in \PP$ be two positive integers. The dimension of $\mathcal{P}^p_n$ is equal to $s^{(p)}_n$, the number of $p$-extended peak sets on $n$ elements: \begin{equation*} \dim \mathcal{P}^p_n = s^{(p)}_n. \end{equation*} \end{theorem} % We postpone the proofs of \cref{thm.non_valid_sets,thm.dimension} respectively to \cref{section.non_valid_sets,section.dimension}. Combining them we characterise the subalgebra $\mathcal{P}^p$. % \begin{theorem}[Basis for algebra of extended peaks] \label{thm.algebra_extended_peaks} Let $p \in \PP$. The family $(L_{n, I}^{p})_{n\geq0, I\subseteq_p[n-1]}$ is a basis of the subalgebra $\mathcal{P}^p$ of $\QSym$. \end{theorem} \begin{proof} Fix $p \in \PP$. As $p$-extended peak quasisymmetric functions are special cases of $q$-fundamentals, the stability by multiplication is actually a direct consequence of Equation (\ref{eq : UU}). Then \cref{thm.non_valid_sets} shows that only $p$-extended peak quasisymmetric functions indexed by $p$-extended peak sets may be linearly independent. Finally, \cref{thm.dimension} shows that for all $n \in \PP$ the dimension of the finite vector space containing homogeneous quasisymmetric functions of degree $n$ is exactly the number of $p$-extended peak sets on $n$ elements. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proofs of \cref{thm.non_valid_sets,thm.dimension}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %As $p$-extended peak quasisymmetric functions are special cases of $q$-fundamentals, the stability by multiplication is actually a direct consequence of Equation (\ref{eq : UU}). We need to show that the basis elements are exactly the ones indexed by $p$-extended peak sets. We proceed in two steps. First we show that for a given $n \in \PP$ the dimension of the vector space spanned by $(L^p_{n, I})_{I\subseteq [n-1]}$ is equal to the number of sets $J$ such that $J\subseteq_p [n-1]$. Secondly we show that for any $I \subseteq [n-1]$ such that $I \nsubseteq_p [n-1]$ $L^p_{n, I}$ may be expressed as a linear combination of some $L^p_{n, J}$ with $J \subseteq_p [n-1]$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Extended peak functions indexed by generic sets} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{section.non_valid_sets} In order to show \cref{thm.non_valid_sets}, compute \begin{equation*} \sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}L^{(q)}_{I \cup J} \end{equation*} using Equation (\ref{eq : LEq}) for integers $i, n, p$ and set $J$ satisfying the conditions of the theorem. Note that for $I \subseteq [i+1, i+p]$, $i+1 \notin \Peak(I \cup J)$ (either $i+1 = 1$ or $i \in J$) and that $\Peak(I \cup J) \cap J = \Peak(J)$ irrelevant of the choice of $I$ (as $i+p+1 \notin J$). As a result, we can decompose in Equation (\ref{eq : LEq}) any subset or peak lacunar subset (i.e. $1$-extended peak subset) of $I\cup J$ as a (peak lacunar) subset of $I$ and a (peak lacunar) subset of $J$. Namely, \begin{align*} &\sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}L^{(q)}_{I \cup J} \\ &= \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|}\!\!\!\!\!\sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}\!\!\!\!\!\!\!\!\!\!\!\!\sum_{\substack{U \subseteq I\\ V \subseteq \Peak(I)\setminus \{i+1\} \\ U\cap V = \emptyset}}\!\!\!\!\!\!\!\!\!\!\!(-q)^{|V|}(q-1)^{|U|}\eta^{(q)}_{U' \cup V'-1 \cup V' \cup U \cup V-1 \cup V}. \end{align*} Next, invert summation indices in the last sums. \begin{align*} &\sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}L^{(q)}_{I \cup J} \\ &= \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|}\!\!\!\!\!\sum_{\substack{U \subseteq [i, i+p]\\ V \subseteq_1 [i+1, i+p] \\ U\cap V = \emptyset\\ U\cap V-1 = \emptyset}}\!\!\!\!\!\!\!\!(-q)^{|V|}(q-1)^{|U|}\eta^{(q)}_{U' \cup V'-1 \cup V' \cup U \cup V-1 \cup V}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \sum_{U \cup V \subseteq I \subseteq [i+1, i+p] \setminus V-1}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!(-1)^{|I|}. \end{align*} The last sum is obviously $0$ except when $U \cup V = [i+1, i+p] \setminus V-1$. As a result, \begin{align*} &\sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}L^{(q)}_{I \cup J} \\ &= \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|} \eta^{(q)}_{U' \cup V'-1 \cup V' \cup [i,i+p]}\sum_{V \subseteq_1 [i+1, i+p]}\!\!\!\!\!\!\!\!(-q)^{|V|}(q-1)^{p - 2|V|}(-1)^{p - |V|}. \end{align*} The summands in the sum over all $1$-extended peak sets $V \subseteq_1 [i+1, i+p]$ depend only on the cardinality of $V$. It easy to show (left to the reader) that \begin{equation*} |\{V\subseteq_1 [i+1, i+p], |V| = v\}| = \binom{p - v}{v}. \end{equation*} Subsequently, \begin{align*} &\sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}L^{(q)}_{I \cup J} \\ &= (-1)^{p}\!\!\!\!\!\!\!\!\! \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|} \eta^{(q)}_{U' \cup V'-1 \cup V' \cup [i+1,i+p]}\sum_{v = 0}^p(-1)^v\binom{p-v}{v}(-q)^{v}(q-1)^{p - 2v}. \end{align*} We use the following lemma. % \begin{lem}[\cite{Sur04}] \label{lem.binom} Let $n \in \PP$ and $x,y \in \CC$, one has \begin{equation*} \sum_{k = 0}^n(-1)^k\binom{n-k}{k}(xy)^k(x+y)^{n-2k} = \sum_{j=0}^n x^{n-j}y^j. \end{equation*} \end{lem} % \noindent Denote for $n \in \PP, c \in \CC$, $[n]_c = (1-c^n)/(1-c)$. As a direct consequence of \cref{lem.binom}, \begin{align*} \sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}L^{(q)}_{I \cup J} &= \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|} \eta^{(q)}_{U' \cup V'-1 \cup V' \cup [i+1,i+p]}\sum_{t= 0}^{p}(-q)^{p-t},\\ &=[p+1]_{-q}\sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|} \eta^{(q)}_{U' \cup V'-1 \cup V' \cup [i+1,i+p]}. \end{align*} End the proof with \begin{equation*} [p+1]_{-\rho_p} = \frac{1 - (-\rho_p)^{p+1}}{1+\rho_p} = 0. \end{equation*} %To see that the basis elements are exactly the ones indexed by a valid $p$-extended peak set, we show the following theorem. %\begin{theorem} %Let $n, p \in \PP$ with $n \geq p+1$, $i$ be an integer such that $0 \leq i \leq n - 1 -p$ and $J \subseteq [n-1]$ be a subset that satisfies $[i+1,i+p+1] \cap J = \emptyset$ and $i \in J \cup \{0\}$. Then, the set $ [i+1,i+p] \cup J \nsubseteq_p [n-1]$ as it contains either a sequence of $p+1$ consecutive elements or the sequence $[1,p]$. Moreover, we have the following equality. %\begin{equation*} %\sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}L^p_{I \cup J} = 0. %\end{equation*} %\end{theorem} % %We assume $i+p+1 \notin J$. %We have two cases. %Assume $i \in J$ or $i=0$. %\begin{align*} %&\sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}L^{(q)}_{J \cup I} \\ %&= \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|}\!\!\!\!\!\sum_{I \subseteq [i+1, i+p]}(-1)^{|I|}\!\!\!\!\!\!\!\!\!\!\!\!\sum_{\substack{U \subseteq I\\ V \subseteq \Peak(I)\setminus \{i+1\} \\ U\cap V = \emptyset}}\!\!\!\!\!\!\!\!\!\!\!(-q)^{|V|}(q-1)^{|U|}\eta^{(q)}_{U' \cup V'-1 \cup V' \cup U \cup V-1 \cup V}\\ %&= \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|}\!\!\!\!\!\sum_{\substack{U \subseteq [i, i+p]\\ V \subseteq_1 [i+2, i+p] \\ U\cap V = \emptyset\\ U\cap V-1 = \emptyset}}\!\!\!\!\!\!\!\!(-q)^{|V|}(q-1)^{|U|}\eta^{(q)}_{U' \cup V'-1 \cup V' \cup U \cup V-1 \cup V}\!\!\!\!\!\!\! %\sum_{U \cup V \subseteq I \subseteq [i+1, i+p] \setminus V-1}\!\!\!\!\!\!\!(-1)^{|I|}\\ %&= \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|} \eta^{(q)}_{U' \cup V'-1 \cup V' \cup [i,i+p]}\sum_{V \subseteq_1 [i+2, i+p]}\!\!\!\!\!\!\!\!(-q)^{|V|}(q-1)^{p - 2|V|}(-1)^{p - |V|}\\ %&= (-1)^{p+1}\!\!\!\!\!\!\!\!\! \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|} \eta^{(q)}_{U' \cup V'-1 \cup V' \cup [i+1,i+p]}\sum_{t\geq 0}(-1)^t\binom{p-t}{t}(-q)^{t}(q-1)^{p - 2t}\\ %&= \!\!\!\!\!\!\!\!\! \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|} \eta^{(q)}_{U' \cup V'-1 \cup V' \cup [i+1,i+p]}\sum_{u= 0}^{p}(-q)^{p-u}\\ %&= \!\!\!\!\!\!\!\!\! \sum_{\substack{U' \subseteq J\\ V' \subseteq \Peak(J) \\ U'\cap V' = \emptyset}}\!\!\!\!\!\!\!(-q)^{|V'|}(q-1)^{|U'|} \eta^{(q)}_{U' \cup V'-1 \cup V' \cup [i+1,i+p]}[p+1]_{-q} %\end{align*} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Finite subspaces dimension} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{section.dimension} For $n \in \PP$ and $q \in \CC$, denote $B_n^{(q)}$ the transition matrix between $(L_{n, I}^{(q)})_{I \subseteq [n-1]}$ and $(\eta^{(q)}_{n, J})_{J \subseteq [n-1]}$ with coefficients given by Equation (\ref{eq : LEq}). Columns and rows are indexed by subsets $I$ of $[n-1]$ sorted in reverse lexicographic order. A subset $I$ is before subset $J$ iff the word obtained by writing the elements of $I$ in decreasing order is before the word obtained from $J$ for the lexicographic order. The column indexed by the subset $I$ corresponds to $L_{n, I}^{(q)}$ and the row indexed by $J$ to $\eta^{(q)}_{n, J}$ (as a direct consequence $B_n^{(q)}$ is the transpose of the similar matrix defined in \cite{GriVas22}). For $n=0$, assume $B_0^{(q)}$ to be the empty matrix. \begin{example} For $n=4$, the transition matrix $B_{4}^{(q)}$ between $(L_{I}^{(q)})_{I \subseteq [3]}$ and $(\eta^{(q)}_{J})_{J \subseteq [3]}$ is given by \begin{equation*} B_{4}^{(q)} = \begin{array}{c|cccccccc} & \emptyset & \{1\} & \{2\} & \{2, 1\} & \{3\} & \{3, 1\}& \{3, 2\} & \{3, 2, 1\}\\ \hline \emptyset & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ \{1\} & 0 & q-1 & 0 & q-1 & 0 & q-1 & 0 & q-1\\ \{2\} & 0 & 0 & q-1 & q-1 & 0 & 0 & q-1 & q-1\\ \{2, 1\} & 0 & 0 & -q & (q-1)^2 & 0 & 0 & -q & (q-1)^2\\ \{3\} & 0 & 0 & 0 & 0 & q-1 & q-1 & q-1 & q-1\\ \{3, 1\} & 0 & 0 & 0 & 0 & 0 & (q-1)^2 & 0 & (q-1)^2 \\ \{3, 2\} & 0 & 0 & 0 & 0 & -q & -q & (q-1)^2 & (q-1)^2\\ \{3,2,1\} & 0 & 0 & 0 & 0 & 0 & -q(q-1) & -q(q-1) & (q-1)^3\\ \end{array} \end{equation*} \end{example} Our goal is to compute the dimension of the kernel of $B_n^{(q)}$ to get the dimension of the vector subspace $\mathcal{P}^p_n$ as $$\dim \mathcal{P}^p_n = \rank(B_n^{(q)}) = 2^{n-1} - \dim \ker B_n^{(q)}.$$ We show the following proposition. % \begin{proposition} \label{prop.kernel} Let $n, p \in \PP$ be two positive integers. We have \begin{equation*} \dim \ker B_n^{(\rho_p)} = \begin{cases}\sum_{k =1}^{p+1} \dim \ker B_{n-k}^{(\rho_p)} + [n > p+1]2^{n-p-2}\;\mbox{ for } n > p,\\ 0\;\mbox{ for } n \leq p. \end{cases} \end{equation*} \end{proposition} % \begin{proof} The second case is a direct consequence of the fact that the matrix $B_n^{(\rho_p)}$ is invertible for $n\leq p$ (see \cite{GriVas22}). To show the general recurrence, assume that $n>p$. As in \cite{GriVas22}, notice that the matrix $B_n^{(q)}$ is block upper triangular. For each $k \in [n]$, let $A_k^{(q)}$ denote the transition matrix from $(L_{n, I}^{(q)})_{I \subseteq [n-1],~ \max(I) = k-1}$ to $(\eta^{(q)}_{n, J})_{J \subseteq [n-1],~\max(J) = k-1}$ (where $\max\varnothing := 0$); this actually does not depend on $n$. Note that $A_k^{(q)}$ is a $2^{k-2} \times 2^{k-2}$-matrix if $k \geq 2$, whereas $A_1^{(q)}$ is a $1 \times 1$-matrix. We have \begin{equation*} B_{n}^{(q)} = \begin{pmatrix} A_1^{(q)}& *& *& \hdots& *\\ 0&A_2^{(q)}& *& \hdots& *\\ 0&0&A_3^{(q)}&\hdots& *\\ 0&0&0&\ddots&*\\ 0&0&0&0&A_n^{(q)}\\ \end{pmatrix}. \end{equation*} We have the following lemma: \begin{lem} \label{lem : rec} The matrices $\left(B_n^{(q)}\right)_n$ and $\left (A_n^{(q)}\right)_n$ satisfy the following recurrence relations (for $n \geq 1$ and $n \geq 2$, respectively): \begin{equation*} B_{n}^{(q)} = \begin{pmatrix} B_{n-1}^{(q)}&B_{n-1}^{(q)}\\ 0 &A_n^{(q)}\\ \end{pmatrix}, \qquad A_{n}^{(q)} = \begin{pmatrix} (q-1)B_{n-2}^{(q)}& (q-1)B_{n-2}^{(q)}\\ -qB_{n-2}^{(q)}&(q-1)A_{n-1}^{(q)}\\ \end{pmatrix}. \end{equation*} \end{lem} \noindent Consider for $n \geq 2$ and coefficients $\alpha, \beta \in \CC$ the kernel of the matrix $\alpha A_{n+1}^{(q)} + \beta B_n^{(q)}$. Let $X$ be a $2^{n-1}$ vector and denote $X^1$ and $X^2$ the two vectors of size $2^{n-2}$ such that $ X = \begin{pmatrix} X^1\\ X^2\\ \end{pmatrix}. $ We compute \begin{align} \label{equation.kernel_recurrence} \left(\alpha A_{n+1}^{(q)} + \beta B_n^{(q)}\right)X = 0 \Leftrightarrow \begin{cases}((q-1)\al+\beta)B_{n-1}^{(q)}(X^1+X^2) = 0\\ -q\al B_{n-1}^{(q)}X^1 + ((q-1)\al+\beta)A_{n}^{(q)}X^2 = 0 \end{cases} \end{align} Two cases arise from the previous equation. Either $((q-1)\al+\beta) \neq 0$ and \begin{align} \label{equation.kernel_recurrence.case_1} \left(\alpha A_{n+1}^{(q)} + \beta B_n^{(q)}\right)X = 0 \Leftrightarrow \begin{cases}B_{n-1}^{(q)}(X^1+X^2) = 0\\ \left(((q-1)\al+\beta)A_{n}^{(q)} + q\al B_{n-1}^{(q)}\right)X^2 = 0 \end{cases} \end{align} or $((q-1)\al+\beta) = 0$ and \begin{align} \label{equation.kernel_recurrence.case_2} \left(\alpha A_{n+1}^{(q)} + \beta B_n^{(q)}\right)X = 0 \Leftrightarrow q\al B_{n-1}^{(q)}X^1 = 0 \end{align} Consider the sequence of coefficients \begin{align*} \left(\alpha_0^{(q)}\;\;\;\; \beta_0^{(q)}\right) &= (0\;\;\;\; 1)\\ \left(\alpha_{n+1}^{(q)}\;\;\;\; \beta_{n+1}^{(q)}\right) &= \left(\alpha_{n}^{(q)}\;\;\;\; \beta_{n}^{(q)}\right)\begin{pmatrix} q-1&q\\ 1&0\\ \end{pmatrix}, \mbox{ for } n \geq 0. \end{align*} Solving the recurrence we have for integer $n \geq 1$ \begin{align*} \left(\alpha_{n}^{(q)}\;\;\;\; \beta_{n}^{(q)}\right) &= (0\;\;\;\; 1){\begin{pmatrix} q-1&q\\ 1&0\\ \end{pmatrix}}^n\\ &= (-1)^n(0\;\;\;\; 1){\begin{pmatrix} [n+1]_{-q}&-q[n]_{-q}\\ -[n]_{-q}&q[n-1]_{-q}\\ \end{pmatrix}}\\ &=(-1)^n(-[n]_{-q}\;\;\;\; q[n-1]_{-q}), \end{align*} where for integer $i$ and complex number $c$ recall that $[i]_c = (1 - c^i)/(1-c)$. Finally notice that for integer $n \geq 1$ \begin{align*} \alpha_{n}^{(q)} (q-1) + \beta_{n}^{(q)} &= (-1)^n\left([n]_{-q} - q(-q)^{n-1}\right)\\ &=(-1)^n[n+1]_{-q}. \end{align*} Get back to the case $q=\rho_p$ for some positive integer $p \in \PP$. As a direct consequence of the definition of $\rho_p$ in \cref{def.extended_peak_qsym}, we have \begin{align*} &[p+1]_{-\rho_p} = 0;\\ &[n]_{-\rho_p} \neq 0,\; 1\leq n \leq p. \end{align*} As a result, if $q=\rho_p$, one may iterate the recurrence in Equation (\ref{equation.kernel_recurrence}) $p$ times with the case of Equation (\ref{equation.kernel_recurrence.case_1}) and one more time to go to the case of Equation (\ref{equation.kernel_recurrence.case_2}). Recall that $\beta_{p+1}^{(\rho_p)} = \rho_p[p]_{-\rho_p} \neq 0$ to conclude the proof. \end{proof} % Noticing that for $n > p+1$, $2^{n-1} = 2^{n-2} + 2^{n-3} + \dots + 2^{n-p-1} + 2\cdot 2^{n-p-2}$ we can deduce the rank of $B_n^{(\rho_p)}$ using \cref{prop.kernel}. We get \begin{equation} \rank \left (B_n^{(\rho_p)}\right) = 2^{n-1} - \dim \ker B_n^{(\rho_p)} = \begin{cases}\sum_{k =1}^{p+1} \rank\left(B_{n-k}^{(\rho_p)}\right)\;\mbox{ for } n > p,\\ 2^{n-1}\;\mbox{ for } 1 \leq n \leq p.\end{cases} \end{equation} We conclude that the sequence of subspace dimensions $(\mathcal{P}^p_n)_n$ follows the same recurrence with the same initial conditions as the sequence of the numbers of $p$-extended peak sets $(s_n^p)_n$. \cref{thm.dimension} follows. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\subsubsection{Number of valid extended peak sets} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %The next step in the proof of \cref{thm.algebra_extended_peaks} is to show that for $n, p \in \PP$ the number of valid $p$-extended peak sets on $n$ elements corresponds to the rank of the matrix $B_n^{(\rho_p)}$ of Theorem \ref{thm.rank}. We show that they actually follow the same recurrence relation. Let $s^{(p)}_n$ be the number of valid $p$-extended peak sets on $n$ elements. Clearly $s^{(p)}_n = 2^{n-1}$ for $1 \leq n \leq p$ and $s^{(p)}_{p+1} = 2^p -1$. Let $n>p$. We build the following bijection. Given a set $I \subseteq_p [n-1]$, we denote $S_k^{n-1}=\{n-k, n-k+1, \dots, n-1\}$ the maximum sequence of consecutive integers of $I$ containing $n-1$ (obviously $k \leq p$). Assume $k=0$ if $n-1 \notin I$. We know that $J = I \setminus S_k^{n-1} \subseteq_{p}[n-k-2]$. Moreover there is a one-to-one correspondance between sets $J \subseteq_{p}[n-k-2]$ and set $I\subseteq_p [n-1]$ whose maximum sequence of consecutive integers containing $n-1$ is $S_k^{n-1}$. As a result %\begin{proposition} %Let $n,p \in \PP$ such that $n>p$. Recall the definition of $s^{(p)}_n$ above. One has %\begin{equation} %s^{(p)}_n = \sum_{k=0}^{p} s^{(p)}_{n-k-1} = \sum_{k=1}^{p+1} s^{(p)}_{n-k} %\end{equation} %\end{proposition} %Finally %\begin{theorem} %Let $n, p \in \PP$ be two positive integers. The rank of the transition matrix $B_n^{(\rho_p)}$ is given by the number of valid $p$-extended peak sets on $n$ elements $s^{(p)}_n$. %\begin{equation} %rank \left (B_n^{(\rho_p)} \right) = s^{(p)}_n %\end{equation} %\end{theorem} %% if you use biblatex then this generates the bibliography %% if you use some other method then remove this and do it your own way \printbibliography \end{document}