You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'I adapt a recently introduced method for integrating over the unitary group (S. Aubert and C.S. Lam, J.Math.Phys. 44, 6112-6131 (2003)) to the orthogonal group. I derive explicit formulas for a number of one, two and three-vector integrals, as well as recursion formulas for more complicated cases.'
author:
- Daniel Braun
bibliography:
- '../mybibs\_bt.bib'
title: Invariant integration over the orthogonal group
---

Introduction
============

Integrals over compact Lie groups arise in physics naturally through applications of random matrix theory [@Guhr98], which plays an important role in various fields of physics, ranging from nuclear theory [@Ullah64], quantum chaos [@Haake91] and transport in mesoscopic devices [@Baranger94], to quantum information theory [@Zyczkowski03]. A new application arose recently in the latter field from the study of statistics of interference in quantum algorithms [@Braun06]. Quantum algorithms can always be represented as real matrices by spending one more qubit (i.e. doubling the size of the Hilbert space), which labels the real or imaginary part of the wave function [@Shi02; @Aharonov03], and the question was posed how this influences the amount of interference necessary in the quantum algorithm compared to a unitary representation [@Arnaud06]. Examining the statistics of interference drawn from the Haar orthogonal ensemble, i.e. the ensemble of orthogonal matrices with a flat distribution according to the Haar measure of the orthogonal group, then leads naturally to consider integrals of monomials of matrix elements over the orthogonal group $O(N)$.

Formulas for one-vector integrals were obtained earlier by Ullah [@Ullah64] and by Mehta [@Mehta91]. An $n-$vector integral is defined as an integral containing elements from only $n$ columns (or from $n$ rows) of the orthogonal matrix. Prosen and co–workers introduced an asymptotic method which works well for large $N$ [@Prosen02]. The problem was solved in principal by Gorin [@Gorin02], who derived recursion relations connecting $n-$vector integrals to $(n-1)-$vector integrals. While the method is general, we will see below that explicit formulas can be obtained in a much easier way in various simple but important cases of integrals of low degree (and/or a small number of vectors). A number of interesting properties of integrals over the orthogonal (as well as the unitary and symplectic) group were also derived in [@Collins04], based on the use of Brauer algebras.

Recently, Aubert and Lam introduced a very elegant method for integration over the unitary group $U(N)$ based solely on the unitary constraint and the invariance of the Haar measure under unitary transformations [@Aubert03]. This method is very powerful, and allowed the authors to obtain explicit formulas for the lowest order integrals, including all one-vector integrals, all two vector integrals with up to three different matrix elements taken to arbitrary powers, and all two and three-vector integrals up to order 6 (the order means here the number of matrix elements in the monomial to be integrated). Recursion relations can be obtained to reduce higher order integrals to these basic integrals. In the present paper I adapt the method of invariant integration to the orthogonal group, and derive the corresponding basic integrals and recursion formulae.

Integrals over the orthogonal group
===================================

Consider orthogonal, real $N\times N$ matrices $O$ with matrix elements $O_{ij}$, $1\le i,j\le N$. We will be interested in integrals of the type $$\label{defI}
{{\cal I}}_{i_1j_1\ldots i_pj_p}\equiv\int(dO)O_{i_1j_1}\ldots O_{i_pj_p}\,,$$ where the order $p$ of the integral is some positive integer, and $(dO)$ denotes the Haar invariant measure of the orthogonal group $O(N)$, normalized to $\int(dO)=1$. These integrals can be calculated based solely on

-   the orthogonality relation $O^TO={\bf 1}=OO^T$ (where $^T$ denotes the transposed matrix), or explicitly $$\label{ortho}
    \sum_{i=1}^NO_{ij}O_{ik}=\delta_{jk}=\sum_{i=1}^NO_{ji}O_{ki}\,,$$ where $\delta_{jk}$ stands for the Kronecker-delta;

