text:
\section{Extremal rank properties of truncated Reed-Muller codes}
\label{sec:reed-muller}
In this section we prove Lemma \ref{prop:evaluation-rank}.
Let $\generatingmatrix{d}$ be the natural generating matrix of the $(d,\sampledim)$ Reed-Muller code over the field $\mathbb{F}_p$ for $p$ an odd prime.
That is,
$\generatingmatrix{d}$ is a $p^\sampledim \times |\monomial{p}{d}{\sampledim}|$ matrix,
where each row is indexed by $a\in \mathbb{F}_p$,
and each column is indexed by a monomial $q\in \monomial{p}{d}{\sampledim}$,
and $M^{(d)}(x,q)=q(x)$.
Clearly the rank of $\generatingmatrix{d}$ is  $|\monomial{p}{d}{\sampledim}|$,
since all the columns are independent.
For $S\subset \mathbb{F}_p^\sampledim$,
define $\generatingmatrix{d}_S$ as $\generatingmatrix{d}$ restricted on rows in $S$.

For fixed $q\in \monomial{p}{d}{\sampledim}$,
$(q(x))_{x\in S}$ is precisely the column corresponding to $q$ in $M^{(d)}$ restricted to  rows indexed by $S$. From this prospective,
the dimension of the subspace spanned by $\{(q(x))_{q\in \monomial{p}{d}{\sampledim}}:x\in S\}$ is exactly the (column) rank of the matrix $\generatingmatrix{d}_S$.
So we can restate Lemma \ref{prop:evaluation-rank} as the following:

\begin{lemma}\label{prop:evalutation-rank-new}
Let $S$ be a subset of $\mathbb{F}_p^\sampledim$ such that $|S|=p^r$,
then $rank(\generatingmatrix{d}_S)\geq |\monomial{p}{d}{r}|$.
\end{lemma}

As noted in the introduction we will derive the more general bound for an
arbitrary value of $|S|$, not only for the restricted case that $|S|=p^r$ that occurs in the above lemma.
We start with the special case where $S$ contains the lexicographically smallest  $|S|$ elements.
(Here lexicographical order means that for $a=(a_1,\cdots,a_\sampledim)$ and $b=(b_1,\cdots,b_\sampledim)$,
$a<b$ if and only if there exists $1\leq k\leq \sampledim$ such that $a_i=b_i$ for $i<k$ and $a_k<b_k$.)
We will show that this is in fact an extremal case.

For integer $\iterator$,
let $S_\iterator\subset \mathbb{F}_p^\sampledim$ be the subset that contains the smallest $\iterator$ elements.
Define $g_d(\iterator)$ as the rank of $\generatingmatrix{d}_{S_\iterator}$.
For the completeness of definition,
we set $g_d(\iterator)=0$ when $d<0$ or $\iterator=0$.
When $\iterator$ is a power of $p$,
it is easy to compute the value of $g_d(\iterator)$.

\begin{lemma}\label{thm-g_d-base}
$
g_d(p^r)=|\monomial{p}{d}{r}|.
$
\end{lemma}

\begin{proof}
Let $x$ be a monomial of degree at most $d$ over $x_1,\cdots,x_\sampledim$.
Notice that $\forall a\in S_{p^r}$,
$a_1=a_2=\cdots=a_{\sampledim-r}=0$.
So if $x$ contains any of the first $\sampledim-r$ variables,
the column indexed by $x$ will be $0$.
On other other hand,
all the columns corresponding to monomials over $x_{\sampledim-r+1},\cdots,x_\sampledim$ of degree at most $d$ are linear independent.
Otherwise this means that some monomial can be represented as a linear combination of other monomials, which is impossible.
So the rank of the submatrix is just the number of monomials over $r$ variables of degree at most $d$.
\end{proof}

It is more complicated to compute the value for general $\iterator$.
With careful observation,
we have the following recursion.

\begin{lemma}\label{def-g_d}
Let $r$ be the unique integer so that $p^r\leq \iterator<p^{r+1}$.
Let $\iterator=k\cdot p^r+c$.
Then
\[
g_d(\iterator)=\sum_{i=0}^{k-1}g_{d-i}(p^r)+g_{d-k}(c).
\]
As a special case, when $c=0$, we have
$
g_d(k\cdot p^r)=\sum_{i=0}^{k-1}g_{d-i}(p^r)
$.
\end{lemma}

\begin{proof}
For the sake of convenience,
let $\monomialeq{p}{d}{r}$ be the set of monomials over the last $r$ variables whose degree equals $d$,
and  $\monomialle{p}{d}{r}$ be the set of monomials over the last $r$ variables whose degree is at most $d$.

Consider the block structure of the matrix.
Let $A_0$ be the submatrix that takes $S_{p^r}$ as rows and  $\monomialle{p}{d-p+1}{r}$ as columns.
For $i=1,2,\cdots,p-1$,
let $A_i$ be the submatrix that takes $S_{p^r}$ as rows and $\monomialeq{p}{d-p+1+i}{r}$ as columns.
Let $A_{\leq i}$ be the blocks $(A_0,\cdots,A_i)$,
then $A_{\leq i}$ is precisely the submatrix that takes $S_{p^r}$ as rows and $\monomialle{p}{d-p+i+1}{r}$ as columns.

Now let us consider the rows for $R_t:=\{a|a_1=\cdots=a_{\sampledim-r-1}=0,a_{\sampledim-r}=t\}$ for $t>0$.
The non-zero parts correspond to monomials that only depend on $x_{\sampledim-r},x_{\sampledim-r+1},\cdots,x_{\sampledim}$.
If we group all the monomials by their degree on $x_{\sampledim-r}$
then, for $t\leq k-1$,
the row will be of the form
\[
A_{\leq p-1},\,t\cdot A_{\leq p-2},\, t^2\cdot A_{\leq p-3},\,
\cdots, \,t^{p-1}\cdot A_{\leq 0}.
\]
Things are a little different for $t=k$,
since $|R_k|<p^r$.
In this case,
we define $A_{\leq i}'$ as the first $c$ rows of $A_{\leq i}$,
and it is easy to check that the row is of the form
\[
A_{\leq p-1}',\,k\cdot A_{\leq p-2}',\, k^2\cdot A_{\leq p-3}',\,
\cdots, \,k^{p-1}\cdot A_{\leq 0}'.
\]
Therefore the matrix $\generatingmatrix{d}_{S_\iterator}$ is of the form:

\begin{center}
\begin{tabular}{ c||c|c|c|c|c }
& $\monomialle{p}{d}{r} $ &$x_{\sampledim-r}\cdot \monomialle{p}{d-1}{r}$ &$x_{\sampledim-r}^2\cdot \monomialle{p}{d-2}{r}$&$\cdots$ & $x_{\sampledim-r}^{p-1}\cdot  \monomialle{p}{d-p+1}{r}$\\
\hline
\hline
 $\{a_{\sampledim-r}=0\}$ & $A_{\leq p-1}$ & $0$ & $0$ & $\cdots$ & $0$  \\
 \hline
   $\{a_{\sampledim-r}=1\}$ & $A_{\leq p-1}$ & $A_{\leq p-2}$ & $A_{\leq p-3}$ & $\cdots$ & $A_{\leq 0}$  \\
 \hline
   $\{a_{\sampledim-r}=2\}$ & $A_{\leq p-1}$ & $2\cdot A_{\leq p-2}$ & $4\cdot A_{\leq p-3}$ & $\cdots$ & $2^{p-1}\cdot A_{\leq 0}$  \\
 \hline
 \vdots & \vdots &\vdots & \vdots & \vdots &\vdots\\
 \hline
  $\{a_{\sampledim-r}=k-1\}$ & $ A_{\leq p-1}$ & $(k-1)\cdot A_{\leq p-2}$ & $(k-1)^2\cdot A_{\leq p-3}$ & $\cdots$ & $(k-1)^{p-1}\cdot A_{\leq 0}$\\
 \hline
  $\{a_{\sampledim-r}=k\}$ & $ A_{\leq p-1}'$ & $k\cdot A_{\leq p-2}'$ & $k^2\cdot A_{\leq p-3}'$ & $\cdots$ & $k^{p-1}\cdot A_{\leq 0}'$\\
 \hline
\end{tabular}
\end{center}

We have two important observations:
\begin{itemize}
\item $A_{\leq p-i-1}$ is the first $|\monomialle{p}{d-i-1}{r}|$ columns of $A_{\leq p-i}$, and
\item $A_{\leq i}'$ is the first $c$ rows of $A_{\leq i}$.
\end{itemize}
Therefore, we can apply Gaussian elimination to turn the matrix in to a block-diagonal matrix.
We do this in two steps.
The following algorithm first eliminates on columns to obtain a triangular matrix, based on the first observation.

\begin{algorithm}[H]\label{algorithm-column-elimination}
\caption{Triangular elimination}
Initialize $I=\{0,\cdots,k\}$, $u=0$.\\
For $i,j\in \{0,1,\cdots,k\}$,
set $b_{i,j}=i^j$.\\
\tcc{$b_{i,j}$ is the coefficient of each block at the beginning.}
\For{$u=0,\cdots,k$}{
\For{$v=u+1,\cdots,p-1$}{
\tcc{Subtract $b_{u,v}b_{u,u}^{-1}$ times the prefix of length $|\monomialle{p}{d-v}{r}|$ of  $u$-th column block from $v$-th column block. }
\For{$i\in \{0,1,\cdots,p-1\}$}{
$
b_{i,v}\leftarrow b_{i,v}-b_{u,v}b_{u,u}^{-1}b_{i,u}
$
}
}
}
\end{algorithm}

We have the following properties.
\begin{claim}\label{lem-elimination}
At the beginning of round $u$ of Algorithm \ref{algorithm-column-elimination},
for all $i\leq u$, we have
$b_{i ,i}\neq 0$,
and at the end of round $u$,
for all $i\leq u$, we have
$b_{i ,j}=0$ for $j=i+1,\cdots,p-1$.
\end{claim}

