# The ELITR ECA Corpus

Philip Williams  Barry Haddow

School of Informatics, University of Edinburgh, Scotland
<EMAIL_ADDRESS>
###### Abstract

We present the ELITR ECA corpus, a multilingual corpus derived from
publications of the European Court of Auditors. We use automatic translation
together with Bleualign to identify parallel sentence pairs in all 506
translation directions. The result is a corpus comprising 264k document pairs
and 41.9M sentence pairs.

##  1 Introduction

Most machine translation systems are trained using large volumes of human-
translated text. The high cost of human translation means that training data
is not typically created specifically for use in machine translation but is
instead repurposed from sources where text has been translated for some other
use. The European Union, which publishes in up to 24 languages has long been a
rich source of data for the machine translation community Koehn (2005);
Steinberger et al. (2006, 2014); Hajlaoui et al. (2014).

In line with other institutions of the EU, the European Court of
Auditors111https://www.eca.europa.eu/ publishes the majority of its official
documents in 23 of the 24 EU languages.222Irish is due to be included from
2022. To our knowledge, this data has not yet been compiled into a publicly
available corpus. In this work, we downloaded PDF reports from the ECA website
and extracted plain text versions to create 23 monolingual corpora, with text
segmented at the document and sentence level. We then used a multilingual
neural machine translation system to automatically translate text in all 506
translation directions and used Bleualign Sennrich and Volk (2011) to identify
parallel sentences. The resulting dataset comprises 264k document pairs and
totalling 41.9M sentence pairs (including duplicates) across all translation
directions. It is available from http://data.statmt.org/elitr-eca.

Sections 2 and 3 describe the methodology in more detail and report some
further statistics of the data.

##  2 Monolingual Corpora

We created monolingual corpora in 23 languages by downloading PDF reports,
extracting plain text, converting to UTF-8, splitting into sentences, de-
hyphenating, and normalizing.

The PDFs were downloaded in May 2020. We first used the ECA website’s search
facility333https://www.eca.europa.eu/en/Pages/PublicationSearch.aspx to obtain
a list of URLs for all available English language PDFs. ECA documents use a
consistent file naming convention where the ISO 639-1 language code is
included in the filename (for example agencies_2019_EN.pdf). We substituted
the 22 other language codes and downloaded all documents that were available.

To obtain plain-text versions of the PDFs, we wrote an Automator script that
used macOS’s built-in support for PDF-to-text conversion. The resulting files
used a mixture of character encodings, so we used
chardet444https://chardet.github.io to automatically detect the encoding of
each file, then converted from that encoding to UTF-8 using iconv.

We split the text into sentences using the split-sentences.perl script from
the Moses toolkit Koehn et al. (2007).

A common problem with text extracted from PDF is that words that were broken
at the end of a line retain their hyphenation and must be re-joined. We used a
simple statistical approach where we collected token counts for each language
across all of the extracted text. We then searched for pairs of tokens where
the first ends in a hyphen, replacing the pair with their concatenation,
either with or without the hyphen depending on which resulting form had been
observed most frequently. For example, dur- ing was replaced with during
because during was seen 8,735 times and dur-ing was never seen. co- financed
was replaced with co-financed because that token was seen 1,079 times and
cofinanced was seen only 63 times.

Finally, we normalized the Unicode representation files by converting them to
NFC form.

Table 1 gives per-language statistics for the resulting corpus.

Language | Documents | Sentences
---|---|---
Bulgarian | 779 | 398,012
Croatian | 444 | 281,783
Czech | 871 | 418,043
Danish | 368 | 193,895
Dutch | 783 | 391,914
English | 1,391 | 661,815
Estonian | 402 | 183,265
Finnish | 1,072 | 535,880
French | 1,229 | 591,559
German | 816 | 376,395
Greek | 1,126 | 541,826
Hungarian | 868 | 426,962
Italian | 181 | 92,540
Latvian | 198 | 94,864
Lithuanian | 434 | 204,860
Maltese | 867 | 398,056
Polish | 867 | 412,476
Portuguese | 1,130 | 527,610
Romanian | 278 | 124,837
Slovak | 869 | 434,025
Slovene | 310 | 138,246
Spanish | 1,143 | 555,153
Swedish | 1,074 | 519,219
Table 1: Monolingual corpus statistics.

##  3 Parallel Corpora

We derived parallel corpora from pairs of plain-text documents for all 506
directed combinations of the 23 languages. For each plain-text version of a
document $d_{x}$ in language $x$ with a corresponding plain-text document
$d_{y}$ in language $y$, we translated $d_{x}$ into language $y$ to create
document $d_{xy}$. We then used Bleualign to identify parallel sentences in
$d_{x}$ and $d_{y}$ based on the similarity of sentences in $d_{y}$ to the
translations in $d_{xy}$. We used a threshold similarity of 10.0 Bleu. We did
this for each language pair $x$-$y$ to create a corpus of parallel sentences,
creating separate corpora for pairs $x$-$y$ and $x$-$y$, from the same set of
documents. This provides the option of taking the intersection of sentence
pairs obtained from translation in both directions, which should be expected
to increase the precision of parallel sentence identification.

In order that the corpus can be filtered based on translation quality, we
provide files in tab-separated format, one per document pair, containing the
source sentence, target sentence, and Bleu score.

Table 2 gives some statistics for the resulting corpus. For space reasons, we
show only the top 10 and bottom 10 language pairs, ordered by number of
sentence pairs.

Language Pair |  Document Pairs |  Sentence Pairs
---|---|---
fr2en |  1,203 |  455,227
en2fr |  1,203 |  454,616
es2en |  1,124 |  437,505
en2es |  1,124 |  437,174
pt2en |  1,112 |  414,160
en2pt |  1,112 |  409,990
el2en |  1,104 |  404,410
en2el |  1,104 |  400,482
sv2en |  1,066 |  398,566
en2sv |  1,066 |  391,925
… |  … |  …
it2lv |  135 |  14,923
et2it |  134 |  14,915
lt2it |  135 |  14,888
lv2hr |  96 |  14,848
it2hu |  134 |  14,497
it2et |  134 |  14,348
hu2it |  134 |  14,266
bg2it |  122 |  13,973
hr2it |  66 |  8,386
it2hr |  66 |  8,300
Table 2: Parallel corpus statistics.

###  3.1 Translation Model

For translation, we trained a single many-to-many multilingual model on a
dataset sampled from the OPUS collection Tiedemann (2012). Similar to prior
work, including Aharoni et al. (2019) and Zhang et al. (2020), our dataset was
English-centric, meaning that all training pairs included English on either
the source or target side. We used all available parallel corpora for English
paired with the 23 non-English EU languages. In order to reduce the dominance
of high-resource language pairs / domains, we applied exponentially smoothed
weighting to domain and language pair choice when sampling sentence pairs. In
total, our training data contained 364M sentence pairs.

Our preprocessing pipeline consisted of corpus cleaning, segmentation, and
target language tagging. For corpus cleaning, we used the clean-corpus-n.perl
script from the Moses toolkit Koehn et al. (2007). This applies a maximum
length threshold of 80 as well as removing empty sentences and sentence pairs
with length ratios greater than 9:1. For segmentation, we trained a single
SentencePiece model Kudo and Richardson (2018) with a vocabulary size of
64,000 BPE subwords and a vocabulary threshold of 50. We added a token to each
source sentence to specify the target language, as in Johnson et al. (2017).

For training we used Marian (Junczys-Dowmunt et al., 2018) with hyperparameter
settings matching the ‘base’ configuration of Vaswani et al. (2017).

##  4 Conclusion

We have presented the ELITR ECA corpus, a multilingual corpus derived from
publications of the European Court of Auditors. The corpus preserves document
boundaries and Bleu similarity scores, and contains between 8,300 and 455,227
sentence pairs per language pair in all 506 translation directions, totalling
41.9M sentence pairs.

## Acknowledgements

This work has received funding from the European Union’s Horizon 2020 Research
and Innovation Programme under Grant Agreement No 825460 (ELITR).

## References

  * Aharoni et al. (2019) Roee Aharoni, Melvin Johnson, and Orhan Firat. 2019.  Massively multilingual neural machine translation.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 3874–3884, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Hajlaoui et al. (2014) Najeh Hajlaoui, David Kolovratnik, Jaakko Väyrynen, Ralf Steinberger, and Daniel Varga. 2014.  DCEP -digital corpus of the European parliament.  In _Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14)_ , Reykjavik, Iceland. European Language Resources Association (ELRA).
  * Johnson et al. (2017) Melvin Johnson, Mike Schuster, Quoc V. Le, Maxim Krikun, Yonghui Wu, Zhifeng Chen, Nikhil Thorat, Fernanda Viégas, Martin Wattenberg, Greg Corrado, Macduff Hughes, and Jeffrey Dean. 2017.  Google’s multilingual neural machine translation system: Enabling zero-shot translation.  _Transactions of the Association for Computational Linguistics_ , 5:339–351.
  * Junczys-Dowmunt et al. (2018) Marcin Junczys-Dowmunt, Roman Grundkiewicz, Tomasz Dwojak, Hieu Hoang, Kenneth Heafield, Tom Neckermann, Frank Seide, Ulrich Germann, Alham Fikri Aji, Nikolay Bogoychev, André F. T. Martins, and Alexandra Birch. 2018.  Marian: Fast neural machine translation in C++.  In _Proceedings of ACL 2018, System Demonstrations_ , pages 116–121, Melbourne, Australia.
  * Koehn (2005) Philipp Koehn. 2005.  Europarl: A parallel corpus for statistical machine translation.  In _MT Summit 2005_.
  * Koehn et al. (2007) Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondřej Bojar, Alexandra Constantin, and Evan Herbst. 2007\.  Moses: Open source toolkit for statistical machine translation.  In _Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics Companion Volume Proceedings of the Demo and Poster Sessions_ , pages 177–180, Prague, Czech Republic.
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 66–71, Brussels, Belgium.
  * Sennrich and Volk (2011) Rico Sennrich and Martin Volk. 2011.  Iterative, MT-based sentence alignment of parallel texts.  In _Proceedings of the 18th Nordic Conference of Computational Linguistics (NODALIDA 2011)_ , pages 175–182, Riga, Latvia. Northern European Association for Language Technology (NEALT).
  * Steinberger et al. (2014) Ralf Steinberger, Mohamed Ebrahim, Alexandros Poulis, Manuel Carrasco-Benitez, Patrick Schlüter, Marek Przybyszewski, and Signe Gilbro. 2014.  An overview of the european union’s highly multilingual parallel corpora.  _Lang. Resour. Eval._ , 48(4):679–707.
  * Steinberger et al. (2006) Ralf Steinberger, Bruno Pouliquen, Anna Widiger, Camelia Ignat, Tomaž Erjavec, Dan Tufiş, and Dániel Varga. 2006.  The JRC-Acquis: A multilingual aligned parallel corpus with 20+ languages.  In _Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC’06)_ , Genoa, Italy. European Language Resources Association (ELRA).
  * Tiedemann (2012) Jörg Tiedemann. 2012.  Parallel data, tools and interfaces in OPUS.  In _LREC_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems 30_ , pages 5998–6008. Curran Associates, Inc.
  * Zhang et al. (2020) Biao Zhang, Philip Williams, Ivan Titov, and Rico Sennrich. 2020.  Improving massively multilingual neural machine translation and zero-shot translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1628–1639, Online. Association for Computational Linguistics.


