\documentclass[10pt]{article}
\usepackage{amsmath,amsfonts}
\usepackage{amssymb}
\usepackage{mathabx}
\usepackage{graphicx}
%\usepackage{color}

\addtolength{\topmargin}{-1.0in}
\addtolength{\textheight}{2.1in}
\addtolength{\oddsidemargin}{-.2in}
\addtolength{\textwidth}{.4in}
\pagestyle{empty}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\F}{\mathcal{F}}
\renewcommand{\L}{\mathcal{L}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\Q}{\mathcal{Q}}
\renewcommand{\S}{\mathcal{S}}
\newcommand{\sgn}{\mathrm{sgn}}
\newcommand{\wt}{\mathrm{wt}}
\newcommand{\lam}{\lambda}
\newcommand{\rk}{\mathrm{rk}}
\newcommand{\Gr}{\mathrm{Gr}}
\newcommand{\Fl}{\mathrm{Fl}}
\newcommand{\eqdef}{
\smash{ 
\stackrel{\text{def}} {=} 
} 
}

\newcommand{\Br}{
\mbox{\small $\smash{ 
  \stackrel {\text{deg}} {\leq}
}$
}}

\newcommand{\dless}{\ {<\hspace{-.6em}\cdot}\ }
\newcommand{\dgr}{\ {>\hspace{-1em}\cdot}\ \ }

