TITLE: Two limits involving integrals: $\lim_{\varepsilon\to 0^+}\left(\int_0^{1-\varepsilon}\frac{\ln (1-x)}{x\ln^p x}dx-f_p(\varepsilon)\right)$, $p=1,2$.
QUESTION [7 upvotes]: By applying the Taylor series expansion to $\ln x$, as $x \to 1$, one has the Laurent series expansion,
$$
\frac1{\ln x}=-\frac1{1-x}+\frac{1}{2}+O\left(1-x\right)
$$
then clearly
$$
\begin{align}
&\lim_{\varepsilon \to 0^+} \int_0^{1-\varepsilon} \frac{\ln (1-x)}{x\ln x}\:dx=\infty
\\\\&\lim_{\varepsilon \to 0^+} \int_0^{1-\varepsilon} \frac{\ln (1-x)}{x\ln^2 x}\:dx=-\infty.
\end{align}
$$
Thus I'm designing the following related limits.

Question. Find $f_1(\varepsilon)$, $f_2(\varepsilon)$ and find a closed form of $c_1$, $c_2$ such that
  $$
\begin{align}
&\lim_{\varepsilon \to 0^+} \left(\int_0^{1-\varepsilon} \frac{\ln (1-x)}{x\ln x}\:dx-f_1(\varepsilon)\right)=c_1
 \tag1
\\\\&
\lim_{\varepsilon \to 0^+} \left(\int_0^{1-\varepsilon} \frac{\ln (1-x)}{x\ln^2 x}\:dx-f_2(\varepsilon)\right)=c_2. \tag2
\end{align}
$$

Edit. A complete answer is now given below.

REPLY [3 votes]: Claim. As $\epsilon \to 0$,
  $$ \int_{0}^{1-\epsilon} \frac{\log(1-x)}{x \log^2 x} \, \mathrm{d}x = \frac{1+\log\epsilon}{\epsilon} + \frac{\gamma - 1 - \log(2\pi)}{2} + o(1). $$

Step 1. Applying the substitution $t = -\log x$ followed by integration by parts, we have
$$ \int_{0}^{1-\epsilon} \frac{\log(1-x)}{x (-\log x)^{s+1}} \, \mathrm{d}x = \frac{\eta^{-s}}{s} \log \epsilon + \frac{1}{s} \int_{\eta}^{\infty} \frac{t^{-s}}{\mathrm{e}^t - 1} \, \mathrm{d}t, \tag{1} $$
where $\eta = -\log(1-\epsilon)$. Now we focus on the latter integral, and define
$$ I = I(\eta, s) = \int_{\eta}^{\infty} \frac{t^{-s}}{\mathrm{e}^t - 1} \, \mathrm{d}t. $$
Step 2. Next, we give an explicit formula for $I(\eta, s)$ for small $\eta > 0$. (By small, we mean $\eta \in (0, 2\pi)$.) This is easily done by mimicking the derivation of the functional equation for $\zeta$ by contour integration. To this end, we first restrict ourselves to the case $\Re(s) \in (1, 2)$ and consider the contour
$\hspace{5em}$
Call by $C_{\eta}$ the entire contour and by $\Gamma_{\eta}$ the circular arc. Assuming the branch cut of $\log$ as $[0, \infty)$, this can be computed as
\begin{align*}
&I - \mathrm{e}^{-2\pi i s} I + \int_{\Gamma_{\eta}} \frac{z^{-s}}{\mathrm{e}^z - 1} \, \mathrm{d}z \\
&\hspace{3em} = \int_{C_{\eta}} \frac{z^{-s}}{\mathrm{e}^z - 1} \, \mathrm{d}z
= 2\pi i \sum_{n \in \Bbb{Z}\setminus\{0\}} \underset{z=2\pi i n}{\mathrm{Res}} \; \frac{z^{-s}}{\mathrm{e}^z - 1} \\
&\hspace{6em} = 2i \mathrm{e}^{-i\pi s} (2\pi)^{1-s} \cos\left(\frac{\pi s}{2}\right) \zeta(s).
\end{align*}
This gives
$$ I(\eta, s) = \frac{1}{1 - \mathrm{e}^{-2\pi i s}} \int_{-\Gamma_{\eta}} \frac{z^{-s}}{\mathrm{e}^z - 1} \, \mathrm{d}z + \frac{(2\pi)^{1-s}}{2\sin\left(\frac{\pi s}{2}\right)} \zeta(s) $$
Since both sides define entire functions on all of $\Bbb{C}$, this identity extends to all of $s \in \Bbb{C}$. Now we plug the power series $\frac{z}{\mathrm{e}^z - 1} = \sum_{n=0}^{\infty} \frac{B_n}{n!} z^n$ into the contour integral above to get
\begin{align*}
I(\eta, s)
&= \sum_{n=0}^{\infty} \frac{B_n}{n!} \frac{\eta^{n-s}}{s - n} + \frac{(2\pi)^{1-s}}{2\sin\left(\frac{\pi s}{2}\right)} \zeta(s) \tag{2} \\
&= \sum_{n=0}^{\infty} \frac{B_n}{n!} \frac{\eta^{n-s}}{s - n} + \Gamma(1-s)\zeta(1-s) \tag{3}
\end{align*}
Step 3. Now we consider the case of interest, i.e., $s = 1$. Taking limit as $s \to 1$ to $\text{(2)}$, only the first 2 leading terms of the series are significant (as $\eta \to 0$) and we can easily compute $I(\eta, 1)$ as
$$ I(\eta, 1) = \frac{1}{\eta} + \frac{1}{2} \log \eta + \frac{1}{2}(\gamma - \log(2\pi)) + \mathcal{O}(\eta). $$
Therefore the claim follows by plugging this to $\text{(1)}$ and utilizing the asymptotics
$$ \frac{1+\log \epsilon}{\eta} + \frac{1}{2}\log\eta = \frac{1+\log\epsilon}{\epsilon} - \frac{1}{2} + o(1). $$

Addendum 1. As a by-product, we can compute @Marco Cantarini's integral:
$$ \int_{0}^{1} \frac{\log(1-x)}{x} \left( \frac{1}{\log^{2} x} - \frac{1}{(1-x)^2} + \frac{1}{1-x}\right) \, \mathrm{d}x = \frac{\gamma + 1 - \log(2\pi)}{2}. $$

Addendum 2. Another by-product is that, for $N \in \Bbb{Z}$ and $N-1 < \Re(s) < N$ we have
$$ \int_{0}^{\infty} x^{s-1} \left( \frac{1}{\mathrm{e}^x - 1} - \sum_{n=-\infty}^{-N} a_n x^{n} \right) \, \mathrm{d}x = \Gamma(s)\zeta(s), $$
where $a_n$ are Laurent coefficients of $\frac{1}{\mathrm{e}^x - 1}$ at $x = 0$:
$$ \frac{1}{\mathrm{e}^x - 1} = \sum_{n=-\infty}^{\infty} a_n x^n = \sum_{n=-1}^{\infty} \frac{B_{n+1}}{(n+1)!} x^n. $$


TITLE: Ore extensions of noetherian $k$-algebras are again noetherian (proof explanation)
QUESTION [4 upvotes]: Let $k$ be a field. All occuring $k$-algebras are required to be associative and unital. By noetherian I always mean left noetherian.

In a lecture I’m currently taking the notion of an Ore extension of a $k$-algebra was introduced (the definition used here can be found at the very end of this post). I’m having trouble understanding a crucial step in the proof of the following theorem:

Theorem: Suppose $R[t,\alpha,\delta]$ is an Ore extension of a $k$-algebra $R$. If $R$ is noetherian, then $R[t,\alpha,\delta]$ is also noetherian.
Proof:
  Let $I \trianglelefteq R[t,\alpha,\delta]$ be a left ideal. We show that $I$ is finitely generated.
  For $d \in \mathbb{Z}_{\geq 0}$ let
  $$
 I_d := \left\{a \in R \,\middle|\, \exists P \in I, \deg P = d, P = \sum_{i=0}^d a_i t^i : a_d = a\right\} \cup \{0\}.
$$
  $I_d$ is a left ideal in $R$. If $a$ is the leading coefficient of $P \in I$ then $\alpha(a)$ is the leading coefficient of $t \cdot P$. Hence $\alpha(I_d) \subseteq I_{d+1}$. It follows that
  $$
 I_0 \subseteq \alpha^{-1}(I_1) \subseteq \alpha^{-2}(I_2) \subseteq \dotsb \subseteq \alpha^{-n}(I_n) \subseteq \dotsb
$$
  is an increasing chain of left ideals in $R$. Because $R$ is noetherian this chain stabilizes for some $N$. Then $\color{red}{I_{N+i} = \alpha^i(I_N)}$ for all $i \geq 0$.
  For $0 \leq d \leq N$ choose generators $a_{d,1}, \dotsc, a_{d,\ell(d)}$ of $I_d$ and polynomials $P_{d,j} \in I$ of degree $d$ such that $a_{d,j}$ is the leading coefficient of $P_{d,j}$. Then $\{P_{d,j} \mid 0 \leq d \leq N, 1 \leq j \leq \ell(d)\}$ generates $I$ (details left as an exercise).

I see that this proof is a generalization of the usual proof of Hilbert’s basis theorem, and by using that $I_{N+i} = \alpha^i(I_N)$ for all $i \geq 0$ I’m able to finish the proof. My problem is that I don’t see why $I_{N+i} = \alpha^i(I_N)$ for all $i \geq 0$. It seems to me that we only get that
$$
 \alpha^{-N}(I_N) = \alpha^{-(N+i)}(I_{N+i})
 \quad \text{for all $i \geq 0$}.
$$
As $\alpha$ is not necessarily surjective this is a weaker statement.

I would like to know:

Is it even true that
  $$
 \text{there exists $N \in \mathbb{N}$ with
 $\alpha^i(I_N) = I_{N+i}$ for all $i \geq 0$?}
$$
If it is not true, then does the above statement
  $$
 \alpha^{-N}(I_N) = \alpha^{-(N+i)}(I_{N+i})
 \quad\text{for all $i \geq 0$}
$$
  suffices to prove the theorem?

While it is not the focus of this question I also include a sketch of the rest of the proof, to show how I use that $\alpha^i(I_N) = I_{N+i}$ for all $i \geq 0$.

Rest of the proof (Sketch):
  Let $J := \langle P_{d,j} \mid 0 \leq d \leq N, 1 \leq j \leq \ell(d) \rangle \subseteq I$. It is easy to see that $P \in J$ for every $P \in I$ with $\deg P \leq N$.
  Suppose that $P = \sum_{i=0}^d a_i t^i \in I$ with $P \notin J$, and that $P$ is of smallest degree with this property. Then $d > N$, so $\color{green}{I_d = \alpha^i(I_N)}$ for $i = d-N > 0$.
  Because $a_d \in I_d$ there exists some $a \in I_N$ with $a_d = \alpha^i(a)$. Let $r_1, \dotsc, r_n \in R$ with
  $$
 a = \sum_{j=1}^{\ell(N)} r_j a_{N,j}
$$
  and set
  $$
 Q := \sum_{j=1}^{\ell(N)} r_j P_{N,j}
$$
  So $Q \in J$ is of degree $N$ and has $a$ as its leading coefficient. By induction it follows that $t^m Q \in J$ is of degree $N+m$ with leading coefficient $\alpha^m(a)$ for all $m \geq 0$.
  In particular $t^i Q \in J$ is of degree $d$ and has leading coefficient $\alpha^i(a) = a_d$. As $P \notin J$ it follows that $P - t^i Q \notin J$. Because $P - t^i Q \in I$ with $\deg(P - t^i Q) < d = \deg(P)$ this contradicts the choice of $P$.

The used definition of an Ore extension:

Proposition/Definition: Suppose that $R$ is a $k$-algebra without zero divisors, $\alpha \colon R \to R$ is an injective $k$-algebra morphism and $\delta \colon R \to R$ is an $\alpha$-derivation, i.e. $\delta$ is $k$-linear with
  $$
 \delta(ab) = \alpha(a)\delta(b) + \delta(a)b
 \quad \text{for all $a,b \in R$}.
$$
  Then there exists a unique $k$-algebra structure on $R[t] = \bigoplus_{i \geq 0} R t^i$ such that

the inclusion $R \hookrightarrow R[t]$, $r \mapsto r t^0$ is a morphism of $k$-algebras,
$\deg(PQ) = \deg(P) + \deg(Q)$ for all $P,Q \in R[t]$,
$t \cdot a = \alpha(a) \cdot t + \delta(a)$ for every $a \in R$.

This $k$-algebra is called an Ore extension of $R$ and denoted by $R[t,\alpha,\delta]$.

(I actually put a few statements and definitions from the lecture together, so in this form there might be some redundancy.)

REPLY [3 votes]: Indeed, the conclusion $\alpha^{i}(I_N)=I_{N+i}$ does not follow.
In fact, the claim of the theorem is incorrect in this generality.
The theorem is true if $\alpha$ is an automorphism, and then the questionable implication also becomes true.
To see that it is not necessarily true if $\alpha$ is not surjective, consider the following example.
Let $R=k[x]$ be a polynomial ring over a field, and let $\alpha$ be the injective endomorphism defined by $\alpha(x)=x^2$.
Thus $\alpha(f(x)) = f(x^2)$ for all $f \in R$.
Claim: $S=R[t;\alpha]$ is not left Noetherian.
Proof: For $n\ge 0$, let $J_n$ be the left ideal of $S$ generated by $x$, $xt$, $\ldots\,$, $xt^n$.
Then of course $J_n \subset J_{n+1}$.
Moreover, $J_n \subsetneq J_{n+1}$ since $xt^{n+1} \notin J_n$, as $x \notin \alpha(R)$.
To see where exactly the proof in your question goes wrong, consider the left ideal $I= \bigcup_{n \ge 0} J_n$.
Denoting, as in your question, the ideal of leading coefficients of $I$ of degree $n$ by $I_n \subset R$, we have simply $I_n=(x)$.
However $\alpha^i(I_n) = \{p(x^{2^i}) \mid p \in k[x], p(0)=0 \} \subsetneq (x)$ for $i \ge 1$.
As a final remark, the ring $S$ is in fact also not right Noetherian.


