TITLE: $\mathcal{C}_1 \subseteq \mathcal{C}_2 \implies \sigma( \mathcal{C}_1) \subseteq \sigma( \mathcal{C}_2) $
QUESTION [5 upvotes]: $\mathcal{C}_1$, $\mathcal{C}_2$ are collections of subsets of $X$,then Im having hard time seeing why the  following is true. Can someone explain them to me?
$\mathcal{C}_1 \subseteq \mathcal{C}_2 \implies \sigma( \mathcal{C}_1) \subseteq \sigma( \mathcal{C}_2) $
$\sigma(\sigma( \mathcal{C} )) = \sigma( \mathcal{C} ) $
where $\sigma( \mathcal{F} ) $ is the sigma field generated by the collection $\mathcal{F}$ of subsets of $X$
thanks

REPLY [4 votes]: Do you remember the proof of the existence of the $\sigma$-field generated by a set? You define $\mathcal{A} = \{\sigma-\text{fields containing}\ $C$\}$ (you note that this family is not empty) and you take the intersection of the elements of $\mathcal{A}$.
Once you have this both the properties follow very easily

$\mathcal{A} = \{\sigma-\text{fields containing}\ C_2\} \subset \{\sigma-\text{fields containing}\ C_1\} = \mathcal{B}$. Then $$\sigma(C_1) = \bigcap_{B \in \mathcal{B}}B \subset \bigcap_{A \in \mathcal{A}}A = \sigma(C_2).$$
Clearly $\sigma(C) \subset \sigma(\sigma(C))$. The other inclusion is given by $\sigma(C) \in \{\sigma-\text{fields containing}\ \sigma(C)\}.$


TITLE: Is there a unique way to construct the overall spatial wavefunction for identical particles?
QUESTION [1 upvotes]: While studying the quantum mechanics of $N$ identical particles, I stumbled upon formulas for generalizing the spatial wavefunction for bosons:
$$\psi(x_1,...,x_N)=\frac{1}{\sqrt{N!\prod_\alpha N_\alpha!}}\sum_p \psi_1(x_1)...\psi_N(x_N)$$
and for fermions, using the Slater Determinant:
$$
\psi(x_1,...,x_N)=\frac{1}{\sqrt{N!}}
\begin{vmatrix}
\psi_1(x_1) & \psi_1(x_2) & ... & \psi_1(x_N)\\
\psi_2(x_1) & \psi_2(x_2) & ... & \psi_2(x_N)\\
 \vdots & \vdots & \ddots & \vdots \\
\psi_N(x_1) & \psi_N(x_2) & ... & \psi_N(x_N)\\
\end{vmatrix}
$$
My question is this: Are these the only ways of constructing wavefunctions for bosons and fermions? If no, how else do we do it? If yes, does the uniqueness of the formulas above point toward some deep fundamental fact about particles?
The way I understand it, the only requirement here is that the spatial wavefunction for the system of bosons be symmetric, and for the system of fermions, anti-symmetric. That said, I have not come across other schemes for constructing these wavefunctions, and I am curious if there are such schemes at all.

REPLY [1 votes]: Determinants and permanents are not the only way.
There is a general result for the permutation group that, if you want to construct a fully symmetric wavefunction by combining the spatial and spin parts, then both parts must have the same permutation symmetry (i.e. must transform by identical irreps).  This applies also for multidimensional representation of the permutation group.
If you want to construct a fully antisymmetric wavefunction, you must combine a spatial and spin part of conjugate symmetries.
As an example, it is possible to construct a fully symmetric 4-particle state by combining spatial states and spin states in the 3-dimensional irrep $\{3,1\}$, and a fully antisymmetric state by combining a spatial part in $\{2,1,1\}$ and a spin part in $\{3,1\}$ (both of which of course are $3$-dimensional).
The explicit sums of products of the various parts are given by the Clebsch-Gordan coefficients for the permutation group (in my example, those would be CG’s for $S_4$).
This method does have the advantage of providing you with state of specific total spin but algebraic cost increases with $n$, and tables of CG’s for $S_n$ aren’t so common (much less pre-packaged codes).
On balance, determinants or permanents are more common, and chemists in particular have developed various clever methods to extract angular momentum or spin information when needed.


TITLE: What is the significance of the derivative of a probability density function of a continuous random variable?
QUESTION [8 upvotes]: What is the significance of the derivative of a probability density function of a continuous random variable ?

REPLY [4 votes]: It reduces Lebesgue-stielgies integral to the usual Lebesgue integral in computing,which is easier.


TITLE: tensor product of finite-dimensional irreducible modules for a semisimple Lie algebra
QUESTION [1 upvotes]: How to prove the following statement:

If $g$ is a semisimple Lie algebra, then the tensor product of finite-dimensional irreducible modules possesses the crucial property of being fully reducible.

REPLY [1 votes]: If $\mathfrak{g}$ is semisimple then all of its finite-dimensional modules are completely reducible (in characteristic zero) --- that's Weyl's theorem


TITLE: Rank of square matrix $A$ with $a_{ij}=\lambda_j^{p_i}$, where $p_i$ is an increasing sequence
QUESTION [8 upvotes]: Let
$$ A = \begin{bmatrix} \lambda_1^{p_1}  & \lambda_2^{p_1}  & \cdots & \lambda_n^{p_1}  \\
\lambda_1^{p_2}  & \lambda_2^{p_2}  & \cdots & \lambda_n^{p_2}  \\
\lambda_1^{p_3}  & \lambda_2^{p_3}  & \cdots & \lambda_n^{p_3}  \\
\vdots & \vdots & \ddots & \vdots \\
\lambda_1^{p_n}  & \lambda_2^{p_n}  & \cdots & \lambda_n^{p_n}  \end{bmatrix}$$
where $p_1=0$ and $p_k >  p_i$ for $i < k \leq n$. Each $p_i$ is an integer number (increasing but bounded) and each $\lambda_j$ is a positive real number.
I believe that I can show that $A$ is full rank if $\lambda_k \neq \lambda_j$ for all $k\neq j$ (distinct). That is the question that I would like to answer, when is $rank(A)=n$. At least I can prove it for $n =2$ and $n=3$ if each $\lambda_j$ is different.
In case it helps,
$$ A = \begin{bmatrix} C\Lambda^{p_1} \\ C\Lambda^{p_2} \\ \vdots \\ C\Lambda^{p_n} \end{bmatrix}$$
where $C = [1\;1\; 1\; \cdots\; 1]$ is a $1\times n$ vector of 1s and $\Lambda = diag\{\lambda_1, \lambda_2, \cdots, \lambda_n\}$ is a diagonal matrix.
Also, if $p_i = i-1$, my hypothesis can be proven as long as the entries of the diagonal matrix are different. I know the later from observability in control system theory. However, the case I am trying to evaluate is more general and $p_i$ might not be $i-1$.