%\newcommand{\multi}[2]{\left(\!\binom{#1}{#2}\!\right)}
%\newcommand{\multi}[2] { \genfrac {(} {)} {0em} {} {#1} {#2} }
\newcommand{\multi}[2]{\left(\!\left(\!
\genfrac{}{}{0pt}{}{#1}{#2}\!\right)\!\right)}

\newcommand{\stirling}[2]{\left\{
\genfrac{}{}{0pt}{}{#1}{#2}\right\}}

\newcommand{\cycle}[2]{\left[
\genfrac{}{}{0pt}{}{#1}{#2}\right]}

\newcommand{\actson}{\mathbin{\rotatebox[origin=c]{-90}{$\circlearrowright$}}}


\begin{document}
\centerline{\bf Math 880 \hfill{\large\bf \quad Homework 6}\hfill Fall 2025}
\vspace{1em}

\noindent  
If you get significant help from a reference or a person, give explicit credit. 
\\[1em]
{\sc Notes.} 
Consider a poset $(\P,\leq)$ with minimal element $\hat 0$.
A rank function $\rk : \P\to\N$ is defined by $\rk(\hat 0)=0$ and
$\rk(a)+1=\rk(b)$ for every covering $a\dless b$.

A {\it lattice} $\L$ is a poset having, for all $a,b\in \L$, 
a well-defined meet $a\wedge b = \text{inf}\{a,b\}$ and join $a\vee b=\text{sup}\{a,b\}$,
and it is {\it distributive} if $(a\wedge b)\vee c = (a\vee c)\wedge (b\vee c)$,
which is equivalent to $(a\wedge b)\vee c = (a\vee c)\wedge (b\vee c)$.
Any finite distributive lattice $\L$ is isomorphic to the order ideals 
of its subposet $\P$ of join-irreducibles: that is, $\L\cong J(\P) \eqdef $ 
$\{I \subset \P \text{ with } (b\in I \ \&\ a\leq b)\Rightarrow a\in I\}$,
ordered by inclusion.

A lattice is {\it semi-modular} if $\rk(a)+\rk(b)\geq \rk(a\wedge b) + \rk(a\vee b)$.
An {\it atom} is a covering element $a\dgr \hat 0$, and $\L$ is {\it atomic} if every element is
a join of atoms (not necessarily uniquely). A lattice is {\it geometric} if it is semi-modular 
and atomic; this is equivalent to the combinatorial structure known as a {\it matroid}.

We define the {\it incidence algebra}: 
$$\textstyle
I(\P) \ =\ \{\alpha:\mathrm{Int}(\P)\to\CC\}
\ \cong\ \bigoplus_{a\leq b}\CC[a,b],
\qquad
\alpha \cong \sum\limits_{a<b} \alpha(a,b)\,[a,b],
$$
\\[-1em]
all functions on the set $\mathrm{Int}(\P)$ 
of intervals $[a,b]=\{c \text{ with } a\leq c\leq b\}$, 
with product:
$$
(\alpha\cdot \beta)(a,b) = \sum_{c\,\in [a,b]}\alpha(a,c)\, \beta(c,b),
\qquad
[a,b]\cdot [c,d] = \left\{\!\!\!\begin{array}{c@{\ \ }l}\
[a,d] & \text{if } b = c \\ 0 & \text{otherwise.}
\end{array}\right.
$$
We can realize $I(\P)$ as certain upper-triangular matrices:
writing $\P=\{a_1,\ldots, a_n\}$ in non-decreasing order ,
$[a_i,a_j]\in I(\P)$ is represented by the unit matrix $E_{ij}\in M_{n\times n}(\CC)$.
The incidence algebra has identity element $\delta = \sum_{a\in\P}\,[a,a]$,
zeta function $\zeta = \sum_{a\leq b}\,[a,b]$, and Mobius function 
$\mu = \zeta^{-1}$, so that $\zeta\cdot\mu = \delta$ is equivalent to
the recursion:
$\mu(a,a)=1$ and $\sum_{c\in [a,b]} \mu(a,c)=0$.

We consider several standard semi-infinite posets $\P_\infty$ which 
contain a minimal element $\hat 0$ as well as
standard elements $\hat 1,\hat 2,\ldots$,
and which have a natural equivalence relation $[a,b]\sim[c,d]$
which splits $\mathrm{Int}(\P)$ into equivalence
classes $\bar 0,\bar 1,\bar 2,\ldots$, where 
$\bar n$ is the equivalence class of $[\hat 0,\hat n]$.
We define the {\it reduced incidence algebra}: 
$$
R(\P_\infty) = \{\,\alpha\in I(\P_\infty)\text{ with } \alpha(a,b) = \alpha(c,d) \text{ for }
[a,b]\sim [c,d]\,\} \ =\ \bigoplus_{n= 0}^\infty \CC\,\overline{n}.
$$
We can write $\alpha$ as a kind of generating function
for the sequence $a_n=\alpha(\hat 0,\hat n)$:
$$
\alpha= a_0\bar 0+a_1\bar 1
+a_2\bar 2+a_3\bar 3+\cdots.
$$
$R(\P_\infty)$ contains the identity $\delta$, 
the zeta function $\zeta$, and the M\"obius function $\mu=\zeta^{-1}$.

A {\it binomial poset} is a ranked poset $\P_\infty$ with a standard chain  
$\hat 0\dless \hat 1\dless \hat 2\dless\cdots$,
such that every interval $[a,b]$ with length $\ell(a,b) =\rk(b)-\rk(a)=n$
has $B(n)$ maximal chains. We let $[a,b]\sim[c,d]$ whenever $\ell(a,b)=\ell(c,d)$.
The algebra $R(\P)$ is isomorphic to 
the formal power series ring $\CC[[x]]$, with $\bar n$ corresponding to
$x^n/B(n)$, so that:
$$
\alpha \cong a_0 + a_1 x + a_2\tfrac{x^2}{B(2)} + a_3 \tfrac{x^3}{B(3)}+\cdots.
$$

The posets $\D_n$ of divisors of $n$ have 
the semi-infinite union $\P=\D_\infty=\{1,2,3,\ldots\}$ ordered by divisibility. 
This has standard elements $\hat n = n$ (which do not lie on a chain), 
and the equivalence of intervals is
$[a,b] \sim [c,d]$ whenever $b/a = d/c$,\footnote{
This is stronger than rank equivalence $\ell(a,b)=\ell(c,d)$
and isomorphism equivalence $[a,b]\cong[c,d]$.
}
which induces equivalence classes $\bar n=\overline{[1,n]}$, making a basis of
the reduced algebra $R(\P) = \bigoplus_{n\geq 1} \CC\,\bar n$.
We have $\bar n\bar m = \overline{nm}$, 
so $R(\P)$ embeds in the ring of complex functions via 
$\bar n\cong n^{-s}$, where $s$ is a complex variable, 
so that $\alpha \cong \sum_{n\geq 1} a_n/n^s$.

\pagebreak

\noindent
{\sc Problems}
\\[1em]
{\bf 1.} 
Direct product of posets: $\P\times\Q$, with $(p,q)\leq (p',q')$ whenever
$p\leq p'$ and $q\leq q'$. Prove: M\"obius function of the product 
is the product of M\"obius functions of $\P$ and $\Q$:
$$
\mu_{\P\times\Q}((p,q), (p',q'))\ =\ \mu_{\P}(p,p')\ \mu_{\Q}(q,q').
$$
{\bf 2.} For the poset $\P=\D_{18}$, the 6-element poset of
divisors of $18=2\cdot3^2$ ordered by divisibility,
work out the M\"obius function $\mu(a,b)$ in several ways:
\\[.5em]
{\bf a.} Write a $6{\times}6$ matrix $Z$ corresponding to $\zeta(a,b)=1$ 
for all $a\leq b$, and invert by Gaussian elimination 
on a double matrix $[Z\,|\,I\,]$, row reducing to 
$[\,I\,|\,M]$ so $M=Z^{-1}$.
\\[.5em]
{\bf b.} Write $Z = I+N$, for identity $I$ and strictly upper-triangular $N$, 
nilpotent with $N^6=0$. By computer, expand the
geometric series $M= (I+N)^{-1} = I-N+N^2-\cdots$.
\\[.5em]
{\bf c.} For each $a\in \P$, draw a copy of the Hasse diagram (a $1\times 2$ rectangle).
Mark $\mu(a,a)=1$, then work upwards recursively using 
$\mu(a,b)=-\sum_{a\leq x<b} \mu(a,x)$. 
\\[.5em]
{\bf d.} Repeat (c) using the Weisner recurrence, within each $[a,b]$
choosing some $c\dgr a$: 
$$
\mu(a,b) = -\sum_x \mu(a, x)
\ \text{ summed over } x\in [a,b] \text{ with }
c \not\leq x\dless b.
$$
\\[-1em]
Do only for the $[a,b]$ where Weisner uses fewer terms than the full recurrence.
Also look up: when is the Weisner recurrence valid?
\\[.5em]
{\bf e.} Apply the product formula of \#1 above to $\D_{18}\cong[0,1]{\times}[0,2]$, 
the direct product of two chains.
Match this with Mobius' original formula for $\mu(n) = \mu(1,n)$:
namely  $\mu(n)= (-1)^k$ if $n$ is the product of $k$ distinct primes, 
and $\mu(n)=0$ if $n$ is divisible by a square number.
%\\[.5em]
%{\bf e.} Evaluate Phillip Hall's Formula:
%$\mu[a,b]=\hat c_0-\hat c_1 + \hat c_2-\cdots$,
%where $\hat c_d$ is the number of chains of length $d$ 
%from $a$ to $b$ in $\P$, starting with $\hat c_0=0, \hat c_1=1$.
%\\[.5em]
%{\bf f.} Consider $\P=\Q\,\sqcup\, \{\hat 0,\hat 1\}$,  
%where $\Q=\{a\in \P\text{ with } \hat 0<a<\hat 1\}$, 
%and form the simplicial complex $\Delta(Q)$ 
%whose elements are all chains in $\Q$. Draw a picture of the
%corresponding topological space, consisting of one-simplexes glued at their endpoints.
%
%Hall's Formula says $\mu[\hat 0,\hat 1]=\tilde \chi(\Delta(Q))$,
%the reduced Euler characteristic of the above topological space,
%the alternating sum of the number of simplexes of each 
%dimension, minus 1.
%Compute $\tilde\chi(\Delta(Q))$ from this definition.
%Also, find the simplest triangulation of this space, and 
%compute $\tilde\chi$ from that.
%\\[.5em]
%{\bf g.} Generalizing (d), for any interval $\P'=[a,b]\subset \P$,
%we have the corresponding open interval $\Q'=(a,b)$.
%For each $[a,b]$, draw the space of the simplicial complex $\Delta(\Q')$, 
%and count chains (or simplexes) to find $\tilde\chi(\Delta(\Q'))=\mu[a,b]$.
\\[1em]
{\bf 3.} Recall the Euler phi-function $\phi(n) = \#\{i\in[n] \text{ with } \gcd(i,n) = 1\}$.
\\[.5em]
{\bf a.}  Find a summation formula for $\sum_{d|n} \phi(d)$, and use Mobius inversion
for $\P = \D_\infty$ to express $\phi(n)$ in terms of $\mu(n) = \mu(1,n)$.
\\[.5em]
{\bf b.} Use the isomorphism of $R(\D_\infty)$ with the ring of Dirichlet series
to find an expression for $f(s) = \sum_{n\geq 1}\phi(n)/n^{s}$
in terms of the Riemann zeta function $\zeta(s) = \sum_{n\geq 1}1/n^{s}$.
\\[.5em]
{\bf c.} Use (b) to show that $\phi(n)$ grows sufficiently fast that
$\sum_{n\geq 1}\phi(n)/n^2$ is divergent.
Thus, there is no $\varepsilon>0$ 
such that $\phi(n) = \mathrm{o}(n^{1-\varepsilon})$.
(For a challenge, be as analytically rigorous about this as possible.
Perhaps learn about Perron's formula.)
\\[1em]
{\bf 4.} Zaslavsky's Theorem (second part): 
Consider an affine hyperplane arrangement $\A$ in $\R^n$
with characteristic polynomial $\chi_\A(x) = \sum_{V\in\L(\A)} \mu(\hat 0, V) \,x^{\dim(V)}$.
Then the hyperplane complement
$$
\R^n\ \setminus\bigcup\limits_{H\in\A} \!\!H
$$ 
\\[-.8em]
has $b(\A)$ {\it bounded} regions, where:
$$b(\A)=(-1)^n \chi_\A(1).$$
Prove this using an appropriate Deletion-Restriction recurrence among $b(\A)$, $b(\A')$, and $b(\A'')$,
where we choose $H_\circ\in \A$ and take $\A'=\A\,\setminus\,\{H_\circ\}$, and
$$
\A'' = \{ H\cap H_\circ \subset H_\circ\text{ for } H \in \A' \},
$$
an arrangement of hyperplanes inside the $(n{-}1)$-dimensional space $H_0$.
Match this with the known Deletion-Restriction recurrence $\chi_\A(x) = \chi_{\A'}(x) - \chi_{A''}(x)$.
\\[1em]

\pagebreak

\noindent
{\bf 5.} For a finite field $F=\FF_q$, recall the $q$-Boolean poset $\B_n(q)$ 
of linear subspaces $V\subset F^n$ ordered by inclusion.
 The semi-infinite union $\B_1(q)\subset \B_2(q) \subset\cdots$ 
 via $F^1\subset F^2\subset\cdots$  is the Boolean poset 
 $\P_\infty=\B_\infty(q)$, with standard elements $\hat n =F^n$.
The reduced incidence algebra $R(\P_\infty)$ is isomorphic to $\CC[[x]]$, with 
basis element $\bar n$ corresponding to $x^n/[n]_q^!$, 
the ring of Eulerian generating functions:
$$
f(x) \ =\  \sum_{n\geq 0} a_n\frac{x^n}{[n]_q^!}
\ =\  a_0 +a_1x + a_2\frac{x^2}{1{+}q} + a_3\frac{x^3}{(1{+}q{+}q^2)(1{+}q)}+\cdots .
$$
{\bf a.} Explain why $\P_\infty$ is a binomial poset with 
$$
B(n) = [n]^{!}_q = \#\mathrm{Flag}(\FF_q^n)= [n]_q [n{-}1]_q\cdots [2]_q[1]_q,
\quad \text{where } [n]_q = \tfrac{q^n-1}{q-1}.
$$
{\bf b.} Show the reciprocal of $\zeta = \sum_{n\geq 0}\frac{x^n}{[n]_q^!} 
\stackrel{\text{def}}= \exp_q(x)$  is the power series
$$
\mu \ =\  \sum_{n\geq 0} (-1)^nq^{\binom n2} \frac{x^n}{[n]_q^!} 
\stackrel{\text{def}}= \text{ Exp}_q(-x),
$$
and determine the Mobius function $\mu(U,V)$ for any $U\subset V$ in $\B_\infty(q)$.
\\
{\it Hint:} Simplify $\zeta\cdot\mu$ with $q$-binomial thm $\prod_{i=1}^n (1+q^{i-1}x)
=\sum_{k=0}^n q^{\binom k2}\binom{n}{k}_{\!q} \, x^k$ (HW 5).
\\
{\it Note:} We determined $\mu$ in class using the Weisner recurrence: $\mu_n = (-q^{n-1})\mu_{n-1}$.
\\[.5em]
{\bf c.} For an $n$-dimensional $V\in\B_n(q)$ and a fixed $F^N$, let 
$$
\alpha(V)  \ =\ \#\{\text{linear}\,f:F^N\to V\}\ =\ q^{Nn},
$$
$$
\beta(V)  \ =\ \#\{\text{surjective linear}\,f:F^N\twoheadrightarrow V\}
$$
Show by linear algebra that $\alpha(V) \ =\ \sum_{W\subset V} \beta(W)$, and
solve for $\beta(V)$ by Mobius inversion, a summation
formula for the number of surjective $f:F^N\twoheadrightarrow F^n$.

Is $\beta(n)$ a good $q$-analog of $\text{surj}(N, n)=\#\{\,\text{surjective } f:[N]\twoheadrightarrow [n]\,\}$?
\\[.5em]
{\bf d.} Determine the number of injective linear mappings $f: F^n\hookrightarrow F^N$ directly by a simple product formula. 
\\[.5em]
{\bf e.} Show  by linear algebra that the number of surjective linear mappings $f:F^N\twoheadrightarrow F^n$
is equal to the number of injective linear mappings $f: F^n\hookrightarrow F^N$.
\\[.5em]
{\bf f.} Use the identity between the product in (d) and the sum in (c) to give another proof of the $q$-binomial theorm.


\end{document}

*****************************************************************

{\bf a.} Recall how we counted necklaces of $n$ beads chosen from $k$ colors,
orbits of the cyclic symmetry group $G=C_n$. Since $G$ has $\phi(n/d)$ permutations
with $d$ cycles, Burnside's Theorem showed that the number of orbits is
the necklace polynomial:
$$\textstyle
N_n(k) = \tfrac{1}{\#G} \sum_{\pi\in G} k^{\mathrm{cyc}(\pi)} = 
\tfrac{1}{n} \sum_{d|n} \phi(n/d) \, k^d.
$$
{\it Problem:} Count the number $M_n(k)$ of {\it aperiodic} necklaces, those with no cyclic symmetry,
so their orbit has size $n$. We use a form of inclusion-exclusion. Show that:
$$\textstyle
k^n = \sum_{d|n} d M_d(k).
$$
That is, if we consider $\alpha(n) = k^n$ and $\beta(n) = n M_n(k)$
as elements of $R(\P)$, we have $\alpha = \zeta\cdot \beta$.
Now give a formula for $M_n(k)$ via Mobius inversion.
\\[.5em]
{\it Note:} For an extension of finite fields $\FF_p\subset\FF_{q}$ with $q=p^n$,
the cyclic group $G=C_n$ is the Galois group, 
generated by the Frobenius automorphism $\Phi(x) = x^p$.
Elements of $\FF_{p^n}$ can be written as 
$a_1 x_\circ+a_2\Phi(x_\circ)+\cdots+a_n\Phi^{n-1}(x_\circ)$ 
for a fixed $x_\circ\in \FF_q$ and arbitrary $a_i\in \FF_p$,
so we may consider the coefficients as taking the role of $k=p$ colors in a necklace.
An orbit of $G$ comprises the roots of an irreducible polynomial over $\FF_p$, and
orbits of size $n$ are the roots of irreducible polynomials of degree $n$.
Thus $M_n(p)$ counts monic irreducible polynomials of degree $n$ in $\FF_p[x]$.
\\[.5em]
{\bf b.} $\D_{n}$ is a lattice. What is the usual number-theory interpretation of
the meet $a\vee b$ and the join $a\wedge b$? 
\\[.5em]
[{\it Added}] {\bf c.} Show that $\D_n$ is distributive. Find its join-irreducible elements,
and show that $k = \bigvee j$ where $j$ runs over all join-irreducibles $\leq k$.
%Show that $\P$ is distributive.
%Hint: If $n$ has the prime factorization $p_1^{m_1}\cdots p_k^{m_k}$,
%then $\D_n\cong [m_1{+}1]\times\cdots[m_k{+}1]$.