TITLE: Why do peaks and troughs of a wave cancel each other out? And why peaks and peaks or troughs and troughs add up?
QUESTION [1 upvotes]: I have thought that the cancellation of peaks and troughs is a consequence of Newton's third law of motion that equal and opposite forces cancel each other out.
Or it has something to do with conservation of energy or momentum.But I have never truly understood it correctly.
I believe there is an obvious and clear explanation that I am simply not aware of.
In other words, how does interference work?

REPLY [1 votes]: Mathematically it can be seen as a consequence of waves obeying a linear second order differential equation.
Physically, for mechanical waves, it’s the fact that forces are additive that result in the addition (superposition) of waves. This means that if two forces are acting at a point, then the net force that acts is the resultant force.
Similarly for EM waves, the fields themselves are additive in nature and the net outcome is the resultant of all the fields at that point.


TITLE: Boundary of boundary of singular cube is zero (Spivak)
QUESTION [7 upvotes]: At the bottom of page 99 of M. Spivak's Calculus on Manifolds he arrives at the formula
$$\partial (\partial c)=\sum_{i=1}^n \sum_{\alpha=0,1} \sum_{j=1}^{n-1} \sum_{\beta=0,1} (-1)^{i+\alpha+j+\beta} (c_{(i,\alpha)})_{(j,\beta)} $$
Here $c$ is a singular $n$-cube in $A \subseteq \mathbb{R}^n$; that is, a continuous function $[0,1]^n \to A$, and $$c_{(i,\alpha)}=c \circ (I^n_{(i,\alpha)}),$$ where $I^n(i,\alpha)$ is the identity function on $[0,1]^n$ applied to $x \in [0,1]^n$ with its i'th coordinate replaced by $\alpha \in \{0,1\}$.
The author then claims:

In this sum $(c_{(i,\alpha)})_{(j,\beta)}$ and $(c_{(j+1,\beta)})_{(i,\alpha)}$ occur with opposite signs. Therefore all terms cancel out in pairs and $\partial (\partial c) = 0$.

I can't see how to pair up the terms exactly: If $i=n$ for example, the term $(c_{(n,\alpha)})_{(j,\beta)}$ seems to be paired with $(c_{(j+1,\beta)})_{(n,\alpha)}$. But doesn't that third subscript take values only in $\{1,2,\dots,n-1\}$?
Can you please help me understand this?
Thank you!

REPLY [5 votes]: Let's try a small value of $n$ first to see how it works. The first nontrivial case is $n=2$, so take $c : [0,1]^2 \to A$ a singular $2$-cube. Its boundary is
$$\partial c = \sum_{i=1}^2 \sum_{\alpha \in \{0,1\}} (-1)^{i+\alpha} c_{(i,\alpha)} = -c_{(1,0)} + c_{(1,1)} + c_{(2,0)} - c_{(2,1)}.$$
If $u : [0,1] \to A$ is a singular $1$-cube, its boundary is:
$$\partial u = -u_{(1,0)} + u_{(1,1)} = -u(0) + u(1)$$
And so we get that:
$$\begin{align}
\partial^2(c) & = - \bigl(-(c_{(1,0)})_{(1,0)} + (c_{(1,0)})_{(1,1)}\bigr) + \bigl(-(c_{(1,1)})_{(1,0)} + (c_{(1,1)})_{(1,1)}\bigr) \\
& \mathrel{\hphantom{=}} + \bigl(-(c_{(2,0)})_{(1,0)} + (c_{(2,0)})_{(1,1)}\bigr) - \bigl(-(c_{(2,1)})_{(1,0)} + (c_{(2,1)})_{(1,1)}\bigr)
\end{align}$$
Now how can we pair this?

The terms of the form $(c_{(2,0)})_{(1,i)}$ are those that look like $c(i,0)$, and so will be paired with the terms of the form $(c_{(1,i)})_{(1,0)}$. But the sign of $(c_{(2,0)})_{(1,i)}$ is $(-1)^{2+0+1+i} = -(-1)^i$, while the sign of $(c_{(1,i)})_{(1,0)}$ is $(-1)^{1+i+1+0} = (-1)^i$, so they are opposite and cancel.
Similarly, the terms of the form $(c_{(2,1)})_{(1,i)}$ are paired with those of the form $(c_{(1,i)})_{(1,1)}$, and the signs cancel again.

So hopefully we now see how it works. What happened above is that in $(c_{(i,\alpha)})_{(j,\beta)}$, if $i > j$, then we first "fix" the $i$th coordinate in $c(t_1, \dots, t_n)$ and then the $j$th; but if $i \le j$, when we fix the the $i$th coordinate to get $c_{(i,\alpha)}$, the new "$j$th" coordinate in $(c_{(i,\alpha)})_{(j,\beta)}$ is really the $(j+1)$st coordinate of $c$! Let's try to formalize that.
We have the set of indices:
$$J_n = \{(i,\alpha,j,\beta) | 1 \le i \le n, \alpha \in \{0,1\}, 1 \le j \le n-1, \beta \in \{0,1\} \},$$
and $\partial^2(c) = \sum_{(i,\alpha,j,\beta) \in J_n} (-1)^{i+\alpha+j+\beta} (c_{(i,\alpha)})_{(j,\beta)}$. We separate $J_n$ in two parts: the set $J_n''$ of indices $(i,\alpha,j,\beta)$ such that $i > j$, and the set $J_n'$ such that $i \le j$. Then there is a bijection between $J_n''$ and $J_n'$ given by:
$$\begin{align}
\theta : J_n' & \to J_n'' \\
(i,\alpha,j,\beta) & \mapsto (j+1,\beta,i,\alpha)
\end{align}$$
Of course, the bijection isn't chosen at random. If $(i,\alpha,j,\beta) \in J_n'$, ie $i \le j$, then:
$$(c_{(i,\alpha)})_{(j,\beta)}(t_1, \dots, t_{n-2}) = c(t_1, \dots, \underbrace{\alpha}_{i\text{th position}}, \dots, \underbrace{\beta}_{(j+1)\text{st position}}, \dots, t_{n-2}),$$
and you see that it is equal to $(c_{(j+1,\beta)})_{(i,\alpha)}$. (At this point I should advise you to check what I've written, if you're not comfortable with all this. Try to see how it works for $n=2$ above, and maybe try $n=3$ if you're courageous. No amount of explanation can replace writing it out for yourself.)
But the signs in front of each are different because of the $+1$ in $j+1$, and so when you pair $(i,\alpha,j,\beta)$ with $\theta(i,\alpha,j,\beta)$ they cancel each other and in the end the sum is zero.

PS: If you're interested in this, this is essentially the combination of the proof that the singular cubes of a space form a (semi-)simplicial abelian group (I didn't mention degeneracies), and that the differential of the Moore complex of a simplicial abelian group has square zero.


TITLE: Pinball on the infinite plane
QUESTION [25 upvotes]: Imagine pinball on the infinite plane, with every lattice
point $\mathbb{Z}^2$ a point pin.
The ball has radius $r < \frac{1}{2}$.
It starts just touching the origin pin, and shoots off at angle $\theta$
w.r.t. the horizontal.
It reflects from pins in the natural manner:

What happens?
More specifically,

Q.
  For a given $r$, what is the measure of the set of angles $\theta$
  for which the pinball remains a finite distance from the origin
  forever?

Many other questions suggest themselves, but let me leave it at that basic question for now.
This problem seems superficially similar to
Polya's Orchard problem (e.g., explored in the MO
question,
"Efficient visibility blocker
s in Polya’s orchard problem"),
but the reflections produce complex interactions.
It is also similar to Pach's enchanted forest problem, mentioned
in the MO question,
"Trapped rays bouncing between two convex bodies",
but it seems simpler than that unsolved problem, due to the lattice regularity.
Has it been considered before, in some guise?
If so, pointers would be appreciated.  Thanks!
Addendum.
My question can be rephrased in terms of the "Sinai billiard,"
as Anthony Quas explains: I am asking for the fate of radial rays in the situation illustrated:

REPLY [5 votes]: This is an infinite horizon Lorentz gas.  Ergodicity in the extended space has been shown for this model, but comparatively recently: D. Szasz and T. Varju, J. Stat. Phys. 129 59-80 (2007).  But as noted already the set of initial conditions has zero measure, so this is not sufficient in itself.  The initial conditions are a smooth one dimensional set in the full two dimensional collision space, so one would expect that if the set of orbits in the collision space with a bound $r$ has dimension $d(r)>1$, the desired set will have dimension
$d(r)-1$, approaching unity as $r\to\infty$.


TITLE: Showing existence of a point such that $f'(x) = f(x)$ according to given condition
QUESTION [2 upvotes]: Let $f:[a, b] \rightarrow R$ be continuous in [a,b], differentiable in $(a, b)$ and $f(a)=0=f(b)$. Then
(A) there exists at least one point $c \in(a, b)$ for which $f^{\prime}(c)=f(c)$
(B) $f^{\prime}(x)=f(x)$ does not hold at any point of $(a, b)$
(C) at every point of $(a, b), \mathrm{f}^{\prime}(x)>\mathrm{f}(x)$
(D) at every point of $(a, b), f^{\prime}(x)<f(x)$.

Approach : Considering $F(x) = f'(x)-f(x)$ we can observe $F(a) = f'(a) , F(b) =f'(b)$ . Also from Rolles theorem we have a point (z) in $f'(x)$ graph in $(a,b)$ such that $f'(z) = 0$ , so we can draw few conclusions like if we consider f'(x) to be >0 for all (a,b) thats not possible because it needs to attain a value 0 too , so . So it can be three cases possible $f'(x)>=0$ , $<=0$  for all $(a,b)$ z is point of local minima of $f(x)$ in this case,  $f'(x) >0$ for $(a,z)$ and $<=0 for [z,b)$ , or $f'(x) <0 for (a,z) ,f'(x)>=0 for [z,b)$ ,
but from these all cases i am not able to conclude any behavior for F(x) so
as to get
f'(x) = f(x) for atleast one point because the last two cases gives the one root of $F(x)$ (in a,b)  but the first case doesnt give it ?

