TITLE: Prove that $\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\frac{1}{\sqrt{4}}+\frac{1}{\sqrt{5}}+\frac{1}{\sqrt{6}}\cdots>\infty$ .
QUESTION [0 upvotes]: I need to a fresh solution, but mine

We have that
$$\begin{align*}
\frac{1}{\sqrt{1}} &+ \frac{1}{\sqrt{2}}+ \frac{1}{\sqrt{3}}+ \frac{1}{\sqrt{4}}+ \frac{1}{\sqrt{5}}+ \frac{1}{\sqrt{6}}+ \frac{1}{\sqrt{7}}\cdots \\
 &> \frac{1}{1}+ \frac{1}{2}+ \frac{1}{3}+ \frac{1}{4}+ \frac{1}{5}+ \frac{1}{6}+ \frac{1}{7}\cdots \\
 &> \frac{1}{1}+ \frac{1}{2}+ \left ( \frac{1}{4}+ \frac{1}{4} \right )+ \left ( \frac{1}{8}+ \frac{1}{8}+
\frac{1}{8}+ \frac{1}{8} \right )\cdots \\
 &= 1+ \frac{1}{2}+ \frac{1}{2}+ \frac{1}{2}+ \frac{1}{2}+ \frac{1}{2}\cdots \\
 &= \infty
\end{align*}$$

REPLY [3 votes]: Because $$\frac{1}{\sqrt{n}}>\frac{2}{\sqrt{n}+\sqrt{n+1}}=2(\sqrt{n+1}-\sqrt{n})$$ and the telescopic summation.

REPLY [0 votes]: An alternative argument, appealing also to the fact that the harmonic series diverges:
$$\underbrace{\frac{1}{\sqrt 1}}_{\displaystyle \ge 1} + \underbrace{\frac{1}{\sqrt 2} + \cdots +\frac{1}{\sqrt 4}}_{\displaystyle \ge \frac{1}{\sqrt 4} = \frac 1 2} + \underbrace{\frac{1}{\sqrt 5} + \cdots +\frac{1}{\sqrt 9}}_{\displaystyle \ge \frac{1}{\sqrt 9} = \frac 1 3} + \cdots$$
In general: let $k^2,(k+1)^2$ be consecutive perfect squares. Then, since $\sqrt x \ge 0$, you'll have
$$\frac{1}{\sqrt{k^2+1}} + \cdots +\frac{1}{\sqrt{(k+1)^2}} \ge \frac{1}{\sqrt{(k+1)^2}}=\frac 1 {k+1}$$
Doing this over and over again throughout the sum allows one to show that
$$\sum_{k=1}^\infty \frac{1}{\sqrt k} \ge \sum_{k=1}^\infty \frac 1 k$$
but the latter diverges.


text:
\section{Helper Lemmas}
\label{sec:helper}
In this section we include some generic helper lemmas. Most of the results are standard and we provide the proof for completeness.
\begin{lemma}
    \label{helper:blocknorm}
    Let $A = \begin{bmatrix}
            A_{11} & A_{12}
            \\
            A_{21} & A_{22}
        \end{bmatrix}$ be an arbitrary $2d \times 2d$ block matrix, where $A_{11}, A_{12}, A_{21}, A_{22}$ are $d \times d$ matrix blocks. Then the operator norm of $A$ is bounded by
    \begin{equation}
        \|A\| \leq \max \left\{ \|A_{11}\|, \|A_{22}\| \right\} + \left\{ \|A_{12}\|, \|A_{21}\| \right\}.
    \end{equation}
\end{lemma}
\begin{proof}[Proof of \cref{helper:blocknorm}]
    Let $A_{ij} = U_{ij} \Sigma_{ij} V_{ij}^T$ be the SVD decomposition of matrix $A_{ij}$, for $i=1,2$, and $j=1,2$. Then
    \begin{equation}
        \begin{bmatrix}
            A_{11} & \\ & A_{22}
        \end{bmatrix}
        =
        \begin{bmatrix}
            U_{11} \Sigma_{11} V_{11}^\intercal & \\ & U_{22} \Sigma_{22} V_{22}^\intercal
        \end{bmatrix}
        =
        \begin{bmatrix}
            U_{11} & \\ & U_{22}
        \end{bmatrix}
        \begin{bmatrix}
            \Sigma_{11} & \\ & \Sigma_{22}
        \end{bmatrix}
        \begin{bmatrix}
            V_{11} & \\ & V_{22}
        \end{bmatrix}^\intercal,
    \end{equation}
    thus
    \begin{equation}
        \left\| \begin{bmatrix}
            A_{11} & \\ & A_{22}
        \end{bmatrix} \right\|
        =
        \left\| \begin{bmatrix}
            \Sigma_{11} & \\ & \Sigma_{22}
        \end{bmatrix} \right\|
        =
        \max\left\{ \|\Sigma_{11}\|, \|\Sigma_{22}\|\right\}
        =
        \max\left\{ \|A_{11}\|, \|A_{22}\|\right\}.
    \end{equation}
    Similarly
    \begin{equation}
        \begin{bmatrix}
             & A_{12} \\ A_{21} &
        \end{bmatrix}
        =
        \begin{bmatrix}
             & U_{12} \Sigma_{12} V_{12}^\intercal \\ U_{21} \Sigma_{21} V_{21}^\intercal &
        \end{bmatrix}
        =
        \begin{bmatrix}
             & U_{12} \\ U_{21} &
        \end{bmatrix}
        \begin{bmatrix}
            \Sigma_{21} & \\  & \Sigma_{12}
        \end{bmatrix}
        \begin{bmatrix}
            V_{21} & \\ & V_{12}
        \end{bmatrix}^\intercal,
    \end{equation}
    thus
    \begin{equation}
        \left\| \begin{bmatrix}
             & A_{12} \\ A_{21 }&
        \end{bmatrix} \right\|
        =
        \left\| \begin{bmatrix}
            \Sigma_{21} & \\ & \Sigma_{12}
        \end{bmatrix} \right\|
        =
        \max\left\{ \|\Sigma_{12}\|, \|\Sigma_{21}\|\right\}
        =
        \max\left\{ \|A_{12}\|, \|A_{21}\|\right\}.
    \end{equation}
    Consequently, by the subadditivity of the operator norm,
    \begin{equation}
        \|A\| \leq  \left\| \begin{bmatrix}
            A_{11} & \\ & A_{22}
        \end{bmatrix} \right\| + \left\| \begin{bmatrix}
             & A_{12} \\ A_{21 }&
        \end{bmatrix} \right\|
        \leq
        \max\left\{ \|A_{11}\|, \|A_{22}\|\right\} + \max\left\{ \|A_{12}\|, \|A_{21}\|\right\}.
    \end{equation}
\end{proof}

\begin{lemma}
    \label{helper:unbalanced:ineq}
    Let $x, y \in \reals^d$, then for any $\zeta > 0$, the following inequality holds
    \begin{equation}
        \|x + y\|^2 \leq (1 + \zeta) \|x\|^2 + (1 + \zeta^{-1}) \|y\|^2.
    \end{equation}
\end{lemma}
\begin{proof}[Proof of \cref{helper:unbalanced:ineq}]
    First note that $\|x + y\|^2 = \|x\|^2 + \|y\|^2 + 2 \langle x, y \rangle$, then the proof follows by $2\langle x, y \rangle \leq \zeta \|x\|^2 + \zeta^{-1} \|y\|^2$ due to Cauchy-Schwartz inequality.
\end{proof}
\begin{lemma}
    \label{helper:3rd:Lip}
    Let $F$: $\reals^d \to \reals$ be an arbitrary twice-continuous-differentiable function that is $Q$-3rd-order-smooth. Then for any $w^1, \ldots, w^M \in \reals^d$, the following inequality holds
    \begin{equation}
        \left\|  \nabla F (\overline{w}) - \frac{1}{M} \sum_{m=1}^M \nabla F(w^m)  \right\|^2
        \leq
        \frac{Q^2}{4M}  \sum_{m=1}^M\left\| w^m - \overline{w} \right\|^4,
    \end{equation}
    where $\overline{w} := \frac{1}{M} \sum_{m=1}^M w^m$.