\begin{proof}
Let us consider the function $f^{(\rounditerator)}_j(i)$,
which denotes the coefficient of the $(i,j)$ block at the beginning of round $\rounditerator$.
We prove a strengthened claim: For $\rounditerator=0,\cdots,k+1$,
\begin{itemize}
\item $f^{(\rounditerator)}_j(i)$ is a monic degree $j$ polynomial on variable $i$,
\item $f^{(\rounditerator)}_i(i)\neq 0$ for $i\leq \rounditerator$, and
\item when $\rounditerator>0$,
$f^{(\rounditerator)}_j(i)=0$ for $i\leq \rounditerator-1$ and $j=i+1,\cdots,p-1$.
\end{itemize}

When $\rounditerator=0$,
we have $f^{(0)}_j(i)=i^j$ which is monic and has degree $j$.
Also,
$f^{(0)}_0(0)=1\neq 0$.
So the base case is true.

The update rule given by the algorithm says
\[
f^{(\rounditerator)}_j(i)=\begin{cases} f^{(\rounditerator-1)}_j(i)-\frac{f^{(\rounditerator-1)}_j({\rounditerator-1})}{f^{(\rounditerator-1)}_{\rounditerator-1}({\rounditerator-1})}\cdot f^{(\rounditerator-1)}_{\rounditerator-1}(i)&\mbox{if } j\geq \rounditerator\\
f^{(\rounditerator-1)}_j(i)& \mbox{if } j<\rounditerator
\end{cases}
\]
When $j<\rounditerator$, clearly $f^{(\rounditerator)}_j(i)$ is still a monic degree $j$ polynomial.
When $j\geq \rounditerator$,
by the induction hypothesis,
$f^{(\rounditerator-1)}_{\rounditerator-1}({\rounditerator-1})\neq 0$,
and the degree of $f^{(\rounditerator-1)}_{\rounditerator-1}(i)$ is strictly smaller than $j$.
Therefore we have that
$f^{(\rounditerator)}_j(i)$ is also a monic  degree $j$ polynomial.

For $i\leq t-2$,
by the induction hypothesis,
$f^{(t-1)}_j(i)=0$ for $j\geq i+1$.
Then both update rules give us $f^{(t)}_j(i)=0$ for $j\geq i+1$.
For the $i=t-1$ case,
 by Gaussian elimination,
$f^{(t)}_j(t-1)=0$ for all $j\geq t$.
Combining the two cases we have for $i\leq t-1$,
$f^{(t)}_j(i)=0$ for $j\geq i+1$.

Notice that
\[
f^{(\rounditerator)}_{\rounditerator}(0)=f^{(\rounditerator)}_{\rounditerator}(1)=\cdots=f^{(\rounditerator)}_{\rounditerator}({\rounditerator-1})=0.
\]
Since $f^{(\rounditerator)}_{\rounditerator}(i)$ is monic and has degree $\rounditerator$,
it can have at most $\rounditerator$ roots.
This implies that $\rounditerator$ cannot be its root,
hence $f^{(\rounditerator)}_{\rounditerator}(\rounditerator)\neq 0$.
\end{proof}

Using this claim we complete the proof of Lemma~\ref{def-g_d}:
After the first step,
the matrix is in the form:
\begin{center}
\scalebox{0.8}{
\begin{tabular}{ c||c|c|c|c|c|c }
& $\monomialle{p}{d}{r} $ &$x_{\sampledim-r}\cdot \monomialle{p}{d-1}{r}$ &$x_{\sampledim-r}^2\cdot \monomialle{p}{d-2}{r}$&$\cdots$ & $x_{\sampledim-r}^{k-1}\cdot  \monomialle{p}{d-k+1}{r}$ & $x_{\sampledim-r}^{k}\cdot  \monomialle{p}{d-k}{r}$  \\
\hline
\hline
 $\{a_{\sampledim-r}=0\}$ & $b_{0,0}A_{\leq p-1}$ & $0$ & $0$ & $\cdots$ & $0$ & $0$ \\
 \hline
   $\{a_{\sampledim-r}=1\}$ & $b_{1,0}A_{\leq p-1}$ & $b_{1,1}A_{\leq p-2}$ & $0$ & $\cdots$ & $0$  & $0$\\
 \hline
   $\{a_{\sampledim-r}=2\}$ & $b_{2,0}A_{\leq p-1}$ & $b_{2,1}A_{\leq p-2}$ & $ b_{2,2}A_{\leq p-3}$ & $\cdots$ & $0$ & $0$ \\
 \hline
 \vdots & \vdots &\vdots & \vdots & \vdots &\vdots &\vdots \\
 \hline
  $\{a_{\sampledim-r}=k-1\}$ & $ b_{k-1,0}A_{\leq p-1}$ & $b_{k-1,1}A_{\leq p-2}$ & $b_{k-1,2}A_{\leq p-3}$ & $\cdots$ &$b_{k-1,k-1}A_{\leq p-k}$ & $0$\\
 \hline
  $\{a_{\sampledim-r}=k\}$ & $ b_{k,0}A_{\leq p-1}'$ & $b_{k,1}A_{\leq p-2}'$ & $b_{k,2}A_{\leq p-3}'$ & $\cdots$ & $b_{k,k-1}A_{\leq p-k}'$ & $ b_{k,k}A_{\leq p-k-1}'$\\
 \hline
\end{tabular}
}
\end{center}
with all other columns having value 0.
Now, the second observation says that $A_{\leq p-i}'$ is a submatrix of
$A_{\leq p-i}$.
Moreover,
we have $b_{i,i}\neq 0$ for $i=0,\cdots,k$.
So we can eliminate row by row
to get a diagonal matrix,
whose rank is very easy to compute.
The rank of $A_{\leq p-i}$ is simply $|\monomialle{p}{d-i+1}{r}|=g_{d-i+1}(p^r)$.
By the definition of the $g_d$ function,
the rank of $A_{\leq 0}'$ is just $g_{d-k}(c)$.
Hence
\[
g_d(\iterator)=g_d(k\cdot p^r+c)=\sum_{i=0}^{k-1}g_{d-i}(p^r)+g_{d-k}(c).\\[-3ex]
\]
\end{proof}

Intuitively,
for any set $S\subset p^\sampledim$ of size $\iterator$,
the rank of $\generatingmatrix{d}_S$ will be larger than that of $\generatingmatrix{d}_{S_\iterator}$,
since $S_\iterator$ is the most compact way to arrange $\iterator$ rows.
Formally stated, this is the following restatement of
Theorem~\ref{thm:main-extremal}:

\begin{theorem}\label{rank-result}
For arbitrary $S\subseteq p^\sampledim$ with $|S|=\iterator$ and for any $d$,
\[
rank(\generatingmatrix{d}_S)\geq rank(\generatingmatrix{d}_{S_\iterator})=g_d(\iterator).
\]
\end{theorem}

Note that $g_d(\iterator)$ does not depend on $\sampledim$.
Indeed, all we need of $\sampledim$ is that $\iterator \le p^\sampledim$ so that the matrix
$\generatingmatrix{d}$ has at least $m$ rows.

Before we actually prove Theorem~\ref{rank-result},
we first argue that this is all we need to prove Lemma \ref{prop:evalutation-rank-new}.
Indeed,
we can simply set $\iterator=p^r$;
then with Lemma~\ref{thm-g_d-base},
we just have when $|S|=p^r$,
\[
rank(\generatingmatrix{d}_S)\geq g_d(p^r)=|\monomial{p}{d}{r}|.
\]

It turns out that in order to prove Theorem \ref{rank-result},
it is sufficient to have the following sub-additivity property of the $g_d$ function.
\begin{lemma}\label{lem-main}
For $a_0\geq a_1\geq \cdots \geq a_{p-1}\geq 0$,
for any $d$,
\[
g_d(\sum_{i=0}^{p-1}a_i)\leq \sum_{i=0}^{p-1}g_{d-i}(a_i).
\]
\end{lemma}

\begin{proof}[Proof of Theorem~\ref{rank-result} from Lemma \ref{lem-main}]
We use induction on the size of $|S|$. When $|S|=1$,
$rank(\generatingmatrix{d}_S)=1$,
while  $g_d(1)=1$,
so the base case is true.