REPLY [1 votes]: Look at the function $g(x) = f(x)e^{-x}$. Then $g(a) = g(b) = 0$, so by Rolle's theorem there is a point $c \in (a,b)$ satisfying $g'(c) = 0$. But
$g'(x) = f'(x) e^{-x} - f(x) e^{-x}$ so that $(f'(c) - f(c))e^{-c} = 0$.


TITLE: Find $f:\mathbb R\to\mathbb R$ such that $f(x)=f'(x)$.
QUESTION [6 upvotes]: Find $f:\mathbb R\to\mathbb R$ such that $f(x)=f'(x)$.

I know that $f(x)$ can be $e^x$, but how to solve this mathematically? Are there any other solutions? Thank you.

REPLY [3 votes]: Simple elementary differential equation. Put $\,y=f(x)\,$ , then::
$$f'(x)=f(x)\iff \frac{dy}{dx}=y\implies \int\frac{dy}{y}=\int dx\implies$$
$$\implies \log y=x+c\implies y=e^{x+c}=Ke^x\;,\;\;K:=e^c=\text{ a constant}$$


text:
\begin{document}

\maketitle

\begin{abstract}
In arXiv:1709.07504 Aguiar and Ardila give a Hopf monoid structure on hypergraphs as well as a general construction of polynomial invariants on Hopf monoids. Using these results, we define in this paper a new polynomial invariant on hypergraphs. We give a combinatorial interpretation of this invariant on negative integers which leads to a reciprocity theorem on hypergraphs. Finally, we use this invariant to recover well-known invariants on other combinatorial objects (graphs, simplicial complexes, building sets, etc) as well as the associated reciprocity theorems.
\end{abstract}

\section{Introduction}

In combinatorics, Hopf structures give an algebraic framework to deal with operations of merging (product) and splitting (co-product) combinatorial objects. The notion of Hopf algebra is well known and used in combinatorics for over 30 years, and has proved its great strength in answering various questions (see for example \cite{HAC}). More recently, Aguiar and Mahajan defined a notion of Hopf monoid \cite{am2},\cite{am} akin to the notion of Hopf algebra and built on Joyal’s theory of species \cite{joy}.

Such as in the case of Hopf algebras, a useful application of Hopf monoids is to define and compute polynomial invariants (see \cite{ABS}, \cite{BB}, \cite{DKT} or \cite{KMT} for various examples), as was put to light by the recent and extensive paper of Aguiar and Ardila \cite{AA}. In particular they give a theorem to generate various polynomial invariants and use it to recover the chromatic polynomial of graphs, the Billera-Jia-Reiner polynomial of matroids and the strict order polynomial of posets. Furthermore they also give a way to compute these polynomial invariants on negative integers hence also recovering the different reciprocity theorems associated to these combinatorial objects.

In this paper, we apply Aguiar and Ardila's theorem to the Hopf monoid of hypergraphs defined in \cite{AA}. This Hopf structure is different than the one defined and studied  in \cite{HypB} (the respective co-products are different).

We obtain a combinatorial description for the (basic) invariant $\chi_I(H)(n)$ in terms of colorings of hypergraphs (Theorem \ref{chi}). We then use another approach (rather technical) than the method of \cite{AA} to get a reciprocity theorem for hypergraphs (Theorem \ref{chi-n}).
Finally, we use these results to obtain polynomial invariants on sub-monoids of the Hopf monoid of hypergraphs.

This paper is an extended version of the extended abstract for FPSAC 2019 \cite{fpsac}.

\section{Definitions and reminders}
\subsection{Hopf monoids}

We recall here basic definitions on Hopf monoids. The interested reader may refer to \cite{am} and to \cite{AA} for more information on this topic. In this paper, $\Bbbk$ is a field and all vector spaces are over $\Bbbk$.

\begin{definition}
A \textit{vector species} $P$ consists of the following data:
\begin{itemize}
\item for each finite set $I$, a vector space $P[I]$,
\item for each bijection of finite sets $\sigma: I\rightarrow J$, a linear map $P[\sigma]:P[I]\rightarrow P[J]$. These maps should be such that $P[\sigma\circ\tau] = P[\sigma]\circ P[\tau]$ and $P[\id] = \id$.
\end{itemize}

A \textit{sub-species} of a vector species $P$ is a vector species $Q$ such that for each finite set $I$, $Q[I]$ is a sub-space of $P[I]$ and for each bijection of finite sets $\sigma: I\rightarrow J$, $Q[\sigma] = P[\sigma]_{|Q[I]}$.

For $P$ and $Q$ two vector species, a \textit{morphism} $f: P\rightarrow Q$ between $P$ and $Q$ is a collection of linear maps $f_I : P[I] \rightarrow Q[I]$ satisfying the naturality axiom: for each bijection $\sigma: I\rightarrow J$, $f_J\circ P[\sigma] = Q[\sigma]\circ f_I$.
\end{definition}

\begin{definition}
A \textit{connected Hopf monoid in vector species} is a vector species $M$ with $M[\emptyset] = \Bbbk$ that is equipped with product and co-product linear maps
\begin{displaymath}
\mu_{S,T}: M[S]\otimes M[T] \rightarrow M[S\sqcup T], \qquad \Delta_{S,T}: M[S\sqcup T] \rightarrow M[S]\otimes M[T],
\end{displaymath}
with $S$ and $T$ disjoint sets, and subject to the following axioms.
\begin{itemize}
\item \textit{Naturality}. For each pair of disjoint sets $S$, $T$, each bijection $\sigma$ with domain $S\sqcup T$, we have $M[\sigma]\circ\mu_{S,T} = \mu_{\sigma(S),\sigma(T)}\circ M[\sigma_{|S}]\otimes M[\sigma_{|T}]$ and $M[\sigma_{|S}]\otimes M[\sigma_{|T}]\circ\Delta_{S,T} = \Delta_{\sigma(S),\sigma(T)}\circ M[\sigma]$.
\item \textit{Unitality}. For each set $I$, $\mu_{I,\emptyset}$, $\mu_{\emptyset,I}$, $\Delta_{I,\emptyset}$ and $\Delta_{\emptyset,I}$ are given by the canonical isomorphisms $M[I]\otimes\Bbbk\cong\Bbbk\cong\Bbbk\otimes M[I]$.
\item \textit{Associativity}. For each triplet of pairwise disjoint sets $R$,$S$, $T$, we have: $\mu_{R,S\sqcup T}\circ\id\otimes\mu_{S,T} = \mu_{R\sqcup S, T}\circ \mu_{R,S}\otimes\id$.
\item \textit{Co-associativity}. For each triplet of pairwise disjoint sets $R$,$S$, $T$, we have: $\Delta_{R,S}\otimes\id\circ\Delta_{R\sqcup S, T} = \id\otimes\Delta_{S,T}\circ\Delta_{R,S\sqcup T}$.
\item \textit{Compatibility}. For each pair of disjoint sets $A$, $B$, each pair of disjoint sets $C$, $D$ ,we have the following commutative diagram, where $\tau$ maps $x\otimes y$ to $y\otimes x$:
\begin{center}
\begin{tikzcd}
\\
P[S]\otimes P[T] \arrow[d, "\Delta_{A,B}\otimes\Delta_{C,D}" swap] \arrow[r, "\mu_{S,T}"] & P[I] \arrow[r, "\Delta_{S',T'}"] & P[S']\otimes P[T']  \\
P[A]\otimes P[B]\otimes P[C]\otimes P[D] \arrow[rr, "\id\otimes\tau\otimes\id" swap] & & P[A]\otimes P[C]\otimes P[B]\otimes P[D] \arrow[u, "\mu_{A,C}\otimes\mu_{B,D}" swap]
\\
\end{tikzcd}
\end{center}
\end{itemize}

A \textit{sub-monoid} of a Hopf monoid $M$ is a sub-species of $M$ stable under the product and co-product maps.

The \textit{co-opposite} Hopf monoid $M^{cop}$ of $M$ is the Hopf monoid with opposite co-product: $\Delta^{M^{cop}}_{S,T}=\Delta^{M}_{T,S}$.

A \textit{morphism of Hopf monoids} in vector species is a morphism of vector species which preserves the products, co-products (compatibility axiom) and the unity (unitality axiom).
\end{definition}

\begin{remark}
Readers more familiar with Hopf algebras can see connected Hopf monoids in vector species as a way to refine the coproduct of connected graded Hopf algebras. In fact there exists a functor $F$ called the \textit{Fock functor} from the category of Hopf monoids into the category of graded Hopf algebras. This functor is such that for a Hopf monoid $M$, the elements of size $n$ of $F(M)$ are the elements of $M[[n]]$ quotiented by the action of the symmetric group: $F(M)_n = M[[n]]_{S_n}$. The coproduct on $F(M)_n$ is then of the form $\Delta_n = f\circ\sum_{S\sqcup T = [n]}\Delta_{S,T}\circ i$ with $i$ and $f$ well chosen maps.
\end{remark}

We will use the term Hopf monoid for connected Hopf monoid in vector species. A sub-monoid of a Hopf monoid $M$ is itself a Hopf monoid when equipped with the product and co-product maps of $M$. We consider this to always be the case.

A \textit{decomposition} of a finite set $I$ is a sequence of pairwise disjoint subsets $S=(S_1,\dots,S_l)$ such that $I=\sqcup_{i=1}^lS_i$. A \textit{composition} of a finite set $I$ is a decomposition of $I$ without empty parts. We will write $S \vdash I$ for $S$ a decomposition of $I$, $S\vDash I$ if $S$ is a composition, $l(S) = l$ the \textit{length} of a decomposition and $|S| = |I|$ the number of elements in the decomposition.

\begin{definition}
Let $M$ a be a Hopf monoid. The \textit{antipode} of $M$ is the collection of maps $\text{S}_I : M[I]\rightarrow M[I]$ given by $\text{S}_{\emptyset} = \id$ and $$ \text{S}_I = \sum_{\substack{(S_1,\dots S_k)\vDash I\\ k\geq 1}}(-1)^{k} \mu_{S_1,\dots,S_k}\circ\Delta_{S_1,\dots S_k},$$ for any non empty finite set $I$.
\end{definition}

This expression of the antipode is known as \textit{Takeuchi's formula}.

\begin{definition}
A \textit{character} on a Hopf monoid $M$ is a collection of linear maps $\zeta_I:M[I]\rightarrow \Bbbk$ subject to the following axioms.
\begin{itemize}
\item \textit{Naturality}. For each bijection $\sigma: I\rightarrow J$, we have $\zeta_J\circ M[\sigma] = \zeta_I$.
\item \textit{Multiplicativity}. For each disjoint sets $S$, $T$, we have $\zeta_{S\sqcup T}\circ\mu_{S,T} = \mu_{\Bbbk}\circ\zeta_S\otimes\zeta_T$.
\item \textit{Unitality}. $\zeta_{\emptyset}(1) = 1$.
\end{itemize}
\end{definition}

Let us recall from \cite{AA} the results which we will use in the sequel.

\begin{definition}
\label{definv}
Let $M$ be a Hopf monoid and $\zeta$ a character on $M$. For $x\in M[I]$ and $n$ an integer, we define:
\begin{displaymath}
\chi_I(x)(n)= \sum_{(S_1, \dots S_n) \vdash I} \zeta_{S_1}\otimes\dots\otimes\zeta_{S_n}\circ\Delta_{S_1,\dots S_n}(x).
\end{displaymath}
\end{definition}

\begin{theorem}[Proposition 16.1 and Proposition 16.2 in \cite{AA}]
\label{inv}
Let $M$ be a Hopf monoid and $\zeta$ a character on $M$ and let $\chi$ be the collection of maps of Definition \ref{definv}. Then $\chi_I(x)$ is a polynomial invariant in $n$ such that:
\begin{enumerate}
\item $\chi_I(x)(1) = \zeta(x)$,
\item $\chi_{\emptyset} = 1$ and $\chi_{S\sqcup T}(\mu(x\otimes y)) = \chi_S(x)\chi_T(y)$,
\item $\chi_I(x)(-n) = \chi_I(\text{S}_I(x))(n)$.
\end{enumerate}
\end{theorem}

Let $M$ be a Hopf monoid. For $I$ a set and $x\in M[I]$ we call $x$ \textit{discrete} if $I=\{i_1,\dots, i_{|I|}\}$ and $x=\mu_{\{i_1\},\dots,\{i_{|I|}\}}x_1\otimes\dots\otimes x_{|I|}$ for $x_j\in M[\{i_j\}]$. Then the maps that send discrete elements onto 1 and other elements onto 0 give us a Hopf monoid character. Following the terminology introduced in Section 17 of \cite{AA}, we call the \textit{basic invariant of $M$} the polynomial invariant of Definition \ref{definv} with this character. We denote $\chi^M$ this polynomial or just $\chi$ when this is clear from the context.

\begin{example}
As shown in Subsection \ref{graphs}, there exists a Hopf monoid structure on graphs whose basic invariant is the chromatic polynomial.
\end{example}

\begin{proposition}[Proposition 16.3 in \cite{AA}]
\label{invmorph}
Let $M$ and $N$ be two Hopf monoids, $\zeta^M$ and $\zeta^N$ characters on $M$ and $N$ and $f: M\rightarrow N$ a Hopf monoid morphism such that for every $I$: $$\zeta^N_I\circ f_I = \zeta^M_I.$$ Denote by $\chi(\zeta^M)$ and $\chi(\zeta^N)$ the polynomial invariants of Definition \ref{definv} with $M$ and $\zeta^M$ and $N$ and $\zeta^N$. For every $I$, one then has: $$ \chi(\zeta^N)_I\circ f_I = \chi(\zeta^M)_I.$$
\end{proposition}

In particular, since Hopf monoid morphisms conserve discrete elements, for $f: M\rightarrow N$ a Hopf monoid morphism and $I$ a set, we have $\chi^N_I\circ f_I = \chi^M_I$.

\subsection{A useful combinatorial identity}

We recall here a classical result of combinatorics and a direct corollary which will be useful in the following section. We only give a sketch of the proofs.

In all the following, given an integer $n$ we will denote by $[n]$ the set $\{1,\dots, n\}$.

\begin{proposition}
Let $n$ and $m$ be two integers. The number of surjections $S_{n,m}$ from $[m]$ to $[n]$ is given by: $$S_{n,m} = \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^m.$$
\end{proposition}

\begin{proof}
This formula can be obtained by the inclusion-exclusion principle.
\end{proof}

\begin{corollary}
\label{idcombi}
For $n$ and $m$ two integers such that $m<n$, and $P$ a polynomial of degree at most $m$, we have: $$\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}P(k) = 0.$$
\end{corollary}

\begin{proof}
The statement above is a direct consequence of the fact that $S_{n,m} = 0$ for $n<m$.
\end{proof}

\section{Basic invariant of hypergraphs}

In all of the following, $I$ always denotes a finite set.

Our goal is to express the basic invariant of the Hopf monoid of hypergraphs defined in Section 20 of \cite{AA}. More specifically we intend to obtain a combinatorial interpretation of $\chi_I(x)(n)$ and $\chi_I(x)(-n)$.

In this context, a \textit{hypergraph over $I$} is a collection of (possibly repeated) subsets of $I$, which we call \textit{edges}\footnote{in some references, the terms \textit{hyperedge} or \textit{multiedge} is used.}. The elements of $I$ are then called \textit{vertices} of $H$ and $HG[I]$ denotes the free vector space of hypergraphs over $I$. Note that two hypergraphs over different sets can never be equal, e.g $\{\{1,2,3\},\{2,3,4\}\}\in HG[[4]]$ is not the same as $\{\{1,2,3\},\{2,3,4\}\}\in HG[[4]\cup\{a,b\}]$. This is illustrated in Figure \ref{same-edges}.

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=1.5]{fig/hg1}
\hspace{5cm}
\includegraphics[scale=1.5]{fig/hg2}
\caption{Two hypergraphs with the same edges but over different sets.}
\label{same-edges}
\end{center}
\end{figure}

The product and co-product for $I=S\sqcup T$ are given by,
\begin{align*}
\mu_{S,T}: HG[S]\otimes HG[T] &\rightarrow HG[I] & \Delta_{S,T}: HG[I] &\rightarrow HG[S]\otimes HG[T] \\
H_1\otimes H_2 &\mapsto H_1\sqcup H_2 & H &\mapsto H_{|S}\otimes H_{/S}
\end{align*}
where $H_{|S} = \{e\in H\, |\, e\subseteq S\}$ is the \textit{restriction of $H$ to $S$} and $H_{/S} = \{e\cap T\, |\, e \nsubseteq S\}$ is the \textit{contraction of $S$ from $H$}. The discrete hypergraphs are then the hypergraphs with edges of cardinality at most 1.

\begin{example}
For $I=[5]$, $S=\{1,2,5\}$ and $T=\{3,4\}$, we have:
\begin{center}
\begin{tikzcd}[column sep=huge]
\raisebox{-21pt}{\includegraphics[scale=1.5]{fig/hg3}} \arrow[r, "\Delta_{S,T}"] & \raisebox{-10pt}{\includegraphics[scale=1.5]{fig/hg4}}\hspace{0.2cm} \otimes \hspace{0.2cm}\raisebox{-10pt}{\includegraphics[scale=1.5]{fig/hg5}}
\end{tikzcd}
\end{center}
\end{example}

In \cite{AA}, Aguiar and Ardila propose a method to obtain a combinatorial interpretation of any polynomial invariant given in Definition \ref{definv} on negative integers, assuming that we have an interpretation of it on positive integers. Their method consists in using a cancellation-free grouping-free formula for the antipode and point 3 of Theorem \ref{inv}.

Here we use a different approach: we express the polynomial dependency of $\chi_I(x)(n)$ in $n$, which we then use to calculate $\chi_I(x)(-n)$ and interpret the resulting formula.

Let us begin by giving a proposition which is needed to show the polynomial dependency of $\chi_I(x)(n)$ in $n$.
For $t\in\mathbb{N}^*$ and a sequence of positive integers $p_1, p_2,\dots, p_t$, we define $F_{p_1,\dots, p_t}$ as a function over the integers given by, for $n\in\mathbb{N}$:$$F_{p_1,\dots, p_t}(n) = \sum_{0\leq k_1 <\dots < k_t\leq n-1} k_1^{p_1}\cdots k_t^{p_t}.$$
Note that if $t>n$, then $F_{p_1,\dots, p_t}(n) = \sum_{\emptyset}\dots=0$.

\begin{proposition}
Let $p_1, p_2,\dots, p_t$ be integers and define $d_k = \sum_{i=1}^k p_i + k$ for $1\leq k \leq t$. Then $F_{p_1,\dots, p_t}$ is a polynomial of degree $d_t$ whose constant coefficient is null and the $(d_t - i)$-th, (for $i < d_t$) coefficient is given by
\begin{displaymath}
\sum_{j_{t-1} = 0}^{\min(j_t, d_{t-1}-1)}\sum_{j_{t-2}}^{\min(j_{t-1}, d_{t-2}-1)}\dots\sum_{j_1 = 0}^{\min(j_2,d_1 - 1)}\prod_{k=1}^t \binom{d_k - j_{k-1}}{j_k - j_{k-1}}\frac{B_{j_k - j_{k-1}}}{d_k - j_{k-1}},
\end{displaymath}
where $j_t = i$ and $j_0 = 0$, and the $B_j$ numbers are the Bernoulli numbers with the convention $B_1 = -1/2$.
\end{proposition}

