text:
\section{Monte-Carlo Simulations}
\label{sec:montecarlo}
\subsection{Monte-Carlo Simulations for Section \ref{sec:selection}}
We performed a monte-carlo analysis of the performance our approach. We considered a special case of the model given in the previous paragraph, with data-generating process:
\begin{align*}
y ~=~& x' h(u) + \epsilon,\\
h(u) ~=~& \theta + A_1 u + A_2 \left(u^2 - \E\left[u^2\right]\right)\\
\Pr(d=1 | x, u) ~=~& \mcL(\sigma_\eta (x'\beta + u'\gamma))\\
x \sim U(-\sigma_x,\sigma_x)^p,~& u\sim U(-\sigma_u, \sigma_u)^d,~ \epsilon \sim N(0, \sigma_\epsilon)
\end{align*}
Such a setting captures the case where $z=(x,u)$, $x$ is a treatment vector and the component $u$ creates treatment effect heterogeneity in a polynomial form. Our goal is to estimate the average treatment effect $\theta$ of $x$, averaging out the effect of $u$. The fact that $d$ is correlated with $u$, does not allow us to simply run a regression between $y$ and $x$ on the non-missing data. We considered the case where $k_\theta$ entries of $\theta$ are non-zero wlog we assumed that these are the first $k_\theta$ coefficients of $\theta$. Moreover, the matrices $A_1$ and $A_2$ are also sparse, in the sense that only the rows that correspond to the support of $\theta$ are non-zero and among the columns only $k_u$ of the entries are non-zero (i.e. only $k_u$ of the variables $u$ have an effect). The non-zero coefficients of $A_1$ and $A_2$ where drawn independently from $U(1, 2)$. The coefficients $\beta$ where drawn independently from $U(0, 1)$ and the coefficients $\gamma$ independently from $U(2,3)$. The non-zero coefficients of $\theta_0$ where equal to $2$.

\begin{figure}[tpb]
\centering
    \includegraphics[scale=.7]{l2_errors_missing.png}
    \caption{\footnotesize{\emph{Missing Data.} Distribution of $\ell_2$ errors of estimate $\hat{\theta}$ from each method, i.e. $\|\hat{\theta}_{\text{method}} - \theta_0\|_2$, across $1000$ experiments. Parameters: $n=5000$, $p=20$, $d=20$, $k_\theta=1$, $k_u=1$, $\theta_0=(2, 0, \ldots, 0)$, $\sigma_\eta=0.1$, $\sigma_x=\sigma_u=3$, $\sigma_\epsilon=1$, $\lambda=\sqrt{\log(p)/n}$.}}
    \label{fig:missing-1}
\end{figure}

The results of $1000$ experiments are depicted in Figures \ref{fig:missing-1} and \ref{fig:missing-2}. We compared three main approaches: i) the direct approach (Direct), where we simply run a lasso regression of $y$ on $x, x*u$ (where $x*u$ denotes all pairwise product terms) using only the non-missing data, ii) the non-orthogonal inverse propensity approach (IPS) where we use the non-orthogonal moment $M$ and we estimate the propensity in a cross-fitting manner, iii) the orthogonal approach (Ortho) based on moment $\Phi$, where we estimate the propensity and function $q_0(z)$ in a cross-fitting manner. The propensity was estimated with a logistic lasso, where the regularization weight was chosen with cross-validation. The function $q_0$ was estimated by running a Random Forest regression between $y$ and $x, u$ and then subtracting a term $x'\tilde{\theta}$, where $\tilde{\theta}$ is a preliminary estimate of $\theta$ computed via the non-orthogonal IPS algorithm. For the second stage estimation in both IPS and Ortho we performed $\ell_1$ penalized estimation with $\lambda=\sqrt{\log(p)/n}$. For the direct method we selected the regularization weight $\lambda$ of the Lasso via cross validation. Apart from these three main methods, we also evaluated the performance of \emph{oracle} versions of both the IPS and the Ortho method, where the nuisance functions $p_0$ and $q_0$ are not estimated but rather the true ones are given by an oracle. These are infeasible methods, evaluated primarily so as to examine the effect of using plugin estimates of these functions as opposed to oracle versions of them. Interestingly, we observe that the orthogonal approach achieves very similar performance to its oracle version, unlike the IPS approach.