Assume that we have proved that for all $S'$ with $|S'|\leq |S|$ and all degrees $d$,
$rank(\generatingmatrix{d}_{S'})\geq g_d(|S'|)$.
Let $t\in [\sampledim]$ be the smallest integer so that $\exists x,y\in S, x_t\neq y_t$.
For $i\in \{0,1,\cdots,p-1\}$,
define $S_i=\{x\in S:x_t=i\}$.
For $j=1,\cdots,p$,
let  $A_{\leq p-j}^{(i)}$ be the submatrix of $M$ that takes $S_i$ as rows and $\monomialle{p}{d+1-j}{p-t}$ as columns.
We claim that we only need to study the following matrix:
\begin{center}
\begin{tabular}{ c|c|c|c|c|c }
& $\monomialle{p}{d}{\sampledim-t} $ &$x_{t}\cdot \monomialle{p}{d-1}{\sampledim-t}$ &$x_{t}^2\cdot \monomialle{p}{d-2}{\sampledim-t}$&$\cdots$ & $x_{t}^{p-1}\cdot  \monomialle{p}{d-p+1}{\sampledim-t}$\\
\hline
 $S_0$ & $A_{\leq p-1}^{(0)}$ & $0$ & $0$ & $\cdots$ & $0$  \\
 \hline
   $S_1$ & $A_{\leq p-1}^{(1)}$ & $A_{\leq p-2}^{(1)}$ & $A_{\leq p-3}^{(1)}$ & $\cdots$ & $A_{\leq 0}^{(1)}$  \\
 \hline
   $S_2$ & $A_{\leq p-1}^{(2)}$ & $2\cdot A_{\leq p-2}^{(2)}$ & $4\cdot A_{\leq p-3}^{(2)}$ & $\cdots$ & $2^{p-1}\cdot A_{\leq 0}^{(2)}$  \\
 \hline
 \vdots & \vdots &\vdots & \vdots & \vdots &\vdots\\
 \hline
  $S_{p-2}$ & $ A_{\leq p-1}^{(p-2)}$ & $(p-2)\cdot A_{\leq p-2}^{(p-2)}$ & $(p-2)^2\cdot A_{\leq p-3}^{(p-2)}$ & $\cdots$ & $(p-2)^{p-1}\cdot A_{\leq 0}^{(p-2)}$\\
 \hline
  $S_{p-1}$ & $ A_{\leq p-1}^{(p-1)}$ & $(p-1)\cdot A_{\leq p-2}^{(p-1)}$ & $(p-1)^2\cdot A_{\leq p-3}^{(p-1)}$ & $\cdots$ & $(p-1)^{p-1}\cdot A_{\leq 0}^{(p-1)}$\\
 \hline
\end{tabular}
\end{center}
This is because all the other columns can be spanned by this matrix.
Indeed, consider a monomial $x=y\cdot z$ where $y$ is a monomial over $x_1,\cdots,x_{k-1}$ and $z$ is over $x_k,\cdots,x_\sampledim$.
Since for all $a\in S$, $a_i$ is fixed for $i=1,\cdots,k-1$,
the column for $x$ is just the column for $z$ times some constant.

We also have one important observation about this matrix.
\begin{itemize}
\item For all $i,j$, $A_{\leq p-j-1}^{(i)}$ is the first $|\monomialle{p}{d-j-1}{\sampledim-t}|$ columns of $A_{\leq p-j}^{(i)}$
\end{itemize}
so we can again use Gaussian elimination.
Although we may not be able to get a diagonal matrix because we do not know the relationship between the $S_i$,
we can carefully modify algorithm \ref{algorithm-column-elimination} to obtain a triangular matrix:

\begin{algorithm}[H]\label{algorithm-elimination}
\caption{Triangular elimination revised}
Initialize $I=\{0,\cdots,p-1\}$, $u=0$.\\
For $i,j\in \{0,1,\cdots,p-1\}$,
set $b_{i,j}=i^j$.\\
\tcc{$b_{i,j}$ is the coefficient of each block at the beginning.}
\While{$I\neq \emptyset$}
{
$i_0=\arg\max_{i\in I}|S_i|$.\\
\For{$v=u+1,\cdots,p-1$}{
\tcc{Subtract $b_{i_0,v}b_{i_0,u}^{-1}$ times $u$-th column block from $v$-th column block }
\For{$i\in \{0,1,\cdots,p-1\}$}{
$
b_{iv}\leftarrow b_{i,v}-b_{i_0,v}b_{i_0,u}^{-1}b_{i,u}
$
}
}
$I\leftarrow I-\{i_0\}$.\\
$u\leftarrow u+1$.
}
\end{algorithm}

Let $(\sigma_0,\sigma_1,\cdots,\sigma_{p-1})$ be the order of indices that
Algorithm~\ref{algorithm-elimination} uses.
Then we have the following properties.
\begin{claim}\label{lem-elimination-new}
At the end of Algorithm 2 we have
\begin{itemize}
\item $b_{\sigma_i ,j}=0$ for $j=i+1,\cdots,p-1$ and
\item $b_{\sigma_i ,i}\neq 0$.
\end{itemize}
\end{claim}

The proof of Claim~\ref{lem-elimination-new} is very similar to that of Claim~\ref{lem-elimination} and we omit it here.
After the elimination,
the matrix is of the form:
\begin{center}
\begin{tabular}{ c|c|c|c|c|c }
& $\monomialle{p}{d}{\sampledim-t} $ &$x_{t}\cdot \monomialle{p}{d-1}{\sampledim-t}$ &$x_{t}^2\cdot \monomialle{p}{d-2}{\sampledim-t}$&$\cdots$ & $x_{t}^{p-1}\cdot  \monomialle{p}{d-p+1}{\sampledim-t}$\\
\hline
 $S_{\sigma_0}$ & $b_{\sigma_0,0}\cdot A_{\leq p-1}^{(\sigma_0)}$ & $0$ & $0$ & $\cdots$ & $0$  \\
 \hline
   $S_{\sigma_1}$ &  & $b_{\sigma_1,1}\cdot A_{\leq p-2}^{(\sigma_1)}$ & 0 & $\cdots$ & 0  \\
 \hline
   $S_{\sigma_2}$ &  & & $b_{\sigma_2,2}\cdot A_{\leq p-3}^{(\sigma_2)}$ & $\cdots$ & 0  \\
 \hline
 \vdots & \vdots &\vdots & \vdots & \vdots &\vdots\\
 \hline

  $S_{\sigma_{p-1}}$ &&  &  & $\cdots$ & $b_{\sigma_{p-1},(p-1)}\cdot A_{\leq 0}^{(\sigma_{p-1})}$\\
 \hline
\end{tabular}
\end{center}
Since it is a triangular matrix,
we can lower bound its rank as
\[
\sum_{i=0}^{p-1}rank(A_{\leq p-1-i}^{(\sigma_i)}).
\]
Recall that  columns of $A_{\leq p-1-i}^{(\sigma_i)}$ are $\monomialle{p}{d-i}{\sampledim-t}$,
so $A_{\leq p-1-i}^{(\sigma_i)}$ is actually $M^{(d-i)}_{S_{\sigma_i}}$.
Since $|S_{\sigma_i}|<|S|$,
 we can apply the induction hypothesis to get
\[
rank(M^{(d-i)}_{S_{\sigma_i}})\geq g_{d-i}(|S_{\sigma_i}|).
\]
Now we can apply Lemma \ref{lem-main} to get
\[
rank(M^{(d)}_S)\geq \sum_{i=0}^{p-1}g_{d-i}(|S_{\sigma_i}|)\geq g_d(\sum_{i=0}^{p-1}|S_{\sigma_i}|)=g_d(\iterator)
\]
as required.
\end{proof}

Therefore to complete our proof of the extremal rank properties of these matrices
in Theorem~\ref{rank-result}, and hence Theorem{thm:main-extremal} and Lemma~\ref{prop:evaluation-rank}, it only remains to prove the sub-additivity property of Lemma~\ref{lem-main} for the $g_d$ function.

config: arxiv


TITLE: $f$ is a non-constant polynomial, $A $ is a set of measure zero, Is this true that $m(f^{-1}A)=0$, where $m$ stands for the Lebesgue measure.
QUESTION [11 upvotes]: Let $f$ be a non-constant polynomial, and let $A \subset \mathbb{R}$ be a set of measure zero, Is this true that $m(f^{-1}A)=0$, where $m$ stands for the Lebesgue measure.
If $A$ is a countable set, it is easy to see that $Cardinality (f^{-1}A) \leq Cardinality (\mathbb{N} * \mathbb{N})$ and it means that $m(f^{-1}A)=0$.
My problem in proving that this is true, is sets like Cantor set, whose measure is zero but is uncountable.
Any hints or ideas is appreciated. Thanks !

REPLY [3 votes]: following @AlexBecker idea :
Suppose $f$ is a polynomial of degree $n$, so it has at most $n-1$ pieces, each of which is monotone. Partition $E$ such that $E=E_1 \cup E_2 \cup ... \cup E_{n-1}$ such that $f$ restricted to each $E_k$ is (strictly) monotone. We can say $$f=f|_{E_1}+f|_{E_2}+...+f|_{E_{n-1}}$$
Therefore we have : $$f^{-1}A=(f|_{E_1})^{-1}A \ \bigsqcup \ (f|_{E_2})^{-1}A \ \bigsqcup \ ... \bigsqcup \ (f|_{E_{n-1}})^{-1}A \ $$
If I show that for each $1 \leq k \leq n-1 $ the set $C_k=(f|_{E_{k}})^{-1}A$ has zero measure, we are done.
Suppose that's not the case, i.e. $mC_k=r_k>0$, and note that since $f|_{E_{k}}$ is strictly monotone on $E_k$, we can find $m_k>0$ (monotone increasing) or $m_k<0$ (monotone decreasing) such that $f'(x) \geq m_k$ for all $x \in E_k$. Therefore we have that $$|m_k| \leq \frac{m \left[f|_{E_{k}}C_k \right]}{m C_k} \Longrightarrow 0 < r_km_k \leq  m \left[f|_{E_{k}} C_k \right] \leq mA \ \ \ (by \ \ Monotonicity)$$
A contradiction. Therefore $$mf^{-1}A=m(f|_{E_1})^{-1}A \ + \ m(f|_{E_2})^{-1}A \ + \ ... + \ m(f|_{E_{n-1}})^{-1}A \ = 0 + 0 + ... + 0 = 0 $$


TITLE: Partitioning a set of rectangles into disjoint subsets each of which consists of disjoint rectangles
QUESTION [3 upvotes]: Suppose we have a list $R$ of axis-aligned rectangles in the plane. There is the well-known problem of determining the maximum subset of $R$ which consists of disjoint rectangles; this problem is known to be NP-hard. There are reasonably efficient algorithms, however, for finding approximations to the maximal independent subset; e.g., see this paper.
I have a twist on this problem. I don't need the maximal independent subset or even a single approximation to it. Rather, I need a list of subsets $R_1,R_2,\dots,R_k$, each of which consists of disjoint rectangles, such that $R_1\cup R_2\cup\dots\cup R_k = R$. It is not necessary that the sets $R_1,\dots,R_k$ themselves be disjoint, though in an ideal solution they would be. I want to find such a list as quickly as possible, with the additional optimization constraint that each individual list should be large (so as to rule out the trivial solution where each list consists of a single rectangle).
If you're curious about the motivation of this problem, it arises in cartography when one wishes to dynamically label a map: each set of labelings corresponds to a set $R_i$ above, and the interactive map cycles through the label sets $R_i$ over time so that all labels are guaranteed to be displayed.

REPLY [1 votes]: Another formulation of your problem: you have a (not neccessarily planar) graph (its vertices are your rectangles and two vertices are connected by an edge if these rectangles overlap) and are looking for a coloring of its vertices (each color being one of your subsets $R_i$) using a low but not neccessarily minimal number of colors.
There exist various algorithms for this, with different tradeoffs between speed and quality of the result. There is also plenty of papers written on this subject. The Algorithm Design Manual by Skiena suggests http://webdocs.cs.ualberta.ca/~joe/Coloring/ and http://mat.gsia.cmu.edu/COLOR/color.html as useful resources, and also gives help in choosing an algorithm as well as an overview of existing implementations. Among these implementations are GraphCol and GOBLIN. It also has plenty of suggestions for further reading.


TITLE: Gaussian elimination number of iteration
QUESTION [1 upvotes]: If $ A $ is an $ n \times n $ matrix and suppose we want to solve $ Ax = b $ using Gaussian elimination. The runtime complexity for Gaussian elimination is $ O(n^3), $ but what is the approximate number of iterations required to perform the algorithm?

REPLY [2 votes]: It depends on what you call an iteration.  Wikipedia says

The number of arithmetic operations required to perform row reduction is one way of measuring the algorithm's computational efficiency. For example, to solve a system of $n$ equations for $n$ unknowns by performing row operations on the matrix until it is in echelon form, and then solving for each unknown in reverse order, requires $\frac{n(n+1)}{2}$ divisions, $\frac{2n^3 + 3n^2 − 5n}{6}$ multiplications, and $\frac{2n^3 + 3n^2 − 5n}{6}$ subtractions, for a total of approximately $\frac{2n^3}{3}$ operations.

REPLY [0 votes]: It indeed does depend on what you consider an iteration because because an iteration can be 1) reduce the rest of the sub-matrix, 2) reduce the following row, or 3) reduce the current matrix element.
If an "iteration" is reducing a single row, then there are $(n-1) + (n - 2) + (n - 3)... \approx O(n^2)$ iterations.  If an iteration is reducing a sub-matrix then there are $n - 1 \approx O(n)$.


