text:
\DOC deep_alpha

\TYPE {deep_alpha : (string * string) list -> term -> term}

\SYNOPSIS
Modify bound variable according to renaming scheme.

\DESCRIBE
When applied to a list of string-string pairs
{
  deep_alpha ["x1'","x1"; ...; "xn'","xn"]
}
\noindent a conversion results that will attempt to traverse a term and
systematically replace any bound variable called {xi} with one called {xi'}. It
will quietly do nothing in cases where that is impossible because of variable
capture.

\EXAMPLE
{
  # deep_alpha ["x'","x"; "y'","y"] `?x. x <=> !y. y = y`;;
  Warning: inventing type variables
  val it : term = `?x'. x' <=> (!y'. y' = y')`
}

\COMMENTS
This is used inside {PART_MATCH} to try to achieve a reasonable correspondence
in bound variable names, e.g. so that the bound variable is still called `{n}'
rather than `{x}' here:
{
  # REWR_CONV NOT_FORALL_THM `~(!n. n < m)`;;
  val it : thm = |- ~(!n. n < m) <=> (?n. ~(n < m))
}

\SEEALSO
alpha, PART_MATCH.

\ENDDOC

subset_name: curated


TITLE: Concrete math generalized josephus recursion understanding 1.15
QUESTION [0 upvotes]: I am studying through the josephus problem in concrete math , Here is the equation of binary form
$$f(1) = α ;$$
$$f(2n + j) = 2f(n) + β_j ,$$
$$\text{ for } j = 0, 1 \text{ and } n \geq 1$$
this part I understand , now the unfolding of the recurrence
\begin{align*}f(b_m b_{m−1}...b_1 b_0)_2 &= 2f(b_m b_{m−1} . . . b_1)_2+ β_{b_0}\\&=4f(b_mb_{m−1}...b_2)_2 + 2β_{b_1} + β_{b_0}\\&=
2^mf((b_m)_2) +2^{m−1}β_{b_{m−1}} + · · · +2β_{b_1}+β_{b_0}
\\&=2^mα + 2^{m−1}β_{b_{m−1}} + · · · + 2β_{b_1} + β_{b_0}\end{align*}
I mean what just happened here ?where did this $β_{b_0}$ came from ?There was just two constants $α$ , $β$ and now there are many. Can someone explain pease?

REPLY [1 votes]: You have $j \in \{0, 1\},$ so you have $\beta_0, \beta_1.$ From the fact that $b_m b_{m−1}\dots b_1 b_0$ is a binary representation of $2n + j$ we have that to get $n$ from $2n + j$ we need to shift bits right and LSB (least significant bit) goes to subscript of $\beta.$ E.g.
$$f(101) = 2f(10) + \beta_1.$$


TITLE: Positive Totient function?
QUESTION [1 upvotes]: We know that:
$$\phi(n) = n(1- 1/p_1)(1-1/p_2)\ldots(1 - 1/p_k)$$
where $\phi$ is the Euler totient function and $p_i$ are the primes dividing $n$.
Is anything known about the similar function
$$\varphi(n)= n(1+1/p_1)(1+1/p_2)\ldots (1+1/p_k)?$$
I'm just looking reading material and references. Does it have a name?

REPLY [1 votes]: Next time you have a similar question, you can try to put the few starting values into the search bar on OEIS.org. In this case, you would've found your answer. (Sometimes it is useful to omit the first value due to different conventions, e.g. here the empty product is taken to be $1$.)

From wikipedia:

The Dedekind psi
function is the
multiplicative function on the positive integers defined by
$$\psi(n)=n \prod_{p \mid n}\left(1+\frac{1}{p}\right),$$
where the product is taken over all primes $p$ dividing $n$. (By
convention, $\psi (1)=1$.)

It starts with $\psi(n)=1, 3, 4, 6, 6, 12, 8, 12, 12, 18,\dots$, which is OEIS entry A001615.

The wikipedia article references:

Leonard Eugene Dickson "History of the Theory Of Numbers", Vol. 1, p. 123, Chelsea Publishing 1952.
Journal für die reine und angewandte Mathematik, vol. 83, 1877, p. 288. Cf. H. Weber, Elliptische Functionen, 1901, 244-5; ed. 2, 1008 (Algebra III), 234-5

Similarly, the Mathworld article references:

Cox, D. A. Primes of the Form x2+ny2: Fermat, Class Field Theory and Complex Multiplication. New York: Wiley, p. 228, 1997.

Guy, R. K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 96, 1994.

Sloane, N. J. A. Sequence A001615/M2315 in "The On-Line Encyclopedia of Integer Sequences."


TITLE: Integrating $\int \frac{e^x}{\sqrt{e^{2x}-1}}dx$ with $u$-substitution only
QUESTION [3 upvotes]: I am trying to integrate this with $u$-substitution only
$$\int \frac{e^x}{\sqrt{e^{2x}-1}}dx$$
I looked at my book's answer key and played around with it a bit, but I'm still very confused.
I know I should choose $u$ to be ${\sqrt{e^{2x}-1}}$
When I differentiate that, I get $$\frac{e^{2x}}{\sqrt{e^{2x}-1}}$$
I get lost here, especially with the numerator. Also is there another $u$ value I can choose?

REPLY [1 votes]: $$\text{Let }\begin{bmatrix}u \\ \mathrm du\end{bmatrix}=\begin{bmatrix}e^x\\e^x\mathrm dx\end{bmatrix}\implies \int\dfrac{e^x}{\sqrt{e^{2x}-1}}\mathrm dx=\int\dfrac{1}{\sqrt{u^2-1}}\mathrm du$$
As has been already illustrated by @EeveeTrainer and @PeterForeman the techniques of u-substitution and knowing-the-derivative-of $\cosh^{-1}x$. So, I would present another way to tackle this using trig-substitution.
$$\text{Let }\begin{bmatrix}u\\\mathrm du\end{bmatrix}=\begin{bmatrix}\sec\theta\\\sec\theta\tan\theta\mathrm d\theta\end{bmatrix}\implies \int \dfrac{1}{\sqrt{u^2-1}}\mathrm du=\int \dfrac{\sec\theta\tan\theta}{\sec\theta}\mathrm d\theta$$
Can you proceed?


TITLE: What do we mean when we say that black holes aren't made of anything?
QUESTION [18 upvotes]: I have read this question:

It turns out that black holes aren't really objects, but rather regions in spacetime. In fact, this is so true that black holes are what we call vacuum solutions: there isn't matter anywhere in the spacetime. All of the mass of the black hole is there due to effects of gravity itself. Another way of thinking it is that a black hole is so collapsed that its mass is entirely due to gravitational energy.
It is a bit harder to grasp this concept, but once you get it, the rest is simpler. The black hole stays there because it isn't "made" of anything. There isn't a star just below the event horizon waiting to come out. There is nothing there, but gravity.

What exactly makes a black hole STAY a black hole?
While it is widely accepted that certain black hole solutions are vacuum solutions, known black holes are hypothesized to be collapsed (neutron) stars, so the collapsed remnant must be there somewhere (or maybe it transforms into the energy of the gravitational field).
Question:

What do we mean when we say that black holes aren't made of anything?

REPLY [0 votes]: What do we mean when we say that black holes aren't made of anything?

I risk the answer.
A black hole in general relativity is a spacetime that have gravity (converging geodesics) but no matter (zero stress-energy tensor). The simplest black hole describes the Schwarzschild vacuum metric that represents static spherically symmetric spacetime free of matter.
Now, the point is that spherical symmetry in general relativity is a feature of spacetime and not matter. The matter merely inherits it through Einstein Field equations (EFE).
Imagine a flat Lorentzian spacetime. It has no gravity because its geodesics do not converge. To cause them converging one needs a piece of matter that when compressed to some critical compactness ratio ($r_{S}/R$) gives rise to the initial event horizon at the center. Further compression shifts the event horizon to the surface of the matter ball what is a very sketchy description of the black formation process. The end result of that process is a spacetime without matter disconnected physically by the event horizon from the hypothetical "interior" transient spacetime.


TITLE: Heat transfer and temperature difference of 2 liquids
QUESTION [2 upvotes]: We know that heat transfer is calculated by equation $Q$=$m$×$C_p$×$\Delta$$T$.
Let's perform 2 experiments-
Imagine I have 2 cups with water with same masses(volume). 1 is at 100 degree C and other at .5 degree C. If we pour these 2 cups of water in another bigger cup.how fast it's temperature reaches equilibrium.
Same test I will perform with temperature of second cup at 30 degrees.
Equation says heat transfer will be higher if temperature difference is high. That means 1st experiment will reach equilibrium faster than second.
Is it right? I am completely confused. It really takes less time to cool a cup of tea at 70 degree C than 100 degree C.

REPLY [3 votes]: The equation you give:
$$ Q = m C_p \Delta T $$
just tells us the total amount of heat transferred, and does not tell us anything about the rate at which the heat transfer occurs. To calculate heat flow we have to solve the heat equation. If you do a physics degree this apparently innocent equation will cause you many hours of frustrated head scratching, so in practice we tend to use simple approximations. In everyday life heat flow tends to be well described by Newton's equation:
$$ \frac{dQ}{dt} \propto \Delta T $$
so, as you suggest, the greater the temperature difference the faster the heat flow.
The experiment you describe isn't really a good way of showing this, because if you mix hot and cold liquid in practice the rate of temperature change will be controlled by how fast you do the mixing. Newton's equation would be more useful if you place the two liquids in contact but don't allow them to mix e.g. have a metal (or some other high thermal conductivity) divider between them. In that case you're quite correct that the initial heat flow will be faster at 100°C than at 70°C. However the 100°C system will take longer to cool because the amoutn of heat, $Q \propto \Delta T$, that needs to be transferred is greater with a 100°C difference. The temperature difference as a function of time will look like:
$$ \Delta T(t) = \Delta T_0 e^{-\alpha t} $$
where $\Delta T_0$ is the initial temperature and $\alpha$ is a constant related to the thermal conductivity (large $\alpha$ means high thermal conductivity). If I use this equation to graph the cooling for 70°C and 100°C initial temperatures (choosing a random value of $\alpha$) I get:

So even though the 100°C difference initially cools faster the 70°C difference always reaches any specified temperature difference before the 100°C does.


text:
\begin{document}

 \title
{On plethysm conjectures of Stanley and Foulkes: the $2 \times n$ case}

  \author {Pavlo Pylyavskyy}
\keywords{Plethysm conjecture}
\address{Department of Mathematics, Massachusetts Institute of
  Technology,
Cambridge, MA 02141}
\email{pasha@mit.edu}

\begin{abstract}
We prove Stanley's plethysm conjecture for the $2 \times n$ case, which composed with the work of Black and List provides another proof of Foulkes conjecture for the $2 \times n$ case. We also show that the way Stanley formulated his conjecture, it is false in general, and suggest an alternative formulation.
\end{abstract}

  \maketitle

\section {Introduction}

Denote by $V$ a finite-dimensional complex vector space, and by $S^mV$ its $m$-th symmetric power. Foulkes in \cite{Foulk} conjectured that the $GL(V)$-module $S^n(S^mV)$ contains the $GL(V)$-module $S^m(S^nV)$ for $n \geq m$. For $m = 2, 3$ and $4$ the conjecture was proved; see \cite{Th}, \cite{DS}, \cite{B}. An extensive list of references can be found in \cite{V}.

In \cite{BL} Black and List showed that Foulkes conjecture follows from the following combinatorial statement. Denote $I_{m,n}$ to be the set of dissections of $\{1, \ldots, mn\}$ into sets of cardinality $m$. Let $s = \bigsqcup_{i=1}^n S_i$ and  $t = \bigsqcup_{i=1}^m T_i$ be elements of $I_{m,n}$ and $I_{n,m}$ respectively. Define matrix $M^{m,n} = (M_{t,s}^{m,n})$ by
$$
M_{t,s}^{m,n} =
\begin{cases}
1 & \text{if $|S_i \cap T_j|=1$ for any $1 \leq i \leq n, 1 \leq j \leq m$;}\\
0 & \text{otherwise.}
\end{cases}
$$

\begin{theorem}[Black, List 89]
If the rank of $M^{m,n}$ is equal to $|I_{n,m}|$ for integers $n \geq m > 1$, then Foulkes conjecture holds for all pairs of integers $(n,r)$ such that $1 \leq r \leq m$.
\end{theorem}

Let $\lambda$ be a partition of $N$. A {\it {tableau}} is a filling of a Young diagram of shape $\lambda$ with numbers from $1$ to $N$, and let $T_{\lambda}$ to be the set of such tableaux. Define two tableaux to be $h$-equivalent, denoted $\equiv_h$, if they can be obtained one from the other by permuting elements in rows and permuting rows of equal length. Define a {\it {horizontal tableau}} to be an element of $H_{\lambda} := T_{\lambda}/\equiv_h$. In other words, rows of a horizontal tableau form a partition of the set $\{1, \ldots, N\}$. Similarly, define $v$-equivalence $\equiv_v$ and the set $V_{\lambda} := T_{\lambda}/\equiv_v$ of {\it {vertical tableaux}} of shape $\lambda$. Consider a horizontal tableau $\mu$ with rows $r_1, \ldots, r_p$ and a vertical tableau $\nu$ with columns $c_1, \ldots, c_q$. Call $\mu$ and $\nu$ {\it {orthogonal}}, denoted $\mu \perp \nu$, if the inequality $|r_i \cap c_j| \leq 1$ holds for all $i, j$ . Equivalently, $\mu$ and $\nu$ are orthogonal if and only if there exists a tableau $\rho$ consistent with both $\mu$ and $\nu$.

Define the matrix $K_{\lambda} = (K_{\lambda}^{\mu, \nu})$ by
$$
K_{\lambda}^{\mu, \nu} =
\begin{cases}
1 & \text{if $\mu \perp \nu$;}\\
0 & \text{otherwise.}
\end{cases}
$$

The rows of $K_{\lambda}$ are naturally labelled by horizontal tableaux, while the columns are labelled by vertical tableaux. Let $\lambda'$ be the conjugate partition. In \cite{Stan}, Stanley formulated a conjecture, which can be equivalently stated as follows.

\begin{conjecture} \label{conj1}
If $\lambda \geq \lambda'$ in dominance order, i.e. $\lambda_1 + \cdots + \lambda_i \geq \lambda'_1 + \cdots + \lambda'_i$ for all $i$, then the rows of $K_{\lambda}$ are linearly independent.
\end{conjecture}

This conjecture is false. For the shape $\lambda$ shown in Figure \ref{lambda}, the inequality $\lambda \geq \lambda'$ holds. However, the matrix $K_{\lambda}$ has more rows than columns, thus the rows cannot be linearly independent. Indeed, $|H_{\lambda}| = \frac{12!}{6!2!2!1!1!2!2!}$, which is greater than $|V_{\lambda}| = \frac{12!}{5!3!1!1!1!1!4!}$. This counterexample was suggested by Richard Stanley as the smallest possible one. The following conjecture seems to be a reasonable alternative formulation, although there is some evidence that it is also false in general, see \cite{N}.

\begin{figure}
\begin{center}
\input{lambda.pstex_t}
\end{center}
\caption{A counterexample for Stanley's conjecture.}\label{lambda}
\end{figure}

\begin{conjecture} \label{conj2}
$K_{\lambda}$ has full rank for all $\lambda$.
\end{conjecture}

Let $\bm {m \times n}$ denote the rectangular shape with $m$ rows and $n$ columns. For rectangular shapes, Stanley's conjecture  implies Foulkes conjecture since $K_{\bm {m \times n}} = M^{m,n}$. For hook shaped $\lambda$, the conjecture is known to be true; see \cite{Stan}. In Section 2 we present a proof of Stanley's conjecture for $\lambda = {\bm {2 \times n}}$.

The author would like to thank Prof. Richard Stanley for the inspiration and many helpful suggestions.

\section{The Main Result}

Our aim is to prove the following theorem.

\begin{theorem} \label{thm}
Conjecture \ref{conj2} is true for $\lambda = {\bm {2 \times n}}$.
\end{theorem}

Note that for rectangular shapes, Conjectures \ref{conj1} and \ref{conj2} are equivalent, because for $m \leq n$, the inequality $|H_{\bm {m \times n}}| \leq |V_{\bm {m \times n}}|$ holds. Therefore, proving that $K_{{\bm {2 \times n}}}$ has full rank is equivalent to proving that its rows are linearly independent. Suppose for contradiction that there is a nontrivial linear combination of rows of $K_{{\bm {2 \times n}}}$ equal to $0$. Let $\tau_{\mu}$ be the coefficient of the row corresponding to a horizontal tableau $\mu$ in this combination. Then for a column of $K_{{\bm {2 \times n}}}$ labelled by a vertical tableau $\nu$, the linear combination $\sum_{\mu} K_{{\bm {2 \times n}}}^{\mu, \nu} \tau_{\mu}$ equals $0$. Alternatively, this sum can be written as $\sum_{\mu \perp \nu} \tau_{\mu} = 0$. Call a $0$-{\it {filter}} a condition on horizontal tableax such that sum of $\tau_{\mu}$ over all $\mu$ satisfying this condition is $0$. Thus, orthogonality to $\nu$ is a $0$-filter. Our aim is to show that being $\mu$ is a $0$-filter for every horizontal tableau $\mu$. Indeed, this is just saying that all $\tau_{\mu}$ are equal to $0$, which contradicts the assumption above.

\begin{definition}
For $k<n$, a {\it {subtableau}} of shape ${\bm {2 \times k}}$ of a vertical tableau $\nu$ of shape ${\bm {2 \times n}}$ is a subset of $k$ columns of $\nu$. A {\it {partial tableau}} is a collection of $k$ columns which is a subtableau of at least one vertical tableau $\nu$.
\end{definition}

In other words, a partial tableau is a vertical tableau of shape ${\bm {2 \times k}}$, filled with numbers from $\{1, \ldots, 2n\}$. We can now generalize the concept of orthogonality as follows. Call a horizontal tableau $\mu$ of shape ${\bm {2 \times n}}$ orthogonal to a partial tableau $\nu'$ of shape ${\bm {2 \times k}}$, where $k < n$, if there exists vertical tableau $\nu$ of shape ${\bm {2 \times n}}$ such that $\mu \perp \nu$, and $\nu'$ is a subtableau of $\nu$. An example is presented in Figure \ref{fig2}. The reason for considering such a generalization is evident from the following theorem.

\begin{figure}
\begin{center}
\input{partial.pstex_t}
\end{center}
\caption{Partial tableau $\nu'$ is a subtableau of $\nu$. Since $\mu \perp \nu$, also $\mu \perp \nu'$.} \label{fig2}
\end{figure}

\begin{theorem}
Orthogonality to a certain partial tableau $\nu'$ is a $0$-filter.
\end{theorem}

\begin{proof}
For a given partial tableau $\nu'$ of shape ${\bm {2 \times k}}$, denote $$F(\nu') = \{\nu \in V_{{\bm {2 \times n}}} \mid \text{ $\nu'$ is a subtableau of $\nu$}\}.$$ Consider the sum $\sum_{\nu \in F(\nu')} \sum_{\mu \perp \nu} \tau_{\mu}$. We claim that for each horizontal tableau $\mu$, $\tau_{\mu}$ enters this sum with the same coefficient. Indeed, the coefficient of a particular $\tau_{\mu}$ is the number of tableaux $\nu$ containing $\nu'$ and orthogonal to $\mu$. Such $\nu$'s are in one-to-one correspondance with matchings between two sets of size $n-k$, as can be seen from the Figure \ref{fig3}. The number of such matchings is $(n-k)!$, which obviously does not depend on particular $\mu$. Therefore, $\frac{1}{(n-k)!} \sum_{\nu \in F(\nu')} \sum_{\mu \perp \nu} \tau_{\mu} = \sum_{\mu \perp \nu'} \tau_{\mu}$. Since each $\sum_{\mu \perp \nu} \tau_{\mu}$ is zero by the assumption above, the sum $\sum_{\mu \perp \nu'} \tau_{\mu}$ is also $0$, which means that orthogonality to $\nu'$ is a $0$-filter.

\begin{figure}
\begin{center}
\input{match.pstex_t}
\end{center}
\caption{Each matching corresponds to exactly one possible tableau $\nu \perp \mu$ containing $\nu'$ as a subtableau.} \label{fig3}
\end{figure}
\end{proof}

We now continue the proof of Theorem \ref{thm}. Choose a particular horizontal tableau $\mu_0$, for example with one row filled with numbers $1, \ldots, n$ and the other row filled with the rest of the numbers. If we show that $\tau_{\mu_0} = 0$, then in a similar fashion (just by relabelling numbers) we can show that all $\tau_{\mu}$'s are $0$, which would be a contradiction with the assumption that the combination of rows of  $K_{{\bm {2 \times n}}}$ is nontrivial. For a given horizontal tableau $\mu$, let $a_{\mu}$ and  $b_{\mu}$ be the numbers of elements of $\{1, \ldots, n\}$ in the rows of $\mu$, so that $a_{\mu} +  b_{\mu} = n$. We do not distinguish between the rows of $\mu$, therefore we can assume that $a_{\mu} \geq b_{\mu}$. Observe that $\mu_0$ is the only horizontal tableau such that $(a_{\mu_0}, b_{\mu_0}) = (n, 0)$. Let $T_a$ be the collection of horizontal tableaux $\mu$ with $a_{\mu} = a$, and call elements of $T_a$ {\it {horizontal tableaux of type}} $a$. Then $\mu_0$ is the only horizontal tableau of type $n$.

\begin{theorem}
For $a \geq n/2$, being a horizontal tableau of type $a$ is a $0$-filter.
\end{theorem}

\begin{proof}
For $k \leq [n/2]$, consider the set $P_k$ of all possible partial tableaux of shape ${\bm {2 \times k}}$, filled with numbers from $\{1, \ldots, n\}$. Consider the sum $\sum_{\nu' \in P_k} \sum_{\mu \perp \nu'} \tau_{\mu}$. We claim that only $\tau_{\mu}$'s for $\mu$ of type at most $n - k$ appear in this sum. We also claim that the coefficient of $\tau_{\mu}$ in the sum depends only on the type of $\mu$.

The first statement is easy to verify. Let $\mu$ be orthogonal to some $\nu' \in P_k$. Then each of the two rows of $\mu$ contains at least $k$ numbers from $\{1, \ldots, n\}$, which means it cannot have type larger than $n-k$. As for the second statement, we can calculate exactly the number of different $\nu' \in P_k$ that are orthogonal to a given $\mu$ of type $a$. Indeed, first choose an unordered $k$-tuple among the $n-a$ elements of $\{1, \ldots, n\}$ in one row of $\mu$. Then match them with a ordered $k$-tuple taken from the $a$ elements of  $\{1, \ldots, n\}$ in the other row. Obviously, such a procedure gives all possible $\nu'$, each exactly once. Therefore, the coefficient of $\tau_{\mu}$ which we are looking for is $c_a^{k} = \frac{(n-a)!a!}{k!(n-a-k)!(a-k)!}$.

We now proceed by induction. For the base case, take $k = [n/2]$. The only horizontal tableaux in the sum $\sum_{\nu' \in P_k} \sum_{\mu \perp \nu'} \tau_{\mu}$ are those of type $n - [n/2]$. Since they all have the same coefficient, and $\sum_{\nu' \in P_k} \sum_{\mu \perp \nu'} \tau_{\mu} = 0$ because each $\sum_{\mu \perp \nu'} \tau_{\mu} = 0$, we conclude that $\sum_{\mu \in T_{n - [n/2]}} \tau_{\mu} = 0$.

Given that being a type $a$ tableau is a $0$-filter for $n - [n/2] \leq a \leq a' < n$, let us show that being a type $a' + 1$ tableau is a $0$-filter. Indeed, $\sum_{\nu' \in P_{n-a'-1}} \sum_{\mu \perp \nu'} \tau_{\mu} = 0$ as before. This equality can be written as $\sum_{n- [n/2] \leq a \leq a'+1} c_a^{n-a'-1} \sum_{\mu \in T_a} \tau_{\mu} = 0$, where $c_a^{n-a'-1}$ is the coefficient calculated above. By the induction assumption, we know that for $n - [n/2] \leq a \leq a'$, the sum $\sum_{\mu \in T_a} \tau_{\mu}$ is $0$. Since $c_{a'+1}^{n-a'-1} \not = 0$, we conclude that $\sum_{\mu \in T_{a'+1}} \tau_{\mu} = 0$.
\end{proof}

A trivial observation to make is that for $a = n$ this theorem implies that $\tau_{\mu_0} = 0$, which leads to the desired contradiction. Therefore, rows of $K_{{\bm {2 \times n}}}$ are linearly independent, which proves Theorem \ref{thm}.

\begin {thebibliography}{[L]}

\bibitem {B}
E. Briand: {\it Polynomes multisymetriques}, Ph. D. dissertation, University of Rennes I, Rennes, France, 2002.

\bibitem {BL}
S. C. Black and R. J. List: A note on plethysm, {\it  European Journal of Combinatorics} {\bf 10} (1989), no. 1, 111--112.

\bibitem {DS}
S. C. Dent and J. Siemons: On a conjecture of Foulkes, {\it  Journal of Algebra} {\bf 226} (2000), 236-249.

\bibitem {Foulk}
H. O. Foulkes: Concomitants of the quintic and sextic up to degree four in the coefficients of the ground form, {\it Journal of London Mathematical Society} {\bf 25} (1950), 205--209.

\bibitem {N}
M. Neunhoffer: Some calculations regarding Foulkes' conjecture, http://www.math.rwth-aachen.de/~Max.Neunhoeffer/talks/goslar2004print.pdf

\bibitem {Stan}
R. Stanley:  Positivity problems and conjectures in algebraic combinatorics,
{\it Mathematics: Frontiers and Perspectives}, American Mathematical Society, Providence, RI, 2000, pp. 295-319.

\bibitem {Th}
R. M. Throll: On symmetrized Kronecker powers and the structure of the free Lie ring, {\it  American Journal of Mathematics} {\bf 64} (1942), 371-388.

\bibitem {V}
R. Vessenes: Generalized Foulkes' conjecture and tableaux construction, http://etd.caltech.edu/etd/available/etd-05192004-121256/unrestricted/Chapter1.pdf

\end {thebibliography}

\end {document}

config: arxiv


TITLE: convergence of $ \sum_{k=1}^{\infty}{ \frac{1}{\sqrt{k(k+1)}} } $
QUESTION [0 upvotes]: I want to prove that $\sum_{k=1}^{\infty}{ \frac{1}{\sqrt{k(k+1)}}  }$ converges. How can I do that?
I have simplified that into:
$\sum_{k=1}^{\infty}{ \frac{1}{\sqrt{k(k+1)}}  } = \sum_{k=1}^{\infty}{ \frac{1}{\sqrt{k^2+k}}  } < \sum_{k=1}^{\infty}{ \frac{1}{k^2+k}  }$
If I show that $\sum_{k=1}^{\infty}{ \frac{1}{k^2+k}  }$ converges
then $\sum_{k=1}^{\infty}{ \frac{1}{\sqrt{k(k+1)}}  }$ must converge, right?
How can I go on ?
I have tried the quotient criterium which gives me equals $1$. So it is not very helpful here.

REPLY [1 votes]: With equvalents:
$\sqrt{k(k+1)}\sim_\infty\sqrt{k^2}=k$, so
$\;\dfrac 1{\sqrt{k(k+1)}}\sim_\infty\frac 1k,\; $
and the harmonic series diverges.


text:
\section{Mixture models}\label{KPCA-sec-GMM}

\subsection{Sub-Gaussian mixture model}\label{KPCA-sec-GMM-sGMM}

Sub-Gaussian and Gaussian mixture models serve as testbeds for clustering algorithms.
Maximum likelihood estimation requires well-specified models and often involves non-convex or combinatorial optimization problems that are hard to solve. The recent years have seen a boom in the study of efficient approaches.
The Lloyd's algorithm \citep{Llo82} with good initialization and its variants are analyzed under certain separation conditions \citep{KKa10, LZh16, Nda18, GZh19}.

Semi-definite programming (SDP) yields reliable results in more general scenarios \citep{ABC15, MVW17, Roy17, FCh18, GVe18, CYa18, CYa20}.

Spectral methods
are more efficient in terms of computation and have attracted much attention \citep{VWa04, CZh18, LZZ19, SSH19}. However, much less is known about spectral methods compared with SDP.

\input{main-kmeans}

\subsection{Gaussian mixture model}\label{KPCA-sec-GMM-GMM}

The symmetries and other structural properties of Gaussian mixture models allow for more precise characterizations than the above. While a main focus of interest is parameter estimation by likelihood-based methods \citep{DLR77} and methods of moments \citep{Pea94},

the problem of clustering is less explored.

Recently there is a surge of interest in sharp statistical guarantees, mostly under the isotropic Gaussian mixture model \citep{LZh16,CZh18,Nda18,LZZ19,CYa20}.
In another line of study, sparsity assumptions are adopted for high-dimensional regimes \citep{ASW13, JWa16}.
We study spectral clustering under the following model.

\begin{definition}[Gaussian mixture model]\label{KPCA-defn-GMM}
For $\by \in \{ \pm 1 \}^n$ and $\bmu \in \RR^d$ with $n, d \geq 2$, we write $\{ \bx_i \}_{i=1}^n \sim \mathrm{GMM} ( \bmu, \by )$ if
\begin{align}
\bx_i = y_i \bmu + \bz_i \in \RR^d ,\qquad i \in [n],
\label{KPCA-sec-GMM-1}
\end{align}
and $\{ \bz_i \}_{i=1}^n \subseteq \RR^d$ are i.i.d. $N(\mathbf{0} , \bI_d)$ vectors.
\end{definition}

It is natural to use the spectral estimator $\hat{\by} = \sgn(\bu_1)$ to recover $\by$, where $\bu_1$ is the leading eigenvector of $\bG = \cH ( \bX \bX^{\top} )$. This method can be viewed as a special case of the spectral algorithm  in Section~\ref{KPCA-sec-GMM-sGMM} that uses $k$-means for two classes and symmetric centroids. To gauge the misclassification rate of $\hat\by$, define
\begin{align}
& \cM ( \hat{\by} , \by ) = \min_{s = \pm 1}
|\{
i \in [n] :~ \hat y_i \neq s y_i
\}|.
\label{eqn-gmm-mismatch}
\end{align}
Note that for the Gaussian mixture model \eqref{KPCA-sec-GMM-1}, $\bar{\bx}_i = y_i \bmu$, $\bar\bX = \by \bmu^{\top}$ and $\bar\bG = \bar\bX \bar\bX^{\top} = \| \bmu \|_2^2 \by \by^{\top}$. Then $\bar\lambda_1 = n \| \bmu \|_2^2$ and $\bar\bu_1 = \by / \sqrt{n}$.

\begin{theorem}\label{KPCA-thm-GMM}
Let $\{ \bx_i \}_{i=1}^n \sim \mathrm{GMM} ( \bmu, \by )$ and $n \to \infty$. Define
\begin{align}
\mathrm{SNR} = \frac{ \| \bmu \|_2^4 }{ \| \bmu \|_2^2 + d / n }.
\label{KPCA-snr-gmm}
\end{align}
	\begin{enumerate}
		\item If $\mathrm{SNR} > (2 + \varepsilon) \log n$ for some constant $\varepsilon > 0$, then $\lim_{n \to \infty} \PP [ \cM (  \hat\by, \by ) = 0 ] = 1$;
		\item If $1 \ll \mathrm{SNR} \leq 2 \log n$, then $\limsup_{n\to\infty} \mathrm{SNR}^{-1} \log \EE \cM ( \hat\by , \by ) \leq - 1 / 2$.
	\end{enumerate}
\end{theorem}

Theorem \ref{KPCA-thm-GMM} characterizes the spectral estimator with explicit constants. Here we do not impose any specific assumption on the dimension $d=d_n$ so long as $\mathrm{SNR} \to \infty$. It may be bounded or diverge at any rate. When $\mathrm{SNR}$ exceeds $2\log n$, $\sgn(\bu_1)$ exactly recovers all the labels (up to a global sign flip) with high probability. When $1 \ll \mathrm{SNR} \leq 2 \log n$, the misclassification rate is bounded from above by $e^{ - \mathrm{SNR} / [2 + o(1)] }$. According to \cite{Nda18}, both results are optimal in the minimax sense. The proof of Theorem \ref{KPCA-thm-GMM} is in Appendix \ref{KPCA-thm-GMM-proof}.

\cite{CZh18} prove that $\mathrm{SNR} \to \infty$ is necessary for any estimator to achieve vanishingly small misclassification rate and derive an upper bound $\EE \cM ( \sgn (\tilde{\bu}_1) , \by ) \lesssim 1/\mathrm{SNR}$ for $\tilde{\bu}_1$ being the leading eigenvector of the unhollowed Gram matrix $\bX \bX^{\top}$. \cite{Nda18} obtains exact recovery guarantees as well as an optimal exponential error bound for an iterative algorithm starting from $\sgn(\bu_1)$. Our analysis shows that the initial estimator is already good enough and no refinement is needed. \cite{CYa20} study the information threshold for exact recovery in multi-class setting and use an SDP to achieve that.

The $\mathrm{SNR}$ in (\ref{KPCA-snr-gmm}) is closely related to (indeed equivalent to in the order of magnitude) that in (\ref{eqn-kmeans-SNR-2}). One can immediately see this by setting $\bmu_1 = \bmu$, $\bmu_2 = - \bmu$ and $\bSigma = \bI_d$ in (\ref{eqn-kmeans-SNR-2}). The $\mathrm{SNR}$ precisely quantifies the signal-to-noise ratio for clustering and is always dominated by the classical one $\| \bmu \|_2^2$. When $d \gg n$, the condition $\mathrm{SNR} \to \infty$ is equivalent to
\begin{align}
\| \bmu \|_2 \gg (d/n)^{1/4}.
\label{KPCA-snr-gmm-1}
\end{align}
This is weaker than the commonly-used assumption
\begin{align}
\| \bmu \|_2 \gg \sqrt{d/n}
\label{KPCA-snr-gmm-2}
\end{align}
for clustering \citep{LZh16, LZZ19}, under which $\mathrm{SNR}$ is asymptotically equivalent to $\| \bmu \|_2^2$. Their discrepancy reflects an interesting high-dimensional phenomenon.

For the Gaussian mixture model in Definition \ref{KPCA-defn-GMM}, parameter estimation and clustering amount to recovering $\bmu \in \RR^d$ and $\by \in \{ \pm 1 \}^n$, respectively. A good estimate of $\bmu$ yields that of $\by$. Hence clustering should be easier than parameter estimation. The difference becomes more significant when $d \gg n$ as clustering targets fewer unknowns. To see this, we write $\bX = (\bx_1,\cdots,\bx_n)^{\top} \in \RR^{n\times d}$ and observe that
\[
\bX = \by \bmu^{\top} + \bZ,
\]
where $\bZ = (\bz_1,\cdots,\bz_n)^{\top} \subseteq \RR^{n \times d}$ has i.i.d. $N(0,1)$ entries. Clustering and parameter estimation correspond to estimating the left and right singular vectors of the signal matrix $\EE \bX$. According to the results by \cite{CZh18} on singular subspace estimation, (\ref{KPCA-snr-gmm-1}) and (\ref{KPCA-snr-gmm-2}) are sharp conditions for consistent clustering and parameter estimation. They ensure concentration of the Gram matrix $\bX \bX^{\top}$ and the covariance matrix $\frac{1}{n}\bX^{\top} \bX$.
When $(d/n)^{1/4} \ll \| \bmu \|_2 \ll \sqrt{d/n}$, consistent clustering is possible even without consistent estimation of the model parameter $\bmu$. Intuitively, there are many discriminative directions that can tell the classes apart but they are not necessarily aligned with the direction of $\bmu$.

Below we outline the proof of Theorem \ref{KPCA-thm-GMM}. The following $\ell_p$ approximation result for the regime $1 \ll \mathrm{SNR} \lesssim \log n$ helps illustrate main ideas. Its proof is deferred to Appendix \ref{KPCA-thm-GMM-Lp-proof}.

\begin{theorem}\label{KPCA-thm-GMM-Lp}
	Under the GMM model in Definition \ref{KPCA-defn-GMM} with $n \to \infty$ and $1 \ll \mathrm{SNR} \lesssim \log n$, there exist $\varepsilon_n \to 0$ and positive constants $C, N$ such that
	\begin{align*}
	\PP ( \| \bu_1 - \bG \bar\bu_1 / \bar\lambda_1 \|_{\mathrm{SNR}} < \varepsilon_n \| \bar\bu_1 \|_{\mathrm{SNR}} ) > 1 - C e^{-\mathrm{SNR}}, \qquad \forall n \geq N.
	\end{align*}
\end{theorem}

In a hand-waving way, the analysis right after (\ref{eqn-intro-Lp}) in the introduction suggests that the expected misclassification rate of $\sgn(\bu_1)$ differs from that of $\sgn(\bG \bar\bu_1 / \bar\lambda_1)$ by at most $O( e^{-\mathrm{SNR}} )$.
Then, it boils down to studying $\sgn(\bG \bar\bu_1 / \bar\lambda_1)$.
Note that
\begin{align*}
( \bG \bar\bu_1 / \bar\lambda_1 )_i  \propto
( \bG \by )_i = \sum_{j=1}^{n} [ \cH ( \bX \bX^{\top}) ]_{ij} y_j = \sum_{j \neq i} \langle \bx_i, \bx_j  y_j \rangle
= (n-1) \langle \bx_i, \hat\bmu^{(-i)} \rangle,~~ \forall i \in [n].
\end{align*}
Here $\hat\bmu^{(-i)} = \frac{1}{n-1} \sum_{j \neq i} \bx_j y_j$ is an estimate of $\bmu$ based on the samples $\{ \bx_j \}_{j \neq i}$ and their labels $\{ y_j \}_{j \neq i}$. It is straightforward to prove
\begin{align*}
\EE \cM ( \sgn(\bG \bar\bu_1 / \bar\lambda_1), \by ) = \frac{1}{n} \sum_{i=1}^{n} \PP [ \sgn(\langle \bx_i, \hat\bmu^{(-i)} \rangle) \neq y_i ] \leq e^{-\mathrm{SNR} / [2 + o(1)]}
\end{align*}
and get the same bound for $\EE \cM ( \sgn(\bu_1), \by )$. When $\mathrm{SNR} > (2+\varepsilon) \log n$, this leads to an $n^{-(1+\varepsilon/2)}$ upper bound for the misclassification rate, which implies exact recovery with high probability as any misclassified sample contributes $n^{-1}$ to the error rate. When $\mathrm{SNR} \leq 2 \log n$, we get the second part in Theorem \ref{KPCA-thm-GMM}. The proof is then finished.

The quantity $ \sgn( \langle \bx_i, \hat\bmu^{(-i)} \rangle )$ is the prediction of $y_i$ by linear discriminant analysis (LDA) given features $\{ \bx_i \}_{i=1}^n$ and additional labels $\{ y_j \}_{j \neq i}$. It resembles an oracle (or genie-aided) estimator that is usually linked to the fundamental limits of clustering \citep{ABH16, ZZh16}, which plays an important role in our analysis as well. By connecting $\bu_1$ with $ \bG \bar\bu_1 / \bar\lambda_1$ and thus $\{ \langle \bx_i, \hat\bmu^{(-i)} \rangle \}_{i = 1}^n$, Theorem \ref{KPCA-thm-GMM-Lp} already hints the optimality of $\sgn( \bu_1 )$. Our analysis may also apply to spectral algorithms in similar problems such as the bipartite stochastic block model \citep{NST21}.

Perhaps surprisingly, both the (unsupervised) spectral clustering and (supervised) LDA achieve the minimax optimal misclassification error $e^{-\mathrm{SNR} / [2 + o(1)]}$. The missing labels do not hurt much. This phenomenon is also observed by \cite{Nda18}. On the other hand, the Bayes classifier $\sgn( \langle \bmu , \bx \rangle )$ given the \emph{true} parameter $\bmu$ achieves error rate $1 - \Phi ( \| \bmu \|_2 )$, where $\Phi$ is the cumulative distribution function of $N(0,1)$. As $\| \bmu \|_2 \to \infty$, this is $e^{ - \| \bmu \|_2^2 / [2 + o(1)] }$ and it is always superior to the minimax error without the knowledge of $\bmu$. From there we get the followings for spectral clustering and LDA.
\begin{itemize}
\item If $\| \bmu \|_2 \gg \sqrt{d / n}$, then $\mathrm{SNR} = \| \bmu \|_2^2 [1 + o(1)]$ and both estimators achieve the Bayes error exponent;
\item If $\| \bmu \|_2 \leq C \sqrt{d / n}$ for some constant $C > 0$, then $\mathrm{SNR} \leq \| \bmu \|_2^2 / (1 + C^{-2})$ and both estimators achieve the minimax optimal exponent that is worse than the Bayes error exponent.
\end{itemize}


TITLE: Can we accelerate a particle to a very high speed by applying force just once?
QUESTION [1 upvotes]: Suppose you have a tennis ball in your hand. When one would throw it towards a wall such that it encounter the surface of the wall at almost a right angle, the ball would come back in the same direction.
Now let us suppose the same scenario but as soon I throw the ball, place a similar wall at my place.
Now the ball would bounce back from the first wall and strike the second, bounce back and strike the first wall and this would continue.
Now suppose there is a very very long swimming pool, filled with a fluid which has particles with very less mass, very less inter particle forces of attraction and coefficient of restitution equal to 1.
Now I jump into it and be near one end of the pool.
Now I push the fluid behind me towards the wall of a pool, and as in the case of a ball, the particles will strike the wall with some force F, with Newton's 3rd law, return with F and hit my back with F. I will get accelerated with F/M( where M is my mass).Again with Newton's 3rd law, my back would also push them with F( where my back is acting as the second wall as in the case of the tennis ball) then they would return to the wall then again push me ,accelerating me, and then I would push them.
Since the pool is very long, I would keep on getting pushed and pushed and so increasing my speed and maybe I will beat sound and since it is so long, get somewhat near light.
I know that the coefficient of restitution of my body is not 1 but we can some what increase it to near one by having some sort of suit.
Is this possible? Are there any flaws ? What are they?

REPLY [2 votes]: In your pool example, you can imagine the pool and the waves you've created in it to be like a battery.  The energy you pushed the water with becomes the energy of the wave (which is a combination of kinetic and potential energy).
Assuming you could remove losses, the wave would continue indefinitely.
But as soon as you try to "surf" on it, you are removing the energy.  As the wave accelerates you forward, you are pushing the wave backward.  This pushing removes energy and makes the wave weaker.  At some point, the wave would disappear and can no longer accelerate you.  Your "battery" is empty.


TITLE: Bochner Integral: Measurability
QUESTION [1 upvotes]: Given a measure space $\Omega$.
Consider plain functions $f$.
Define the plain integral as usual:
$$f\geq0:\quad\int f\mathrm{d}\mu:=\sup_{s\leq f}\int s\mathrm{d}\mu$$
Do vanishing integrals imply measurability:
$$\int|f-s_n|\mathrm{d}\mu\to0\implies s_{n_k}\to f\implies f\in\mathcal{M}$$
(Be aware that the usual proof heavily depends upon measurability!)
Have a guess! ;)

REPLY [0 votes]: No, they don't!
Consider a Vitali set $V\subseteq[0,1]$.
Then one has trivially:
$$\int|\chi_V-0|\mathrm{d}\mu\equiv\mu_*(V)=0$$
However, it is not even measurable!


TITLE: Can transcendental functions be approximated to algebraic ones.
QUESTION [0 upvotes]: I just wanted sin(x) in terms of algebraic operations like addition,multiplication,etc.
And can we extract that from the right angled triangle sides ratio definition, sine=altitude/hypotenuse
or we have to involve calculus.

REPLY [2 votes]: If an infinite polynomial is fine with you, we can use the Taylor Series for $\sin(x)$.  It is derived though calculus, however.
$$\sin(x)=\sum_{n=0}^{\infty}\frac{(-1)^{n}x^{2n+1}}{(2n+1)!}=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots$$