text:
\subsection{The case of non-simple matrices}
\label{subsec:proof-main-lemma-bireg}

In this subsection we will show to decompose an arbitrary $A|B$-biregular graph
into a collection of simple biregular graphs, i.e., where
the matrices are all simple.
We will first present the intuition.

Let $G=(U,V,E_1,\ldots,E_t)$ be a $A|B$-biregular graph,
where $A\in \bbNop^{t\times m}$ and $B\in \bbNop^{t\times n}$.
Let $U=U_1\cup\cdots\cup U_m$ and $V=V_1\cup\cdots \cup V_n$
be the witness partition.
For each $1\leq j \leq m$ and $1\leq j'\leq n$,
we define $G_{j,j'}$ as the subgraph of $G$ restricted to the vertices in $U_j \cup V_{j'}$.
We will argue that for each $j,j'$,
the graph $G_{j,j'}$ is a $A'|B'$-biregular graph
where $A',B'$ are both simple matrices, and further that the simple
matrices for different $j$ and $j'$ satisfy some natural additional constraints
that we can capture in our construction.
Simple matrices correspond to biregular graph problems where:
\begin{itemize}
\item  for each color $c$, either
the cardinality constraint on adjacent left-to-right edges for every partition is periodic, or the
cardinality constraint on adjacent left-to-right edges for every partition is a fixed outdegree.
\item for each color $c$, the same holds for right-to-left edges.
\end{itemize}
Consider partitions  $U_j$ and $V_{j'}$,  fix a color $c$ and let us focus on the constraints
for elements of $U_j$ $c$ on adjacent edges in $V$. The matrix $A$ specifies such a constraint,
which is either fixed or periodic. Suppose the constraint is a fixed number $r$, which specifies
the total outdegree in all of $V$ for elements of $U_j$.
We can partition $U_j$ further based on whether the number of those adjacent elements that lie in $V_j$
is $1, 2 \ldots r$. This gives some fixed number of partition classes, with each associated to a
different constraint on outgoing edges in $G_{j,j'}$. But all of these constraints
will be of fixed degree.
Now conversely suppose the constraint is of the form $\prdp{a}$ for some $a$. Again we can partition
the $U_j$ according to whether the outdegree to elements of $V_j$ is $\prdp{b}$ for $b \leq a$.
All of the constraints for different partition classes will be  periodic.
Similarly, if the constraint is $\prdp{\infty}$,
we partition $U_j$ according to whether the outdegree to elements of $V_j$ is $\prdp{\infty}$,
or $\prdp{0},\ldots,\prdp{p-1}$.
The situation is the same if we consider constraints on adjacent edges for elements of $V_{j'}$.
Of course, there are additional restrictions on the guesses we can make for different
choices of $j$ and $j'$. For example in the case where the constraint given by $A$ for
$U_j$ is a fixed element $r$, we need to be sure that the guesses on outdegrees
into the  different $V_{j'}$ add to one. But the number of these ``global choices'' is also
fixed.

We now present the formalization of this idea.
For a column vector $C\in \bbNop^{t\times 1}$,
a behavior function of $C$ towards $n$ partitions
is a function $g:[t]\times [n]\to \bbNop$ such that:
\begin{align*}
\begin{pmatrix}
\sum_{j=1}^n g(1,j)
\\
\vdots
\\
\sum_{j=1}^n g(t,j)
\end{pmatrix}
& = \
C
\end{align*}
and for each $1\leq i \leq t$ the following holds.
\begin{itemize}
\item
If $C_{i,1}$ is periodic, then for each $1\leq j \leq n$,
$g(i,j)$ is periodic.
\item
If $C_{i,1}$ is fixed, then for each $1\leq j \leq n$,
$g(i,j)$ is fixed.
\end{itemize}
We define by $\cG[C,n]$ the set of all behavior function of $C$ towards $n$ partitions.

For each $C$, for each $1\leq j \leq n$, we define the following matrix $M[C,n,j]$:
\begin{align*}
M(C,n,j) & :=
\begin{pmatrix}
g_1(1,j) & g_2(1,j) & \cdots & g_k(1,j)
\\
g_1(2,j) & g_2(2,j) & \cdots & g_k(2,j)
\\
\vdots & \vdots  & \ddots & \vdots
\\
g_1(t,j) & g_2(t,j) & \cdots & g_k(t,j)
\end{pmatrix},
\end{align*}
where $g_1,\ldots,g_k$ are all the behavior functions of $C$ towards $n$ partitions.

It is not difficult now to show the following.
Let $G=(U,V,E_1,\ldots,E_t)$ be $A|B$-biregular graph,
and let $U=U_1\cup\cdots \cup U_m$ and $V=V_1\cup \cdots \cup V_n$
be any partitions.
\begin{itemize}
\item
If $G$ is $A|B$-biregular with witness partition $U=U_1\cup\cdots \cup U_m$
and $V=V_1\cup\cdots\cup V_n$,
then for every $1\leq i \leq m$ and $1\leq j \leq n$,
the subgraph $G_{i,j}$ is $M(A_{*,i},n,j)|M(B_{*,j},m,i)$-biregular.
\item
If for every $1\leq i \leq m$ and $1\leq j \leq n$,
the graph $G_{i,j}$ is $M(A_{*,i},n,j)|M(B_{*,j},m,i)$-biregular,
then $G$ is $A|B$-biregular graph with witness partition
$U=U_1\cup\cdots \cup U_m$
and $V=V_1\cup\cdots\cup V_n$.
\end{itemize}

From here, for $A\in \bbNop^{t\times m}$ and $B\in \bbNop^{t\times n}$,
the Presburger formula for an arbitrary $A|B$-biregular graph
can be defined by taking the conjunction of formulas for the
simple case.
Formally we proceed as follows.
\begin{itemize}
\item
For each $1\leq i \leq m$,
for each behavior function $g$ of $A_{*,i}$ towards $n$ partitions,
we have a variable $X_{i,g}$.

Let $\vX_i=(X_{i,g_1},\ldots,X_{i,g_k})$, where $g_1,\ldots,g_k$ are all the behavior functions
of $A_{*,i}$ towards $n$ partitions.
\item
Similarly,
for each $1\leq i \leq n$,
for each behavior function $g$ of $B_{*,i}$ towards $m$ partitions,
we have a variable $Y_{i,g}$, and we can let $\vY_i=(Y_{i,g_1},\ldots,Y_{i,g_k})$, where $g_1,\ldots,g_k$ are all the behavior functions
of $B_{*,i}$ towards $m$ partitions.
\end{itemize}
The formula $\bireg_{A|B}(\vx,\vy)$ is defined as follows.:
\begin{align*}
\bireg_{A|B}(\vx,\vy) & := \
\exists \vX_1\cdots \exists \vX_m\ \exists \vY_1\cdots\exists\vY_n
\
\bigwedge_{i=1}^m\bigwedge_{j=1}^n
\bireg_{M(A_{*,i},n,j)|M(B_{*,j},m,i)}(\vX_i,\vY_j)
\\ &
\qquad\qquad\qquad\qquad\wedge \
\vx=(\vX_1\cdot\vone,\ldots,\vX_m\cdot\vone) \ \wedge\
\vy=(\vY_1\cdot\vone,\ldots,\vY_n\cdot\vone).
\end{align*}
Intuitively, $X_{i,g}$ represents the number of vertices
in $U_i$ with behavior function $g$.

This formula can then be modified for the complete case as follows:
\begin{align*}
\biregc_{A|B}(\vx,\vy) & := \
\exists \vX_1\cdots \exists \vX_m\ \exists \vY_1\cdots\exists\vY_n
\
\bigwedge_{i=1}^m\bigwedge_{j=1}^n
\biregc_{M(A_{*,i},n,j)|M(B_{*,j},m,i)}(\vX_i,\vY_j)
\\ &
\qquad\qquad\qquad\qquad\wedge \
\vx=(\vX_1\cdot\vone,\ldots,\vX_m\cdot\vone) \ \wedge\
\vy=(\vY_1\cdot\vone,\ldots,\vY_n\cdot\vone).
\end{align*}

config: arxiv


TITLE: A problem in Graph theory $e\le 5/3 v-10/3$
QUESTION [1 upvotes]: I am having the problem in the following question:

Suppose $G$ is a connected simple planar graph with $e$ edges and $v$ vertices with no cycles of length 4 or less. Then prove that $$ e\le \frac{5}{3}v-\frac{10}{3},\ \ \text{for }v\ge 4 $$

I know the following result  Let $G$ be a connected planar simple graph with $v$ vertices, where $v \ge 3$ and $e$ edges. Then $e \le 3v - 6$.
But I am unable to do the above. So could you please help me.
Thanks.

REPLY [1 votes]: Hint Redo the same proof as the one for $e \leq 3v-6$:
By Euler
$$v-e+f=2$$
Now, if there are no cycles, $f=1$ and prove the result.
If there are cycles, count the edges by faces. Since each face has at least 5 edges, your count is at least $5f$. Since you count each edge exactly twice, your count is exactly $2e$.
This shows that
$$2e \geq 5f$$
Combine this with Euler formula and you are done


TITLE: BU with tensor product H-space structure
QUESTION [10 upvotes]: Hi,
I came across the space $BU_\otimes$ when struggling with twisted K-theory. Segal proved that this is an H-space, right? I have read a dozen times by now that the group $[X, BU_\otimes]$ consists of the vector bundles of virtual dimension 1. I can clearly see the semi-group structure there, but what does the inverse of such a bundle look like?
Best regards,
Ulrich Pennig

REPLY [14 votes]: I'll write $U(X)=[X,BU_\otimes]$.  So $U(X)\subset K(X)=[X,Z\times BU]$ is the multiplicatively closed subset corresponding to "virtual bundles of rank 1".
Likewise, I'll write $I(X)=[X,BU]\subset K(X)$ for the ideal of "virtual bundles of rank 0".
There's a bijection $a\mapsto 1+a$ from $I(X)$ to $U(X)$.
Here's the claim: if $X$ is compact (let's say it's a finite CW-complex of dimension $n$), then $I(X)$ is a nilpotent ideal (in fact, $I(X)^{n+1}=0$).  This is a generic fact about multiplicative cohomology theories, and it can be proved in a number of ways; you can think about it in terms of the multiplicative properties of the Atiyah-Hirzebruch spectral sequence, for instance.
For such $X$, it is clear that elements of $1+a\in U(X)$ are invertible, given by the series $(1+a)^{-1}=1+a+a^2+\cdots$ which terminates since $a\in I(X)$ and $I(X)$ is nilpotent.
For infinite dimensional $X$, you need to argue a little harder.  If $X=\lim_{\to} X_i$ where the $X_i$ are finite CW-complexes, then there is a surjection $K(X)\to \lim_{\leftarrow} K(X_i)$, which restricts to  surjections for $I(X)$ and $U(X)$.
The kernel is a $\lim^1$-term.  If the $\lim^1$-term vanishes, then it's clear that elements of $U(X)$ are invertible, since their images in the $U(X_i)$ are invertible.  It's enough to check that $\lim^1$-vanishes in the case that $X=BU_\otimes$, which is a standard calculation.


TITLE: Prove that G contains at least |X| − 1 fixed-point-free elements, i.e., elements g such that Fix(g) is empty.
QUESTION [0 upvotes]: Let $G$ be a finite group acting transitively on a finite set $X$ where $|X| > 1$. Prove that $G$ contains at least $|X| − 1$ fixed-point-free elements, i.e., elements $g$ such that
$Fix(g)$ is empty.

REPLY [1 votes]: The average number of fixed points is 1.  The identity fixes $|X|$ points.  The rest is arithmetic.... How many 0's do you need to have any chance of bringing the average down to 1?
How do you know the average number of fixed points is one?  Each element of $X$ is in an orbit of length $|X|$ and so fixed by $|G|/|X|$ elements of $G$.  There are $|X|$ elements of $X$, so there are $|X|\cdot\frac{|G|}{|X|}=|G|$ pairs $(g,x)$ with $x^g=x$.  Thus in total, the $|G|$ elements of $G$ have $|G|$ fixed points.


TITLE: Axioms of noncommutative rings
QUESTION [1 upvotes]: Is there an abelian group $R$ with multiplication operator with this properties ?
(i) $a(bc)=(ab)c$
(ii) $a(b+c)=ab+ac$  , $(b+c)a=ba+ca$

And a unique element $e$ s.t
  (iii) $ea=a\quad \forall a\in R $

But there exists $x\in R$ s.t $xe\neq x$ .

REPLY [2 votes]: My solution was inspired by this question.
Consider the set $R$ of matrices with integer entries of the form
$$
\begin{pmatrix} a & a\\ b & b \end{pmatrix}
$$
Then $R$ is an abelian group under addition and a semigroup under the multiplication of matrices. Distributivity also holds. Now, the formula
$$
\begin{pmatrix} a & a\\ b & b \end{pmatrix}\begin{pmatrix} x & x\\ y & y\end{pmatrix} = \begin{pmatrix} a(x+y) & a(x+y)\\ b(x+y) & b(x+y) \end{pmatrix}
$$
shows that every matrix
$\begin{pmatrix} x & x\\ y & y\end{pmatrix}$ such that $x + y = 1$ is a right identity. However, there is no left identity. You can of course take the dual operation if you wish to have a left identity and no right identity, like in your question.


TITLE: Expressive power of FO with $\mu$
QUESTION [8 upvotes]: Let us consider the first-order logic extended with the least fixed point operator (FO+LFP). That is, together with the usual first-order formulas, we also have formulas of the form:
$$\mu X[\overline{y}] . \phi(X, \overline{y})$$
where $X$ (must occur positively in $\phi$) is a "predicate" variable of arity equal to the length of sequence of "parameters" $\overline{y}$. The semantic of this formula (in a given algebraic structure) is the least set $X^*$ such that:
$$X^*(\overline{y})  \Leftrightarrow \phi(X^*, \overline{y})$$
For example, if $R$ is a binary relation symbol, then:
$$\mu X[y_1, y_2] . R(y_1, y_2) \vee (\exists_z R(y_1, z) \wedge X(z, y_2))$$
defines the transitive closure of $R$.
If $A$ is an algebraic structure, let us write $\mathit{Th_{lfp}}(A)$ for the first-order theory of $A$ extended with the least fixed point operator (i.e. the set of all FO+LFP sentences that are true in $A$).
Does there exist an algebraic structure $A$ such that both of the following hold:

$\mathit{Th_{lfp}}(A)$ is decidable
FO+LFP is strictly more expressive than FO over $A$ (i.e. there is a FO+LFP formula that is not equivalent to FO formula over $A$)?

An example of a structure that satisfies the first property (but does not satisfy the second) is the structure of rational numbers with the natural ordering $\langle\mathcal{Q}, \leq\rangle$.
An example of a structure that satisfies the second property (but does not satisfy the first) is the structure of natural numbers with the natural ordering $\langle\mathcal{N}, \leq\rangle$.
One intuition is that there should be no such structure $A$ --- if $A$ defines arbitrary long well-founded orders, then the theory of $A$ should be undecidable; and if it does not define, then LFP seems to be pretty useless.
Another intuition is that there might be such a structure, because the above intuition is difficult to formalize, thus may contain essential holes.

REPLY [2 votes]: You also might be interested in the paper The Role of Decidability in First Order Separations over Classes of Finite
Structures by Steven Lindell and Scott Weinstein. While they don't address the above question directly, they investigate connections between the decidability of the first-order theory of a (family of) structures and the power of first order vs. LFP definability. For example, they prove that "$\text{Th}(\mathcal{C}$) is decidable" implies $\text{FO}(\mathcal{C}) \neq \text{FO+LFP}(\mathcal{C})$ when $\mathcal{C}$ is a proficient family of structures.
(Here $\text{Th}(\mathcal{C})$ is the set of first-order sentences satisfied for all structures in $\mathcal{C}$. Proficient simply means that there is no finite bound on the closure ordinals of all LFP formulas.)


TITLE: Derivative of determinant at some point
QUESTION [1 upvotes]: Let $c:\mathbb{R} \rightarrow \mathbb{M}_n(\mathbb{R})$ defined by $$c(t)=A e^{tB}$$ where $A\in GL(n,\mathbb{R})$ and $B \in \mathbb{M}_n(\mathbb{R})$.
The question ask me to find $c'(0)$ and $(\text{det}\circ c)'(0)$.
Then find the derivative of $\text{det}:\mathbb{M}_n(\mathbb{R})\rightarrow \mathbb{R}$ at $A$

I did the first part, where:
$$c'(0)=AB$$
$$(\text{det}\circ c)'(0)=\text{det}(A)  \text{Tr}(B)$$
But I don't know how to deduce $D\text{det}_A$, the derivative of $\text{det}$ at $A$.
Here is what I was thinking, since $D\text{det}_A$ takes initial tangent vector (which is $c'(0)$) to initial tangent vector of $\text{det}\circ c$.
Hence,
$$D\text{det}_A(c'(0)) =(\text{det}\circ c)'(0) $$
and I don't know what to do next.

REPLY [0 votes]: For finding $d(\det)_A$, let's use what you've already computed.  Given $B\in M_n(\mathbb{R})$, we have the curve $c(t)=A\exp{tA^{-1}B}$ with $c(0)=A$ and $c'(0)=B$.  Thus
\begin{align*}
d(\det)_A(B)&=d(\det)_A(c'(0))\\
&=(\det\circ c)'(0)\\
&=\det{A}\operatorname{tr}(A^{-1}B).
\end{align*}


TITLE: Graph Theory book with lots of Named Graphs/ Graph Families
QUESTION [4 upvotes]: I'm doing a research about an operation on graphs and I am now in the point where I want to apply it to some named graphs or to some of the graph families like paths, cycles, wheels, etc. I am wondering if there is a book or a paper that contains different named graphs and graph families. Currently I have the following references:
mathworld.wolfram.com/topics/SimpleGraphs.html
en.wikipedia.org/wiki/Gallery_of_named_graphs
altermundus.fr/downloads/documents/NamedGraphs.pdf
graphclasses.org/smallgraphs.html
What I am looking for is like an encyclopedia of graphs where I can look at the graph and its properties. I'm looking for graph families where you can easily get the next graph (ex.paths, cycles). My above references are webpages and I'm wondering if there might be a book containing these things. Well any additional resources of any form will be very welcome.
Thank you!

REPLY [3 votes]: Recently, I also needed such a reference. The House of Graphs proved to be very helpful.


TITLE: Why are quadratic forms so special and why not investigate in higher forms?
QUESTION [6 upvotes]: Ok, this is a soft question.
If $K$ is a field of characteristic different from $2$, one can use the polarization identity to get a one-to-one correspondence between

homogeneous polynomials of degree $2$ in $K[X_1,...X_n]$ variables,
symmetric bilinear forms $K^n\times K^n\to K$,
symmetric $n\times n$-matrices with $K$-entries.

Quadratic forms are extensively studied. Why not to study 'cubic forms' or more generally '$n$-forms' in the same intensity? Perhaps one gets a correspondence of cubic forms with $3$-dimensional $n\times n\times n$-matrices. Is it just not investigated so much as quadratic forms just because these 'higer dimensional matrices' are more difficult to handle?

REPLY [1 votes]: The recent work of Bhargava and his collaborators is (among other things) aimed at studying higher degree forms, higher dimensional matrices, and so on.  You might be interested in looking at it, if only to get an idea of what people are doing.  (If you search for Manjul Bhargava on the arxiv, you will find lots of papers.)


TITLE: A Remark on One-Parameter Differmorphism Group
QUESTION [1 upvotes]: I am reading Arnold's ODE (3rd edition) and I am confused with the remark.
Page 62 :

Remark. The condition of smooth dependence on the time t is needed in order to eliminate pathological examples such as the following:
let { $\alpha$ } be a basis of the group R i.e., a set of real numbers such that each real number has a unique representation in the form of a finite linear combination of numbers of the set with integer coefficients.

Q1.) I think he is not talking about the vector basis since the integer is not even a field.
How can I show there indeed exists such "basis" ?

To each number $\alpha$ of the basis we assign the translation of the line by some distance, paying no attention to other elements of the basis. Setting $g^{\alpha_1+...+\alpha_k}=g^{\alpha_1}...g^{\alpha_k}$, we obtain a one-parameter transformation group each of whose element is a translation of the line consequently a differmorphism; but in general $g^t$ is not a smooth function of t and is even discontinuous.

Q2.) I don't know how this reasoning shows $g^t$ must be smooth with respect to t, as he remarks at the beginning.

Instead of smoothness with respect to t one may require only continuous(from which smoothness is a consequence) but we have no need to do this.

Q3.) I don't understand this either. Please give me a hint.

REPLY [1 votes]: Regarding Q1), I think that you cannot show anything, because such a basis does not exist.  Indeed, suppose it exists, and pick some (necessarily nonzero) $\alpha$ belonging to it. $\alpha/2$ is a nonzero real number, so it must be uniquely expressed in the form
$$
\frac{\alpha}{2} = k_1 \alpha_1 + \ldots + k_n \alpha_n,
$$
where $k_1, \dots, k_n \in \mathbb{Z} \setminus \{0\}$, $\alpha_1, \dots, \alpha_n$ belong to the basis.  Then we have
$$
\alpha = (2k_1) \alpha_1 + \ldots + (2k_n) \alpha_n,
$$
which means that $\alpha$ has two representations, a contradiction.
I would look for a such a pathological one-parameter group in the following way. Take any non-measurable solution of Cauchy's functional equation $h(t + s) = h(t) + h(s)$, and define
$$
g^t(x) = e^{h(t)}x, \quad x \in \mathbb{R}.
$$

EDIT: We have obtained a homomorphism of the additive group of reals into the
groups of scalings of $\mathbb{R}$.  I chose it since it looks to me more natural in the context of linear differential equations.  However, to remain in the setup of the textbook one should rather choose a homeomorphism of the additive group of reals into the groups of translations of $\mathbb{R}$.  Then
$$
g^t(x) = x + h(t), \quad x \in \mathbb{R}.
$$

Now, you can find answers to Q2) and Q3) in Overview of basic facts about Cauchy functional equation.


TITLE: Calculate the number of functions $f:A \rightarrow B$ satisfying the condition $f(1) \le f(2)...\le f(n)$
QUESTION [0 upvotes]: Let $n$ be a positive integer and Denote by $X$ the set of all
  functions $f$ from the set $A=\{1,2,...n\}$ to the set $B=\{1,2,3 \} $.
Calculate the number of functions $f:A \rightarrow B$ satisfying the
  condition $f(1) \le f(2)...\le f(n)$

This is an exam practice question for Discrete Math and I am trying to understand the solutions given. It is a relatively straight forward question, but the solutions aren't very clear.

It says that the list of values $(f(1),f(2),...,f(n))$ must have the
  form $(1,1,..,1,2,2,,,2,3,3,,,3)$. Let $k_i$ be the number of entries
  equal to $i$ in such a list for $i = 1,2,3$. The number of lists of
  this form is $k_1 + k_2 + k_3  = n$.

This is all fine, and then it says:

The number of such triples is ${n+2}\choose{2}$.

There is no further explanation. My first thought was that the solution would be the stirling number $S(n,3)$, but this clearly also counts functions which do not satisfy the condition. How was the solution of the number of triples derived?
Many thanks!

REPLY [2 votes]: Define a function $f$ this way:

Write the numbers $1,\ldots,n$.
If there is some $j$ such that $f(j)=1$ and $f(j+1)>1$ put a line ($|$) between $j$ and $j+1$. If $f(1)\neq 1$ put the line at the beginning. If $f(n)=1$ put the line at the end.
If there is some $j$ such that $f(j-1)<2$ and $f(j)=3$ then put a line between $j-1$ and $j$. If $f(n)\neq 3$, put it at the end. If $f(1)=3$, put it at the beginning.

This way you assign a function $f$ (of the set that you want to count) to a sequence of $n$ numbers and two lines, and this assignation is clearly bijective. Thus, you have to count how many of such sequences there are. Note that, although the numbers are different, you must write them in order, so the computation is the same as if they were indistiguishable. There are $n$ numbers and two lines, that is, $n+2$ symbols. Then the number of such functions is $\binom{n+2}2$, or, equivalently, $\binom{n+2}n$.


TITLE: Possibilities of an automorphism on $Z_{20}$
QUESTION [1 upvotes]: This is a question from the book Contemporary Abstract Algebra, specifically chapter 6 on isomorphisms. The question is:
Suppose that $\phi: Z_{20} \to Z_{20}$ is an automorphism and $\phi(5) = 5$. What are the possibilities of $\phi(x)$?
Attempt of Solution
I have made an attempt at solving it. Firstly, we know that an isomorphism carries the identity of the first group to the identity of the second group. Since the identity is $0$, and it is an automorphism, so $\phi(0) = 0$.
Next up, we know that an isomorphism preserves the order of an element. So I made a list of all elements of $Z_{20}$ with the same order. For reference, here's the list (excluding $5$ and $0$):
\begin{align*}
1) & \, \{1, 3, 7, 9, 11, 13, 17, 19 \} &\text{ (Order is 20) } \\
2) & \, \{2, 6, 14, 18 \} &\text{ (Order is 10) } \\
3) & \, \{4, 8, 12, 16 \} &\text{ (Order is 5) } \\
4) & \, \{10 \} &\text{ (Order is 2) } \\
5) & \, \{15 \} &\text{ (Order is 4) } \\
\end{align*}
So we can restrict $\phi$ in that if it is an automorphism, it must map $0, 5, 10$ and $15$ to themselves. Also, it can only map the rest of the elements to some element in their set otherwise order will change.
That give $8! \cdot 4! \cdot 4!$ possibilities in total. Is this approach correct, or I'm missing something else?

