TITLE: Using (Potential) Energy to estimate velocity?
QUESTION [0 upvotes]: I'm reading Cohen's Concepts of nuclear physics. In the first chapter, he calculates a value for Electrostatic energy to insert a proton inside a nucleus, using coulomb potential energy formula $E_{c}=\frac{Z e^{2}}{4 \pi \epsilon_{0} R}$ where R is the typical radius for A=120 nucleus. This comes out to be 13 MeV.
He then says that though this is an underestimation, the order of magnitude is correct. And for this energy, the nucleons have non-relativistic velocities (0.15c).
My question is simple - This is electrostatic potential energy, how could this be used to estimate the velocity of nucleons. For that, shouldn't the kinetic energy of nucleons be used?

REPLY [0 votes]: The name of the theorem escapes me, but the statement is that for classical 1D motion under potential $V\sim x^n$
$$
\langle T\rangle = \frac{n}{2}\langle V\rangle
$$
Telling us that knowing the expectation of V is enough to know about T.
Assuming the ground state. We know second order perturbations to the hamiltonian shift the ground state to lower E, (the p^4 term is symmetric on the ground state, so first order vanishes) which is how we know that we underestimate T with this estimation.
Edit: the name is the Virial Theorem


TITLE: Show that a nonnegative harmonic function is constant
QUESTION [1 upvotes]: Suppose that $f(z): \mathbb{C} \rightarrow \mathbb{R}$ is harmonic and that $f(z) \ge 0 $ for all complex $z$.  Then $f$ must be constant.
I imagine that I will need to make use of Liousville's theorem or otherwise show that $f'$ is zero.  However the problem is that the book has not mentioned anything about harmonic functions other then the definition that the second partials of the real and imaginary parts add to zero.  It is clear that an analytic function is harmonic from the Cauchy Riemann equations, is the converse true?
Thanks in advance

REPLY [5 votes]: Let $u(x,y)$ be an harmonic non negative function. Then, exists an harmonic conjugate $v(x,y)$ such that $f(z)=u(x,y)+iv(x,y)$ where $z=x+iy$ is analytic in $\mathbb{C}$.
Now, consider $e^{f(z)}$. This function is analytic as $e$ and $f$ are, is never zero, and $|e^{f(z)}|=e^u \geq 1 $ because $u \geq 0$. Then $\frac{1}{e^{f(z)}}$ is analytic and bounded so for Liouville's theorem, must be constant. In this way, $u$ must be constant too.


TITLE: Proving $\sin 20^\circ \, \sin 40^\circ \, \sin 60^\circ \, \sin 80^\circ =\frac{3}{16}$
QUESTION [1 upvotes]: The problem is to prove that
$$\sin 20^\circ \, \sin 40^\circ \, \sin 60^\circ \, \sin 80^\circ =\frac{3}{16}$$
All my attempts were to get them in $\sin (2A)$ form after eliminating $\sin 60^\circ$ in both sides. Unfortunately, all these attempts were futile.
Any hints are welcomed.

REPLY [2 votes]: HINT:
Using Prove $ \sin(A+B)\sin(A-B)=\sin^2A-\sin^2B $,
$$\sin(60^\circ-x)\cdot\sin x\sin(60^\circ+x)=\sin x[\sin^2120^\circ-\sin^2x]=\dfrac{3\sin x-4\sin^3x}4$$
$$\implies4\sin(60^\circ-x)\cdot\sin x\sin(60^\circ+x)=\sin3x$$
Set $x=20^\circ$


TITLE: Is it possible to build a category whose arrows are interpretations that's fairly natural?
QUESTION [1 upvotes]: Is it possible to build a category whose arrows are model-theoretic interpretations in such a way that:

the presence or absence of parameters is handled in an elegant way.
the notion of a definable interpretation has a definition that's categorical and doesn't appeal to the concrete implementation of an interpretation.

I think we can define an interpretation in the following way.
This presentation exactly follows the presentation given in Wikipedia, except that I'm baking whether parameters are allowed into my concrete representation of an interpretation.
Let an interpretation $(b, n, i)$ from $A$ to $B$ be a triple consisting of $b$ which is $0$ or $1$, a positive integer $n$, and a binary relation $i \subset A^n \times B$ subject to the following constraints.

$i$ is right-total. For all $b$, $i^{\leftarrow}(b)$ is not empty.
$i$ is left-unique. For all $a$, $i^{\rightarrow}(a)$ has cardinality $0$ or $1$.
If $b$ is $0$, every $0$-definable subset of $A^n$ is $0$-definable in $B$.
If $b$ is not $0$, every with-parameters-definable subset of $A^n$ is with-parameters-definable in $B$.

There are a couple of small things that I don't really like about this way of talking about what an interpretation is:

Interpretations with parameters and interpretations without parameters live in separate realms. We can compose them and get a relation that is left-unique and right-total, but it won't necessarily be an interpretation. I think this is because we're controlling whether parameters are allowed at the level of the interpretation, rather than choosing it independently for the source and destination.
The multiplicity thing seems like it would be handled better by defining a notion of raising a structure to a given power $A^n$ rather than adding additional content that lives alongside the interpretation.

Here's one idea I had for how to do this, which I'll call a quasimodel, which is just the carrier of a model (i.e. a set) equipped with a boolean lattice of definable sets.
Let's define the notation $[A, U, n]$ where $A$ is a first-order structure, $U$ is the set of the parameters of $A$, and $n$ is a positive integer to be the quasimodel $((A'')^n, \Lambda(n))$ where $A''$ is the carrier of $A$ and $\Lambda(n)$ is the lattice of $A$-definable subsets with $n$ free variables.
In this setting, an interpretation $i : [A, U, n] \rightarrow^p [B, V, k]$ where $\rightarrow^p$ denotes a surjective partial function is just a partial function from $A$ to $B$ such that for all $\alpha$ in the lattice of $[A, U, n]$, $i^{\rightarrow}(\alpha)$ is in the lattice of $[B, V, k]$.
So, I think we can reasonably collect our quasimodels into a class of objects and make interpretations the maps between them.
We also have a notion of definability, which I think can be construed as follows:
$i : [A, U, n] \to^p [A, U, k]$ is definable if and only if the graph of the interpretation (an ($1+n+k$)-ary relation) is in $[A, U, 1+n+k]$.
We might be able to open this definition up a little bit and define $i : [A, U, n] \to^p [A, U'', k]$ to be definable when it is in $[A, U \cap U'', 1+n+k]$.
However, I can't figure out how to express this in a way that's more categorical.

REPLY [3 votes]: I've been meaning to write an answer for some time, expanding on user Dabouliplop's comments.
There is indeed a satisfying categorical treatment of interpretations, coming (unsurprisingly) from categorical logic. This will be a long answer, so I've broken it into sections. I'll first describe a category of interpretations between theories, and then explain how to obtain from this a category of interpretations between structures, as you desire.

For any first-order theory $T$, there is a category $C_T$, called the syntactic category of $T$. Its objects are first-order formulas, up to provable equivalence modulo $T$, and its arrows are definable functions, up to provable equivalence modulo $T$. More formally, if $\varphi(x)$ and $\psi(y)$  are formulas, we first rename the variables as necessary to make sure that $x$ and $y$ are disjoint tuples of variables. Then an arrow $[\varphi(x)]\to [\psi(y)]$ is represented by a formula $\theta(x,y)$ such that $T\models \forall x\, (\varphi(x)\to \exists^! y\, (\psi(y)\land \theta(x,y)))$, and two such formulas $\theta(x,y)$ and $\theta'(x,y)$ represent the same arrow if $T\models \forall x\, \forall y\, ((\varphi(x)\land \psi(y))\rightarrow (\theta(x,y)\leftrightarrow \theta'(x,y)))$.
The syntactic category $C_T$ can be equipped with the structure of a Boolean category. Essentially, this structure corresponds to the logical structure of formulas. For example, subobjects have meets and joins and complements in the subobject lattice (and, or, and not), and pullbacks have left and right adjoints (the quantifiers). Conversely, it turns out that every Boolean category is equivalent to one of the form $C_T$ for some (multi-sorted) first-order theory $T$.
Now if $C$ and $D$ are Boolean categories, then a functor $F\colon C\to D$ is a Boolean functor if it preserves all the structure of Boolean categories. A Boolean functor between syntactic categories, $I\colon C_T\to C_{T'}$ gives a translation from formulas in the language of $T$ to formulas in the language of $T'$, which preserves the logical structure and the truths of $T$. That is, it's an interpretation of $T$ in $T'$.

Well, really it's a definition of $T$ in $T'$, where a definition is a special type of interpretation that doesn't allow quotients by definable equivalence relations. To get to the general notion of interpretation, we have a few options:

On the logical side, we could replace $T$ and $T'$ with their canonical expansions $T^{\mathrm{eq}}$ and $(T')^{\mathrm{eq}}$ which eliminate imaginaries. Now a definition of $T^{\mathrm{eq}}$ in $(T')^{\mathrm{eq}}$ is the same as an interpretation of $T$ in $T'$. The syntactic category $C_{T^{\text{eq}}}$ has the additional structure of a Boolean pretopos, which is a Boolean category admitting "quotients" by internal equivalence relations.

On the categorical side, we could replace $C_T$ and $C_{T'}$ with their pretopos completions, introducing new "quotients". Witing $\widehat{C}$ for the pretopos completion of $C$, a morphism of pretoposes $\widehat{C_T}\to \widehat{C_{T'}}$ corresponds to an interpretation of $T$ in $T'$.