\begin{proof}
We show this by induction on $t$. For $t=1$ the expression of the coefficients gives us the well-known identity $F_p(n) = \sum_{i=0}^p \binom{p+1}{i}\frac{B_i}{p+1}n^{p+1-i}$. Hence the result is true for $t=1$. Suppose now the result is true for $t\geq 1$ and let $p_1, p_2,\dots, p_{t+1}$ be $t+1$ integers. Denote by $a_i$ the $d_t -i$ coefficient of $F_{p_1,\dots, p_t}(n)$. We then have:
\begin{align*}
F_{p_1,\dots, p_{t+1}}(n) &= \sum_{0\leq k_1 <\dots < k_{t+1}\leq n-1} k_1^{p_1}\cdots k_{t+1}^{p_{t+1}} = \sum_{k_{t+1}=0}^{n-1}k_{t+1}^{p_{t+1}}\sum_{0\leq k_1 <\dots < k_t\leq k_{t+1}-1}  k_1^{p_1}\cdots k_t^{p_t}\\
&= \sum_{k = 0}^{n-1} k^{p_{t+1}}F_{p_1,\dots, p_t}(k) \\
&= \sum_{k = 0}^{n-1} k^{p_{t+1}}\sum_{j = 0}^{d_t -1} a_j k^{d_t-j} \\
&= \sum_{j = 0}^{d_t - 1} a_j\sum_{k = 0}^{n-1} k^{p_{t+1} + d_t -j} = \sum_{j = 0}^{d_t - 1} a_j\sum_{k = 0}^{n-1} k^{d_{t+1} -1 - j} \\
&= \sum_{j = 0}^{d_t - 1} a_j F_{d_{t+1} - 1 - j}(n) \\
&= \sum_{j = 0}^{d_t - 1} a_j\sum_{i = 0}^{d_{t+1}-1-j}\binom{d_{t+1}-j}{i}\frac{B_i}{d_{t+1} - j} n^{d_{t+1} - j -i} \\
&= \sum_{j = 0}^{d_t - 1}\sum_{i = 0}^{d_{t+1}-1-j} a_j\binom{d_{t+1}-j}{i}\frac{B_i}{d_{t+1} - j} n^{d_{t+1} - j -i} \\
&= \sum_{j = 0}^{d_t - 1}\sum_{i = j}^{d_{t+1}-1} a_j\binom{d_{t+1}-j}{i-j}\frac{B_{i-j}}{d_{t+1} - j} n^{d_{t+1} - i} \\
&= \sum_{i = 0}^{d_{t+1} - 1}\left(\sum_{j = 0}^{\min(i,d_t - 1)} a_j\binom{d_{t+1}-j}{i-j}\frac{B_{i-j}}{d_{t+1}-j}\right) n^{d_{t+1} - i}.
\end{align*}
This concludes this proof.
\end{proof}

Before stating our results on $\chi_I(H)(n)$ we need to introduce some definitions. There exists a canonical bijection between decompositions and functions with co-domain of the form $[n]$. In the sequel, we will want to seamlessly pass from one notion to the other. We hence give a few explanations on this bijection. Given an integer $n$, the canonical bijection between decompositions of $I$ of size $n$ and functions from $I$ to $[n]$ is given by:
\begin{align*}
b_{I,n}: \{f:I\rightarrow [n]\} &\rightarrow \{P\vdash I\,|\, l(P)=n\} \\
f &\mapsto (f^{-1}(1),\dots,f^{-1}(n)).
\end{align*}
If it is clear from the context what are $I$ and $n$, we will write $b$ instead of $b_{I,n}$. If $P$ is a partition we will also refer to $b^{-1}(P)$ by $P$ so that instead of writing ``i such that $v\in P_i$'' and ``i and j such that $v\in P_i$, $v'\in P_j$ and $i<j$ '' we can just write $P(v)$ and $P(v)<P(v')$. Similarly, if $P$ is a function we will refer to $b(P)$ by $P$ so that $P_i = P^{-1}(i)$. Also remark that $b_{I,n}$ induces a bijection between compositions of $I$ of size $n$ and surjections from $I$ to $[n]$.

\begin{definition}
Let $H$ be a hypergraph over $I$ and $n$ be an integer. A \textit{coloring of $H$ with $[n]$} is a function from $I$ to $[n]$ (or a decomposition of $I$ of length $n$ from what precedes this) and in this context the elements of $[n]$ are called \textit{colors}.

Let $S\vdash I$ be a coloring of $H$. For $v\in e\in H$, we say that $v$ is a \textit{maximal vertex of $e$ (for $S$)} if $v$ is of maximal color in $e$ and we call the \textit{maximal color of $e$ (for $S$)} the color of a maximal vertex of $e$. We say that a vertex $v$ is a \textit{maximal vertex (for $S$)} if it is a maximal vertex of an edge.

If $J\subseteq I$ is a subset of vertices, the \textit{order of appearance of $J$ (for $S$)} is the composition $\cano(S_{|J})$ where $S_{|J} = (S_1\cap J,\dots, S_{l(S)}\cap J)$. The map $\cano$ sends any decomposition to the composition obtained by dropping the empty parts.

\end{definition}

\begin{example}
\label{hgcolo}
We represent the coloring of a hypergraph on $I=\{a,b,c,d,e,f\}$ with $\{${\color{DarkGreen}1$(\bullet)$},{\color{DarkBlue}2$(\times)$},{\color{DarkMagenta}3$(\square)$},{\color{DarkRed}4$(\blacksquare)$}$\}$:
\begin{center}
\includegraphics[scale=1.6]{fig/hgcolobw}
\end{center}
The maximal vertex of $e_1$ is $a$ and the maximal vertices of $e_3$ are $c$ and $d$. The maximal color of $e_2$ is {\color{DarkMagenta}{3}}. The order of appearance of $\{a,c,d,e\}$ is $(\{e\},\{c,d\},\{a\})$.

\end{example}

\begin{definition}
Let $H$ be a hypergraph over $I$. An \textit{orientation} of $H$ is a function $f$ from $H$ to $I$ such that $f(e)\in e$ for every edge $e$. A \textit{directed cycle} in an orientation $f$ of $H$ is a sequence of distinct edges $e_1,\dots, e_k$ such that $f(e_1)\in e_2\setminus f(e_2),\dots, f(e_k)\in e_1\setminus f(e_1)$. An orientation is \textit{acyclic} if it does not have any directed cycle. Let $\mathcal{A}_H$ be the set of acyclic orientations of $H$.

An orientation $f$ of $H$ and a coloring $S$ of $H$ with $[n]$ are said to be \textit{compatible} if $S(f(e)) = \max(S(e))$ for every $e\in H$. They are said to be \textit{strictly compatible} if $f(e)$ is the unique maximal vertex of $e$.
\end{definition}

\begin{example}
The coloring given in Example \ref{hgcolo} has two compatible acyclic orientations: both send $e_1$ on $a$, $e_2$ on $c$ and $e_4$ on $b$, but one sends $e_3$ on $c$ and the other $e_3$ on $d$.

For the color set $\{${\color{DarkBlue}1$(\bullet)$},{\color{DarkRed}2$(\times)$}$\}$, the following coloring has 4 compatible orientations but only two are acyclic.
\begin{center}
\includegraphics[scale=1.6]{fig/hgcolo3bw}
\end{center}
\end{example}

\begin{theorem}
\label{chi}
Let $I$ be a set and $H\in HG[I]$ a hypergraph over $I$. Then $\chi_I(H)(n)$ is the number of colorings of $H$ with $[n]$ such that every edge has only one maximal vertex. This is also the number of strictly compatible pairs of acyclic orientations and colorings with $[n]$.
Furthermore, defining $P_{H,f} = \{ P \vDash f(H)\, |\,  v\in e\setminus f(e) \Rightarrow P(v)< P(f(e))\}$, for every $f\in \mathcal{A}_H$,

we have that $$\chi_I(H)(n) = n^{|J_H|}\sum_{f\in \mathcal{A}_H}\sum_{P\in P_{H,f}} F_{p_1,\dots, p_{l(P)}}(n),$$ where $J_H\subseteq I$ is the set of isolated vertices of $H$ (i.e vertices not in an edge) and for every $P\in P_{H,f}$, $p_i =|\tilde{P}_i|$ and $\tilde{P}_i = \left(\bigcup_{e\in f^{-1}(P_i)}e\right) \cap f(H)^c\bigcap_{j<i} \tilde{P}_j^c$.
\end{theorem}

\begin{proof}
For $S$ a decomposition of $I$ of size $n$, let $H_1\in HG[S_1],\dots,H_n\in HG[S_n]$ be hypergraphs such that $H_1\otimes\dots\otimes H_n = \Delta_{S_1,\dots, S_n}(H)$. Let $S$ be a decomposition of $I$ of size $n$. Let $e$ be an edge. We then have the equivalence:
\begin{align*}
e\in H_i &\iff e\cap S_i \not = \emptyset \wedge\forall j>i, e\cap S_j = \emptyset \\
&\iff \text{$e\cap S_i$ is the set of maximal vertices of $e$}
\end{align*}
Hence, we have that
\begin{align*}
\zeta_{S_1}\otimes\dots\otimes\zeta_{S_n}\circ\Delta_{S_1,\dots, S_n}(H) = 1 &\iff \forall e\in H, e\in H_i \Rightarrow |e\cap S_i| = 1\\
&\iff\text{each edge has only one maximal vertex.}
\end{align*}
The equivalence between the colorings such that every edge has only one maximal vertex and the strictly compatible pairs of acyclic orientations and colorings is given by the bijection $S\mapsto (e\mapsto v_e,S)$, where $v_e$ is the unique vertex in $e$ such that $S(v_e) = \max(S(e))$.

The term $n^{|J_H|}$ in the formula is trivially obtained, in the following we hence consider that $H$ has no isolated vertices.

Informally, the formula can be obtained by the following reasoning. To choose a coloring such that every edge has only one maximal vertex, one can proceed in the following way:
\begin{enumerate}
\item choose the maximal vertex of each edge ($f\in \mathcal{A}_H$),
\item choose in which order those vertices appear ($P\in P_{H,f}$),
\item choose the color of those vertices ($k_1+1,\dots,k_{l(P)}+1$), (and notice that the set of such choices is empty if $l(P)> n$, which allows us not to add this non polynomial dependency in $n$ at the previous choice),
\item choose the colors of the yet uncolored vertices which are in the same edge than a vertex of minimal color in $f(H)$ ($k_1^{|\tilde{P}_1|}$); then those in the same edge than a vertex of second minimal color in $f(H)$ ($k_2^{|\tilde{P}_2|}$), etc.
\end{enumerate}

More formally, we show that there exists a bijection between the set of colorings such that every edge has only one maximal vertex and the set $$\bigsqcup_{f\in \mathcal{A}_H}\bigsqcup_{P\in P_{H,f}}\bigsqcup_{0\leq k_1 < k_2 < \dots < k_{l(P)}\leq n-1} \prod_{1\leq i \leq l(P)}[k_i]^{\tilde{P}_i},$$ where $[k_i]^{\tilde{P}_i}$ is the set of maps from $\tilde{P}_i$ to $[k_i]$. Let $g$ be a coloring of interest and define:
\begin{itemize}
\item $f:e \mapsto v\in e$ such that $g(v) = \max(g(e))$,
\item $P = h\circ g(f(H))$ where $h$ is the increasing bijection from $g(f(H))$ to $[|f(H)|]$,
\item $\tilde{P}_i = \left(\bigcup_{e\in f^{-1}(P_i)}e\right) \cap f(H)^c\bigcap_{j<i} \tilde{P}_j^c$ for $1\leq i\leq l(P)$,
\item $k_i = g(P_i) - 1$ for $1\leq i \leq l(P)$.
\end{itemize}
The function $f$ not being in $\mathcal{A}_H$ would imply that there exists a vertex $v$ such that $g(v)<g(v)$. This is not possible, hence $f\in \mathcal{A}_H$. We also have that $P\in P_{H,f}$ because by definition of $g$, $v\in e\setminus f(e)$ implies $g(v) < g(f(e))$ and $h$ is increasing. It is also clear that $0\leq k_1< \dots < k_{l(P)} \leq n-1$. The image of $g$ is then $(g_{|\tilde{P}_1},\dots,g_{|\tilde{P}_{l(P)}})$ which is in $\prod_{1\leq i \leq l(P)}[k_i]^{\tilde{P}_i}$ since for every $v\in \tilde{P}_i$ we must have $g(v) < g(P_i)$ by definition. Let us now consider $f\in \mathcal{A}_H$, $P\in P_{H,f}$, $1\leq k_1 < \dots < k_{l(P)}$ and $(g_1,\dots g_{l(P)})\in \prod_{1\leq i \leq l(P)}[k_i]^{\tilde{P}_i}$. Let $h$ be the increasing bijection from $[l(P)]$ to $\{k_1+1,\dots, k_{l(P)}+1\}$ and define $g: I \rightarrow [n]$ by $g_{|\tilde{P}_i} = g_i$ and $g_{|f(H)} = h\circ P$ (it is sufficient since $(\tilde{P}_1,\dots \tilde{P}_{l(P)},f(H))$ is a partition of $I$). Let us show that $g$ is a coloring of interest. Let be $v\in e\setminus f(e)$,
\begin{itemize}
\item if $v\in f(H)$ then $P(v)<P(f(e)$) by definition and so $g(v) < g(f(e))$, since $h$ is increasing,
\item if $v\not\in f(H)$ then $v\in \tilde{P}_i$ with $i\leq P(f(e))$ and so $g(v) = g_i(v) \leq k_i < k_i + 1 \leq k_{P(f(e))} + 1 = g(f(e))$.
\end{itemize}
We conclude the proof by remarking that the two defined transformations are inverse functions.
\end{proof}