REPLY [3 votes]: Let $x=\phi(1)$ so that $\phi(5)=5x$. Then the automorphisms you want are those corresponding to the solutions of the congruence $5x\equiv5\bmod 20$ which are coprime to $20$. The previous congruence is equivalent to
$$
x\equiv1\bmod 4
$$
and thus $x\in\{1,9,13,17\}$


TITLE: Checking if $Z$ is an F-distribution using change of variable technique
QUESTION [0 upvotes]: Two independent random variables $X_1$ and $X_2$ have the following pdf
$f(x_1,x_2)= e^{-x_1-x_2}$ for $x_1, x_2>0$, and $0$, otherwise.
Using the change of variable technique, determine whether $Z=X_1 X_2^{-1}$ has an F-distribution. If it has, state its degrees of freedom and hence $var(Z)$.
I would really appreciate it if someone could guide me on how to go about this question. Thanks in advance.

REPLY [0 votes]: I do not know what "change of variables" I can use in computing, but we have for $z \in \def\R{\mathbf R}\R$, $z \ge 0$
\begin{align*}
  \def\P{\mathbf P}\P(Z < z) &= \int_{\{x \in \R^2 \mid x_i > 0, x_1 < zx_2\}} f(x)\, dx\\
    &= \int_{(0,\infty)} \int_{(0,zx_2)} \exp(-x_1-x_2)\, dx_1\, dx_2\\
    &= \int_{(0,\infty)} \int_{(0, zx_2)} \exp(-x_1)\, dx_1 \exp(-x_2)\, dx_2\\
    &= \int_{(0,\infty)} \left[-\exp(-x_1)\right]_0^{zx_2}\, \exp(-x_2)\, dx_2\\
    &= \int_{(0,\infty)} \bigl(1 - \exp(-zx_2)\bigr)\,\exp(-x_2)\, dx_2\\
    &= \int_{(0,\infty)} \exp(-x_2) - \exp\bigl(-(z+1)x_2\bigr)\, dx_2\\
    &= 1 - \frac 1{z+1}