Finally, we could beef up the definition of the syntactic category directly, allowing an object to be a pair $(\varphi(x),E(x,x'))$, where $E$ is a formula which $T$ proves defines an equivalence relation on $\varphi(x)$, and adjusting the notion of arrow appropriately. The resulting syntactic category, call it $C'_T$, is a Boolean pretopos, and again we work with pretopos morphisms.

It turns out that all three of these are essentially the same: $C'_T$, $\widehat{C_T}$, and $C_{T^{\mathrm{eq}}}$ are all equivalent as Boolean pretoposes. To make the notation simpler, let's just write $C_T$ for the pretopos assigned to the theory $T$.

What about models? The category $\mathsf{Set}$ can also be equipped with the structure of a Boolean pretopos. A pretopos morphism $M\colon C_T\to \mathsf{Set}$ assigns a set to each formula, in such a way that the logical structure is preserved (e.g., meets of subobjects correspond to intersections). That is, it's exactly a model of $T$. To me, this is one of the most interesting things about categorical logic: interpretations and models are the same kind of thing, namely structure-preserving functors.
Now if $I\colon C_{T'}\to C_T$ is the pretopos morphism corresponding to an interpretation of $T'$ in $T$. Then for any model $M\colon C_T\to \mathsf{Set}$, we can compose to get a model $M\circ I\colon C_{T'}\to \mathsf{Set}$. This is the map from models of $T$ to models of $T'$ obtained from the interpretation.
In other words, the contravariant functor $\mathrm{Mod}$ from theories to classes, assigning to each theory its class of models, is represented by the pretopos $\mathsf{Set}$, in the sense that $\mathrm{Mod}(-)\cong \mathrm{Hom}_{\mathsf{BoolPreTop}}(C_{-},\mathsf{Set})$.

Now what about a category of interpretations between structures? Well, an interpretation of $A$ in $B$ is just the same thing as an interpretation of the complete theory $\mathrm{Th}(A)$ in the complete theory $\mathrm{Th}(B)$ which happens to transform the model $B$ into the model $A$.
Now remember, $A$ is a model of its complete theory, i.e. a pretopos morphism $A\colon C_{\mathrm{Th}(A)}\to \mathsf{Set}$. Similarly, we have $B\colon C_{\mathrm{Th}(B)}\to \mathsf{Set}$. An interpretation $I\colon C_{\mathrm{Th}(A)}\to C_{\mathrm{Th}(B)}$ acts on models by composition, so it transforms $B$ into $A$ exactly when $B\circ I = A$.
Let's write $\mathsf{CBPT}$ for the category of complete Boolean pretoposes. This is the subcategory of Boolean pretoposes consisting of the complete theories.
It's now apparent that we can identify the category of structures and interpretations between them with the slice category $\mathsf{CBPT}/\mathsf{Set}$. An object is a pretopos morphisms from a complete Boolean pretopos to $\mathsf{Set}$ (a structure, viewed as a model of its complete theory) and an arrow is a pretopos morphism (an interpretation) which composes correctly with the models.

Finally, what about parameters? Well, an interpretation of $A$ in $B$ which uses arbitrary parameters from $B$ is the same thing as a parameter-free interpretation of $A$ in $B$ where we view $B$ as a structure in the language with a constant symbol for every element of $B$. In general, if we want to consider interpretations in $B$ using parameters from a subset $C\subseteq B$, we just need to name the elements of $C$ by constant symbols.
So every structure appears "many times" in the slice category $\mathsf{CBPT}/\mathsf{Set}$, once for each choice of which elements are named by constant symbols, and you can view morphisms into each of these objects as interpretations allowing different sets of parameters.


TITLE: An absolutely convergent series may be rearranged.
QUESTION [4 upvotes]: Any rearrangement of an absolutely convergent sequence $(a_n)$ is another absolutely convergent sequence with the same limit.  Let $(a_{\sigma(n)})$ be the rearranged sequence under the bijection of indices $\sigma$.
My proof attempt.  Let $T_N = \sum_{n=1}^N |a_{\sigma(n)}|$ be the $N$th partial sum of the rearranged absolute series.   Similarly let $S_N$ be the partial sum of the original absolute series.   I know I want to try to prove the absolute sequences Cauchy.  Still working on it.

REPLY [7 votes]: You needn't make the $N$s match. You know you can take $N$ large enough so that $$\sum_{k\geqslant N}|a_k|<\varepsilon$$
Now pick $M$ large enough so that all the terms in $T_M$ are some of the terms in $S_N$. Then how large is $$\left|\sum_{k\geqslant 0}a_k-T_M\right|?$$


text:
\begin{document}
\maketitle
\begin{abstract}
This paper is based on a series of talks given at the Patejdlovka
Enumeration Workshop held in the Czech Republic in November 2007. The
topics covered are as follows. The graph polynomial, Tutte-Grothendieck invariants, an overview of relevant elementary finite Fourier analysis, the Tutte polynomial
of a graph
as a Hamming weight enumerator of its set of tensions (or flows), description
of a family of
polynomials containing the graph polynomial which yield
Tutte-Grothendieck invariants in a similar way.
\end{abstract}

\section{Introduction}

The graph polynomial is a generalization of the Vandermonde
determinant (which may be viewed as the graph polynomial of a complete graph) that
was considered by Sylvester and Petersen in the nineteenth century in
connection with binary quantic forms. Alon,
Tarsi and Matiyasevich in more recent years have found that it contains
a good deal of information about the vertex colourings of a graph. For
example, the number of proper $3$-colourings of a graph
is a simply defined function of the coefficients of its graph
polynomial. In this
article we consider a family of polynomials containing the graph
polynomial and ask whether other Tutte-Grothendieck invariants
can be obtained in a similar way. Our results are obtained by expressing the relevant
parameter as
the partition function of a vertex colouring model (such as the Potts
model) or, in different language, the graph parameter obtained from homomorphisms to a weighted graph.

In Section \ref{sec: Petersen graph poly} we define the graph
polynomial and explore its relation to proper
vertex colourings. In Section \ref{sec: TG} Tutte-Grothendieck
invariants are defined and their pervasiveness noted. In Section
\ref{sec: Fourier} a potted account is given of
Fourier analysis on finite Abelian groups which will be used to obtain our results. In Section
\ref{sec: we} tensions
and flows of a graph are defined and the view of the Tutte polynomial as a Hamming
weight enumerator propounded. In the final Section \ref{sec: graph polynomials} we
characterize those polynomials which share with the graph
polynomial the property of yielding a Tutte-Grothendieck invariant from the $\ell_2$-norm of their coefficients. More generally, the graph
polynomial is seen to belong to a family of polynomials
 whose $\ell_2$-norm is equal to an
 evaluation of the complete weight enumerator of the
set of tensions (or flows) of the graph.

An expanded version of Section \ref{sec: Fourier} can be found in
\cite{AJG07}, and an even more fulsome presentation is given in \cite{CCC07}.
The book \cite{Terras99} is recommended for an introduction to finite
Fourier analysis and its wide range of applications.

\section{The graph polynomial}\label{sec: Petersen graph poly}
Let $G=(V,E)$ be a graph
with some fixed, arbitrary
orientation of its edges, and denote its directed edge set by
$\overrightarrow{E}$.

Let $Q$ be a finite set of size $q$. A
{\em proper vertex $q$-colouring} using colour set $Q$ is an assignment of colours $(c_v:v\in
V)\in Q^V$ such that $c_u\neq c_v$ whenever $\{u,v\}\in E$.
The number of proper vertex $q$-colourings of $G$ is denoted by
$P(G;q)$ (an
evaluation of the chromatic polynomial of $G$ at $q$).

Let $\mathbf{x}=(x_v: v\in V)$ be a tuple of commuting indeterminates
indexed by $V$ and
define the {\em graph polynomial}\,\footnote{The graph polynomial has
  not yet acquired the qualification of a proper name.
The `Sylvester-Petersen polynomial' might be a candidate
\cite{Sylvester1878, P1891}. Matiyasevich analyses the graph polynomial of the line
graph of a cubic plane graph in order to obtain reformulations of the
Four Colour Theorem \cite{M04}. Alon and Tarsi \cite{AT92, AT97,
  Tarsi} interpret its
coefficients in terms of orientations; their interpretations in
terms of proper vertex colourings will be described in this
section. Ellingham  and Goddyn \cite{EG96} call the graph polynomial
the {\em graph  monomial} averring that the latter has a less
anonymous character than the former.} $F(G)$ in $\mathbb{C}[\mathbf{x}]$ by
$$F(G;\mathbf{x})=\prod_{(u,v)\in\overrightarrow{E}}(x_u-x_v).$$
Given an assignment of values $\mathbf{c}=(c_v:v\in V)\in\mathbb{C}^V$
to the indeterminates $\mathbf{x}=(x_v:v\in V)$, the graph polynomial takes a non-zero value
if and only if
$\mathbf{c}$ corresponds to a proper vertex colouring with colour set
$Q=\{c_v:v\in V\}$. Set $\zeta=e^{2\pi i/q}$. By restricting $c_v$ to one of the $q$ points
$1,\zeta,\ldots,\zeta^{q-1}$ on the unit circle  a criterion emerges
for the existence of a proper vertex $q$-colouring of $G$ in terms of
the polynomial $F(G;\mathbf{x})$.

The algebraic
variety of points $\{(c_v:v\in V):c_v\in
\{1,\zeta,\ldots,\zeta^{q-1}\}\}$ corresponds to the ideal
$(x_v^q-1:v\in V)$ of the ring $\mathbb{C}[\mathbf{x}]$.
Denote the graph polynomial modulo the ideal generated by the
polynomials $x_v^q-1$ by
$$F^{(q)}(G;\mathbf{x})=F(G;\mathbf{x})\bmod (x_v^q-1:v\in V).$$

By Lagrange interpolation,
\begin{align*} F^{(q)}(G;\mathbf{x}) & =\sum_{(a_v:v\in V)}\prod_{v\in V}\prod_{a\neq
  a_v}\frac{x_v-\zeta^{a}}{\zeta^{a_v}-\zeta^{a}}\;F(G;(\zeta^{a_v}:v\in V)\,)\\
 & = q^{-|V|}\sum_{(a_v:v\in V)}\prod_{v\in
  V}\frac{x_v^q-1}{\zeta^{-a_v}x_v-1}F(G;(\zeta^{a_v}:v\in V)\,),\end{align*}
 where the summations are over $(a_v:v\in
V)\in\{0,1,\ldots, q-1\}^V$ and the last line follows since $\prod_{a\neq a_v}(\zeta^{a_v}-\zeta^{a})=\zeta^{(q-1)a_v}\prod_{b\neq 0}(1-\zeta^b)=\zeta^{-a_v}q.$
The relationship between coefficients of the polynomial $F^{(q)}(G;\mathbf{x})$ and
its evaluations at points $(\zeta^{a_v}:v\in V)$ is exhibited here as
a basis change between the basis of monomials $\prod_{v\in
  V}x_v^{a_v}$ and the basis of polynomials $\prod_{v\in
  V}\frac{x_v^q-1}{\zeta^{-a_v}x_v-1}$. The connection is the Fourier transform. This article is
an elaboration of this remark.

Alon and Tarsi \cite{AT97} use the ``Combinatorial Nullstellensatz'' \cite{A99}
to prove that
$F^{(q)}(G;\mathbf{x})\neq 0$ if and only if
$P(G;q)>0$, and also show that more can be said.

For a polynomial
$F(\mathbf{x})\in\mathbb{C}[\mathbf{x}]/(x_v^q-1:v\in V)$, let
$[\mathbf{x}^\mathbf{a}]F(\mathbf{x})$ denote the coefficient of the
monomial $\mathbf{x}^{\mathbf{a}}=\prod_{v\in V}x_v^{a_v}$ in its
expansion to the monomial basis. In particular,
$[\mathbf{x}^\mathbf{0}]F(\mathbf{x})$ is the constant term of $F(\mathbf{x})$. The (squared) $\ell_2$-norm
$\|F(\mathbf{x})\|_2^2$ is defined by
$$\|F(\mathbf{x})\|_2^2=\sum_{\mathbf{a}\in\{0,1,\ldots,q-1\}^V}\big|[\mathbf{x}^\mathbf{a}]F(\mathbf{x})\big|^2.$$

That this is a norm includes the fact that
  $F^{(q)}(G;\mathbf{x})\neq 0$ if and only if
  $\|F^{(q)}(G;\mathbf{x})\|_2^2\neq 0$.

\begin{theorem}\label{thm: Alon Tarsi} {\rm  \cite{AT97}} For each $q\in\mathbb{N}$,
 $$\|F^{(q)}(G;\mathbf{x})\|_2^2=q^{-|V|}4^{|E|}\sum_{\mathbf{c}\in\{0,1,\ldots,
    q-1\}^V}\prod_{uv\in E}\sin^2\frac{\pi(c_v-c_u)}{q},$$
 the sum being over all vertex colourings of $G$ with colours
 $\{0,1,\ldots, q-1\}$. In particular,  for $q=3$ this is $3^{|E|-|V|}P(G;3)$.
\end{theorem}

For the next theorem we require a further definition. A {\em $(q,1)$-flow} of
$G$ is a partial orientation of $G$ with the property that at each
vertex the number of edges directed out of $v$ is congruent to the
number of edges directed into $v$ modulo $q$. (A partial orientation
is obtained when some edges of $G$ are assigned an orientation while
the other edges remain undirected.) By referring to the fixed
orientation $\overrightarrow{E}$ of $G$, it is possible to
use the equivalent definition as an assignment of values $(b_e:e\in
E)$ to the edges of $G$ with the properties that  $b_e\in\{0,1,-1\}$
and the net flow (incoming minus outgoing values) at each vertex is equal to
zero modulo $q$.

\begin{theorem}\label{thm: Tarsi} {\rm \cite{Tarsi}}
For each $q\in\mathbb{N}$,
 $$\|F^{(q)}(G;\mathbf{x})\|_2^2=(-1)^{|E|}\sum_{(q,1)\mbox{\rm \small -flows}\;
  \mathbf{b}}(-2)^{|E|-|\mathbf{b}|},$$
where
$|\mathbf{b}|=\#\{e\in E:b_e\neq 0\}$.
\end{theorem}

One aim of this article is to reveal the underlying relationship
between  Theorems \ref{thm: Alon Tarsi} and \ref{thm: Tarsi} in a more
general context. The other is to characterize those polynomials of the form
$$\prod_{(u,v)\in\overrightarrow{E}}\;\sum_{a,b\in\{0,1,\ldots,
  q-1\}}\;\;f(a,b)x_u^ax_v^b\hspace{1cm}\mbox{\rm
  mod}\, (x_v^q-1:v\in V)$$
whose $\ell_2$-norm is a Tutte-Grothendieck invariant (such as
$P(G;q)$). The graph polynomial is the case $f(1,0)=1, f(0,1)=-1$ and
$f(a,b)=0$ otherwise, and Theorem \ref{thm: Alon Tarsi} says that for
$q=3$ its $\ell_2$-norm is the Tutte-Grothendieck invariant $3^{|E|-|V|}P(G;3)$.

\section{Tutte-Grothendieck invariants}\label{sec: TG}

Let $G=(V,E)$ be a graph, loops and parallel edges permitted,  with
$k(G)$ components, rank $r(G)=|V|-k(G)$ and nullity $n(G)=|E|-r(G)$.

{\em Deleting} an edge $e\in E$ gives a graph $G\setminus e$ with one fewer
edge than $G$. {\em Contracting} $e$ gives a graph $G/e$ with one fewer vertex
and one fewer edge than $G$. Many graph parameters may be
recursively defined via contraction-deletion recurrences.

\begin{definition}
A function $F$ from (isomorphism classes of) graphs to $\mathbb{C}[\alpha,\beta,\gamma,x,y]$ is a {\em Tutte-Grothendieck
  invariant} if it satisfies, for each graph $G=(V,E)$ and any edge
$e\in E$,
\be\label{TG}F(G)=\begin{cases} \gamma^{|V|} & E=\emptyset,\\
 xF(G/e) & e \;\; \mbox{\rm a bridge,}\\
 yF(G\setminus e) & e \;\;\mbox{\rm a loop,}\\
 \alpha F(G/e)+\beta F(G\setminus e) & e \;\;\mbox{\rm not a bridge or loop.}\end{cases}
\ee
\end{definition}

See for example the accounts in
\cite{DW93, BB98, GR01} for an appreciation of the ubiquity of Tutte-Grothendieck
invariants.
For $A\subseteq E$, the subgraph $(V,A)$ is obtained from $G$ by
deleting edges not in $A$. Given $G=(V,E)$, the rank of the graph
$(V,A)$ is denoted by $r(A)$.
A Tutte-Grothendieck invariant is an evaluation of the {\em Tutte
  polynomial}, defined by
\be\label{eqn: Tutte}T(G;x,y)=\sum_{A\subseteq E}(x-1)^{r(E)-r(A)}(y-1)^{|A|-r(A)}.\ee
The Tutte polynomial is a rescaling of the Whitney rank polynomial of $G$
(for which see for example \cite{GR01}), a generating function for $(|A|,r(A))$ over all
subgraphs $(V,A)$ of $G$. The coefficients of the Tutte polynomial are
non-negative integers (see for example \cite{B94,BB98}), a fact while not evident from its definition in
equation \eqref{eqn: Tutte} is more readily seen in its alternative
formulation as a Tutte-Grothendieck invariant with $\alpha=\beta=\gamma=1$.

\begin{theorem}\label{thm: TG}
 If $F$ is a Tutte-Grothendieck invariant satisfying the equations
 \eqref{TG} then
$$F(G)=\gamma^{k(G)}\alpha^{r(G)}\beta^{n(G)}T(G;\frac{x}{\alpha},\frac{y}{\beta}).$$
\end{theorem}

See \cite{BB98} for how to interpret this evaluation for the case $\alpha=0$ or $\beta=0$.

\begin{example}\label{ex: monochrome} The {\em monochromial} $P(G)=P(G;q,y)$ (bad colouring
    polynomial, coboundary polynomial, partition function of the $q$-state Potts model) is defined by
\be\label{eqn: monochrome poly} P(G;q,y)=\sum_{\mathbf{c}\in
    Q^V}y^{\#\{(u,v)\in\overrightarrow{E}:c_u=c_v\}},\ee where $Q$ is
a set of $q$ colours (states) and $\mathbf{c}=(c_v:v\in V)$ is a
vertex colouring of $G$ using colours from $Q$.
It is easily verified that the function $P$ satisfies
$$P(G)=\begin{cases} q^{|V|} & E=\emptyset,\\
(y+q-1)P(G/e) & \mbox{\rm $e$ a bridge,}\\
yP(G\setminus e) & \mbox{\rm $e$ a loop,}\\
(y-1)P(G/e)+P(G\setminus e) & \mbox{\rm $e$ not a bridge or
  loop.}\end{cases}$$
By Theorem \ref{thm: TG},
\be\label{eqn: mono poly}P(G;q,y)=q^{k(G)}(y-1)^{r(G)}T(G;\frac{y\!-\!1\!+\!q}{y\!-\!1},y).\ee
In particular, the {\em chromatic polynomial} $P(G;q)$,
counting the number of proper vertex $q$-colourings of $G$, is given by
$$P(G;q)=q^{k(G)}(-1)^{r(G)}T(G;1-q,0).$$
\end{example}

Let $Q$ be a set of size $q$ (later in this article to be an additive Abelian group of order $q$) and
 $\mathbf{w}=(w_{a,b})$ a tuple of complex numbers indexed by
$(a,b)\in Q\times Q$. Assume that the edges $\{u,v\}$ of $G=(V,E)$ have been
given an arbitrary, fixed orientation $(u,v)$. Denote by
$\overrightarrow{E}$ the resulting set of directed edges. Consider the partition function for a vertex $Q$-colouring model that assigns a weight $w_{a,b}$ to a directed edge $(u,v)$ coloured $(a,b)$:
\begin{equation}\label{eqn: S}
F(G;\mathbf{w})=\sum_{\mathbf{c}\in Q^V}\prod_{(u,v)\in\overrightarrow{E}}w_{c_u,c_v}=\sum_{\mathbf{c}\in Q^V}\prod_{(a,b)\in Q\times Q}w_{a,b}^{\;\;\;\;\#\{(u,v)\in\overrightarrow{E}\,:\,(c_u,c_v)=(a,b)\}}.
\end{equation}
This partition function may be interpreted as the weight
of a graph homomorphism $G\rightarrow H$, where $H$ is the directed graph on
vertex set $Q$ and edge set $\{(a,b):w_{a,b}\neq 0\}$, with edge
weights $w_{a,b}$, i.e., the weighted graph $H$ has adjacency matrix $(w_{a,b})_{a,b\in Q}$.
(It is possible to also have vertex weights for $H$ in addition to its edge
weights, but this will not be considered here. See for example
\cite{FLS04, S05} and \cite{HN04, GNR07} for more on vertex
colouring models and on graph homomorphisms.)

\begin{theorem}\label{TG Hamming}
The graphical invariant $F(G;\mathbf{w})$ defined by equation \eqref{eqn: S} is a Tutte-Grothendieck invariant if and only if there are constants $y,w$ such that
$$w_{a,b}=\begin{cases} w & a\neq b,\\
 y & a=b.\end{cases}
$$
In this case $F(G;\mathbf{w})=F(G;w,y)=q^{k(G)}w^{n(G)}(y-w)^{r(G)}T(G;\frac{y-(q\!-\!1)w}{y-w},\frac{y}{w})$. (If $w=0$ then $F(G;0,y)=y^{|E|}$ and if $w=y$ then $F(G;y,y)=q^{|V|}y^{|E|}$.)
\end{theorem}

A sketch only of a proof of Theorem \ref{TG Hamming} is
given.\footnote{I am grateful to Delia Garijo for alerting me to the
  fact that I was assuming the truth of something that required
  proof, and also for her description of how she has been tackling a related,
  stronger result.}

(A fuller version will
appear in a forthcoming paper.) The
following lemma is the main tool.

\begin{lemma}\label{lemma: mth powers}
If $u_1,\ldots, u_r,v\in\mathbb{C}$ satisfy
\begin{equation}\label{eqn: all m} u_1^m+u_2^m+\cdots +u_r^m=rv^m,\ee
for all integers $m\geq 0$, then
$$u_1=u_2=\cdots =u_r=v.$$
\end{lemma}
\begin{proof}
We may assume $v\neq 0$. Rewriting the relation \eqref{eqn: all m} in terms of ordinary
generating functions,
$$(1-u_1z)^{-1}+(1-u_2z)^{-1}+\cdots + (1-u_rz)^{-1}=r(1-vz)^{-1},$$
for all $z\in\mathbb{C}$ such that
$$|z|<\min\{|u_i|^{-1}:1\leq i\leq r, \; u_i\neq 0\}\cup\{|v|^{-1}\}.$$
Multiplying out to clear fractions, this is to say that
$$\sum_{1\leq i\leq r}(1-vz)\prod_{j\neq i}(1-u_jz)=r\prod_{1\leq j\leq r}(1-u_jz).$$
Equating coefficients of $z^k$ in this polynomial of degree $r$
 in $z$ yields
$$\sum_{1\leq i\leq r}e_k(u_1,\ldots, u_{i-1},v,u_{i+1},\ldots,
u_r)=re_k(u_1,\ldots, u_r),$$
where $e_k$ is the $k$th elementary symmetric function. Cancelling
terms just involving the $u_i$ (which comprise altogether $r-k$ copies of
$e_k(u_1,\ldots, u_r)$ on the left-hand side of the equation:
each $k$-subset of $\{u_1,\ldots, u_r\}$ occurs in $r-k$ of the sets
$\{u_1,\ldots, u_{i-1},v,u_{i+1},\ldots, u_r\}$) and factoring
out the resulting common factor of $v$ (on the left-hand side of the equation, each $(k-1)$-subset of $\{u_1,\ldots, u_r\}$
occurs in $r-k+1$ terms),
$$(r-k+1)ve_{k-1}(u_1,\ldots, u_r)=ke_k(u_1,\ldots, u_r).$$
By this recursive formula we obtain
$$e_k(u_1,\ldots, u_r)=\frac{r-k+1}{k}ve_{k-1}=\binom{r}{k}v^k.$$
This implies that $u_1,\ldots, u_r$ are uniquely determined as the
roots of the polynomial $(z-v)^r$, i.e., $u_i=v$ for each $1\leq i\leq r$.
\end{proof}

\begin{proof} {\it (of Theorem \ref{TG Hamming}.)}  In one direction, given that $w_{a,b}=w$ for $a\neq b$
  and $w_{a,a}=y$, the evaluation of the Tutte polynomial follows from that of the
  monochromial given in equation \eqref{eqn: mono poly}
  in Example \ref{ex: monochrome} above with $x=y/w$.

In the other direction, suppose that there are constants
$\alpha,\beta,\gamma, x,y$ such that $F(G;\mathbf{w})=F(G)$ satisfies
the relations \eqref{TG} for a Tutte-Grothendieck invariant.
By checking that this is indeed the case for the three families of
graphs $X_m, Y_m, Z_m$ ($m\in\mathbb{N}$) itemized below
the desired conclusion is
reached. Each of these families of graphs
possess the following virtues:  (i) the graphs obtained by contracting
or deleting an edge are
of the same form or belong to one of the other families, and (ii) it is
possible to write down $F$ as given by the partition function
\eqref{eqn: S} as a succinct formula, thereupon to substitute this
formula into the contraction-deletion recurrence of \eqref{TG}, and
finally to avail oneself of Lemma
\ref{lemma: mth powers} (or a variant of this lemma).

For $m\in\mathbb{N}$ consider:
\begin{itemize}

\item[(i)] $Y_m$, the graph on one vertex with $m$ loops.
  $F(Y_1)=\sum_{a\in Q}w_{a,a}=qy$. The relation
  $F(Y_m)=yF(Y_{m-1})=qy^m$ is used to show that
  $w_{a,a}=y$ for each $a\in Q$.

\item[(ii a)] $X_m$, the graph on two vertices connected by $m$ parallel
  edges. $F(X_1)=\sum_{a,b\in Q}w_{a,b}=qx$. The relation
  $F(X_m)=\alpha F(Y_{m-1})+\beta F(X_{m-1})$ for $m\geq 2$ is used to show that $\{w_{a,b}:a,b\in Q\}$ contains
  at most two distinct values $y,w$: there is $S$ with
  $\{(a,a):a\in Q\}\subseteq S\subseteq Q\times Q$ such that $w_{a,b}=y$ for $(a,b)\in S$, and $w_{a,b}=w$ otherwise.

\item[(ii b)] $X_m^n$,
the graph $X_m$ with $n$ edges oriented in one direction, $m-n$ in the
other. That $F(X_m)$ is independent of any orientation of the edges of $X_m$
(giving a graph $X_m^n$) is used to show that $w_{a,b}=w_{b,a}$ for all $a,b\in Q$,
i.e., the set $S$ defined in (ii a) is closed under the involution $(a,b)\mapsto (b,a)$.

\item[(iii)] $Z_m$, the star graph with $m$ edges (one vertex degree $m$, and $m$
vertices degree $1$). The relation $F(Z_m)=xF(Z_{m-1})=qx^m$ is used to show that $\#\{b\in Q:(a,b)\in S\}$ is
independent of $a$, whereby it follows from (ii b) that either
$S=\{(a,a):a\in Q\}$ or $S=Q\times Q$.

\end{itemize}
\end{proof}

We now know how to recognize a Tutte-Grothendieck invariant. To aid
our search amongst graph polynomials of the sort defined in Section
\ref{sec: Petersen graph poly} we shall use instruments from Fourier
analysis, a subject to which we now turn.

\section{Fourier analysis on finite Abelian groups} \label{sec: Fourier}

\subsection{The algebra $\mathbb{C}^Q$}

Let $Q$ be an additive Abelian group of order $q$. In later sections
$Q=\mathbb{Z}_q$, the integers under addition modulo $q$.

The set $\mathbb{C}^Q$ of
functions $f:Q\rightarrow\mathbb{C}$ forms a $q$-dimensional Hermitian
inner product space. The inner product is defined by
$$\langle f,g\rangle=\sum_{a\in Q}f(a)\ol{g(a)},$$
the bar denoting complex conjugation.
The {\em $\ell_2$-norm} is defined by $\|f\|_2=\langle
f,f\rangle^{\frac12}$ and defines a metric on the space $\mathbb{C}^Q$.

The space $\mathbb{C}^Q$ has an orthonormal basis of {\em indicator functions}  $\{\delta_a:a\in Q\}$,
$$\delta_a(b)=\begin{cases} 1 & a=b,\\ 0 & a\neq b.\end{cases}$$

There are several definitions of
multiplication that make $\mathbb{C}^Q$ an algebra:
\begin{itemize}
\item[(i)] {\em Pointwise product}
$$f\cdot g(a)=f(a)g(a).$$
\item[(ii)] {\em Convolution}
$$f\ast g(a)=\sum_{b\in Q}f(a)g(b-a).$$
\item[(iii)] {\em Cross-correlation}
$$f\star g(a)=\sum_{b\in Q}\ol{f(a)}g(b+a).$$
\end{itemize}
The effect of these operations on the indicator functions is
as follows:
 $$\delta_a\cdot\delta_b=\delta_a(b)\delta_a,\hspace{1cm}\delta_a\ast\delta_b=\delta_{a+b},\hspace{1cm}\delta_a\star\delta_b=\delta_{b-a}.$$

The Abelian group $Q$ has {\em dual group} equal to the set of {\em
  characters} of $Q$ under pointwise multiplication. For each $c\in
Q$, the character
$\chi_c: Q\rightarrow\mathbb{C}^\times$ is a group homomorphism:
$\chi_c(a+b)=\chi_c(a)\chi_c(b)$ for
all $a,b\in Q$.
The multiplicative group of characters of $Q$ is isomorphic to the
additive group $Q$.
(This is only true when $Q$ is a finite Abelian group, and, for
 the applications later in this article, is the reason why only finite Abelian groups are considered.)

The set $\{\chi_c:c\in Q\}$ forms an orthogonal basis for
$\mathbb{C}^Q$, with $\langle\chi_a,\chi_b\rangle=q\delta_a(b)$.

In the algebra $\mathbb{C}^Q$,
$$\chi_a\cdot\chi_b=\chi_{a+b},\hspace{1cm}\chi_a\ast\chi_b=q\delta_a(b)\chi_a=\chi_{a}\star\chi_b.$$

Supposing the additive group $Q$ has the further structure of a ring
(such as $\mathbb{Z}_q$ with addition and multiplication modulo $q$),
a {\em generating character} $\chi$ satisfies $\chi_a(b)=\chi(ab)$ for
all $a,b\in Q$.
When $Q=\mathbb{Z}_q$, the character $\chi$ defined by
$\chi(a)=e^{2\pi ia/q}$ (or $e^{2\pi i ca/q}$ for any fixed $c$
coprime with $q$) is a generating character.

\subsection{The Fourier transform}

The evaluation of the Fourier transform of a function at a point is
the projection of the function onto a character:
$$\wh{f}(b)=\langle f,\chi_b\rangle=\sum_{a\in Q}f(a)\chi_b(-a),$$
i.e., $$\wh{f}=\sum_{b\in Q}f(b)\chi_{-b}.$$
Orthogonality of the basis $\{\chi_c:c\in Q\}$ yields:

\begin{itemize}

\item[(i)] the Fourier inversion formula,

$$f(a)=q^{-1}\langle\wh{f},\chi_{-a}\rangle=q^{-1}\sum_{b\in Q}\wh{f}(b)\chi_b(a),$$
i.e., the Fourier transform may be regarded as a change of basis from
indicators to characters:
$$f=\sum_{a\in Q} f(a)\delta_a=q^{-1}\sum_{b\in Q}\wh{f}(b)\chi_b.$$

\item[(ii)] Plancherel's formula,
 $$\langle \wh{f},\wh{g}\rangle=q\langle f,g\rangle.$$

\item[(iii)] Parseval's formula,
 $$\|f\|_2^2=q^{-1}\|\wh{f}\|_2^2.$$
Thus the normalized Fourier transform $f\mapsto q^{-\frac12}\wh{f}$ is
  a unitary transformation, giving an isometry of the metric space
  $\mathbb{C}^Q$.
\end{itemize}

The Fourier transform is an isomorphism of the algebra
$(\mathbb{C}^Q,\ast)$ with the algebra $(\mathbb{C}^Q,\cdot)$:
\be\label{eqn: point to conv}\wh{f\cdot g}=q^{-1}\wh{f}\ast\wh{g},\hspace{1cm}\wh{f\ast g}=\wh{f}\cdot\wh{g},\hspace{1cm}\wh{f\star g}=\ol{\wh{f}}\cdot\wh{g},\ee
and in particular
 $$\wh{f\star f}=|\wh{f}|^2$$
(the finite version of the Wiener-Khintchine formula).
That the Fourier transform is an isometry carrying convolution to pointwise
multiplication makes it useful in the analysis of random walks on
Cayley graphs on $Q$, where steps on the graph correspond to addition
of group elements -- see for example \cite{Terras99} and
the references therein.
To prove the formulae in \eqref{eqn: point to conv} it suffices to
determine the effect of the Fourier transform on basis
functions and then appeal to linearity and distributivity. For
example, $\wh{\delta_a\star\delta_b}=\wh{\delta_{b-a}}=\chi_{a-b}=\ol{\wh{\delta_a}}\cdot\wh{\delta_b}.$\smallskip

For an additive subgroup $P$ of $Q$, the {\em annihilator} of $P$ is defined by
$$P^\sharp=\{b\in Q:\forall_{a\in P}\; \chi_b(a)=1\}.$$
and is isomorphic to the quotient group $Q/P$.

Extend the indicator function notation from elements to subsets
$P\subseteq Q$
by setting $\delta_P=\sum_{a\in P}\delta_a$.

For our purposes, a key property of the Fourier transform is
that
 $$\wh{\delta_P}=|P|\delta_{P^\sharp}.$$

By Fourier inversion,
$$\delta_P\star f(b)=q^{-1}\langle\wh{\delta_P}\cdot\wh{f},\chi_{-b}\rangle,$$ giving the
{\em Poisson summation formula}
 $$\sum_{a\in P}f(a+b)=|P^\sharp|^{-1}\sum_{a\in P^\sharp}\wh{f}(a)\chi_b(a).$$

\subsection{The algebra $\mathbb{C}^{Q^n}$ and the polynomial ring
  $\mathbb{C}[\mathbf{x}]/(x_i^q-1:1\leq i\leq n)$}
In this section we assume that the Abelian group $Q$
has the further structure of a commutative ring. Let $\mathbf{Q}=Q^n$ denote the $n$-fold direct product of $Q$, which is an
Abelian group of order $q^n$ and a module over $Q$. Put a ring structure on $Q^n$ by defining
componentwise multiplication of  $\mathbf{a}=(a_1,\ldots, a_n)$, $\mathbf{b}=(b_1,\ldots, b_n)\in Q^n$,
$$\mathbf{a}\mathbf{b}=(a_1b_1,\ldots, a_nb_n).$$
The Hermitian inner product space $\mathbb{C}^{Q^n}$ is the $n$-fold
tensor product of $\mathbb{C}^Q$: given $f_1,\ldots,
f_n\in\mathbb{C}^Q$ define
 $$f_1\otimes\cdots \otimes f_n(a_1,\ldots, a_n)=f_1(a_1)\cdots f_n(a_n),$$
and in particular $f^{\otimes n}(\mathbf{a})=f(a_1)\cdots f(a_n).$

The characters of $Q^n$ are the functions defined by
$\chi_{\mathbf{a}}=\chi_{a_1}\otimes \cdots\otimes\chi_{a_n}.$

Define the Euclidean (dot) product by
$$\mathbf{a}\cdot\mathbf{b}=a_1b_1+\cdots +a_nb_n.$$
If $\chi$ a generating character for $Q$, then
$\chi^{\otimes n}$ is a generating character for $Q^n$:
$$\chi_{\mathbf{a}}(\mathbf{b})=\chi^{\otimes n}(\mathbf{a}\mathbf{b})=\chi(a_1b_1)\cdots\chi(a_nb_n)=\chi(\mathbf{a}\cdot\mathbf{b}).$$
 Given that $Q$ has a generating character,
 for a submodule $\mathbf{P}$ of $Q^n$ the annihilator
$$\mathbf{P}^\sharp=\{\mathbf{b}\in Q^n:\forall_{\mathbf{a}\in \mathbf{P}}\hspace{0.3cm}\chi_{\mathbf{a}}(\mathbf{b})=1\}$$
is equal to the {\em orthogonal} submodule
$$\mathbf{P}^\perp=\{\mathbf{b}\in Q^n:\forall_{\mathbf{a}\in\mathbf{P}}\hspace{0.3cm}\mathbf{a}\cdot\mathbf{b}=0\}.$$

The Fourier transform on $Q^n$ is given by
$$\wh{f_1\otimes\cdots\otimes f_n}=\wh{f_1}\otimes\cdots\otimes\wh{f_n},$$
and in particular $\wh{f^{\otimes n}}=\wh{f}^{\otimes n}.$

It may be helpful to spell
out the relationship between polynomials in the ring
$\mathbb{C}[\mathbf{x}]/(x_i^q-1:1\leq i\leq n)$ (where
$\mathbf{x}=(x_i:1\leq i\leq n)$ is an $n$-tuple of commuting
indeterminates) and functions in the space
$\mathbb{C}^{\mathbb{Z}_q^n}$. The aim of course is to translate
statements about the reduced graph polynomial $F^{(q)}(G;\mathbf{x})$, which
belongs to $\mathbb{C}[\mathbf{x}]/(x_v^q-1:v\in V)$, into statements
about functions in $\mathbb{C}^{\mathbb{Z}_q^V}$. The latter space has now
the advantage of familiarity and the accoutrements of a succinct
notation.

Take
$Q=\mathbb{Z}_q$, which has generating character $\chi(a)=\zeta^{a}$ for
 primitive $q$th root of unity $\zeta$.

The algebra $\mathbb{C}^{\mathbb{Z}_q^n}$ is isomorphic to
$\mathbb{C}[\mathbf{x}]/(x_i^q-1:1\leq i\leq n)$ and the
following correspondences obtain:
$$\delta_{\mathbf{a}}=\delta_{a_1}\otimes\cdots\otimes
\delta_{a_n}\hspace{1cm}\mbox{with}\hspace{1cm}\mathbf{x}^{\mathbf{a}}=\prod_{1\leq
  i\leq n}x_i^{a_i},$$
$$\chi_{\mathbf{a}}=\chi_{a_1}\otimes\cdots\otimes\chi_{a_n}\hspace{1cm}\mbox{with}\hspace{1cm}\prod_{1\leq
  i\leq n}\frac{x_i^q-1}{\zeta^{-a_i}x_i-1},$$
$$\mathbf{f}=\sum_{\mathbf{a}\in\mathbb{Z}_q^n}\mathbf{f}(\mathbf{a})\delta_{\mathbf{a}}\hspace{1cm}\mbox{with}\hspace{1cm}F(\mathbf{x})=\sum_{\mathbf{a}\in
  \mathbb{Z}_q^n}\mathbf{f}(\mathbf{a})\mathbf{x}^{\mathbf{a}}.$$
Finally, $$F(\zeta^{a_1},\ldots,
\zeta^{a_n})=\wh{\mathbf{f}}(\mathbf{a}),$$
and Lagrange interpolation on points $\{(\zeta^{a_1},\ldots,
\zeta^{a_n}):(a_1,\ldots,a_n)\in\mathbb{Z}_q^n\}$ is the Fourier basis change:
$$\sum_{\mathbf{a}\in \mathbb{Z}_q^n}\mathbf{f}(\mathbf{a})\mathbf{x}^{\mathbf{a}}=q^{-n}\sum_{\mathbf{a}\in\mathbb{Z}_q^n}\wh{f}(\mathbf{a})\prod_{i=1}^n\frac{x_i^q-1}{\zeta^{-a_i}x_i-1}.$$

\subsection{Weight enumerators and the Tutte polynomial}\label{sec: we}

We finish this section on Fourier analysis with a discussion of the
Tutte polynomial as a weight enumerator that gives us the opportunity
at the same time to define {\em
  flows} and {\em tensions} of a graph, which definitions are needed
for the next section.

It will be convenient to extend the domain of a function $\mathbf{f}$
on elements $\mathbf{a}\in Q^n$ to subsets $\mathbf{P}\subseteq Q^n$, setting
$$\mathbf{f}(\mathbf{P})=\sum_{\mathbf{a}\in\mathbf{P}}\mathbf{f}(\mathbf{a}).$$
The {\em Hamming weight}  of $\mathbf{a}=(a_1,\ldots, a_n)$ is
$|\mathbf{a}|=\#\{i:a_i\neq 0\}.$
The {\em Hamming weight enumerator} of $\mathbf{P}$ is defined to be the
the generating function for vectors in $\mathbf{P}$ counted according to their number of zero entries:
$$\sum_{\mathbf{a}\in\mathbf{P}}x^{n-|\mathbf{a}|}=(x\delta_0+\delta_{Q\setminus
  0})^{\otimes n}(\mathbf{P}).$$
The {\em complete weight enumerator} of $\mathbf{P}$ keeps account of the
number of entries equal to a given element of $Q$:
$$\sum_{\mathbf{a}\in\mathbf{P}}\prod_{a\in Q}x_a^{\#\{1\leq i\leq
  n:a_i=a\}}=\big(\sum_{a\in Q}x_a\delta_a\big)^{\otimes E}(\mathbf{P}).$$
The Hamming weight enumerator is the specialization $x_0=x$ and
$x_a=1$ for $0\neq a\in Q$.

For a submodule $\mathbf{P}$ of $Q^n$,
$$\wh{\delta_{\mathbf{P}}}=|\mathbf{P}|\delta_{\mathbf{P}^\perp}.$$
The Poisson summation formula
$$\mathit{\mathbf{f}}(\mathbf{P}+\mathbf{b})=\frac{1}{|\mathbf{P}^\perp|}\wh{\mathbf{f}}\cdot\chi_{\mathbf{b}}(\mathbf{P}^\perp),$$
with $\mathbf{b}=\mathbf{0}$ and $\mathbf{f}=f^{\otimes n}$ gives the
duality formula between the complete weight enumerator
of $\mathbf{P}$ (with $x_a=f(a)$) and the complete weight enumerator
of $\mathbf{P}^\perp$ (with $x_a=\wh{f}(a)$). When
$f=x\delta_0+\delta_{Q\setminus 0}$ it yields the MacWilliams duality formula for Hamming weight enumerators.

Recall that the graph $G=(V,E)$ has a fixed orientation of its edges,
with directed edge set denoted by $\overrightarrow{E}$. Represent this
ground orientation as a matrix $\gamma$ indexed by $V\times E$,
setting
$$\gamma_{v,e}=\begin{cases} +1 & \mbox{\rm if $e=(u,v)$ in $\overrightarrow{E}$,}\\
  -1 & \mbox{\rm if $e=(v,u)$ in $\overrightarrow{E}$,}\\
0 &  \mbox{\rm if $e$ is not incident with $v$.}\end{cases}$$
A {\em $Q$-tension} of $G$ is a vector $\mathbf{a}\in Q^E$ comprising the differences between endpoints
in a vertex colouring $\mathbf{c}\in Q^V$, i.e., if
$e=(u,v)$ then the $Q$-tension $\mathbf{a}$ associated with
$\mathbf{c}$ is defined by
$$a_e=\sum_{v\in V}\gamma_{v,e}c_v=c_v-c_u.$$
A {\em $Q$-flow} of $G$ is a vector $\mathbf{b}\in Q^E$ such that, for
each vertex $v$,
$$\sum_{e\in E}\gamma_{v,e}b_e=0.$$

When $G$ is planar, $Q$-flows of $G$ correspond to $Q$-tensions of the planar dual graph $G^*$. In particular, when $Q=\mathbb{F}_2$, the $\mathbb{F}_2$-flows of $G$ (cycles/ Eulerian subgraphs) correspond to $\mathbb{F}_2$-tensions (cutsets) of $G^*$.

A {\em nowhere-zero} $Q$-tension is one that takes only non-zero values, and arises from a proper vertex
$Q$-colouring; similarly, a nowhere-zero $Q$-flow is a flow takes
non-zero values only
(and for plane graphs corresponds to a proper face $Q$-colouring of
the embedded graph).

If $\mathbf{P}$ is the set of $Q$-tensions of $G$ (of which there are
$q^{r(G)}$) then $\mathbf{P}^\perp$ is the set of
$Q$-flows of $G$ (of which there are $q^{n(G)}$).
With this notation, the monochromial is given by
$$\sum_{\mathbf{c}\in
  Q^V}y^{\#\{(u,v)\in\overrightarrow{E}:c_u=c_v\}}=q^{k(G)}\sum_{\mathbf{a}\in\mathbf{P}}y^{|E|-|\mathbf{a}|},$$
since there are $q^{k(G)}$ vertex $Q$-colourings yielding any given $Q$-tension. Consequently, by Example \ref{ex: monochrome}, the Hamming weight enumerator of the set $\mathbf{P}$
of $Q$-tensions of $G$ is a specialization of the Tutte polynomial:
$$\sum_{\mathbf{a}\in\mathbf{P}}y^{|E|-|\mathbf{a}|}=(y-1)^{r(G)}T(G;\frac{y-1+q}{y-1},y).$$

By the Poisson summation formula (MacWilliams duality),
$$(y\delta_0+\delta_{Q\setminus 0})^{\otimes E}(\mathbf{P})=q^{-n(G)}[(y-\!1+\!q)\delta_0+(y-\!1)\delta_{Q\setminus
    0}]^{\otimes E}(\mathbf{P}^\perp).$$
Putting $x=\frac{y-\!1+\!q}{y-\!1}$, the Hamming weight enumerator of
the set $\mathbf{P}^\perp$ of $Q$-flows of $G$ is given by
 $$\sum_{\mathbf{b}\in\mathbf{P}^\perp}x^{|E|-|\mathbf{b}|}=(x-1)^{n(G)}T(G;x,\frac{x-1+q}{x-1}).$$

A corollary of Theorem \ref{TG Hamming} is that if an evaluation of the complete weight
enumerator of $Q$-tensions (or $Q$-flows) is a Tutte-Grothendieck
invariant (an evaluation of the
Tutte polynomial with a certain simple type of prefactor)
then it is in fact an evaluation of the Hamming weight
enumerator.
In fact, the proof of Theorem \ref{TG Hamming} says the same is true
of any class of graphs that contains multiple loops on one vertex,
multiple parallel
edges between two vertices, and stars whose central vertex is of
arbitrary degree. This notably includes the
class of planar graphs.

There are nevertheless (infinite) classes of graphs for which an
evaluation of the complete weight enumerator of $Q$-tensions of $G$
coincides with the value of a Tutte-Grothendieck invariant and yet is not an evaluation of the
Hamming weight enumerator.

For example, if $G=(V,E)$ is the line graph of a plane cubic
graph then a result ultimately due to Penrose \cite{P71} (but see \cite{EG96} for
a full account) is that
$$\sum_{\mathbf{c}\in\mathbb{Z}_3^V}0^{\#\{(u,v)\in\overrightarrow{E}:
  c_u=c_v\}}(-1)^{\#\{(u,v)\in
  \overrightarrow{E}:c_v-c_u=-1\}}=(-1)^{|V|}P(G;3),$$
i.e., the complete weight enumerator of $\mathbb{Z}_3$-tensions of $G$
with $x_0=0, x_1=1, x_{-1}=-1$ is an evaluation of the Tutte
polynomial. However, since the class of line graphs of plane cubic
graphs is not
closed under deletion or contraction, one is prevented from calling this a
Tutte-Grothendieck invariant.

\section{Polynomials akin to the graph polynomial}\label{sec: graph polynomials}

 Suppose $F^{(q)}(G;\mathbf{x})\in\mathbb{C}[\mathbf{x}]/(x_v^q-1:v\in V)$ is a graph polynomial of the general
 form
\begin{align*}F^{(q)}(G;\mathbf{x}) & = \prod_{(u,v)\in\overrightarrow{E}}\sum_{(a,b)\in
  \mathbb{Z}_q^2}f(a,b)x_u^ax_v^b\\
 & =\sum_{\mathbf{c}\in (\mathbb{Z}_q^2)^E}f^{\otimes
  E}(\mathbf{c})\prod_{(u,v)\in \overrightarrow{E}}x_u^{c_{u,e}}x_v^{c_{v,e}},\end{align*}
where $\mathbf{c}=(c_e:e\in E)$, $c_e=(c_{u,e},c_{v,e})$ for edge $e$
directed as $(u,v)$ in $\overrightarrow{E}$, and
$f^{\otimes E}(\mathbf{c})=\bigotimes_{e\in E}f(c_{u,e},c_{v,e}).$
The graph polynomial of Petersen et al. introduced in Section
\ref{sec: Petersen graph poly} is the case $f(1,0)=1,
f(0,1)=-1$ and $f(a,b)=0$ otherwise. (Henceforth the name ``Petersen's
   graph polynomial'' will be used when it needs to be distinguished.)

In this section we address the following questions:

\begin{itemize}

\item[(A)] When is the partition function  of the vertex colouring (states) model\,\footnote{ The vertex colouring model assigns weight $F^{(q)}(G;(\zeta^{d_v}:v\in V)\,)$ to a given vertex colouring $\mathbf{d}\in\mathbb{Z}_q^V$. In terms of graph homomorphisms, this vertex colouring model corresponds to considering $\mathbf{d}$ as a homomorphism from $G$ to a weighted directed graph $H$ on vertex set $\mathbb{Z}_q$, with an edge $(c,d)$ having weight
$$\sum_{a,b}f(a,b)\zeta^{ac+bd}=\wh{f}(c,d).$$
The total weight of the homomorphism $\mathbf{d}: G\rightarrow H$ is
the product of all the weights on $(d_u,d_v)$ for edges $(u,v)$ of
$G$, i.e., $\wh{f}^{\otimes E}(\mathbf{c})$ where
$\mathbf{c}\in(\mathbb{Z}_q^2)^E$ is defined by $(c_{u,e},
c_{v,e})=(d_u,d_v)$. The partition function in question~(A) is a sum over all
homomorphisms [$\mathbf{d}$, encoded by $\mathbf{c}\in(\mathbb{Z}_q^2)^E$] weighted in this way.}
$$\sum_{\mathbf{d}\in \mathbb{Z}_q^V}F^{(q)}(G;(\zeta^{d_v}:v\in V)\,)=q^{|V|}[\mathbf{x}^{\mathbf{0}}]F^{(q)}(G;\mathbf{x})$$
a Tutte-Grothendieck invariant (an evaluation of the Tutte polynomial)?

\item[(B)] When is the squared
$\ell_2$-norm
$$\|F^{(q)}(G;\mathbf{x})\|_2^2=\sum_{\mathbf{a}\in\mathbb{Z}_q^V}\left|[\mathbf{x}^{\mathbf{a}}]F^{(q)}(G;\mathbf{x})\right|^2$$
a Tutte-Grothendieck invariant?

\item[(C)] What are the equivalents of Theorems \ref{thm: Alon Tarsi} and \ref{thm: Tarsi} in this more general case?
\end{itemize}

By Parseval's formula,
$$\|F^{(q)}(G;\mathbf{x})\|_2^2 = q^{-|V|}\sum_{\mathbf{d}\in\mathbb{Z}_q^V}|F^{(q)}(\zeta^{d_v}:v\in V)|^2,$$
where, writing $\mathbf{c}$ for the vector with entries $(c_{u,e},c_{v,e})=(d_u,d_v)$,
$$|F^{(q)}(G;\zeta^{d_v}:v\in V)|^2= |\wh{f}^{\,\otimes E}(\mathbf{c})|^2.$$
Since $|\wh{f}|^2=\wh{f\star f}$, this implies that the $\ell_2$-norm
of $F^{(q)}(G;\mathbf{x})$ is equal to the constant term of the polynomial
$\wt{F}^{(q)}(G;\mathbf{x})$ in $\mathbb{C}[\mathbf{x}]/(x_v^q-1:v\in V)$ defined by
$$\wt{F}^{(q)}(G;\mathbf{x})=\prod_{(u,v)\in\overrightarrow{E}}f\star
f(a,b)x_u^ax_v^b.$$

For example, the $\ell_2$-norm of Petersen's graph polynomial
$$F^{(q)}(G;\mathbf{x})=\prod_{(u,v)\in\overrightarrow{E}}(x_u-x_v)\;\;\bmod
(x_v^q-1:v\in V)$$
is the constant term of the polynomial
\begin{align*}
|F^{(q)}(G;\mathbf{x})|^2 & =\prod|x_u-x_v|^2=\prod
(x_u-x_v)(x_u^{-1}-x_v^{-1}),\\
& = \prod (2-x_ux_v^{-1}-x_u^{-1}x_v)\;\;\bmod
(x_v^q-1:v\in V).\end{align*}
[This calculation uses the correspondence of the ideal $(x_v^q-1:v\in V)$ with the
algebraic variety of points $(\zeta^{d_v}:v\in V)$, i.e.,
indeterminates $x_v$ are roots of unity, for which complex
conjugates are the same as multiplicative inverses.]

Let $M=\{(a,a):a\in Q\}$ be the submodule of $Q\times Q$ comprising
monochromatic pairs. The orthogonal submodule is $M^\perp=\{(a,-a):a\in Q\}$.
By Theorem \ref{TG Hamming}, $[\mathbf{x}^\mathbf{0}]F^{(q)}(G;\mathbf{x})$ is a
Tutte-Grothendieck invariant if and only if there are constants $y,w$
such that $\wh{f}=y\delta_M+w\delta_{Q\times Q\setminus M}$. By the above
remarks, $\|F^{(q)}(G;\mathbf{x})\|_2^2$ is a Tutte-Grothendieck invariant
if and only if
$$\wh{f\star f}=y\delta_{M}+w\delta_{Q\times Q\setminus M}.$$
By Fourier inversion,
this is the case if and only if $f\star f=(y+(q-1)w)\delta_0+(y-w)\delta_{M^\perp\setminus 0}$.

\begin{proposition} \label{prop: constant} The
constant term of $F^{(q)}(G;\mathbf{x})$ is a Tutte-Grothendieck
invariant if and only if
$$F^{(q)}(G;\mathbf{x})=\prod_{(u,v)\in\overrightarrow{E}}\big[
  y+(q-1)w+(y-w)(x_u^{q-1}x_v+\cdots + x_ux_v^{q-1})\big]\bmod(x_v^q-1:v\in
V),$$
in which case
$$[\mathbf{x}^\mathbf{0}]F^{(q)}(G;\mathbf{x})=(qw)^{n(G)}(y-w)^{r(G)}T(G;\frac{y-(q-1)w}{y-w},\frac{y}{w}).$$
\end{proposition}
For example, when $y=0, w=1$ and $q=3$ this says that
$$\prod_{(u,v)\in\overrightarrow{E}}(2-x_ux_v^{2}-x_u^{2}x_v)\bmod(x_v^3-1:v\in V)$$
has constant term $3^{n(G)}(-1)^{r(G)}T(G;-2,0)=3^{|E|-|V|}P(G;3)$.

That the constant term of the polynomial defined in Proposition \ref{prop: constant} is a Tutte
polynomial evaluation can be seen by inspection since,
for $a,b\in\mathbb{Z}_q$,
$$\zeta^{(q-1)a+b}+\zeta^{(q-2)a+2b}+\cdots +\zeta^{a+(q-1)b}=\begin{cases} -1 & a\neq b\\
 q-1 & a=b,\end{cases}$$
so that in this case
\begin{align*}
q^{|V|}[\mathbf{x}^{\mathbf{0}}]F^{(q)}(G;\mathbf{x}) &
  =\sum_{\mathbf{a}\in\mathbb{Z}_q^V}F^{(q)}(G;(\zeta^{a_v}:v\in
  V)\,)\\
& =
  \sum_{\mathbf{c}\in\mathbb{Z}_q^V}(qy)^{\#\{(u,v)\in\overrightarrow{E}:c_u=c_v\}}(qw)^{\#\{(u,v)\in\overrightarrow{E}:c_u\neq
    c_v\}}.\end{align*}

Whereas Proposition \ref{prop: constant} limits the graph polynomials which have
constant term equal to an evaluation of the Tutte polynomial to a
single family -- giving a rather dull answer to question~(A) above -- the possible choices for $f$ defining
$F^{(q)}(G;\mathbf{x})$ so that the $\ell_2$-norm $\|F^{(q)}(G;\mathbf{x})\|_2^2$ is a
Tutte-Grothendieck invariant are unlimited -- making the answer to
question~(B) potentially equally as dull.
The criterion $|\wh{f}|^2=y\delta_M+w\delta_{Q\times Q\setminus M}$
[or $f\star f=(y+(q-1)w)\delta_0+(y-w)\delta_{M^\perp\setminus 0}$]
can be satisfied by taking $\wh{f}=\sum_{a\in  Q}z_{a,b}\delta_{(a,b)}$ for any complex numbers $z_{a,b}$ that
satisfy $|z_{a,a}|^2=y$ if $a=b$ and $|z_{a,b}|^2=w$ otherwise.

Nonetheless, it seems worth describing a family of polynomials which
contains Petersen's graph polynomial as a special case and in some sense naturally
generalizes it.  In this family it is also possible to give a
meaningful answer to question (C) asking for equivalents to
Theorems \ref{thm: Alon Tarsi} and \ref{thm: Tarsi}.

\subsection{A family of polynomials containing the graph polynomial}

 Suppose that supp$(f)\subseteq\{(a,b):a+sb=t\}$ for some constants
$s,t\in\mathbb{Z}_q$. Then
\begin{align*}
F^{(q)}(G;(\zeta^{d_v}:v\in
V)\,) & =\prod_{(u,v)\in\overrightarrow{E}}\sum_{(a,b)\in
  \mathbb{Z}_q^2}f(a,b)\zeta^{ad_u+bd_v}\\
 & =\sum_{\mathbf{c}\in(\mathbb{Z}_q^2)^E}f^{\otimes
  E}(\mathbf{c})\prod_{(u,v)\in\overrightarrow{E}}\zeta^{c_{u,e}d_u+c_{v,e}d_v}.\end{align*}
The equation $f(a,b)=f(t-sb,b)=:g(b)$ defines $g\in\mathbb{C}^{\mathbb{Z}_q}$ and
 the sum over
$\mathbf{c}\in(\mathbb{Z}_q^2)^E$ can be rewritten as a sum over $\mathbf{b}\in\mathbb{Z}_q^E$.
In particular,  $s=1$ when the polynomial $\sum_{a,b}f(a,b)x_u^ax_v^b$ is homogeneous.

Given that $a_e+sb_e=t$, we have
$a_{e}d_u+b_ed_v=(t-sb_e)d_u+b_ed_v=b_e(d_v-sd_u)+td_u.$
For $e=(u,v)\in\overrightarrow{E}$, define $S:\mathbb{Z}_q^V\rightarrow\mathbb{Z}_q^E$  by
$$(S\mathbf{d})_e=d_v-sd_u$$ and $T:\mathbb{Z}_q^V\rightarrow\mathbb{Z}_q^E$ by $$(T\mathbf{d})_e=td_u.$$

For $\mathbf{b}\in\mathbb{Z}_q^E$, the transpose $S^\top$ is given by
$$(S^\top\mathbf{b})_v=\sum_{e=(u,v)\in\overrightarrow{E}}b_e\;-\hspace{0.5cm}s\sum_{e=(v,u)\in\overrightarrow{E}}b_e$$
and $$(T^\top\mathbf{b})_v=t\sum_{e=(v,u)\in\overrightarrow{E}}b_e.$$
When $s=1$ (which is the case for Petersen's graph
polynomial) the linear transformation $S$ is the {\em coboundary} and $S^\top$ the
{\em boundary}. Here the submodule $\ker(S^\top)$ comprises the
 $\mathbb{Z}_q$-flows of $G$ and im$(S)$ the  $\mathbb{Z}_q$-tensions
of $G$.

We have
\begin{align*}F^{(q)}(G;\mathbf{x}) & =
  \prod_{(u,v)\in\overrightarrow{E}}\;\;\sum_{b\in\mathbb{Z}_q}g(b)x_u^{t-sb}x_v^b\\
 & =\sum_{\mathbf{b}\in\mathbb{Z}_q^E}\prod_{e=(u,v)\in \overrightarrow{E}}g(b_e)x_u^{t-sb_e}x_v^{b_e}\\
& = \sum_{\mathbf{b}\in\mathbb{Z}_q^E}g^{\otimes
    E}(\mathbf{b})\prod_{v\in
    V}x_v^{S^\top\mathbf{b}+T^\top\mathbf{1}},\end{align*}
where $\mathbf{1}$ is the all-one vector in
$\mathbb{Z}_q^V$. ($T^\top\mathbf{1}$ is $t$ times the outdegree score
of $\overrightarrow{E}$.) \smallskip

The following theorem provides an answer to the question~(A) posed in the
previous section, and more.

\begin{theorem}
If $S^\top\mathbf{b}=\mathbf{a}-T^\top\mathbf{1}$ then
 $$[\mathbf{x}^{\mathbf{a}}]F^{(q)}(G;\mathbf{x}) = g^{\otimes
  E}(\ker(S^\top)+\mathbf{b}),$$
a complete coset weight enumerator of $\ker(S^\top)$.

In particular,  the coefficient
$[\mathbf{x}^{T^\top\mathbf{1}}]F^{(q)}(G;\mathbf{x})$ is an evaluation of the
 complete weight
  enumerator of $\ker(S^\top)$ (and of im$(S)$).
\end{theorem}
For example, in Petersen's graph polynomial, where $g=\delta_0-\delta_1$,
$$[\mathbf{x}^{T^\top\mathbf{1}}]\prod_{(u,v)\in\overrightarrow{E}}(x_u-x_v)\bmod(x_v^q-1:v\in
V) = \sum_{(q,1)\mbox{\rm \small -flows } \, \mathbf{b}}0^{\#\{e\in
  E:b_e=-1\}}(-1)^{\#\{e\in E:b_e=1\}},$$
where a $(q,1)$-flow is a $\mathbb{Z}_q$-flow taking values only in
$\{0,1,-1\}$ (and here the sum need only range over those taking
values in $\{0,1\}$).

When $s=1$ (for which $S$ is the coboundary, ${\rm im}(S)$ the set of
$\mathbb{Z}_q$-tensions, $\ker(S^\top)$ the set of
$\mathbb{Z}_q$-flows) and
$$F^{(q)}(G;\mathbf{x})=\prod_{(u,v)\in\overrightarrow{E}}\;\sum_{b\in\mathbb{Z}_q}g(b)x_u^{t-b}x_v^b,$$
 the coefficient
$[\mathbf{x}^{T^\top\mathbf{1}}]F^{(q)}(G;\mathbf{x})$ is an evaluation of the Tutte
polynomial if and only if $g=x\delta_0+\delta_{\mathbb{Z}_q\setminus
  0}$ (by Theorem \ref{TG Hamming}; this is the case covered by
Proposition \ref{prop: constant}). If $g$
does not take this form then the coefficient
$[\mathbf{x}^{T^\top\mathbf{1}}]\ol{F}(\mathbf{x})$ is not an
evaluation of the Hamming
weight enumerator of $\mathbb{Z}_q$-flows but of some other
specialization of the complete weight enumerator. \medskip

To find the $\ell_2$-norm, observe that, for $\mathbf{d}\in\mathbb{Z}_q^V$,
\begin{align*}
  F^{(q)}(G;(\zeta^{d_v}:v\in
V)\,) & = \sum_{\mathbf{b}\in\mathbb{Z}_q^E}g^{\otimes
  E}(\mathbf{b})\zeta^{(S^\top\mathbf{b})\cdot \mathbf{d}+T^\top\mathbf{1}\cdot\mathbf{d}}\\
 & = \sum_{\mathbf{b}\in\mathbb{Z}_q^E}g^{\otimes
  E}(\mathbf{b})\zeta^{\mathbf{b}\cdot S\mathbf{d}+\mathbf{1}\cdot
  T\mathbf{d}}\\
& =\zeta^{\mathbf{1}\cdot T\mathbf{d}}\wh{g}^{\otimes E}(-S\mathbf{d}),\end{align*}
and
$$|F^{(q)}(G;(\zeta^{d_v}:v\in V)\,)|^2=|\wh{g}^{\otimes{E}}(-S\mathbf{d})|^2=|\wh{g}^{\otimes{E}}(S\mathbf{d})|^2.$$

 By Parseval's formula,
\begin{align*}\|F^{(q)}(G;\mathbf{x})\|_2^2  & = q^{-|V|}\sum_{\mathbf{d}\in\mathbb{Z}_q^V}|\wh{g}^{\otimes
  E}(S\mathbf{d})|^2.\\
&
=q^{-|V|}|\ker(S)|\sum_{\mathbf{b}\in\mbox{\rm \small
    im}(S)}(|\wh{g}|^2)^{\otimes E}(\mathbf{b}).\end{align*}

By the Poisson summation formula, and
using  ${\rm im}(S)^\perp=\ker(S^\top)$,
$|\ker(S)|=q^{|V|}/|{\rm im(S)}|$, we deduce the following, which
provides an answer to question (C).
 \begin{theorem}\label{thm: l2 norm}
If $$F^{(q)}(G;\mathbf{x})=\prod_{(u,v)\in\overrightarrow{E}}\;\sum_{b\in
    \mathbb{Z}_q}g(b)x_u^{t-sb}x_v^{b},$$
then
\begin{align*}\|F^{(q)}(G;\mathbf{x})\|_2^2 & =\frac{1}{|{\rm im}(S)|}\sum_{\mathbf{b}\in{\rm
    im}(S)}|\wh{g}^{\otimes E}|^2(\mathbf{b})\\
& =\sum_{\mathbf{b}\in\ker(S^\top)}(g\star g)^{\otimes
    E}(\mathbf{b}),\end{align*}
where as usual $S:\mathbb{Z}_q^V\rightarrow\mathbb{Z}_q^E$ is defined by
$(S\mathbf{d})_e=d_v-sd_u$ for $e=(u,v)\in\overrightarrow{E}$.
\end{theorem}

\begin{example} Petersen's graph polynomial modulo $(x_v^q-1:v\in V)$ has $s=1=t$,
$g=\delta_0-\delta_1$, $g\star g=2\delta_0-\delta_1-\delta_{-1}$. The
transformation $S:\mathbb{Z}_q^V\rightarrow\mathbb{Z}_q^E$ is the
coboundary operator, $S^\top$ the boundary, $\ker(S^\top)$ the
set of $\mathbb{Z}_q$-flows of $G$.
This gives Tarsi's result, Theorem \ref{thm: Tarsi}, that the $\ell_2$-norm of Petersen's graph
polynomial modulo $(x_v^q-1:v\in V)$ is equal to
$$(-1)^{|E|}\sum_{\mathbf{b}\in\{-1,0,1\}^E\cap\ker(S^\top)}(-2)^{\#\{e\in E: b_e=0\}},$$
where the sum is over {\em $(q,1)$-flows} of $G$.
\end{example}

\begin{example} The polynomial
$$\prod_{uv\in E}(x_u+x_v)$$
is a generating function for score vectors of orientations of $G$, and
as such its number of non-zero coefficients turns out to be equal to
$T(G;2,1)$, the number of forests of $G$. (See for example \cite{BO92}).
By Theorem \ref{thm: l2 norm} with  $g=\delta_0+\delta_1, g\star g=2\delta_0+\delta_{1}+\delta_{-1}$, when this polynomial is reduced modulo $(x_v^3-1:v\in V)$ it has $\ell_2$-norm
equal to $T(G;2,4)$. Determining how many
non-zero coefficients the polynomial has (its $\ell_0$-norm) when reduced modulo
$(x_v^q-1:v\in V)$ includes as a subproblem determining whether a
graph is {\em $\mathbb{Z}_q$-connected}, a notion defined in \cite{JLPT92}.
\end{example}

Theorem \ref{TG Hamming} applied to the result of Theorem~\ref{thm: l2
  norm} has the following consequence, answering
question~(B).
\begin{corollary}\label{cor: l2 Tutte}
The $\ell_2$-norm $\|F^{(q)}(G;\mathbf{x})\|_2^2$ of the polynomial
defined in Theorem \ref{thm: l2 norm} is an
evaluation of the Tutte polynomial $T(G;x,y)$ with $(x-1)(y-1)=q$  if
and only if $s=1$ and $g\star g$, equivalently $|\wh{g}|^2$, is constant on
$\mathbb{Z}_q\setminus 0$.
\end{corollary}

We finish with three examples of functions $g$ satisfying the
conditions of Corollary \ref{cor: l2 Tutte}, yielding families of polynomials that have
$\ell_2$-norm equal to a Tutte-Grothendieck invariant.

A {\em $(q,k,\ell)$-difference set} in an Abelian group $Q$ is a subset $P$ of size $k$
with the property that $\#\{a,b\in P:a-b=c\}=\ell$ for each $c\in
Q\setminus 0$. For example, $Q\setminus 0$ is a
$(q,q-1,q-2)$-difference set. All
non-zero $c$ have exactly $q-2$ ways of being written as $a-b$ for
$a,b\in Q\setminus 0$ since for given $a\in Q\setminus\{0,c\}$ there is a
unique $b\in Q\setminus \{0,c\}$ with $a-b=c$.

Note that a
function is constant on non-zero values if and only if the same is true
of its Fourier transform: if $f=t\delta_0+\delta_{Q\setminus 0}$ then
$\wh{f}=(t\!-\!1\!+\!q)\delta_0+(t\!-\!1)\delta_{Q\setminus 0}$. This
fact,
together with the equation
$\delta_P\star\delta_P=\sum_{c\in Q}\#\{a,b\in P:a-b=c\}\delta_c$,
implies that the Fourier transform $\wh{\delta_P\star\delta_P}=|\wh{\delta_P}|^2$ is constant on
$Q\setminus 0$ if and only if $P$ is a $(q,k,\ell)$-difference set in $Q$,  i.e., $\delta_P\star\delta_P=k\delta_0+\ell\delta_{Q\setminus 0}$.

 \begin{example} If $g=\delta_P$ for some $P\subseteq
\mathbb{Z}_q$, or
more generally $g=\delta_P+r\delta_{\mathbb{Z}_q\setminus P}$ for any constant
  $r$, then $|\wh{g}|^2$ is constant on $\mathbb{Z}_q\setminus
0$ if and only if $P$ is a difference set in
$\mathbb{Z}_q$. When $P=\mathbb{Z}_q\setminus 0$ this is the family of
polynomials described in Proposition \ref{prop:
  constant} whose constant terms were also Tutte-Grothendieck invariants.
\end{example}

A {\em $(q,k,\ell,m)$-partial difference set} in $Q$ is a subset $P$ of size $k$
with the property that
$\delta_P\star\delta_P=k\delta_0+\ell\delta_{P\setminus
  0}+m\delta_{Q\setminus (P\cup 0)}$. For example, a subgroup $P$ of
size $k$ is a $(q,k,k,0)$-partial difference set.

\begin{example}  If
$P\subseteq\mathbb{Z}_q\setminus 0$ and
$g=\delta_P-\delta_{\mathbb{Z}_q\setminus (P\cup 0)}$ then  then $|\wh{g}|^2$ is constant on $\mathbb{Z}_q\setminus
0$  iff $q$ is odd and $P$ is a Paley difference set or partial
  difference set, i.e. $|P|=(q-1)/2$ and
$$\delta_P\star\delta_P=\begin{cases} \frac{q-1}{2}\delta_0+\frac{q-5}{4}\delta_P+\frac{q-1}{4}\delta_{\mathbb{Z}_q\setminus(P\cup
  0)} \\
\frac{q-1}{2}\delta_0+\frac{q-3}{4}\delta_{\mathbb{Z}_q\setminus 0}, \end{cases}$$
according as $q\equiv \pm 1\pmod 4$. (For odd prime $q$, the set of non-zero squares in $\mathbb{Z}_q$ is an example of such a $P$.)
\end{example}

\begin{example} When $q$ is prime and
$g=\sum_{a\in\mathbb{Z}_q}\psi(a)\delta_a$ for a multiplicative
character $\psi$ of $\mathbb{Z}_q^\times$, then
$|\wh{g}|^2=q\delta_{\mathbb{Z}_q\setminus 0}$, i.e., the polynomial
$$F^{(q)}(G;\mathbf{x})=\prod_{(u,v)\in\overrightarrow{E}}\sum_{b\in\mathbb{Z}_q}\psi(b)x_u^{t-b}x_v^b$$
has $\ell_2$-norm $q^{|E|-|V|}P(G;q)$. (The case $q=3$ is Petersen's graph polynomial reduced modulo $(x_v^3-1:v\in V)$.)
\end{example}

{\small
\bibliography{fourier}
\bibliographystyle{plain-annote}
}

\end{document}

config: arxiv


TITLE: Expected centered entropy of the binomial distribution
QUESTION [9 upvotes]: In short, the function I am interested in is the following:
$$I_n(p) = \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[h(p) - h\left(\tfrac{k}{n}\right)\right],$$
where $h(x) \triangleq -x \log x - (1-x) \log (1-x)$ is the standard binary entropy function. I am able to prove that for large $n$ this function attains a local maximum around $p \approx \frac{1.338}{n}$ at which $I_n(p) \approx \frac{0.84}{n}$ in case binary logarithms are used. By assuming that $p = \frac{\alpha}{n}$ for $\alpha = O(1)$ and using a Poisson approximation of the binomial distribution, the value $\alpha \approx 1.338$ is a (numerically found) maximizing value of
$$\max_{\alpha > 0} \left\{\sum_{z=1}^{\infty} \frac{\alpha^z}{z!} e^{-\alpha} (z \log z) - \alpha \log \alpha\right\}.$$
Note that the latter expression does not contain $n$ anymore; I am interested in large-$n$ asymptotics of $I_n(p)$ which leads to the above, $n$-independent expression.
What I would like to show is that this point $p = \frac{\alpha}{n}$ is actually not just a local, but a global maximum, i.e., there are no values $p = \omega(\frac{1}{n})$ with even higher asymptotic values of $I_n(p)$ for large $n$. So my question can be formulated as:

Can we prove that for large $n$, $\max\limits_{p \in [0,1]} I_n(p) \to I_n(\frac{\alpha}{n})$ with $\alpha \approx 1.338184$?

Numerical inspection of $I_n(p)$ for say $n = 100\,000$ shows that $I_n(p) \propto \frac{1}{n}$ is nice and smooth, has two global maxima at $\frac{\alpha}{n}$ and $1 - \frac{\alpha}{n}$ with value $\frac{0.84}{n}$ and a local minimum at $p = \frac{1}{2}$ with value $\frac{0.72}{n}$ (and two trivial minima at $0$ and $1$ with value $0$). The figure below sketches what $I_n(p)$ (scaled with a factor $n$) looks like for small $n$. As $n$ increases, the function might be best described as a flat line at height $0.72$ with two peaks close to $0$ and $1$ of height $0.84$.

I've tried various approaches using e.g. Taylor expansions of the entropy, but I am not able to prove that "order terms" are actually small for arbitrary $p$. Also, a bound given here using Jensen's inequality is not sharp enough; it's roughly a factor $2$ too loose to prove the above statement.
Any help would be appreciated!

Attempt 1
For large $n$, the dominating terms in the summation in $I_n$ come from values $k \approx np$. Expanding $h(\frac{k}{n})$ around $k = np$ leads to
$$h\left(\frac{k}{n}\right) = h(p) + \left(\frac{k}{n} - p\right) h'(p) + \frac{1}{2}\left(\frac{k}{n} - p\right)^2 h''(p) + \frac{1}{6}\left(\frac{k}{n} - p\right)^3 h^{(3)}(p) + \dots.$$
Substituting this back into the definition of $I_n(p)$, this leads to
$$I = \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[-\left(\tfrac{k}{n} - p\right) h'(p) - \tfrac{1}{2}\left(\tfrac{k}{n} - p\right)^2 h''(p) - \tfrac{1}{6}\left(\tfrac{k}{n} - p\right)^3 h^{(3)}(p) - \dots\right].$$
Now the term $\frac{k}{n}$ leads to a factor $\frac{np}{n} = p$ when pulled out of the summation, so the first term disappears. As the second term is simply the variance (scaled by a factor $1/n^2$), this term results in $\frac{1}{2n}  p(1-p)h''(p)$. As $h'(p) = \log_2(\frac{1-p}{p})$ and $h''(p) = -1/[p(1-p)\ln 2]$, the second term contributes $1/(2n \ln 2) \approx \frac{0.72}{n}$ as expected. So we have:
$$I_n(p) = \frac{1}{2n \ln 2} + \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[- \tfrac{1}{6}\left(\tfrac{k}{n} - p\right)^3 h^{(3)}(p) - \dots\right].$$
At this point, what remains is to show that all remaining order terms are small, if $np(1-p) = \omega(1)$.

Attempt 2
Using the approach described here, consider the sum
$$S = \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \frac{k}{n} \log_2 \frac{k}{n}.$$
First, we can cancel the $\frac{k}{n}$ with factors in the binomial coefficient, and pull out a factor $p$ to obtain
$$S = p \sum_{k=1}^n \binom{n-1}{k-1} p^{k-1} (1-p)^{n-k} \log_2 \frac{k}{n} = p \sum_{k=0}^{n-1} \binom{n-1}{k} p^{k} (1-p)^{n-k-1} \log_2 \frac{k+1}{n}.$$
Applying Jensen's inequality, we obtain
$$S \leq p \log_2\left(\sum_{k=0}^{n-1} \binom{n-1}{k} p^{k} (1-p)^{n-k-1} \frac{k+1}{n}\right) = p \log_2 \frac{(n-1)p + 1}{n}.$$
Pulling out the term $\log_2 p$, we obtain
$$S \leq p \log_2 p + p \log_2\left(1 + \frac{1 - p}{np}\right).$$
Applying the same procedure to the other term in $I_n(p)$, this leads to
$$I_n(p) \leq h(p) + \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[\frac{k}{n} \log_2 \frac{k}{n} + \frac{n-k}{n} \log_2 \frac{n-k}{n}\right] \\
= h(p) + \left[p \log_2 p + p \log_2\left(1 + \frac{1 - p}{np}\right)\right] + \left[(1-p) \log_2 (1-p) + (1-p) \log_2\left(1 + \frac{p}{n(1-p)}\right)\right] \\
= p \log_2\left(1 + \frac{1 - p}{np}\right) + (1-p) \log_2\left(1 + \frac{p}{n(1-p)}\right)$$
Using $\ln(1 + x) \leq x$ for all $x$, this leads to
$$I_n(p) \leq \frac{1 - p + p}{n \ln 2}.$$
Unfortunately this is a factor $2$ off, as $I_n(p) \sim \frac{1}{2n \ln 2}$ for almost all $p$.

REPLY [4 votes]: By symmetry I can assume $p\le\frac12$.  I will use natural logs.
Put $f(x)=h(p)-h(x)$ and $b_k = \binom{n}{k} p^k(1-p)^{n-k}$.
Define $k_0=\lceil pn/2\rceil$ and $k_1=n-k_0$.
The plan is: find polynomials $f_0(x),f_1(x)$ such that $f_0(x)\le f(x)\le f_1(x)$ for $k_0/n\le x\le k_1/n$. Then make bounds on the various parts of
$$\sum_{k=0}^{k_0-1} b_k(f(k/n)-f_0(k/n)) + \sum_{k=0}^n b_k f_0(k/n) + \sum_{k=k_1+1}^n b_k (f(k/n)-f_0(k/n)) \le \sum_{k=0}^n b_k f(k/n) \le \sum_{k=0}^{k_0-1} b_k(f(k/n)-f_1(k/n)) + \sum_{k=0}^n b_k f_1(k/n) + \sum_{k=k_1+1}^n b_k (f(k/n)-f_1(k/n))
.$$
Since $f^{(iv)}(x) = 2/x^3+2/(1-x)^3$, we can use Taylor's theorem with remainder to get
$$f_j(x) = (\ln p -\ln(1-p))(x-p) + \frac{(x-p)^2}{2p(1-p)}
 - \frac{(1-2p)(x-p)^3}{6p^2(1-p)^2} + \frac{j(8-8p+2p^2+p^3)(x-p)^4}{3p^3(2-p)^2}$$
for $j=0,1$.  Maple now tells us
$$\sum_{k=0}^n b_k f_j(k/n)=\frac{1}{2n}-\frac{(1-2p)^2}{6p(1-p)n^2} + \frac{Bj}{n^2},$$
where $$B = \frac{(1-p)^2(8-8p+2p^2+p^3)}{p(2-p)^2}
 + \frac{(1-p)(8-8p+2p^2+p^3)(1-6p+6p^2)}{3p^2(2-p)^2n}.$$
This much is $1/(2n)+O(1/(pn^2))$.
In the range $0\le k\le k_0-1$, $b_k$ is dominated by a geometric series with ratio $\frac12$ and $f(x)-f_j(x)=O(p\ln p)$.  Using the Stirling approximation for $b_k$, we find that
$$\sum_{k=0}^{k_0-1} b_k(f(k/n)-f_j(k/n))=o(1/n)$$ for $p\ge (2+\epsilon)\ln\ln n/n$.
In the range $k_1+1 \le k\le n$, $b_k\le 2^{-3n/4}$ (using the assumption $p\le \frac12$) and $f(x)-f_j(x)=O(p^{-3})$, so this part is negligible compared to the previous part.
In summary,
$$\sum_{k=0}^n b_k f(k/n) = \frac{1+o(1)}{2n}$$
for $(2+\epsilon)\ln\ln n/n\le p\le 1-(2+\epsilon)\ln\ln n/n$, any $\epsilon\gt 0$.
For the case $p=a/n$ with $a=O(\ln\ln n)$, use $\binom{n}{k}=\frac{n^k}{k!}\left(1-\binom{k}{2}/n -O(k^3/n^2)\right)$ and simple bounds on the tail to find
$$\sum_{k=0}^n b_k f(k/n) = \sum_{k=0}^{(\ln n)^2} \frac{a^k}{k!}\left(1-\frac{\binom{k}{2}}{n}-\frac{ak}{n}\right)f(k/n) + O((\ln n)^{O(1)}/n^2).$$


TITLE: Value of a cyclic sum
QUESTION [3 upvotes]: Let $a,b,c$ satisfy the equation $x^3+px^2+qx+r=0$. Is it possible to determine $\frac{ab}{a+b}+\frac{bc}{b+c}+\frac{ac}{a+c}$ in terms of $p,q,r$? I stumbled upon this while thinking about an inequality problem. What i could do so far is this:
We have the relations $a+b+c=-p,ab+bc+ca=q,abc=-r$ from vietas relations. So by slightly rewriting the terms we can make them a little bit symmetric like $\frac{abc}{ac+bc}$. In this manner,the numerators become constant since $abc$ is constant. But what bothers me is we will still be left with the denominators which are not completely free of $a,b$ or $c$. And evalutating them by expansion seems to be a daunting task. Is there any clever way to approach this?

REPLY [2 votes]: Note that $\frac{ab}{a+b} = \frac{1}{\frac{1}{a}+\frac{1}{b}}$.
Suppose we have the monic cubic $f(x) = x^3+a_2x^2+a_1x+a_0$ with roots $\alpha, \beta, \gamma$. We can make use of the following two operations:

$\frac{1}{a_0}x^3f(\frac{1}{x})$ is the unique monic cubic with roots $\frac{1}{\alpha}, \frac{1}{\beta}, \frac{1}{\gamma}$.
$-f(\alpha+\beta+\gamma-x) = -f(-a_2-x)$ is the unique monic cubic with roots $\alpha+\beta,\,\alpha+\gamma,\,\beta+\gamma $.

Applying (1) to the original cubic:
$x^3+\frac{q}{r}x^2+\frac{p}{r}x+\frac{1}{r}$ has roots $\frac{1}{a}, \frac{1}{b}, \frac{1}{c}$.
Applying (2) to the result:
$$\left(x+\tfrac{q}{r}\right)^3 - \tfrac{q}{r}\left(x+\tfrac{q}{r}\right)^2 +\tfrac{p}{r}\left(x+\tfrac{q}{r}\right) - \tfrac{1}{r} = x^3+\tfrac{2q}{r}x^2+\tfrac{q^2+pr}{r^2} x + \tfrac{pq-r}{r^2}$$
has roots $\frac{1}{a}+\frac{1}{b},\, \frac{1}{a}+\frac{1}{c},\, \frac{1}{b}+\frac{1}{c}$.
Finally, applying (1) again gives
$$x^3+\tfrac{q^2+pr}{pq-r}x^2 + \tfrac{2qr}{pq-r}x+\tfrac{r^2}{pq-r}$$
which has roots $\frac{1}{\frac{1}{a}+\frac{1}{b}},\,\frac{1}{\frac{1}{a}+\frac{1}{c}},\,\frac{1}{\frac{1}{b}+\frac{1}{c}}$.
Your cyclic sum is the sum of the roots of this polynomial, which by Vieta is $$-\frac{q^2+pr}{pq-r}.$$


TITLE: Some problems in group theory
QUESTION [0 upvotes]: May I know if my proof/solution is correct? Thank you v. much.
1.) If $G, H$ are finite groups of order $10$ and $21$ respectively, then every homomorphism $f:G \to H$ satisfies $f[G] = \{e_H\}.$
Proof:
Given $g \in G-\{e_G\}, \ o(g) =  2, 5 \ or  \ 10.$ Suppose $f(g) \neq e_H.$ Then, $o(f(g))= 3,7  \ or \ 21.$
$o(g) =2 \implies (f(g))^2=e_H \implies 2|21.$ (Contradiction)
$o(g)=5 \implies (f(g))^5 = e_H \implies o(f(g))|5.$ (Contradiction)
$o(g)=10 \implies (f(g))^{10} = e_H \implies o(f(g))|10.$ (Contradiction)
2.) Let $g=(12)(123)(12345) \in S_5.$ Express $g^{222}$ as product of disjoint cycles.
Solution: $g = (1345) \implies o(g) = 4 \implies g^{222}=g^2 = (14)(35).$

REPLY [1 votes]: Your first proof is fine. Alternately, you can mention that for all $g\in G,$ and any homomorphism $f:G\to H,$ we must have $o(g)\mid 10$ and $o\bigl(f(g)\bigr)\mid 21,$ but since $$f(g)^{o(g)}=f\left(g^{o(g)}\right)=f(e_G)=e_H,$$ then we must have $o\bigl(f(g)\bigr)\mid o(g),$ and so $o\bigl(f(g)\bigr)\mid 10.$ The only positive common factor of $10$ and $21$ is $1,$ so $o\bigl(f(g)\bigr)=1$ for all $g\in G$ and all homomorphisms $f:G\to H,$ meaning the only homomorphism $G\to H$ is the map $g\mapsto e_H.$ This (non-casewise) argument allows us to easily generalize to the result that if $G$ and $H$ are finite groups with relatively prime orders, then the only homomorphism $G\to H$ is the map $g\mapsto e_H.$
Your second proof also looks fine.


TITLE: Maximize sum of edge weights on spanning tree
QUESTION [0 upvotes]: Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$.
Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, let the sum of all edge weights on spanning tree is maximized.

I wonder if there is a polynomial time algorithm for this problem.
If so, what should the algorithm do? Why is it right? Has there been any discussion in the academic circle?

REPLY [1 votes]: This is the degree-constrained spanning tree problem, and it is NP-hard:
https://en.wikipedia.org/wiki/Degree-constrained_spanning_tree


TITLE: Uniqueness of 2nd order IVP
QUESTION [2 upvotes]: How do I show that the IVP
$x''(t)=\arctan{(x(t))}\arctan{(t)}$ with $x(0)=e$, $x'(0)=e^2$
is or isn't uniquely solvable and defined on $\mathbb{R}$?

REPLY [0 votes]: The solution is unique on $\mathbb{R}$.
The most popular way to verify whether a solution of dynamical system is unique is to show Lipschitzness condition as stated below.

[1, Theorem 3.2] (Global Existence and Uniqueness) Suppose that $f(t, x)$ is piecewise continuous in $t$ and satisfies $\lVert f(t, x) - f(t, y) \rVert \leq L \lVert x-y \rVert$
$\forall x, y \in \mathbb{R}^n$, $\forall t \in [t_0, t_1]$.
Then, the state equation $\dot{x} = f(t, x)$, with $x(t_0) = x_0$, has a unique solution over $[t_0, t_1]$.

In this case, $f(t, x) = [x_2 \ \arctan(t) \arctan(x_1)]^T$ where $x = [x_1 \  x_2]^T$.
Observe that $\lvert \arctan(t) \arctan(x_1) - \arctan(t) \arctan(y_1) \rvert \leq (\pi/2)\lvert x_1 - y_1 \rvert$ (Note that $g(x) := \arctan(x) \Rightarrow \lvert g'(x) \rvert=\frac{1}{1+x^2} \leq 1 \Rightarrow g$ is Lipschitz continuous with Lipschitz constant of $1$).
Hence, $\lVert f(t, x) - f(t, y) \rVert \leq (\pi/2)\lVert [(x_2-y_2) \  (x_1-y_1)]^T \rVert = (\pi/2) \lVert x - y\rVert$ implies that the dynamical system has a unique solution on $\mathbb{R}$ (Hint: applying this to forward and backward cases).
Reference
[1] H. K. Khalil, Nonlinear Systems, 3rd ed. Upper Saddle River, NJ: Prentice Hall, 2002.


TITLE: Isomorphism between $U_{10}$ , $U_8$ , $U_5$
QUESTION [0 upvotes]: I'm trying to decide which groups are isomorphic to one another .
$$\begin{align*}
U_5 &= \{1,2,3,4\}\\
U_8 &= \{1,3,5,7\}\\
U_{10} &= \{1,3,7,9\}
\end{align*}$$
I've checked and verified that $U_{10}$ and $U_5$ are cyclic , by finding the creator generator of each group: The creator generator  of $U_5$ is $2$ and the creator generator of $U_{10}$ is $3$).
The question is, how can I verify that $U_8$ is not cyclic ? Is there a fast way to determine that, without checking if one of the elements creates generates all other elements in the group ?

REPLY [4 votes]: In a cyclic group, there is at most one element of order $2$: because a cyclic group of order $n$ has exactly one subgroup of order $d$ for each $d$ that divides $n$; if $2|n$, then there is exactly one subgroup of order $2$. But distinct elements of order $2$ generate distinct subgroups of order $2$.
Since $-1$ is always of order $2$ in $U_n$, we already know that $7$ is of order $2$ in $U_8$. To verify that $U_8$ is not cyclic, it is enough to note that $3^2\equiv 1\pmod{8}$. Thus, $U_8$ has at least two elements of order $2$, and so cannot be cyclic.

As an aside: it is incorrect to talk about the generator of a cyclic group, unless the group has order $2$; every cyclic group of order $n\gt 2$ has many generators; in fact, it has $\varphi(n)$ generators. So $3$ is a generator of $U_{10}$, but not the only one ($7$ also generates); $2$ is a generator of $U_5$, but it is not the only one ($3$ also generates).


TITLE: How many configurations can be made arranging $n$ objects in a circular alignment?
QUESTION [0 upvotes]: How many configurations can be made arranging $n$ objects in a circular alignment?
Solution:
$$\frac{n!}{n} = (n - 1)!$$
since for each permutation there are $n$ equivalents.
I don't understand the solution, can someone explain?

REPLY [0 votes]: Imagine taking $4$ people, Adam, Ben, Claire and Dave. Make them sit down on a straight bench. How many different ways they can do this?
Well, on the leftmost place you can choose from $4$ people. For the next seat you can pick from $3$ people and so on. This gives $4!$ different ways to sit down.
Observe that in this case $ABCD$ is definitely different from $DABC$ right?
Now imagine asking them to sit down around a circular table. In this case you could think in a similar fashion, BUT the above two ways wont be different. So in case of a circular table the following cases are the same (or more formally called equivalent)
$$
ABCD, \quad DABC,\quad CDAB, \quad BCDA
$$
Observe that I always just moved the last one to the beginning. This could be done in $4$ times since there are $4$ people.
So for each arrangement on the straight bench we got $4$ equivalent arrangements around the circular table making the number of different arrangements around the table $4$ times less.
Now if you have $n$ people you could arrange them on a straight bench in $n!$ different ways but when you would like to arrange the around a circular table you will be able to shift $n$ times all of which would give rise to the same order (read, say clockwise) so I have to remove these cases by dividing with the number of people that is $n$. Giving rise to the formula in your question.
Hope this helped :)

REPLY [0 votes]: It all depends on what you count as an equivalent configuration.
You start with $n!$ configurations, corresponding to the $n!$ permutations of $n$ distinguishable objects.
But if configurations that are related by a rotation are counted as equivalent, then each equivalence class contains $n$ different permutations. So the number of equivalent configurations is $\frac{n!}{n}=(n-1)!$.
And if configurations that are related by a rotation or a reflection are counted as equivalent, then each equivalence class contains $2n$ different permutations. So the number of equivalent configurations is then $\frac{n!}{2n}=\frac{(n-1)!}{2}$.


TITLE: Homomorphism between Lie group and transformation groups
QUESTION [2 upvotes]: Let $M$ be a differential manifold. Let $\mathfrak{X}(M)$ be the set of smooth vector field over $M$. Let $g$ be a finite Lie subalgebra of $\mathfrak{X}(M)$. Let $G$ be a connected, simply connected Lie group whose Lie algebra is $g$.
Suppose $g$ has the property that $\forall X\in g$, $X$ is complete. We can thus define the transformation $X_t\in\mathrm{Diff}(M)$. The group generated by all such transformations is a subgroup of $\mathrm{Diff}(M)$, denoted $H$.
If $\dim g=1$, $\exp(tX)\rightarrow X_t$ defines a homomorphism $G\rightarrow H$.
In general, how do we prove that there exists such a homomorphism?
(in Kobayashi, page 13, it is stated that the group $G$ acts locally on $M$, which, I believe, is equivalent to the existence of such a homomorphism. The homomorphism is also used in the proof of lemma 1 on the same page).

REPLY [0 votes]: Here I give a proof idea:
Let $N=G\times M$ and $g_\times$ be the vector field defined by $(g,m)\mapsto(X_{\mathfrak{X}(G)}(g),X_{\mathfrak{X}(M)}(m))$. Then by Frobenius theorem there exists a unique submanifold $\mathcal{L}_m$ passing by $(e,m)$ integrating $g_\times$. We prove that $\mathcal{L}_m\simeq G$ by the first projection, and there exists $\mathrm{Diff}(\mathcal{L}_m)\rightarrow\mathrm{Diff}(M)$ a group homomorphism induced by the second projection (which concerns picking a pre-image in $\mathcal{L}_m$ the choice of which which leaves the overall operation invariant). And finally we observe that the composite morphism:
$$G\rightarrow\mathrm{Diff}(G)\rightarrow\mathrm{Diff}(\mathcal{L}_m)\rightarrow\mathrm{Diff}(M)$$
sends $\exp(tX)$ to $X_t$.


TITLE: Computing the operator norm
QUESTION [0 upvotes]: Consider the normed vector space $E$ of all the polynomials with real coefficients in $[0, 1]$, and the $\ell^2$  norm.
Consider the operator $A: E\to E$ such that $P(x) \mapsto x P(x)$. Calculate the operator norm.
This is my attempt. In $0\leq x \leq 1$ we have
$$
\int^{1}_{0}x^2P^2(x)dx \leq \int^{1}_{0} P^2(x)dx,
$$
which leads to
\begin{align*}
\| A\| &= \sup_{P(x)} \frac{\| xP(x)\|}{\| P(x)\|}\\
&=\sup_{P(x)} \sqrt{\frac{\int^{1}_{0}x^2P^2(x)dx}{\int^{1}_{0} P^2(x)dx}}\\
&= 1
\end{align*}
Is this correct? I am not sure because of the supremum.

REPLY [1 votes]: All you've shown is that $\|A\| \le 1$.  You could try using specific polynomials to get a lower bound. For instance, if $P(x) = x^m$ then $\|P\|_{L^2} = \dfrac 1{\sqrt{2m+1}}$ and $\|AP\|_{L^2} = \dfrac 1{\sqrt{2m+3}}$ so that $$\|A\| \ge \frac{\|AP\|_{L^2}}{\|P\|_{L^2}} = \sqrt \frac{2m+1}{2m+3}.$$


TITLE: Dimension of Fibers of a Morphism "Proof" Contradicts Later Theorem
QUESTION [0 upvotes]: I'm working on Exercise 3.22(b) in Hartshorne which states:

Let $f: X \to Y$ be a dominant morphism of integral schemes of a finite type over a field $k$. Let $e = \dim X - \dim Y$ be the relative dimension of $X$ over $Y$. For any point $y \in f(X)$, show that every irreducible component of the fiber $X_y$ has dimension $\geq e$.

The proof I came up with is:
Let $y =f(x)$ for some $x \in X$ and let $Z'$ denote some irreducible component of $f^{-1}(y)$ with generic point $r$. Let $Z = \overline{\{r\}}$, where closure is done in $X$. Then, by exercise 3.22(a)*, $\mathrm{codim}(Z, X) \leq \mathrm{codim}(Y', Y)$ where $Y' := \overline{\{y\}}$ with closure done in $Y$. Then because codimension is the difference of dimension for varieties, $\dim(X) - \dim(Z) \leq \dim(Y) - \dim(Y')$, so rearranging we obtain $e \leq \dim(Z) - \dim(Y') = \dim(Z') - \dim(Y')$ because the dimension of any locally closed set is the dimension of its closure. Thus in particular $e \leq \dim(Z')$."
My problem with this proof is that if $y$ is not a closed point, this says that $e < \dim(Z')$, which would in particular violate a theorem that says that for any morphism of integral $k$ varieties, there is a nonempty open set $U \subset Y$ such that for all $y \in U$ the fiber above $y$ is pure dimension exactly $e$. (See Theorem 11.4.1 here.)
What precisely is going wrong here?
Edit: Given the comments of this question, I suspect it is not the case that $\dim(Z) = \dim(Z')$, so is the theorem about dimension of a locally closed subset false?
*Exercise 3.22(a) states that with the above setup, if $Y'$ is a closed irreducible subset of $Y$ whose generic point $\eta'$ is contained in $f(X)$, and $Z$ is any irreducible component of $Y'$ with $\eta' \in f(Z)$, then $\mathrm{codim}(Z, X) \leq \mathrm{codim}(Y', Y)$.

REPLY [2 votes]: Figured it out! An irreducible component of a fiber of the map $\pi: X \to Y$ need not be locally closed in $X$--for example, consider the identity morphism $\mathrm{Spec}(k[x]) \to \mathrm{Spec}(k[x])$, whose fiber at the generic point is, of course, the generic point, which is not locally closed (and is not even constructible).


TITLE: What are the rules for plotting directed graphs?
QUESTION [0 upvotes]: Say I have an ordered pair of sets. One contains the vertices and the other - edges.
What are the rules for actually plotting the graphs with these givens? Can a graph be plotted differently given the same set of vertices and same set of edges?

REPLY [1 votes]: There are no rules for plotting graphs.  As long as you have a dot for each vertex and a line for each edge, and the edges connect the appropriate vertices as indicated by the edge set of the graph, it doesn't matter how the graph is drawn.


TITLE: A sequence that changes sign finally at infinity?
QUESTION [1 upvotes]: I want to make a sequence $a_n$ that changes its sign at infinity.
What I'm try to make is this: $a_n$ of negative number or zero $\to$  it's limit is some positive $\epsilon$ right next to zero.
$\qquad a_n \le 0$    (for all n  $\in Z^+$)
$\qquad \lim\limits_{n \to \infty} a_n = \epsilon $, where $\epsilon\gt 0$.
Is this sequence possible?
Could you find an explicit function?
$\,\,$  Thanks in advance.

REPLY [11 votes]: No, it is not possible. Suppose otherwise. Then, there is some $N\in\mathbb N$ such that$$n\geqslant N\implies\lvert a_n-\varepsilon\rvert<\varepsilon\iff0<a_n<2\varepsilon.$$But this is impossible, since you are assuming that you always have $a_n\leqslant0$.

REPLY [3 votes]: Such a sequence doesn't exist. Note that if $a_n \le 0$ for all $n\in\Bbb N_0$, then $0$ is an upper bound of the sequence, so in particular
$$\lim_{n\to\infty} a_n \le \limsup_{n\to\infty} a_n\le\sup_{n\in\Bbb N_0} a_n \le 0.$$


TITLE: How do you evaluate limit of $\frac{\sqrt{a+x} - \sqrt a}{x\sqrt a(\sqrt{a+x})}$ when $x$ tends to $0$?
QUESTION [1 upvotes]: I tried rationalization method where we multiply both the numerator and denominator with appropriate opposite factor of numerator. But I could only get $\frac{1}{\sqrt {a^2+ax}(2 \sqrt {a + \sqrt x)}}$. But the final solution in textbook says it should be $\frac{1}{2a^{3/2}}$. Please help.

REPLY [0 votes]: Easier solution: Write $y=\sqrt{x+a}$ and $b=\sqrt{a}$, then
\begin{align}\lim_{x \to 0}\frac{\sqrt{a+x}-\sqrt{a}}{x\sqrt{a}\sqrt{a+x}} &= \lim_{y \to b}\frac{y-b}{by(y^2-b^2)}\\&=\lim_{y \to b}\frac{1}{by(y+b)}\\
&= \frac{1}{2b^3}=\frac{1}{2a\sqrt{a}}\end{align}


TITLE: Linear homogeneous recurrence relations with repeated roots; motivation behind looking for solutions of the form $nx^n$?
QUESTION [22 upvotes]: If we have a linear homogeneous recurrence relation, such as $t_{k+1}=4t_k-4t_{k-1}$, and attempt to find solutions of the form $t_n=x^n$ for some $x \in \mathbb{R} \setminus \{0\}$, we obtain the characteristic polynomial $(x-2)^2=0$.  The characteristic polynomial has repeated roots, so the standard technique is to look for solutions of the form $t_n=nx^n$ too.
It's routine to check that $t_n=n x^n$ is indeed another solution to the recurrence.  But, if I didn't already know that $t_n=n x^n$ is a solution, why would I think to look at solutions of this form?

Question: What motivation is there to consider solutions such as $t_n=n x^n$ in the case of repeated roots?

I find it easy to motivate looking for solutions of the form $t_n=x^n$, since e.g. for the Fibonacci numbers $F(n)$, we can prove exponential upper and lower bounds on $F(n)$, and it seems reasonable to suspect that similar inequalities hold more generally.

REPLY [16 votes]: Linear Algebra:
To set the stage, let $V$ be the vector space of sequences $a_0, a_1, ... $ (say of elements of an algebraically closed field) indexed by non-negative integers. On this vector space define the shift operator $S : V \to V$, which sends a sequence $a_i$ to the sequence $(Sa)_i = a_{i+1}$. To say that $a$ satisfies a linear recurrence with characteristic polynomial $p$ is then precisely to say that
$$p(S) a = 0.$$
Since we're working over an algebraically closed field, we can factor
$$p(S) = \prod_{i=1}^n (S - \lambda_i I)^{m_i}$$
and then write our recurrence as
$$\prod_{i=1}^n (S - \lambda_i I)^{m_i} a = 0.$$
In particular, any sequence satisfying $(S - \lambda_i I)^{m_i} a = 0$ (a generalized eigenvector of $S$ with eigenvector $\lambda_i$) satisfies the recurrence, and standard results in linear algebra imply that generalized eigenvectors span the entire space of solutions.
So it suffices to solve the generalized eigenvector equation. First, I'm not sure if you know this, so it's worth saying: if $m_i = 1$, then the space of solutions to
$$(S - \lambda_i I) a = 0$$
is spanned by $a_n = \lambda_i^n$ and this is the clearest reason I can think of (eigenvector decomposition) to look for exponential solutions.
Before we tackle the general case, another special case: $\lambda_i = 1$. In this case $S - I$ is just the forward difference operator, and the sequences satisfying
$$(S - I)^n a = 0$$
are precisely the polynomial sequences of degree less than $n$. This should be a familiar fact about the forward difference operator, and it turns out to imply the general result. Indeed, suppose $a$ satisfies
$$(S - \lambda_i I)^n a = 0$$
and write $a_n = \lambda_i^n b_n$ for some sequence $b_n$.
Lemma: $((S - \lambda_i I)a)_n = \lambda_i^{n+1} ((S - I)b)_n$.
Proof. Straightforward computation.
By induction, it follows that
$$(S - \lambda_i I)^n a = 0 \Leftrightarrow (S - I)^n b = 0$$
and the conclusion follows. (I haven't discussed the case $\lambda_i = 0$ but the solutions are easy to describe here.)
A Limiting Argument:
We'll work through a simple representative example since the goal here is motivation. Consider a sequence $a$ satisfying $(S - \lambda_1 I)(S - \lambda_2 I) a = 0$ where $\lambda_1 \neq \lambda_2$, and let's see what happens if we let $\lambda_1 \to \lambda_2$. To take this limit sensibly we'll fix initial conditions $a_0 = 0, a_1 = 1$. This will give
$$a_n = \frac{\lambda_1^n - \lambda_2^n}{\lambda_1 - \lambda_2}$$
Now taking the limit $\lambda_2 \to \lambda_1$ and applying, for example, l'Hopital's rule, we obtain
$$a_n = n \lambda_1^{n-1}.$$
Differential Equations:
The shift operator $S$ defined above has another incarnation as differentiation $D$: indeed, we just need to associate to a sequence $a_0, a_1, ...$ the exponential generating function
$$A(t) = \sum_{n=0}^{\infty} a_n \frac{t^n}{n!}.$$
Solutions to $p(S) a = 0$ then become solutions to differential equations $p(D) A = 0$. But now that we can work in the formalism of differential equations we can appeal to physical intuition: in physical terms, the relevant phenomenon is resonance. More concretely, let's work with a forced harmonic oscillator
$$m \frac{d^2 x}{dt^2} + kx = \sin \omega t.$$
(Think of periodically pushing a swing.) Note that $x$ satisfies $(m D^2 + k)(D^2 + \omega^2) x = 0$. This polynomial has repeated roots when $\omega^2 = \frac{m}{k}$, that is, when the frequency of the forcing function matches the "natural frequency" of the system (if physicists have better terms for these I've forgotten them). In that case one can observe experimentally in the relevant physical systems (e.g. the Tacoma Narrows bridge) that the amplitude of the oscillations increase linearly with time, and one can observe mathematically that the solution involves terms like $t \sin \omega t$ (and one simple way to see this is to use the limiting argument above). Computing the Taylor series of such solutions then gives the familiar extra factor of $n$.

REPLY [5 votes]: One way to look at this would be using generating functions.
The generating function comes out to
$$F(x) = \frac{Q(x)}{P(x)}$$
where the polynomial $P(x)$ is got from the characteristic polynomial, by replacing $x$ by $\frac{1}{x}$ and multiplying by an appropriate power of $x$.
Now using the partial fraction decomposition
$$ \frac{Q(x)}{(x-a_1)^{n_1} \dots (x-a_k)^{n_k}} = \sum_{i=1}^{k} \sum_{j=1}^{n_i} \frac{A_{ij}}{(x-a_1)^j}$$
tells us that we should get a polynomial in $n$.


TITLE: Get all dihedral angles of a tetrahedron given three angles and three edges
QUESTION [3 upvotes]: Suppose you have a general tetrahedron, you are given the three angles that define a vertex of that tetrahedron. You also know the length of the edges that converge on this same vertex.
Given that, calculate all dihedral angles.
From This question and its accepted answer I can get three of the six dihedral angles. I am trying to figure out the rest (the ones at the "base").
I tried adapting the answer for that question, extending the definition of  $\vec v_1$, $\vec v_2$, $\vec v_3$, so that now they are not unit vectors, but their magnitude is the length of the edges.
Then we could similarly define a unit normal vector for the "base" as:
$$\vec n_{12}=\dfrac{\vec v_1 \times \vec v_2}{|\vec v_1 \times \vec v_2|}  \quad\text{and} \quad \vec n_{b}=\dfrac{\vec v_1 \times \vec v_2 + \vec v_2 \times \vec v_3 + \vec v_3 \times \vec v_1}{|\vec v_1 \times \vec v_2 + \vec v_2 \times \vec v_3 + \vec v_3 \times \vec v_1|}$$
so then, similar to that answer:
$$\text{cos}(θ_{ab})=-\vec n_{12}\cdot \vec n_{b}$$
But this hasn´t taken me very far. I feel like I might be very close but my vector arithmetics is too rusty. Or it is just simply wrong.
EDIT: Already solved this, thanks to your answers. However I am still trying to solve using my original approach. After some vector operations I get to this:
$\text{cos}(θ_{ab})=- \dfrac{a^2b^2\text{sin}^2\phi_{ab}+b^2ac(\text{cos}\phi_{ab}\text{cos}\phi_{bc}-\text{cos}\phi_{ac})+a^2bc(\text{cos}\phi_{ac}\text{cos}\phi_{ab}-\text{cos}\phi_{bc})}{ab\text{sin}\phi_{ab}(|\vec v_1 \times \vec v_2 + \vec v_2 \times \vec v_3 + \vec v_3 \times \vec v_1|)}$
Where $a,b,c$ are the lengths of the edges along $\vec v_1,\vec v_2,\vec v_3$ (also their magnitudes) and $\phi_{ab}$ is the angle between edges $a$ and $b$ (and so on)
So it is looking quite well, because it is mostly in terms of the angles and edge lengths, but still need to simplify those vectors. Any ideas?

REPLY [2 votes]: Let exactly three faces of any polyhedron meet at a vertex. Also let the angle of each polygon at that vertex be known. Call them $\alpha$, $\beta$, and $\gamma$. Let $\theta$ be the dihedral angle on the edge opposite the face having angle $\gamma$. Here is a relationship that can be used to derive $\theta$:
$\cos \theta = \frac {\cos \gamma - \cos \alpha \cos \beta}{\sin \alpha \sin \beta}$
The derivation of that equation is explained in this article.
With the given angles alone, it is possible to use this same formula to derive the dihedral angles on all three of the given edges.
Now, use the cosine rule of triangles to derive the lengths of the three unknown edges, one edge opposite each of the given angles. At this point, you will have the lengths of all six edges of the tetrahedron, i.e., all three sides on each triangle face. Use the cosine rule again to derive all three angles on each face.
At this time, you have the angle of all three faces meeting at any vertex. The equation above can now be used to clean up the remaining dihedral angles.


TITLE: Confusion about implicit differentiation $\frac{dy}{dx}$
QUESTION [2 upvotes]: Today I learnt about implicit differentiation using this:
$\frac{d}{dx}(f)$ = $\frac{df}{dy} \times \frac{dy}{dx}$
I don't understand when doing implicit differentiation how the d/dy part works for y terms:
$\frac{d(y^2)}{dx} = \frac{d(y^2)}{dy}\times\frac{dy}{dx}=2y\frac{dy}{dx}$
Why is the derivative of $y^2$ with respect to $y$, $2y$? Do you assume it's a function of something else?
And similarly if you apply this same formula to an $x$ term (even though its not needed) you get:
$\frac{d(x^2)}{dx} =\frac{d(x^2)}{dy}\times\frac{dy}{dx}$
How does that simplify to the $2x$ I know it is?
Thanks

REPLY [2 votes]: The derivative of $y^2$ with respect to $y$ is $2y$ because of the definition of derivative:
$$\lim_{h \to 0} \frac{(y+h)^2-y^2}{h} = 2y.$$
In the last expression you write
$$\frac{d(x^2)}{dx} = \frac{d(x^2)}{dy}\frac{dy}{dx}$$
but this is meaningful only when $x$ is a function of $y$. So assume $x = f(y)$. Then, by the first equation you mention in the question, the right hand side is
$$\frac{d(f^2)}{dy}\frac{dy}{dx} = 2f(y)f'(y)\frac{dy}{dx} = 2xf'(y)\frac{dy}{dx} = 2x\frac{dx}{dy}\frac{dy}{dx} = 2x\frac{dx}{dx} = 2x.$$


TITLE: How can I decompose this 6th-degree polynomial fraction into partial fractions?
QUESTION [1 upvotes]: How can I use partial-fraction decomposition for this fraction?
$$f(x)\equiv\dfrac{-x^{5}+2x^{4}-3x^{3}+4x^{2}-5x+6}{7(x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1)}.$$

REPLY [1 votes]: Note that the denominator is a factor of $x^7+1$, the other factor being $x+1$. So the zeros of the denominator are at $x=\,$e$^{\pm\text i(2k+1)\pi}$ ($k=0,1,2$). Pairing off the complex conjugates gives$$f(x)\equiv\sum_{k=0}^2\frac{a_kx+b_k}{x^2-2x\cos\frac17(2k+1)\pi+1},$$where $a_k$ and $b_k$ are real constants to be determined. Substituting in six values of $x$ (e.g. $x=0$) will give six linear equations in the constants, enabling them to be determined.
On further thought, it's best to simplify first by multiplying numerator and denominator by $x+1$, to get$$f(x)\equiv\frac{-1}{7(x+1)}+ \frac1{x^7+1}.$$Then it's easier to calculate $f(x)$ at the substituted values.