\begin{example}
The coloring given in Example \ref{hgcolo} is not counted in $\chi_I(H)(4)$ since $e_3$ has two maximal vertices. However by changing the color of $d$ to {\color{DarkBlue}2} we do obtain a coloring where every edge has only one maximal vertex.

Let $H$ be the hypergraph $\{\{1,2,3\},\{2,3,4\}\}\in HG[[4]]$ represented in Figure \ref{same-edges}. Then we have $\chi_{[4]}(H)(n)= n^4 - \frac{8}{3}n^3+\frac{5}{2}n^2-\frac{5}{6}n$ and we do verify that, for example, $\chi_{[4]}(H)(2)=3$.
\end{example}

We are now interested in the value of $(-1)^{|I|}\chi_I(H)(-n)$. Let us first state two lemmas. The first lemma justifies the use of the $F_p$ (with $p$ a finite sequence of integers) polynomials to express the basic invariant: they have a good expression on negative integers. The second lemma is a result which can be interpreted on graphs and partitions as we do, but also on posets and linear extensions. It is the crux of the proof of Theorem \ref{chi-n}.

Given an integer $n$, a sequence of positive integers $p=p_1,\dots, p_t$ is said to be a \textit{decomposition} of $n$ if $n=\sum_{i=1}^t p_i$. We denote this by $p\vdash n$. If $p=(p_{1,1},\dots,p_{1,k_1},p_{2,1},\dots,p_{2,k_2},\dots,p_{l,k_l})$ and $q=(q_1,\dots, q_l)$ are two decompositions of the same integer, we say that $q$ \textit{coarsens} $p$ or $p$ \textit{refines} $q$ and write $p\prec q$ if $(p_{i,1},\dots,p_{i,k_i})$ is a decomposition of $q_i$ for $1\leq i\leq l$.

\begin{example}
The sequences $p_1=(4,2,3,3)$, $p_2=(3,1,2,2,1,1,1,1)$ and $p_3 = (4,3,1,1,3)$ are three decompositions of $12$ such that $p_2$ refines $p_1$ and there is no relation of refinement and coarsening between $p_3$ and the two other sequences.
\end{example}

\begin{lemma}
\label{f-n}
Let $p$ be a sequence of positive integers of length $t$. Then $$F_{p}(-n) = (-1)^{d_t}\sum_{p\prec q} F_q(n+1).$$
\end{lemma}

\begin{proof}
Remark that $\sum_{p\prec q} F_q(n+1)$ can also be written as $\sum_{0\leq k_1 \leq\dots\leq k_t\leq n}k_1^{p_1}\cdots k_t^{p_t}$. We now proceed by induction on $t$. For $t=1$, we have
\begin{align*}
F_p(-n) &= \sum_{i=0}^p \binom{p+1}{i}\frac{B_i}{p+1}(-n)^{p+1-i} \\
&= \frac{(-1)^{p+1}}{p+1}n^{p+1} -\frac{1}{2}(-1)^pn^p + (-1)^{p+1}\sum_{i=2}^p \binom{p+1}{i}\frac{B_i}{p+1}n^{p+1-i} \\
&= (-1)^{p+1}\left(\frac{1}{p+1}n^{p+1} +\frac{1}{2}n^p + \sum_{i=2}^p \binom{p+1}{i}\frac{B_i}{p+1}n^{p+1-i}\right) \\
&= (-1)^{p+1}(F_p(n) + n^p) = (-1)^{p+1}F_p(n+1),
\end{align*}
where the second equality comes from the fact that $B_i =0$ when $i$ is an odd number different from 1. Suppose now our proposition is true up to $t$. In the proof of Proposition 2 we showed that $F_{p_1,\dots, p_{t+1}}(n) = \sum_{j = 0}^{d_t - 1} a_j F_{d_{t+1} - 1 - j}(n)$ where $a_j$ is the $d_t-j$ coefficient of $F_{p_1,\dots, p_{t}}(n)$. This gives
\begin{align*}
F_{p_1,\dots, p_{t+1}}(-n) &= \sum_{j = 0}^{d_t - 1} a_j (-1)^{d_{t+1} - j}\sum_{k=0}^{n}k^{d_{t+1} - 1 - j} = -\sum_{j = 0}^{d_t - 1} a_j\sum_{k = 0}^{n} (-k)^{p_{t+1} + d_t -j} \\
&= -\sum_{k = 0}^{n} (-k)^{p_{t+1}}\sum_{j = 0}^{d_t -1} a_j (-k)^{d_t-j} = (-1)^{p_{t+1}+1}\sum_{k = 0}^n k^{p_{t+1}} F_{p_1,\dots,p_t}(-k) \\
&= (-1)^{p_{t+1}+1}\sum_{k_{t+1} = 0}^n k_{t+1}^{p_{t+1}} (-1)^{d_t}\sum_{0\leq k_1 \leq\dots\leq k_t\leq k_{t+1}}k_1^{p_1}\cdots k_t^{p_t} \\
&= (-1)^{d_{t+1}}\sum_{0\leq k_1 \leq\dots\leq k_{t+1} \leq n}k_1^{p_1}\cdots k_{t+1}^{p_{t+1}} \\
&= (-1)^{d_{t+1}}\sum_{p\prec q} F_q(n+1),
\end{align*}
where the fifth equality is our induction hypothesis.
\end{proof}

\begin{definition}
Let $I$ and $J$ be two disjoint sets and $P = (P_1,\dots,P_l)\vDash I$ and $Q = (Q_1,\dots, Q_k) \vDash J$ be two compositions. The \textit{product} of $P$ and $Q$ is the composition $P\cdot Q = (P_1,\dots,P_l,Q_1,\dots Q_k)$. The \textit{shuffle product} of $P$ and $Q$ is the set $sh(P,Q) = \{R\vDash I\sqcup J\,|\, P=\cano (R_{|I}), Q=\cano(R_{|J})\}$.

Let $P'=(P_{1,1},\dots,P_{1,k_1},P_{2,1},\dots,P_{2,k_2},\dots,P_{l,k_l})$ be another composition of $I$. We say that $P'$ \textit{refines} $P$ and write $P'\prec P$ if $P_i = \bigcup_{j=1}^{k_i}P_{i,j}$ for $1\leq i\leq l$.
\end{definition}

Recall that compositions can be seen as surjections and that for a decomposition $P\vDash I$ and an element $v\in I$, we denote by $P(v)$ the index $i$ such that $v\in P_i$.

\begin{lemma}
\label{compsum}
Let $I$ be a set and $P\vDash I$ a composition of $I$. We have the identity: $$\sum_{Q\prec P} (-1)^{l(Q)} = (-1)^{|P|}.$$