\end{lemma}
\begin{proof}[Proof of \cref{helper:3rd:Lip}]
    \begin{align}
             & \left\|  \frac{1}{M} \sum_{m=1}^M \nabla F(w^m) - \nabla F (\overline{w})    \right\|^2
        \\
        =    & \left\|  \frac{1}{M} \sum_{m=1}^M \left( \nabla F(w^m) - \nabla F (\overline{w}) - \nabla^2 F (\overline{w})(w^m - \overline{w}) \right)   \right\|^2
        \tag{since $\frac{1}{M} \sum_{m=1}^M w^m - \overline{w} = 0$}
        \\
        \leq & \frac{1}{M} \sum_{m=1}^M\left\|   \nabla F(w^m) - \nabla F (\overline{w}) - \nabla^2 F (\overline{w})(w^m - \overline{w}) \right\|^2
        \tag{Jensen's inequality}
        \\
        \leq & \frac{Q^2}{4M}  \sum_{m=1}^M\left\| w^m - \overline{w} \right\|^4.
        \tag{$Q$-3rd-order-smoothness}
    \end{align}
\end{proof}

\begin{lemma}
    \label{helper:diff:4th}
    Let $X$ and $Y$ be two i.i.d. $\reals^d$-valued random vectors, and assume $\expt X = 0$, $\expt \|X\|^4 \leq \sigma^4$. Then
    \begin{equation}
        \expt \|X+Y\|^2 \leq 2 \sigma^2, \quad \expt \|X+Y\|^3 \leq 4 \sigma^3, \quad \expt \|X+Y\|^4 \leq 8 \sigma^4.
    \end{equation}
\end{lemma}
\begin{proof}[Proof of \cref{helper:diff:4th}]
    The first inequality is due to $ \expt \|X+Y\|^2 = \expt \|X\|^2 +  \expt \|Y\|^2 = 2\sigma^2$ where $\expt \|X\|^2 \leq \sigma^2$ follows by applying H\"older's inequality to the assumption $\expt \|X\|^4 \leq \sigma^4$.

    The \nth{4} moment is bounded as
    \begin{align}
             & \expt \|X+Y\|^4 = \expt \left[ \|X\|^2 + \|Y\|^2 + 2 \langle X,  Y \rangle \right]^2
        \\
        =    & \expt \left[ \|X\|^4 + \|Y\|^4 + 2 \|X\|^2 \|Y\|^2 + 4 \langle X,  Y \rangle^2 + 4 \|X\|^2 \langle X,  Y \rangle  + 4\|Y\|^2 \langle X,  Y \rangle  \right]
        \\
        =    & \expt \left[ \|X\|^4 + \|Y\|^4 + 2 \|X\|^2 \|Y\|^2 + 4 \langle X,  Y \rangle^2 \right] \tag{by independence and mean-zero assumption}
        \\
        \leq & \expt \left[ 4\|X\|^4 + 4\|Y\|^4 \right] \tag{Cauchy-Schwarz inequality} \leq 8 \sigma^4.
    \end{align}

    The \nth{3} moment is bounded via Cauchy-Schwarz inequality since
    \begin{equation}
        \expt \|X+Y\|^3 \leq \sqrt{\expt \|X+Y\|^2 \expt \|X+Y\|^4} \leq 4 \sigma^3.
    \end{equation}
\end{proof}

\begin{lemma}
    \label{helper:inv:times:log}
    Let $\varphi(x) := \frac{1}{x^q} \log^p (a + b x)$, where $a, p, q \geq 1$, $b > 0$ are constants. Then suppose $a \geq \exp (p/q)$, it is the case that $\varphi(x)$ is monotonically decreasing over $(0, +\infty)$.
\end{lemma}
\begin{proof}[Proof of \cref{helper:inv:times:log}]
    Without loss of generality assume $b = 1$, otherwise we put $\psi(x) = \varphi(x/b)$ then $\psi$ has the same form (up to constants) with $b = 1$. Taking derivative for $\varphi(x) = x^{-q} \log^p (a + x)$ gives
    \begin{align}
        \varphi'(x)
        & =
        \frac{px^{-q} \log^{p -1} (a+x) }{a + x} - q x^{-q-1} \log^p (a+x)
        \\
        & =
        \frac{x^{-q-1}\log^{p-1}(a+x)}{a+ x} \left( p x - q(a + x) \log(a+x) \right).
    \end{align}
    Since $a \geq 1$ and $x > 0$ we always have $ \frac{x^{-q-1}\log^{p-1}(a+x)}{a+ x} \geq 0$. Suppose $a \geq \exp(p/q)$ then
    \begin{equation}
        px - q(a+x) \log (a+x)
        <
        px - qx \log (a)
        \leq
        px - qx \cdot \frac{p}{q}
        \leq
        0.
    \end{equation}
    Hence $\varphi'(x) < 0$ and thus $\varphi(x)$ is monotonically decreasing.
\end{proof}

config: arxiv


TITLE: What are the possible remainders when the $110^{th}$ power of an integer is divided by $121$?
QUESTION [1 upvotes]: I was checking the following Euler's theorem exercise:

What are the possible remainders when the $110^{th}$ power of an integer is divided by $121$?

I've started working from calculating $\phi (110) = 40$
Now I'm thinking about applying $\mod 121$ but I'm unable to. So now I'm maybe in the wrong way. Any help or clue will be really appreciated.

REPLY [1 votes]: $\phi (110)$ is utterly irrelevent.
Euler's theorem tells us about $a^k \pmod {n}$ and how $k$ and $\phi(n)$ relate.
$\phi (k)$ has got sod all to do with fish and fishsticks.
So we want to know how $110$ and $\phi(121)= \phi(11^2) = 11(11-1)$ relate.
How do they relate?
....
So we can break your task into the following.
1) Figuring out what $\phi(121)=\phi(11^2) = 11(11-1)$ is.
2) Figuring how $110$ relates to $\phi(121)$.  In particular what $100 \mod \phi(121)$ is.
3) Figuring if $\gcd(a,121)=1$ then what is $110 \pmod {\phi(121)}\equiv a^{(110 \%{\phi(121)})}$ are for the different values of $a$ so that $\gcd(a,121) = 1$.
4) Figure out what happens when $\gcd(a,121) \ne 1$.
Now as the prime factorization of $121 = 11^2$ and $\phi(11^2) = 11(11-1)$.....
Those become fairly easy questions.


TITLE: Does a topological space contain the closed sets?
QUESTION [3 upvotes]: I am confused concerning the relation between closed sets and a topological space.
I know that a topological space is mostly defined in terms of open sets via the underlying topology and ist requiered properties. The sets defining the topology are then called open sets.
Given the de Morgan laws one could restate this in terms of closed sets. But this will then necessarily imply that the closed sets define the topology and thus the topological space which contains them. That the topological space will contain both open and closed sets makes me totally confused.
I know that one of the differences between a sigma algebra and a topological space is precisely this: through the complementation the sigma algebra contains also the closed sets whereas the topological space does not.
Can somebody help me clarify this confusion ?
Thanks.

REPLY [1 votes]: Ah, I think I see your problem:

"I know that a topological space is mostly defined in terms of open
  sets via the underlying topology"