(D.6) $\infty>|[Dw]^{i}|(U)=\int_{U}|\partial_{i}w|\;\mathrm{d}x.$

The $W^{1,1}$-regularity follows. Note however that the maximum principle is
also not clear for $W^{1,1}$-solutions.
Step 2: We find an equation that characterizes $w$ uniquely. To this end let
$\phi\in C^{2}(\overline{U})$ be such that $\phi|_{\partial U}=0$. Our aim is
to show that

(D.7) $\int_{U}w\Delta\phi\;\mathrm{d}x=\int_{\partial
U}\mathrm{tr}(w)\partial_{\nu}\phi\;\mathrm{d}\mathcal{H}^{n-1}.$

To this end we extend $\phi$ to a $C^{2}_{c}(\mathbb{R}^{n})$-function which
is possible due to the boundary regularity. Let $\overline{\phi}\in
C^{2}_{c}(\mathbb{R}^{n})$ be this extension. Then by Lemma D.1 one has

(D.8) $\displaystyle\int_{U}w\Delta\phi\;\mathrm{d}x$
$\displaystyle=\int_{U}w\Delta\overline{\phi}\;\mathrm{d}x=\int_{U}w\;\mathrm{div}(\nabla\overline{\phi})\;\mathrm{d}x$
(D.9) $\displaystyle=\int_{\partial
U}\mathrm{tr}(w)\nabla\phi\cdot\nu\;\mathrm{d}\mathcal{H}^{n-1}-\int_{U}\nabla\phi\;\mathrm{d}[Dw]$
(D.10) $\displaystyle=\int_{\partial
U}\mathrm{tr}(w)\nabla\phi\cdot\nu\;\mathrm{d}\mathcal{H}^{n-1}-\int_{U}\nabla\phi\nabla
w\;\mathrm{d}x.$

Next we intend to approximate $\phi$ by a sequence of functions
$(\phi_{n})_{n\in\mathbb{N}}\subset C_{0}^{\infty}(U)$ to get rid of the
second summand. This approximation is nonstandard because of the fact that one
only has $\nabla w\in L^{1}$. We claim that there exist
$(\phi_{n})_{n\in\mathbb{N}}\subset C_{0}^{\infty}(U)$ such that
$\phi_{n}\rightarrow\phi$ in $W_{0}^{1,2}(U)$ and
$||\nabla\phi_{n}||_{L^{\infty}}\leq||\nabla\phi||_{L^{\infty}}$. To this end
notice that (since $\phi|_{\partial\Omega}=0$) for all $n\in\mathbb{N}$ the
functions $\left(\phi-\frac{1}{n}\right)^{+}$ and
$\left(\phi+\frac{1}{n}\right)^{-}$ have compact support in $U$ and lie in
$W^{1,2}_{0}(U)$. This implies that for $\epsilon<\epsilon_{0}$ appropriately
small $\left(\phi-\frac{1}{n}\right)^{+}*\psi_{\epsilon}\in C_{0}^{\infty}(U)$
and
$\left(\phi-\frac{1}{n}\right)^{+}*\psi_{\epsilon}\rightarrow\left(\phi-\frac{1}{n}\right)^{+}$
in $W_{0}^{1,2}(U)$ as $\epsilon\rightarrow 0$. We infer that for all
$n\in\mathbb{N}$ there exists $\epsilon_{n}>0$ such that
$\left(\phi-\frac{1}{n}\right)^{+}*\psi_{\epsilon_{n}}\in C_{0}^{\infty}(U)$
and
$||\left(\phi-\frac{1}{n}\right)^{+}*\psi_{\epsilon_{n}}-\left(\phi-\frac{1}{n}\right)^{+}||_{W_{0}^{1,2}}<\frac{1}{n}$.
Similarly we can find $\widetilde{\epsilon_{n}}>0$ such that
$\left(\phi-\frac{1}{n}\right)^{-}*\psi_{\widetilde{\epsilon}_{n}}\in
C_{0}^{\infty}(U)$ and
$||\left(\phi-\frac{1}{n}\right)^{-}*\psi_{\widetilde{\epsilon}_{n}}-\left(\phi-\frac{1}{n}\right)^{-}||_{W_{0}^{1,2}}<\frac{1}{n}$.
By possibly shrinking $\epsilon_{n}$ or $\widetilde{\epsilon}_{n}$ we may
assume that $\epsilon_{n}=\widetilde{\epsilon_{n}}$. Now define

(D.11)
$\phi_{n}:=\left(\phi-\frac{1}{n}\right)^{+}*\psi_{\epsilon_{n}}+\left(\phi+\frac{1}{n}\right)^{-}*\psi_{{\epsilon}_{n}}$

It is then straightforward to show that $(\phi_{n})_{n\in\mathbb{N}}\subset
C_{0}^{\infty}(U)$ and $\phi_{n}\rightarrow\phi$ in $W_{0}^{1,2}(U)$. It
remains to show that
$||\nabla\phi_{n}||_{L^{\infty}}\leq||\nabla\phi||_{L^{\infty}}$. To this end
notice that

(D.12)
$\displaystyle\nabla\left[\left(\phi-\frac{1}{n}\right)^{+}*\psi_{\epsilon_{n}}\right](x)$
$\displaystyle=\int_{U}\left(\phi-\frac{1}{n}\right)^{+}(y)\nabla_{x}\psi_{\epsilon_{n}}(x-y)\;\mathrm{d}y$
(D.13)
$\displaystyle=-\int_{U}\left(\phi-\frac{1}{n}\right)^{+}(y)\nabla_{y}\psi_{\epsilon_{n}}(x-y)\;\mathrm{d}y$
(D.14)
$\displaystyle=\int_{U}\nabla\left(\phi-\frac{1}{n}\right)^{+}(y)\psi_{\epsilon_{n}}(x-y)\;\mathrm{d}y$
(D.15)
$\displaystyle=\int_{U\cap\\{\phi>\frac{1}{n}\\}}(\nabla\phi)\psi_{\epsilon_{n}}(x-y)\;\mathrm{d}y.$

Similarly

(D.16)
$\nabla\left[\left(\phi-\frac{1}{n}\right)^{-}*\psi_{\epsilon_{n}}\right](x)=\int_{U\cap\\{\phi<-\frac{1}{n}\\}}(\nabla\phi)\;\psi_{\epsilon_{n}}(x-y)\;\mathrm{d}y.$

We obtain by Young’s inequality that

(D.17)
$|\nabla\phi_{n}(x)|=\left|\int_{U\cap\\{|\phi|>\frac{1}{n}\\}}(\nabla\phi)\;\psi_{\epsilon_{n}}(x-y)\;\mathrm{d}y\right|\leq||\nabla\phi||_{L^{\infty}(U)}||\psi_{\epsilon_{n}}||_{L^{1}(\mathbb{R}^{n})}=||\nabla\phi||_{L^{\infty}(U)}.$

It follows that
$||\nabla\phi_{n}||_{L^{\infty}}\leq||\nabla\phi||_{L^{\infty}}$. Note that we
may assume after the choice of an appropriate subsequence that
$\nabla\phi_{n}\rightarrow\nabla\phi$ pointwise almost everywhere. Since
$||\nabla\phi_{n}||_{L^{\infty}}\leq||\nabla\phi||_{L^{\infty}}$ and $|\nabla
w|\;||\nabla\phi||_{L^{\infty}}\in L^{1}$ we infer by the dominated
convergence theorem that

(D.18) $\int_{U}\nabla
w\nabla\phi\;\mathrm{d}x=\lim_{n\rightarrow\infty}\int_{U}\nabla
w\nabla\phi_{n}\;\mathrm{d}x=\lim_{n\rightarrow\infty}\int_{U}w\Delta\phi_{n}=0,$

where we used (4.40) in the last step. We infer from (D.10) that for each
$\phi\in C^{2}(\overline{U})$ such that $\phi|_{\partial U}=0$ one has

(D.19) $\int_{U}w\Delta\phi\;\mathrm{d}x=\int_{\partial
U}\mathrm{tr}(w)\partial_{\nu}\phi\;\mathrm{d}\mathcal{H}^{n-1}.$

With this equation we will be able to show that
$||w||_{L^{\infty}(U)}\leq||\mathrm{tr}(w)||_{L^{\infty}(\partial U)}$.
Step 3: Show the claim under the additional assumption that $\mathrm{tr}(w)$
has a $C^{\infty}$-extension on $\overline{U}$, say $\overline{w}\in
C^{\infty}(\overline{U})$ is such that $\overline{w}|_{\partial
U}=\mathrm{tr}(w)$. Then one has for all $\phi\in C^{2}(\overline{U})$ such
that $\phi|_{\partial U}=0$ by the divergence theorem