Furthermore let $G$ be a directed acyclic graph on $I$ and consider the \textit{constrained set} \linebreak[4] $C(G,P)=\{Q\prec P\,|\, \forall (v,v')\in G,Q(v)< Q(v')\}$. We have the more general identity: $$\sum_{Q\in C(G,P)} (-1)^{l(Q)} = \left\{\begin{array}{cl}
0  & \text{if there exists $(v,v')\in G$ such that $P(v')<P(v)$},    \\
(-1)^{|P|}  & \text{if not.}\end{array}\right.$$
\end{lemma}

\begin{proof}
Since $\sum_{Q\prec P} (-1)^{l(Q)} = \prod_{i=1}^{l(P)}\sum_{Q\vDash P_i} (-1)^{l(Q)}$ we only need to show that $\sum_{Q\vDash I} (-1)^{l(Q)} = (-1)^{|I|}$ to prove the first identity. Since the compositions of $I$ of size $n$ and the surjections from $I$ to $[n]$ are in bijection, we have that:
\begin{align*}
\sum_{Q\vDash I} (-1)^{l(Q)} &= \sum_{n=1}^{|I|} (-1)^n S_{|I|,n} = \sum_{n=1}^{|I|} (-1)^n \sum_{k=1}^n (-1)^{n-k}\binom{n}{k}k^{|I|} \\
&= \sum_{k=1}^{|I|}(-1)^k\left(\sum_{n=k}^{|I|}\binom{n}{k}\right)k^{|I|} = \sum_{k=1}^{|I|}(-1)^k\binom{|I|+1}{k+1}k^{|I|} \\
&= (-1)^{|I|}\sum_{k=0}^{|I|-1}(-1)^{k}\binom{|I|+1}{k}(|I|-k)^{|I|} \\
&= (-1)^{|I|}(1 + \sum_{k=0}^{|I|+1}(-1)^{k}\binom{|I|+1}{k}(|I|-k)^{|I|}) \\
&= (-1)^{|I|}.
\end{align*}
Note that the last equality is a direct consequence of Corollary \ref{idcombi}.

To show the second identity first remark that the case where the sum is null is straightforward: if there exists $(v,v')\in G$ such that $P(v')<P(v)$, then $C(G,P) = \emptyset$ and so the sum is null. From now on we only consider non empty summation sets. In this case we have that $\sum_{Q\in C(G,P)} (-1)^{l(Q)} = \prod_{i=1}^{l(P)}\sum_{Q\in C(G\cap {P_i}^2,(P_i))} (-1)^{l(Q)}$ and we only need to show that \linebreak[4] $\sum_{P\in C(G)} (-1)^{l(P)} = (-1)^{|I|}$ where $C(G)=C(G,(I))$. Let $S(G)$ denote the sum $\sum_{P\in C(G)} (-1)^{l(P)}$ from now on.

If $G$ is not connected let $I=J\sqcup K$ and $G=H\sqcup H'$ where $V(H) = J$ and $V(H') = K$. Let $P\in C(H)$ and $Q\in C(H')$ and suppose without loss of generality that $m = l(Q) < l(P) = M$. To choose $R$ in $sh(P,Q)$ we can first choose its length; then which indices are going to have a part of $Q$; and then which indices among them are also going to have a part of $P$. This leads to:
\begin{align*}
\sum_{R\in sh(P,Q)} (-1)^{l(R)} &= \sum_{k=M}^{m+M}(-1)^{k}\binom{k}{m}\binom{m}{M-(k-m)} \\
&= \sum_{k=0}^{m} (-1)^{k+M}\binom{M+k}{m}\binom{m}{k-m} \\
&= (-1)^{M}\sum_{k=0}^{m} (-1)^{m-k}\binom{M+m-k}{m}\binom{m}{k} \\
&= \frac{(-1)^{M}}{m!}\sum_{k=0}^{m} (-1)^{m-k}\binom{m}{k}\frac{(m+M-k)!}{(M-k)!} \\
&= \frac{(-1)^{M}}{m!}\sum_{k=0}^{m} (-1)^{m-k}\binom{m}{k}(-k)^m \\
&= \frac{(-1)^{m+M}}{m!}\sum_{k=0}^{m} (-1)^{m-k}\binom{m}{k}k^m \\
&= \frac{(-1)^{m+M}}{m!}S_{m,m} = (-1)^{m+M} = (-1)^{l(P)+l(Q)},
\end{align*}
where the fifth equality follows from Corollary \ref{idcombi}. This shows that $S(G)$ is multiplicative (with the product being the disjoint union) and so we can restrict ourselves to showing that $S(G) = (-1)^{|I|}$ for $G$ a connected graph. We will do this by induction on the number of edges of $G$.

Suppose now that $G$ is connected. If $G$ has no edges then $G$ is reduced to a single vertex and the result is trivial. Thus let be $(v,v')\in G$. We say that $(v,v')$ is superfluous if there exists $v_0$, $v_1$, ..., $v_{k+1}\in I$ such that $v=v_0$, $v'=v_{k+1}$ and $(v_i,v_{i+1})\in G$ for all $i\in [k]$. If $(v,v')$ is superfluous then $C(G) = C(G(v,v'))$ and so $S(G) = S(G\setminus(v,v')) = (-1)^{|I|}$ by induction. Otherwise we have $C(G\setminus(v,v')) = C(G) + C(t_{(v,v')}(G)) + C(G\setminus(v,v'))\cap\{P\vDash I\,|\, P(v) = P(v')\}$, where $t_{(v,v')}$ sends $G$ on $G\setminus(v,v')\cup(v',v)$. By induction, we know that $S(G\setminus(v,v')) = (-1)^{|I|}$ and since $C(G\setminus(v,v'))\cap\{P\vDash I\,|\, P(v) = P(v')\} = C\left(G\cap(I/v')^2\cup\bigcup_{(w,v')\in G\setminus(v,v')} (w,v)\cup\bigcup_{(v',w)\in G} (v,w)\right)$, we also have by induction that $\sum_{P\in C(G\setminus(v,v'))\cap\{P\vDash I\,|\, P(v) = P(v')\}} (-1)^{l(P)} = (-1)^{|I|-1}$. Hence, we have the equivalence $S(G) = (-1)^{|I|} \iff S(t_{(v,v')}(G)) = (-1)^{|I|}$.

Let $e_1, \dots, e_k$ be a sequence of edges such that for every $i$, $G_i = t_{e_i}\circ\dots\circ t_{e_1}(G)$ does not have a directed cycle. Then we have that $S(G) = (-1)^{|I|}$ if and only if $S(G_k) = (-1)^{|I|}$. If $G$ has a cycle then we can find a sequence such that $G_k$ has a superfluous edge and hence $S(G_k) = (-1)^{|I|}$. If $G$ does not have any cycle then every sequence of edges satisfies the condition ``$G_i$ does not have a directed cycle'' and so $S(G) = (-1)^{I}$ as long as there exists a directed graph $G'$ with the same underlying non-oriented graph than $G$ such that $S(G') = (-1)^{|I|}$. Given a non-oriented connected graph $H$, we can always find a directed graph $G$ on it with only one vertex $v$ such that for every $w\in V(G)$, $(w,v)\not \in G$. Then we have that $C(G) = (\{v\})\cdot C(G\cap (V(G)-v)^2)$ which gives us $S(G) = -S(G\cap (V(G)-v)^2) = (-1)^{|V(G)|}$ by induction. This concludes the proof.
\end{proof}

We can now state the main result of this section which is a direct generalization to hypergraphs of the reciprocity theorem of Stanley on graphs \cite{stan}.

\begin{theorem}[Reciprocity theorem on hypergraphs]
\label{chi-n}
Let $I$ be a set and $H\in HG[I]$ a hypergraph over $I$. Then $(-1)^{|I|}\chi_I(H)(-n)$ is the number of compatible pairs of acyclic orientations and colorings with $[n]$ of $H$. In particular, $(-1)^{|I|}\chi_I(H)(-1) = |\mathcal{A}_H|$ is the number of acyclic orientations of $H$.
\end{theorem}

\begin{proof}

From Proposition \ref{chi} and Lemma \ref{f-n} we have that $$\chi_I(H)(-n) = (-n)^{|J_H|}\sum_{f\in \mathcal{A}_H}\sum_{P\in P_{H,f}}(-1)^{\sum_{i=1}^{l(P)}p_i + l(P)}\sum_{(p_1, \dots, p_{l(P)}) \prec q}F_q(n+1).$$
Remark that:
\begin{itemize}
\item $\sum_{i=1}^{l(P)}p_i = |I\setminus J_H| -|f(H)|$ (since $(\tilde{P}_1,\dots \tilde{P}_{l(P)}, f(H))$ is a partition of $I\setminus J_H$),
\item $\phi :\{Q\vDash f(H)\,|\, P\prec Q\} \rightarrow \{q\vdash(|I\setminus J_H| -|f(H)|)\,|\, (p_1,\dots, p_{l(P)}) \prec q\}$ $Q\mapsto (|\tilde{Q}_1|,\dots, |\tilde{Q}_{l(Q)}|)$ is a bijection (where $\tilde{Q}_i$ is defined in the same way that $\tilde{P}_i$ in Theorem \ref{chi}).
\end{itemize}
This leads to:
\begin{align*}
(-1)^{|I|}\chi_I(H)(-n) &= n^{|J_H|}\sum_{f\in \mathcal{A}_H}(-1)^{|f(H)|}\sum_{P\in P_{H,f}}(-1)^{l(P)}\sum_{P\prec Q} F_{\phi(Q)}(n+1)\\
&= n^{|J_H|}\sum_{f\in \mathcal{A}_H}(-1)^{|f(H)|}\sum_{Q\vDash f(H)}\left(\sum_{\substack{P\prec Q\\P\in P_{H,f}}} (-1)^{l(P)}\right)F_{\phi(Q)}(n+1).
\end{align*}
By definition of $\mathcal{A}_H$, $G = \{(v,f(e))\,|\, v\in e\setminus f(e)\}$ is a directed acyclic graph on $f(H)$. Hence, remarking that $\{ P\prec Q\,|\, P\in P_{H,f}\} = C(G,Q)$, Lemma \ref{compsum} leads to:
\begin{align*}
(-1)^{|I|}\chi_I(H)(-n) &= n^{|J_H|}\sum_{f\in \mathcal{A}_H}(-1)^{|f(H)|}\sum_{\substack{P\vDash f(H)\\ P(v)\leq P(v') \forall(v,v')\in G}} (-1)^{|f(H)|}F_{\phi(P)}(n+1) \\
&= n^{|J_H|}\sum_{f\in \mathcal{A}_H}\sum_{P\in P_{H,f}'} F_{\phi(P)}(n+1) \\
&= n^{|J_H|}\sum_{f\in \mathcal{A}_H}\sum_{P\in P_{H,f}'}F_{p_1,\dots, p_{l(P)}}(n+1),
\end{align*}
where $P_{H,f}' = \{ P\vDash f(H)\,|\, P(v\in e\setminus f(e) \leq P(f(e)\}$.
To conclude, we now need to show that the set of compatible pairs (acyclic orientation, coloring with $n$) is in bijection with $$\bigsqcup_{f\in \mathcal{A}_H}\bigsqcup_{P\in P_{H,f}'}\bigsqcup_{0\leq k_1 < \dots < k_{l(P)}\leq n}[k_1]^{Q_1}\times\dots\times [k_{l(P)}]^{Q_{l(P)}}.$$ This can be done in a way analogous to the one used in the proof of Theorem \ref{chi}, the only difference being that we choose (with the same terms used in the proof) $g(P_i) = k_i$ instead of $g(P_i) = k_i+1$.
\end{proof}

\begin{example}
For any $I$, any $H\in HG[I]$ and $n$ a positive integer, we have $\chi_I(H)(n) \leq (-1)^{|I|}\chi_I(H)(-n)$. This comes from the fact that any strictly compatible pair is compatible. This is observed for $H=\{\{1,2,3\},\{2,3,4\}\}\in HG[[4]]$: $$\chi_{[4]}(H)(n)= n^4 - \frac{8}{3}n^3+\frac{5}{2}n^2-\frac{5}{6}n < n^4 + \frac{8}{3}n^3+\frac{5}{2}n^2+\frac{5}{6}n = (-1)^4\chi_{[4]}(H)(-n).$$
We also verify that $H$ does have $\chi_{[4]}(H)(-1) = 7$ acyclic orientations ($3\times 3$ orientations minus the two cyclic orientations).
\end{example}

\section{Application to other Hopf monoids}

In this section we use Theorem \ref{chi} and Theorem \ref{chi-n} to obtain a combinatorial interpretation of the basic invariants for the Hopf monoids presented in Sections 20 to 25 of \cite{AA}.

The general method to do this will be to use the fact that these Hopf monoids can be seen as sub-monoids of the Hopf monoid of simple hypergraphs, and then present an interpretation of what is an acyclic orientation on these particular Hopf monoids.

The result from subsection \ref{sshg} is new. The result from subsection \ref{graphs} already appears in \cite{AA}. The results of subsections \ref{sc} to \ref{paths} are new, but they can be derived from more general results in previous papers (details are provided at the beginning of each subsection). Note that however, we present here a uniform approach to obtain these results.

In all the following, we denote by $\chi$ the basic invariant of the Hopf monoid of hypergraphs.

\subsection{Simple hypergraphs}
\label{sshg}
A hypergraph is \textit{simple} if it has no repeated edges. The vector species $SHG$ of simple hypergraphs is not stable by the contraction defined on hypergraphs but it still admits a Hopf monoid structure. The product and co-product are given by, for $I=S\sqcup T$:
\begin{align*}
\mu_{S,T}: SHG[S]\otimes SHG[T] &\rightarrow SHG[I] & \Delta_{S,T}: SHG[I] &\rightarrow SHG[S]\otimes SHG[T] \\
H_1\otimes H_2 &\mapsto H_1\sqcup H_2 & H &\mapsto H_{|S}\otimes H_{/S},
\end{align*}
where $H_{|S} = \{e\in H\, |\, e\subseteq S\}$ and $H_{/S} = \{e\cap T\, |\, e \nsubseteq S\}\cup\{\emptyset\}$ but this time without repetition, i.e $H_{/S}$ can also be defined as $\{B\subseteq\,|\, \exists A\subseteq S, A\sqcup B \in H\}$. A discrete simple hypergraph is then a simple hypergraph with edges of cardinality at most one.

\begin{proposition}
\label{shg}
$\chi^{SHG}$ is the restriction of $\chi$ to the vector species of simple hypergraphs.
\end{proposition}

\begin{proof}
Let $s: HG\rightarrow SHG$ be the Hopf monoid morphism which removes any repetition of edges and let $H$ be a simple hypergraph over $I$. Considering $SHG$ as a sub-species of $HG$ and $s$ as a morphism of vector species we have: $\chi^{HG}_I(H) = \chi^{HG}_I(s(H))$. Then using the fact that $s$ is a Hopf monoid morphism stable on the sub-species of discrete elements we have that: $\chi^{HG}_I(s(H))=\chi^{SHG}_I(H)$. This concludes the proof.
\end{proof}

\subsection{Graphs}
\label{graphs}
The result of this subsection has already been given in Section 18 of \cite{AA}, but we give it here as a consequence of our result in the previous section.

A \textit{graph} can be seen as a hypergraph whose edges are all of cardinality 2. As for the vector species of simple hypergraphs, the vector species $G$ of graphs is not stable by the contraction defined on hypergraphs, but it still admits a Hopf monoid structure. The product and co-product are given by, for $I=S\sqcup T$:
\begin{align*}
\mu_{S,T}: G[S]\otimes G[T] &\rightarrow G[I] & \Delta_{S,T}: G[I] &\rightarrow G[S]\otimes G[T] \\
g_1\otimes g_2 &\mapsto g_1\sqcup g_2 & g &\mapsto g_{|S}\otimes g_{/S},
\end{align*}
where $g_{|S}$ is the sub-graph of $g$ induced by $S$ and $g_{/S} = g_{|T}$. A discrete graph is then a graph with no edges.

A \textit{proper coloring} of a graph is a coloring such that no edge has its two vertices of the same color. The chromatic polynomial of a graph is the polynomial $T$ such that $T(n)$ is the number of proper colorings with $n$ colors.

\begin{corollary}[Proposition 18.1 in \cite{AA}]
The basic invariant of $G$ is the chromatic polynomial.
\end{corollary}

\begin{proof}
Let $HG_{\leq 2}$ be the Hopf monoid of hypergraphs with edges of cardinality at most 2 and let $s:HG_{\leq 2}\rightarrow G$ be the Hopf monoid morphism which removes edges of cardinality 1. Since $HG_{\leq 2}$ is a Hopf sub-monoid of $HG$ we have that $\chi^{HG_{\leq 2}}$ is the restriction of $\chi$ to $HG_{\leq 2}$. Using the same reasoning than in the proof of Proposition \ref{shg}, with $G$ and $HG_{\leq 2}$ instead of $SHG$ and $HG$, we get that $\chi^{G}$ is the restriction of $\chi$ to $G$.
Furthermore, for $g$ a graph and $S$ a coloring of $g$, we have the equivalence between ``each edge has a unique maximal vertex'' and ``$S$ is a proper coloring''. The result follows.
\end{proof}

In particular, by evaluating $\chi$ on negative integers for a graph, we recover the classical reciprocity theorem of Stanley \cite{stan}.

\subsection{Simplicial complexes}
\label{sc}
In \cite{sc} Benedetti, Hallam, and Machacek constructed a combinatorial Hopf algebra of simplicial complexes and in particular they obtained results which generalise those given in this subsection.

An \textit{abstract simplicial complex}, or simplicial complex, on $I$ is a collection $C$ of subsets of $I$, called \textit{faces}, such that any subset of a face is a face i.e $J \in C$ and $K \subset J$ implies $K \in C$. By Proposition 21.1 of \cite{AA}, the vector species $SC$ of simplicial complexes is a sub-monoid of the Hopf monoid of simple hypergraphs.

The \textit{1-skeleton} of a simplicial complex is the graph formed by its faces of cardinality 2.

\begin{corollary}
Let $I$ be a set, $C\in SC[I]$ and $g$ its 1-skeleton. Then $\chi^{SC}_I(C)$ is the chromatic polynomial of $g$.
\end{corollary}

\begin{proof}
It is clear that any coloring of $C$ such that each edge has a unique maximal vertex induces a proper coloring of $g$. On the other hand if $J$ is a face of $C$ then it is also a clique of $g$, and so any proper coloring of $g$ must color all the vertices in $J$ in different colors. In particular there must be a unique maximal vertex in $J$.
\end{proof}

\subsection{Building sets}
Building sets and graphical building sets have been studied in a Hopf algebraic context by Gruji\'c in \cite{gr} where he gave similar results to the ones obtained in this subsection and the following one.

Building sets were independently introduced by De Concini and Procesi in \cite{DCP} and by Schmitt in \cite{Schmi}. A \textit{building set} on $I$ is collection $B$ of subsets of $I$, called \textit{connected sets}, such that if $J,K\in B$ and $J\cap K\not = \emptyset$ then $J\cup K\in B$ and for all $i\in I$, $\{i\}\in B$. By Proposition 22.3 of \cite{AA} the vector species $BS$ of building sets is a sub-monoid of the Hopf monoid of simple hypergraphs.

The maximal sets of a building set are called \textit{connected components}.

\begin{definition}
Let $B$ be a building set on $I$ with only one connected component. We define recursively a set of rooted trees which we call \textit{skeletons} of $B$.
\begin{itemize}
\item If $I=\{r\}$ is a singleton and $B=\{\{r\}\}$ the sole skeleton of $B$ is the rooted tree reduced to its root $r$.
\item If $I$ is not a singleton let $r$ be any element of $I$ and let $I_1,\dots,I_k$ be the maximal connected sets of $B$ not containing $r$. Then for each $i$ we associate to $I_i$ the building set $B_i=\{J\,|\,J\in B\text{ and }J\subseteq I_i\}$ on $I_i$. For each of these building sets, choose a skeleton $s_i$ and denote $r_i$ its root. Then the tree $s=\{(r,r_1),\dots,(r,r_k)\}\cup s_1\cup\dots\cup s_k$ with root $r$ is a skeleton of $B$.
\end{itemize}

Let $B$ a building set. Its \textit{skeletons} are the disjoint unions of skeletons of its connected component.
\end{definition}

\begin{remark}

The skeletons are exactly the $B$-$forests$ where all the vertices are singletons as defined in Definition 22.6 of \cite{AA}.
\end{remark}

A rooted forest can be seen as a forest with an orientation which sends each edge on the parent vertex. Hence, one can define compatible and strictly compatible colorings of a rooted forest. Moreover, these notions correspond to the notions of \textit{natural-$T$-partition} and \textit{strict-$T$-partition} of \cite{gr}.

\begin{corollary}
\label{corbuild}
Let $I$ be a set and $B\in BS[I]$. Then $\chi^{BS}_I(B)(n)$ is the number of strictly compatible pairs of skeletons and colorings with $[n]$ and $\chi^{BS}_I(B)(-n)$ is the number of compatible pairs of skeletons and colorings with $[n]$. In particular, $\chi^{BS}_I(B)(-1)$ is the number of skeletons of $B$.
\end{corollary}

\begin{proof}
Since $BS$ is a sub-monoid of $SHG$ we know that $\chi^{BS}$ is the restriction of $\chi$ to $BS$. Hence, we only need to show that there exists a bijection $b$ which preserves compatibility with colorings between the acyclic orientations of $B$ seen as a hypergraph and its skeletons. Furthermore, since the acyclic orientations of a disjoint union of hypergraphs are the disjoint unions of their acyclic orientations and the skeletons of a disjoint union of building sets are the disjoint unions of their skeletons, we only have to show this bijection for a building set with one connected component.

We will do this by induction on the size of $I$. If $I=\{r\}$ is a singleton and $B=\{\{r\}\}$, then the unique acyclic orientation of $B$ is $f:\{r\}\mapsto r$ and the unique skeleton of $B$ is the rooted tree with only vertex $r$. These two elements are both compatible with all the colorings hence the preserving bijection $b: f \mapsto \{r\}$.

If $I$ is not a singleton, let $K$ be the connected component of $B$.
Let $f$ be an acyclic orientation of $B$ and $r=f(K)$. Then necessarily all the connected sets of $B$ containing $r$ are also sent on $r$ by $f$ because otherwise we would have a cycle (since these connected sets are contained in $K$ by definition). Let now $I_1,\dots I_k$ be the maximum connected sets not containing $r$ and $B_1,\dots,B_k$ their associated building sets. Then $f_{|I_i}$ is an acyclic orientation of $B_i$ and $s_i = b(f_{|I_i})$ is a skeleton of $B_i$ for $1\leq i\leq k$. Let $r_i$ be the root of $s_i$ for $1\leq i\leq k$. Then, by definition of a skeleton, the tree $b(f)=\{(r,r_1),\dots,(r,r_k)\}\cup s_1\cup\dots\cup s_k$ rooted in $r$ is a skeleton of $B$.

Let now $s$ be a skeleton of $B$ and $r$ be its root. Let $B_0$ be the set of connected sets of $B$ containing $r$ and $I_0$ be the set of vertices which are in a connected set containing $r$ which is not the connected component. Let $I_1,\dots, I_k$ be the maximal connected set of $B$ not containing $r$ and $B_1,\dots,B_k$ be their associated building sets. Note that since $B$ is a building set, one has $I_i\cap I_j = \emptyset$ for $1\leq i\not = j\leq k$ (or else $I_i\subsetneq I_i\cup I_j\in B$ is not maximal).

By definition of a skeleton, $s$ has exactly $k$ sub-trees $s_1,\dots, s_k$ such that $s_i$ is a skeleton of $B_i$ for $1\leq i\leq k$.
Define $f_i=b^{-1}(s_i)$ for $1\leq i\leq k$ and $f_0$ the acyclic orientation of $B_0$ which sends every connected set of $B_0$ on $r$. Let $f$ be the orientation of $B$ which sends a connected set $K\in B_i$ on $f_i(K)$ for $i$ such that $K\in B_i$. This orientation is everywhere well defined because $B_0,B_1,\dots,B_k$ is, by definition, a partition of $B$. Suppose $f$ is not acyclic and let $e_1,\dots e_l$ be a directed cycle. Then necessarily the connected sets $e_1,\dots e_l$ can not all be in the same $B_i$ because $f_{|I_i} = f_i$ is acyclic. Without loss of generality, let $e_1\in B_{i_1}$ and $e_2\in B_{i_2}$ with $i_1\not = i_2$.
\begin{itemize}
\item Suppose $i_1 \not = 0$ and $i_2 \not = 0$. Then $f(e_1)\in e_1\cap e_2\subseteq I_{i_1}\cap I_{i_2}$, which is not possible by maximality of $I_{i_1}$.
\item Suppose $i_1 = 0$. Then $r = f(e_1) \in e_1\cap e_2\subseteq I_{i_2}$, which is not possible by definition of $I_{i_2}$.
\item Suppose $i_2 = 0$. Then by the previous point $e_3$ must also be in $B_0$. An iteration then implies that all the $e_i$ must be in $B_0$. This contradicts the hypothesis $i_1\not = i_2$.
\end{itemize}
Hence $f$ is an acyclic orientation.

The fact that in the two preceding constructions the root of the skeleton is the image of the connected component along with the induction hypothesis enable us to conclude that $b$ is bijection that preserves compatibility with colorings.
\end{proof}

\subsection{Simple graphs, ripping and sewing}
A \textit{simple} graph is a simple hypergraph that is also a graph. The vector species $W$ of simple graphs admits a Hopf monoid structure, the product and co-product are given by, for $I=S\sqcup T$:
\begin{align*}
\mu_{S,T}: W[S]\otimes W[T] &\rightarrow W[I] & \Delta_{S,T}: W[I] &\rightarrow W[S]\otimes W[T] \\
w_1\otimes w_2 &\mapsto w_1\sqcup w_2 & w &\mapsto w_{|S}\otimes w_{/S}
\end{align*}
where $w_{|S}$ is the sub-graph of $w$ induced by $S$ and $w_{/S}$ is the simple graph on $T$ with an edge between $u$ and $v$ if there is a path from $u$ to $v$ in which all the vertices which are not ends are in $S$. These two operations are respectively called \textit{ripping out $T$} and \textit{sewing through $S$}. A discrete simple graph is then a simple graph with no edges.

\begin{definition}[Definition 23.1 in \cite{AA}]
Let be $w\in W[I]$. A \textit{tube} is a subset $J\subseteq I$ such that $w_{|J}$ is connected. The set of tubes of $w$ is a building set called \textit{graphical building set of $w$} and which we denote $\text{tubes}(w)$.
\end{definition}

By Proposition 23.3 of \cite{AA} we know that $w\mapsto \text{tubes}(w)$ is a Hopf monoid morphism between $W$ and $BS$.

Given a rooted tree we call its \textit{direct sub-trees} the sub-trees with roots the children of the root.

\begin{definition}
Let be $w\in W[I]$ a connected simple graph. We define the set of \textit{partitioning trees of $w$} inductively by the following:
\begin{itemize}
\item if $I=\{v\}$, then the unique partitioning of $w$ is the graph with $\{v\}$ as only vertex,
\item else choose $v\in I$ and a partitioning tree for each connected component of $w_{|I\setminus \{v\}}$. The tree with root $v$ and direct sub-trees these partitioning trees is then a partitioning tree of $w$.
\end{itemize}
If $w$ is not connected anymore, a \textit{partitioning forest of $w$} is the disjoint union of partitioning trees of each connected component of $w$.
\end{definition}

\begin{corollary}
Let $I$ be a set and $w\in W[I]$. Then $\chi^{W}_I(w)(n)$ is the number of colorings of $w$ with $[n]$ such that every path with ends of the same color has a vertex of color strictly greater than the colors of the ends. It is also the number of strictly compatible pairs of partitioning forests and colorings with $[n]$. $\chi^{W}_I(w)(-n)$ is the number of compatible pairs of partitioning forests and colorings with $[n]$. In particular, $\chi^{W}_I(w)(-1)$ is the number of partitioning trees of $w$.
\end{corollary}

\begin{proof}
Since $w\mapsto \text{tubes}(w)$ is a Hopf monoid morphism, we know from what follows Proposition \ref{invmorph} that $\chi^W_I(w) = \chi^{BS}_I(\text{tubes}(w))$. Hence from Corollary \ref{corbuild}, $\chi^W_I(w)(n)$ is the number of strictly compatible pairs of skeletons of $\text{tubes}(w)$ and colorings with $[n]$ and $\chi^W_I(w)(-n)$ is the number of compatible pairs of skeletons of $\text{tubes}(w)$ and colorings with $[n]$.

Furthermore since $\chi^{BS}$ is the restriction of $\chi$ to $BS$ we have that $\chi^W_I(w) = \chi_I(\text{tubes}(w))$ so $\chi^{W}_I(w)(n)$ is also the number of colorings of $\text{tubes}(w)$ such that all edges have a unique maximal vertex.

Given these two facts we now only need to show the two following points:
\begin{itemize}
\item A coloring $I\rightarrow [n]$ is a coloring of $\text{tubes}(w)$ such that all edges have a unique maximal vertex if and only if it is a coloring of $w$ such that every path with ends of the same color has a vertex of color strictly greater than the colors of the ends.
\item The partitioning forests of $w$ are exactly the skeletons of $\text{tubes}(w)$.
\end{itemize}

We begin by the first assertion. Let $S$ be a coloring of $\text{tubes}(w)$ of interest and $v_1,\dots,v_k$ a path of $w$ such that $S(v_1) = S(v_k)$. Then $w_{|\{v_1,\dots, v_k\}}$ is connected and so $\{v_1,\dots, v_k\}$ is an edge of $\text{tubes}(w)$. Since $v_1$ and $v_k$ are of the same color, their color can not be the maximal color. Hence there exists an $i$ such that $S(v_i) > S(v_1) = S(v_k)$ and $S$ is a coloring of $w$ of interest. Let now $S$ be a coloring of $w$ of interest and $e$ an edge of $\text{tubes}(w)$ with two vertices $v_1$ and $v_2$ of the same color. Then, since $w_{|e}$ is connected by definition, there exists a path in $e$ from $v_1$ to $v_2$ and hence $v_3$ such that $S(v_3) > S(v_1) = S(v_2)$. Thus there can only be one vertex of maximal color in $e$ and $S$ is a coloring of $\text{tubes}(w)$ of interest.

To show that partitioning forests and skeletons are the same objects, just remark that given a vertex $v\in J$, where $w_{|J}$ is a connected component of $w$, the connected components of $w_{|J\setminus\{v\}}$ are exactly the maximal connected sets of $\text{tubes}(w)$ included in $J$ but not containing $v$.
\end{proof}

\subsection{Set partitions}

Proposition 24.4 of \cite{AA} states that there exists an isomorphism between the Hopf monoid of permutahedra and the Hopf monoid of set partitions. Furthermore, Propositions 17.3 and 17.4 of \cite{AA} give a combinatorial interpretation of the basic invariant of the Hopf monoid of generalized permutahedra $GP$. The Hopf monoid of permutahedra being a sub-monoid of a quotient of $GP$, it should be possible to deduce the result presented in this subsection from the aforementioned propositions.

A \textit{partition of $I$} is a subset of $\mathcal{P}(I)\setminus\{\emptyset\}$ such that all elements, which are called \textit{parts}, are disjoints and their union equals $I$. The vector species $\Pi$ of partitions admits a Hopf monoid structure, the product and co-product are given by, for $I=S\sqcup T$:
\begin{align*}
\mu_{S,T}: \Pi[S]\otimes \Pi[T] &\rightarrow \Pi[I] & \Delta_{S,T}: \Pi[I] &\rightarrow \Pi[S]\otimes \Pi[T] \\
\pi_1\otimes \pi_2 &\mapsto \pi_1\sqcup \pi_2 & \pi &\mapsto \pi_{|S}\otimes \pi_{|T},
\end{align*}
where for $\pi=\{\pi^1,\dots,\pi^l\}$, $\pi_{|S}$ is the partition of $S$ obtained by taking the intersection with $S$ of each part $\pi^i$ and forgetting the empty parts. A discrete partition is then a partition where all parts are singletons.

A \textit{cliquey graph} is a disjoint union of cliques. By Proposition 24.2 of \cite{AA} we know that $\pi\mapsto c(\pi)$ is a Hopf monoid from $\Pi$ to $W$, where $c(\pi)$ is the cliquey graph with a clique on each part of $\pi$.

\begin{corollary}
Let $I$ be a set and $\pi = \{\pi^1,\dots,\pi^l\}\in\Pi[I]$. Then $\chi^{\Pi}_I(\pi)(n) = \Pi_{i=1}^lp_i!\binom{n}{p_i}$ where $p_i = |\pi^i|$.
\end{corollary}

\begin{proof}
Since $\chi^{\Pi}$ is multiplicative and $\pi\mapsto c(\pi)$ is a Hopf monoid morphism, we only need to show that $\chi^{W}_I(w)(n)=|I|!\binom{n}{|I|}$ where $w$ is the clique on $I$. A coloring $S$ of $w$ is such that every path with ends of the same color has a vertex of color strictly greater than the colors of the ends if and only if all vertices are of different colors (because for each pair $v_1,v_2$ of vertices $v_1,v_2$ is a path in $w$). Hence the number of such colorings is the number of injections from $I$ to $[n]$. This concludes the proof.
\end{proof}

\subsection{Paths}
\label{paths}
As for the previous subsection, Proposition 25.7 of \cite{AA} states that the Hopf monoid of sets of paths is isomorphic to the Hopf monoid of associahedra which is a sub-monoid of a quotient of $GP$. Hence, it should also be possible to deduce the result of this subsection from \cite{AA}.

A \textit{word} on $I$ is a total ordering of $I$. The \textit{paths} on $I$ are the words on $I$ quotiented by the relation $w_1\dots w_{|I|} \sim w_{|I|}\dots w_1$. A \textit{set of paths} $\alpha$ of $I$ is a partition $(I_1,\dots, I_l)$ of $I$ with a path $s_i$ on each part $I_i$ and we will write $\alpha = s_1|\dots|s_l$. The vector species $F$ of sets of paths admits a Hopf monoid structure, the product and co-product are given by, for $I=S\sqcup T$:
\begin{align*}
\mu_{S,T}: F[S]\otimes F[T] &\rightarrow F[I] & \Delta_{S,T}: F[I] &\rightarrow F[S]\otimes F[T] \\
\alpha_1\otimes \alpha_2 &\mapsto \alpha_1\sqcup \alpha_2 & \alpha &\mapsto \alpha_{|S}\otimes \alpha_{/S}
\end{align*}
where if $\alpha = s_1|\dots|s_l$, $\alpha_{|S}= s_1\cap S|\dots| s_l\cap S$ forgetting the empty parts and $\alpha_{/S}$ is the set of paths obtained by replacing each occurrence of an element of $S$ in $\alpha$ by the separation symbol $|$. A discrete set of paths is then a set of paths where all paths have only one element.

\begin{example}
For $I=\{a,b,c,d,e,f,g\}$ and $S=\{b,c,e\}$ and $T=\{a,d,f,g\}$, we have: $$\Delta_{S,T}(bfcg|aed) = bc|e\otimes f|g|a|d.$$
\end{example}

By Proposition 25.1 of \cite{AA} we know that $\alpha \mapsto l(\alpha)$ is a morphism of Hopf monoids from $F$ to $W^{cop}$; where $l(s_1|\dots|s_l)$ is the simple graph whose connected components are the paths induced by $s_1,\dots, s_l$.

\begin{example}
For $I=\{a,b,c,d,e,f,g\}$ and $\alpha=bfcg|aed$, $l(\alpha)$ is the following graph:
\begin{center}
\includegraphics[scale=1.5]{fig/path}
\end{center}
\end{example}

\begin{corollary}
Let $I$ be a set and $\alpha$ be a path on $I$. Then $\chi^F_I(\alpha)(n)$ is the number of strictly compatible pairs of binary trees with $|I|$ vertices and colorings with $[n]$ and $\chi^F_I(\alpha)(-n)$ is the number of compatible pairs of binary trees with $|I|$ vertices and colorings with $[n]$. In particular $\chi^F_I(\alpha)(-1) = C_{|I|}$ where $C_n = \frac{1}{n+1}\binom{2n}{n}$ is the $n$-th Catalan number.
\end{corollary}

\begin{proof}
First remark that by definition, $\chi^{W^{cop}} = \chi^{W}$ and so $\chi^F_I(\alpha)(n) = \chi^W_I(l(\alpha))(n)$. Fix one of the two total orderings of $I$ induced by $\alpha$ so that we can consider the left and the right of a vertex $v$ of $l(\alpha)$. Then each vertex of $l(\alpha)$ is totally characterised by the number of vertices on its left (and on its right) and hence the partitioning trees of $l(\alpha)$ are exactly the binary trees with $|I|$ vertices.
\end{proof}

\bigskip
\bigskip
\noindent{\bf Concluding remarks}

Let us end this paper by presenting some perspectives for future work.
We plan to generalize the results of this paper to all characters on the Hopf monoid of hypergraphs. While Theorem \ref{chi} does generalize easily for characters with value in $\{0,1\}$, the conditions on the characters are slighlty more involved for Theorem \ref{chi-n} to hold.

Finally, an open question that appears interesting to us is to recover Theorem \ref{chi-n} using the antipode formula given in \cite{AA}. We refer the reader to \cite{HypB} where this has been done for a different Hopf structure on hypergraphs.

\bigskip

\noindent{\bf Acknowledgement}

The authors would like to thank Alexander Postnikov for pointing out to them (after the submission of this paper) a different approach to obtain the basic invariant for hypergraphs \cite{Pos1}\cite{Pos2}. The authors are also grateful to the anonymous referee for his useful comments on a preliminary version of this paper.

\bibliographystyle{plain}
\bibliography{redac}
\end{document}

config: arxiv


TITLE: Huffman Coding Integer Identifier Table
QUESTION [1 upvotes]: this might be trivial but I have a brainfog here! I am working through a JPEG compression problem using Huffman codes. According to our book, the process for coding a quantized matrix for a jpeg has three ingredients; the huffman tree for the DC components, another huffman tree for the AC components and an integer identifier table. The problem is to encode the given matrix into bit streams using huffman coding:-
\begin{matrix}
-19 & 7 & 2 & -1 & 0 & 0 & 0 & 0 \\
-10 & -5 & 1 & 1 & 0 & 0 & 0 & 0\\
2 & -1 & -1 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
\end{matrix}
This is the given integer identifier table:-
$$
\begin{array}{c}
\text{L} & \text{Entry} & \text{Binary}\\
0 & 0 & -- \\
1 & -1,1 & 0,1 \\
2 & -2,-3,3,2 & 00,01,10,11 \\
3 & -7,-6,-5,-4,4,5,6,7 & 000,001,010,011,100,101,110,111 \\
4 & -15,-14,...,-8,8,...,14,15 & 0000,0001,...,0111,1000,...,1110,1111 \\
5 & -31,-30,...,-16,16,...,30,31 & 00000,00001,...,01111,10000,...,11110,11111 \\
6 & -63,-62,...,-32,32,...,62,63 & 0000000,000001,...,011111,100000,...,111110,111111 \\
. & . & . \\
. & . & . \\
\end{array}
$$
Thus far I am clear on determining the size of y for a given 8 * 8 matrix where $Y_0 = -19$ which is 5 and thus translates into 110 using the DPCM tree, however, I can't see the pattern in building the above table for the extra digits for -19. Appreciate any guidance....

REPLY [1 votes]: It’s not clear to me exactly what you’re asking, so I’ll address the three possibilities that occur to me. Bear in mind, however, that I’ve never worked with the algorithm, and this answer is based entirely on what I’ve picked up by reading in the last couple of hours; you may be working with a slightly different presentation of it.

The integer identification table is constructed in a straightforward manner. If $n$ is a positive integer, we assign to it its ordinary binary representation, which of course has a leading $1$. Thus, for example, $19$ is assigned the string $10011$. If $n$ is a negative integer such that $2^k\le-n<2^{k+1}$, let $f(n)=n+2^{k+1}-1$, and assign to $n$ the ordinary binary representation of $f(n)$ with a leading $\mathbf 0$. For example, $2^4\le 19<2^5$, so $$f(-19)=-19+2^5-1=12\;,$$ and $-19$ is assigned the string $01100$.
To use the integer identification table to construct the intermediate code, process the entries in the $8\times 8$ matrix in zig-zag order. Your first value is $-19$, which is represented by $01100$, a string of length $5$. It is preceded by $0$ zeroes, so the first two elements of the intermediate code are $(0,5),01100$: $0$ zeroes, followed by a $5$-bit code, which is $01100$.
The next entry in the matrix in zig-zag order is $7$, which is encoded as $111$; it is preceded by $0$ zeroes, so the next two elements of the intermediate code are $(0,3),111$: $0$ zeroes, followed by a $3$-bit code, which is $111$.
The next few entries in zig-zag order are $-10,2,-5,2,-1,1,-1,1,0,0,-1,1,0$, and then $64-15=49$ zeroes. The intermediate code is therefore
$$\begin{align*}
&\{(0,5),01100,(0,3)111,(0,4),0101,(0,2),10,(0,3),010,(0,2),10,\\
&\;\,(0,1),0,(0,1),1,(0,1),0,(0,1),1,(\color{red}{2},1),0,(0,1),1,(0,0)\}
\end{align*}\;.\tag{1}$$
The red $2$ represents the two zeroes before the last $-1$, and the final $(0,0)$ pair indicates that there are no more non-zero entries.
The last step is to use a Huffman encoding to transform $(1)$ into a bit string. The elements to be assigned Huffman codes are the ordered pairs, not counting the final $(0,0)$. Use the following frequency table to construct a Huffman code in the usual way. $$\begin{array}{cc}\text{pair}&\text{frequency}\\ \hline(0,1)&5\\(0,2)&2\\(0,3)&2\\(0,4)&1\\(0,5)&1\\(2,1)&1\end{array}$$ One possible encoding is: $$\begin{array}{cc}\text{pair}&\text{code}\\ \hline (0,1)&0\\(0,2)&110\\(0,3)&111\\(0,4)&100\\(0,5)&1010\\(2,1)&1011\end{array}$$ Now just replace each pair in $(1)$ by its code and leave the bit strings in $(1)$ as they are; the resulting bit string begins $\color{red}{1010}01100\color{red}{111}111\ldots$, where the red bits are the Huffman codes of the first two pairs.


TITLE: Is my proof for $\sqrt{2}$ Irrationality correct?
QUESTION [2 upvotes]: I use strong induction on $p$.
Proof:
We want to show that $\forall q\in \mathbb{N} \big[q>0 \rightarrow \neg\exists p\in\mathbb{N}\big(p/q=\sqrt{2}\big)\big]$. Let $q$ be arbitrary natural number and $q>0$.
Inductive Hypothesis :
Let $k\in\mathbb{N}$ and $k<p$ such that $\big[q>0 \rightarrow \neg\exists k\in\mathbb{N}\big(k/q=\sqrt{2}\big)\big]$.
Inductive Step :
If $p=0$ then $k<0$ therefore the statement $\big[q>0 \rightarrow \neg\exists p\in\mathbb{N}\big(k/q=\sqrt{2}\big)\big]$ is vacuously true. If $p>0$ to see that $\sqrt{2}$ is irrational, suppose it isn't. This means that $\big[\exists p\in\mathbb{N}\big(p/q=\sqrt{2}\big)\big]$. So $p/q=\sqrt{2} \iff q=p/\sqrt{2}$. It follows that $k=\frac{p}{\sqrt{2}}\sqrt{2} \iff k=p$. Then if we let $p=k$ we get $\big[\exists k\in\mathbb{N}\big(k/q=\sqrt{2}\big)\big]$. This contradicts our inductive hypothesis. Thus $\sqrt{2}$ is irrational.
If the proof is not correct then what have I gone wrong? Thanks in advance.

REPLY [1 votes]: I can see that you've done something wrong because you haven't used the definition of $\sqrt{2}$ anywhere, so the same argument would seemingly apply to any number.
I understand the setup and the base case but it's hard to follow the rest of your argument.  For strong induction you are supposed to be trying to prove that if $\sqrt{2}$'s numerator is at least $p$ then it's also at least $p+1$, but I don't know how to prove $\sqrt{2}$ is irrational this way either.
Try setting up the problem this way instead, with the definition unpacked immediately:
$\forall p \in \mathbb{N} : \forall q \in \mathbb{N}: q \gt 0 \rightarrow p^2 \ne 2 \cdot q^2$


TITLE: How to calculate the total resistance of the 5-cell (4 dimensional pyramid)?
QUESTION [2 upvotes]: The total resistance of an electrical circuit with the shape of a triangle or pyramid is easy to find.
Each edge has the resistance (value is R)
How can I find the total resistance of the 5-cell (4 dimensional pyramid)

REPLY [6 votes]: In the article:

Severino V. Gervacio, "Resistance distance in complete $n$-partite graphs", Disc. App. Math. 203, pp. 53–61

the author cites the surprising and elegant result (see refs. [3, 7, 9] therein) that

[F]or a connected graph, the summation of effective resistances between all pairs of adjacent vertices is equal to the total number of vertices minus 1.

This assumes a resistance of 1 (dimensionless) along each edge of the graph;  for a resistance of $R$ along each graph, we simply multiply the result of this theorem by $R$.
For a complete graph on $n$ vertices (which is the same as the skeleton of the $n$-cell), this implies that the total of all resistances of adjacent pairs of vertices is $n-1$.  Since all pairs of vertices are adjacent in a complete graph, there are $n(n-1)/2$ pairs of adjacent vertices, and so the resistance between any pair of adjacent vertices is $2/n$ (or $2R/n$ if the resistance of each edge is $R$.)


TITLE: How to solve system of equations using inverse matrix?
QUESTION [2 upvotes]: System of equations is the following:
$$x + 4y + 2z = 10$$
$$4x - 3y+0z = 6$$
$$2x + 2y + 2z = 14$$
Here is my solution:
$$det(A) = 1 *(-3 * 2 - 0 * 2) -4 * (4 * 2 - 0 * 2) + 2 * (4 * 2 - (-3) * 2)$$
$$= -6 -32 + 28$$
$$= -10$$
$$
    +\begin{pmatrix}
    -3 & 0 \\
    2 & 2 \\
    \end{pmatrix}
$$
$$
    -\begin{pmatrix}
    4 & 0 \\
    2 & 2 \\
    \end{pmatrix}
$$
$$
    +\begin{pmatrix}
    4 & -3 \\
    2 & 2 \\
    \end{pmatrix}
$$
$$
    -\begin{pmatrix}
    4 & 2 \\
    2 & 2 \\
    \end{pmatrix}
$$
$$
    +\begin{pmatrix}
    1 & 2 \\
    2 & 2 \\
    \end{pmatrix}
$$
$$
    -\begin{pmatrix}
    1 & 4 \\
    2 & 2 \\
    \end{pmatrix}
$$
$$
    +\begin{pmatrix}
    4 & 2 \\
    -3 & 0 \\
    \end{pmatrix}
$$
$$
    -\begin{pmatrix}
    1 & 2 \\
    4 & 0 \\
    \end{pmatrix}
$$
$$
    +\begin{pmatrix}
    1 & 4 \\
    4 & -3 \\
    \end{pmatrix}
$$
Above equals to:
$$
    \begin{pmatrix}
    -6 & -8 & 14 \\
    -4 & -2 & 6 \\
    -6 & -8 & -15\\
    \end{pmatrix}
$$
Then I multiply it by 1/-10 and the result is:
$$
    \begin{pmatrix}
    0,6 & 0,4 & 0,6 \\
    0,8 & 0,2 & -0,8 \\
    -1,4 & -0,6 & 1,5\\
    \end{pmatrix}
$$
Then I multiply it by:
$$
    \begin{pmatrix}
    10 \\
    4 \\
    16\\
    \end{pmatrix}
$$
Result is:
$$
    \begin{pmatrix}
    6 & 2,4 & 8,4 \\
    8 & 1,2 & -11,2 \\
    -14 & -3,6 & 21\\
    \end{pmatrix}
$$
Which results in:
$$
    \begin{pmatrix}
    16,8 \\
    -2\\
    3,4\\
    \end{pmatrix}
$$
So according to this logic:
$$x = 16,8$$
$$y = -2$$
$$z = 3,4$$
However when I test this solution it is incorrect, can anyone tell me what I'm doing wrong? Thanks.

REPLY [0 votes]: $$A=
    \begin{matrix}
    1 & 4 & 2 \\
    4 & -3 & 0 \\
    2 & 2 & 2 \\
    \end{matrix}
$$
$$b=
    \begin{matrix}
    10 \\
    6 \\
    14 \\
    \end{matrix}
$$
To find the inverse of A:
1.Find the Determinant: $\Delta A$ =-10
2.Find the matrix of cofactors:
$$\begin{matrix}
  -6 & -8 & 14\\
  -4 & -2 & 6\\
   6 & 8  & -19\\
 \end{matrix}$$
Cofactor for (i,j) the element =$(−1)^{i+j}\Delta M_{i,j}$ where $\Delta M_{i,j}$ is the minor for the (i,j) element
3.Take the transpose the matrix of cofactors:
$$\begin{matrix}
  -6 & -4 & 6\\
  -8 & -2 & 8\\
   14 & 6  & -19\\
 \end{matrix}$$
4. And in the end divide the matrix by the determine $\Delta A$ computed in step 1.
$$\begin{matrix}
  \frac{3}{5} & \frac{2}{5} & \frac{-3}{5}\\
  \frac{4}{5} & \frac{1}{5} & \frac{-4}{5}\\
   \frac{-7}{5} & \frac{-3}{5}  & \frac{19}{10}\\
 \end{matrix}$$
And to find the solution multiply the inverse to the matrix b:
We get $x=0,y=-2, z=9$


TITLE: How much energy is carried away by neutrinos in matter-antimatter annihilation?
QUESTION [3 upvotes]: Some people say that neutrinos carry away most of the energy, some others say just a fraction. So what is the truth? what is the percentage of energy lost due to neutrinos?

REPLY [2 votes]: Anna's answer is good, but it doesn't go far enough.  If you start with equal amounts of matter and antimatter, you end up with equal amounts of electrons and positrons, which eventually annihilate to photons.  You also end up with equal amounts of neutrinos and antineutrinos, which also eventually annihilate to photons.  So those (anti-)neutrinos only keep that energy temporarily. The only other permanent outlet is gravitons, which are entirely negligible.  So eventually,  all the energy ends essentially up as photons.