\end{align*}
To compute the density function of $Z$, we take the derivative, hence
$$ f_Z(z) = \frac 1{(z+1)^2}, \qquad z \ge 0 $$


TITLE: Residue of $f(z) = \frac{z-2}{z^2}\sin(\frac{1}{1-z})$ at $z = 1$
QUESTION [3 upvotes]: Given the complex function $f(z) = \frac{z-2}{z^2}\sin(\frac{1}{1-z})$, how can we calculate the residue at the essential singularity at $z = 1$?

REPLY [4 votes]: Let us define $\xi=z-1$ (such that we can calculate the residue at $\xi=0$). The function is given by
$$\frac{1-\xi}{(1+\xi)^2} \sin(\xi^{-1}).$$ For the residue, we need to obtain the coefficient in front of $\xi^{-1}$ in the Laurent expansion around $\xi=0$. We have the Laurent expansions
 $$\sin(\xi^{-1}) = \sum_{k=0}^\infty \frac{(-1)^k}{(2k+1)!\xi^{2k+1}}$$ and
$$\frac{1-\xi}{(1+\xi)^2} = \sum_{k=0}^\infty (-1)^k (2k+1) \xi^k$$ valid for $0<|\xi|<1$.
As the original function is the product of these functions, the residue (= coefficient in front of $\xi^{-1}$) is given by
$$
\begin{align}
\text{Res}_{z=1}\left[\frac{z-2}{z^2}\sin\left(\frac{1}{1-z}\right) \right]
&= \sum_{k=0}^\infty \frac{(-1)^k}{(2k+1)!} (-1)^{2k} (4k+1) \\
&=\sum_{k=0}^\infty \frac{(-1)^k [2 (2k +1 ) -1]}{(2k+1)!}  \\
&= 2\cos(1) - \sin(1) \approx 0.24
\end{align}$$


TITLE: Which kind of subsets of primes one needs to generate a positive ratio of the natural numbers?
QUESTION [7 upvotes]: Not knowing elementary number theory well, I ask this one, which is not very clear to answer, rather I am looking for some results around this question or known theorems. The problem is the following:
The set of prime numbers $\mathbb{P}=2,3,5,7,11...$ generates $\mathbb{N}$ by multiplication. Now I am interested in subsets $S$ of $\mathbb{P}$, which generate a positive fraction of all numbers, that means:
There is $\epsilon>0$ which holds the following equation for all $N \in\mathbb{N}$ big enough: $$\frac{\|span(S)_{\leq N}\|}{N}\geq \epsilon N$$ where $span(S)_{\leq N}$ is the subset of $\mathbb{N}_{\leq N}$, which consists of the numbers, whose prime factors are all elements of $S$.
Clearly $S$ has to be infinite to have this property, but what can one say about $S$ more specificely? Is there any known criterions or examples for $S$ being too small to generate a positive ratio of the natural numbers?

REPLY [12 votes]: Let $T=\mathbb P\setminus S$. If $\sum_{p\in T}1/p=\infty$, then $\prod_{p\in T}(1-1/p)=0$ and for any $\epsilon>0$, there exist $p_1,\ldots,p_n\in T$ such that $\prod_{i=1}^n(1-1/p_i)<\epsilon$. Now modulo $P=p_1\cdots p_n$, the fraction of integers that have no factor of the form $p_i$ with $i\le n$ is $\prod(1-1/p_i)<\epsilon$. Hence in the entire set of natural numbers, those with no factor in $T$ has density less than $\epsilon$.
Conversely, if $\sum_{p\in T} 1/p<\infty$, then let $\alpha=\prod_{p\in T}(1-1/p)$. Then $0<\alpha<1$. Let $M$ be chosen such that $\sum_{p\in T; p>M} 1/p<\alpha/2$. Then up to $N$, the number of integers that has a factor in $T$ that exceeds $M$ is at most $\sum_{p\in T; p>M} N/p<\alpha N/2$. For large $N$, the number of $n\le N$ having no factor in $T$ below $M$ is close to $\alpha N$, and hence the density of $n$'s having no factor in $T$ is at least $\alpha/2$.


TITLE: Why does $E_g\left[-\frac{(x-\mu)^2}{2\sigma^2}\right] = -\sigma^2_0+\frac{(\mu-\mu_0)^2}{\sigma^2}$
QUESTION [1 upvotes]: I'm reading about information criteria and I bumped into an example, where the author tries to approximate a true data generating normal function $g(x|\mu_0, \sigma^2_ 0)$ with an approximation model:
$$f(x|\mu,\sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right).$$
The goal is to have $f(x|\mu,\sigma^2)\approx g(x|\mu_0, \sigma^2_ 0)$. Anyways, in the text I'm reading the author then writes the following:
$$\log f(x|\mu,\sigma^2) = -\frac{1}{2}\log2\pi\sigma^2-\frac{(x-\mu)^2}{2\sigma^2},$$
which is completely clear. But this next one is where I start to get trouble, he writes:
$$E_g[\log f(x|\mu,\sigma^2)] = -\frac{1}{2}\log2\pi\sigma^2-\sigma^2_0+\frac{(\mu-\mu_0)^2}{\sigma^2},$$
where expectation has been calculated with respect to the true distribution $g$. It therefore seems to me that:

$$E_g\left[-\frac{(x-\mu)^2}{2\sigma^2}\right] =
 -\sigma^2_0+\frac{(\mu-\mu_0)^2}{\sigma^2}.$$

I don't immediately see why this is true, so I tried to show it myself:
$$E_g\left[-\frac{(x-\mu)^2}{2\sigma^2}\right]=-\frac{1}{2\sigma^2}\left(E_g\left[x^2-2x\mu+\mu^2\right]\right) = -\frac{1}{2\sigma^2}\left(E_g\left[x^2\right]-2\mu E_g\left[x\right]+E_g\left[\mu^2\right]\right)$$
$$=-\frac{1}{2\sigma^2}\left(E_g\left[x^2\right]-2\mu\mu_0+\mu^2\right).$$
In the above I have used the assumption that $E_g\left[x\right]=\mu_0$ and I also assume that $E_g\left[(x-\mu_0)^2\right]=\sigma^2_0$. So now I need to show that:
$$-\frac{1}{2\sigma^2}\left(E_g\left[x^2\right]-2\mu\mu_0+\mu^2\right)=-\sigma^2_0+\frac{(\mu-\mu_0)^2}{\sigma^2}$$
and now I start to doubt my derivation.
Question: Am I going in the right direction? Is there some mistake in my reasoning here that I have made?
P.S. If you need more information please let me know. Sorry I had small mistake in the equation, fixed.
UPDATE: to see my reference book where my question originates, please see page 62 in the book Information Criteria and Statistical Modeling

REPLY [2 votes]: \begin{equation}
E_g[x^2] = \sigma_0^2  + \mu_0^2
\end{equation}
Therefore,
\begin{equation}
\begin{aligned}
E_g[x^2] - 2 \mu \mu_0 + \mu^2 &= \sigma_0  + \mu_0^2 - 2 \mu \mu_0 + \mu^2\\
&=\sigma_0^2 + (\mu - \mu_0)^2
\end{aligned}
\end{equation}
and it holds that
\begin{equation}
E_g\left[-\frac{(x-\mu)^2}{2\sigma^2}\right] =
- \frac{\sigma^2_0+(\mu-\mu_0)^2}{2\sigma^2}.
\end{equation}
This agrees with equation (3.7) in the book you are refering to. However, when there is a relation between $\sigma_0$ and $\sigma$ the formula can be reduced.
It seems in the book you are referring to that the specified model has a $\sigma$ given by the empirical variance. Try writing this in terms of the true variance.


TITLE: the moduli spaces that contain direct sums of line bundles
QUESTION [1 upvotes]: Let $U_X(n,d)$ be the moduli space of semistable vector bundle of rank $n$ and degree $d$ over a smooth projective curves over the complex numbers.
How do I know if $U_X(n,d)$ contains direct sums of line bundles? I have found on a paper that this is true when $d=n(g-1)$ where $g$ is the genus of the curve, does any of you know why is it true? When does $U_X(n,d)$ not contain any direct sum of line bundles?
Thanks a lot!