(D.20) $\displaystyle\int_{U}w\Delta\phi\;\mathrm{d}x=\int_{\partial
U}\mathrm{tr}(w)\partial_{\nu}\phi\;\mathrm{d}\mathcal{H}^{n-1}$
$\displaystyle=\int_{\partial
U}\overline{w}\partial_{\nu}\phi\;\mathrm{d}\mathcal{H}^{n-1}$ (D.21)
$\displaystyle=\int_{U}\nabla\overline{w}\nabla\phi\;\mathrm{d}x+\int_{U}\overline{w}\Delta\phi\;\mathrm{d}x$
(D.22)
$\displaystyle=-\int_{U}\Delta\overline{w}\phi\;\mathrm{d}x+\int_{U}\overline{w}\Delta\phi\;\mathrm{d}x$

Hence for all $\phi\in C^{2}(\overline{U})$ such that $\phi|_{\partial U}=0$
one has

(D.23)
$\int_{U}(w-\overline{w})\Delta\phi\;\mathrm{d}x=-\int_{U}\Delta\overline{w}\phi\;\mathrm{d}x.$

By Lemma 3.1 we conclude that $w-\overline{w}\in W_{0}^{1,q}(U)$ for some
$q>1$ and solves $\Delta(w-\overline{w})=-\Delta\overline{w}$ in the weak
$W_{0}^{1,q}$-sense. By elliptic regularity this implies that
$w-\overline{w}\in C^{\infty}(\overline{U})$. We infer that $w\in
C^{\infty}(\overline{U})$, $\Delta w=0$ classically, and $w|_{\partial
U}=\overline{w}|_{\partial U}=\mathrm{tr}(w)$. By the (classical) maximum
principle we have
$||w||_{L^{\infty}(U)}\leq||\mathrm{tr}(w)||_{L^{\infty}(\partial U)}$. We
have shown the claim under the additional assumption of Step 3.
Step 4: We show the claim under the (weaker) additional assumption that
$\mathrm{tr}(w)\in C^{0}(\partial U)$. If $\mathrm{tr}(w)\in C^{0}(\partial
U)$, then by Tietze’s extension theorem we can find $v\in
C_{0}^{0}(\mathbb{R}^{n})$ such that $v=w$ on $\partial U$. Now $v$ can be
locally uniformly approximated by $(v_{n})_{n\in\mathbb{N}}\subset
C_{0}^{\infty}(\mathbb{R}^{n})$ which means that $w$ can be uniformly
approximated on $\partial U$ by $v_{n}|_{\partial U}$ — i.e. by functions that
possess a $C^{\infty}$ extension to $\overline{U}$. Now let
$(w_{n})_{n\in\mathbb{N}}\subset C^{\infty}(\overline{U})$ be the solutions of

(D.24) $\begin{cases}-\Delta w_{n}=0&\mathrm{in}\;U,\\\
\quad\;\;w_{n}=v_{n}&\mathrm{on}\;\partial U.\end{cases}$

Note that then
$||w_{n}-w_{m}||_{L^{\infty}(U)}\leq||v_{n}-v_{m}||_{L^{\infty}(\partial U)}$
and hence $w_{n}$ converges in $L^{\infty}(U)$ to some $\widetilde{w}\in
L^{\infty}(U)$. Using the Gauss divergence theorem and (D.19) we find for each
$\phi\in C^{2}(\overline{U})$ such that $\phi|_{\partial U}=0$ that

(D.25) $\displaystyle\int_{U}\widetilde{w}\Delta\phi\;\mathrm{d}x$
$\displaystyle=\lim_{n\rightarrow\infty}\int_{U}w_{n}\Delta\phi\;\mathrm{d}x=\lim_{n\rightarrow\infty}\int_{\partial
U}v_{n}\partial_{\nu}\phi\;\mathrm{d}\mathcal{H}^{n-1}$ (D.26)
$\displaystyle=\int_{\partial
U}\mathrm{tr}(w)\partial_{\nu}\phi\;\mathrm{d}\mathcal{H}^{n-1}=\int_{U}w\Delta\phi\;\mathrm{d}x.$

Hence we infer that for all $\phi\in C^{2}(\overline{U})$ such that
$\phi|_{\partial U}=0$ one has

(D.27) $\int_{U}(\widetilde{w}-w)\Delta\phi\;\mathrm{d}x=0.$

By Lemma 3.1 we infer that $\widetilde{w}-w$ lies in $W_{0}^{1,q}(\Omega)$ for
some $q>1$ and is a weak solution of $\Delta(\widetilde{w}-w)=0$. By
uniqueness of weak solutions of the Dirichlet problem in $W_{0}^{1,q}$ we find
$\widetilde{w}=w$. Hence

(D.28)
$||w||_{L^{\infty}(U)}=||\widetilde{w}||_{L^{\infty}(U)}=\lim_{n\rightarrow\infty}||w_{n}||_{L^{\infty}(U)}\leq\liminf_{n\rightarrow\infty}||v_{n}||_{L^{\infty}(\partial
U)}=||\mathrm{tr}(w)||_{L^{\infty}(\partial U)}.$

We have now shown the claim under the additional assumption of Step 4.
Step 5: Next we assume nothing except $\mathrm{tr}(w)\in L^{\infty}(\partial
U)$. We know that then by Proposition C.1 there exist
$(v_{n})_{n\in\mathbb{N}}\subset C^{0}(\partial U)$ such that
$v_{n}\rightarrow\mathrm{tr}(w)$ in $L^{1}(\partial U)$ and
$||v_{n}||_{L^{\infty}(\partial U)}\leq||w||_{L^{\infty}(\partial U)}$. Now
let $(w_{n})_{n\in\mathbb{N}}\subset C^{\infty}(\overline{U})$ be the weak
$W_{0}^{1,2}$-solutions to

(D.29) $\begin{cases}-\Delta w_{n}=0&\mathrm{in}\;U,\\\
\quad\;\;w_{n}=v_{n}&\mathrm{on}\;\partial U.\end{cases}$

Then by [Anna, p.467] one has for each $x\in U$

(D.30) $w_{n}(x)=\int_{\partial U}K_{U}(x,y)v_{n}(y)\;\mathrm{d}y,$

where $K_{U}\in C^{\infty}(U\times\partial U)$ is the Poisson kernel for $U$.
Since by [Anna, Theorem 4]

(D.31) $|K_{U}(x,y)|\leq C_{U}\frac{\mathrm{dist}(x,\partial
U)}{|x-y|^{n-1}},$

the dominated convergence theorem yields for all $x\in U$

(D.32) $\lim_{n\rightarrow\infty}w_{n}(x)=\int_{\partial
U}K_{U}(x,y)\mathrm{tr}(w)(y)\;\mathrm{d}y=:w^{*}(x),\quad(x\in U).$

Hence $(w_{n})_{n\in\mathbb{N}}$ converges pointwise on $U$ to some measurable
function $w^{*}:U\rightarrow\mathbb{R}$. Since
$||w_{n}||_{L^{\infty}(U)}\leq||v_{n}||_{L^{\infty}(\partial
U)}\leq||\mathrm{tr}(w)||_{L^{\infty}(\partial U)}$ we infer that $w^{*}\in
L^{\infty}$ and

(D.33)
$||w^{*}||_{L^{\infty}}\leq\liminf_{n\rightarrow\infty}||w_{n}||_{L^{\infty}}\leq||\mathrm{tr}(w)||_{L^{\infty}(\partial
U)}.$

By the dominated convergence theorem, the Gauss divergence theorem and (D.19)
we infer for all $\phi\in C^{2}(\overline{U})$ such that $\phi|_{\partial
U}=0$

(D.34) $\displaystyle\int_{U}w^{*}\Delta\phi\;\mathrm{d}x$
$\displaystyle=\lim_{n\rightarrow\infty}\int_{U}w_{n}\Delta\phi\;\mathrm{d}x=\lim_{n\rightarrow\infty}\int_{\partial
U}v_{n}\partial_{\nu}\phi\;\mathrm{d}\mathcal{H}^{n-1}$ (D.35)
$\displaystyle=\int_{\partial
U}\mathrm{tr}(w)\partial_{\nu}\phi\;\mathrm{d}\mathcal{H}^{n-1}=\int_{U}w\Delta\phi\;\mathrm{d}x.$

It follows again that

(D.36) $\int_{U}(w^{*}-w)\Delta\phi\;\mathrm{d}x=0\quad\forall\phi\in
C^{2}(\overline{U}):\phi|_{\partial U}=0.$

and hence by 3.1 we obtain that $w^{*}-w\in W_{0}^{1,q}(U)$ for some $q>1$ and
by uniqueness of solutions to the Dirichlet problem in $W_{0}^{1,q}(U)$ we
infer once again $w=w^{*}$ which gives
$||w||_{L^{\infty}(U)}\leq||w^{*}||_{L^{\infty}(U)}\leq||\mathrm{tr}(w)||_{L^{\infty}(\partial
U)}$. ∎

## References

  * [1]
AltH. W.CaffarelliL. A.Existence and regularity for a minimum problem with
free boundaryJ. Reine Angew. Math.3251981105–144ISSN 0075-4102Review
MathReviews@article{Alt, author = {Alt, H. W.}, author = {Caffarelli, L. A.},
title = {Existence and regularity for a minimum problem with free boundary},
journal = {J. Reine Angew. Math.}, volume = {325}, date = {1981}, pages =
{105–144}, issn = {0075-4102}, review = {\MR{618549}}}

  * [3]
BreitD.CianchiA.DieningL.KuusiT.SchwarzacherS.The $p$-laplace system with
right-hand side in divergence form: inner and up to the boundary pointwise
estimatesNonlinear Anal.1532017200–212ISSN 0362-546XReview
MathReviewsDocument@article{Breit, author = {Breit, D.}, author = {Cianchi,
A.}, author = {Diening, L.}, author = {Kuusi, T.}, author = {Schwarzacher,
S.}, title = {The $p$-Laplace system with right-hand side in divergence form:
inner and up to the boundary pointwise estimates}, journal = {Nonlinear
Anal.}, volume = {153}, date = {2017}, pages = {200–212}, issn = {0362-546X},
review = {\MR{3614668}}, doi = {10.1016/j.na.2016.06.011}}

  * [5]