REPLY [6 votes]: It is not true that $\text{rank}(A)=n$ whenever the $\lambda_i$ are pairwise ditinct, even for $n=3$. Consider
\begin{equation}
A=\left(\begin{array}{ccc}
1&1&1\\
{\lambda_1}&{\lambda_2}&{\lambda_3}\\
{\lambda_1}^3&{\lambda_2}^3&{\lambda_3}^3
\end{array} \right)
\end{equation}
Then $\det(A)=-({\lambda_1}-{\lambda_2})({\lambda_1}-{\lambda_3})({\lambda_2}-{\lambda_3})({\lambda_1}+{\lambda_2}+{\lambda_3})$ so that if ${\lambda_1}+{\lambda_2}+{\lambda_3}=0$, even if the $\lambda_i$ are pairwise distinct, we'll have $\det(A)=0$ so it will not be full rank.
EDIT: Expanding the answer as per the comments, and taking into consideration now that all $\lambda_i$ are positive. When $p_i=i-1$ we have a Vandermonde Matrix, whose determinant is simply
$$\prod_{0\leq i<j \leq n} (\lambda_j-\lambda_i)$$
This confirms that the determinant is $0$ if and only if $\lambda_i=\lambda_j$ for some $i\neq j$, that is, when the $\lambda_i$'s are pairwise distinct $A$ is indeed full-rank.
In the more general case that the $p_i$ can skip powers as in the question, $\det(A)$ is an alternating polynomial (notice that swapping two columns is equivalent to swapping tow variables and causes a change of sign). As such, it is a product $v\cdot s$ of a Vandermonde determinant $v$ by a symmetric polynomial $s$ (in $\lambda_1,\lambda_2, \dots, \lambda_n$).
We can conclude more with Schur polynomials. Indeed, we have that $\det(A)$ is, up to sign, given by
$$a_{\displaystyle (p_1,p_2,\dots,p_n)}(\lambda_1,\lambda_2,\dots,\lambda_n)$$
so the symmetric polynomial $s$ that's multiplying the Vandermonde determinant in $\det(A)$ is a Schur polynomial.
Finally, use that Schur polynomials can be written as linear combinations with non-negative integer coefficients of monomial symmetric polynomials:
$$s=\sum_{\mu}K_{\mu}m_{\mu}$$
where $K_{\mu}>0$ for all $\mu$ and $m_{\mu}$ is a monomial symmetric polynomial. Since these functions are positive whenever their arguments are all positive, so too is $s$.
Hence, when the $\lambda_i$ are all positive, $s$ does not vanish, so in that range $\det(A)=0$ if and only if $\lambda_i=\lambda_j$ for some $i\neq j$. In other words, when the $\lambda_i$ are positive, $A$ is full rank if and only if the $\lambda_i$ are pairwise distinct.
EDIT²: It means that the determinant is of the form
$$\left(\prod_{1\leq i < j \leq n} (\lambda_j - \lambda_i)\right) \cdot s(\lambda_1, \dots, \lambda_n)$$
where $s$ is a Schur polynomial. As a Schur polynomial, $s$ is a symmetric polynomial and can be written as a (finite) linear combination
$$s(\lambda_1,\dots, \lambda_n) = \sum_{\mu}K_{\mu}\cdot m_{\mu}$$
where the $K_{\mu}$ are all non-negative integers and the $m_{\mu}$ are monomial symmetric polynomials.
Monomial symmetric polynomials can be indexed by a partition $i=i_1+i_2+\cdots + i_j$ (where we assume without loss of generality $i_1 \geq i_2 \geq \dots \geq i_j \geq 0$). Such a partition is indicated simply by $(i_1,i_2,\dots,i_j)$ and gives rise to the following polynomial
$$m_{(i_1,i_2,\dots,i_j)}(X_1,X_2,\dots , X_j)=\sum\limits_{\sigma \in P(i_1,i_2,\dots,i_j)} {X_1}^{\sigma(i_1)}\cdot {X_2}^{\sigma(i_2)} \dots{X_j}^{\sigma(i_j)}$$
where $P(i_1,i_2,\dots,i_j)$ is the set of all distinct permutations of $(i_1,i_2,\dots,i_j)$.
For concrete examples on these polynomials, consider this wikipedia article. Also, the Schur polynomial in my first example matrix $A$ up above is $$s(\lambda_1,\lambda_2,\lambda_3)= 1 \cdot m_{(1,0,0)}(\lambda_1,\lambda_2,\lambda_3)=\lambda_1+\lambda_2+\lambda_3$$
In particular, when $X_1,X_2,\dots, X_j >0$ any monomial symmetric polynomial is a sum of positive terms and thus itself positive. Hence, $s$ too is positive when the $\lambda_i$'s are positive.


text:
\begin{document}

\maketitle
\abstract{
The discrete Fourier transform test is a randomness test included in NIST SP800-22.
However, the variance of the test statistic is smaller than expected and the theoretical value of the variance is not known.
Hitherto, the mechanism explaining why the former variance is smaller than expected has been qualitatively explained based on Parseval's theorem.
In this paper, we explore this quantitatively and derive the variance using Parseval's theorem under particular assumptions. Numerical experiments are then used to show that this derived variance is robust.
}

\section{Introduction}
Random number sequences are used in many fields.
These sequences play a particularly important role in information security including cryptography because high ``randomness'' is required in such fields.
Thus, evaluation of random number sequences and their generators is indispensable.

Randomness tests are one of the most fundamental evaluation methods in this respect.
These are hypothesis tests, and the null is that the given sequence is truly random.
Randomness tests do not require information about the generator which resulted in the given sequence.
Thus, such tests can be widely used without regard to the generators.
There are many kinds of randomness tests and some test sets have been proposed.
NIST SP800-22 \cite{NIST} is one of the most well-known test sets; the first version was published in 2001 and revision 1a, published in 2010, is currently the most recent variant.
Revision 1a consists of 188 test items which can be grouped according to 15 types.