REPLY [2 votes]: $\newcommand{\L}{\mathcal L}
\DeclareMathOperator{\rk}{rk}$
Say you have some line bundles $\L_i$ of degree $d_i$. The degree is additive, so $E = \deg (\bigoplus \L_i) = \sum_i d_i$. So to get a vector bundle of rank $n$ and degree $d$, we whould have $n$ line bundles, such that $d_1+\cdots +d_n = d$.
Now, unless they all have the same degree the sum cannot be semistable. If they have different degree, suppose that $d_1$ is the maximum. Then
$$
d_1 = \frac{\deg \L_1}{\rk \L_1} > \frac{\deg E}{\rk E} = \frac{d_1+\cdots + d_n}{n}.
$$
In other words, $d_1$ is strictly bigger than the average of all the degrees. This shows that in order for $U_X(n,d)$ to contain a direct sum of line bundles, $d$ has to be a multiple of $n$. I don't understand why you would need $d=n(g-1)$ specifically (for example, if $n=1$ then all vector bundles are sums of line bundles, in that they are just line bundles). Which paper did you see this in?


TITLE: If Electrical flux is no. of field lines passing through the area then why the formula is $E$ dot $A$ (Area)?
QUESTION [1 upvotes]: I have been taught that flux is no. of field lines passing through the surface. But my question how  does the formula for calculating electric flux is matching with the above statements?
The formula for electric flux is $E \cdot S$. How does the field lines is getting by the dot product of $E$ and $S$ (area vector). May be i am not able to understand the relation between the field lines and field strength? Please someone explain?

REPLY [1 votes]: Let me state just in case, that when we refer to a surface vector we refer to the orthogonal vector that points away from the surface:

The actual formula for flux is not the cross product (which increases when things become perpendicular), but the dot product (which increases when things become parallel), which is obviously what happens here, since the flux is gonna become larger when the surface vector becomes parallel with the electric field:

And finally, the most important, what actually is the number of "electric lines" is the flux itself, not the electric field. The field is more like the density of lines, which is the number of lines in an area of size 1 (that is why a bigger field means the strength is higher at that point, while a bigger flux can just be that you took into account a bigger area). That is why the flux is the field (density of lines [n of lines/area]) multiplied by the area! :).

(In this last picture, the electric field in the left panel, is higher than in the right panel, because you see way more lines per area unit, they are more "condensed" -> higher electric field.
But if the electric field lines in the left, when we do zoom out stop in that area and the rest is empty of lines, but in the right panel if we zoom out, there keeps appearing new ones at some point taking enough area the left panel will have higher total flux, even when in the centre it has a weaker electric field. )


text:
\iffalse

\section{Partially Linear Regression (Simplified)}
\label{sec:plr}
\swcomment{focus on the case where $k$-sparse vectors are not a
  function of the features}

Consider the following variant of \emph{partially linear regression
  (PLR)} model due to \citet{Robinson}. In this model, we have
observations $Z_i = (T_i, Y_i, X_i, x_i)$, in which $T_i\in \RR$
represents the treatment or policy applied, $Y_i\in \RR$ represents
the outcome, $X_i\in \RR^p$ represents the control, and
$x_i\in \cX\subseteq \RR^d$ is the feature vector that captures the
heterogeneity. The set of parameters are related via the following
equations:
\begin{align}
  Y_i &= \theta_0(x_i)\, T_i + f_0(X_i) + \eps, \label{maineq}\\
  T_i &= g_0(X_i) + \eta_i, \label{confounding}
\end{align}
where $\eta_i, \eps_i$ represent the unobserved noises such that
\[
 \Ex{}{\eps_i \mid X_i, x_i, T_i} = 0, \quad\Ex{}{\eta_i \mid x_i, X_i} = 0
\]
In the main equation \eqref{maineq},
$\theta_0\colon \RR^d\rightarrow [-1, 1]$ represents the treatment
effect function, the main object we would like to infer. The
confounding equation \eqref{confounding} keeps track of the dependence
of the treatment variable on controls. In particular, the controls
affect the treatment $T$ via the function $g_0$ and also affect the
outcome $y$ via the function $f_0$. We consider functions $f_0$ and
$g_0$ that are high-dimensional linear functions:
\begin{align}\label{k-sparse}
  f_0(X_i) = \langle X_i, \beta_0 \rangle, \\
  g_0(X_i) = \langle X_i, \gamma_0 \rangle
\end{align}
where $\beta_0, \gamma_0$ are both $k$-sparse vectors in $\RR^p$.
Moreover, let $q_0(x_i) = \theta_0(x_i)\gamma_0 +
\beta_0$. Consequently, this means
\[
  \langle X_i, q_0(x_i) \rangle = \Ex{}{Y_i\mid x_i, X_i}.
\]

Suppose we have $n$ observations $Z_1, \ldots , Z_n$ drawn i.i.d. from
the underlying distribution. Our goal is to estimate the treatment
effect $\theta_0(x)$ for some target feature $x$.