TITLE: Are electrons really elementary particles?
QUESTION [1 upvotes]: I know that physicist do accept that fact as "an assumption", or "as a fact" due to "proofs" (or missing unroof).
But are electrons really to be considered as elementary particles?

REPLY [1 votes]: At this time the question about is the electron a composed particle has to be more a theoretical than a experimental contemplation. We haven't the tools or perhaps we are not willing to make such experiments. Fact is that your question seems not to interesting science at the moment. But the question is serious and very legitim. To accelerate an electron you need the interaction with photons. During positive acceleration the electron "consumes" the photons momentum (mostly partially and sometime full) and during negative acceleration it emits photons.
We know else that the electron has both a electric field and a magnetic dipole moment (a magnetic field) and that photons have a oscillating electric and an oscillating magnetic field. Furthermore the photons, accelerating the electron, shielding the electron's electric field. On the other side, during the interaction of an electron with the nucleus the electron emit photons and seems to stay without his electric field. It is not illegitimate to suppose that the electrons electric field nearby the nucleus is weakened. Have a look on my paper about composed particles and the one about magnetic dipole moments of the electron orbits.


TITLE: Limit of $x^x$ without L'Hôpital
QUESTION [2 upvotes]: I was trying to calculate $\lim_{x \to 0^{+}} x^x$ without L'Hôpital's rule but could not make progress.
My best shot was to show that $\lim_{x \to 0^{+}} x\ln x = 0$ as that would imply the first limit.
Can anyone help me?

REPLY [1 votes]: Consider $A=x^x$. Taking logarithms $\log(A)=x\log(x)$ which goes to $0$ if $x\to 0$. So $\log(A)\to 0 \implies A \to 1$.


text:
\begin{document}

\title[Dimension variation for Drinfeld cuspforms of level $\Gamma_1(t)$]{Dimension variation of Gouv\^{e}a-Mazur type
for Drinfeld cuspforms of level $\Gamma_1(t)$}
\author{Shin Hattori}
\address[Shin Hattori]{Department of Natural Sciences, Tokyo City University}

\date{\today}

\begin{abstract}
Let $p$ be a rational prime and $q>1$ a $p$-power. Let $S_k(\Gamma_1(t))$ be the space of Drinfeld cuspforms of level $\Gamma_1(t)$ and weight $k$ for $\bF_q[t]$. For any non-negative rational number $\alpha$, we denote by $d(k,\alpha)$ the dimension of the slope $\alpha$ generalized eigenspace for the $U$-operator acting on $S_k(\Gamma_1(t))$. In this paper, we prove a function field analogue of the Gouv\^{e}a-Mazur conjecture for this setting. Namely, we show that for any $\alpha\leq m$ and $k_1,k_2>\alpha+1$, if $k_1\equiv k_2 \bmod p^m$, then $d(k_1,\alpha)=d(k_2,\alpha)$.
\end{abstract}

\maketitle

\section{Introduction}

Let $p$ be a rational prime, $q>1$ a $p$-power, $A=\bF_q[t]$ and $\wp\in A$ a monic irreducible polynomial. For
$K_\infty=\bF_q((1/t))$, we denote by $\bC_\infty$ the $(1/t)$-adic completion of an algebraic closure of $K_\infty$.
Then the Drinfeld upper half plane $\Omega=\bC_\infty\setminus K_\infty$ has a natural structure of a rigid analytic
variety over
$K_\infty$.

Let $k$ be an integer and $\Gamma$ a subgroup of $\mathit{SL}_2(A)$. Then a Drinfeld modular form of level
$\Gamma$ and weight $k$ is a rigid analytic function $f:\Omega\to \bC_\infty$ satisfying
\[
f\left(\frac{az+b}{cz+d} \right)=(cz+d)^kf(z)\text{ for any }z\in \Omega,\ \begin{pmatrix}
a&b\\c&d
\end{pmatrix} \in \Gamma
\]
and a holomorphy condition at cusps.
The notion of Drinfeld modular form can be considered as a function field analogue of that of elliptic modular form and
the former often has properties which are parallel to the latter. However, despite that the theory of $p$-adic families
of elliptic modular forms is highly developed and has been yielding many applications, $\wp$-adic properties of
Drinfeld modular forms are not well-understood yet. A typical difficulty in the Drinfeld case seems that a na\"{i}ve
analogue of the universal character $\bZ_p^\times\to \bZ_p[[\bZ_p^\times]]^\times$ is not locally analytic by
\cite[Lemma
2.5]{Jeong} and thus similar constructions to those in the classical case including \cite{AIP-SMF} will not immediately produce an analytic family of invertible sheaves interpolating automorphic line bundles.

Still, there seem to exist interesting structures in $\wp$-adic properties of Drinfeld modular forms. In \cite{BV1,
BV0}, Bandini-Valentino studied an analogue of the classical Atkin $U$-operator, which we also denote by $U$, acting on
the space $S_k(\Gamma_1(t))$ of Drinfeld cuspforms of level $\Gamma_1(t)$ and weight $k$. The operator $U$ is defined by
\begin{equation}\label{EqnDefU}
(Uf)(z)=\frac{1}{t}\sum_{\beta\in \bF_q}f\left(\frac{z+\beta}{t}\right).
\end{equation}
The normalized $t$-adic valuation of an eigenvalue of $U$ is called slope. Note that here we adopt the different
normalization from that of Bandini-Valentino, and as a result our notion of slope is smaller than theirs by one.
For a non-negative rational number $\alpha$, we denote by $d(k,\alpha)$ the dimension of the generalized eigenspace of
$U$ acting on $S_k(\Gamma_1(t))$ for the eigenvalues of slope $\alpha$. Then they proposed a conjecture on a $p$-adic
variation of $d(k,\alpha)$ with respect to $k$ \cite[Conjecture 6.1]{BV0} which can be regarded as a function field
analogue of the Gouv\^{e}a-Mazur conjecture \cite[Conjecture 1]{GM}. In this paper, we will prove it.

\begin{thm}(Theorem \ref{Main})\label{MainIntro}
	Let $m\geq 0$ be an integer and $\alpha$ a non-negative rational number. Suppose $\alpha\leq m$. Then the dimension $d(k,\alpha)$ of the slope $\alpha$ generalized eigenspace in $S_k(\Gamma_1(t))$ satisfies
	\[
	k_1,k_2> \alpha+1,\ k_1\equiv k_2\bmod p^m\Rightarrow d(k_1,\alpha)=d(k_2,\alpha).
	\]
	\end{thm}

For the proof, put
\[
P^{(k)}(X)=\det(I-XU\mid S_k(\Gamma_1(t))).
\]
First note that, as is mentioned in \cite[\S4, Remarks]{Wan}, the arguments of \cite{GMU} and \cite{Wan}
can be generalized over suitable Drinfeld modular curves (including $X^\Delta_1(\frn)$ of \cite{Ha_DMC}). In
particular, the characteristic power series of $U$ acting on the spaces of $\wp$-adic overconvergent Drinfeld modular
forms of weight $k_1$ and $k_2$ are congruent modulo $\wp^{p^m}$. Also in our setting, we can show the
congruence $P^{(k_1)}(X)\equiv P^{(k_2)}(X)\bmod t^{p^m}$ up to some factor. However, though with this we can prove
Theorem
\ref{MainIntro} for $p\geq 3$, it is not enough to settle the case of $p=2$ on which Bandini-Valentino stated
their conjecture.

Instead, we investigate the formula of the representing matrix of $U$ given by Bandini-Valentino \cite[(3.1)]{BV1} more closely.
Luckily, the representing matrix is of very special form: each entry on the $j$-th column (with the normalization that the
leftmost column is the zeroth) is an element of $\bF_q t^{j}$. Thanks to this fact, we can give a lower bound of
elementary divisors of the representing matrix (Lemma \ref{LemGliss}). Then a perturbation argument shows that the
$n$-th coefficients of $P^{(k)}(X)$
and $P^{(k+p^m)}(X)$ are much more congruent than modulo $t^{p^m}$ up to some factor of slope $\geq k-1$ (Corollary
\ref{Perturb}), which is enough to yield Theorem
\ref{MainIntro} for any $p$.

\subsection*{Acknowledgments} The author would like to thank Gebhard B\"{o}ckle for informing him of Valentino's table
computing characteristic polynomials of $U$, and Maria Valentino for pointing out an error in the author's previous
computer calculation. This work was supported by JSPS KAKENHI Grant Number JP17K05177.