\begin{figure}[htpb]
    \centering
    \includegraphics[scale=0.7]{l2_decrease_missing.png}
    \caption{\footnotesize{\emph{Missing Data.} Distribution of decrease in $\ell_2$ errors of estimate $\hat{\theta}$ between each method and the proposed Ortho method, i.e. $\|\hat{\theta}_{\text{method}}-\theta_0\|_2 - \|\hat{\theta}_{\text{Ortho}} - \theta_0\|_2$, across $1000$ experiments. We observe that the proposed method leads to a statistically significant positive decrease in error, as compared to each other method (except its oracle version) and even outperforms the oracle version of the IPS approach. Moreover, its performance compared to its oracle version is statistically identical. Parameters: $n=5000$, $p=20$, $d=20$, $k_\theta=1$, $k_u=1$, $\theta_0=(2, 0, \ldots, 0)$, $\sigma_\eta=0.1$, $\sigma_x=\sigma_u=3$, $\sigma_\epsilon=1$, $\lambda=\sqrt{\log(p)/n}$.}}
    \label{fig:missing-2}
\end{figure}

\begin{figure}[htpb]
    \centering
    \begin{subfigure}[t]{.9\textwidth}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{dmr_kz_1_se_1_dx_sx.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{ipmr_kz_1_se_1_dx_sx.png}
    \end{subfigure}
    \subcaption{Varying $(p, \sigma_x)$}
    \end{subfigure}
    \begin{subfigure}[t]{0.9\textwidth}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{dmr_kz_1_sx_3_dx_se.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{ipmr_kz_1_sx_3_dx_se.png}
    \end{subfigure}
    \subcaption{Varying $(p, \sigma_\epsilon)$}
    \end{subfigure}
    \caption{\footnotesize{\emph{Missing Data.} Median percentage decrease in $\ell_2$ error between (Direct, IPS) and Ortho, i.e. $100\times \frac{\text{error}_{\text{Method}} - \text{error}_{\text{Ortho}}}{\text{error}_{\text{Method}}}$ across $100$ experiments as two parameters of the DGP vary. When a parameter is not shown then the following default values are assumed: $n=5000$, $p=20$, $d=20$, $k_\theta=1$, $k_u=1$, $\theta_0=(2, 0, \ldots, 0)$, $\sigma_\eta=0.1$, $\sigma_x=\sigma_u=3$, $\sigma_\epsilon=1$, $\lambda=\sqrt{\log(p)/n}$.}}
    \label{fig:missing-3}
\end{figure}

\subsection{Monte-Carlo Simulations for Section~\ref{sec:strategic}}
We performed a monte-carlo analysis of the performance our orthogonal estimation approach. We considered a special case of the model, where the errors follow a gambit distribution and hence the probability of entry takes a logistic linear form:
\begin{align*}
\Pr[y_i=1 | x] ~=~& \mcL\left(x' \alpha_0^i + g_0^{-i}(x)\Delta_0^i\right),\\
x \sim U(-\sigma_x,\sigma_x)^p
\end{align*}
where $g_0^i:[-\sigma_x, \sigma_x]^p \rightarrow [0,1]$ is the equilibrium mapping of the game of incomplete information. We considered two data generating processes (DGPs): i) a stylized dgp (DGP1) where $\Delta_0^2=0$ and therefore the estimation of $g_0^2$ boils down to a logistic lasso, while the estimation of $\alpha_0^1, \Delta_0^1$ depends on the estimate $g_0^2$, ii) an equilibrium based dgp (DGP2) where we computed the fixed point $g_0$ of the equilibrium equations and then generated entry decisions from the logistic function. In this setting estimating $g_0^2$ is non-trivial as the dependence on $x$ might not follow a logistic-linear form. We denote with $k_i = \|\alpha_0^i\|$, the sparsity of the coefficient associated with each player.

\begin{figure}[tpb]
    \centering
    \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_error_one_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_decrease_one_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_error_one_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_decrease_one_player.png}
    \end{subfigure}
    \caption{\footnotesize{\emph{Games.} Distribution of $\ell_1$ and $\ell_2$ errors and error decreases of estimate $\hat{\theta}$ from each method, i.e. $\|\hat{\theta}_{\text{method}} - \theta_0\|_2$, across $100$ experiments based on the games setting DGP1. Parameters: $n=10000$, $p=1000$, $k_1=1$, $k_2=3$, $\alpha_0^1=(1, 0, \ldots, 0)$, $\alpha_0^2=(u_1, u_2, u_3, 0, \ldots, 0)$, with $u_i\sim U(-2, 2)$, $\Delta_0^1=-2$, $\Delta_0^2=0$, $\sigma_x=1$, $\lambda=\sqrt{\log(p)/4n}$.}}
    \label{fig:games-1}