A common approach for estimating such quantity $\theta_0(x)$ is to
first compute a set of weights $a_i$ over the observations that
measure the relevance of each observation $Z_i$ in the estimation of
$\theta_0(x)$.  This allows us to find a local neighborhood containing
the target $x$ and then to perform a local estimation. To that end, we
adopt the \emph{generalized random forest (GRF} method due to \citet{ATW17}
for computing such set of weights. At a high level, we build a set of
$B$ trees, indexed by $b=1, \ldots , B$, such that each tree is
computed using a subsample (without replacement) of size $s$. The set
of leaves in each tree partition the feature space $\cX$ into
different regions. We can then identify a set of points $L_b(x)$ that
fall into the same leaf as the target feature $x$ in each tree $b$ and
assign weights to observations accordingly.

The key technical challenge for the estimation problem is the presence
high-dimensional confounding factors $X$. In particular, we are
primarily interested in the setting where the dimension $p$ of the
confounder $X$ is much larger than the sample size $n$. In order to
overcome the confounding effects from $X$, we rely on the double
machine learning method due to~\cite{doubleML} that orthogonalizes the
effects from $X$ when estimating $\theta$. To describe our algorithm,
we will first show how to incorporate double machine learning with a
tree learner.

\subsection{Tree Learner $\cL_T$}
Our algorithm proceeds over $B$ iterations. In each iteration $b$,
given a subsample $S_b$ as input, the tree learner first randomly
partitions the dataset into three subsets of equal sizes $S_b^1$,
$S_b^2$ and $S_b^3$. It mainly uses $S_b^1$ to place splits in the
tree, and uses the features $x_i$ in $S_b^2$ and $S_b^3$ for stopping
rules and balance maintainence. Crucially, the tree learner does not
uses the controls and outcomes in $S_b^2$ and $S_b^3$ when building
the tree, which is important for reducing the bias in the local
estimation later.

Similar to standard random forest algorithms, our tree learner starts
with a root node that contains the entire feature vector space $\cX$,
iteratively grows the tree by greedily selecting the splits that
maximize certain splitting criterion, until certain stopping condition
is met.

To overcome bias in the process of placing splits, we also incoporate
double machine learning techniques in the splitting criterion.  In
particular, at any moment of the tree building, for each parent node
$P$, the learner will first perform the following two-stage local
estimation over the set of observations in $S^1_b$ that reach $P$.
First, we compute Lasso estimates $\hat q_P$ and $\hat \gamma_P$:
\begin{align*}
  \hat \gamma_P &= \argmin_{\gamma} \frac{1}{2|P\cap S_b^1|} \sum_{Z_i\in P\cap S_b^1} (T_i
                  -\langle W_i, \gamma\rangle)^2 + \lambda_\gamma \|\gamma\|_1\\
  \hat q_P &= \argmin_{q} \frac{1}{2|P\cap S_b^1|} \sum_{Z_i\in P\cap S_b^1} (Y_i - \langle W_i, q\rangle)^2 + \lambda_q \|q\|_1
\end{align*}
for some regularization parameters $\lambda_\gamma$ and $\lambda_q$.
Given the vectors $\hat \gamma_P$ and $\hat q_P$, we compute the
residuals on the observations
\[
  \hat Y_i = Y_i -\langle W_i, \hat q_P \rangle, \quad \hat T_i = T_i -\langle
  W_i, \hat \gamma_P \rangle
\]
Importantly, this step partials out the effects from $W_i$ in each
observation, and largely reduce the bias from when we peform the
second-stage estimation:

\begin{equation*}
  \hat \theta_P = \argmin_{\theta} \frac{1}{|P\cap S_b^1|}\sum_{Z_i\in P\cap S_b^1} \frac{1}{2}\left( \langle \hat
    T_i , \theta\rangle - \hat Y_i \right)^2
\end{equation*}

Given the estimates $\hat \theta_P, \hat \gamma_P$ and $\hat q_P$ at
each parent node $P$, we would like to find an axis-aligned split of
some node into two children $C_1$ and $C_2$ such that if we perform
the same two-stage estimation separately at each child, the new
estimates $\hat \theta_{C_1}$ and $\hat \theta_{C_2}$ will maximize
the following heterogeneity score:
$\Delta(C_1, C_2) = \sum_{j=1}^2 \frac{1}{|C_j|}\left(\hat
  \theta_{C_j} - \hat \theta_{P} \right)^2$.

However, performing the two-stage estimation of $\hat \theta_{C_1}$
and $\hat \theta_{C_2}$ for all possible splits is too computationally
expensive. Instead, we will approximate these estimates by taking a
Newton step from the parent node estimate $\hat \theta_P$. More
formally, let us write
$\lres(\theta, Z_i) = \frac{1}{2}\left( \langle \hat T_i ,
  \theta\rangle - \hat Y_i \right)^2$ to denote the residualized
square loss function. Then for each observation $Z_i$ that reaches the
node $P$, the gradient is:
\begin{equation}\label{grad}
  \nabla_\theta \lres(\hat \theta_P, Z_i) = (\hat Y_i - \hat \theta_P
  \hat T_i)\, \hat T_i
\end{equation}
The empirical Hessian over the observations in $P$ is:
\[
  A_P = \nabla_\theta^2 \left(\frac{\sum_{i\in P\cap S_b^1} \lres(\hat
      \theta_P, Z_i)}{|P\cap S_b^1|}\right) = - \frac{\sum_{i\in P\cap
      S_b^1}\hat T_i^2}{|P\cap S_b^1|}
\]
Then for any child node $C$ given by a candidate split, our proxy
estimate is then given by taking a Newton step with observations that
reach node $C$:
\[
  \tilde \theta_{C} = \hat \theta_P - \sum_{i\in C} A_P^{-1} (\hat Y_i
  - \hat \theta_P \hat T_i)\, \hat T_i
\]
Given the estimates $\tilde \theta_{C}$ for each possible child $C$,
we will select the split that maximizes the following proxy
heterogeneity score:\footnote{Our splitting criterion can be viewed as
  an instantiation of the one in \citet{ATW17} with a moment function
  defined by the gradient of the residualized square loss
  in~\Cref{grad}.}
\begin{equation}\label{splitting}
  \tilde \Delta(C_1, C_2) = \sum_{j=1}^2 \frac{1}{|C_j|} \left(\tilde
    \theta_{C_j} -\hat \theta_P \right)^2
\end{equation}

Finally, when building the tree, the learner also ensures that both
sets $S_b^2$ and $S_b^3$ contain at least one observations that fall
under the leaf containing the target feature $x$.

 \iffalse
\begin{itemize}
\item $\omega$-\emph{regularity} for $\omega\leq 0.2$: each split
  leaves at least a fraction $\omega$ of the observations in $S_b^2$ on each
  side of the split and, moreover, the trees are fully grown to depth
  $r$ for some $r \in \NN$, i.e., there are between $r$ and $2r - 1$
  observations in each leaf of the tree.
\item there is at least
\end{itemize}
\fi

\subsection{Local Estimation}
Given a set of $B$ trees returned by the tree learner $\cL_T$, we can
now identify a set of observations that are close to the target point
$x$. In order to reduce the confounding effects from $W$, we will
again perform a similar two-stage local estimation with double machine
learning. In particular, for each tree $b$, let $L_b(x)\subseteq \cW$
be the leaf of the tree containing the target feature $x$, and
$L_b^2(x)$ and $L_b^3(x)$ be the set of observations that lie in the
set $L_b(x)$ in the sets $S_b^2$ and $S_b^3$ respectively.

For each observation $i$ in the input data set, we can also compute
the weights as
\begin{align}\label{weight}
  w_{ib} = \frac{\mathbf{1}[Z_i\in L_b^2(W)]}{|L_b^2(x)|}\\
  a_{ib} = \frac{\mathbf{1}[Z_i\in L_b^3(W)]}{|L_b^3(x)|}
\end{align}
The importance weights provide a measure of how relevant each
observation for the following two-stage estimation. First, we will
solving the following weighted Lasso problem
\begin{align}
  \hat \gamma = \argmin_{\gamma} \frac{1}{2}\sum_{i=1}^n \sum_{b=1}^B w_{ib} \left(T_i - \langle W_i , \gamma\rangle  \right)^2 + \lambda_\gamma \|\gamma\|_1 \\
  \hat q = \argmin_{q} \frac{1}{2}\sum_{i=1}^n \sum_{b=1}^B w_{ib} \left(Y_i - \langle W_i , q \rangle  \right)^2 + \lambda_q \|\gamma\|_1
\end{align}

Then for each $b\in [B]$ and each observation
$Z_i= (T_i, Y_i, W_i, x_i)\in L_b^3(x)$, we compute the residuals
using Lasso estimates $\hat \gamma$ and $\hat q$:
\begin{equation}\label{rest}
  \hat Y_{i} = Y_i -\langle W, \hat q \rangle, \quad \hat T_{i} = T_i -\langle
  W_i, \hat \gamma \rangle
\end{equation}
Again, this is an important step to eliminate the confounder effects
during the second-stage estimation. In the second step, we compute the
following weighted residualized regression problem on the dataset:
\begin{equation}\label{ols}
  \hat \theta = \argmin \frac{1}{B} \sum_{i=1}^n \sum_{b=1}^B
  a_{ib} \left(\theta \hat T_{i} - \hat Y_{i} \right)^2
\end{equation}
\fi

\section{Omitted Proofs from \Cref{sec:kernel-lasso}}

\begin{proof}[Proof of \Cref{nuisance-main}]
  By convexity of the loss $\ell$ and the fact that $\hat{\nu}(x)$ is
  the minimizer of the weighted penalized loss, we have:
\begin{align*}
\lambda \left(\|\nu_0(x)\|_1 - \|\hat{\nu}(x)\|_1\right) \geq~&
\sum_{i=1}^n a_i(x)\, \ell(Z_i;\hat{\nu}(x)) - \sum_{i=1}^n a_i(x)\, \ell(Z_i;\nu_0(x)) \tag{optimality of $\hat{\nu}(x)$}\\
\geq~& \sum_{i=1}^n a_i(x)\ldot{\nabla_{\nu}\ell(z_i;\nu_0(x))}{\hat{\nu}(x) - \nu_0(x)} \tag{convexity of $\ell$}\\
 \geq~& - \left\|\sum_{i} a_i(x) \nabla_\nu \ell(z_i;\nu_0(x))\right\|_{\infty} \|\hat{\nu}(x) - \nu_0(x)\|_1 \tag{Cauchy-Schwarz} \\
 \geq~& - \frac{\lambda}{2}  \|\hat{\nu}(x) - \nu_0(x)\|_1 \tag{assumption on $\lambda$}
\end{align*}
If we let $\rho(x) = \hat{\nu}(x) - \nu_0(x)$, then observe that by the definition of the support $S$ of $\nu_0(x)$ and the triangle inequality, we have:
\begin{align*}
\|\nu_0(x)\|_1 - \|\hat{\nu}(x)\|_1 & = \|\nu_0(x)_S\|_1 + \|\nu_0(x)_{S^c}\|_1 - \|\hat\nu(x)_S\|_1 - \|\hat\nu(x)_{S^c}\|_1 \tag{separability of $\ell_1$ norm}\\
&= \|\nu_0(x)_S\|_1 - \|\hat\nu(x)_S\|_1 - \|\hat\nu(x)_{S^c}\|_1 \tag{definition of support}\\
&= \|\nu_0(x)_S\|_1 - \|\hat\nu(x)_S\|_1 - \|\hat\nu(x)_{S^c}-\nu_0(x)_{S^c}\|_1 \tag{definition of support}\\
&= \|\nu_0(x)_S - \hat{\nu}(x)_S\|_1 - \|\hat\nu(x)_{S^c}-\nu_0(x)_{S^c}\|_1 \tag{triangle inequality}\\
&\leq \|\rho(x)_S\|_1 - \|\rho(x)_{S^c}\|_1 \tag{definition of $\rho(x)$}

\end{align*}

Thus re-arranging the terms in the latter series of inequalities, we get that $\rho(x) \in C(S(x); 3)$.

We now show that the weighted empirical loss function satisfies a conditional restricted strong convexity property with constant $\hat{\gamma}=\gamma - k\sqrt{s\ln(d_\nu/\delta)/n}$ with probability $1-\delta$. This follows from observing that:
\begin{align*}
H = \nabla_{\nu\nu} \sum_{i=1}^n a_i(x)\, \ell(z_i;\nu) = \sum_{i=1}^n a_i \nabla_{\nu\nu}\ell(z_i; \nu)  \succeq \sum_{i=1}^n a_i \mcH(z_i) = \frac{1}{B} \sum_{b} \sum_{i\in b} a_{ib}(x) \mcH(z_i)
\end{align*}
Thus the Hessian is lower bounded by a matrix whose entries correspond to a Monte-Carlo approximation of the $U$-statistic:
\begin{equation}
U = \frac{1}{\binom{n}{s}}\sum_{S\subseteq [n]: |S|=s} \frac{1}{s!} \sum_{i\in S}\Ex{\omega}{ a_i(S, \omega) \mcH(z_i)}
\end{equation}
where $\Pi_s$ denotes the set of permutations of $s$ elements, $S_{\pi}$ denotes the permuted elements of $S$ according to $\pi$ and $S_{\pi}^1, S_{\pi}^2$ denotes the first and second half of the ordered elements of $S$ according to $\pi$. Finally, $a_i(S,\omega)$ denotes the tree weight assigned to point $i$ by a tree learner trained on $S$ under random seed $\omega$.

Hence, for sufficiently large $B$, by a $U$-statistic concentration inequality \cite{Hoeffding} and a union bound, each entry will concentrate around the expected value of the $U$ statistic to within $2\sqrt{s\ln(d_\nu/\delta)/n}$, i.e.: with probability $1-\delta$:
\begin{equation}
\left\|\frac{1}{B} \sum_{b} \sum_{i\in b} a_{ib}(x) \mcH(z_i) - \Ex{}{U}\right\|_{\infty} \leq 2\sqrt{\frac{s\ln(d_\nu/\delta)}{n}}
\end{equation}
Moreover, observe that by the tower law of expectation and by honesty of the ORF trees we can write:
\begin{equation}
\Ex{}{U} = \Ex{}{\frac{1}{\binom{n}{s}}\sum_{S\subseteq [n]: |S|=s} \frac{1}{s!} \sum_{i\in S} a_i(S, \omega) \Ex{}{\mcH(z_i)\mid x_i}}
\end{equation}
Since each $\Ex{}{\mcH(z_i)\mid x_i}$ satisfies the restricted eigenvalue condition with constant $\gamma$, we conclude that $\Ex{}{U}$ also satisfies the same condition as it is a convex combination of these conditional matrices. Thus for any vector $\rho\in C(S(x);3)$, we have w.p. $1-\delta$:
\begin{align*}
\rho^T H \rho \geq~& \rho^T  \left(\sum_{i=1}^n a_i(x) \mcH(z_i)\right) \rho \tag{lower bound on Hessian}\\
 \geq~&  \rho^T \Ex{}{U}\rho - 2\sqrt{\frac{s\ln(d_\nu/\delta)}{n}} \|\rho\|_1^2 \tag{$U$-statistic matrix concentration}\\
 \geq~& \gamma \|\rho\|_2^2 - 2\sqrt{\frac{s\ln(d_\nu/\delta)}{n}} \|\rho\|_1^2 \tag{restricted strong convexity of population}\\
 \geq~& \left(\gamma - 32k\sqrt{\frac{s\ln(d_\nu/\delta)}{n}}\right) \|\rho\|_2^2 \tag{$\rho\in C(S(x); 3)$ and sparsity, imply: $\|\rho\|_1\leq 4\sqrt{k} \|\rho\|_2$}
\end{align*}

Since $\rho(x)\in C(S(x);3)$ and since the weighted empirical loss satisfies a $\hat{\gamma}$ restricted strong convexity:
\begin{align*}
\sum_{i=1}^n a_i(x)\, \ell(z_i;\hat{\nu}(x)) - \sum_{i=1}^n a_i(x)\, \ell(z_i;\nu_0(x))
\geq~&  \sum_{i=1}^n a_i(x)  \ldot{\nabla_{\nu}\ell(z_i;\nu_0(x))}{\hat{\nu} - \nu_0(x)}
       + \hat{\gamma} \|\rho(x)\|_2^2\\
\geq~& -\frac{\lambda}{2} \|\rho(x)\|_1^2 + \hat{\gamma} \|\rho(x)\|_2^2 \tag{assumption on $\lambda$}
\end{align*}
Combining with the upper bound of $\lambda\left(\|\rho(x)_{S(x)}\|_1 - \|\rho(x)_{S(x)^c}\|_1\right)$ on the difference of the two weighted empirical losses via the chain of inequalities at the beginning of the proof, we get that:
\begin{align*}
\hat{\gamma} \|\rho(x)\|_2^2 \geq \frac{3\lambda}{2} \|\rho(x)_{S(x)}\|_1 - \frac{\lambda}{2}\|\rho(x)_{S(x)^c}\|_1 \leq  \frac{3\lambda}{2} \|\rho(x)_{S(x)}\|_1  \leq  \frac{3\lambda\sqrt{k}}{2} \|\rho(x)_{S(x)}\|_2 \leq \frac{3\lambda\sqrt{k}}{2} \|\rho(x)\|_2
\end{align*}
Dividing both sides by $\|\rho(x)\|_2$ and combining with the fact that $\|\rho(x)\|_1\leq 4\sqrt{k}\|\rho(x)\|_2$ yields the first part of the theorem.

\paragraph{Bounding the gradient.}
Let $\tau = 1/(2\alpha d)$. We first upper bound the expected value of
each entry of the gradient. By the shrinkage property of the ORF
weights:
\begin{align*}
\left|\sum_{i=1}^n \Ex{}{a_i(x)\nabla_{\nu_j}\ell(z_i;\nu_0(x)) \mid x_i}\right|  \leq~& \left|\Ex{}{\nabla_{\nu_j}\ell(z;\nu_0(x)) \mid x}\right| + \Ex{}{\sum_{i=1}^n a_i(x) \left|\Ex{}{\nabla_{\nu_j}\ell(z_i;\nu_0(x)) \mid x_i}- \Ex{}{\nabla_{\nu_j}\ell(z;\nu_0(x)) \mid x}\right|}\\
\leq~& \left|\nabla_{\nu_j} L(\nu_0(x); x)\right| + L\Ex{}{\sum_{i=1}^n a_i(x) \left\|x_i - x\right\|} \tag{Lipschitzness of $\nabla_{\nu}L(\nu; x)$}\\
\leq~& \left|\nabla_{\nu_j} L(\nu_0(x); x)\right| + L\,s^{-\tau} \tag{Kernel shrinkage}\\
\leq~& L\,s^{-\tau} \tag{First order optimality condition of $\nu_0(x)$}
\end{align*}
Moreover, since the quantity $\sum_{i} a_i(x) \nabla_{\nu_j} \ell(z_i;\nu_0(x))$ is also a Monte-Carlo approximation to an appropriately defined $U$-statistic (defined analogous to quantity $U$), for sufficiently large $B$, it will concentrate around its expectation to within $\sqrt{s \ln(1/\delta)/n}$, w.p. $1-\delta$. Since the absolute value of its expectation is at most $Ls^{-\tau}$, we get that the absolute value of each entry w.p. $1-\delta$ is at most $L s^{-\tau} + \sqrt{s \ln(1/\delta)/n}$. Thus with a union bound over the $p$ entries of the gradient, we get that uniformly, w.p. $1-\delta$ all entries have absolute values bounded within $L s^{-\tau} + \sqrt{s \ln(d_\nu/\delta)/n}$.
\end{proof}

\section{Omitted Proofs from Heterogeneous Treatment Effects
  Estimation}

We now verify the moment conditions for our CATE estimation satisfies
the required conditions in \Cref{tech-conditions}.

\subsection{Local Orthogonality}
Recall that for any observation $Z = (T, Y, W, X)$, any parameters
$\theta\in \RR^p$, nuisance estimate $\hat h$ parameterized by
functions $q, g$, we first consider the following \emph{residualized}
score function for PLR is defined as:
\begin{align}\label{eq:PLR}
  \psi(Z; \theta,  h(X, W)) = \left\{Y -  q(X, W) -  \langle \theta,\left(T - g(X, W)\right) \rangle \right\} (T - g(X, W)),
\end{align}
with
$h(X, W)= (q(X, W), g(X, W))$.

For discrete treatments, we also consider the following \emph{doubly
  robust} score function, with each coordinate indexed by treament $t$
defined as:
\begin{align}\label{eq:dr}
  \psi^t(Z;\theta, h(X, W)) = m^t(X, W) + \frac{\left(Y - m^t(X, W)\right) \mathbf{1}[T = t]}{g^t(X,
    W)} - m^0(X, W) - \frac{\left(Y - m^0(X, W)\right) \mathbf{1}[T = 0]}{g^0(X,
    W)} - \theta^t
\end{align}
where $h(X, W) = (m(X, W), g(X, W))$.

\begin{lemma}[Local orthogonality for residualized
  moments]\label{cond-orthog}
  The moment condition with respect to the score function $\psi$
  defined in \eqref{eq:PLR} satisfies conditional orthogonality.
\end{lemma}

\begin{proof}
  We establish local orthogonality via an even stronger
  \emph{conditional orthogonality}:
\begin{equation}
  \Ex{}{\nabla_{h} \psi(Z, \theta_0(x), h_0(X, W)) \mid W, x} = 0
\end{equation}

In the following, we will write $\nabla_h \psi$ to denote the gradient
of $\psi$ with respect to the nuisance argument. For any $W, x$, we
can write
\begin{align*}
  \Ex{}{\nabla_{h} \psi\left(Z; \theta_0(x), \left(q_0(x, W) ,  g_0(x, W)\right) \right) \mid W, x} = \Ex{}{\left( T - g_0(x, W), - Y +  q_0(x, W) + 2\theta_0(x)^\intercal \, (T - g_0(x, W)) \right) \mid W, x}
\end{align*}
Furthermore, we have
$\Ex{}{T - g_0(x, W) \mid W, x} = \Ex{}{\eta \mid W,
  x} = 0$ and
\begin{align*}
  \Ex{}{-Y + q_0(x, W) + 2 \theta_0(x)^\intercal\, (T - g_0(x, W))\mid W, x} &=\Ex{}{q_0(x, W)-Y  + 2\theta(x)^\intercal \eta\mid W, x} = 0
\end{align*}
where the last equality follows from that $\Ex{}{\eta \mid W, x} = 0$
and $\Ex{}{\langle W, q_0\rangle - Y\mid W, x} = 0$.
\end{proof}

\begin{lemma}[Local orthogonality for doubly robust
  moments]\label{cond-orthog}
  The moment condition with respect to the score function $\psi$
  defined in \eqref{eq:dr} satisfies conditional orthogonality.
\end{lemma}

\begin{proof}
  For every coordinate (or treatment) $t$, we have
  \begin{align*}
    &~~~\Ex{}{\nabla_{g} \psi^t\left(Z; \theta_0(x), \left(m_0(x, W) ,
      g_0(x, W)\right) \right) \mid W, x} \\
    &= \Ex{}{-\frac{(Y - m_0^t(X, W))\mathbf{1}[T=t]}{(g_0^t(x, W))^2} + \frac{(Y - m_0^0(X, W))\mathbf{1}[T=t]}{(g_0^0(x, W))^2}\mid W, x}\\
    &= \Ex{}{-\frac{(Y - m_0^t(X, W))}{(g_0^t(x, W))^2}\mid W, x, T = t} \Pr[T = t\mid W, x]\\
    &+\Ex{}{\frac{(Y - m_0^0(X, W))}{(g_0^0(x, W))^2}\mid W, x, T = 0} \Pr[T = 0\mid W, x] = 0
  \end{align*}
and
  \begin{align*}
    &~~~\Ex{}{\nabla_{m} \psi^t\left(Z; \theta_0(x), \left(m_0(x, W) ,
      g_0(x, W)\right) \right) \mid W, x} \\
    &= \Ex{}{\nabla_{m}\left(m_0^t(x, W) + \frac{\left(Y - m_0^t(x, W)\right) \mathbf{1}[T = t]}{g_0^t(x,
      W)} - m_0^0(x, W) -  \frac{\left(Y - m_0^0(x, W)\right) \mathbf{1}[T = 0]}{g_0^0(x,
      W)}  \right)\mid W, x} \\
    &= \Ex{}{\nabla_{m}\left(m_0^t(x, W) + \frac{\left( - m_0^t(x, W)\right) \mathbf{1}[T = t]}{g_0^t(x,
      W)} - m_0^0(x, W) -  \frac{\left( - m_0^0(x, W)\right) \mathbf{1}[T = 0]}{g_0^0(x,
      W)} \right)\mid W, x} \\
    &=\nabla_{m}\left( \Ex{}{m_0^t(x, W)  - m_0^t(x, W) - m_0^0(x, W) + m_0^0(x, W)\mid W, x}\right) = 0
  \end{align*}
This complets the proof.
\end{proof}

\subsection{Identifiability}

\begin{lemma}[Identifiability for residualized moments.]
  As long as $\mu(X, W)$ is independent of $\eta$ conditioned on $X$
  and the matrix $\Ex{}{\eta \eta^\intercal \mid X=x}$ is invertible
  for any $x$, the parameter $\theta(x)$ is the unique solution to
  $m(x; \theta, h) = 0$.
\end{lemma}

\begin{proof}
  The moment conditions $m(x; \theta, h) = 0$ can be written as
  \begin{align*}
    \Ex{}{\left\{Y - q_0(X, W) -  \theta^\intercal\left(T - g_0(X, W)\right)  \right\} (T - g_0
    (X, W)) \mid X = x} = 0  \end{align*}
The left hand side can re-written as
\begin{align*}
  \Ex{}{\left\{\ldot{\eta}{\mu_0(X, W)} + \eps - \ldot{\theta}{ \eta})
  \right\} \eta\mid X = x} &= \Ex{}{\left\{\ldot{\eta}{\mu_0(X, W)} -
                             \ldot{\theta}{\eta}) \right\} \eta\mid X = x}\\
                           &= \Ex{}{\ldot{\mu_0(X, W) -
                             \theta}{\eta}) \eta\mid X = x}\\
                           &= \Ex{}{\eta \eta^\intercal\mid X = x} \Ex{}{\mu_0(X, W) -
                             \theta\mid X = x}