The word "definition" and "defined" is ambiguous.  Here is an anology:
A triangle is defined by its three sides.
We may define a triangle by one side and the two angles adjacent to it.
Those sentences are both true but seem contradictory.
A triangle has $!6!$ components three sides, three angles.  But if we have three of those components we can (usually) determine completely the entire triangle.
But we classify a triangle by its three sides.
The same it true of a topology.
A topological space is a set, and an assignment of all possible subsets to either open, closed, both or neither so that the assignment conforms to specific conditions.
We classify a topological space by a class of subsets that are stated to be open.  From that class we can determine completely and unambiguously, what status (open, closed, both, or neither) all subsets of the topological space are.
So we say $(G, \tau)$ is a topology where $G$ is a set, and $\tau$ is a list of open subsets.
Okay, suppose we have a set $G$ and $\rho$, a list of closed subsets.  Can we create a topology from this?  Of course!  If $\rho$ is a list of closed subsets* then $\tau = \{L^c| L \in \rho\}$ will be the bases list of open subsets.
So the topology that we created with $G$ and $\rho$ is $(G, \tau =\{L^c| L \in \rho\})$.
There's absolutely nothing strange about this.  The topology was created by us knowing its closed subsets, but the topology is still a set and a class of open sets.  It's just that the open sets are the compliments of the closed sets.  Not the closed sets themselves.
======
"The sets defining the topology are then called open sets."
That's sort of a weird and backward way of looking at it.  The topology is distinguished and recognized by which of its subsets are open.  But we can define the topology in any dang way we want--- so long as the definition necessarily means precisely those subsets are the subsets that are open.
So a set is closed if and only if it's complement is open.  So if we chose to define the topology by listing the closed sets we'd get the same result.  The topology's open sets can be determined by the compliment of the closed sets.
But we wouldn't call those defining sets open sets.  We'd call them closed sets because they were defined to be the closed sets.
"That the topological space will contain both open and closed sets makes me totally confused."  Topologies always contain both open and closed sets.  That's not a big deal.
Okay, let's do an example.  Let $X = \{1,2,3,4\}$.  It has $16$ subsets.  And let $\tau$ = $\{\{2\}, \{1,3\}\}$ that means the open sets will be $X, \emptyset, \{2\}, \{1,3\}, \{2\}\cup \{1,3\} = \{1,2,3\}$.  And the closed sets will be the complements of those $X, \emptyset, \{1,3,4\}, \{2,4\} ,\{4\}$. The remaining 8 sets, $\{1\},\{3\},\{1,2\}, \{1,4\},\{2,3\},\{3,4\}\{1,2,4\},\{2,3,4\}$ are neither open nor closed.
Now we could just as easily define the topology by listing the closed sets.  We'll call the base of closed sets $\rho$. So we can define a topology via $\rho = \{\{1,3,4\},\{2,4\}\}$.  From this we would conclude the closed sets are $X,\emptyset,\{1,3,4\},\{2,4\}, \{1,3,4\} \cap \{2,4\} = \{4\}$.  We'd take the complements to find the open sets.  $X, \emptyset, \{2\},\{1,3\},\{1,2,3\}$. The remaining 8 sets, $\{1\},\{3\},\{1,2\}, \{1,4\},\{2,3\},\{3,4\}\{1,2,4\},\{2,3,4\}$ are neither open nor closed.
This is the exact same topology as it has the exact same open, closed, both and neither subsets.
ADDENDUM
In light of precise definitions:
Let $X$ be a set:  Let $\tau$ be a list of subsets of $X$ so that: 1) $X, \emptyset \in \tau$.  ii) for any $U, V \in \tau$ then $U\cap V \in \tau$ , iii) for any $\phi \subset \tau$ then $\cup_{U \in \phi} U \subset \tau$.
We say that $\tau$ is a topology on $X$.
Now let $\rho$ be a list of subset of $X$ so that 1) $X, \emptyset \in \rho. ii) for any $U, V \in \rho $U\cup V \in \rho$ , iii) for any $\phi \subset \rho$ then $\cap_{U \in \phi} U \subset \rho$
We set and $\rho$ is  a notology on $X$.
Exercise:  It can be verified that $\tau$ is a topology on $X$ if and only if $\{U^c| U \in \tau\}$ is a notology on $X$ (and vice versa).
Now a topological space $\langle X, \tau\rangle$ is the set $X$ and a topology $\tau$ on it, with the understanding that the $U\in \tau$ have the property of being "open".  The $V \in \{U^c|U\in \tau\}$ have the property of being "closed".  And all other subsets have neither property.
ANd let's say  a notological space $\rangle X, \rho\langle$ is the set $X$ and a notology $\rho$ on it, with the understanding that the $U\in \rho$ have the property of being "closed".  The $V \in \{U^c|U\in \rho\}$ have the property of being "open".  And all other subsets have neither property.
Notice that notological space $\rangle X, \rho\langle$ and the topological space $\langle X, \{U^c|U \in \rho\} \rangle$ are the exact same construct!
That really is all the comment is saying.


TITLE: What is the limit of $ (1 - \frac{1}{n})^{2n}$ as n goes to infinity?
QUESTION [0 upvotes]: $ (1 - \frac{1}{n})^{2n} = ((1-\frac{1}{n})^2)^n = (1-\frac{2}{n} + \frac{1}{n^2})^n$.
If I ignore the $\frac{1}{n^2}$ term inside the parenthesis I have that the limit is $e^{-2}$ which agrees with Mathematica.  Can I ignore this term?  Why?

REPLY [2 votes]: $\lim \left(1-\frac2n+\frac1{n^2}\right)^n=\lim \left(1+\frac1n\left(-2+\frac1{n}\right)\right)^n=e^{\lim \left(-2+\frac1{n}\right)}=e^{-2}.$
Or you could just do $\lim \left(1-\frac1n\right)^{2n}=e^{2\times (-1)}=e^-2.$
The rule here is $\lim (1+a_n)^{b_n}=e^{\lim (na_nb_n)}.$


TITLE: Show that $x+e^{-Bx^2}\mbox{cos}(x)$ has only one root over all reals ($B>0$).
QUESTION [4 upvotes]: Let $B>0$ and define for all $x\in \mathbb{R}$ the function $f(x)=x+e^{-Bx^2}\mbox{cos}(x)$. Prove that $f$ has exactly one root over $\mathbb{R}$.
My original attempt was to show that the function $g(x)=-e^{-Bx^2}\mbox{cos}(x)$ is contractive (in this sense) and the result would follow from the Bannach Fixed Point theorem. However, I posted this as a question (look here) and I've concluded that this idea is not the best one. Can anyone give me a tip about how to attack this problem? Thanks in advance!

REPLY [1 votes]: My idea started out as trying to apply the Banach fixed point theorem and then boiled down to a simpler idea.
Let $g(x)=-e^{-Bx^2} \cos(x)$. Note as you already have that $x$ is a root of $f$ if and only if it is a fixed point of $g$.
Now notice that $g(\mathbb{R}) \subseteq [-1,1]$ and $g([-1,1]) \subseteq [-1,0]$. We can't easily do much better than $g([-1,0]) \subset [-1,0]$, so for now we'll just say that any fixed point of $g$ must be in $[-1,0]$.
But on $(-1,0)$, $e^{-Bx^2}$ and $\cos(x)$ are both strictly increasing, so $f$ is strictly increasing there as well. So there is at most one root. Moreover $f$ is negative at $-1$ and positive at $0$, so by the intermediate value theorem there is at least one root. So there is exactly one root.


TITLE: Getting all solutions to system linear equation from one solution
QUESTION [0 upvotes]: I am trying find all solution to dependent system linear equation. Suppose that I have one solution to system linear equation. It's possible modify system linear equation to find other solutions?
EDIT:
Thanks for replies.
I specify my equations, Ax = b. Matrix A is square integer matrix size 144. b is vector contains all-6 number. I am looking only 0-1 solution, i.e x=0 or x=1. Number of variables is 144. I found one solution from gurobi optimalization(find only one optimal solution), but I know that exists another solutions. I want to modify system of linear equation. Is it possible?

REPLY [0 votes]: It depends on the size of the kernel, and whether the system in homogeneous or not. If you the system in homogeneous and the kernel's dimension is 1, then your one solution will suffice, as the rest are just multiples of that solution.
However, if the kernel's dimension is larger, you'll need more solutions, and any linear combination of them would be a solution as well.
If the system in inhomogeneous, a single solution together with all the solutions to the corresponding homogeneous system, should produce all solutions.


TITLE: Rank these notations from most valid to least valid
QUESTION [1 upvotes]: $$\mathbb{Z}[\sqrt{-3}]$$
$$\mathbb{Z}\left[\frac{i \sqrt{3} - 1}{2}\right]$$
$${\bf{A}}(-3)$$
$$\mathbb{Z}[\omega]$$
$$\mathbb{Z}\left[-\frac{1}{2} + \frac{\sqrt{-3}}{2}\right]$$
$$\mathbb{Z}[\sqrt{-27}]$$
$$\mathbb{Z}\left[\frac{\sqrt{-3}}{2}\right]$$
I don't know how to number equations without a preamble, so please cut me a little slack.
Of course $\omega = -\frac{1}{2} + \frac{\sqrt{-3}}{2}$, right?
The notation with the bold A comes from a really old book found in some public libraries and used bookstores.

REPLY [1 votes]: I would add $\mathcal{O}_{\mathbb{Q}(\sqrt{-3})}$ to the list and rank them thus:

$\mathcal{O}_{\mathbb{Q}(\sqrt{-3})}$
$\mathbb{Z}[\omega]$ (assuming $\omega$ has been defined)
$\mathbb{Z}\left[-\frac{1}{2} + \frac{\sqrt{-3}}{2}\right]$
$\mathbb{Z}\left[\frac{i \sqrt{3} - 1}{2}\right]$ (I wouldn't call myself an algebraic number theorist, but I don't like this one either, I guess I would prefer to limit $i$ to discussion of Gaussian integers).
${\bf A}(-3)$ (Ethan Bolker used this one in a book that's available as a Dover reprint).

As others have already mentioned, neither $\mathbb{Z}[\sqrt{-3}]$ nor $\mathbb{Z}[\sqrt{-27}]$ are integrally closed.
Even though $\frac{\sqrt{-3}}{2} = \frac{1}{2} + \omega$, I don't know quite what to make of $\mathbb{Z}\left[\frac{\sqrt{-3}}{2}\right]$.


text:
\section{INTRODUCTION}

In the context of robotics and autonomous driving, online trajectory planning, usually as part of a hierarchical planning architecture, is still an essential part of research  to meet the requirements of navigation in increasingly complex and highly dynamic environments.
In contrast to classical path planning approaches~\cite{lavalle2006,lamiraux2004}, trajectory planning takes the temporal profile into account and enables improved performance as well as explicit compliance with kinodynamic and dynamic constraints.
An established method is the extension of the well-known elastic band (EB) path planning approach~\cite{quinlan1995} to trajectory deformation in~\cite{delsart2008}.
Lau et al. present a method that represents trajectories by Bézier splines and adheres to kinodynamic constraints of non-holonomic robots~\cite{lau2009}.
Not only for mobile robots, but especially for integrator dynamics, online planning algorithms based on covariant or stochastic gradient descent and obstacle potentials are provided in~\cite{ratliff2009,kalakrishnan2011}.
Delsart et al. extend the EB approach to the deformation of trajectories rather than paths~\cite{delsart2008}.
Lau et al.~\cite{lau2009} optimize trajectories represented by splines according to kinodynamic constraints of the robot.

\begin{figure}[t]
	\begin{tikzpicture}[font=\footnotesize]
	\tikzstyle{box1}=[draw, rectangle,minimum width=3.7cm, minimum height=0.8cm, align=center, rounded corners=1ex]
	\tikzstyle{box2}=[box1, minimum width=3.9cm]
	\tikzstyle{colored}=[fill=gray!15]

	\node[box1] (ocp) at (0,0) {\textbf{Optimal control problem}\\ \scriptsize Optimize w.r.t. controls (+states/time)};

	\node[box1, xshift=-2.3cm, yshift=-1.6cm] (mpc_nlp) at (ocp) {\textbf{Nonlinear program}\\ \scriptsize (or nonlinear system of equations)};
	\node[box1, colored, yshift=-1.27cm] (mpc) at (mpc_nlp) {\textbf{Model predictive controller}};

	\node[box2, xshift=2.3cm, yshift=-1.6cm] (flat_sys) at (ocp) {\textbf{Flat system model}\\ \scriptsize Optimize w.r.t. flat output (+time)};
	\node[box2, yshift=-1.27cm] (flat_nlp) at (flat_sys) {\textbf{Nonlinear program}};
	\node[box2, yshift=-1.27cm] (soft_constr) at (flat_nlp) {\textbf{Soft-constraint approximation}\\ \scriptsize Unconstrained optimization problem};
	\node[box2, colored, yshift=-1.27cm] (teb) at (soft_constr) {\textbf{Timed-Elastic-Band approach}\\ \scriptsize Time-optimal, \scriptsize finite-diff. collocation};

	\draw [-latex] (ocp) -- (mpc_nlp) node [pos=0.5,align=center, left=0.45cm] {Direct methods\\(or indirect methods)};
	\draw [-latex] (mpc_nlp) -- (mpc) node [pos=0.5,align=center, left] {State feedback};
	\draw [-latex] (ocp) -- (flat_sys) node [pos=0.5,align=center, right=0.45cm] {Conversion of\\cost \& constraints};
	\draw [-latex] (flat_sys) -- (flat_nlp) node [pos=0.5,align=center, right] {Direct methods};
	\draw [-latex] (flat_nlp) -- (soft_constr) node [pos=0.5,align=center, right] {Penalty methods};
	\draw [-latex] (soft_constr) -- (teb) node [pos=0.5,align=center, right] {State feedback};
	\end{tikzpicture}
	\caption{From optimal control to online motion planning}
	\label{fig:ocp_to_motion_planning}
	\vspace{-\baselineskip}
\end{figure}

Many optimization based approaches can be derived from a generic optimal control formulation~\cite{gulati2011, bonalli2019} and interpreted with state feedback as a variant of predictive control.
Predictive controllers repeatedly solve an optimal control problem (OCP) during runtime while commanding the first action of the optimal control trajectory to the system in each closed-loop step.
\reffigc{fig:ocp_to_motion_planning} shows two examples for such derivations. The left side shows what is commonly known as model predictive control (MPC) of continuous-time systems.
Direct methods discretize the OCP to obtain a nonlinear program (NLP) for which many efficient solving techniques exist~\cite{betts2010_book}.
State feedback then completes the approach to a model predictive controller. Note that the controller type depends on the OCP formulation,
e.g., receding horizon MPC and variable horizon MPC.
Since the computational burden is large, many approaches restrict the solution space or approximate the original problem.
For example the dynamic window approach (DWA)~\cite{fox1997} can be interpreted as a special receding horizon MPC scheme~\cite{ogren2005}.
The search space is restricted to a (collision-free) constant control input for the complete horizon.
The required computation times are low but due to the less degrees of freedom in control, the approach is suboptimal and cannot predict motion reversals such that control of car-like robots is rather limited.
Another approach is the Timed-Elastic-Band (TEB) approach, which was originally derived as a scalarized multi-objective least squares optimization~\cite{roesmann2012}.
It can also be derived from a time-optimal control problem as shown in the right of \reffig{fig:ocp_to_motion_planning}.
Hereby, the robot kinematics are expressed geometrically similar to a flat system model in the pose space and a nonlinear program is obtained by applying direct transcription, in particular finite-difference collocation.
The nonlinear program is then transformed to an unconstrained least-squares problem by applying quadratic penalty functions~\cite{roesmann2017}.
In~\cite{roesmann2017_iros}, the TEB is extended to car-like robots, however, the flat system model limits the definition of arbitrary constraints, e.g. limits on the steering rate are not included yet.
Recently, an extension and reformulation in terms of Lie groups is proposed in~\cite{deray2019}.

Since computational resources have increased and algorithms have become more efficient, the interest in full MPC-based approaches has been growing.
Path following control with recursive feasibility and stability properties is provided in~\cite{faulwasser2016_tac}.
Zhang et al. generate collision-free trajectories and considers general obstacles and that can be represented as the union of convex sets~\cite{zhang2017optimizationbased}.
A recent approach based on convex inner approximations provides feasible and collision-free solutions in a few solver iterations~\cite{schoels2019nmpc}.

Motion planning for robot navigation usually includes non-Euclidean rotational components, i.e. the robot's heading.
The contribution of this paper is as follows: We propose an MPC-based motion planning scheme that differs from others by the explicit consideration of orientation groups during optimization.
To our best knowledge, available MPC-based approaches are tailored for Euclidean state spaces.
Our MPC formulation is versatile and includes many common realizations including receding horizon quadratic form and shrinking horizon time-optimal objectives.
We further provide a generic, highly customizable and easily extendable C++ software framework with Robot Operating System (ROS) integration (\textit{mpc\_local\_planner}).

The paper is organized as follows:
\refsecc{sec:prob_description} provides the formal problem description of the approach and \refsec{sec:realization} the numerical realization.
Section~\ref{sec:evaluation} first evaluates the proposed approach with a kinematic bicycle model
and then conducts a comparative analysis for a common navigation scenario.
Finally, section~\ref{sec:conclusions} concludes the work.


text:
\begin{document}

\author{Assaf Goldberger and Ilias Kotsireas}

\title{Formal Orthogonal Pairs via Monomial Representations and Cohomology}

\maketitle

\abstract{A Formal Orthogonal Pair is a pair $(A,B)$ of symbolic rectangular matrices such that $AB^T=0$. It can be applied for the construction of Hadamard and Weighing matrices. In this paper we introduce a systematic way for constructing such pairs. Our method involves Representation Theory and Group Cohomology. The orthogonality property is a consequence of non-vanishing maps between certain cohomology groups. This construction has strong connections to the theory of Association Schemes and (weighted) Coherent Configurations. Our techniques are also capable for producing (anti-) amicable pairs. A handful of examples are given.}

\section{Introduction}
A (classical) \emph{Hadamard Matrix} of order $n$ is a $n\times n$ matrix $H$ over $\{-1,1\}$ such that $HH^T=nI_n$. A \emph{Weighing Matrix} of order $n$ and weight $k$ is a matrix $W$ over $\{-1,0,1\}$ such that $WW^T=kI_n$. We shall say that $H$ is a $H(n)$ and $W$ is a $W(n,k)$. A well-known necessary condition for the existence of Hadamard matrices (excluding the trivial cases $n = 1, 2$) is that $ n \equiv 0 \,\, (mod \,\,4)$. The sufficiency of the condition $n \equiv 0 \,\, (mod \,\, 4)$ is the famous Hadamard Conjecture, which states that an $H(n)$ should exist for every $n$ divisible by $4$. N. J. A. Sloane maintains an on-line database of Hadamard matrices of various orders \cite{NJAS:HM:DB}. The Magma computer algebra system \cite{Magma:1997} features two databases containing Hadamard and skew-Hadamard matrices of various orders.\\

There are hundreds of constructions for Hadamard and Weighing Matrices. One prolific method is to employ \emph{Orthogonal Designs}, see \cite{Geramita:Seberry:LNPAM:1979}, \cite{Seberry:ODs:2017}. This is a symbolic $n\times n$ matrix $O$ with commuting indeterminate entries taken from a set $\{0,t_1,\ldots,t_m\}$ such that $OO^T=\sum s_it_i^2 I_n$ for some positive $(s_1,\ldots,s_m)\in \ZZ^m$ with $\sum s_i=n$. In a typical application, one would like to replace the indeterminates with matrix blocks. The problem is that blocks usually do not commute. Hence by substituting $t_i\gets B_i$, one is led to the condition that $B_iB_j^T=B_jB_i^T$ for all $i,j$. We say that $(B_i,B_j)$ is an \emph{Amicable Pair}.\\

Another prolific method is that of \emph{Cocyclic Matrices}. These are matrices $M$ indexed by a finite group $G$ such that for all $i,j$, $M_{i,j}=f(i^{-1}j)\omega(i^{-1},j)/\omega(i^{-1},i),$ where $f:G\to \{-1,0,1\}$ is some function, and $\omega:G\times G \to \{-1,1\}$ is a \emph{2-cocycle} (see below, this is slightly inconsistent with some of the literature, e.g. as in \cite{Horadam1995}). Allowing $f$ to take values in a ring, they form a *-Algebra (i.e. closed under addition, multiplication and transpose), which is why they are good candidates for being Hadamard matrices. Cocyclic matrices arose first from an abstract notion of orthogonality \cite{deLauney:Flannery:ADT:2011}. Finding Cocyclic Hadamard Matrices is an active area of research, see for example \cite{Alvarez:AAECC:2012}, \cite{Alvarez:JSC:2018}, \cite{OCathain:Roeder:DCC:2011}. Many known Hadamard Matrices are found to be Cocyclic, see for example \cite{Horadam:PUP:2007,Horadam:CC:2010}. There is a close connection between Cocyclic Matrices and automorphisms. If $M$ is a $\{-1,0,1\}$-matrix, an automorphism of $M$ is a pair $(L,R)$ of $\{\pm 1\}$ monomial matrices (= signed permutations) such that $LMR^T=M$. The collection of all automorphisms is a group, denoted $\Aut(M)$ under matrix multiplication. For a Cocyclic $M$, one has a central $2$-covering group of $G$ as an automorphism subgroup.\\

In this paper we will introduce a new construction for Hadamard and weighing matrices. We define

\begin{defn}
	Let $I,J$ be finite disjoint sets of (not necessarily commuting) indeterminates. A \emph{Formal Orthogonal Pair} (FOP) is a pair $(A,B)$ of rectangular matrices such that
	\begin{itemize}
		\item[(i)] The entries of $A$ are $\pm i$ for elements $i\in I\cup \{0\}$.
		\item[(ii)] The entries of $B$ are $\pm j$ for elements $j\in J\cup \{0\}$.
		\item[(iii)] $AB^T=0$.
	\end{itemize}
\end{defn}

The matrices $A$ and $B$ are assumed to be over the non-commutative ring $\ZZ\{I\cup J\}$ generated over $\ZZ$ by the symbols in $I\cup J$, where $-x$ is the negative of $x$. The equality $AB^T=0$ is to be understood over that ring.\\

Note that unlike with Orthogonal Designs, we do not assume that the indeterminates commute. In fact, by substituting arbitrary blocks, even rectangular (all of the same size) into an FOP, we still will get the orthogonality. Note that this notion of FOP is different from the notion of "Orthogonal Pairs" as appears in \cite{Craigen:ArsComb:1992}\\

In this paper, we will show how to construct orthogonal pairs, by techniques from Representation Theory and Group Cohomology.  By no means we can construct all of them. Those that we can construct come together with an automorphism group $G$, whose action preserves both $A$ and $B$. Moreover, the orthogonality property will be a consequence of the specific group action. Our construction may be explained in terms of Representation Theory (simpler), and Group Cohomology (harder, but more general). For the cohomology point of view, we refer the reader to \cite{goldberger2019cohomology} where the theory is explained in detail. As a side effect, we can also construct (formal) amicable pairs.

\section{Projective Monomial Representations}\label{mon}
\subsection{Basic Theory}
We are given a finite group $G$. A \emph{Projective Representation} of $G$ is a map $\rho: G\to GL(V)$ where $V$ is a finite dimensional vector space over a field $F$, and for all $g,g'\ni G$, $\rho(gg')=\pm \rho(g)\rho(g')$. In our applications we will have $F=\QQ$. By abuse, we will say that $V$ is a Projective Representation of $G$. If we write $\rho(gg')=\omega(g,g') \rho(g)\rho(g')$ for $\omega:G\to \{\pm 1\}$, then $\omega$ is a $2$-cocycle:

$$ \omega(g',g'')\omega(g,g'g'')=\omega(gg',g'')\omega(g,g'), \ \forall g,g',g''\in G.$$ We say that $\omega$ is the cocycle of the projective representation $V$. A projective representation $V$ is \emph{irreducible} if there is no $G$-invariant subspace other than 0. It is a theorem that when $char F$ is prime to $2|G|$, then each representation breaks down to a direct sum of irreducible representations. A \emph{morphism} of representations $V\to V'$ is a homomorphism of spaces, that commutes with the $G$-action. Note that $V,V'$ need to have the same cocycle.\\

Attached to a 2-cocycle $\omega$, is a central extension $\widetilde G$ of $G$ such that
$$1 \to \{\pm 1\}\to \widetilde{G} \to G \to 1$$ is exact, and $\{\pm 1\}$ is in the center of $\wG$. The 2-cocycle $\omega$ can be recovered from this extension by the existence of a functional section $s:G\to \wG$ such that $s(g)s(g')=\omega(g,g') s(gg')$. It is easy to see that every representation $\tilde \rho:\wG\to GL(V)$ of $\wG$ gives rise to a projective representation of $\rho:G\to GL(V)$ (with cocycle $\omega$), defined by $\rho=\tilde\rho\circ s$. Conversely, any projective representation of $G$ can be lifted to an ordinary representation of $\wG$.
As with ordinary representations, we have\\
\begin{thm}[Schur's Lemma]
	If $T: V\to V'$ is a morphism between irreducible projective representations, then either (i) $T=0$, or (ii) $T$ is an isomorphism.$\Box$
\end{thm}

\begin{defn}
	A projective monomial representation is a projective representation $\rho:G\to GL(V)$ together with a basis $M=\{m_i\}$ of $V$ such that for any $g\in G$, $gm_i=\pm m_j$, $j=j(g,i)$. In other words, the representing matrix $[\rho(g)]_M$ in the basis $M$ is monomial (= a signed permutation).
\end{defn}
We call $M$ a \emph{monomial basis} of $V$.

\begin{ex}
	Let $X$ be a finite $G$-set. Then each $g\in G$ acts on $X$ as a permutation $\pi(g)$. Consider the vector space $V=F[X]$, of formal sums of elements of $X$ with coefficients in $F$. Then $V$ is a monomial (in fact permutation) representation of $G$, with monomial basis $M=X$.
\end{ex}

\begin{ex}
	Let $G=B_3\subset O(3)$ the symmetry group of the cube $C=[-1,1]^3\subset \RR^3$. Then $B_3$ is the group of all $\{\pm 1\}$-$3x3$ monomial matrices, and the inclusion $B_3\subset O(3)$ is a monomial representation $V$. Moreover,  $\hat V=\RR[C]$ is an 8-dimensional permutation representation of $G$, and it can be shown that $\hat V$ contains $V$ as a direct summand.
\end{ex}

\begin{ex}\label{cocrep} {\bf Cocyclic Representations.}\label{cocyclic} Let $G$ be a finite group and $\omega:G\times G \to \{\pm 1\}$ be a 2-cocycle. We define an action of $G$ on $F[G]$ by
	$$(g,[g'])\mapsto \omega(g,g')[gg'].$$ Then it is easy to check that this defines a projective monomial representation of $G$.
\end{ex}

\begin{defn}
	Let $V,V'$ be projective monomial representations of $G$, with monomial bases $M,M'$. Let $Hom_M(V,V')$ be the set of all matrices $[T]_{M,M'}$ representing a morphism $T:V\to V'$ with respect to $M$ and $M'$. We also write $End_M(V)=Hom_M(V,V)$.
\end{defn}
Given $V,M,V',M'$ as in the definition, we may define a $G$-action on the group $Hom(V,V')$ (=linear transformations $V\to V'$ as vector spaces) by setting
$$(gf)(v)\ := \ gf(g^{-1}v).$$ This defines an {\bf ordinary} $G$-representation on $Hom(V,V')$. By passing to matrix representations, it takes the form
$$ (g,[T]_{M,M'})\mapsto [g]_M [T]_{M,M'} [g]_{M'}^{-1}.$$ The elements of $Hom_M(V,V')$ are precisely those that are left invariant under this action.

We claim:
\begin{prop}\label{prop24}
	If $V,V'$ are two projective monomial representations, then $Hom_M(V,V')$ is spanned over $F$ by a basis $\{E_i\}$ of $\{0,-1,1\}$-matrices with pairwise disjoint supports. Each $E_i$ is supported on an orbit of the $G$-action on $M\times M'$.
\end{prop}

\begin{proof}
	The elements of $H_M(V,V')$ are those that satisfy
	\be \label{inv} [T]_{M,M'}=[g]_M[T]_{M,M'}[g]_{M'}^{-1}.\ee By ignoring signs, the group $G$ acts by permutations on the monomial bases $M$ and $M'$ and hence on $M\times M'$, splitting $M\times M'=\sqcup_{i=1}^m O_i$ to a disjoint union of $G$-orbits.\\

	Pick a representative $(v,w) \in O_i$. Then the matrix value of $[T]_{M,M'}$  at each position $(v',w')\in O_i$ is determined uniquely from the value at $(v,w)$. More precisely, if the value at $(v,w)$ is $a$, and $gv=\eps v'$, $gw=\mu w'$, then the value at $(v',w')$ is $\eps\mu a$. By setting up $a=1$ (and $0$ at all other orbits) we get a $\{0,\pm 1\}$-matrix $E_i$, and every other matrix in $Hom_M(V,V')$ is a unique linear combination of the $E_i$.
\end{proof}

\begin{rem}It should be noted that
	some of the $E_i$ may be zero. This happens when the $G$-action gives conflicting signs to an element (equivalently all elements) in $O_i$. We discuss this in \S\ref{ori} below. This phenomena is fundamental to our construction.
\end{rem}

\subsection{Structure as *-algebras, modules and relation to Weighted Coherent Configrations}

For a monomial representation $V$, $End_M(V)$ is a matrix algebra: It is closed under addition and matrix multiplication. It is also a *-algebra (i.e. closed under the transpose), as is evident from equation \eqref{inv}. But it has more structure. It has a basis $\{E_i\}$ of $\{0,-1,1\}$-matrices with disjoint supports. This implies that $E_i^T=E_j$ for some $j$, and that \be E_iE_j=\sum_k \lambda^k_{i,j} E_k\ , \ \lambda^k_{i,j}\in \ZZ.\ee

Moreover, by forgetting signs we have a permutation $G$-action on the monomial basis, and hence obtain a representation which we shall denote $|V|$. Then $End_M(|V|)$ is again a *-algebra, has a basis $\{F_i\}$ of $\{0,1\}$-matrices supported on the $G$-orbits of $M\times M$, and satisfy
\be F_iF_j=\sum_k \mu^k_{i,j} E_k\ , \ \mu^k_{i,j}\in \ZZ_{\ge 0}.\ee
The *-algebra $End_M(|V|)$ is a special case of a \emph{Coherent Configuration} ~\cite{higman1975coherent}. Moreover, there exists a $\{0,-1,1\}$-matrix $W$, called a \emph{weight}-matrix ~\cite{higman1976coherent}, such that
\be\label{W} End_M(|V|)\to End_M(V), \ \ A \mapsto A\circ W\ee
is a surjective map of vector spaces. Here $\circ$ is the Hadamard  ( = entrywise) product.\\

All of the above can be extended to modules. The group $Hom_M(V,V')$ is closed under multiplication by $End_M(V)$ on the left, and $End_M(V')$ on the right. Hence it is a \emph{bimodule}. Moreover, it has a $\{0,-1,1\}$-basis $P_i$ with disjoint support such that
\be E_iF_j=\sum \theta^k_{i,j} F_k\ , \ \theta^k_{i,j}\in \ZZ.\ee
Likewise one can define the bimodule $Hom_M(|V|,|V'|)$ and a weight matrix with a property analogous to \eqref{W}.

\begin{ex} {\bf The algebra of Cocyclic Matrices}
	By taking the projective monomial representation $V$ of Example \ref{cocrep}, the algebra $End_M(V)$ is precisely the algebra of Cocyclic Matrices (cf. Introduction).
\end{ex}

\subsection{Monomial and Induced Representations}\label{23} Suppose that $V$ is a projective monomial representation of $G$ with basis $M$. Then $M=\sqcup M_i$ is a union of $G$-orbits and accordingly $V=\bigoplus_i V_i$, a sum of projective monomial representations. For the remainder of section \ref{23}, assume $M$ is $G$-transitive. Pick up $m_0\in M$ and let $H=\{h\in G: hm_0=\pm m_0\}.$ Let $\widetilde{H}\subset \wG$ be the preimage of $H$. Then a $G$-sets $M\simeq G/H=\wG/\widetilde{H}$. Now, write $hm_0=\chi(h)m_0$ for $\chi:H\to \{\pm 1\}$. Then $m_0$ spans a 1-dimensional projective representation of $H$ and with respect to the cocycle $\omega|_{H\times H}$, which in turn is a coboundary (of $\chi$).
\begin{thm}\label{lem1}
	Let $F[G]$ be the cocyclic projective representation. We define a projective right $H$ action by letting
	$([g],h)\mapsto \omega(g,h)[gh].$ With this action
	$$V\simeq F[G]\tensor_H (Fm_0),$$ as projective $G$ representations.
\end{thm}
\begin{proof}
	We give a map $V\to F[G]\tensor_{H} (Fm_0)$ as follows. For each $m\in M$, choose an element $g_m\in \wG$ s.t. $g_mm_0=\eps(m) m$, $\eps(g)=\pm 1$. Then we send $m\mapsto \eps(m)\omega(g_m,1)[g_m]\tensor m_0$. Acting by $g$ on the left, we must show that $gm$ maps to the action of $g$ on $\eps(g)\omega(g_m,1)[g_m]\tensor m_0$. We may write $gg_m=g_{n}h$ for the basis element $n$ such that $gm=\tau(g,m)n$, and $h\in H$.\\

	 Interpreting the $g$ action on $F[G]$, we have to check that
	 $\tau(g,m)n \mapsto \omega(g,g_m)\eps(g)\omega(g_m,1)[gg_m]\tensor m_0=\omega(g,g_m)\eps(m)\omega(g_m,1)[g_nh]\tensor m_0=\omega(g,g_m)\eps(m)\omega(g_m,1)\chi(h)\omega(g_n,h)[g_n]\tensor m_0.$ This amounts to showing that
	 \be\label{ugly} \tau(g,m)\omega(g_n,1)\eps(n)= \omega(g,m)\eps(m)\omega(g_m,1)\chi(h)\omega(g_n,h).\ee

	 But by using $gg_m=g_nh$ and the projectivity of $V$, we
	see that $\omega(g,g_m)^{-1}g(g_mm_0)=\omega(g_n,h)^{-1}g_n(hm_0)$. Then \eqref{ugly} follows using $hm_0=\chi(h)m_0$, $g_mm_0=\eps(m)m$, $g_nm_0=\eps(n)n$ and $gm=\tau(g,m)n$, and the fact that $\omega(x,1)$ is independent of $x$. This shows that $V\to F[G]\tensor_H Fm_0$ is a $G$-homomorphism. The elements $[g_m]\tensor m_0$ are an $F$-basis for $F[G]\tensor_H Fm_0$, hence our map is an isomorphism.
\end{proof}

For every 2-cocycle $\omega$ on $G$ and every subgroup $H\subset G$ such that $\omega|_{HxH}=d\chi$ is a coboundary, one can construct a 1-dimensonal projective representation $U=span\{u_0\}$ of $H$, by letting $hu_0:=\chi(h)u_0.$
\begin{defn}
	The projective induced representation is
	$$ Ind_H^G U = F[G]\tensor_H U.$$
\end{defn}

 The induced representation $V=Ind_H^G U$, is monomial, with monomial basis $[g_i]\tensor u_0$, $g_i$ being any choice of  right coset representatives: $G=\sqcup_i g_iH$.\\

 \begin{rem}
 	We see from here that \emph{Induction} produces all projective monomial representations, up to isomorphism. Note that the coboundary source $\chi$ \emph{is not unique}. It may be altered by a character: $\chi'(h)=\psi(h)\chi(h)$ where $\psi:H\to \{\pm 1\}$ is a homomorphism. Different choices of $\chi$ will result in \emph{non-isomorphic} induced representations.
 \end{rem}

\subsection{Formal Orthogonal Pairs}
We have seen that $Hom_M(V,V')$ has a basis of $\{0,-1,1\}$-matrices. It may sometimes happen that $Hom_M(V,V')=0$. This is the case, if and only if the irreducible components of $V$ and those of $V'$ have no isomorphic components in common (by Schur's Lemma). As a corollary of Proposition \ref{prop24}, we have:

\begin{lem}\label{orth}
	Suppose that $A\in Hom_M(W,V)$ and $B\in Hom_M(W,V')$. Then
	$$Hom_M(V,V')=0 \ \ \implies \ \ AB^T=0.$$
\end{lem}

\begin{proof}
	We claim that $B^T\in Hom_M(V',W)$, from which it follows that $AB^T\in Hom_M(V',V)=0 \implies AB^T=0$. The elements of $Hom_M(V,W)$ are characterized as the matrices $C$ such that $[g]_M C [g]_{M'}^{-1}=C$ for all $g\in G$. Taking transpose shows that $B^T\in Hom_M(V',W)$.
\end{proof}

\begin{cor}
	Taking formal linear combinations of the $\{0,-1,1\}$ bases of $Hom_M(W,V)$ and $Hom_M(W,V')$, we get a \emph{Formal Orthogonal Pair}.
\end{cor}

\subsection{Orientability}\label{ori}
We are left with the question, how to construct a triple of projective monomial representations $(V,V',W)$, such that $Hom_M(W,V)\neq 0$, $Hom_M(W,V')\neq 0$, but $Hom_M(V',V)=0$? We can analyze the situation by decomposing $V,V',W$ into irreducible components over $F$. But this does not help us to construct the representations in the first place. Fortunately there is a group-theoretic practical test which can help in designing the representations.\\

First, choose a 2-cocyle $\omega:GxG\to \{\pm 1\}$, and two subgroups $H,H'\subset G$ such that the restriction to $H$ and $H'$ are couboundaries:
\begin{align}
\label{27}\omega(h_1,h_2)&=\chi(h_1h_2)\chi(h_1)^{-1}\chi(h_2)^{-1} \quad \forall h_1,h_2\in H\\
\label{28}\omega(h'_1,h'_2)&=\chi'(h'_1h'_2)\chi'(h'_1)^{-1}\chi'(h'_2)^{-1} \quad \forall h'_1,h'_2\in H.
\end{align}
Next we define two 1-dimensional projective representations $U,U'$ of $H,H'$, such that $(h,u_0)\mapsto \chi(h)u_0$ and $(h',u'_0)\mapsto \chi'(h')u'_0$. We induce to $G$ to obtain $V=Ind_H^G U$ and $V'=Ind_H^G U'$, with monomial bases $M=\{[g_i]\tensor u_0\}$ and $M'=\{[g'_i]\tensor u'_0\}$. The elements of $Hom_M(V,V')$ are the matrices $A$ s.t. $[g]_M A [g]_{M'}^{-1}=A$ for all $g\in G$. The action of $G$ partitions $A$ (more precisely $M\times M'=G/H\times G/H'$) into orbits.
\begin{defn}
	An element $(m,m')\in M\times M'$ is \emph{orientable}, if for every element $t\in G$ such that $tm=\eps(t) m$ and $tm'=\eps'(t) m'$, we have $\eps(t)=\eps'(t)$. Otherwise it is \emph{non-orientable}.
\end{defn}

As a corollary of Proposition \ref{prop24} we have,
\begin{lem}
	Orientability depends only on the orbit. We have
	$$dim Hom_M(V,V')\ = \ \text{Number of orientable orbits.}$$
\end{lem}
Finally there is a technical criterion for orientability:
\begin{lem}[\cite{goldberger2019spectral}]\label{or}
	Let $V,V'$ be the induced projective monomial representations as above. Then a point $(m,m')=([g_i]\tensor u_0,[g'_j]\tensor [u'_0])$ is orientable, if and only if
	$$ \chi(g_i^{-1}tg_i)=\chi'(g^{'-1}_jtg'_j)\quad \forall t\in g_iHg_i^{-1}\cap g'_jH'g^{'-1}_j.$$
\end{lem}
\begin{rem}
	Orientability depends on the choice of trivilalizations $\chi,\chi'$. One could modify $\chi$ to $\chi\psi$ where $\psi:H\to \{\pm 1\}$ is a homomorphism.
\end{rem}

\section{The Cohomology Picture}
\subsection{A spectral sequence}
The theory in \S\ref{mon} can also be cast in terms of spectral sequences and cohomology. In fact this approach is more holistic, can be generalized to more contexts (action on coefficients, higher dimensional designs, connections to Brauer Groups, dual theories and more). Another advantage is that formulae can be derived from Homological Algebra. We only give here a brief statement, while a full treatment is developed in \cite{goldberger2019spectral}.\\

We begin with a finite group $G$, and two finite $G$-sets $X$ and $Y$. Let $\mu=\{\pm 1\}$, and $\mu^+=\{0,-1,1\}.$ An $X\times Y$ matrix is a $\mu^+$-valued matrix indexed by $X\times Y$. The group $G$ acts on those matrices by the rule
$$(gA)_{x,y}:=A_{g^{-1}x,g^{-1}y}.$$ Two matrices $A$ and $B$ are \emph{D-equivalent} if $A=D_1AD_2$ for $\mu$-valued diagonal matrices $D_i$. D-equivalence is denoted as $A\sim_D B$.
\begin{defn}
	A \emph{Cohomology Developed Matrix} (CDM) is an $X\times Y$ matrix such that
	\be\label{CDM} gA\sim_D A \quad \forall g\in G.\ee
\end{defn}
It can be shown that CDMs are elements of $Hom_M(V,V')$ for projective monomial $V,V'$, and vice versa, all elements of
$Hom_M(U,W)$ are CDM's.\\

Note that CDM's are closed under the Hadamard (= entrywise) product. Moreover, if we fix a set of orbits
$\mathcal O$ which is the support, then they form an Abelian group, denoted by $CDM(\mathcal O).$ Let $Mat(\O)$ be the group of all $\O$-supported matrices under the Hadamard product. We have
$$ CDM(\O)/D-\text{equiv.}=H^0(G,Mat(\O)/D-\text{equiv.}).$$
To compute the cohomology in the right hand side, we use a suitable resolution and obtain the following theorem. For simplicity we assume that the only trivial $D$-equivalence on $Mat(\O)$ is given by scalar matrices.

\begin{thm}
	There exists a first quadrant spectral sequence $E\implies H^*(G,Mat(\O)/D-\text{equiv.})$ whose $E^1$-page is given by
	\begin{align}
	    E^1_{0,q} &= H^q(G,\mu),\\
	    E^1_{1,q} &= \bigoplus_{H\in Stab(X)} H^q(H,\mu) \oplus \bigoplus_{H'\in Stab(Y)} H^q(H',\mu)\\
	    E^1_{2,q} &=\bigoplus_{Q\in Stab(\O)} H^q(Q,\mu)\\
	    E^1_{p,q} &=0 \quad  \forall p\ge 3.
	\end{align}
	The differentials are given by the restriction maps. $Stab(X)$ is a the set of stabilizer subgroups of all points in $X$, up to conjugacy.
\end{thm}

\begin{rem}
		The elements of $E^2_{0,2}$ are generated by 2-cocycles that are in the kernel of $d^1$ - the restriction to the stabilizers of points in $X$ and $Y$. This is manifested in conditions \eqref{27}-\eqref{28}. In addition, the elements of $E^3_{0,2}$ must have trivial image in $H^1(Q,\mu)$ for all $Q\in Stab(\O).$ This is the orientability condition.
\end{rem}

\section{Examples}

\subsection{$G=$ A vector Space}
In this example we take $G=(\ZZ/2)^n$. The cohomology $H^2(G,\{\pm 1\})$ is represented by bilinear forms $\omega:G\times G\to \{\pm 1\},$ modulo isotropic forms (i.e $\omega(v,v)=1$). Take $n=4$, and the form $\omega(v,w)=\sum_{i \mod 4}v_iw_{i+1}.$ Consider the isotropic subspaces $H=span\{(1,1,1,1),(0,1,1,1)\}$, $H'=span\{(1,1,1,1),(0,1,0,1)\}$ and $K=span\{(0,0,0,1)\}$. Thus $\omega$ descends to the trivial class in the restriction to those spaces, with the following trivializations:
\begin{align*}
\chi&=\chi_H((0,0,0,0))=1;&\ \chi_H(v)=-1 \text{ otherwise},\\
\chi'&=\chi_{H'}((0,1,0,1))=-1;&\ \chi_H(v)=1 \text{ otherwise},\\
\chi_K&=1.
\end{align*}
With this we obtain the FOP
{\small
$$A \ = \ \left(\begin{array}{rrrrrrrr}
b & a & b & -a & a & b & -a & -b \\
b & a & -b & -a & -a & b & a & b \\
a & b & a & -b & b & a & -b & -a \\
a & b & -a & -b & -b & a & b & a
\end{array}\right),\ B \ = \ \left(\begin{array}{rrrrrrrr}
c & d & d & d & c & -c & c & d \\
-c & -d & d & -d & c & c & c & d \\
-d & -c & c & -c & d & d & d & c \\
-d & -c & -c & -c & -d & d & -d & -c
\end{array}\right).$$
}

\subsection{A partial weighing block-circulant family}
Let $n\ge 4$ be an integer, $G=\ZZ/2 \wr \ZZ/n$ be the wreath product of size $n2^n$. Then $V:=(\ZZ/2)^n \vartriangleleft G$. We work with $\omega=1$ the trivial cocycle. Next,we choose three subspaces $H_1,H_2,H_3\subset V$ and three characters $\chi_i:H_i\to \{\pm 1\}.$ We restrict our attention to spaces generated by standard vectors $\{e_i\}$. We encode the choice $(H,\psi)$ by a $\{0,-1,1\}$-vector $\rho$, where for instance $\rho=(1,-1,0,0,\ldots)$ means that $H$ is spanned by $e_1,e_2$ and $\chi(e_1)=1,\chi(e_2)=-1$. Write $X_i=G/H_i$. A straightforward application of Lemmas \ref{or} and \ref{orth} yields:

\begin{lem}\label{41} Let $(A,B)$ be the formal pair generated by the CDM's on $X_1\times X_3$ and $X_2\times X_3$. Then
	 $AB^T=0$ if the circulant matrices $C_i$ whose first row is $\rho_i$ satisfy
		$(C_1C_2^T)_{i,j}<(|C_1||C_2|^T)_{i,j} \ \forall i,j.$ Furthermore,
		 $AA^T=\lambda I$ if $(C_1C_1^T)_{i,j}<(|C_1||C_1|^T)_{i,j} \ \forall i\neq j.$
\end{lem}

As an example, let $\rho_1=(-1,1,\ldots,1)$, $\rho_2=(1,-1,-1,1,1\ldots,1)$ and $\rho_3=(0,0,0,1,1,\ldots,1)$. These satsify conditions (a) and (b) in Lemma \ref{41}, hence we obtain an FOP $(A,B)$, each of size $n\times 8n$. $A$ consists of $3$ orientable orbits of row weight =8 each  and $B$ has $2$ orientable orbits. Moreover, the orientable orbits of $A$ have disjoint support from those of $B$. As a corollary we get:

\begin{thm}
	For every integer $n\ge 4$, there exist a partial weighing matrix $P$ of size $4n\times 8n$ and row weight 32. Moreover, there is a reordering of $P$ such that it is composed out of circulant $n\times n$ blocks.
\end{thm}

\begin{proof}(Sketch) We have $AA^T=24I_n$ and $BB^T=16I_n$, as formal matrices. It follows that the five orbits of $A$ and $B$ are mutually orthogonal. As they are disjoint, we can combine them into one formal orthogonal matrix $C=A+B$, s.t. $CC^T=32I_n$. Due to formality, we may substitute a $4x1$ column for each symbol, four of these taken from a Hadamard $H(4)$ and the fifth=0. This constructs $P$. The the $\ZZ/n$ factor in $G$ acts as automorphisms on $P$, and by analyzing orbits and taking care of signs we obtain the block-circulant structure.
\end{proof}

\subsection{A Formal Amicable Pair}
It is easier to generate Amicable Pairs, i.e. a pair $(A,B)$ such that $AB^T$ is symmetric. For this we need $A$ and $B$ to be $X\times Y$ CDM's such that all $X\times X$ CDM's must be symmetric. The setup includes a group $G$ whose orbits on $X\times X$ are symmetric. An example is the Dihedral group $D_n$ realized as the set of affine transformations $G=\{x\mapsto ax+b\ | \ b\in \ZZ/n,\ a=\pm 1\}.$ Assume that $n$ is even. We choose $H=\{x\mapsto \pm x\}$ and $H'=\{id\}\cup \{x\mapsto x+n/2\}$. Take $\omega=1$ and let $\chi$ and $\chi'$ to be the unique nontrivial characters. The resulting Formal Amicable Pair is:

{\tiny
$$ A,B= \left(\begin{array}{rrrrrr}
c & -c & -a & a & -b & b \\
-b & -a & -b & c & c & a \\
-a & -b & c & -b & a & c \\
-c & c & a & -a & b & -b \\
-b & -a & -b & c & c & a \\
-a & -b & c & -b & a & c
\end{array}\right), \left(\begin{array}{rrrrrr}
f & -f & -d & d & -e & e \\
-e & -d & -e & f & f & d \\
-d & -e & f & -e & d & f \\
-f & f & d & -d & e & -e \\
-e & -d & -e & f & f & d \\
-d & -e & f & -e & d & f
\end{array}\right).$$
}

\subsection{Summary} Formal Orthogonal Pairs provide a new methodology to construct Hadamard and Weighing Matrices. The main tools in their construction involves representation theory and Group Cohomology. They can be used either via block substitutions, or by partitioning a matrix into formal orthogonal tuples.

\bibliographystyle{alpha}
\bibliography{biblfop}

\end{document}


text:
\begin{document}

\maketitle

\begin{abstract}
  Evaluating treatment effect heterogeneity widely informs treatment
  decision making. At the moment, much emphasis is placed on the
  estimation of the conditional average treatment effect via flexible
  machine learning algorithms. While these methods enjoy some
  theoretical appeal in terms of consistency and convergence rates,
  they generally perform poorly in terms of uncertainty
  quantification. This is troubling since assessing risk is crucial
  for reliable decision-making in sensitive and uncertain
  environments. In this work, we propose a conformal inference-based
  approach that can produce reliable interval estimates for
  counterfactuals and individual treatment effects under the potential
  outcome framework. For completely randomized or stratified randomized experiments with perfect
  compliance, the intervals have guaranteed average coverage in finite
  samples regardless of the unknown data generating mechanism. For
  randomized experiments with ignorable compliance and general
  observational studies obeying the strong ignorability assumption,
  the intervals satisfy a doubly robust property which states the
  following: the average coverage is approximately controlled if
  either the propensity score or the conditional quantiles of
  potential outcomes can be estimated accurately.  Numerical studies
  on both synthetic and real datasets empirically demonstrate that
  existing methods suffer from a significant coverage deficit even in

  simple models. In contrast, our methods achieve the
  desired coverage with reasonably short intervals.

\end{abstract}

\input{intro}
\input{setup}
\input{counterfactual}
\input{effect}
\input{extension}

\section*{Acknowledgment}
E. C. was supported by Office of Naval Research grant N00014-20-12157. L. L. was supported by NSF OAC grant 1934578.
The authors are grateful to David Arbour, Susan Athey, Eytan Bakshy, Stephen Bates, Richard A. Berk, Peter J. Bickel, Jelena Bradic, Andreas Buja, Michael Celentano, Peng Ding, Dean Eckles, Nikolaos Ignatiadis, Yucen Luo, Edward Kennedy, Roger Koenker, Arun Kumar Kuchibhotla, Elizabeth L. Ogburn, Zhimei Ren, Thomas S. Richardson, James Robins, Chiara Sabatti, Jasjeet S. Sekhon, Dylan Small, Sean Taylor, Eric Tchetgen Tchetgen, Yuhao Wang, Jeffrey Wong, Bin Yu, and Xiao-Hua Zhou for their constructive feedback.

\bibliography{conformal_causal}
\bibliographystyle{plainnat}

\clearpage
\appendix

~\\
\begin{center}
  \begin{Large}
    \textbf{Appendix}
  \end{Large}
\end{center}

\input{appendix}

\end{document}


text:
\section{Related work}\label{PreviousWork}

Developing faster SDP solvers has drawn a fair amount of attention in both the optimization and the theoretical computer science communities. Most of the existing results for SDP solvers can be cast in two different approaches: direct, convex methods and factorization methods. We summarize previous work below.

A number of recent works aim to produce large-scale SDP solvers.
Among the direct approaches (which proceed in the convex domain directly), \citet{SPARSESDP} introduced a Frank-Wolfe type method for a restricted class of SDPs. Here, the key is that each iteration increases the rank of the solution only by one, so that if only a few iterations are required to reach satisfactory accuracy, then only low dimensional objects need to be manipulated. This line of work was later improved by \citet{HybridDSP}, \citet{FastSpecta} and \citet{SublinearSDP} through hybrid methods.
Still, if high accuracy solutions are desired, a large number of iterations will be required, eventually leading to large-rank iterates. In order to overcome such issue, \citet{SketchyDecisions} recently proposed to combine conditional gradient and sketching techniques in order to maintain a low rank representation of the iterates.

Among the low-rank approaches, our work is closest to (and indeed largely builds upon) recent results of~\citet{bhojanapalli2018smoothed}. For the real case, they consider a penalized version of problem~\eqref{eq:eq3} (which we here refer to as  (P-SDP)) and its related penalized Burer--Monteiro formulation, here called (P-P). With high probability upon random perturbation of the cost matrix, they show approximate global optimality of ASOSPs for (P-P), assuming $k$ grows with $\sqrt{m}$ and either the SDP is compact or its cost matrix is positive definite.
Given that there is a zero-measure set of SDPs where SOSPs may be suboptimal, there can be a small-measure set of SDPs where ASOSPs are not approximately optimal~\citep{bhojanapalli2018smoothed}. In this context, the authors resort to smoothed analysis, in the same way that we do here.

One important drawback of that work is that the final result does not hold for the original SDP, but for a non-equivalent penalized version of it. This is one of the points we improve here, by focusing on smooth SDPs as defined in~\citep{boumal2016non}.