\end{figure}

We evaluated the performance of several approaches for estimating the parameters of player $1$, i.e. $\theta_0=(\alpha_0^1, \Delta_0^1)$. The results of $100$ experiments are depicted in Figures \ref{fig:games-1}, \ref{fig:games-2} and \ref{fig:games-3}. We compared three main approaches: i) an \emph{infeasible} oracle logistic (OracleLG) approach, where we used the true entry probability of player $2$, $g_0^2$ and then run a logistic lasso for estimating $\theta_0$, ii) a non-orthogonal two-stage logistic lasso (2SLG), where we estimated $g_0^2$ in the first stage using a logistic lasso (potentially mis-specified model in DGP2) in a cross-fitting manner and then run a second stage logistic lasso for estimating $\theta_0$, iii) an orthogonal two stage approach (2SOrthoLG), where in the first stage we estimated $g_0^2$ and a preliminary $\tilde{\theta}_0$, via a logistic lasso, in a cross-fitting manner, so as to compute the orthogonal correction term and in the second stage we run an orthogonal loss minimization. We observe that 2SOrthoLG consistently outperforms 2SLG and is at par with the infeasible OracleLG.

\begin{figure}[tpb]
    \centering
    \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_error_two_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_decrease_two_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_error_two_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_decrease_two_player.png}
    \end{subfigure}
    \caption{\footnotesize{\emph{Games.} Distribution of $\ell_1$ and $\ell_2$ errors and error decreases of estimate $\hat{\theta}$ from each method, i.e. $\|\hat{\theta}_{\text{method}} - \theta_0\|_2$, across $100$ experiments based on the games setting DGP2. Parameters: $n=10000$, $p=1000$, $k_1=1$, $k_2=3$, $\alpha_0^1=(1, 0, \ldots, 0)$, $\alpha_0^2=(u_1, u_2, u_3, 0, \ldots, 0)$, with $u_i\sim U(-2, 2)$, $\Delta_0^1=-2$, $\Delta_0^2=-3$, $\sigma_x=1$, $\lambda=\sqrt{\log(p)/4n}$.}}
    \label{fig:games-2}
\end{figure}

\begin{figure}[tpb]
    \centering
    \begin{subfigure}[t]{0.46\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_games_varying_p_sigma_n_5000.png}
        \caption{$n=5000$}
    \end{subfigure}
    ~
     \begin{subfigure}[t]{0.46\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_games_varying_p_sigma_n_10000.png}
        \caption{$n=10000$}
    \end{subfigure}
    \caption{\footnotesize{\emph{Games.} Median percentage decrease in $\ell_2$ error between 2SLG and 2SOrthoLG, i.e. $100\times \frac{\text{error}_{\text{2SLG}} - \text{error}_{\text{2SOrthoLG}}}{\text{error}_{\text{2SLG}}}$ across $100$ experiments based on the games  DGP1 and as $p$ varies in $\{1000, 2000, 5000\}$ and $\sigma_x$ varies in $\{1, 2, 3\}$. Parameters: $k_1=1$, $k_2=3$, $\alpha_0^1=(1, 0, \ldots, 0)$, $\alpha_0^2=(u_1, u_2, u_3, 0, \ldots, 0)$, with $u_i\sim U(-2, 2)$, $\Delta_0^1=-2$, $\Delta_0^2=-3$, $\lambda=\sqrt{\log(p)/4n}$.}}
    \label{fig:games-3}
\end{figure}

\subsection{Monte Carlo Simulations for Section~\ref{sec:nonlinearTE}}