A discrete Fourier transform test (DFTT) is one of the randomness tests included in NIST SP800-22.
The algorithm for the DFTT included in the first version is as follows:
\begin{enumerate}
\item Input an $n$-bit sequence $X$. Here, each bit of $X$ is 0 or 1.
\item Convert each bit $x$ to $2x-1$ (each bit becomes 1 or -1).
\item Perform DFT to obtain the Fourier spectrum series
\begin{align}
|f_0|,|f_1|,\cdots,|f_{\left\lfloor\frac{n}{2}\right\rfloor-1}|,
\end{align}
where
\begin{align}
|f_j|:=\sqrt{\left(\sum_{k=0}^{n-1}x_k\cos\left(\frac{2\pi kj}{n}\right)\right)^2+\left(\sum_{k=0}^{n-1}x_k\sin\left(\frac{2\pi kj}{n}\right)\right)^2},
\end{align}
with $x_k$ being the $(k+1)$-th bit of $X$.
\item Count the elements of $\{|f_0|,|f_1|,\cdots,|f_{\left\lfloor\frac{n}{2}\right\rfloor-1}\}$ satisfying $|f_i|<\sqrt{3n}$.
Let $N_1$ be such a number.
\item Compute $d$ defined by
\begin{align}
d=\frac{N_1-0.95\frac{n}{2}}{\sqrt{(0.95)(0.05)\frac{n}{2}}}.
\end{align}
\item Compute p-value $p$ defined by
\begin{align}
p=\text{erfc}\left(\frac{|d|}{\sqrt{2}}\right),
\end{align}
where erfc denotes the complementary error function.
\end{enumerate}
For $j=1,2,\cdots,n-1$, $\frac{2}{n}|f_j|^2$ follows the $\chi^2$-distribution with 2 degrees of freedom as $n\to\infty$.
If $Z$ is a stochastic variable and $\frac{2}{n}|Z|^2$ follows a $\chi^2$-distribution with 2 degrees of freedom, then
\begin{align}
\text{Prob}\{\ |Z|<\sqrt{3n}\ \}\sim 0.95.
\end{align}
Thus, it is expected that $N_1$ approximately follows a normal distribution with an average and variance of $0.95\frac{n}{2}$ and $(0.95)(0.05)\frac{n}{2}$, respectively.
If this holds, $d$ and $p$ approximately follow a standard normal distribution and a uniform distribution over the interval $[0,1]$, respectively.

However, the following problems were revealed by \cite{Kim-Umeno-Hasegawa,Hamano}.
\begin{itemize}
\item The threshold $\sqrt{3n}$ is an approximation and it is not accurate enough for practical use.
\item The variance of $N_1$ observed numerically is far smaller than expected.
\end{itemize}
To address the first problem, Kim et al. proposed that the threshold value should be changed from $\sqrt{3n}$ to $\sqrt{-n\log(0.05)}$ \cite{Kim-Umeno-Hasegawa}.
If $Z$ is a stochastic variable and $\frac{2}{n}|Z|^2$ follows a $\chi^2$-distribution with 2 degrees of freedom,
\begin{align}
\text{Prob}\{\ |Z|<\sqrt{-n\log(0.05)}\ \}=0.95\ .
\end{align}
Then, we can state that the proposed threshold is appropriate. The DFTT included in revision 1a uses this proposed value.

To address the second problem, Kim et al. also proposed to use $(0.95)(0.05)\frac{n}{4}$ as an estimate of the variance of $N_1$ \cite{Kim-Umeno-Hasegawa}.
In other words, because the variable $d$ should follow a standard normal distribution, they proposed to change the computation of $d$ to
\begin{align}
d=\frac{N_1-0.95\frac{n}{2}}{\sqrt{(0.95)(0.05)\frac{n}{4}}}.
\end{align}
Subsequently, Hamano et al. proposed $(0.95)(0.05)\frac{n}{2}\times0.528\simeq(0.95)(0.05)\frac{n}{3.7879}$ as the variance of $N_1$ \cite{Hamano-Yamamoto} and Pareschi et al. proposed $(0.95)(0.05)\frac{n}{3.8}$ as that \cite{Pareschi}.
These proposed values were experimentally derived but the theoretical value of this variance has not been derived.

Yamamoto et al. qualitatively explained why the variance of $N_1$ is smaller than\\ $(0.95)(0.05)\frac{n}{2}$ based on Parseval's theorem \cite{Yamamoto-Kaneko}.
We believe that the explanation is persuasive.
In this paper, we derive the variance of $N_1$ based on Parseval's theorem with some assumptions.
Although some alternative tests to DFTT have been proposed \cite{Okada,Iwasaki-SCIS}, these are not dealt with herein, because the DFTT is now preferred and revising a parameter is easier than revising the algorithms.

The remainder of the paper is organized as follows.
In section 2, we introduce the qualitative explanation based on Parseval's theorem which has hitherto been documented in the literature.
In section 3, we theoretically derive the value of the variance with Parseval's theorem and some assumptions.
In section 4, we perform some experiments and discuss the validity of the result in Section 3.
Finally, in section 5 we offer conclusions.

\section{Qualitative explanation based on Parseval's theorem}
In this section, we briefly introduce the qualitative explanation by Yamamoto et al. This also serves as preparation for the next section.

By Parseval's theorem, it follows that
\begin{align}
\sum_{j=0}^{n-1}|f_j|^2=n\sum_{k=0}^{n-1}|x_k|^2.
\end{align}
For $k=0,1,\cdots,n-1$, $|x_k|^2=1$ because $x_k=\pm1$.
Then,
\begin{align}
\sum_{j=0}^{n-1}|f_j|^2=n^2.
\end{align}
By the symmetry of the Fourier transformation,
\begin{align}
|f_{n-j}|=|f_j|
\end{align}
for arbitrary $j$.
Then,
\begin{align}
\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor-1}|f_j|^2=
\begin{cases}
\frac{n^2}{2}+\frac{|f_0|^2}{2}-\frac{|f_{\frac{n}{2}}|^2}{2}\ \ \ \ &(n\text{:even})\\
\frac{n^2}{2}+\frac{|f_0|^2}{2}\ \ &(n\text{:odd})
\end{cases}
.\label{restriction}
\end{align}
From \cite{Hirose}, for $j=1,2,\cdots,n-1$, we have
\begin{align}
V\left[|f_j|^2\right]=n^2-2n, \label{hirose1}
\end{align}
where $V[Z]$ is the variance of variable $Z$.
For $j=0$, it follows that
\begin{align}
V\left[|f_0|^2\right]&=V\left[\left(\sum_{k=0}^{n-1}x_k\right)^2\right]\\
&=\mathbb{E}\left[\left(\sum_{k=0}^{n-1}x_k\right)^4\right]-\mathbb{E}\left[\left(\sum_{k=0}^{n-1}x_k\right)^2\right]^2\\
&=\sum_{k_1=0}^{n-1}\sum_{k_2=0}^{n-1}\sum_{k_3=0}^{n-1}\sum_{k_4=0}^{n-1}\mathbb{E}\left[x_{k_1}x_{k_2}x_{k_3}x_{k_4}\right]-\left\{\sum_{k_1=0}^{n-1}\sum_{k_2=0}^{n-1}\mathbb{E}\left[x_{k_1}x_{k_2}\right]\right\}^2\\
&=2n^2-2n,\label{hirose2}
\end{align}
where $\mathbb{E}[\cdot]$ is $\frac{1}{2^n}\sum_{X\in\{-1,1\}^n}(\cdot)$\ .
Using (\ref{hirose1}) and (\ref{hirose2}),
\begin{align}
V\left[\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor-1}|f_j|^2\right]\leq& \max\left\{4V\left[\frac{|f_0|^2}{2}\right],4V\left[\frac{|f_{\left\lfloor\frac{n}{2}\right\rfloor}|^2}{2}\right]\right\}\\
=&2n^2-2n.\label{varianceofenergy}
\end{align}
If $|f_0|, |f_1|, \cdots, |f_{\left\lfloor\frac{n}{2}\right\rfloor-1}|$ are mutually independent, then
\begin{align}
V\left[\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor-1}|f_j|^2\right]
=&\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor-1}V\Big[|f_j|^2\Big]\\
=&\left\lfloor\frac{n}{2}\right\rfloor(n^2-2n)+n^2.\label{varianceofenergywithassumption}
\end{align}
Comparing (\ref{varianceofenergy}) and (\ref{varianceofenergywithassumption}), we conclude that the energy $\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor-1}|f_j|^2$ is restricted to a narrow area in $\mathbb{R}$ by the dependency among $|f_0|, |f_1|, \cdots, |f_{\left\lfloor\frac{n}{2}\right\rfloor-1}|$.