-   and the invariance of the Haar measure, meaning that for any function $f(O)$ and an arbitrary (real) orthogonal ($N\times N$) matrix $V$, $$\label{inv}
    \int(dO)f(O)=\int(dO)f(VO)=\int(dO)f(OV)\,.$$ Here we will use for $f(O)$ the monomial $$\label{f}
    f(O)=\prod_{\lambda=1}^p O_{i_\lambda j_\lambda}\equiv O_{IJ}\,,$$ and we have introduced the notation $O_{IJ}$, where $I=\{i_1,\ldots,i_p\}$, $J=\{j_1,\ldots,j_p\}$. Correspondingly, ${{\cal I}}_{i_1j_1\ldots i_pj_p}$ will be abbreviated as ${{\cal I}}_{i_1j_1\ldots i_pj_p}\equiv {{\cal I}}(O_{IJ})$.

Relations from invariance
=========================

A number of powerful relations are obtained from choosing different explicit orthogonal matrices, under which ${{\cal I}}(O_{IJ})$ must be invariant.

Global sign change {#gsc}
------------------

The simplest example consist of $V=-{\bf 1}$, i.e. $V_{ij}=-\delta_{ij}$, clearly an orthogonal transformation, with $O'=VO=-O$. Eq.(\[inv\]) implies $f(O)=(-1)^pf(O)$. Thus, $p$ needs to be even, otherwise the integral will be zero. Even $p$ will therefore be assumed from now on.

Local sign change {#lsc}
-----------------

Another orthogonal transformation is induced by a matrix $V$ with matrix elements $V_{ij}=(-1)^{s_i}\delta_{ij}$, where $s_i\in\{0,1\}$. It leads to new matrix elements $O_{ij}'=(VO)_{ij}=(-1)^{s_i}O_{ij}$ and $f(O')=(-1)^{\sum_{\lambda=1}^ps_{i_\lambda}}f(O)$. As each $s_{i_\lambda}$ is arbitrary $\in\{0,1\}$, eq.(\[inv\]) implies that each $i_\lambda$ has to appear an even number of times. The same reasoning applied to multiplication with $V$ from the right lets us conclude that also each $j_\lambda$ has to appear an even number of times, otherwise the integral will be zero.

Permutations
------------

Consider the permutation that exchanges two indices, $i_0\leftrightarrow
j_0$. It is induced by a transformation $V$ with matrix elements $V_{ij}=\delta_{ij}$ for $i\ne i_0,j_0$, $V_{i_0j_0}=V_{j_0i_0}=1$, $V_{i_0i_0}=V_{j_0j_0}=0$, which is manifestly orthogonal. An arbitrary permutation can be obtained by concatenating exchanges of two indices. The corresponding matrices are multiplied, and since the product of two orthogonal matrices is again orthogonal, an arbitrary permutation $P$ can always be represented as real orthogonal matrix $V$. Multiplication from the left permutes the left hand indices in $O$, $f(VO)=\prod_\lambda O_{P(i_\lambda)j_\lambda}$, and multiplication from the right permutes the right hand indices, $f(OV)=\prod_\lambda O_{i_\lambda
  P(j_\lambda)}$. Therefore the value of the indices is of no importance, the only thing which counts is the multiplicity of all different indices. Thus, we may rewrite $I$ and $J$ as $I=\{(i_1)^{\mu_1},(i_2)^{\mu_2},\ldots,(i_t)^{\mu_t}\}$ and $J=\{(j_1)^{\nu_1},(j_2)^{\nu_2},\ldots,(j_s)^{\nu_s}\}$, with $\sum_{i=1}^t\mu_i=p=\sum_{i=1}^s\nu_i$, where $p$ is an even integer according to section \[gsc\], and all $\mu_i$ and $\nu_i$ must be even (section \[lsc\]). We might even drop the indices $i_\lambda$ and $j_\lambda$ all together (e.g.  chose them once for all as $i_\lambda=\lambda$ ($\lambda=1,\ldots,t$), $j_\lambda=\lambda$ ($\lambda=1,\ldots,s$)), and just keep the multiplicities ${{\cal M}}\equiv
\{\mu_1,\ldots,\mu_t\}$, ${{\cal N}}\equiv\{\nu_1,\ldots,\nu_s\}$.

This result suggests a graphical representation of ${{\cal I}}(O_{IJ})$, where all first indices in $O_{IJ}$ are represented by a dot in a left column (one dot for each different index), and all different second indices in $O_{IJ}$ are represented by a dot in a right column. These dots are joined by lines, where each line represents a factor $O_{i_\lambda j_\lambda}$. If a factor appears to the power $m_\lambda$, we denote that power next to the line (see fig. \[fig.graphs\]).

If all powers $m_\lambda$ are even, the integral is positive, and is called a “direct integral”; otherwise it is called “exchange integral” [@Aubert03]. In contrast to the integrals encountered for the unitary group [@Aubert03], there are no complex conjugate factors here. This simplifies things at first, as we have to deal with only one type of lines, but also complicates things as it will lead to larger freedom in moving lines around (see below). Therefore, several recursion relations and their solutions will turn out to be more complicated than in the unitary case.

Transposition
-------------

We have $(dO)=(dO^T)$, and therefore ${{\cal I}}(O_{IJ})={{\cal I}}(O_{JI})$. In the graphical language this tells us that all diagrams are invariant under reflection at a central vertical line.

Rotations {#sec.rot}
---------

Consider a rotation in the plane spanned by the basis vectors pertaining to the indices $a$ and $b$, $V_{ij}=\delta_{ij}$ for $i\ne a,b$, $V_{aa}=V_{bb}=\cos\xi$, $V_{ab}=-V_{ba}=(\sin\xi)$. Multiplied from the right, this transforms matrix elements according to $O_{ia}'=(\cos\xi)
O_{ia}-(\sin\xi) O_{ib}$, $O_{ib}'=(\sin\xi)
O_{ia}+(\cos\xi) O_{ib}$, $O_{ij}'=O_{ij}$ otherwise. It is most instructive to consider the effect of this rotation for a simple example, the integral ${{\cal I}}((O_{11})^d)$, $d$ even, and $a=1$, $b=2$. Expanding $(O_{11}')^d$, we obtain $$\label{IO11}
{{\cal I}}((O_{11}')^d)=\sum_{e=0}^d{d\choose
e}(\cos\xi)^{d-e}(-\sin\xi)^{e} \int
(dO)(O_{11})^{d-e}(O_{12})^e={{\cal I}}((O_{11})^d)\,,$$ where the last equal sign is dictated by the invariance under rotations, so the left hand side must be independent of $\xi$. As the only independent form of $\cos\xi$ and of $\sin\xi$ are powers of $\cos^2\xi+\sin^2\xi$, the left side can only contain even values of $e$, such that with $e=2\tilde{e}$, $d=2\tilde{d}$ $$\begin{aligned}
{{\cal I}}((O_{11}')^d)&=&\sum_{\tilde{e}=0}^{\tilde{d}}{2\tilde{d}\choose
2\tilde{e}}(\cos\xi)^{2(\tilde{d}-\tilde{e})}(\sin\xi)^{2\tilde{e}}{{\cal I}}((O_{11})^{2(\tilde{d}-\tilde{e})}(O_{12})^{2\tilde{e}})\\
&=&\sum_{\tilde{e}
 =0}^{\tilde{d}}M_e(\cos\xi)^{2(\tilde{d}-\tilde{e})}(\sin\xi)^{2\tilde{e}}\,,\label{expan}\\  
M_e&=&  {2\tilde{d}\choose
2\tilde{e}}{{\cal I}}((O_{11})^{2(\tilde{d}-\tilde{e})}(O_{12})^{2\tilde{e}})\,.\label{Me}\end{aligned}$$ Invariance under rotations requires that $M_e\propto {\tilde{d}\choose
\tilde{e}}$. The proportionality constant can be fixed from $\tilde{e}=0$, $M_0={{\cal I}}((O_{11})^d)\equiv F_1(2\tilde{d})$, and we are thus lead to $M_e={\tilde{d}\choose 
\tilde{e}}{{\cal I}}((O_{11})^d)$. Together with (\[Me\]) this leads to a series of relationships, $$\label{F2}
F_2(2(\tilde{d}-\tilde{e}),2\tilde{e})\equiv
{{\cal I}}((O_{11})^{2(\tilde{d}-\tilde{e})}(O_{12})^{2\tilde{e}})=\frac{ {\tilde{d}\choose
\tilde{e}}}{{2\tilde{d}\choose
2\tilde{e}}}{{\cal I}}((O_{11})^d)=\frac{ {\tilde{d}\choose
\tilde{e}}}{{2\tilde{d}\choose
2\tilde{e}}}F_1(2\tilde{d})\,.$$ In the graphical language, we have rotated $2\tilde{e}$ lines away from the right dot to a new, empty dot, and we have found a relationship between this new integral and the old one, containing only one line of multiplicity $d=2\tilde{d}$. The same reasoning can be applied to a dot which is part of a more complicated diagram, i.e. a dot in which lines from several other dots terminate. The total number of lines arriving at the dot will again be denoted by $d$, and must still be even. Invariance under rotations implies again the same form (\[expan\]) after expanding the powers of all matrix elements which get transformed, and leads to the same eq.(\[F2\]), where now $F_1(2\tilde{d})$ means the original diagram, and $F_2(2(\tilde{d}-\tilde{e}),2\tilde{e})$ the diagram in which $2\tilde{e}$ lines have been rotated away from one dot to another, empty dot. Note that exactly the same relation is obtained for integration over the hypersphere (instead of integration over the orthogonal group) [@Aubert03]. This is not surprising, as (\[IO11\]) is a one–vector integral, such that only the normalization of each column is involved, but no orthogonality relation between different columns. More generally, any one–vector integral over the orthogonal group $O(N)$ equals the corresponding integral over the hypersphere in $N$ dimensions [@Gorin02].

Eq.(\[F2\]) can be iterated to give the relations called “fan relations” in [@Aubert03], $$\label{Fn}
F_t(2(\tilde{d}-\tilde{d}_1),2(\tilde{d}_1-\tilde{d}_2),\ldots,2(\tilde{d}_{t-2}-\tilde{d}_{t-1}),2\tilde{d}_{t-1}))=
F_1(2\tilde{d})\frac{{\tilde{d}\choose\tilde{d}_1}{\tilde{d_1}\choose\tilde{d}_2}\cdot\ldots\cdot{\tilde{d}_{t-2}\choose\tilde{d}_{t-1}}}{{2\tilde{d}\choose2\tilde{d}_1}{2\tilde{d}_1\choose2\tilde{d}_2}\cdot\ldots\cdot{2\tilde{d}_{t-2}\choose2\tilde{d}_{t-1}}}  \,.$$ We recognize $2\tilde{d}_{t-1}=m_t$ as the multiplicity of the last line (line $t$), $2(\tilde{d}_{t-2}-\tilde{d}_{t-1})=m_{t-1}$ as the multiplicity of line $t-1$, and so on, up to the multiplicity $m_1=2(\tilde{d}-\tilde{d}_1)$ of the first line. The relationships between $\tilde{d}_i$ and $m_j$ are easily inverted, and, when re-injected into (\[Fn\]), lead to the final form of the “fan relation” for an integral represented by the diagram in fig.\[fig.fan\], $$\label{Fn2}
F_t(m_1,\ldots,m_t)=F_1(d)\frac{(d/2)!}{d!}\frac{m_1!\cdot\ldots\cdot m_t!}{(\frac{m_1}{2})!\cdot\ldots\cdot(\frac{m_t}{2})!}\,.$$ The integral for a single line with multiplicity $d$, $F_1(d)$, will be calculated in the next section.

Relations from Orthogonality
============================

The orthogonality relation (\[ortho\]) is a handy tool to reduce the number of lines in a diagram. It is most instructive to consider as simple example the integral $$\label{f2}
F_2(2(m-1),2)={\int (dO)}(O_{1k})^{2(m-1)}(O_{1l})^2\,\,\,\,\,k\ne l\,,$$ As we have seen, the value of the integral is independent of the index $l$, as long as $l\ne k$. At the same time, if we sum over [*all*]{} possible values of $l$ (i.e. $l=1,\ldots,N$), we can make use of (\[ortho\]), as $\sum_{l=1}^N(O_{1l})^2=1$. Therefore, $$\begin{aligned}
 \label{F21}
(N-1)F_2(2(m-1),2)&=&\sum_{l=1}^N{\int (dO)}(O_{1k})^{2(m-1)}(O_{1l})^2-{\int (dO)}(O_{1k})^{2m}\nonumber\\
&=&F_1(2(m-1))-F_1(2m)\,.\end{aligned}$$ This is an equation independent of the fan relation (\[Fn2\]). The latter leads in the present case to $$\label{F22}
F_2(2(m-1),2)=\frac{F_1(2m)}{2m-1}\,,$$ and combining this with (\[F21\]) gives a recursion relation for $F_1(2m)$, $$\label{recurF}
F_1(2m)=\frac{2m-1}{2m+N-2}F_1(2m-2)\,,$$ with the obvious solution $$\label{F2m}
F_1(2m)=\frac{(2m-1)!!(N-2)!!}{(2m+N-2)!!}\,.$$ The normalization $F_1(0)={\int (dO)}=1$ was used, and can be retrieved from (\[F2m\]) if we define $(-1)!!=1$.

The orthogonality relation is useful if we have a dot in which only two lines end. Note that so far we have used again just the normalization of each line in the orthogonal matrix. If the two lines ending in dot $l$ on the right were replaced by two lines originating from two different dots on the left, the sum over all values of $l$ would give zero, regardless of the rest of the diagram.

Z–integrals
===========

As an application of the techniques introduced, we now consider all possible integrals with up to three different factors, two indices on the right, and two on the left (see fig.\[fig.Z\]), baptized “Z–integrals” in [@Aubert03], $$\label{Z}
Z(m_1,m_2,m_3)={\int (dO)}(O_{11})^{m_1}(O_{12})^{m_2}(O_{22})^{m_3}\,.$$ All multiplicities $m_1,m_2,m_3$ must be even. We start from the integral ${{\cal I}}(3b)$ shown in fig.\[fig.Z\], obtained by rotating two lines away from the first dot on the left to a new dot. The latter is arbitrary, and we can sum over it, avoiding the already taken indices 1 and 2, whereas in the full sum the extra line disappears, $$\label{sum3b}
\sum_{k=3}^N{{\cal I}}(3b)=(N-2){{\cal I}}(3b)=Z(m_1,m_2,m_3-2)-Z(m_1,m_2,m_3)-Z(m_1,m_2+2,m_3-2)\,.$$ On the other hand, the fan relation (\[Fn2\]) can be applied to the upper two lines of the diagram (3b), which gives ${{\cal I}}(3b)=\frac{1}{m_3-1}Z(m_1,m_2,m_3)$. Once we insert the latter result into (\[sum3b\]), we find the recursion $$\label{recurZ}
Z(m_1,m_2,m_3)=\frac{m_3-1}{N+m_3-3}\left(Z(m_1,m_2,m_3-2)-Z(m_1,m_2+2,m_3-2)\right)\,,$$ which should be supplemented by the initial value $$\label{Zanf}
Z(m_1,m_2,0)=F_2(m_1,m_2)=\frac{(m_1+m_2-1)!!(N-2)!!}{(m_1+m_2+N-2)!!}\frac{(\frac{m_1+m_2}{2})!m_1!m_2!}{(m_1+m_2)!(\frac{m_1}{2})!(\frac{m_2}{2})!}$$ obtained from the fan relation (\[Fn2\]). If we apply the recursion relation again, we easily convince ourselves that its solution is of the form $$\label{Z1}
Z(m_1,m_2,m_3)=\frac{(m_3-1)!!(N-3)!!}{(N+m_3-3)!!}
 \sum_{i=0}^{m_3/2}{m_3/2\choose  i}Z(m_1,m_2+2i,0)(-1)^i\,.$$

A closed form can be found for the sum in this equation, if we consider $N$ even and odd separately. For $N$ even, (\[Zanf\]) can be re-expressed as $$\label{Zanf2}
Z(m_1,m_2,0)=\frac{\left(\frac{N-2}{2}\right)!m_1!m_2!}{2^{m_1+m_2}(\frac{m_1}{2})!(\frac{m_2}{2})!(\frac{m_1+m_2+N-2}{2})!}\,,$$ such that $$\begin{aligned}
Z(m_1,m_2,m_3)&=&\frac{(m_3-1)!!(N-3)!!}{(N+m_3-3)!!}
\frac{\left(\frac{N-2}{2}\right)!m_1!}{2^{m_1+m_2}(\frac{m_1}{2})!} 
S_1\,,\nonumber\\
S_1&\equiv&\sum_{i=0}^{m_3/2}\left(\frac{-1}{4}\right)^i{m_3/2\choose
  i}\frac{(m_2+2i)!}{(\frac{m_2}{2}+i)!(\frac{m_1+m_2+2i+N-2}{2})!}\nonumber\\
&=&\frac{2^\frac{m_2-m_3}{2}(m_2-1)!!(m_1+m_3+N-3)!!}{(m_1+N-3)!!(\frac{m_1+m_2+m_3+N-2}{2})!}\,.\label{Zfin}\end{aligned}$$ This leads to the final result $$\begin{aligned}
Z(m_1,m_2,m_3)&=&\frac{m_1!m_2!m_3!\left(\frac{m_1+N-2}{2}\right)!\left(\frac{m_3+N-2}{2}\right)!}{2^{m_1+m_2+m_3}(m_1+N-2)!(m_3+N-2)!\left(\frac{m_1+m_3+N-2}{2}\right)!\left(\frac{m_1+m_2+m_3+N-2}{2}\right)!}\nonumber\\
&&\times\frac{(m_1+m_3+N-2)!(N-2)!}{\left(\frac{m_1}{2}\right)!\left(\frac{m_2}{2}\right)!\left(\frac{m_3}{2}\right)!}
\\
&=&\frac{2^{2-N}\Gamma(\frac{1+m_1}{2})\Gamma(\frac{1+m_2}{2})\Gamma(\frac{1+m_3}{2})\Gamma(N-1)\Gamma(\frac{1}{2}(N+m_1+m_3-1))}{\pi\Gamma(\frac{1}{2}(N+m_1-1))\Gamma(\frac{1}{2}(N+m_3-1))\Gamma(\frac{1}{2}(N+m_1+m_2+m_3))}\,.\end{aligned}$$ The latter form turns out to be valid also for odd $N$.

Exchange integrals
==================

Exchange integrals contain at least one line with odd multiplicity, and can therefore be positive or negative. The total number of lines arriving in any dot must, of course, still be even, otherwise the integral vanishes. Consider the structurally simplest exchange integral depicted in fig.\[fig.X\], $$\label{X}
X(r,s,t,u)\equiv {\int (dO)}(O_{11})^r(O_{21})^s(O_{22})^t(O_{12})^u\,,$$ $r,s,t,u\in \mathbb{N}$. The case $r=s=t=u=1$ is easily solved by summing over the index of an arbitrary point, say the upper right one. We obtain $$\label{X1111}
X(1,1,1,1)=-\frac{1}{N-1}F_2(2,2)=-\frac{1}{(N-1)N(N+2)}\,.$$ For general $r,s,t,u$ we derive a recursion relation using invariance under a rotation between indices 1 and 3 (where 3 is a new index), multiplied from the right. This gives $$\begin{aligned}
X(r,s,t,u)=X'(r,s,t,u)&\equiv&{\int (dO)}\left((\cos\xi) O_{11}-(\sin\xi)
O_{13}\right)^r\left((\cos\xi) O_{21}-(\sin\xi)
O_{23}\right)^sO_{22}^tO_{12}^u\nonumber\\
&=&(\cos\xi)^{r+s}M_0+(\cos\xi)^{r+s-2}(\sin\xi)^2 M_1+\ldots\end{aligned}$$ where $M_0=X(r,s,t,u)$ is evident from choosing $\xi=0$, and $M_1$ is given by the diagrams in fig.\[fig.X\] with corresponding values ${{\cal I}}(4a)$, ${{\cal I}}(4b)$, and ${{\cal I}}(4c)$, $$\label{M1X}
M_1=\frac{r(r-1)}{2}{{\cal I}}(4a)+rs{{\cal I}}(4b)+\frac{s(s-1)}{2}{{\cal I}}(4c)\,.$$ According to section \[sec.rot\], we must have $M_1=\frac{r+2}{2}X(r,s,t,u)$.

The order of the integrals ${{\cal I}}(4a)$, ${{\cal I}}(4b)$, and ${{\cal I}}(4c)$ can again be reduced by summing over the index of the new point, which yields $$\begin{aligned}
{{\cal I}}(4a)&=&\frac{1}{N-2}\left(X(r-2,s,t,u)-X(r,s,t,u)-X(r-2,s+2,t,u)\right)\\
{{\cal I}}(4b)&=&-\frac{1}{N-2}\left(X(r,s,t,u)+X(r-1,s-1,t+1,u+1)\right)\\
{{\cal I}}(4c)&=&\frac{1}{N-2}\left(X(r,s-2,t,u)-X(r,s-2,t+2,u)-X(r,s,t,u)\right)\,.\end{aligned}$$ If we insert these integrals into (\[M1X\]), we get the recursion relation $$\begin{aligned}
X(r,s,t,u)&=&\frac{1}{(r+s)(N-2)+r(r-1)+2rs+s(s-1)}\big(-2rsX(r-1,s-1,t+1,u+1)\nonumber\\ 
&&+r(r-1)\left(X(r-2,s,t,u)-X(r-2,s+2,t,u)\right)\nonumber\\
&&+s(s-1)\left(X(r,s-2,t,u)-X(r,s-2,t+2,u)\right)\big)\,.\label{Xrec}\end{aligned}$$ No closed solution of this recursion relation could be found, but the principle of its application is clear: Iterating (\[Xrec\]) will reduce the multiplicities of the lines with power $r$ or $s$, till a power zero is achieved, and then the integral is reduced to a Z-integral, whose value is known for all multiplicities of the remaining lines, see eq.(\[Zfin\]). Note that the formula corresponding to (\[Xrec\]) for the unitary case is quite different, as one must rotate always one line corresponding to a non-conjugated matrix element and one line corresponding to a complex conjugated matrix element [@Aubert03].

Integrals of order 6
====================

In this final section I will give explicit formulas for all integrals of order $p=6$, which are not of the fan-type or Z-type. They are shown in figure \[fig.p6\], and will be denoted accordingly ${{\cal I}}(5a)$, ${{\cal I}}(5b)$, ${{\cal I}}(5c)$, ${{\cal I}}(5d)$, ${{\cal I}}(5e)$, ${{\cal I}}(5f)$, ${{\cal I}}(5g)$. All of them are obtained by summing over the index indicated by an arrow. We are lead to $$\begin{aligned}
{{\cal I}}(5a)&=&\frac{1}{N-1}\left(F_2(2,2)-F_3(2,2,2)\right)=
\frac{N+3}{(N-1)N(N+2)(N+4)}\\    
{{\cal I}}(5b)&=&\frac{1}{N-2}(Z(2,0,2)-2{{\cal I}}(5a))=
\frac{-2+N(N+3)}{(N-2)(N-1)N(N+2)(N+4)} \\ 
{{\cal I}}(5c)&=&-\frac{1}{N-1}F_2(2,4)=-\frac{3(N-2)!!}{(N-1)(N+4)!!}={{\cal I}}(5d)\\
{{\cal I}}(5e)&=&-\frac{1}{N-1}F_3(2,2,2)=-\frac{(N-2)!!}{(N-1)(N+4)!!}\\
{{\cal I}}(5f)&=&-\frac{1}{N-2}\left({{\cal I}}(5a)+{{\cal I}}(5e)\right)=-\frac{1}{(N-2)(N-1)N(N+4)}\\ 
{{\cal I}}(5g)&=&-\frac{2}{N-2}{{\cal I}}(5e)=\frac{2(N-2)!!}{(N-2)(N-1)(N+4)!!}\,.\end{aligned}$$

Summary
=======

As a summary, I have adapted the method of invariant integration introduced in [@Aubert03] to the case of integration over the orthogonal group $O(N)$. Explicit formulas were obtained for all one–vector integrals (these coincide with integrals over a hypersphere in $N$ dimensions), for all two–vector integrals with up to three different matrix elements, as well as for all integrals up to order 6. In more complicated cases recursion relations were derived, in particular for all exchange integrals with two different indices on the left and two on the right.

[*Acknowledgments:*]{} This work was supported by the Agence National de la Recherche (ANR), project INFOSYSQQ.