\section{Dimension variation}

Let $k\geq 2$ be an integer. Put
\[
\Gamma_1(t)=\left\{\gamma\in \mathit{GL}_2(A)\ \middle|\ \gamma\equiv \begin{pmatrix}1&*\\0&1\end{pmatrix}\bmod
t\right\}\subseteq \mathit{SL}_2(A).
\]
On the space $S_k(\Gamma_1(t))$ of Drinfeld cuspforms of level $\Gamma_1(t)$ and weight $k$, we consider the
$U$-operator for $t$ defined by (\ref{EqnDefU}).
Note that we follow the usual normalization of the $U$-operator which differs from that of \cite[\S 2.4]{BV1} by $1/t$. Then Bandini-Valentino \cite[(3.1)]{BV1} explicitly describe the action of $U$ with respect to some basis $\mathbf{c}_0^{(k)},\ldots, \mathbf{c}_{k-2}^{(k)}$, which reads as follows with our normalization:

\begin{equation}\label{EqnBV}
\begin{split}
U(\mathbf{c}_j^{(k)})=&(-t)^j\tbinom{k-2-j}{j}\mathbf{c}_j^{(k)}-t^j\sum_{h\in \bZ, h\neq 0}\left\{\tbinom{k-2-j-h(q-1)}{-h(q-1)}\right.\\
&\left.+(-1)^{j+1}\tbinom{k-2-j-h(q-1)}{j} \right\}\mathbf{c}_{j+h(q-1)}^{(k)}.
\end{split}
\end{equation}
Here it is understood that the binomial coefficient $\binom{c}{d}$ is zero if any of $c,d,c-d$ is negative and the
terms involving $\mathbf{c}_{j+h(q-1)}^{(k)}$ are zero if $j+h(q-1)\notin
[0,k-2]$. We denote by $U^{(k)}=(U^{(k)}_{i,j})_{0\leq i,j\leq k-2}$ the representing matrix of $U$ for this basis.
Then we have $U^{(k)}\in M_{k-1}(A)$. We identify the $t$-adic completion of $A$ with $\bF_q[[t]]$ naturally and
consider $U^{(k)}$ as an element of $M_{k-1}(\bF_q[[t]])$.

\begin{dfn}\label{DefGliss}
Let $B=(B_{i,j})_{0\leq i\leq m-1,0\leq j\leq n-1}$ be an element of $M_{m,n}(\bF_q[[t]])$. We say $B$ is glissando if $B_{i,j}\in \bF_q t^{j}$ for any $i,j$.
\end{dfn}

By (\ref{EqnBV}), the matrix $U^{(k)}$ is glissando.

\begin{lem}\label{LemGliss}
	Let $B=(B_{i,j})_{0\leq i\leq m-1,0\leq j\leq n-1}$ be a glissando matrix in $M_{m,n}(\bF_q[[t]])$. Let $s_1\leq
	s_2\leq\cdots \leq s_{r}$ be the elementary divisors of $B$ (namely, they are integers or $+\infty$ such that
	$t^{s_i}$ is the $(i-1,i-1)$-entry of the Smith normal form of $B$). Then we have $s_l\geq l-1$ for any $l$.
	\end{lem}