We performed an experimental evaluation of our orthogonal estimation method for the case of the logistic link function presented in Example \ref{ex:logistic}. We considered the following concrete data generating process, which is a non-linear generalization of the Partially-Linear Regression model:
\begin{align*}
    \Pr[y=1|u, \tau] =& \mcL(\tau \cdot u'\theta_0 + u'\alpha_0), & y\in \{0, 1\}\\
    \tau =& u'\beta_0 + \eta,\\
    \eta \sim N(0, \sigma_\eta),~~& u \sim U(-\sigma_u, \sigma_u)
\end{align*}
where $\tau\in \R$ is a base treatment variable, $u\in \R^p$ is a high-dimensional vector of features/control variables and $y\in \R$ is an outcome of interest. The target parameter $\theta_0$ corresponds to a linear parametrization of the heterogeneous treatment effect of $\tau$ on the utility of an agent in a binary discrete choice model. The features $u$ also have a confounding effect, in the sense that they have a direct impact on the utility apart from determining the heterogeneity in the effect of $\tau$.

In this setting our orthogonal approach with cross-fitting described in this section boils down to the following steps:
\begin{enumerate}
    \item Split the data-set $S$ in half and on the first sample:
    \begin{enumerate}
        \item Compute estimate $\hat{\beta}$ of $\beta_0$ via a Lasso regression of $\tau$ on $u$.
        \item Compute a preliminary estimate $\tilde{\theta}$ of $\theta_0$ and an estimate $\hat{\alpha}$ of $\alpha_0$, by running a logistic $\ell_1$ penalized regression of $y$ on $\tau \cdot u$ and $u$.
        \item Let the estimates of the nuisance functions be: $\hat{\pi}(u) = u'\hat{\beta}$, $\hat{q}(u) = u'\hat{\beta}\cdot u'\tilde{\theta} + u'\hat{\alpha}$, $\hat{V}(z) = \mcL'(\tau u'\tilde{\theta} + u'\hat{\alpha})$ and evaluate them on the other half of the data to obtain nuisance quantities, $\hat{\pi}_i = \hat{\pi}(u_i), \hat{q}_i=\hat{q}(u_i), \hat{V}_i=\hat{V}(z_i)$ for each sample $i$.
    \end{enumerate}
    \item Repeat the above process to compute the nuisance estimates for the first half of the data, by exchanging the role of the two data splits.
    \item  Using the nuisance estimates for all data points, run an orthogonal $\ell_1$ penalized regression based on the loss:
\begin{equation*}
    L_S(w_i, \theta, \hat{g}(z_i)) = \frac{1}{n}\sum_i \frac{y_i\cdot \log\left(\mcL\left((\tau_i - \hat{\pi}_i) u_i'\theta+\hat{q}_i\right)\right) + (1-y_i)\cdot \log\left(1-\mcL((\tau_i - \hat{\pi}_i) u_i'\theta+\hat{q}_i)\right)}{\hat{V}_i}
\end{equation*}
\end{enumerate}
We compared our approach to a direct approach where we estimate $\theta_0$ by running a logistic $\ell_1$ penalized regression, regressing $y$ on $\tau\cdot u$ and $u$ and then reading the target parameter from the coefficients associated with variables $\tau \cdot u$. Figure~\ref{fig:experiments-logistic} provides a sample of the experimental performance of the two approaches, showing a smaller $\ell_1$ and $\ell_2$ error of the orthogonal approach across $100$ experiments.

\begin{figure}[tpb]
     \centering
    \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_error_logistic.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_decrease_logistic.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_error_logistic.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_decrease_logistic.png}
    \end{subfigure}
    \caption{\footnotesize{\emph{Heterogeneous Treatment Effects with Logistic Link Function.} Direct vs orthogonal estimation for heterogeneous treatment effect model with a logistic link function. We simulated $100$ experiments, with data generating parameters: $n=5000$, $p=2000$, $k=2$, $k_g=\|\alpha_0\|_0=\|\beta_0\|_0=5$, $\sigma_\eta=3$, $\sigma_u=0.5$. Supports of $\alpha_0$ and $\beta_0$ are identical and all non-zero coefficients of $\alpha_0, \beta_0, \theta_0$ are equal to one. The left figure shows the distribution of the $\ell_2$ errors of the two methods as well as the distribution of the decrease in $\ell_2$ error when going from from the direct regression to the orthogonal plug-in estimation across the $100$ experiments. The right figure shows the corresponding quantities for the $\ell_1$ norm}}
    \label{fig:experiments-logistic}