Yamamoto et al. claimed that this restriction explains why $V[N_1]$ is smaller than $(0.95)(0.05)\frac{n}{2}$.
If some elements of $\{|f_0|, |f_1|, \cdots, |f_{\left\lfloor\frac{n}{2}\right\rfloor-1}|\}$ take large values, then some other elements must take small values to maintain the restriction.
As a result, the probability that $N_1$ takes a value far from the average is forced to be small, i.e., $V[N_1]$ is smaller than $(0.95)(0.05)\frac{n}{2}$.

\section{Quantitative analysis based on Parseval's theorem}
From our perspective, the qualitative explanation introduced in the previous section is persuasive.
The restriction by Parseval's theorem will be critical to deriving $V[N_1]$.
Thus, in this section, we theoretically derive $V[N_1]$ with Parseval's theorem under particular assumptions.
To simplify discussion we assume that $n$ is even, but this is not essential.
We define $m$ as $\frac{n}{2}$.

\subsection{Assumptions}
If we know the analytical form of the joint probability density function depending on \\$\left(|f_0|, |f_2|, \cdots, |f_{m-1}|\right)$, we can derive $V[N_1]$.
However, the form is not known.
Thus, we need to assume a certain analytical form and in this subsection we discuss which such form is appropriate.
First, we introduce the following proposition.
\begin{prop}
\label{prop-3}
Let $R$ be an arbitrary natural number.
Then, the joint probability density function depending on $\left(\frac{1}{m}|f_1|^2, \frac{1}{m}|f_2|^2, \cdots, \frac{1}{m}|f_R|^2\right)$ converges to
\begin{align}
\frac{1}{2^R}\exp\left(-\frac{\sum_{j=1}^R|f_j|^2}{2m}\right)
\label{pdf}
\end{align}
as $m\to \infty$.
\end{prop}
In Proposition \ref{prop-3}, $R$ is a fixed value.
As an analogy, let us assume that the joint probability density function depending on $\left(\frac{1}{m}|f_0|^2, \frac{1}{m}|f_2|^2, \cdots, \frac{1}{m}|f_{m-1}|^2\right)$ converges to
\begin{align}
\frac{1}{2^m}\exp\left(-\frac{\sum_{j=0}^{m-1}|f_j|^2}{2m}\right).
\label{pdf2}
\end{align}
However, there are two problems:
\begin{itemize}
\item Even as $n\to\infty$, i.e., $m\to\infty$, $\frac{1}{m}|f_0|^2$ does not follow a $\chi^2$-distribution with 2 degrees of freedom, which is the limit distribution of $\frac{1}{m}|f_j|^2,\ (j\ne 0)$.
\item The energy is restricted to a narrow area by (\ref{restriction}).
\end{itemize}
To address these problems, we assume the following:
\begin{itemize}
\item For sufficiently large $n$, the value of $V[N_1]$ will be virtually preserved even if $\frac{1}{m}|f_0|^2$ are replaced with a variable following a $\chi^2$-distribution with 2 degrees of freedom.
Thus, we assume that $\frac{1}{m}|f_0|^2$ follows a $\chi^2$-distribution with 2 degrees of freedom.
\item The energy $\sum_{j=0}^{m-1}|f_j|^2$ is restricted by (\ref{restriction}), and it is not constant.
However, by (\ref{varianceofenergy}), we can state that the standard deviation of the energy is sufficiently smaller than the average of that energy.
Thus, we assume that
\begin{align}
\sum_{j=0}^{m-1}|f_j|^2=2m^2.\label{constantrestriction}
\end{align}

\end{itemize}
Based on the above two assumptions and (\ref{pdf2}), we further assume the following.
\begin{asu}
\label{assumption}
In $\mathbb{R}^m$, $\left(|f_0|^2, |f_2|^2, \cdots, |f_{m-1}|^2\right)$ is restricted on the surface defined by (\ref{constantrestriction}), and it is uniformly distributed in the area where $|f_j|^2\geq0\ j=0,1,2,\cdots,m-1$ on the surface.
\end{asu}

\subsection{Analysis using polar coordinates}

To derive $V\left[N_1\right]$, we need probability density functions depending on $|f_i|^2$ for $i=0,1,\cdots,m-1$ and joint probability density functions depending on $\left(|f_i|^2,|f_j|^2\right)$ for $i\ne j$.
In this subsection, we derive these different density functions under Assumption \ref{assumption}.

Under Assumption \ref{assumption}, $\Bar{p}$ which is the joint probability density function depending on $\left(|f_0|^2, |f_1|^2, \cdots, |f_{m-1}|^2\right)$ is as follows:
\begin{align}
\Bar{p}(|f_0|^2, |f_1|^2, \cdots, |f_{m-1}|^2)=
\begin{cases}
C_1&(|f_j|^2\geq0\ (j=0,1,\cdots,m-1)\text{ and }\sum_{j=0}^{m-1}|f_j|^2=2m^2)\\
0&(\text{otherwise})
\end{cases}
.\label{uniformdistribution}
\end{align}
We use polar coordinates,
\begin{align}
 |f_0| &= r \cos\theta_1, \label{X_0}\\
      |f_1| &= r \sin\theta_1 \cos\theta_2, \\
      |f_2|  &= r\sin\theta_1 \sin\theta_2 \cos\theta_3, \\
              &\vdots \\
      |f_{m-2}| &= r \sin\theta_1 \cdots \sin\theta_{m-2} \cos \theta_{m-1}, \\
      |f_{m-1}| &= r \sin\theta_1 \cdots \sin\theta_{m-2} \sin \theta_{m-1},
\end{align}
where $r\geq 0$, $0\leq \theta_i\leq \pi$ ($i=1,2,\cdots,m-2$), and $0\leq \theta_{m-1}< 2\pi$.
The Jacobian for the change in coordinates is
\begin{align}
r^{m-1} \prod_{i=1}^{m-1}\left(\sin\theta_i\right)^{m-i-1}.
\end{align}
For $j=0,1,\cdots,m-1$, it follows that
\begin{align}
d|f_j|^2=2|f_j|d|f_j|.
\end{align}
Then, we have
\begin{align}
\prod_{j=0}^{m-1}d|f_j|^2
=&2^m\prod_{j=0}^{m-1}|f_j|d|f_j|.\\
=&2^mr^{m-1}\left(\prod_{j=0}^{m-1}|f_j|\right) \left(\prod_{i=1}^{m-1}\left(\sin\theta_i\right)^{m-i-1}\right) drd\theta_1d\theta_2\cdots d\theta_{m-1}\\
=&2^mr^{2m-1}\left(\prod_{i=1}^{m-1}\left(\sin\theta_i\right)^{2m-2i-1}\cos \theta_i\right) drd\theta_1d\theta_2\cdots d\theta_{m-1}.
\label{henkan}
\end{align}

Let $p_j$ be a probability density function depending on $|f_j|^2$ and $p_{(i,j)}$ be a joint probability density function depending on $(|f_i|^2,|f_j|^2)$.
First, we derive $p_0$.
By (\ref{X_0}), $|f_0|^2=r^2\cos^2\theta_1$.
Then, by (\ref{uniformdistribution}) and (\ref{henkan}),
\begin{align}
p_0(|f_0|^2)d|f_0|^2=
\begin{cases}
C_2 \left(\sin\theta_1\right)^{2m-3}\cos \theta_1 d\theta_1\ \ &(0\leq |f_0|^2\leq 2m^2)\\
0 &(\text{otherwise})
\end{cases}
,
\end{align}
and
\begin{align}
d|f_0|^2=C_3\sin \theta_1 \cos \theta_1d\theta_1,
\end{align}
where $C_2$ and $C_3$ are constants.
Then,
\begin{align}
p_0(|f_0|^2)=
\begin{cases}
\frac{m-1}{2m^2} \left(1-\frac{|f_0|^2}{2m^2}\right)^{m-2}\ \ &(0\leq |f_0|^2\leq 2m^2)\\
0 &(\text{otherwise})
\end{cases}
.
\end{align}
Because $|f_0|^2,|f_1|^2,\cdots|f_{m-1}|^2$ follow the same distribution under Assumption \ref{assumption}, for $j=0,1,\cdots,m-1$,
\begin{align}
p_j(|f_j|^2)=
\begin{cases}
\frac{m-1}{2m^2} \left(1-\frac{|f_j|^2}{2m^2}\right)^{m-2}\ \ &(0\leq |f_j|^2\leq 2m^2)\\
0 &(\text{otherwise})
\end{cases}
.\label{syuuhen}
\end{align}

By (\ref{uniformdistribution}), $p_{(i,j)}$ depends only on $|f_i|^2+|f_j|^2$.
Then, by (\ref{syuuhen}),
\begin{align}
&p_{(i,j)}(|f_i|^2,|f_j|^2)\nonumber\\
=&
\begin{cases}
\frac{(m-1)(m-2)}{(2m^2)^2} \left(1-\frac{|f_i|^2+|f_j|^2}{2m^2}\right)^{m-3}&(|f_i|^2\geq0, |f_j|^2\geq0\text{ and }|f_i|^2+|f_j|^2\leq 2m^2)\\
0 &(\text{otherwise})
\end{cases}
.\label{niko}
\end{align}

\subsection{Theoretical derivation of $V[N_1]$}
In this subsection, we derive $V[N_1]$ using the results from the previous subsection.
For notational convenience, we introduce $T=\sqrt{-n\log(0.05)}$.
With this $T$, we define
\begin{align}
F_j:=
\begin{cases}
1\ \ &(|f_j|\leq T)\\
0   &(|f_j|>T)
\end{cases}
,
\end{align}
for $j=0,1,\cdots,m-1$.
Then, the variance is decomposed as
\begin{align}
V[N_1]=&V\left[\sum_{j=0}^{m-1}F_j\right]\\
=&\sum_{j=0}^{m-1}V\Big[F_j\Big]+\sum_{(i,j)|i\ne j}C\Big[F_i, F_j\Big]\sqrt{V\Big[F_i\Big]V\Big[F_j\Big]},
\label{tenkai}
\end{align}
where $C[X,Y]$ is the correlation coefficient between variables $X$ and $Y$.
By (\ref{syuuhen}) and (\ref{niko}), we have $V[F_i]$ and $C[F_i,F_j]$ as follows.
\begin{align}
&V\left[F_i\right]=\left(1-\frac{T^2}{2m^2}\right)^{m-1}-\left(1-\frac{T^2}{2m^2}\right)^{2m-2},\label{bunsan}\\
&C\left[F_i,F_j\right]=\frac{\left(1-\frac{T^2}{m^2}\right)^{m-1}-\left(1-\frac{T^2}{2m^2}\right)^{2m-2}}{\sqrt{V\left[F_i\right]V\left[F_j\right]}}.\label{soukan}
\end{align}
Substituting (\ref{bunsan}) and (\ref{soukan}) into (\ref{tenkai}), we arrive at
\begin{align}
V\left[N_1\right]
=m\times&\left\{\left(1-\frac{T^2}{2m^2}\right)^{m-1}-\left(1-\frac{T^2}{2m^2}\right)^{2m-2}\right\}\nonumber\\
&+m(m-1)\times\left\{\left(1-\frac{T^2}{m^2}\right)^{m-1}-\left(1-\frac{T^2}{2m^2}\right)^{2m-2}\right\}.
\label{rironbunsan}
\end{align}
Assuming that $V\left[N_1\right]=(0.95)(0.05)\frac{n}{a}$, we have
\begin{align}
a
=\frac{2\times0.05\times0.95}{\left(1-\frac{T^2}{2m^2}\right)^{m-1}-\left(1-\frac{T^2}{2m^2}\right)^{2m-2}+(m-1)\times\left\{\left(1-\frac{T^2}{m^2}\right)^{m-1}-\left(1-\frac{T^2}{2m^2}\right)^{2m-2}\right\}}.
\label{riron}
\end{align}
Figure \ref{rironkyokusen} shows that $a$ approximately converges to 3.7903 as $m\to\infty$.
Broadly speaking, this is consistent with previous studies.
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{a.png}
\end{center}
\begin{picture}(0,0)
\put(240,10){\Large $m$}
\put(60,110){\rotatebox{90}{\Large $a$}}
\end{picture}
\caption{Plot of (\ref{riron})}
\label{rironkyokusen}
\end{figure}

\section{Numerical experiments}
In the previous section, we used Assumption \ref{assumption}.
It is obvious that the true distribution is never the distribution defined by Assumption \ref{assumption}.
 However, they are very close in some sense and so we expect that (\ref{rironbunsan}) and (\ref{riron}), which are derived based on Assumption \ref{assumption}, are appropriate.
In this section, we discuss the validity of (\ref{rironbunsan}) and (\ref{riron}).

\subsection{Experiment 1}
By (\ref{tenkai}) which holds for both distributions, if $a$ converges to a certain value as $m\to\infty$, then the limit value depends only on the leading terms of $V[F_i]$ and $C[F_i,F_j]$.
By (\ref{bunsan}), for Assumption \ref{assumption},
\begin{align}
\lim_{m\to\infty}V[F_j]=(0.05)(0.95).
\label{bunsanlim}
\end{align}
With the true distribution, $\frac{1}{m}|f_j|^2$ converges to the $\chi^2$-distribution with 2 degrees of freedom for all $j$ except $j=0$, and (\ref{bunsanlim}) also holds.
We do not need to consider the case that $j=0$, because $V[F_0]$ becomes relatively smaller than $\sum_{j=0}^{m-1}V\left[F_j\right]$ as  $m\to\infty$.

Then, we should investigate the leading term of $C[F_i,F_j]$.
By the same argument, cases where $i=0$ and $j=0$ can be excepted.
We generated $10^8$ sequences using the Mersenne Twister \cite{MT}, performed DFT, and computed $C[F_1,F_2]$.
Figure \ref{cor} compares the $C[F_1,F_2]$ with that derived from Assumption \ref{assumption}.
The results corroborate that the leading term of $C[F_i,F_j]$ in both distributions is the same.

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{cor.png}
\end{center}
\caption{Comparing $C[F_1,F_2]$}
\label{cor}
\end{figure}

\subsection{Experiment 2}
We computed the value of $a$ with $10^8$ sequences generated by the Mersenne Twister \cite{MT}.
In general, randomness tests do not use $10^8$ sequences.
However, we need to compute the value of $a$ with high accuracy to discuss the validity of (\ref{rironbunsan}) and (\ref{riron}), so we used many sequences.
Each sequence was $10^6$-bit.
The experiments were repeated 10 times and the results are presented in Table \ref{table}.
Based on this, we can conclude that 3.7903, which was derived in the previous section, is close to the experimental result and a more accurate value compared to those generated in previous studies.

\begin{table}[h]
\caption{Value of $a$ computed using the Mersenne Twister}
\label{table}
\begin{center}
\begin{tabular}{cc}
\hline
Trial No.&$a$\\
\hline
1& 3.790208\\
2& 3.790127\\
3& 3.790568\\
4& 3.790496\\
5& 3.789058\\
6& 3.791035\\
7& 3.789565\\
8& 3.790191\\
9& 3.790522\\
10& 3.790403\\
\hline
Total &3.790217$\pm$ 0.000527\\
\hline
\end{tabular}
\end{center}
\end{table}

\section{Conclusion}
We have theoretically derived the variance of DFTT test statistics based on Parseval's theorem.
Because the variances reported by previous studies are based on numerical experiments, we can state that our result is superior subject to the tenability of the assumptions used.
In addition, and importantly, the derived value is consistent with experimental results generated herein.
Thus, we advocate that the value derived in this paper should be used when DFTT is performed so that randomness can be tested for more precisely.

config: arxiv


TITLE: Symmetry for dipole conservation in field theory
QUESTION [3 upvotes]: In article The Fracton Gauge Principle complex scalar field is considered.
There's statement, that for conservation of charge one needs usual U(1) global symmetry:
$$
\phi \to e^{i\alpha}\phi \Rightarrow Q =\int d^Dx \rho
$$
For conservation of dipole moment:
$$
\phi \to e^{i\vec x \cdot \vec \lambda}\phi \Rightarrow Q^i =\int d^Dx x^i\rho
$$
Why for dipole moment we need such symmetry?

REPLY [1 votes]: I think the right way to think about it is to first ask what the symmetry
$$
\phi \longrightarrow e^{i\theta} \phi
$$
means. The actual Unitary operator acting on the many-body Hilbert space that corresponds to this transformation is
$$
U(\theta) = \exp\left( i\theta \sum_r \phi^\dagger_r \phi_r \right)
$$
It is easy to see that $\phi$ transforms as shown in the first equation upon the adjoint action of $U$. So you see that the the $U(1)$ symmetry is generated by the total particle number operator. So, a system that has this symmetry conserves particle number and vice versa.
Now we consider a system with conservation of dipole moment. Dipole moment is given by the vector operator $\sum_r \boldsymbol{r}\phi^\dagger_r \phi_r $. Therefore, conservation of dipole moment actually refers to three independent conservation laws, whose corresponding unitary operator will be parametrised by a 3-vector $\boldsymbol{\lambda}$ as
$$
U(\boldsymbol{\lambda}) = \exp\left( i\boldsymbol{\lambda} \cdot \sum_r \boldsymbol{r}\phi^\dagger_r \phi_r \right)
$$
Now one can ask how does this act on the particle annihilation operator at a particular site $\phi_{r_0}$. We can simply look at the adjoint action
\begin{equation}
\begin{split}
\phi_{r_0} \longrightarrow U^\dagger\phi_{r_0} U &= \exp\left( -i\boldsymbol{\lambda} \cdot \sum_r \boldsymbol{r}\phi^\dagger_r \phi_r \right) \phi_{r_0} \exp\left( i\boldsymbol{\lambda} \cdot \sum_r \boldsymbol{r}\phi^\dagger_r \phi_r \right) \\
&=\exp(i\boldsymbol{\lambda} \cdot \boldsymbol{r_0})\phi_{r_0}
\end{split}
\end{equation}
Thus we see that what you stated is indeed the transformation that is generated by the total dipole moment operator, so it is the corresponding symmetry to it. Note that we can easily generalise this argument to the continuum.


TITLE: random variable, random sum
QUESTION [2 upvotes]: I have problem to show the following. Maybe someone has an idea :/
Let $X_1,...,X_n$ be i.i.d. copies of a random variable X with $|X|<1$. Let $S_n=X_1+..+X_n$. Then for any $A>0$:
$\mathbb{P}(|S_n-n\mathbb{E}[X]|\geq An)\leq C_A e^{-c_An}$
for some constants $C_A,c_A>0$ depending on $A$.
I have tried this before:
$\mathbb{P}(|S_n-n\mathbb{E}[X]|\geq An)= \mathbb{P}(|\sum_{i=1}^nX_i-\mathbb{E}[X]|\geq An)= \mathbb{P}(|\frac{1}{n}\sum_{i=1}^n X_i-\mathbb{E}[X]|\geq A)\leq \mathbb{P}(\frac{1}{n}\sum_{i=1}^n| X_i-\mathbb{E}[X]|\geq A)$

REPLY [2 votes]: Hint: Markov's inequality

(Extended version for monotonically increasing functions)
Edit (based on your try):
Let us bring you closer to the right direction. Observe that your problem is a special case of the famous

Hoeffding's inequality, see https://en.wikipedia.org/wiki/Hoeffding%27s_inequality

Essentially, the statement is slightly more general than your scenario, but you will get definitely inspired by its proof! Observe, it makes use of Markov's inequality (as I hinted).


TITLE: Understanding an Inequality from the AdaGrad paper involving expectation
QUESTION [2 upvotes]: Reading the paper on AdaGrad, an optimization method for machine learning, I am coming across an inequality I do not understand on page 5, available here
Denote $g_{1:T}$ as a matrix $G_T=[g_1, \ldots g_T]$ consisting of the sub gradients of dimension $d$ of the hinge loss function $L_t(x) = max(0, 1- y (z \cdot x_t))$ for $x$ a weight vector of dimension $d$, $z$ a feature vector, and $y$ its correct label at time step $T$.
Denote $g_{1:T,i}$ as the $i'th$ row of the matrix. They write:

For our first example, which was also given by McMahan and Streeter
(2010), consider the following sparse random data scenario, where the
vectors $z_t \in \{−1,0,1\}^d$. Assume that at in each round $t$,
feature $i$ appears with
probability $p_i = min\{1, ci^{−a}\}$ for some $\alpha \in (1,
 \infty)$ and a dimension independent constant c. Then taking the
expectation of the gradient terms, we have:
$(1) $$\mathbb{E}
 \sum_{i=1}^{d}||g_{1:T, i}||_2 = \sum_{i=1}^{d} \mathbb{E}
 [\sqrt{|\{t:|g_{t,i}| = 1 \}}|] \leq \sum_{i=1}^{d}
\sqrt{\mathbb{E}|\{t:|g_{t,i}|=1\}|} = \sum_{i=1}^{d} \sqrt{p_iT}$

I am not sure what the random variable is in this case. I believe what is happening is for each dimension of our sub gradient input vector, we are considering the expectation of the row of our matrix $G_T$ which will only be non-zero for sub gradient time step indices $t$ where the $i'th$ index of the gradient is $0$, and then applying Jensen's Inequality.
I also know that the gradient of the hinge loss is
$ \frac {\partial L} {\partial x_i} (x) = -y * z_i$ if $y (z \cdot x) < 1$, and $0$ otherwise. I'm not sure what the authors mean by a feature $i$ appears. Does this mean a value of $z_{t_{i}}$ that is non-zero?
I'm looking for a clarification of $(1)$ and would be happy to provide any other details/corrections.

REPLY [1 votes]: The notation in the paper is indeed confusing and many steps are not clear/explicit.  I'll give it a go!
Let's start computing the subgradient.
Notice that $$y_t\langle z_t, x\rangle = 1$$ is an hyperplane dividing the space of the parameters in 2 halves. On both these halves, the subgradient is actually a gradient and you can compute it just by standard calculus. On the dividing hyperplane the gradient is not well defined, as there is no unique linear approximate to the function on that point, but in this case this does not really matter (I'll explain later).
Where $y_t\langle z_t, x\rangle > 1$ the loss is identically $0$ and the gradient is $0$.
Where $y_t\langle z_t, x\rangle < 1$, the $i$-th partial derivative is $$\frac{\partial f_t(x)}{\partial x_i} = -z_{t, i}y_t.$$
What about $y_t\langle z_t, x\rangle = 1$? In this case you get the subgradient which is a full set and not a single vector. This is not a problem, as all we care is to find some bound for the components of each one of these vectors. Thinking about the hinge loss in one or two dimensions, you can convince yourself that each vector in the subgradient must have $i$-th component living in the interval $[-z_{t, i}y_t, 0]$. So for the purposes of getting the inequality we can consider the worst case, i.e the $i$-th component being equal to $-z_{t, i}y_t$.
And these are all the possible values of the gradient.
We also know that $z_{t, i}$ is nonzero with probability $p_i$, this means that the components of the gradient are nonzero with probability at most $p_i$.
Lastly, we notice that the standard hinge loss is used in 2 class classification problems, where $y_t = \pm 1$.
Finally, we are ready for equation $(1)$!
The first equality follows from the linearity of the expected value and from the fact that $g_{t, i}$ is $\pm1$ or $0$, so the sum of the square is equal to the number of elements that are not $0$.
The inequality follows from Jensen's inequality.
The last equality follows from computing the expected value of $\vert\vert(g_{1, i}, \dots g_{T, i})\vert\vert_{1}$ (which is equal to the number of nonzero elements in the $i$-th component of the gradients) which is
$$ \mathbb{E}[\sum_{t=1}^{T}\vert g_{t, i}\vert] = \sum_{t=1}^{T}\mathbb{E}[\vert g_{t, i}\vert] = \sum_{t=1}^{T} p_i = Tp_i.$$


TITLE: Prove that if the product of $a$ and $b$ has multiplicative inverse modulo $m$
QUESTION [0 upvotes]: Suppose we have integers $a$,$\space b$ and $m$ with $m \gt 1$.  Prove that if the product $a*b$ has a multiplicative inverse modulo m, then so does each of $a$ and $b$.

REPLY [2 votes]: $$1\pmod m=(ab)x=a(bx)=(ax)b$$


TITLE: Vector space of convergent sequences, prove it's complete
QUESTION [0 upvotes]: In the space of convergent sequences, such that for a convergent sequence $(a_n)$ we have $\sum _{n=1} ^{+ \infty} a_n ^2 < \infty$, we define a norm $(a_n) \rightarrow \sqrt{\sum _{n=1} ^{+ \infty} a_n ^2}$.
Prove that the space is complete with this norm and determine absolute and commutative convergence of $\sum _{n=1} ^{+ \infty} \frac{1}{n} e_n$ in this space.
I've already checked that it is indeed a norm. Could you give me some help with the rest?
Thank you.

REPLY [1 votes]: Your definiton of convergence is wrong
$||a_n-a_m||= \sqrt{\sum\limits_{i=1}^{\infty} (a_n(i)-a_m(i))^2}$
Now for each $i$, $a_n(i)$ must be a bounded sequence. (why?) what does bolzano-weirestrass tell you, which you can use to construct a candidate limit?


TITLE: Conjectured closed form of $G^{2~2}_{3~3}\left(1\middle|\begin{array}c1,1;b+1\\b,b;0\end{array}\right)$
QUESTION [6 upvotes]: In my answer to this question, I come across the following case of the Meijer G-function:
$$F(b)=G^{2~2}_{3~3}\left(1\middle|\begin{array}c1,1;b+1\\b,b;0\end{array}\right), b>0$$
and based on my experiments, $F(b)$ have the following closed form:
$$F(b)
\stackrel?=\frac{\Gamma(b)}{b}\left(-\gamma-\psi(b)+\frac{2^{1-b}}{b}{_2F_1}\left(\begin{array}c1,1\\b+1\end{array}\middle|-1\right)+b{_3F_2}\left(\begin{array}c1,1,b+1\\2,2\end{array}\middle|-1\right)\right)$$
Is there any chance of proving this?
Edit: Using the definition of the Meijer G-Function, $F(b)$ have the integral representation:
$$F(b)=\frac{1}{2\pi}\int^{+\infty}_{-\infty}\frac{\Gamma(\tfrac{b}{2}+ix)\Gamma(\tfrac{b}{2}-ix)}{\tfrac{b^2}{4}+x^2}dx.$$
Edit 2: I've found a further generalization:
$$F(b,z)=G^{2~2}_{3~3}\left(z\middle|\begin{array}c1,1;b+1\\b,b;0\end{array}\right)=\frac{1}{2\pi}\int^{+\infty}_{-\infty}\frac{\Gamma(\tfrac{b}{2}+ix)\Gamma(\tfrac{b}{2}-ix)}{\tfrac{b^2}{4}+x^2}e^{(b/2+ix)\log z}dx\\
\stackrel?=\frac{\Gamma(b)z^b}{b}\left(-\log z-\gamma-\psi(b)+\frac{(z+1)^{1-b}}{b}{_2F_1}\left(\begin{array}c1,1\\b+1\end{array}\middle|-z\right)+bz~{_3F_2}\left(\begin{array}c1,1,b+1\\2,2\end{array}\middle|-z\right)\right), b\not\in\{0,-1,-2,\dots\},z\neq0,-1.$$
Edit 3: Further simplified the ${_2F_1}$ part.

REPLY [1 votes]: Using the method in the other answer, assuming it is enough to sum the residues in the upper half-plane as in that case, I get
$$
\frac{1}{2\pi}\,\int _{-\infty }^{\infty }\!{\frac {\Gamma  \left(b/2+ix
 \right) \Gamma  \left( b/2-ix \right) {{\rm e}^{ \left( b/2+ix
 \right) \ln  \left( z \right) }}}{{b}^{2}/4+{x}^{2}}}{dx}
={\frac {\Gamma  \left( b \right) \ln  \left( z \right) }{b}}-{
\frac {\Psi \left( b \right) \Gamma  \left( b \right) }{b}}-{\frac {
\gamma\,\Gamma  \left( b \right) }{b}}+{\frac {\Gamma  \left( b
 \right) }{{b}^{2}}}+
\frac{\Gamma  \left( b \right) b}{z(b+1)}
\;{\mbox{$_4$F$_3$}\left(1,1,b+1,b+1;\,2,2,b+2;\,-\frac{1}{z}\right)}
$$
Numerically, this seems to agree with the formula given in the question.


text:
{\bf Problem.} Given the function $f(x)=3x^3+2$, find the value of $x$ so that $f^{-1}(x)=4$.
{\bf Level.} Level 4
{\bf Type.} Algebra
{\bf Solution.} The equation $f^{-1}(x)=4$ is equivalent to $x=f(4)$.  Therefore we want to find the value $f(4)$. We compute $f(4) = 3 \cdot 4^3 + 2 = \boxed{194}$.

set_name: MATH


TITLE: What's known about the 3rd coefficient in the BMV conjecture?
QUESTION [3 upvotes]: The most appealing statement of the Bessis-Moussa-Villani conjecture is as follows:

Conjecture: For all Hermitian positive semidefinite $n\times n$ matrices $A$ and $B$,
  and all positive integer $m$, the polynomial function
  $$t \in \mathbb{R}\mapsto g(t) \equiv tr[(A + t B)^m] =
\sum\limits_{
k=0}^m
a_kt^k$$
  has only nonnegative coefficients $a_k, k=1,\cdots,m$.

Most recent and past research concerns on the quantities $m$ and $n$. What about trying to prove the conjecture in the following way: first show that $a_m\ge0$, $a_0\ge0$, $a_{m-1}\ge0$, $a_1\ge0$, $a_{m-2}\ge0$, $a_2\ge0$. And then go on to show $a_3\ge 0$ (and so is $a_{m-3}\ge 0$)...
But it seems difficult to show $a_3\ge 0$. Can anyone share some idea on this particular coefficient?
UPDATED
What is the largest term in $S_{2m,m}(AB)$ ? More precisely, consider the word in two positive definite letters $A^{k_1}BA^{k_2}B\cdots A^{k_m}B$ , where $(k1,k2,\cdots,k_m)$  is a pair of nonnegative integer solution of $k_1+k_2+\cdots+k_m=m$ . Is it true that $tr(A^{k_1}BA^{k_2}B\cdots A^{k_m}B)\le tr(A^mB^m)$ ?

REPLY [3 votes]: There is a proof of the full BMV conjecture by Herbert Stahl
http://prof.beuth-hochschule.de/stahl/
on the preprint server that was added end of July 2011:
http://arxiv.org/abs/1107.4875
I have no opinions from colleagues about the proof so far.


TITLE: How to determine if two points lie in a particular section of circle.
QUESTION [1 upvotes]: I'll take assistance from the figure below.
 O is the center of the circle, and A,B,C are the points on the circle, and are known. i.e. the x,y coordinates of these three points are known. I want to know, that for the center point O, and any other point, say a,b,c [small characters], if O and that particular point is in the same region.
To add to the assumption, let us say, AB and the other line are horizontal or vertical. i.e. parallel to the X and Y axis.
Also, what if I remove this assumption?
Thanks.
EDIT I guess, for the given assumption, I could just check if the other point (not the center) has the x and y coordinates, in range of the A B and C, towards the side of center. That is, if center has coordinate value more for A and not for B and not for C, then so should the other point? Will that be correct?
What if the assumption is false?

REPLY [1 votes]: You can just calculate which side of $AB$ the point is on.  If $AB$ is horizontal, you just check the $y$ coordinate of the point.  If $AB$ is not horizontal, you have the line AB as $y-y_A=\frac {y_B-y_A}{x_B-x_A}(x-x_A)$  A point is above the line if the left side is greater than the right.
The line through $C$ you check the same way.  If it is vertical, just check the $x$ coordinate.  If it is not, there is nothing to specify its slope and you need to fix that, but the idea is the same.