\begin{proof}
	We prove the lemma by induction on $n$. For $n=1$, we have $s_1=0$ if $B\neq O$ and $s_1=+\infty$ otherwise. For
	$n>1$, we may assume $B\neq O$ and let $c$ be the integer with $0\leq c\leq n-1$ such that the leftmost non-zero column
	of $B$ is the $c$-th one. Since $B$ is glissando, the first elementary divisor of $B$ is $c\geq 0$ and the rest are
	equal to the elementary divisors of a matrix $t^{c+1} B'$, where $B'$ is also glissando with $n-1$ columns. Let
	$s'_1\leq \cdots\leq s'_{r'}$ be the elementary divisors of $B'$. By the induction hypothesis, we have $s'_l\geq
	l-1$ and thus $s_l=c+1+s'_{l-1}\geq  l-1$ for $l\geq 2$. This concludes the proof.
	\end{proof}

Let $v_t$ be the $t$-adic additive valuation normalized as $v_t(t)=1$. For any element $P(X)=\sum_{n=0}^\infty p_n X^n\in \bF_q[[t]][[X]]$, the Newton polygon of $P(X)$ is by definition the lower convex hull of the set
\[
\{(n,v_t(p_n))\mid n\geq 0\}.
\]

\begin{lem}\label{LemGlissSlope}
	Let $B\in M_m(\bF_q[[t]])$ be a glissando matrix. For any non-negative integer $l$, put
	\[
	P(X)=\det(I-t^l XB)=\sum_{n=0}^m p_n X^n\in \bF_q[[t]][X].
	\]
	\begin{enumerate}
		\item\label{LemGlissSlope-n} $v_t(p_n)\geq ln+\frac{1}{2}n(n-1)$.
		\item\label{LemGlissSlope-s} Any slope of the Newton polygon of $P(X)$ is no less than $l$.
	\end{enumerate}
	\end{lem}
\begin{proof}
	First note that, for the characteristic polynomial
	$Q(X)=\det (XI-t^l B)$, we have $P(X)=X^{m} Q(X^{-1})$ and thus $p_n$ is, up to a sign,
	equal to the sum of the principal $n\times n$ minors of $t^l B$. Since $B$ is glissando, this shows (\ref{LemGlissSlope-n}). Since $p_0=1$, the resulting inequality $v_t(p_n)\geq ln$ implies (\ref{LemGlissSlope-s}).
	\end{proof}

Now we put
\[
P^{(k)}(X)=\det(I-XU^{(k)})=\sum_{n=0}^{k-1} a_n^{(k)} X^n
\]
and $a_n^{(k)}=0$ for any $n\geq k$.
Let $y=N^{(k)}(x)$ be the Newton polygon of $P^{(k)}(X)$. For any non-negative rational number $\alpha$, we denote by $d(k,\alpha)$ the dimension of the generalized
eigenspace for the eigenvalues of normalized $t$-adic valuation $\alpha$. Then $d(k,\alpha)$ is equal to the width of
the segment of slope $\alpha$ in the Newton polygon $N^{(k)}$.

\begin{lem}\label{LemOrd}
	$d(k,0)=1$.
	\end{lem}
\begin{proof}
	By (\ref{EqnBV}), we have $U^{(k)}_{0,0}=\binom{k-2}{0}=1$. On the other hand, since $U^{(k)}$ is glissando, we have $v_t(U^{(k)}_{i,j})\geq j$ and
	\[
	a_1^{(k)}=-\sum_{j=0}^{k-2} U^{(k)}_{j,j}\equiv -1\bmod t.
	\]
	Moreover, from Lemma \ref{LemGlissSlope} (\ref{LemGlissSlope-n}) we obtain $v_t(a_n^{(k)})>0$ for any $n\geq 2$. This yields the lemma.
	\end{proof}

\begin{lem}\label{binomp}
	Let $a$ and $b$ be non-negative integers. Let $m\geq 1$ be an integer. Then we have
	\[
	\tbinom{a+p^m}{b}\equiv \tbinom{a}{b}+\tbinom{a}{b-p^m} \bmod p.
	\]
	Here it is understood that $\binom{c}{d}=0$ if any of $c,d,c-d$ is negative.
	\end{lem}
\begin{proof}
	This follows from
	\[
	(X+1)^{a+p^m}\equiv (X+1)^a(X^{p^m}+1)\bmod p.
	\]
	\end{proof}

\begin{prop}\label{UMod}
	Let $m\geq 1$ be an integer. Then there exist glissando matrices $C\in M_{p^m,k-1}(A)$ and $D\in M_{p^m,p^m-k+1}(A)$ satisfying
	\[
	U^{(k+p^m)}\equiv \left(\begin{array}{c|c|c}U^{(k)} & O & O \\ C & t^{k-1} D& O\end{array}\right) \bmod t^{p^m}.
	\]
	Here it is understood that the middle blocks are empty if $p^m\leq k-1$.
	\end{prop}
\begin{proof}
	Let $j$ be an integer satisfying $0\leq j\leq k+p^m-2$. By (\ref{EqnBV}), the element $U(\mathbf{c}_j^{(k+p^m)})$ is equal to
	\begin{align*}
	(&-t)^j\tbinom{k+p^m-2-j}{j}\mathbf{c}_{j}^{(k+p^m)}\\
	&-t^j\sum_{h\in \bZ, h\neq 0}\left\{\tbinom{k+p^m-2-j-h(q-1)}{-h(q-1)}+(-1)^{j+1}\tbinom{k+p^m-2-j-h(q-1)}{j} \right\}\mathbf{c}_{j+h(q-1)}^{(k+p^m)}.
	\end{align*}

	Note that both of $U^{(k+p^m)}_{i,j}$ and $U^{(k)}_{i,j}$ are divisible by $t^{p^m}$ for $j\geq p^m$. Since $U^{(k+p^m)}$ is glissando, what we need to show is
	\begin{enumerate}
		\item\label{UModSmall} For any $j \leq \min\{k-2,p^m-1\}$ and $i\in [0,k-2]$, we have $U^{(k+p^m)}_{i,j}=U^{(k)}_{i,j}$, and
		\item\label{UModMiddle} If $k\leq p^m$, then for any $j\in [k-1,p^m-1]$ and $i\in [0,k-2]$, we have $U^{(k+p^m)}_{i,j}=0$.
		\end{enumerate}

	First we suppose $j\leq \min\{k-2,p^m-1\}$. By Lemma \ref{binomp}, the element $U(\mathbf{c}_j^{(k+p^m)})$ equals
	\begin{align*}
	&(-t)^j\left(\tbinom{k-2-j}{j}+\tbinom{k-2-j}{j-p^m}\right)\mathbf{c}_{j}^{(k+p^m)}\\
	&-t^j\sum_{\substack{h\in \bZ, h\neq 0\\j+h(q-1)\in [0,k-2]}}\left\{\tbinom{k-2-j-h(q-1)}{-h(q-1)}+\tbinom{k-2-j-h(q-1)}{-h(q-1)-p^m}\right.\\
	&\left.+(-1)^{j+1}\left(\tbinom{k-2-j-h(q-1)}{j}+ \tbinom{k-2-j-h(q-1)}{j-p^m}\right)\right\}\mathbf{c}_{j+h(q-1)}^{(k+p^m)}\\
	&-t^j\sum_{\substack{h\in \bZ, h\neq 0\\j+h(q-1)\geq k-1}}\left\{\tbinom{k+p^m-2-j-h(q-1)}{-h(q-1)}+(-1)^{j+1}\tbinom{k+p^m-2-j-h(q-1)}{j}\right\}\mathbf{c}_{j+h(q-1)}^{(k+p^m)}.\\
	\end{align*}
	Hence $U(\mathbf{c}_j^{(k+p^m)})$ agrees with
	\begin{align*}
	&\sum_{i=0}^{k-2}U^{(k)}_{i,j}\mathbf{c}_i^{(k+p^m)}+(-t)^j\tbinom{k-2-j}{j-p^m}\mathbf{c}_{j}^{(k+p^m)}\\
	&-t^j\sum_{\substack{h\in \bZ, h\neq 0\\j+h(q-1)\in [0,k-2]}}\left\{\tbinom{k-2-j-h(q-1)}{-h(q-1)-p^m}+(-1)^{j+1}\tbinom{k-2-j-h(q-1)}{j-p^m}\right\}\mathbf{c}_{j+h(q-1)}^{(k+p^m)}\\
	&-t^j\sum_{\substack{h\in \bZ, h\neq 0\\j+h(q-1)\geq k-1}}\left\{\tbinom{k+p^m-2-j-h(q-1)}{-h(q-1)}+(-1)^{j+1}\tbinom{k+p^m-2-j-h(q-1)}{j}\right\}\mathbf{c}_{j+h(q-1)}^{(k+p^m)}.\\
	\end{align*}

	Since $j<p^m$, we have $\binom{k-2-j}{j-p^m}=0$. For the case of $j+h(q-1)\in [0,k-2]$, we also have
	$-h(q-1)-p^m\leq j-p^m<0$ and $\binom{k-2-j-h(q-1)}{-h(q-1)-p^m}=\binom{k-2-j-h(q-1)}{j-p^m}=0$. This proves (\ref{UModSmall}).

	Next we suppose $k\leq p^m$ and $j\in [k-1,p^m-1]$. For any $i\in [0,k-2]$, the element $U^{(k+p^m)}_{i,j}$ is equal to
	\[
	-t^j\left\{\tbinom{k+p^m-2-j-h(q-1)}{-h(q-1)}+(-1)^{j+1}\tbinom{k+p^m-2-j-h(q-1)}{j}\right\}
	\]
	if we can write $i=j+h(q-1)$ with some $h\neq 0$, and zero otherwise. Since $i\leq k-2$, we have $k-2-j-h(q-1)\geq 0$ and Lemma \ref{binomp} implies
	\begin{align*}
	\tbinom{k-2-j-h(q-1)+p^m}{-h(q-1)}&=\tbinom{k-2-j-h(q-1)}{-h(q-1)}+\tbinom{k-2-j-h(q-1)}{-h(q-1)-p^m},\\
	\tbinom{k-2-j-h(q-1)+p^m}{j}&=\tbinom{k-2-j-h(q-1)}{j}+\tbinom{k-2-j-h(q-1)}{j-p^m}.
	\end{align*}
	Since $i=j+h(q-1)\in [0,k-2]$ and $j<p^m$, we have
	$\binom{k-2-j-h(q-1)}{-h(q-1)-p^m}=\binom{k-2-j-h(q-1)}{j-p^m}=0$ as is seen above. Since $j\geq k-1$, we also have
	$\binom{k-2-j-h(q-1)}{-h(q-1)}=\binom{k-2-j-h(q-1)}{j}=0$. This proves (\ref{UModMiddle}) and the proposition follows.
\end{proof}

Let $V\in M_{k+p^m-1}(A)$ be the matrix of the right-hand side of Proposition \ref{UMod}. Let $D'$ be the upper $(p^m-k+1)\times (p^m-k+1)$ block of $D$ if $k\leq p^m$ and $D'=O$ otherwise. Then $D'$ is also glissando. Put
\[
\tilde{P}(X)=\det(I-XV)=P^{(k)}(X)\det(I-t^{k-1}XD')
\]
and write $\tilde{P}(X)=\sum_{n=0}^{k+p^m-1} \tilde{a}_n X^n$. We denote by $\tilde{N}$ the Newton polygon of $\tilde{P}(X)$.

\begin{cor}\label{Perturb}
	Let $m$ and $n$ be integers satisfying $m\geq 1$ and $0\leq n\leq k+p^m-1$. Then we have
	\[
	v_t(a_n^{(k+p^m)}-\tilde{a}_n)\geq p^m+\sum_{l=1}^{n-1}\min\{l-1, p^m\}.
	\]
	\end{cor}
\begin{proof}
Write
\[
U^{(k+p^m)}=V+t^{p^m} W
\]
with some $W\in M_{k+p^m-1}(A)$. Let $s_1\leq\cdots\leq s_{k+p^m-1}$ be the
elementary
divisors of $V$. Since $V$ is glissando, by Lemma \ref{LemGliss} we obtain $s_l\geq l-1$ for any $l$. Then \cite[Theorem
4.4.2]{Ked} shows
\[
v_t(a_n^{(k+p^m)}-\tilde{a}_n)\geq p^m+\sum_{l=1}^{n-1}\min\{s_l, p^m\}\geq p^m+\sum_{l=1}^{n-1}\min\{l-1, p^m\}.
\]
\end{proof}

\begin{lem}\label{LemNum}
	Let $m$ and $n$ be integers satisfying $m \geq 1$ and $n\geq 2$. Then we have
	\[
	p^m+\sum_{l=1}^{n-1}\min\{l-1, p^m\}>m(n-1).
	\]
	\end{lem}
\begin{proof}
	First we assume $n-2\geq p^m$. Then the left-hand side of the lemma is equal to
	\begin{equation}\label{EqnLarge}
	p^m+\sum_{l=1}^{p^m+1}(l-1)+\sum_{l=p^m+2}^{n-1} p^m=\frac{1}{2}p^m(p^m+3)+p^m(n-2-p^m).
	\end{equation}
	For $m\geq 1$, we have $\frac{1}{2}p^m\geq m$ and thus $\frac{1}{2}p^m(p^m+3)\geq m(p^m+2)$. Hence the right-hand side of (\ref{EqnLarge}) is greater than $m(n-1)$.

	Next we assume $n-2< p^m$. In this case, the left-hand side of the lemma equals $p^m+\frac{1}{2}(n-1)(n-2)$. It is greater than $m(n-1)$ if and only if
	\[
	\left(n-\left(m+\frac{3}{2}\right)\right)^2+2p^m-m(m+1)-\frac{1}{4}> 0.
	\]
	Since $m$ and $n$ are integers, the first term is no less than $\frac{1}{4}$. Since we can show $2p^m>m(m+1)$ for any $p$ and $m\geq 1$, the lemma follows also for this case.
	\end{proof}

\begin{lem}\label{LemWindow}
	The part of the Newton polygon $\tilde{N}$ of $\tilde{P}(X)$ of slope less than $k-1$ agrees with that of $N^{(k)}$.
	\end{lem}
\begin{proof}
	For any $Q(X)\in \bF_q[[t]][X]$ and any non-negative rational number $\alpha$, the Newton polygon of $Q(X)$ has a
	segment of slope $\alpha$ and width $l$ if and only if it has exactly $l$ roots of normalized $t$-adic
	valuation $-\alpha$. By Lemma \ref{LemGlissSlope} (\ref{LemGlissSlope-s}), every root of the polynomial
	$\det(I-t^{k-1}XD')$ has normalized $t$-adic valuation no more than $-(k-1)$. Thus, for $\tilde{P}(X)$ and
	$P^{(k)}(X)$, the sets of roots of normalized $t$-adic valuation more than $-(k-1)$ agree including
	multiplicities. This shows the lemma.
\end{proof}

\begin{thm}\label{Main}
	Let $k$ and $m$ be integers satisfying $k\geq 2$ and $m\geq 0$. Let $\alpha$ be a non-negative rational number satisfying $\alpha\leq m$ and $\alpha< k-1$. Then we have $d(k+p^m,\alpha)=d(k,\alpha)$.
	\end{thm}
\begin{proof}
	Let $\{\alpha_1,\ldots,\alpha_N\}$ be the set of slopes of the Newton polygons $N^{(k+p^m)}$ and $N^{(k)}$ which is no more than $m$ and less than $k-1$, and renumber them so that $\alpha_i< \alpha_{i+1}$ for any $i$. We proceed by induction, following the proof of \cite[Lemma 4.1]{Wan}. By Lemma \ref{LemOrd}, we have $\alpha_1=0$ and $d(k+p^m,0)=d(k,0)=1$. Thus we may assume $m\geq 1$ and $N\geq 2$.

	Suppose that for some $r\leq N-1$, the equality $d(k+p^m,\alpha_i)=d(k,\alpha_i)$ holds for any $i$ satisfying $1\leq i\leq r$. By Lemma \ref{LemWindow}, this means that the Newton polygons $N^{(k)}$, $N^{(k+p^m)}$ and $\tilde{N}$ agree with each other on the part of slope no more than $\alpha_r$. Put $\alpha=\alpha_{r+1}>\alpha_1=0$ and let us prove $d(k+p^m,\alpha)=d(k,\alpha)$. We choose $k'\in \{k,k+p^m\}$ such that the slope $\alpha$ occurs in $N^{(k')}$ and let $k''$ be the other. Let $\beta$ be the slope of $N^{(k'')}$ on the right of $\alpha_r$. Then $\beta\geq \alpha$.

	Let $(n,v_t(a_n^{(k')}))$ be the endpoint of the segment of $N^{(k')}$ of slope $\alpha$. Since the Newton polygon $N^{(k')}$ has a segment of slope zero, we have $n\geq 2$ and
	\[
	N^{(k')}(n)=v_t(a_n^{(k')})\leq \alpha (n-1)\leq m(n-1).
	\]
	Then Corollary \ref{Perturb} and Lemma \ref{LemNum} imply
	\begin{equation}\label{EqnDiff}
	v_t(a_n^{(k')})<v_t(a_n^{(k+p^m)}-\tilde{a}_n).
	\end{equation}

	If $k'=k$, then Lemma \ref{LemWindow} shows $v_t(a_n^{(k')})=v_t(a_n^{(k)})=v_t(\tilde{a}_n)$ and from (\ref{EqnDiff}) we obtain $v_t(a_n^{(k+p^m)})=v_t(\tilde{a}_n)=v_t(a_n^{(k)})$. This equality implies $\alpha=\beta$ and $d(k,\alpha)\leq d(k+p^m,\alpha)$. In particular, the slope $\alpha$ also occurs in $N^{(k+p^m)}$.

	If $k'=k+p^m$, then (\ref{EqnDiff}) gives $v_t(\tilde{a}_n)=v_t(a_n^{(k+p^m)})$. Let $\gamma$ be the slope of the
	Newton polygon $\tilde{N}$ on the right of $\alpha_r$. Then this equality implies $\gamma\leq \alpha<k-1$. By Lemma
	\ref{LemWindow}, we have $\beta=\gamma\leq \alpha$. Therefore, we have $\alpha=\beta=\gamma$ and the width of the
	segment of slope $\alpha$ in $\tilde{N}$ is no less than that in $N^{(k+p^m)}$. Thus Lemma \ref{LemWindow} again
	shows $d(k,\alpha)\geq d(k+p^m,\alpha)$. In particular, the slope $\alpha$ also occurs in
	$N^{(k)}$. Combining these two cases, we obtain $d(k,\alpha)=d(k+p^m,\alpha)$. This concludes the proof of Theorem
	\ref{Main}.
\end{proof}

\section{Remarks}

Computations using (\ref{EqnBV}) with Pari/GP indicate that the slopes appearing in $S_k(\Gamma_1(t))$ have some
patterns (see also \cite[\S6]{BV0}). The below is a table of the case $p=q=2$, where the bold numbers denote
multiplicities.

\begin{table}[h]
	\begin{center}
		\begin{tabular}{c|c}
			$k$&slopes\\\hline
			$2$& $0^{\mathbf{1}}$\\
			$3$& $0^{\mathbf{1}}, +\infty^{\mathbf{1}}$\\
			$4$& $0^{\mathbf{1}}, 1^{\mathbf{1}},+\infty^{\mathbf{1}}$\\
			$5$& $0^{\mathbf{1}}, \tfrac{3}{2}^{\mathbf{2}}, +\infty^{\mathbf{1}}$\\
			$6$& $0^{\mathbf{1}}, 1^{\mathbf{1}}, 2^{\mathbf{1}}, +\infty^{\mathbf{2}}$\\
			$7$& $0^{\mathbf{1}}, 2^{\mathbf{1}}, \tfrac{5}{2}^{\mathbf{2}}, +\infty^{\mathbf{2}}$\\
			$8$& $0^{\mathbf{1}}, 1^{\mathbf{1}}, 3^{\mathbf{3}}, +\infty^{\mathbf{2}}$\\
			$9$& $0^{\mathbf{1}}, \tfrac{3}{2}^{\mathbf{2}}, \tfrac{7}{2}^{\mathbf{2}}, +\infty^{\mathbf{3}}$\\
			$10$& $0^{\mathbf{1}}, 1^{\mathbf{1}}, 2^{\mathbf{1}}, 4^{\mathbf{3}}, +\infty^{\mathbf{3}}$\\
			$11$& $0^{\mathbf{1}}, 2^{\mathbf{1}}, 4^{\mathbf{1}}, \tfrac{9}{2}^{\mathbf{4}}, +\infty^{\mathbf{3}}$\\
			$12$& $0^{\mathbf{1}}, 1^{\mathbf{1}}, 3^{\mathbf{1}}, 4^{\mathbf{1}}, 5^{\mathbf{3}},
			+\infty^{\mathbf{4}}$\\
		\end{tabular}
		\begin{tabular}{c|c}
			$k$&slopes\\\hline
			$13$& $0^{\mathbf{1}}, \tfrac{3}{2}^{\mathbf{2}}, 4^{\mathbf{1}}, \tfrac{11}{2}^{\mathbf{4}},
			+\infty^{\mathbf{4}}$\\
			$14$& $0^{\mathbf{1}}, 1^{\mathbf{1}}, 2^{\mathbf{1}}, 5^{\mathbf{1}}, 6^{\mathbf{5}},
			+\infty^{\mathbf{4}}$\\
			$15$& $0^{\mathbf{1}}, 2^{\mathbf{1}}, \tfrac{5}{2}^{\mathbf{2}}, 6^{\mathbf{1}},
			\tfrac{13}{2}^{\mathbf{4}}, +\infty^{\mathbf{5}}$\\
			$16$& $0^{\mathbf{1}}, 1^{\mathbf{1}}, 3^{\mathbf{3}}, 7^{\mathbf{5}}, +\infty^{\mathbf{5}}$\\
			$17$& $0^{\mathbf{1}}, \tfrac{3}{2}^{\mathbf{2}}, \tfrac{7}{2}^{\mathbf{2}}, \tfrac{15}{2}^{\mathbf{6}},
			+\infty^{\mathbf{5}}$\\
			$18$& $0^{\mathbf{1}}, 1^{\mathbf{1}}, 2^{\mathbf{1}}, 4^{\mathbf{3}}, 8^{\mathbf{5}},
			+\infty^{\mathbf{6}}$\\
			$19$& $0^{\mathbf{1}}, 2^{\mathbf{1}}, 4^{\mathbf{1}}, \tfrac{9}{2}^{\mathbf{2}}, 8^{\mathbf{1}},
			\tfrac{17}{2}^{\mathbf{6}}, +\infty^{\mathbf{6}}$\\
			$20$& $0^{\mathbf{1}}, 1^{\mathbf{1}}, 3^{\mathbf{1}}, 4^{\mathbf{1}}, 5^{\mathbf{1}}, 8^{\mathbf{1}},
			9^{\mathbf{7}}, +\infty^{\mathbf{6}}$\\
			$21$& $0^{\mathbf{1}}, \tfrac{3}{2}^{\mathbf{2}}, 4^{\mathbf{1}}, \tfrac{11}{2}^{\mathbf{2}},
			8^{\mathbf{1}}, \tfrac{19}{2}^{\mathbf{6}}, +\infty^{\mathbf{7}}$\\
			$22$& $0^{\mathbf{1}}, 1^{\mathbf{1}}, 2^{\mathbf{1}}, 5^{\mathbf{1}}, 6^{\mathbf{1}}, 8^{\mathbf{1}},
			9^{\mathbf{1}}, 10^{\mathbf{7}}, +\infty^{\mathbf{7}}$\\
			$23$& $0^{\mathbf{1}}, 2^{\mathbf{1}}, \tfrac{5}{2}^{\mathbf{2}}, 6^{\mathbf{1}}, 8^{\mathbf{1}},
			10^{\mathbf{1}}, \tfrac{21}{2}^{\mathbf{8}}, +\infty^{\mathbf{7}}$\\
		\end{tabular}
	\end{center}
\end{table}

From the table, it seems that only small denominators are allowed for slopes: In the author's computation, as is already mentioned in \cite[\S1]{BV0}, the only
case a non-trivial denominator appears is the case of $p=2$ and the denominator is at most $2$. Moreover, it seems
likely that the finite slopes of $S_k(\Gamma_1(t))$ are less than $k-1$, and that for any $n$, the $n$-th smallest
finite slope of $S_k(\Gamma_1(t))$ is bounded independently of $k$ (say, by $q^{n-1}$). If the
latter observations hold in general, then combined with Theorem \ref{Main} it follows that for any $n$, the $n$-th
smallest
finite slopes of $S_k(\Gamma_1(t))$ are periodic of $p$-power period with respect to $k$ including multiplicities. For example, it
seems from the table that the third smallest finite slopes of $S_k(\Gamma_1(t))$ in the case of $p=q=2$ are the repetition of
\[
2^{\mathbf{1}}, \tfrac{5}{2}^{\mathbf{2}}, 3^{\mathbf{3}},\tfrac{7}{2}^{\mathbf{2}}, 2^{\mathbf{1}}, 4^{\mathbf{1}}, 3^{\mathbf{1}},4^{\mathbf{1}}.
\]
This could be thought of as a function field analogue of Emerton's theorem \cite{Emerton} which asserts that the minimal
slopes of $S_k(\Gamma_0(2))$ are periodic of period $8$.


TITLE: Calculate simple trajectory
QUESTION [0 upvotes]: I'm working with OpenGL developing a simple (very simple) game. I came across a problem with calculating a missile trajectory (unfortunately don't have many math skills).
I'm working with $x$, $y$ and $z$ coordinates. My target is set at coordinates $(40,40,0)$ and my missile launcher is at $(40,0,50)$ with a zero angle.
I'm discarding gravitational forces and other forces.
If my missile position was perpendicular to my target and with a zero angle, and an constant velocity, if I fire the missile, it would go at a given rate, decreasing is $z$ coordinate and stop at $z=0$.
My problem is if the missile is not perpendicular to the target and if it as an angle.
So my simple question is how can I calculate the trajectory, my target is set at some coordinates and my missile launcher at another coordinates and with some angle?

REPLY [1 votes]: I assume we fire directly at the target. Suppose the speed of the bullet is $v$. Then, at time $t$, the position of the bullet will be
\begin{align*}
x &= 40     \\
y &= 40vt/d        \\
z &= 50 - 50vt/d
\end{align*}
where $d = \sqrt{4100}$ is the distance between the launch site and the target. You can check that the bullet reaches the target when $t = d/v$.


text:
\section{Stability of Dynamic Modified-CS and CS-residual}
In Theorem \ref{modcsbnd} (Theorem \ref{csresbnd}), we bounded the modified-CS (CS-residual) error as a function of $|\Delta|$ and $|\Delta_e|$. The bound is small as long as $|\Delta|$ and $|\Delta_e|$ are small. The important question is: under what conditions on the measurement model,  will $|\tDelta_e|$, $|\tDelta|$ (and hence $|\Delta_e|$, $|\Delta|$) remain stable, i.e. remain bounded by a small value compared to the signal support size, at all times?

When measurements are noiseless and we use noiseless-modified-CS, the answer to the above is trivial since in that case $\Delta$ and $\Delta_e$ contain the additions and removals from the true support respectively. Thus, as long as the maximum number of support additions and removals satisfy the exact reconstruction condition, the  reconstruction error will be stable at zero at all times. But when measurements are noisy, $\Delta_t$ also contains the undetected part of the previous support, besides the new additions. Similarly for $\Delta_e$. Thus, there is a need to explicitly find conditions under which $|\Delta|$ and $|\Delta_e|$ remain bounded by a time-invariant small value at all times. This, in turn, will imply that the signal estimation error is small compared to the signal power at all times.

\subsection{Signal model for studying stability}
For studying stability, we need to assume a signal model. We assume a simple deterministic model that (a) allows equal and nonzero number of additions/removals from the support at every time, (b) allows a new coefficient magnitude to gradually increase from zero, at a rate $M/d$, for a duration, $d$, and finally reach a constant value, $M$, (c) allows coefficients to gradually decrease and become zero (get removed from support) at the same rate, and (d) has constant signal power and support size.

\begin{sigmodel} Assume the following.
\ben

\item At $t=0$, the support size is $S_0$. The support contains $2S_a$ elements each with magnitude $M/d,2M/d, \dots (d-1)M/d$, and $S_0-(2d-2)S_a$ elements with magnitude $M$.

\item At each $t>0$, $S_a$ coefficients get added to the support at magnitude $M/d$. Denote this set by $\Aset_t$.

\item At each $t>0$, $S_a$ coefficients which had magnitude $M/d$ at $t-1$ get removed from the support (magnitude becomes zero). Denote this set by $\Rset_t$.

\item At each $t>0$, the magnitude of $S_a$ coefficients which had magnitude $(j-1) M/d$ at $t-1$ increases to $jM/d$. This occurs for all $1 \le j \le d-1$.

\item At each $t>0$, the magnitude of $S_a$ coefficients which had magnitude $(j+1)M/d$ at $t-1$ decreases to $jM/d$. This occurs for all $1 \le j \le (d-1)$.

\een
\label{sigmod2}
\end{sigmodel}

From the above model, the size and composition of the support at any time is the same as that at $t=0$. The size is $|N_t|=S_0$ and $N_t$ consists of $(d-1)S_a$ increasing coefficients and $(d-1)S_a$ decreasing coefficients, and $S_0- (2d-2)S_a$ constant coefficients with magnitude $M$.

To understand the model better, let us define the following.
\bd
Define the following
\ben
\item $\Dset_{t}(j): = \{i: |x_{t,i}| = jM/d, \ |x_{t-1,i}| = (j+1)M/d \}$.
\item $\Iset_{t}(j): = \{i: |x_{t,i}| = jM/d, \ |x_{t-1,i}| = (j-1)M/d \}$.
\item Small coeff. set, $\Sset_t(j):= \{i:  0 < |x_{t,i}| < j M/d \}$.
\item Newly added set, $\Aset_t:= \Iset_t(1)$.
\item Newly removed set, $\Rset_t:= \Dset_t(0)$.
\een
\ed
Consider a $d_0 \le d$. From the signal model, it is clear that at any time, $t$, $S_a$ elements enter the small coefficients' set, $\Sset_t(d_0)$, from the bottom (set $\Aset_t$) and $S_a$ enter from the top (set $\Dset_{t}(d_0-1)$). Similarly $S_a$ elements leave  $\Sset_t(d_0)$ from the bottom  (set $\Rset_t$) and $S_a$ from the top (set $\Iset_{t}(d_0)$). Thus,
\bea
\Sset_t(d_0) = \Sset_{t-1}(d_0)  \cup (\Aset_t \cup \Dset_{t}(d_0-1)) \setminus (\Rset_t \cup \Iset_{t}(d_0)) \ \ \
\label{sseteq}
\eea

\bd
Define
\ben
\item Increasing set, $\Inc_t := \Iset_t(1) \cup \Iset_t(2) \dots \cup  \Iset_t(d-1)$
\item Decreasing set, $\Dec_t := \Dset_t(1) \cup \Dset_t(2) \dots \cup  \Dset_t(d-1)$
\item Constant set, $\Con_t:= \{i : |x_{t,i}| = M \}$.
\een
Clearly $\Con_t = N_t \setminus (\Inc_t \cup \Dec_t)$.
\ed

With the above definitions, a generative model for Signal Model \ref{sigmod2} can be specified as follows. At each $t > 0$,
\ben

\item Select $\Dset_t(d-1) \subseteq \Con_{t-1}$ of size $S_a$ and select the newly added set, $\Iset_t(1) \subseteq N_{t-1}^c$ of size $S_a$.

\item Update the sets:
\bea
\Iset_t(j) \se \Iset_{t-1}(j-1), \ \forall \ j=2, \dots (d-1) \nn \\
\Dset_t(j) \se \Dset_{t-1}(j+1), \ \forall \ j=1, \dots (d-2) \nn \\
\Inc_t \se \Inc_{t-1} \cup \Iset_t(1) \setminus \Iset_t(d) \nn \\
\Dec_t \se \Dec_{t-1} \cup \Dset_t(d-1) \setminus \Dset_t(0) \nn \\
\Con_t \se \Con_{t-1} \cup  \Iset_t(d) \setminus \Dset_t(d-1) \nn \\
N_t \se \Inc_t \cup \Dec_t \cup \Con_t
\eea

\item Update the coefficient magnitudes:
\bea
|(x_{t})_{\Inc_{t}}| \se |(x_{t-1})_{\Inc_{t}}| + M/d \nn \\
|(x_{t})_{\Dec_{t}}| \se |(x_{t-1})_{\Dec_{t}}| - M/d \nn \\
|(x_{t})_{\Con_{t}}| \se |(x_{t-1})_{\Con_{t}}|
\eea

\item  The model does not assume anything about signs. But a reasonable generative model will keep the signs the same except when the coefficient first gets added (at that time, can set the sign to $\pm 1$ with equal probability).
\een


TITLE: Numerically solving equations with expectations
QUESTION [0 upvotes]: I have a equation $\mathbb{E}_\theta f(x,\theta)=a$, where $\theta$ is a vector real random variable with a known distribution, $a$ is a real constant, $x$ is a real (can be vector valued) variable. The function $f$ is too complex in $\theta$ for me to find a closed form expectation thus removing $\theta$.
One way to solve this is to set a value to $x$ and compute expectation using monte-carlo method and then increment or decrement $x$ and redo... I know that the function $f$ is monotonic in $x$ so the above method works. Is there some other, possibly easier way to solve it numerically? I am using Matlab and it would be great if there is existing function that I can use where I input $f$ and CDF of $\theta$ and it outputs solution.

REPLY [0 votes]: Monte-Carlo functions are quite easy to create, I don't think some special-made function will help you out too much. Thus, similar to what was suggested, what you can to do is create a function that takes x as an input and performs the numerical integration. Call this function $exp\_mean(x)$.
$exp\_mean(x)=E_{\theta}[f(x,\theta)] - a$
(Hint: If possible, take the draws outside of the function so that you do not need to re-draw values every time the function is called). Then, use one of the non-linear solvers to solve for x such as fsolve.
x = fsolve('exp_mean',x0)
where x0 is some starting value. Try experimenting with different values for the number of draws and starting values. (I always prefer to do a grid search to obtain starting values).


TITLE: How do I take the gradient of the position operator?
QUESTION [0 upvotes]: I have a function $$g(\hat{\vec{x}}) = e^{-(\hat{\vec{x}} - \vec{r})^2 / 2r_c^2}$$ Here, $\hat{\vec{x}}$ is the position operator, $r_c$ is parameter and $\vec{r}$ denotes a classical position. I want to expand this around $\hat{\vec{x}}$, which I assume to be valid if $||\hat{\vec{x}}_{\alpha}|| \ll |\vec{x}|, |r|$, where $||*||$ is an operator norm. Is this assumption correct, or am I on the wrong track here?
The expansion up to first order is given then by $$g(\hat{\vec{x}}) \approx g(0) + \nabla g(\hat{\vec{x}})|_{\hat{\vec{x}} = 0} * \hat{\vec{x}}$$
I evaluate the gradient by first doing the outer derivatives $$\nabla g(\hat{\vec{x}})|_{\hat{\vec{x}} = 0} = e^{\vec{r}^2 / 2r_c^2} \frac{\vec{r}}{r_c^2}\nabla (\hat{\vec{x}} - \vec{r})|_{\hat{\vec{x}} = 0}$$
Now, I do get stuck on the last factor in the above expression
$$\nabla (\hat{\vec{x}} - \vec{r})|_{\hat{\vec{x}}$$
In particular, I do not understand how to take the derivative of an operator which isn't given in any basis. Is that even possible? Is there any intuition on how to understand the derivative of the position operator?
I would be very grateful for any hints on how to solve this.
Thanks!

REPLY [1 votes]: There is no issue of non-commutativity, here, as all $\hat{\vec{x}}$s commute with each other and all c-numbers (ordinary non-operator expressions), and can thus be treated as plain vector variables, effectively c-numbers, themselves, formally.
So, then,
$$ \nabla e^{-(\hat{\vec{x}} - \vec{r})^2 / 2r_c^2}\Bigl |_{\hat{\vec{x}} = 0} = e^{-\vec{r}^2 / 2r_c^2} \frac{\vec{r}}{r_c^2}~~.
$$