BreitDominicCianchiAndreaDieningLarsKuusiTuomoSchwarzacherSebastianPointwise
calderón-zygmund gradient estimates for the $p$-laplace systemJ. Math. Pures
Appl. (9)1142018146–190ISSN 0021-7824Review
MathReviewsDocument@article{Breit2, author = {Breit, Dominic}, author =
{Cianchi, Andrea}, author = {Diening, Lars}, author = {Kuusi, Tuomo}, author =
{Schwarzacher, Sebastian}, title = {Pointwise Calder\'{o}n-Zygmund gradient
estimates for the $p$-Laplace system}, journal = {J. Math. Pures Appl. (9)},
volume = {114}, date = {2018}, pages = {146–190}, issn = {0021-7824}, review =
{\MR{3801753}}, doi = {10.1016/j.matpur.2017.07.011}}

  * [7]
CarboneLucianoDe ArcangelisRiccardoUnbounded functionals in the calculus of
variationsChapman & Hall/CRC Monographs and Surveys in Pure and Applied
Mathematics125Representation, relaxation, and homogenizationChapman &
Hall/CRC, Boca Raton, FL2002xiv+394ISBN 1-58488-235-2Review
MathReviews@book{Carbone, author = {Carbone, Luciano}, author = {De
Arcangelis, Riccardo}, title = {Unbounded functionals in the calculus of
variations}, series = {Chapman \& Hall/CRC Monographs and Surveys in Pure and
Applied Mathematics}, volume = {125}, note = {Representation, relaxation, and
homogenization}, publisher = {Chapman \& Hall/CRC, Boca Raton, FL}, date =
{2002}, pages = {xiv+394}, isbn = {1-58488-235-2}, review = {\MR{1910459}}}

  * [9]
DanersDanielDomain perturbation for linear and semi-linear boundary value
problemstitle={Handbook of differential equations: stationary partial
differential equations. Vol. VI}, series={Handb. Differ. Equ.},
publisher={Elsevier/North-Holland, Amsterdam}, 20081–81Review
MathReviewsDocument@article{Daners, author = {Daners, Daniel}, title = {Domain
perturbation for linear and semi-linear boundary value problems}, conference =
{title={Handbook of differential equations: stationary partial differential
equations. Vol. VI}, }, book = {series={Handb. Differ. Equ.},
publisher={Elsevier/North-Holland, Amsterdam}, }, date = {2008}, pages =
{1–81}, review = {\MR{2569323}}, doi = {10.1016/S1874-5733(08)80018-6}}

  * [11]
Dall’AcquaAnnaSweersGuidoEstimates for green function and poisson kernels of
higher-order dirichlet boundary value problemsJ. Differential
Equations20520042466–487ISSN 0022-0396Review MathReviewsDocument@article{Anna,
author = {Dall'Acqua, Anna}, author = {Sweers, Guido}, title = {Estimates for
Green function and Poisson kernels of higher-order Dirichlet boundary value
problems}, journal = {J. Differential Equations}, volume = {205}, date =
{2004}, number = {2}, pages = {466–487}, issn = {0022-0396}, review =
{\MR{2092867}}, doi = {10.1016/j.jde.2004.06.004}}

  * [13]
DipierroSerenaKarakhanyanAram L.ValdinociEnricoLimit behaviour of a singular
perturbation problem for the biharmonic operatorAppl. Math.
Optim.8020193679–713ISSN 0095-4616Review
MathReviewsDocument@article{Dipierro1, author = {Dipierro, Serena}, author =
{Karakhanyan, Aram L.}, author = {Valdinoci, Enrico}, title = {Limit behaviour
of a singular perturbation problem for the biharmonic operator}, journal =
{Appl. Math. Optim.}, volume = {80}, date = {2019}, number = {3}, pages =
{679–713}, issn = {0095-4616}, review = {\MR{4026596}}, doi =
{10.1007/s00245-019-09598-7}}

  * [15]
DipierroSerenaKarakhanyanAram L.ValdinociEnricoA free boundary problem driven
by the biharmonic operatorPreprint2018@article{Dipierro2, author = {Dipierro,
Serena}, author = {Karakhanyan, Aram L.}, author = {Valdinoci, Enrico}, title
= {A free boundary problem driven by the biharmonic operator}, journal =
{Preprint}, date = {2018}}

  * [17]
DoktorPavelApproximation of domains with lipschitzian boundaryEnglish, with
Czech and loose Russian summariesČasopis Pěst. Mat.10119763237–255ISSN
0528-2195Review MathReviews@article{Doktor, author = {Doktor, Pavel}, title =
{Approximation of domains with Lipschitzian boundary}, language = {English,
with Czech and loose Russian summaries}, journal = {\v{C}asopis P\v{e}st.
Mat.}, volume = {101}, date = {1976}, number = {3}, pages = {237–255}, issn =
{0528-2195}, review = {\MR{0461122}}}

  * [19]
DuzaarFrankMingioneGiuseppeGradient estimates via non-linear potentialsAmer.
J. Math.133201141093–1149ISSN 0002-9327Review
MathReviewsDocument@article{Duzaar1, author = {Duzaar, Frank}, author =
{Mingione, Giuseppe}, title = {Gradient estimates via non-linear potentials},
journal = {Amer. J. Math.}, volume = {133}, date = {2011}, number = {4}, pages
= {1093–1149}, issn = {0002-9327}, review = {\MR{2823872}}, doi =
{10.1353/ajm.2011.0023}}

  * [21]
DuzaarFrankMingioneGiuseppeGradient estimates via linear and nonlinear
potentialsJ. Funct. Anal.2592010112961–2998ISSN 0022-1236Review
MathReviewsDocument@article{Duzaar2, author = {Duzaar, Frank}, author =
{Mingione, Giuseppe}, title = {Gradient estimates via linear and nonlinear
potentials}, journal = {J. Funct. Anal.}, volume = {259}, date = {2010},
number = {11}, pages = {2961–2998}, issn = {0022-1236}, review =
{\MR{2719282}}, doi = {10.1016/j.jfa.2010.08.006}}

  * [23]
EvansLawrence C.GariepyRonald F.Measure theory and fine properties of
functionsTextbooks in MathematicsRevised editionCRC Press, Boca Raton,
FL2015xiv+299ISBN 978-1-4822-4238-6Review MathReviews@book{EvGar, author =
{Evans, Lawrence C.}, author = {Gariepy, Ronald F.}, title = {Measure theory
and fine properties of functions}, series = {Textbooks in Mathematics},
edition = {Revised edition}, publisher = {CRC Press, Boca Raton, FL}, date =
{2015}, pages = {xiv+299}, isbn = {978-1-4822-4238-6}, review =
{\MR{3409135}}}

  * [25]
Fernandez-RealXavierThe thin obstacle problem: a
surveyPreprint2020@article{FernandezReal, author = {Fernandez-Real, Xavier},
title = {The Thin Obstacle Problem: A Survey}, journal = {Preprint}, date =
{2020}}

  * [27]
GazzolaFilippoGrunauHans-ChristophSweersGuidoPolyharmonic boundary value
problemsLecture Notes in Mathematics1991Positivity preserving and nonlinear
higher order elliptic equations in bounded domainsSpringer-Verlag,
Berlin2010xviii+423ISBN 978-3-642-12244-6Review
MathReviewsDocument@book{Sweers, author = {Gazzola, Filippo}, author =
{Grunau, Hans-Christoph}, author = {Sweers, Guido}, title = {Polyharmonic
boundary value problems}, series = {Lecture Notes in Mathematics}, volume =
{1991}, note = {Positivity preserving and nonlinear higher order elliptic
equations in bounded domains}, publisher = {Springer-Verlag, Berlin}, date =
{2010}, pages = {xviii+423}, isbn = {978-3-642-12244-6}, review =
{\MR{2667016}}, doi = {10.1007/978-3-642-12245-3}}

  * [29]
GilbargDavidTrudingerNeil S.Elliptic partial differential equations of second
orderClassics in MathematicsReprint of the 1998 editionSpringer-Verlag,
Berlin2001xiv+517ISBN 3-540-41160-7Review MathReviews@book{GilTru, author =
{Gilbarg, David}, author = {Trudinger, Neil S.}, title = {Elliptic partial
differential equations of second order}, series = {Classics in Mathematics},
note = {Reprint of the 1998 edition}, publisher = {Springer-Verlag, Berlin},
date = {2001}, pages = {xiv+517}, isbn = {3-540-41160-7}, review =
{\MR{1814364}}}

  * [31]