\end{figure}


TITLE: What is different between maximal cyclic subgroup with cyclic maximal subgroup?
QUESTION [2 upvotes]: What is different between  "maximal cyclic subgroup" with "cyclic maximal subgroup"?
Are these are equal or different?(example?)

REPLY [3 votes]: A maximal cyclic subgroup is a cyclic subgroup that is maximal among all cyclic subgroups. That is there is no other cyclic subgroup that would contain it while there might be other non-cyclic subgroups that are larger.
A cyclic maximal subgroup is a maximal subgroup (among all subgroups) that is cyclic. That is it is a maximal subgroup that happens to be cyclic.
I think this is the default reading, but I would not rely on everybody using or understanding it in this way.
Note that a cyclic maximal subgroup is always a maximal cyclic subgroup but the converse might not be true.

In the additive group  $\mathbb{Z}/p^2\mathbb{Z} \times \mathbb{Z}/p^3\mathbb{Z} $.
The subgroup $ \{0 \} \times \mathbb{Z}/p^3\mathbb{Z}$ is a maximal cyclic subgroup, yet not a maximal subgroup and thus not a cyclic maximal subgroup either.
In the additive group  $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p^3\mathbb{Z} $.
The subgroup $ \{0 \} \times \mathbb{Z}/p^3\mathbb{Z}$ is a maximal cyclic subgroup, and also a maximal subgroup and thus a cyclic maximal subgroup.


TITLE: Functor category's objects fail to be a class?
QUESTION [4 upvotes]: Given two categories, we can form the functor category whose objects are functors. Functors by definition consist of two mappings from in general classes to classes, which makes it fail to be a set. But set theory in which classes are involved avoids Rusell's paradox by only allowing sets as members. This argument shows that functor category's objects fail to be a class, which makes functor category fail to be a category.
I've never been trained in axiomatic set theory, so I guess my first question should be:is there anything wrong with the above argument? If it works, then how can we overcome the difficulty?
There are other similar problems bothering me: in say K-theory, we take the equivalence classes of modules/vector bundles as our objects. However the equivalence class of any module is always a proper class, just as we can't talk about the set consisting of all sets with a single element. This is a somehow "universal" problem, since equivalence classes appear everywhere, and we're technically almost never allowed to use the construction whenever classes are involved.

REPLY [5 votes]: As has been discussed, there are plenty of ways to set up the foundations and definitions so that it is not a problem to have proper classes of proper classes, rather than of sets.
But you are right to worry about functor "categories".  In Mac Lane's language, a small category has a set of objects and a set of morphisms.  A locally small category has a class of objects, and between any two objects a set of morphisms — this is what most commonly is given the name "category".  A large category may have a class of morphisms between some pair of objects.  The point is that the functor category between any two small categories is again small, and the functor category from a small category to a locally small one is locally small.  But the functor category between two locally small categories might be large.  Consider for example the category whose objects are sets and whose morphisms are isomorphisms; then in its endofunctor category identity functor has $\prod_c c! = 2^{\sum_c c}$ automorphisms, where $c$ ranges over cardinalities and $c!$ is the cardinality of the set of automorphisms of a set of size $c$ (we have $2^c \leq c! \leq c^c$, but $c^c \leq (2^c)^c = 2^{c^2} = 2^c$ for infinite $c$).