\end{align*}
Since the conditional expected covariance matrix
$\Ex{}{\eta \eta^\intercal\mid X = x}$ is invertible, the expression
above equals to zero only if
$\Ex{}{\mu_0(X, W) - \theta \mid X = x} = 0$. This implies that
$\theta = \Ex{}{\mu_0(X, W)\mid X=x} = \theta_0(x)$.
\end{proof}

\begin{lemma}[Identifiability for doubly robust moments.]
  As long as $\mu(X, W)$ is independent of $\eta$ conditioned on $X$
  and the matrix $\Ex{}{\eta \eta^\intercal \mid X=x}$ is invertible
  for any $x$, the parameter $\theta(x)$ is the unique solution to
  $m(x; \theta, h) = 0$.
\end{lemma}

\begin{proof}
  For each coordinate $t$, the moment condition can be written as
\begin{align}\label{eq:dr}
\Ex{}{m_0^t(X, W) + \frac{\left(Y - m_0^t(X, W)\right) \mathbf{1}[T = t]}{g_0^t(X,
    W)} - m_0^0(X, W) - \frac{\left(Y - m_0^0(X, W)\right) \mathbf{1}[T = 0]}{g_0^0(X,
    W)} - \theta^t \mid X = x} = 0
\end{align}
Equivalently,
\begin{align*}\label{eq:dr}
  \Ex{}{m_0^t(X, W)  - m_0^0(X, W)  - \theta^t \mid X = x} = \Ex{W}{\Ex{}{- \frac{\left(Y - m_0^t(X, W)\right) \mathbf{1}[T = t]}{g_0^t(X,
  W)} + \frac{\left(Y - m_0^0(X, W)\right) \mathbf{1}[T = 0]}{g_0^0(X,
  W)}  \mid W, X = x}}
\end{align*}
The inner expectation of the right hand side can be written as:
\[
  \Ex{}{- \frac{\left(Y - m_0^t(X, W)\right) \mathbf{1}[T =
      t]}{g_0^t(X, W)} + \frac{\left(Y - m_0^0(X, W)\right)
      \mathbf{1}[T = 0]}{g_0^0(X, W)} \mid W, X = x} = 0
\]
This means the moment
condition is equivalent to
\[
  \Ex{}{m_0^t(X, W) - m_0^0(X, W) \mid X = x} = \theta^t.
\]
This completes the proof.
\end{proof}

\subsection{Smooth Signal}
Now we show that the moments $m(x;\theta, h)$ are $O(1)$-Lipschitz in
$x$ for any $\theta$ and $h$ under standard boundedness conditions on
the parameters.

First, we consider the residualized moment function is defined as
  \[
    \psi(Z; \theta, h(X, W)) = \left\{Y - q(X, W) - \theta^\intercal\left(T -
        g(X, W)\right) \right\} (T - g(X, W)),
  \]
  Then for any $\theta$ and $h$ given by functions $g$ and $q$,
  \[
    m(x; \theta, h) = \Ex{}{\left\{Y - q(x, W) - \theta^\intercal\left(T - g(x,
          W)\right) \right\} (T - g(x, W)) \mid X = x}
  \]

  \paragraph{Real-valued treatments} In the real-valued treatment
  case, each coordinate $j$ of $g$ is given by a high-dimensional
  linear function: $g^j(x, W) = \langle W, \gamma^j\rangle$, where
  $\gamma^j$ is a $k$-sparse vectors in $\mathbb{R}^{d_\nu}$
  with$\ell_1$ norm bounded by a constant, and $q(x, W)$ can be
  written as a $\langle q', \phi_2(W)\rangle$ with $q'$ is a
  $k^2$-sparse vector in $\mathbb{R}^{d_\nu^2}$ and $\phi_2(W)$
  denotes the degree-2 polynomial feature vector of $W$.
  \[
    m_j(x; \theta, h) = \Ex{}{\left\{Y - \langle q', \phi_2(W)\rangle
        - \theta_j\left(T - \langle \gamma^j, W\rangle\right) \right\}
      (T - g(x, W)) \mid X = x}
  \]
  Note that as long as we restrict the space $\Theta$ and $H$ to
  satisfy $\|\theta\| \leq O(1)$, $\|\gamma\|_1, \|q'\|_1 \leq 1$, we
  know each coordinate $m_j$ is smooth in $x$.

  \paragraph{Discrete treatments with residualized moments.} In the
  discrete treatment case, each coordinate $j$ of $g$ is of the form
  $g^j(x, W) = \cL(\langle W, \gamma^j\rangle)$, where
  $\cL(t) = 1/(1 + e^{-t})$ is the logistic function.  The estimate
  $q$ consists of several components. First, consider function $f$ of
  the form $f(x, W) = \langle W, \beta \rangle$ as an estimate for the
  outcome of the null treament. For each $t\in \{e_1, \ldots, e_p\}$,
  we also have an estimate $m^t(x, W)$ for the expected
  counter-factual outcome function $\mu^t(x) + f(x, W)$, which takes
  the form of $\langle b , W\rangle$. Then the estimate $q$ is defined
  as:
\begin{equation*}
  q(x, W) = \sum_{t=1}^p (m^t(x, W) - f(x, W)) g^t(x, W) + f(x, W).
\end{equation*}
With similar reasoning, as long as we restrict $\Theta$ and $H$ to
satisfy $|\theta| \leq O(1)$, $\|\gamma^j\|_1 \leq 1$ for all $j$, and
$\|\beta\|_1, \|b\|_1 \leq 1$, we know each coordinate $m_j$ is smooth
in $x$.

\paragraph{Discrete treatments with doubly robust moments.}

Redcall that for each coordinate $t$, the moment function with input
$\theta$ and nuisance parameters $m, g$ is defined as
\begin{align}\label{eq:dr}
  \Ex{}{m^t(x, W) + \frac{\left(Y - m^t(x, W)\right) \mathbf{1}[T = t]}{g^t(x,
  W)} - m^0(x, W) - \frac{\left(Y - m^0(x, W)\right) \mathbf{1}[T = 0]}{g^0(x,
  W)} - \theta^t \mid X = x}
\end{align}
where each $m^t(x, W)$ takes the form of $\langle b, W \rangle$ and
each $g^t(x, W) = \cL(\langle W, \gamma^t\rangle)$, with $\cL$
denoting the logistic function. Then as long as we restrict the
parameter space and $H$ to satisfy $\|\gamma^t\|_1$ for all $t$, then
we know that $|\langle \gamma^t , W\rangle| \leq O(1)$ and so
$g^t(x, W)\geq \Omega(1)$. Furthermore, if we restrict the vector $b$
to satisfy $\|b\|_1 \leq 1$, we know each coordinate $m_j$ is smooth
in $x$.

\subsection{Curvature}
Now we show that the jacobian $\nabla_\theta m(x;\theta_0(x), h_0)$
has minimum eigenvalues bounded away from 0.

\paragraph{Residualized moments.}
First, we consider the residualized moment function is defined as
  \[
    \psi(Z; \theta, h(X, W)) = \left\{Y - q(X, W) - \theta^\intercal\left(T -
        g(X, W)\right) \right\} (T - g(X, W)),
  \]
  Then for any $\theta$ and $h$ given by functions $g$ and $q$,
  \[
    m(x; \theta, h) = \Ex{}{\left\{Y - q(x, W) - \theta^\intercal\left(T - g(x,
          W)\right) \right\} (T - g(x, W)) \mid X = x}
  \]

  Let $J$ be the expected Jacobian
  $\nabla_\theta m(x; \theta_0(x), h_0)$, and we can write
  $$J_{jj'}= \Ex{}{(T_j - g_0^j(x, W))(T_{j'} - g_0^{j'}(x, W))\mid
    X=x}$$ Then for any $v\in \mathbb{R}^p$ with unit $\ell_2$ norm,
  we have
  \begin{align*}
    v J v^\intercal& = \Ex{}{\sum_j (T_j- g_0^j(x, W))^2 v_j^2 + 2\sum_{j, j'}(T_j - g_0^j(x, W))(T_{j'} - g_0^{j'}(x, W)) v_j v_{j'} \mid X=x}\\
                   &= \Ex{}{\left(\sum_j (T_j - g_0^j(x, W)) v_j \right)^2\mid X=x}\\
                   &=  \Ex{}{v^\intercal (\eta \eta^\intercal) v\mid X=x}

  \end{align*}
  Then as long as the conditional expected covariance matrix
  $\Ex{}{ \eta \eta^\intercal \mid X=x}$ has minimum eigenvalue
  bounded away from zero, we will also have $\min_{v} v J v^\intercal$
  bounded away from zero.

\paragraph{Discrete treatments with doubly robust moments.}

Redcall that for each coordinate $t$, the moment function with input
$\theta$ and nuisance parameters $m, g$ is defined as
\begin{align}\label{eq:dr}
  \Ex{}{m^t(x, W) + \frac{\left(Y - m^t(x, W)\right) \mathbf{1}[T = t]}{g^t(x,
  W)} - m^0(x, W) - \frac{\left(Y - m^0(x, W)\right) \mathbf{1}[T = 0]}{g^0(x,
  W)} - \theta^t \mid X = x}
\end{align}
Then $\nabla_\theta m(x; \theta_0(x), h_0) = - I$, which implies the
minimum eigevalue is 1.

\subsection{Smoothness of scores}

\paragraph{Residualized moments.}
First, we consider the residualized moment function with each
coordinate defined as
  \[
    \psi_j(Z; \theta, h(X, W)) = \left\{Y - q(X, W) -
      \theta^\intercal\left(T - g(X, W)\right) \right\} (T_j - g_j(X,
    W)),
  \]
  Observe that for both real-valued and discrete treatments, the
  scales of $\theta$, $q(X, W)$, and $g(X, W)$ are bounded by
  $O(1)$. Thus, the smoothness condition immediately follows.

\paragraph{Doubly robust moments.}
For every treatment $t$,
\[
  \psi_t(Z; \theta, h(X, W)) = {m^t(X, W) + \frac{\left(Y - m^t(X,
        W)\right) \mathbf{1}[T = t]}{g^t(X, W)} - m^0(X, W) -
    \frac{\left(Y - m^0(X, W)\right) \mathbf{1}[T = 0]}{g^0(X, W)} -
    \theta^t}
\]
Recall that each $m^t(x, W)$ takes the form of $\langle b, W \rangle$
and each $g^t(x, W) = \cL(\langle W, \gamma^t\rangle)$, with $\cL$
denoting the logistic function.  Then as long as we restrict the
parameter space and $H$ to satisfy $\|\gamma^t\|_1$ for all $t$, then
we know that $|\langle \gamma^t , W\rangle| \leq O(1)$ and so
$g^t(X, W)\geq \Omega(1)$. Furthermore, if we restrict the vector $b$ to
satisfy $\|b\|_1 \leq 1$, we know each $m_j(X, W)\leq
O(1)$. Therefore, the smoothness condition also holds.

\subsection{Accuracy for discrete treatments}

For both score functions, we require that each discrete treatment
(including the null treatment) is assigned with constant probability.

\begin{corollary}[Accuracy for residualized scores]
  Suppose that $\beta_0(X)$ and each coorindate
  $\beta_0(X), \gamma_0^j(X)$ and $\theta(X)$ are Lipschitz in $X$
  and have $\ell_1$ norms bounded by $O(1)$ for any $X$. Assume that
  distribution of $X$ admits a density that is bounded away from zero
  and infinity.  For any feature $X$, the conditional covariance
  matrices satisfy
  $\Ex{}{\eta \eta^\intercal \mid X}\succeq \Omega(1) $,
  $\Ex{}{W W^\intercal \mid X} \succeq \Omega(1)I_{d_\nu}$. Then with
  probability $1 - \delta$, ORF returns an estimator $\hat \theta$
  such that
  \[
    \|\hat \theta - \theta_0\| \leq O\left(n^{\frac{-1}{2 + 2\alpha d}}\sqrt{\log(n d_{\nu}/\delta)} \right)
  \]
  as long as the sparsity
  $k \leq O\left(n^{\frac{1}{4 + 4\alpha d}} \right)$ and the
  subsampling rate of ORF $s = \Theta(n^{\alpha d/(1 + \alpha d)})$.
  Moreover, for any $b \in \RR^p$ with $\|b\|\leq 1$, there exists a
  sequence $\sigma_n = \Theta(\sqrt{\polylog(n) n^{-1/(1+\alpha d)}})$
  such that
  \[
    \sigma_n^{-1} \ldot{b}{\hat\theta -\theta} \rightarrow_d \mathcal{N}(0, 1),
  \]
  as long as the sparsity
  $k=o\left(n^{\frac{1}{4 + 4\alpha d}} \right)$ and the subsampling
  rate of ORF $s = \Theta(n^{\epsilon + \alpha d/(1 + \alpha d)})$ for
  any $\epsilon>0$.
\end{corollary}

\begin{corollary}[Accuracy for doubly robust scores]
  Suppose that $\beta_0(X)$ and each coorindate
  $u_0^j(X), \gamma_0^j(X)$ are Lipschitz in $X$ and have $\ell_1$
  norms bounded by $O(1)$ for any $X$. Assume that distribution of $X$
  admits a density that is bounded away from zero and infinity.  For
  any feature $X$, the conditional covariance matrices satisfy
  $\Ex{}{\eta \eta^\intercal \mid X}\succeq \Omega(1) $,
  $\Ex{}{W W^\intercal \mid X} \succeq \Omega(1)I_{d_\nu}$. Then with
  probability $1 - \delta$, ORF returns an estimator $\hat \theta$
  such that
  \[
    \|\hat \theta - \theta_0\| \leq O\left(n^{\frac{-1}{2 + 2\alpha d}}\sqrt{\log(n d_{\nu}/\delta)} \right)
  \]
  as long as the sparsity
  $k \leq O\left(n^{\frac{1}{4 + 4\alpha d}} \right)$ and the
  subsampling rate of ORF $s = \Theta(n^{\alpha d/(1 + \alpha d)})$.
  Moreover, for any $b \in \RR^p$ with $\|b\|\leq 1$, there exists a
  sequence $\sigma_n = \Theta(\sqrt{\polylog(n) n^{-1/(1+\alpha d)}})$
  such that
  \[
    \sigma_n^{-1} \ldot{b}{\hat\theta -\theta} \rightarrow_d \mathcal{N}(0, 1),
  \]
  as long as the sparsity
  $k=o\left(n^{\frac{1}{4 + 4\alpha d}} \right)$ and the subsampling
  rate of ORF $s = \Theta(n^{\epsilon + \alpha d/(1 + \alpha d)})$ for
  any $\epsilon>0$.
\end{corollary}

\iffalse The next lemma allows us to bound the maximum scale of the
PLR score function.

\begin{lemma}\label{lem:psimax}
  Suppose that the nuisance parameters satisfy
  $\max\{\|\hat q -q_0(x) \|_1\leq L_q \|\hat \gamma - \gamma_0\|_1\}
  \leq L_\gamma$. Then for any $\theta\in [-1, 1]$ any observation
  $Z_i= (T_i, Y_i, W_i, x_i)$,
  $\psi(Z_i; \theta, \hat h) \leq O\left((k + L_q+
    L_\gamma)L_\gamma\right)$.
\end{lemma}

\begin{proof}
  By H\"{o}lder inequality and the boundedness assumption that
  $\|q_0(x)\|_1 \leq O(k)$, $|Y_i|, |T_i| \leq O(k)$ for any
  observation $i$, we have:
  \[
    | Y_i - \langle \hat q , W_i\rangle| \leq O(k + L_q),\qquad | T_i
    - \langle \hat \gamma, W_i \rangle| \leq O(L_\gamma).
  \]
  It follows that for any $\theta\in [-1, 1]$,
  \[
    \psi(Z_i; \theta, \hat h) \leq \{O(k+L_q) +T_i - \langle \hat
    \gamma, W_i\rangle \}(T_i - \langle \hat \gamma, W_i\rangle)\leq
    O\left((k + L_q+ L_\gamma)L_\gamma\right),
  \]
  which recovers the stated bound.
\end{proof}

\begin{claim}\label{noisebound}
  Under \Cref{plrass}, consider any $W\in \RR^p$ and $x' \in \RR^d$
  such that $\|x' - x\|_2\leq \tau$, then