GiustiEnricoMinimal surfaces and functions of bounded variationMonographs in
Mathematics80Birkhäuser Verlag, Basel1984xii+240ISBN 0-8176-3153-4Review
MathReviewsDocument@book{Giusti, author = {Giusti, Enrico}, title = {Minimal
surfaces and functions of bounded variation}, series = {Monographs in
Mathematics}, volume = {80}, publisher = {Birkh\"{a}user Verlag, Basel}, date
= {1984}, pages = {xii+240}, isbn = {0-8176-3153-4}, review = {\MR{775682}},
doi = {10.1007/978-1-4684-9486-0}}

  * [33]
KilpeläinenT.$p$-Laplacian type equations involving measurestitle={Proceedings
of the International Congress of Mathematicians, Vol. III}, address={Beijing},
date={2002}, publisher={Higher Ed. Press, Beijing}, 2002167–176Review
MathReviews@article{Kilpelainen, author = {Kilpel\"{a}inen, T.}, title =
{$p$-Laplacian type equations involving measures}, conference =
{title={Proceedings of the International Congress of Mathematicians, Vol.
III}, address={Beijing}, date={2002}, }, book = {publisher={Higher Ed. Press,
Beijing}, }, date = {2002}, pages = {167–176}, review = {\MR{1957528}}}

  * [35]
KilpeläinenTeroHölder continuity of solutions to quasilinear elliptic
equations involving measuresPotential Anal.319943265–272ISSN 0926-2601Review
MathReviewsDocument@article{Kilpelainen2, author = {Kilpel\"{a}inen, Tero},
title = {H\"{o}lder continuity of solutions to quasilinear elliptic equations
involving measures}, journal = {Potential Anal.}, volume = {3}, date = {1994},
number = {3}, pages = {265–272}, issn = {0926-2601}, review = {\MR{1290667}},
doi = {10.1007/BF01468246}}

  * [37]
LiebermanGary M.Regularized distance and its applicationsPacific J.
Math.11719852329–352ISSN 0030-8730Review MathReviews@article{Lieberman, author
= {Lieberman, Gary M.}, title = {Regularized distance and its applications},
journal = {Pacific J. Math.}, volume = {117}, date = {1985}, number = {2},
pages = {329–352}, issn = {0030-8730}, review = {\MR{779924}}}

  * [39]
LittmanW.StampacchiaG.WeinbergerH. F.Regular points for elliptic equations
with discontinuous coefficientsAnn. Scuola Norm. Sup. Pisa Cl. Sci.
(3)17196343–77ISSN 0391-173XReview MathReviews@article{Stampacchia, author =
{Littman, W.}, author = {Stampacchia, G.}, author = {Weinberger, H. F.}, title
= {Regular points for elliptic equations with discontinuous coefficients},
journal = {Ann. Scuola Norm. Sup. Pisa Cl. Sci. (3)}, volume = {17}, date =
{1963}, pages = {43–77}, issn = {0391-173X}, review = {\MR{161019}}}

  * [41]
MingioneGiuseppeGradient potential estimatesJ. Eur. Math. Soc.
(JEMS)1320112459–486ISSN 1435-9855Review MathReviewsDocument@article{Mingione,
author = {Mingione, Giuseppe}, title = {Gradient potential estimates}, journal
= {J. Eur. Math. Soc. (JEMS)}, volume = {13}, date = {2011}, number = {2},
pages = {459–486}, issn = {1435-9855}, review = {\MR{2746772}}, doi =
{10.4171/JEMS/258}}

  * [43]
MirandaCarloPartial differential equations of elliptic typeErgebnisse der
Mathematik und ihrer Grenzgebiete, Band 2Second revised edition. Translated
from the Italian by Zane C. MottelerSpringer-Verlag, New York-
Berlin1970xii+370Review MathReviews@book{Miranda, author = {Miranda, Carlo},
title = {Partial differential equations of elliptic type}, series =
{Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 2}, note = {Second
revised edition. Translated from the Italian by Zane C. Motteler}, publisher =
{Springer-Verlag, New York-Berlin}, date = {1970}, pages = {xii+370}, review =
{\MR{0284700}}}

  * [45]
MüllerM.The biharmonic alt-caffarelli problem in
2dPreprint2020Link@article{Marius, author = {Müller, M.}, title = {The
biharmonic Alt-Caffarelli Problem in 2D}, journal = {Preprint}, date = {2020},
url = {https://arxiv.org/abs/2001.04914}}

  * [47]
PonceAugusto C.Elliptic pdes, measures and capacitiesEMS Tracts in
Mathematics23From the Poisson equations to nonlinear Thomas-Fermi
problemsEuropean Mathematical Society (EMS), Zürich2016x+453ISBN
978-3-03719-140-8Review MathReviewsDocument@book{Ponce, author = {Ponce,
Augusto C.}, title = {Elliptic PDEs, measures and capacities}, series = {EMS
Tracts in Mathematics}, volume = {23}, note = {From the Poisson equations to
nonlinear Thomas-Fermi problems}, publisher = {European Mathematical Society
(EMS), Z\"{u}rich}, date = {2016}, pages = {x+453}, isbn =
{978-3-03719-140-8}, review = {\MR{3675703}}, doi = {10.4171/140}}

  * [49]
RudinWalterReal and complex analysisMcGraw-Hill Book Co., New York-Toronto,
Ont.-London1966xi+412Review MathReviews@book{Rudin, author = {Rudin, Walter},
title = {Real and complex analysis}, publisher = {McGraw-Hill Book Co., New
York-Toronto, Ont.-London}, date = {1966}, pages = {xi+412}, review =
{\MR{0210528}}}

  * [51]
RussEmmanuelA survey about the equation ${\rm div}\,u=f$ in bounded domains of
$\mathbb{R}^{n}$Vietnam J. Math.4120134369–381ISSN 2305-221XReview
MathReviewsDocument@article{Russ, author = {Russ, Emmanuel}, title = {A survey
about the equation ${\rm div}\,u=f$ in bounded domains of $\mathbb{R}^n$},
journal = {Vietnam J. Math.}, volume = {41}, date = {2013}, number = {4},
pages = {369–381}, issn = {2305-221X}, review = {\MR{3142402}}, doi =
{10.1007/s10013-013-0034-2}}

  * [53]
TaylorMichael E.Partial differential equations ii. qualitative studies of
linear equationsApplied Mathematical Sciences1162Springer, New
York2011xxii+614ISBN 978-1-4419-7051-0Review MathReviewsDocument@book{Taylor,
author = {Taylor, Michael E.}, title = {Partial differential equations II.
Qualitative studies of linear equations}, series = {Applied Mathematical
Sciences}, volume = {116}, edition = {2}, publisher = {Springer, New York},
date = {2011}, pages = {xxii+614}, isbn = {978-1-4419-7051-0}, review =
{\MR{2743652}}, doi = {10.1007/978-1-4419-7052-7}}

  * [55]
TorresMonicaOn the dual of $BV$title={Contributions of Mexican mathematicians
abroad in pure and applied mathematics}, series={Contemp. Math.},
volume={709}, publisher={Amer. Math. Soc., Providence, RI}, 2018115–129Review
MathReviewsDocument@article{Torres, author = {Torres, Monica}, title = {On the
dual of $BV$}, conference = {title={Contributions of Mexican mathematicians
abroad in pure and applied mathematics}, }, book = {series={Contemp. Math.},
volume={709}, publisher={Amer. Math. Soc., Providence, RI}, }, date = {2018},
pages = {115–129}, review = {\MR{3826951}}, doi = {10.1090/conm/709/14296}}

  * [57]
VerchotaGregoryLayer potentials and regularity for the dirichlet problem for
laplace’s equation in lipschitz domainsJ. Funct. Anal.5919843572–611ISSN
0022-1236Review MathReviewsDocument@article{Verchota, author = {Verchota,
Gregory}, title = {Layer potentials and regularity for the Dirichlet problem
for Laplace's equation in Lipschitz domains}, journal = {J. Funct. Anal.},
volume = {59}, date = {1984}, number = {3}, pages = {572–611}, issn =
{0022-1236}, review = {\MR{769382}}, doi = {10.1016/0022-1236(84)90066-1}}

  * [59]
XiongQiZhangZhenqiuGradient potential estimates for elliptic obstacle
problemsJ. Math. Anal. Appl.49520211124698, 32ISSN 0022-247XReview
MathReviewsDocument@article{Xiong, author = {Xiong, Qi}, author = {Zhang,
Zhenqiu}, title = {Gradient potential estimates for elliptic obstacle
problems}, journal = {J. Math. Anal. Appl.}, volume = {495}, date = {2021},
number = {1}, pages = {124698, 32}, issn = {0022-247X}, review =
{\MR{4172853}}, doi = {10.1016/j.jmaa.2020.124698}}

  * [61]


# Acyclic orientations and poly-Bernoulli numbers

P. J. Cameron
University of St Andrews  C. A. Glass
City University London  R. U. Schumacher
City University London EPSRC Grant EP/P504872/1

###### Abstract

In 1997, Masanobu Kaneko defined _poly-Bernoulli numbers_ , which bear much
the same relation to polylogarithms as Berunoulli numbers do to logarithms. In
2008, Chet Brewbaker described a counting problem whose solution can be
identified with the poly-Bernoulli numbers with negative index, the _lonesum
matrices_.

The main aim of this paper is to give formulae for the number of acyclic
orientations of a complete bipartite graph, or of a complete bipartite graph
with one edge added or removed.

Our formula shows that the number of acyclic orientations of $K_{n_{1},n_{2}}$
is equal to the poly-Bernoulli number $B_{n_{1}}^{(-n_{2})}$. We also give a
simple bijective identification of acyclic orientations and lonesum matrices.

We make some remarks on the context of our result, which are expanded in
another paper.

##  1 Introduction

We begin by giving a few definitions we will use throughout. An _acyclic
orientation_ of an undirected graph $G$ is an assignment of direction to each
edge in such a way that we obtain no directed cycles, thus obtaining an
acyclic directed graph. Let $a(G)$ be the number of acyclic orientations of a
graph $G$. There is always at least one acyclic orientation of $G$ obtained by
ordering the vertices of $G$ and orienting edges from smaller to larger vertex
index. Next we define $K_{n_{1},n_{2}}$ to be the _complete bipartite graph on
$n_{1}+n_{2}$ vertices_ to be the graph whose vertices are partitioned into
sets of sizes $n_{1}$ and $n_{2}$, having all possible edges between these two
sets and none within them. We denote by $S(n,k)$ the _Stirling number of the
second kind_ which counts the number of ways to partition a set of $n$ objects
into $k$ non-empty subsets.

##  2 The number of acyclic orientations of certain graphs

Our main results are given in the next three theorems.

###### Theorem 2.1

The number of acyclic orientations of the complete bipartite graph
$K_{n_{1},n_{2}}$ is

$\sum_{k=1}^{\min\\{n_{1}+1,n_{2}+1\\}}(k-1)!^{2}S(n_{1}+1,k)S(n_{2}+1,k),$

where $S$ denotes Stirling numbers of the second kind.

###### Theorem 2.2

Let $G$ be the graph obtained from $K_{n_{1},n_{2}}$ by adding an edge $e_{1}$
joining two vertices in the bipartite block of size $n_{1}$, where $n_{1}>1$.
Then

$a(G)=a(K_{n_{1}n_{2}}+e_{1})=a(K_{n_{1},n_{2}})+a(K_{n_{1}-1,n_{2}}).$

###### Theorem 2.3

Let $G$ be the graph obtained by deleting an edge from $K_{n_{1},n_{2}}$. Then

$a(G)=a(K_{n_{1}n_{2}}-e)=a(K_{n_{1},n_{2}})-\frac{1}{2}X,$

where

$\displaystyle X=1+\sum_{k=2}^{\min\\{n_{1},n_{2}\\}+1}\quad((k-2)!)^{2}\,\,$
$\displaystyle[(2k-3)S(n_{1}+1,k)S(n_{2}+1,k)$
$\displaystyle-(k-2)(S(n_{1}+1,k)S(n_{2},k)+S(n_{1},k)S(n_{2}+1,k))$
$\displaystyle-S(n_{1},k)S(n_{2},k)\,].$

We will prove these three theorems in the next three subsections.

###  2.1 Proof of Theorem 2.1

Let $A$ and $B$ be the two bipartite blocks; we will imagine their vertices as
coloured amber and blue respectively. Now any acyclic orientation of the graph
can be obtained by ordering the vertices and making the edges point from
smaller to greater. If we do this, we will have alternating amber and blue
intervals; the ordering within each interval is irrelevant in identifying the
orientation, but the ordering of the intervals themselves matters.

In terms of structure for a given orientation, call two points $a_{1},a_{2}\in
A$ _equivalent_ if the orientations of $\\{a_{1},b\\}$ and $\\{a_{2},b\\}$ are
the same for all $b\in B$. Points of $A$ are equivalent if and only if they
are not separated by a point of $B$ in any ordering giving rise to the acyclic
orientation. Similarly for $B$. This gives us the intervals, which are
interleaved.

It is left to count alternating intervals. To get around the problem that the
first interval in the ordering might be in either $A$ or $B$, and similarly
for the last interval, we use the following trick. Add a dummy amber vertex
$a_{0}$ to $A$ and a dummy blue vertex $b_{0}$ to $B$. Now partition
$A\cup\\{a_{0}\\}$ and $B\cup\\{b_{0}\\}$ into the same number, say $k$, of
intervals. This can be done in $S(n_{1}+1,k)S(n_{2}+1,k)$ ways. Now we order
the intervals so that

  * •

the interval containing $a_{0}$ is first;

  * •

the colours of the intervals alternate;

  * •

the interval containing $b_{0}$ is last.

This can be done in $(k-1)!^{2}$ ways. Finally, delete the dummy points.

Summing over $k$ gives the total number claimed.

###  2.2 Proof of Theorem 2.2

Let $G$ be the graph consisting of $K_{n_{1},n_{2}}$ (with bipartite blocks
$A$ and $B$) together with an edge joining two vertices in $A$. Now any
acyclic orientation of $K_{n_{1},n_{2}}$ can be extended to either one or two
acyclic orientations of $G$; so $a(G)=A(K_{n_{1},n_{2}})+Z$, where $Z$ is the
number of acyclic orientations of $K_{n_{1},n_{2}}$ for which the added edge
$\\{a_{1},a_{2}\\}$ can be oriented in either direction.

The edge $\\{a_{1},a_{2}\\}$ can be oriented in either direction without
creating a cycle, iff $\\{a_{1},b\\}$ has the same orientations as
$\\{a_{2},b\\}$, for each vertex $b$ of $B$. Thus, we are effectively finding
an acyclic orientation of $K_{n_{1}-1,n_{2}}$. So $Z=a(K_{n_{1}-1,n_{2}})$.

###  2.3 Proof of Theorem 2.3

Deleting an edge is a little more difficult. Suppose that we calculate the
number $X$ of acyclic orientations of $K_{n_{1},n_{2}}$ which remain acyclic
when a given edge $e=\\{a,b\\}$ is flipped. (This number clearly does not
depend on the chosen edge.) Then the number of acyclic orientations of
$G=K_{n_{1},n_{2}}-e$ is $a(K_{n_{1},n_{2}})-\frac{1}{2}X$. For if we call
this number $Y$, then $\frac{1}{2}X$ of the acyclic orientations of $G$ extend
to two acyclic orientations of $K_{n_{1},n_{2}}$, while the remaining
$Y-\frac{1}{2}X$ extend to a unique acyclic orientation; so
$a(K_{n_{1},n_{2}})=X+(Y-\frac{1}{2}X)$, giving the result. It thus remains to
verify the formula for $X$ given in the statement of the theorem.

We follow the construction in the proof of Theorem 2.1. The edge $e$ can be
flipped in an orientation if and only if the part of the partition of $B$
containing $b$ immediately precedes or follows the part of the partition of
$A$ containing $a,$ in the corresponding vertex ordering. (If a part of $B,$
containing a vertex $b^{\prime}$ say, and a part of $A,$ containing a vertex
$a^{\prime},$ intervene, then we have arcs $(a,b^{\prime})$,
$(b^{\prime},a^{\prime})$ and $(a^{\prime},b)$, so the arc $(a,b)$ is forced.
Similarly in the other case.)

If $k=1$, then all edges are directed from $A$ to $B$, and $(a,b)$ can be
flipped. So this contributes $1$ to the sum.

Suppose that $k>2$. We distinguish four cases, according as $a_{0}$ and $a$
are or are not in the same part, and similarly for $b_{0}$ and $b$. Of the
$S(n_{1}+1,k)$ partitions of $A\cup\\{a_{0}\\}$, $S(n_{1},k)$ have $a_{0}$ and
$a$ in the same part: this is found by regarding $a_{0}$ and $a$ as the same
element, partitioning the resulting set of size $n_{1}$, and then separating
them again.

#### Case 1

$a_{0}$ and $a$ in the same part, $b_{0}$ and $b,$ in the same part. Since
$k>1$, the parts containing $a_{0}$ and $b_{0},$ and hence the parts
containing $a$ and $b,$ are not consecutive, so the contribution from this
case is $0$.

#### Case 2

$a_{0}$ and $a$ in the same part, $b_{0}$ and $b$ not. There are
$S(n_{1},k)(S(n_{2}+1,k)-S(n_{2},k))$ pairs of partitions with this property.
Now the part containing $b$ must come immediately after the part containing
$a$, so there are only $(k-2)!$ orderings of the parts of $B$, while still
$(k-1)!$ for the parts of $A$.

#### Case 3

$b_{0}$ and $b$ in the same part, $a_{0}$ and $a$ not. This case is the same
as Case 2, with $n_{1}$ and $n_{2}$ interchanged.

#### Case 4

$a_{0}$ and $a$ in different parts, $b_{0}$ and $b$ in different parts. There
are $(S(n_{1}+1,k)-S(n_{1},k))(S(n_{2}+1,k)-S(n_{2},k))$ such pairs of
partitions. Now the parts containing $a$ and $b$ must be adjacent, so must
occur as $(3,2),(3,4),(5,4),\ldots,$ or $(2k-1,2k-2)$ in the ordering of
parts: there are $(2k-3)$ possibilities. Once one possibility has been chosen,
the position of two parts for both $A$ and $B$ are fixed, so there are
$((k-2)!)^{2}$ possible orderings.

Combining all of the above terms and rearranging, gives the value of $X,$
completing the proof.

###  2.4 Some numerical values

It is instructive to view the numerical values of the number of acyclic
orientations of bipartite graphs $K_{n_{1},n_{2}}$. When $n_{1}=1$, the graph
is a tree, and we have $a(K_{1,n})=2^{n}$. For $n_{1}$ between $2$ and $7$
Table 1 gives the number of acyclic orientations of the complete bipartite
graphs and Tables 2 and 3 those graphs with an edge added or removed,
calculated from the formulae in Theorems 2.1, 2.2 and 2.3. In Table 2 for
$K_{n_{1},n_{2}}+e_{1}$, the added edge $e_{1}$ is in the bipartite block of
size $n_{1}$. All of these values have been checked by calculating the
chromatic polynomial of the graph. (A theorem of Stanley [5] asserts that the
number of acyclic orientations of an $n$-vertex graph $G$ is
$(-1)^{n}P_{G}(-1)$, where $P_{G}$ is the chromatic polynomial of $G$.)

$\begin{array}[]{|c||r|r|r|r|r|r|}\hline\cr n_{1}\setminus
n_{2}&\lx@intercol\hfil 2\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
3\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
4\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
5\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
6\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
7\hfil\lx@intercol\vrule\lx@intercol\\\ \hline\cr\hline\cr
2&14&46&146&454&1394&4246\\\ \hline\cr 3&&230&1066&4718&20266&85310\\\
\hline\cr 4&&&6902&41506&237686&1315666\\\ \hline\cr
5&&&&329462&2441314&17234438\\\ \hline\cr 6&&&&&22934774&22934774\\\ \hline\cr
7&&&&&&2193664790\\\ \hline\cr\end{array}$ Table 1: The number of acyclic
orientations of $K_{n_{1},n_{2}}$ $\begin{array}[]{|c|r|r|r|r|r|r|}\hline\cr
n_{1}\setminus n_{2}&\lx@intercol\hfil
2\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
3\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
4\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
5\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
6\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
7\hfil\lx@intercol\vrule\lx@intercol\\\ \hline\cr 2&18&54&162&486&1458&4374\\\
\hline\cr 3&60&276&1212&5172&21660&89556\\\ \hline\cr
4&192&1296&7968&46224&257952&1400976\\\ \hline\cr
5&600&5784&48408&370968&2679000&18550104\\\ \hline\cr
6&1848&24984&279192&2770776&25376088&219463704\\\ \hline\cr
7&5640&105576&1553352&19675752&225164040&2395894056\\\ \hline\cr\end{array}$
Table 2: The number of acyclic orientations of $K_{n_{1},n_{2}}+e_{1}$
$\begin{array}[]{|c|r|r|r|r|r|r|}\hline\cr n_{1}\setminus
n_{2}&\lx@intercol\hfil 2\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
3\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
4\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
5\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
6\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
7\hfil\lx@intercol\vrule\lx@intercol\\\ \hline\cr 2&8&28&92&292&908&2788\\\
\hline\cr 3&&152&736&3344&14608&62192\\\ \hline\cr
4&&&5000&30952&180632&1012936\\\ \hline\cr 5&&&&253352&1915672&13715144\\\
\hline\cr 6&&&&&18381608&164501368\\\ \hline\cr 7&&&&&&1812141032\\\
\hline\cr\end{array}$ Table 3: The number of acyclic orientations of
$K_{n_{1},n_{2}}-e$

Note that as well as the formula $a(K_{1,n})=2^{n}$ we have
$a(K_{2,n}+e_{1})=2\cdot 3^{n}$. This is because the graph $K_{2,n}+e_{1}$
consists of $n$ triangles sharing a common edge $e_{1}$, there are two ways to
orient the edge $e_{1}$, and then three ways to choose the orientations of the
remaining edges of each triangle to avoid a cycle. Putting these two results
together in Theorem 2.2 gives us $a(K_{2,n})=2\cdot 3^{n}-2^{n}$. Is there a
closed formula for $a(K_{n_{1},n_{2}})$ in general?

##  3 Poly-Bernoulli numbers and lonesum matrices

The formulae for the number of acyclic orientations of a bipartite graph
$K_{n_{1},n_{2}}$ in Theorem 2.1 appear to be obscure. However, we now show
that it is actually the poly-Bernoulli number in the variables $n_{1}$ and
$n_{2}$, as defined by Kaneko, for which another combinatorial interpretation
was found by Brewbaker. In this section we explain the connections.

###  3.1 Poly-Bernoulli numbers

This is only a very brief introduction to the poly-Bernoulli numbers, which
were introduced by Masanobu Kaneko [3] in 1997. Kaneko gave the following
definitions. Let

$\mathrm{Li}_{k}(z)=\sum_{m=1}^{\infty}\frac{z^{m}}{m^{k}},$

and let

$\frac{\mathrm{Li}_{k}(1-\mathrm{e}^{-x})}{1-\mathrm{e}^{-x}}=\sum_{n=0}^{\infty}B_{n}^{(k)}\frac{x^{n}}{n!}.$

The numbers $B_{n}^{(k)}$ are the _poly-Bernoulli numbers of order $k$_.
Kaneko gave a couple of nice formulae for the poly-Bernoulli numbers of
negative order, of which one is relevant here.

######  Theorem 3.1 (Kaneko)

$B_{n}^{(-m)}=\sum_{j=0}^{\min(n,m)}(j!)^{2}S(n+1,j+1)S(m+1,j+1).$

This formula has the (entirely non-obvious) corollary that these numbers have
a symmetry property: $B_{n}^{(-m)}=B_{m}^{(-n)}$ for all non-negative integers
$n$ and $k$. Kaneko’s Theorem together with Theorem 2.1 gives the following
result.

###### Theorem 3.2

The number of acyclic orientations of $K_{n_{1},n_{2}}$ is the poly-Bernoulli
number $B_{n_{1}}^{(-n_{2})}=B_{n_{2}}^{(-n_{1})}$.

###  3.2 Lonesum matrices

Another combinatorial interpretation was given by Chad Brewbaker [1] in 2008.
A zero-one matrix is a _lonesum matrix_ if it is uniquely determined by its
row and column sums. Clearly a lonesum matrix cannot contain either
$\pmatrix{1&0\cr 0&1\cr}$ or $\pmatrix{0&1\cr 1&0\cr}$ as a submatrix (in not
necessarily consecutive rows or columns). (Since if one such submatrix
occurred it could be flipped into the other without changing the row and
column sums.) Ryser [4] showed that, conversely, a matrix containing neither
of these is a lonesum matrix. Brewbaker showed that the number of $n_{1}\times
n_{2}$ lonesum matrices is given by the poly-Bernoulli number
$B_{n_{1}}^{(-n_{2})}$. We give the simple argument why this number is equal
to the number of acyclic orientations of $K_{n_{1},n_{2}}$.

In one direction, number the vertices in the bipartite blocks from $1$ to
$n_{1}$ (in $A$) and from $1$ to $n_{2}$ (in $B$). Now given an orientation of
the graph, we can describe it by a matrix whose $(i,j)$ entry is $1$ if the
edge from vertex $i$ of $A$ to vertex $j$ of $B$ goes in the direction from
$A$ to $B$, and $0$ otherwise. The two forbidden submatrices for lonesum
matrices correspond to directed $4$-cycles; so any acyclic orientation gives
us a lonesum matrix.

Conversely, if an orientation of a complete bipartite graph contains no
directed $4$-cycles, then it contains no directed cycles at all. For suppose
that there are no directed $4$-cycles, but there is a directed cycle
$(a_{1},b_{1},a_{2},b_{2},\ldots,a_{k},b_{k},a_{1})$. Then the edge between
$a_{1}$ and $b^{\prime}$ must be directed from $a_{1}$ to $b^{\prime}$, since
otherwise there would be a $4$-cycle $(a_{1},b_{1},a_{2},b_{2},a_{1})$. But
then we have a shorter directed cycle
$(a_{1},b_{2},a_{3},\ldots,b_{k},a_{1})$. Continuing this shortening process,
we would eventually arrive at a directed $4$-cycle, a contradiction. (This
simply says that the cycle space of the complete bipartite graph is generated
by $4$-cycles.)

##  4 Maximizing the number of acyclic orientations

We believe that the graphs $K_{n_{1},n_{2}}$, for $|n_{1}-n_{2}|\leq 1$,
maximise the number of acyclic orientations over the class of all graphs with
the same numbers of vertices and edges as these graphs. The evidence and
partial results on this are presented in a companion paper [2].

##  5 Acknowledgements

Robert Schumacher was funded by EPSRC Grant EP/P504872/1.

## References

  * [1] Chad Brewbaker, A combinatorial interpretation of the poly-Bernoulli numbers and two Fermat analogues, Integers 8 (2008), #A02 (9pp.)
  * [2] P. J. Cameron, C. A. Glass and R. U. Schumacher, in preparation.
  * [3] Masanobu Kaneko, Poly-Bernoulli numbers, Journal de Théorie des Nombres de Bordeaux 9 (1997), 221–228.
  * [4] Herbert J. Ryser, Combinatorial properties of matrices of zeros and ones, Canadian J. Math. 9 (1957), 371–377.
  * [5] Richard Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171–178.


# On a kinematic proof of Andoyer variables canonicity

Anatoly Neishtadt

###### Abstract

We present a kinematic proof that the Andoyer variables in rigid body dynamics
are canonical. This proof is based on the approach of “virtual rotations” by
H. Andoyer. The difference from the original proof by Andoyer is that we do
not assume that the fixed in body frame is the frame of principal moments of
inertia, and do not use explicit formulas for the kinetic energy of the body
that include moments of inertia.

##  1 Introduction

The canonical Andoyer variables in rigid body dynamics were introduced by H.
Andoyer in [1, 2]. Wide use of these variables started after works of V.V.
Beletskii [4], who invented closely related variables, and A. Deprit [5], who
invented the same variables as Andoyer and used them to represent the free
rotation of rigid body in the phase plane. Andoyer proved that his variables
are canonical using a kinematic approach based on “virtual rotations”. Deprit
used formulas of spherical trigonometry in his proof that the variables are
canonical. Proof of canonicity of Andoyer variables in [6] is based on the
representation of infinitesimal rotation from the absolute frame of reference
to the fixed in body frame via the Andoyer angles. In this note we present a
proof based on the original approach by Andoyer. Unlike [1, 2, 5] we do not
assume that the fixed in body frame is the frame of principal moments of
inertia and do not use explicit formulas for the kinetic energy of the body
that include moments of inertia. We do not calculate the infinitesimal
rotation as in [6] either. Our proof uses just general definitions of
canonical transformations, kinetic energy and angular momentum as well as
properties of the mixed product of vectors.

A review of works on canonical variables in rigid body dynamics prior to
Andoyer’s studies (F. J. Richelot (1850), J. A. Serret (1866), R. Radau
(1869), F. Tisserand (1889)) is given in [6, 7].

##  2 Coordinate frames. Definition of the Andoyer variables

Consider the classical problem of motion of a rigid body about a fixed point
(e.g., [3, 8]). Let $OXYZ$ be an absolute Cartesian frame of references, Fig.
1, a. Let $Oxyz$ be a fixed in body Cartesian frame (e.g., the frame of
principal moments of inertia of the body for the point $O$ as in [1, 2, 5]),
Fig. 1, b. Denote $\vec{G}$ the angular momentum of the body. Define a
Cartesian frame of reference $O\xi\eta\zeta$ as follows, Fig.1, a, b. Axis
$O\zeta$ is directed along $\vec{G}$. Axis $O\xi$ is in the plane $OZ\zeta$.
Axis $O\eta$ is orthogonal to the plane $O\xi\zeta$. The canonical Andoyer
variables are $L,G,\Theta,l,g,\vartheta$ (we a use slightly modified notation
from [5]). Angles $l,g,\vartheta$ are shown in Fig. 1, a, b, $L$ is the
projection of $\vec{G}$ onto axis $Oz$, $G$ is the absolute value of
$\vec{G}$, $\Theta$ is the projection of $\vec{G}$ onto axis $OZ$.

Figure 1: Coordinate frames.

Denote $\vec{e}_{X},\vec{e}_{Y},\vec{e}_{Z}$,
$\vec{e}_{x},\vec{e}_{y},\vec{e}_{z}$ and
$\vec{e}_{1},\vec{e}_{2},\vec{e}_{3}$ unit coordinate vectors of frames
$OXYZ$, $Oxyz$ and $O\xi\eta\zeta$, respectively. We denote
$\vec{a}\cdot\vec{b}$ and $\vec{a}\times\vec{b}$ the scalar (“dot”) and the
vector (“cross”) products of $\vec{a}$ and $\vec{b}$.

##  3 Canonicity condition

Let $q_{1},q_{2},q_{3}$ be any generalised coordinates that characterise
position of the frame $Oxyz$ with respect to the absolute frame $OXYZ$ (e.g.,
$q_{1},q_{2},q_{3}$ could be the Euler angles). The kinetic energy of the body
$T$ is a function of these coordinates and their velocities:
$T=T(q_{1},q_{2},q_{3},\dot{q}_{1},\dot{q}_{2},\dot{q}_{3})$. Denote
$p_{1},p_{2},p_{3}$ the momenta canonically conjugate to these coordinates,
$p_{j}=\partial T/\partial\dot{q}_{j},\ j=1,2,3$. Then
$q_{1},q_{2},q_{3},p_{1},p_{2},p_{3}$ is a system of canonical variables for
the considered problem. Express the Andoyer variables via
$q_{1},q_{2},q_{3},p_{1},p_{2},p_{3}$. To prove that this transformation is
canonical we should check that (e.g., [3], p. 241)

$p_{1}dq_{1}+p_{2}dq_{2}+p_{3}dq_{3}=Ldl+Gdg+\Theta d\vartheta.$ (3.1)

This would prove that the Andoyer variables are canonical.

As it is traditional in Analytical Dynamics, consider the rigid body as a
system of $N$ material points. Let $m_{i},\vec{r}_{i},\ i=1,2,\ldots,N$ be
masses and position vectors in the absolute frame of these points. Express
position vectors via coordinates $q_{1},q_{2},q_{3}$:
$\overline{r}_{i}=\overline{r}_{i}(q_{1},q_{2},q_{3})$. Then

$\displaystyle
d{\overline{r}_{i}}=\sum_{j=1}^{3}\frac{\partial{\overline{r}_{i}}}{\partial
q_{j}}dq_{j},$ (3.2)
$\displaystyle\dot{\overline{r}_{i}}=\sum_{j=1}^{3}\frac{\partial{\overline{r}_{i}}}{\partial
q_{j}}\dot{q}_{j}.$

and

$\frac{\partial\dot{\overline{r}_{i}}}{\partial\dot{q}_{j}}=\frac{\partial{\overline{r}_{i}}}{\partial
q_{j}}$

(this is a standard relation used in derivation of the Lagrange equations from
the D’Alembert principle, e.g., [8], p. 20).

The angular momentum $\vec{G}$ and the kinetic energy of the body $T$ are

$\vec{G}=\sum_{i=1}^{N}m_{i}(\vec{r}_{i}\times\dot{\overline{r}_{i}}),\
T=\frac{1}{2}\sum_{i=1}^{N}m_{i}(\dot{\overline{r}_{i}}\cdot\dot{\overline{r}_{i}}).$

Consider identities

$\displaystyle\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot
d{\overline{r}_{i}}=\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot\sum_{j=1}^{3}\frac{\partial{\overline{r}_{i}}}{\partial
q_{j}}dq_{j}=\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot\sum_{j=1}^{3}\frac{\partial\dot{\overline{r}_{i}}}{\partial\dot{q}_{j}}dq_{j}$
(3.3)
$\displaystyle=\sum_{j=1}^{3}\left(\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot\frac{\partial\dot{\overline{r}_{i}}}{\partial\dot{q}_{j}}\right)dq_{j}=\sum_{j=1}^{3}\frac{\partial}{\partial\dot{q}_{j}}\left(\frac{1}{2}\sum_{i=1}^{N}m_{i}(\dot{\overline{r}_{i}}\cdot\dot{\overline{r}_{i}})\right)dq_{j}$
$\displaystyle=\sum_{j=1}^{3}\frac{\partial
T}{\partial\dot{q}_{j}}dq_{j}=p_{1}dq_{1}+p_{2}dq_{2}+p_{3}dq_{3}.$

In view of (3.1) this implies that to prove the canonicity of the Andoyer
variables we have to show that

$\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot
d{\overline{r}_{i}}=Ldl+Gdg+\Theta d\vartheta.$ (3.4)

##  4 The check of canonicity condition (3.4)

Express position vectors of material points via the Andoyer variables. Note
that $\overline{r}_{i}$ depends on $L,G,\Theta$ via angles $\chi,\rho$,
$L=G\cos\chi,\Theta=G\cos\rho$. Thus
$\overline{r}_{i}=\overline{r}_{i}(l,g,\vartheta,\chi,\rho),\ i=1,2.\ldots,N$.
Calculate $d{\overline{r}_{i}}$ and substitute the obtained expressions into
the left hand side of (3.4). We get

$\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot
d{\overline{r}_{i}}=k_{l}dl+k_{g}dg+k_{\vartheta}d\vartheta+k_{\chi}d{\chi}+k_{\rho}d\rho$
(4.1)

with some coefficients $k_{l},k_{g},\ldots,k_{\rho}$. Calculate these
coefficients.

  * •

Put $dl=1$ and give value 0 to all other differentials in the right hand side
of (4.1). Then $d\vec{r}_{i}$ should be equal to the velocity of the point
with the position vector $\vec{r}_{i}$ when the rigid body rotates
(counterclockwise) about the axis $Oz$ with the angular speed 1:
$d\vec{r}_{i}=\vec{e}_{z}\times\vec{r}_{i}$. Then

$k_{l}=\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot(\vec{e}_{z}\times\vec{r}_{i})=(\sum_{i=1}^{N}m_{i}\vec{r}_{i}\times\dot{\overline{r}_{i}})\cdot\vec{e}_{z}=\vec{G}\cdot\vec{e}_{z}=L$

because $L$ is the projection of $\vec{G}$ onto the axis $Oz$.

  * •

Put $dg=1$ and give value 0 to all other differentials in the right hand side
of (4.1). Then $d\vec{r}_{i}$ should be equal to the velocity of the point
with the position vector $\vec{r}_{i}$ when the rigid body rotates about the
axis $O\zeta$ with the angular speed 1:
$d\vec{r}_{i}=\vec{e}_{3}\times\vec{r}_{i}$. Then

$k_{g}=\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot(\vec{e}_{3}\times\vec{r}_{i})=(\sum_{i=1}^{N}m_{i}\vec{r}_{i}\times\dot{\overline{r}_{i}})\cdot\vec{e}_{3}=\vec{G}\cdot\vec{e}_{3}=G$

because $\vec{e}_{3}$ is directed along $\vec{G}$.

  * •

Put $d\vartheta=1$ and give value 0 to all other differentials in the right
hand side of (4.1). Then $d\vec{r}_{i}$ should be equal to the velocity of the
point with the position vector $\vec{r}_{i}$ when the rigid body rotates about
the axis $OZ$ with the angular speed 1:
$d\vec{r}_{i}=\vec{e}_{Z}\times\vec{r}_{i}$. Then

$k_{\vartheta}=\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot(\vec{e}_{Z}\times\vec{r}_{i})=(\sum_{i=1}^{N}m_{i}\vec{r}_{i}\times\dot{\overline{r}_{i}})\cdot\vec{e}_{Z}=\vec{G}\cdot\vec{e}_{Z}=\Theta$

because $\Theta$ is the projection of $\vec{G}$ onto the axis $OZ$.

  * •

Put $d\chi=1$ and give value 0 to all other differentials in the right hand
side of (4.1). Then $d\vec{r}_{i}$ should be equal to the velocity of the
point with the position vector $\vec{r}_{i}$ when the rigid body rotates about
the node line $O\kappa$ in Fig. 1, b with the angular speed 1:
$d\vec{r}_{i}=\vec{n}\times\vec{r}_{i}$, where $\vec{n}$ is the unit vector of
the axis $O\kappa$. Then

$k_{\chi}=\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot(\vec{n}\times\vec{r}_{i})=(\sum_{i=1}^{N}m_{i}\vec{r}_{i}\times\dot{\overline{r}_{i}})\cdot\vec{n}=\vec{G}\cdot\vec{n}=0$

because $\vec{n}$ is orthogonal to $\vec{G}$.

  * •

Put $d\rho=1$ and give value 0 to all other differentials in the right hand
side of (4.1). Then $d\vec{r}_{i}$ should be equal to the velocity of the
point with the position vector $\vec{r}_{i}$ when the rigid body rotates about
the axis $O\eta$ with the angular speed 1:
$d\vec{r}_{i}=\vec{e}_{2}\times\vec{r}_{i}$. Then

$k_{\rho}=\sum_{i=1}^{N}m_{i}\dot{\overline{r}_{i}}\cdot(\vec{e}_{2}\times\vec{r}_{i})=(\sum_{i=1}^{N}m_{i}\vec{r}_{i}\times\dot{\overline{r}_{i}})\cdot\vec{e}_{2}=\vec{G}\cdot\vec{e}_{2}=0$

because $\vec{e}_{2}$ is orthogonal to $\vec{G}$.

Thus we have $k_{l}=L,k_{g}=G,k_{\vartheta}=\Theta,k_{\chi}=k_{\rho}=0$. This
proves the canonicity condition (3.4).

##  5 Conlusion

A kinematic proof is given that the Andoyer variables in rigid body dynamics
are canonical. The proof is based on the approach of “virtual rotations” by
Andoyer. The difference from the original proof by Andoyer is that we do not
assume that the fixed in body frame is the frame of principal moments of
inertia, and do not use explicit formulas for the kinetic energy of the body
that include moments of inertia.

## References

  * [1] Andoyer H. Sur les problèmes fondamenteaux de la mécanique céleste. Bull. Astron. Ser. I, 32, 5–18 (1915)
  * [2] Andoyer H. Cours de Mécanique Céleste, vol. I. Gauthier-Villars, Paris (1923)
  * [3] Arnold V. I. Mathematical Methods of Classical Mechanics: Graduate Texts in Mathematics 60. Springer-Verlag, New York (1978)
  * [4] Beletskii V.V. Motion of an Artificial Satellite About Its Center of Mass. NASA TTF-429 (1966)
  * [5] Deprit A. Free rotation of the rigid body studied in the phase plane. American Journal of Physics, 35, 424–428 (1967)
  * [6] Deprit A., Elipe A. Complete reduction of the Euler-Poinsot problem. Journal of the Astronautical Sciences, 35, 603–628 (1993)
  * [7] Gurfil P., Elipe A., Tangren W., Efroimsky M. The Serret-Andoyer formalism in rigid-body dynamics: I. Symmetries and perturbations. Regular and Chaotic Dynamics, 12, 389–425 (2007)
  * [8] Goldstein H., Poole C. P., Safko J. L. Classical Mechanics (3rd ed.). Addison-Wesley, Boston (2001)

Anatoly Neishtadt

Department of Mathematical Sciences

Loughborough University, Loughborough LE11 3TU, United Kingdom

Space Research Institute, Moscow 117997, Russia

E-mail<EMAIL_ADDRESS>