TITLE: Diagonal terms of the inverse of positive definite matrix
QUESTION [1 upvotes]: I have a matrix $A = I + G$ where $G_{ii} = 0$ for all $i$, and $G_{ij} \in \{0, a\}$ with $a \in [0, 1[$, $G$ is symmetric, and such that $A$ is positive definite.
We know that the inverse of $A$, call it $B$, is also symmetric positive definite, and also that $B_{ii} > 1$ for all $i$.
My question: is it true that $B_{ii} > B_{ij}$ for all $i, j$?
Any help welcome! Thanks

REPLY [1 votes]: The answer is no.  For a random counter-example, consider
$A:= \left[\begin{matrix}1 & \frac{5}{9} & 0 & 0 & 0\\\frac{5}{9} & 1 & 0 & \frac{5}{9} & \frac{5}{9}\\0 & 0 & 1 & \frac{5}{9} & \frac{5}{9}\\0 & \frac{5}{9} & \frac{5}{9} & 1 & \frac{5}{9}\\0 & \frac{5}{9} & \frac{5}{9} & \frac{5}{9} & 1\end{matrix}\right]\implies A^{-1}= \left[\begin{matrix}\frac{1053}{103} & - \frac{1710}{103} & - \frac{1125}{103} & \frac{2025}{206} & \frac{2025}{206}\\- \frac{1710}{103} & \frac{3078}{103} & \frac{2025}{103} & - \frac{3645}{206} & - \frac{3645}{206}\\- \frac{1125}{103} & \frac{2025}{103} & \frac{1503}{103} & - \frac{1260}{103} & - \frac{1260}{103}\\\frac{2025}{206} & - \frac{3645}{206} & - \frac{1260}{103} & \frac{9999}{824} & \frac{8145}{824}\\\frac{2025}{206} & - \frac{3645}{206} & - \frac{1260}{103} & \frac{8145}{824} & \frac{9999}{824}\end{matrix}\right]$
(check row 3)


TITLE: Integrable function has a graph that's a null set?
QUESTION [2 upvotes]: I'm asked in an exercise to prove every integrable real function $f : R \rightarrow R$ on an interval $[a,b]$ has a graph that's a null set. I would appreciate some assistance with this!
More information: Integrable here means Darboux/Riemann integrable. This is not a measure theory question and I am unfamiliar with measure theory results and theorems.
We have already proven that if f is continuous, then its graph will be a null set. I was trying to generalize the ideas from that proof to this proof but I haven't succeeded yet... I really have no idea how to approach this.
Thanks a lot!

REPLY [3 votes]: (Note: I'm assuming below that $f$ is bounded; Riemann integrability is usually only considered for bounded functions, so this is not an unreasonable assumption.)
Given a function $f$, an interval $[a,b]$, and a partition $P$ of $[a,b]$, let us denote by $\overline{S}(f,P)$ the upper Riemann sum of $f$ on $[a,b]$ relative to the partition $P$; that is, we consider
$$\overline{S}(f,P) = \sum_{i=1}^{n}s_{i}\Delta_i$$
where $a=x_0\lt x_1\lt\cdots\lt x_n=b$ is the partition, $s_i$ is supremum of the values of $f(x)$ on $[x_{i-1},x_i]$, and $\Delta_i=x_i-x_{i-1}$. Similarly, let $\underline{S}(f,P)$ be the lower Riemann sum of $f$ on $[a,b]$ relative to the partition $P$, that is
$$\underline{S}(f,P) = \sum_{i=1}^n m_i\Delta_i$$
where $m_i$ is the
infimum of the values of $f$ on $[x_{i-1},x_i]$.
$f$ is integrable on $[a,b]$ if and only if it is bounded, and for any sequence of partitions $P_n$ of $[a,b]$ such that the mesh size $\lVert P_n\rVert\to 0$ as $n\to\infty$, we have
$$\lim_{n\to\infty}\underline{S}(f,P_n) = \lim_{n\to\infty}\overline{S}(f,P_n),$$
or equivalently, if
$$\lim_{n\to\infty}\Bigl( \overline{S}(f,P_n) - \underline{S}(f,P_n)\Bigr) = 0.$$
Now think about what $\overline{S}(f,P_n) - \underline{S}(f,P_n)$ represents. At any given subinterval of the partition $[x_i,x_{i+1}]$, we are taking $\bigl(s_i - m_i\bigr)\Delta_i$. Now, $\Delta_i$ is the length of the interval; $s_i$ is the supremum of the values the function takes, and $m_i$ is the infimum value the function takes. That means that the graph of the function on this interval is contained in the rectangle $[x_i,x_{i+1}]\times[m_i,s_i]$, which has area exactly $\bigl(s_i-m_i\bigr)\Delta_i$. That is, the difference between $\overline{S}(f,P_n)$ and $\underline{S}(f,P_n)$ can be interpreted as the sum of the areas of a collection of rectangles that contains the graph of $y=f(x)$.
Can you take it from here? (Note that the above does not depend in any way on whether $f$ is positive, negative, chaotic, continuous, or not; just on the fact that it is bounded and integrable).


TITLE: Finding set of triplets which sum to N with additional constraints.
QUESTION [3 upvotes]: Given a number n, we construct a set S with triplets $(x_i, y_i, z_i)$ such that $x_i+y_i+z_i = n$  $\forall$ $ 1 \le i \le |S| $. Also $x_i\ge 0, y_i\ge 0, z_i\ge 0$. Additionally we must satisfy the constraint that all $x_i's$ in S are unique and all $y_i's$ in S are unique and all $z_i's$ in S are unique.
Find the maximum size of set S and find any such set S.
This problem was part of a contest here: Beautiful Set 3 which has ended. There is tutorial section which is very terse. Although I understand what is being done there it is not very clear why that algorithm would give a correct answer.
So if you help in understand the tutorial or give another answer/algorithm, I would greatly appreciate it.

REPLY [2 votes]: First we argue that $|S| \leq \frac{2n}{3} + 1$.
To see this, note that $$n|S| = \sum_i (x_i + y_i + z_i) \geq 3\frac{|S|(|S|-1)}{2}$$
Then we show how to find an $S$ with $|S| = \lfloor\frac{2n}{3} \rfloor + 1$. Suppose $n = 3k + j$ for $j = 0,1,2$

If $j = 0$, take the triples $(2i,k-i,2k-i)$ where $i = 0,1,2,\dots, k$ and $(2i+1,2k-i,k-i-1)$ where $i = 0,1,2,\dots, k-1$.
If $j=1$, take the above triples for $j = 0$ and add one to each $x_i$.
If $j=2$ then take the above triples for $j = 0$, add one to each $x_i$ and each $y_i$ and append the triple $(0,0,n)$.

Note that in each case there are $\lfloor\frac{2n}{3}\rfloor + 1$ triples, no $x_i,y_i,z_i$ repeats, and each triple sums to $n$.


text:
\section{Absolute Value induces Equivalence not Compatible with Integer Addition}
Tags: Congruence Relations, Integer Addition, Absolute Value Function

\begin{theorem}
Let $\Z$ be the [[Definition:Integer|set of integers]].
Let $\RR$ be the [[Definition:Relation|relation]] on $\Z$ defined as:
:$\forall x, y \in \Z: \tuple {x, y} \in \RR \iff \size x = \size y$
where $\size x$ denotes the [[Definition:Absolute Value|absolute value]] of $x$.
Then $\RR$ is not a [[Definition:Congruence Relation|congruence relation]] for [[Definition:Integer Addition|integer addition]].
\end{theorem}

\begin{proof}
From [[Absolute Value Function on Integers induces Equivalence Relation]], $\RR$ is an [[Definition:Equivalence Relation|equivalence relation]].
However, consider that:
{{begin-eqn}}
{{eqn | l = \size {-1} = \size 1
      | o = \leadsto
      | r = -1 \mathop \RR 1
      | c =
}}
{{eqn | l = \size 2 = \size 2
      | o = \leadsto
      | r = 2 \mathop \RR 2
      | c =
}}
{{end-eqn}}
By conventional [[Definition:Integer Addition|integer addition]]:
:$-1 + 2 = 1$
while:
:$1 + 2 = 3$
But it does not hold that:
:$\size 1 = \size 3$
Therefore $\RR$ is not a [[Definition:Congruence Relation|congruence relation]] for [[Definition:Integer Addition|integer addition]].
Hence the result, by [[Proof by Counterexample]].
{{qed}}
\end{proof}

config: wiki


TITLE: Collective term for interpolation and extrapolation
QUESTION [2 upvotes]: Is there a collective term for both interpolation and extrapolation? If there is such a term, what is it?

REPLY [0 votes]: Control theorists sometimes use the word "filtering" to describe both.
https://english.stackexchange.com/questions/146171/hypernym-for-interpolation-and-extrapolation
has several suggestions, including "regression", "fitting", and "estimation".