\begin{align*}
  \left|\Delta \gamma(x, x', W) \right| &\leq O( \tau \|W\|_\infty)\\
  \left|\Delta q(x, x', W) \right| &\leq O( \tau k \|W\|_\infty)
\end{align*}
\end{claim}

\subsection{Background for Lasso}

Let $w\in \RR^p$ be a $k$-sparse vector. Let
$W_1, \ldots , W_m\in\RR^p$ be a set of covariates that are drawn from
distribution $\cN(0, \sigma^2 \mathbf{I}_p)$.

We will write $\mathbf{W}$ to denote the design matrix with each rows
$\{W_i\}_{i=1}^m$. We say that the matrix $\bW$ satisfies the
\emph{restricted eigenvalue (RE)} condition with parameters
$(\alpha, \gamma)$ if
\[
  \frac{\frac{1}{m} \nu \bW^\intercal \bW \nu}{\|\nu\|_2^2} \geq
  \gamma \mbox{ for all non-zero } \nu\in C(S; \alpha)
\]
where
$C(S; \alpha) = \{\nu\in \RR^p \mid \|\nu_{S^c}\|_1 \leq \alpha
\|\nu_S\|_1\}$ and $S$ is the support of $w$.

\begin{lemma}[Follows from Corollary 1 of~\citet{RE-condition}]
  Fix a sample size $m$. Suppose that each covariates $W_i$ is drawn
  independently from $\cN(0, \sigma^2 \mathbf{I}_p)$. Then for
  universal positive constants $c, c', c''$, if
  \[
    m > c''k\log p
  \]
  then the design matrix $W$ satisfies the RE condition with
  parameters $(3, \sigma^2/8)$ with probability at least
  $1 - c'\exp(-cn)$.
\end{lemma}

Let $y_1, \ldots , y_n$ be responses such that for each $i$,
\[
  y_i = \langle W_i, w \rangle + \xi_i.
\]
where $\xi_i$ denotes the noise. Now consider the Lasso solution given
by:
\[
  \hat w = \argmin_{w'} \frac{1}{2m} \sum_{i=1}^m (y_i - \langle w' ,
  W_i\rangle)^2 + \lambda_m \|w'\|_1
\]

The following standard result allows us to bound the error rate of
$\|\hat w - w\|_2$.

\begin{theorem}[See e.g.~\cite{Lasso-Book}]
  Suppose that the design matrix $\bW$ satisfies the RE condition with
  parameters $(3, \gamma)$. Then given any regularization parameter
  $\lambda_m \geq 2\|\bW^\intercal \xi\|_\infty/m$, the estimate
  $\hat w$ satisfies the following bound:
\[
  \|\hat w - w\|_2 \leq \frac{3}{\gamma} \sqrt{k} \lambda_m.
\]
\end{theorem}

\begin{lemma}[Concentration on sub-Gaussian r.v.]
  Let $W$ be a sub-Gaussian random variable with parameter
  $\sigma$. Suppose that $\Ex{}{W} = \mu$, then
\[
  \Pr[| W - \mu | \geq t]  \leq 2 \exp(-t^2/(2\sigma^2))
\]
\end{lemma}

\begin{corollary}[Bounds on the noise variables]
  Let $W_1, \ldots, W_m$ be $m$ independent 1-sub-Gaussian random
  variables such that for each $i\in [m]$, $\Ex{}{W_i} =0$. Then with
  probability $1 - \delta$,
\[
  \max_i |W_i| \leq \sqrt{2\log(2m/\delta)}.
\]
\end{corollary}

\begin{proof}[Proof of \Cref{noisebound}]
  Consider any $W\in \RR^p$ and $x' \in \RR^d$ such that
  $\|x' - x\|_2\leq \tau$, then First, we obtain the following bound
  with a simple application of Holder inequality:
\begin{align*}
  \left|\langle W, \gamma_0(x) \rangle - \langle W, \gamma_0(x')
    \rangle \right|
& \leq \|W\|_\infty \|\gamma_0(x) - \gamma_0(x')
  \|_1 \\
&\leq O(\tau \|W\|_\infty)
\end{align*}

Similarly, we also have
\[
  \left|\langle W, \gamma_0(x) \rangle - \langle W, \gamma_0(x')
    \rangle \right| \leq O(\tau \|W\|_\infty)
\]
Moreover,
\begin{align*}
  &~~\left| \theta(x) \langle W , \gamma_0(x) \rangle -   \theta(x') \langle W , \gamma_0(x') \rangle \right|\\
  &  =  \left|\theta(x) \langle W, \gamma_0(x) \rangle - \theta(x) \langle W, \gamma_0(x')\rangle +  \theta(x) \langle W, \gamma(x') \rangle - \theta(x') \langle W, \gamma(x')\rangle\right|\\
  &  \leq  \left|\theta(x) \langle W, \gamma_0(x) \rangle - \theta(x) \langle W, \gamma_0(x')\rangle\right| +\left| \theta(x) \langle W, \gamma(x') \rangle - \theta(x') \langle W, \gamma(x')\rangle\right| \tag{Triangle inequality}\\
  &\leq  |  \theta(x)\langle W, \gamma_0(x) - \gamma_0(x')\rangle|
    + \left| \theta(x) - \theta(x') \right|\left|  \langle W, \gamma(x') \rangle\right| \\
  &\leq O\left( \|W\|_\infty \|\gamma_0(x) -\gamma_0(x')\|_1 \right)  + O\left(\tau \|W\|_\infty \|\gamma_0(x')\|_1\right)
    \tag{Holder inequality}\\
  &\leq O\left(\tau \|W\|_\infty k \right)
\end{align*}
Then our stated bound regarding $q_0$ follows directly from triangle
inequality.
\end{proof}

\section{Setting Minimum Leaf Size $r$}
Recall that our main convergence analysis uses the general convergence
result of GMM estimation (\Cref{thm:converge}), so it does not
optimize the dependence on the minimum leaf size $r$. We now give a
heuristic on how one can optimize the dependence on $r$, which is
useful for choosing this parameter in the experiments when the
features $x$ are higher-dimensional.

Recall that in the final bound of \Cref{thm:converge}, there are two
terms. The first term comes from the kernel error, which is upper
bounded the kernel shrinkage $O(s^{-\tau})$. We can replace
$s^{-\tau}$ by a more refined bound
$d\left(\frac{s}{2r - 1}\right)^{\frac{-1}{2\alpha d}}$ as given in
\Cref{detailed-shrinkage}. The second term comes from the sampling
error $|\Psi(\theta, \hat h) - \mu(\theta)|$, which can be bounded by
$O(k\sqrt{s\ln(1/\delta)/n})$ using the first-order tail bound for
$U$-statistic. We can in fact obtain a second-order error bound by
using the Bernstein inequality~\citep{bernstein}:
\[
  |\Psi(\theta, \hat h) - \mu(\theta)| \leq O\left( \sqrt{\frac{
        V^2}{(n/s)}\ln(1/\delta)} +
    \frac{k}{(n/s)}\ln(1/\delta)\right)
\]
where $V$ denotes the variance of the following random variable
$$
\Psi' = \sum_{i=1}^s a_{ib} \psi(Z_i; \theta, \hat h(W_i))
$$
where $\{Z_i\}_{i=1}^s$ is a set of i.i.d. observations, and each
$a_{ib}$ is the tree weight assigned by the tree learner that
partitions the input data as
$S^1_b= \{Z_1, \ldots , Z_{\lfloor s/2\rfloor}\}$ and
$S^2_b= \{Z_{\lfloor s/2 \rfloor + 1}, \ldots , Z_{s}\}$. We can
further rewrite the expression
\[
  \Psi' = \sum_{Z_i \in L_b^2(x)} \frac{1}{|L_b^2(x)|} \psi(Z_i;
  \theta, \hat h(W_i))
\]
where $L_b^2(x)$ denotes the subset of observations in $S_b^2$ that
fall into the same leaf as $x$. Note that for any observation in
$S_b^2$, the terms $\psi(Z_i; \theta, \hat h(W_i))$ are independent
conditioned on the realization of $x_i$'s and $S_b^1$. Thus, the
random variable $\Psi'$ conditioned on the realization of $x_i$'s and
$S_b^1$ can be viewed as a sum of $|L_b^2(x)|$ independent random
variables. By law of total variance we can write
\begin{align*}
  V &= \Ex{}{\text{Var}(\Psi' \mid x_1, \ldots, x_s, S_b^1)} +
      \text{Var}\left(\Ex{}{\Psi' \mid x_1, \ldots, x_s, S_b^1}\right)\\
    &\leq
      O(k^2/r) +   \text{Var}\left(\Ex{}{\Psi' \mid x_1, \ldots, x_s, S_b^1}\right)
\end{align*}
where the last inequality follows from the fact that
$r\leq |L_b^2(x)|\leq 2r$. Note that as $\theta$ converges to the
target value $\theta_0$, and the $\hat h$ converges the target
nuisance parameter $h_0$, the conditional expectation
$\Ex{}{\Psi' \mid x_1, \ldots, x_s, S_b^1}$ is tending to 0, so its
variance has lower order than $k^2/r$. Therefore, it suffices to
choose $r$ to optimize the sum of the dominating terms from the kernel
error and the sampling error:
\[
  \frac{k^2}{r} \sqrt{\frac{s\ln(1/\delta)}{n}} + d \left(\frac{s}{2r
      - 1} \right)^{\frac{-1}{2\alpha d}}
\]
If subsample size
$s = \left(\frac{n}{k^2\ln(p)} \right)^{\frac{1}{2\tau + 1}}$, then we
can set $r = \frac{k}{d}^{2/{2+ 2\tau}}$ to balance the two sources of
error.
\fi


TITLE: Is $G$ an Abelian group?
QUESTION [1 upvotes]: Denote by $f_{a,b}$ the map from $\mathbb R$ to $\mathbb R$ such that $f(x)=ax+b$ for all $x \in \mathbb R$, where $a,b \in \mathbb R$ with $a\neq0$.
Let $G=\{f_{a,b}|a,b\in \mathbb R,a \neq0\}$. So I have already shown that $f_{a,b}$ is a bijection for any $a,b \in \mathbb R $ with $a\neq 0$ and prove that it is a subgroup of the group Sym$_{\mathbb R}$ for all bijective maps from $\mathbb R$ to $\mathbb R$.

Now I want to find if $G$ is an abelian group or not.
  I am aware abelian is the same as commutative, i.e., $ab=ba$.

However I am confused as to how I would apply this to my group. This is a group under composition, or at least that's was I was required to use to show it is a subgroup.
I assume the same still stands to show whether or not it is commutative. In any case I have tried two methods, both of which could be wrong.
I tried to show:
$$(ax+b)(a'x'+b')=(a'x'+b')(ax+b),$$
but under composition it would be trying to show:
$$(a'(ax+b)+b')=(a(a'x'+b')+b).$$
But they both don't seem right to me, in any case I'm not really sure what the right direction is. Any help/hints would be very appreciated.

REPLY [3 votes]: A group $G$ is abelian iff $gh = hg$ for all $g,h \in G$. Now, what are elements in your group? They are functions. So let us take two of them $g = f_{a,b}$ and $h = f_{c,d}$. Now calculate $gh$ and $hg$:
$$ gh(x) = g(cx + d) = a(cx + d) + b = acx + ad + b $$
$$ hg(x) = h(ax + b) = c(ax + b) + d = cax + cb + d $$
Now two functions are equal iff their value is same on every $x$. Now can you say whether $gh = hg$?

REPLY [1 votes]: Is $\;f_{a,b}\circ f_{c,d}=f_{c,d}\circ f_{a,b}\;$ ? Meaning:
$$a(cx+d)+b\stackrel?=c(ax+b)+d\iff acx+ad+b\stackrel?=acx +bc+d$$
Now you produce a counterexample to deduce $\;G\;$ is non-abelian.

REPLY [1 votes]: It is about the second equation you posted (i.e. composition). But there is only one $x$ (no $x'$). Multuiplying it out then gives $$a'ax+a'b+b'=aa'x+ab'+b$$ which is not true in general. So no, the group is not abelian.

REPLY [1 votes]: You have to take 2 elements in $G$, say, $g$=$f_{a,b} $ and $g'$=$f_{a',b'}$, now check the composition:
$g○g'(x)= f_{a,b} (a'x+b') = aa'x+ab'+b$
$g'○g (x)= f_{a',b'} (ax+b) =a'ax+a'b+b'$
From here is easy to construct a counterexample and show it is not abelian.