TITLE: How matter waves travel faster than light?
QUESTION [2 upvotes]: I read this in my physics textbook. It says that matter waves travel faster than light. Why is it so?
Also are matter waves G-Waves?

REPLY [0 votes]: the book presents de broglie
λ=h/p
in classical form.
in classical mechanics there is no limit for speed.
once you insert the relativistic energy:
E=mc^2+(p^2 c^2)^2
you see that matter waves can not travel faster than light.


TITLE: Pigeonhole principle Q: What is the smallest integer k with the following property: whenever x_1, ... ,x_k are integers between 1 and 15, either (i) …
QUESTION [1 upvotes]: Question:
What is the smallest integer $k$ with the following property: whenever $x_1$, ... ,$x_k$ are integers between 1 and 15, either
(i) there are $i$ and $j$ with $i\neq j$ such that $x_i = x_j$, or
(ii) there are $i$ and $j$ with $i \neq j$ such that $x_i + x_j = 16$?
Your answer should justify that your chosen k has this property, and also that no smaller k has this property.
Where I am at so far:
The pigeonhole principle states that if $n + 1$ pigeons are placed in $n$ pigeonholes, then there exists a pigeonhole which contains at least two pigeons.
Thus take our pigeons to be our choices and the integers between $1$ and $15$ to be pigeonholes. If $16$ pigeons are placed into $15$ pigeonholes then there is some pigeonhole which contains at least two pigeons. This means there is some integer which has been chosen at least two times. This means there is some $i$ and $j$ where $i \neq j$ and $x_i = x_j$.
So I know $k = 16$ is the smallest integer which satisfies the first property. This means the smallest integers which satifies property two has to be at least $16$.
I know that $1$ and $15$, $2$ and $14$, $3$ and $13$, $2$ and $14$, $1$ and $15$, $6$ and $10$, $7$ and $9$ and $8$ and $8$ make $16$. But I don't know where to go from here.

REPLY [3 votes]: I know that 1 and 15, 2 and 14, 3 and 13, 2 and 14, 1 and 15, 6 and 10, 7 and 9 and 8 and 8 make 16.

So let those be the holes. In other words, take the $8$ holes
$$
\{1,15\}, \{2, 14\}, \{3, 13\}, \{4, 12\}, \{5, 11\}, \{6, 10\}, \{7, 9\}, \{8\}
$$
As long as there is only one pigeon in each hole, then all pigeons are different (requirement (i)), and none of them add to $16$ (requirement (ii)). However, the moment you have two pigeons in the same hole, either those two are equal, or they add to $16$. Problem solved.


TITLE: Function $f(t) - kf(1-t) = t$ . Rearrange and find the formula for f(t)
QUESTION [0 upvotes]: Click here to see the question
So for question 2 (ii a), if i say from (i), we know the identity cannot hold when k is + or- 1. Therefore for (*), the equation cannot be valid thus there is no solution. Is it a reasonable answer?
For (c), I tried to expand the $(2t-1)^3$ to $8t^3-12t^2+6t-1$ but then I do not know how to continue.

REPLY [0 votes]: To prove ii)a
$f({1\over2})-f({1\over2})={1\over2}$ contradiction. You should be able to figure out b) based on this.
For c)
Let $f(t)=at^3+bt^2+ct+d$
Then $f(1-t)=-at^3+(b+3a)t^2+(-3a-2b-c)t+(a+b+c+d)$
So $2a=8,-3a=-12,2c+2b+3a=6,-a-b-c=-1$
So $a=4,b+c=-3,d=$anything will work.


text:
\section{Introduction}

Conditional distribution functions and conditional quantiles estimation is an important task in several domains including environment, insurance or industry. It is also an important tool for Quantile Oriented Sensitivity Analysis (QOSA), see e.g., \citet{fort2016new,maume2018estimation,browne2017estimate}. In order to estimate conditional quantiles, various methods exist such as kernel based estimation or quantile regression \citep{koenker2001quantile} but they present some limitations. Indeed, the performance of kernel methods strongly depends on the bandwidth parameter selection and quickly breaks down as the number of covariates increases. On one other hand, quantile regression is not adapted in a non-gaussian setting since the true conditional quantile  is not necessarily a linear combination of the input variables \citep{maume2017quantile}. To overcome these issues, we propose to explore the Random Forest estimation of conditional quantiles \citep{meinshausen2006quantile}.

Random forest algorithms allow a flexible modeling of interactions in high dimension by building a large number of regression trees and averaging their predictions. The most famous random forest algorithm is that of \citet{breiman2001random} whose construction is based on the seminal work of \citet{amit1997shape,ho1998random,dietterich2000ensemble}. Breiman's random forest estimate is a combination of two essential components: Bagging and Classification And Regression Trees (CART)-split criterion \citep{breiman1984classification}. Bagging for \textit{bootstrap-aggregating} was proposed by \citet{breiman1996bagging} in order to improve the performance of weak or unstable learners.

Random forests are also related to some local averaging algorithms such as nearest neighbors methods \citep{lin2006random,biau2010layered} or kernel estimators \citep{scornet2016random}. More precisely, thanks to \citet{lin2006random}, the random forest method can be seen as an adaptive neighborhood regression procedure and therefore the prediction (estimation of the conditional mean) can be formulated as a weighted average of the observed response variables.

Based on that approach, we develop a Weighted Conditional Empirical Cumulative Distribution Function (W\textunderscore C\textunderscore ECDF) approximating the Conditional Cumulative Distribution Function (C\textunderscore CDF). Then, $\alpha$-quantile estimates are obtained by using W\textunderscore C\textunderscore ECDF instead of C\textunderscore CDF. \cite{meinshausen2006quantile} defined a W\textunderscore C\textunderscore ECDF with weights using the original dataset whereas we allow to construct the weights using the bootstrap samples, as it is done practically in regression random forests. We prove the almost sure consistency of these estimators. Both estimators have several advantages over methods such as kernel methods \citep{nadaraya1964estimating,watson1964smooth}. Due to the intrinsic tree building process, random forest estimators can easily handle both univariate and multivariate data with few parameters to tune. Besides, these methods have good predictive power and can outperform standard kernel methods \citep{davies2014random,scornet2016random}. Lastly, being based on the random forest algorithm, they are also easily parallelizable and can handle large dataset. A implementation of both algorithms is made available within a \texttt{Julia} package called \texttt{ConditionalDistributionForest} \citep{ConditionalDistributionForest} as well as a \texttt{python} package named \texttt{qosa-indices}, \citep{qosa_indices}.

The C\textunderscore CDF can be seen as a regression function. On this basis, we were interested in the literature dealing with the consistency of random forest estimates in order to show the convergence of ours estimators. \\
Several authors such as \citet{breiman2004consistency, biau2012analysis, wager2015adaptive, scornet2015consistency, mentch2016quantifying, wager2018estimation,goehry2019random} have established asymptotic properties of particular variants and simplifications of the original Breiman's random forest algorithm. Facing some theoretical issues with the bootstrap, most studies replace it by subsampling, assuming that each tree is grown with $s_n<n$ observations randomly chosen without replacement from the original dataset. Most of the time, in order to ensure the convergence of the simplified model, the subsampling rate $s_n / n$ is assumed to tend to zero at some prescribed rate, assumption that excludes the bootstrap mode. Besides, the consistency is generally showed by assuming that the number of trees goes to infinity which is not fully relevant in practice. Under some conditions, \citet{scornet2016asymptotics} showed that if the infinite random forest regression estimator is $\LL^2$ consistent then so does the finite random forest regression estimator when the number of trees goes to infinity in a controlled way. \\
Recent attempts to bridge the gap between theory and practice, provide some results on random forest algorithms at the price of fairly strong conditions. For example, \citet{scornet2015consistency} showed the $\LL^2$ consistency of random forests in an additive regression framework by replacing the bootstrap step by subsampling. Their result rests on a fundamental lemma developped in \citet{scornet2015supplementary} which reviews theoretical random forest. Highlighted by a counterexample developed in Section \ref{sec:4:consistency}, assumptions are required to get out of the additive framework. Furthermore, consistency and asymptoctic normality of the whole algorithm were recently proved under strong conditions by \citet{wager2018estimation} replacing bootstrap by subsampling and simplifying the splitting step. One of the strong conditions used in the Theorem 3.1. of \citet{wager2018estimation} is that the individual trees satisfy a condition called \textit{honesty}. An example of an honest tree given by the authors is \textit{one where the tree is grown using one subsample, while the predictions at the leaves of the tree are estimated using a different subsample.} Due to this assumption, the authors admit that their theorems are not valid for the practical applications most of the time because almost all implementations of random forests use the training sample twice.

Thus, despite an active investigation during the last decade, the consistency of the original (i.e. with the bootstrap samples) Breiman's random forest method is not fully proved. This motivated our work. \\
Our major contribution is the proof of the almost everywhere uniform convergence of the estimator W\textunderscore C\textunderscore ECDF both using the bootstrap samples (\Cref{theo:4:num_1}) or the original one (\Cref{theo:4:num_2}). To the best of our knowledge, this is the first consistency result under realistic assumptions for a method based on bootstrap samples in the random forest field. Remark that \citet{meinshausen2006quantile} gave of proof of the consistency in probability of the W\textunderscore C\textunderscore ECDF for a simplified model where the weights are considered as constant while they are indeed random variables heavily data-dependent.

The paper is organized as follows. Breiman's random forest algorithm is detailed in Section \ref{sec:2:RF} and notations are stated. The random forest estimations of C\textunderscore CDF based both on bootstrap samples and the original dataset are introduced in Section \ref{sec:3:QRF} as a natural generalization of regression random forests. The main consistency results are presented in Section \ref{sec:4:consistency} and the proofs of those are gathered in Section \ref{sec:5:proofs}. Section \ref{sec:6:num_example} is devoted to a short simulation study and a conclusion is given in Section \ref{sec:7:conclusion}.

config: arxiv


TITLE: How to evaluate: $\int_0^1x^{n-1}(1-x)^{n+1}dx$
QUESTION [2 upvotes]: How can I evaluate the following integral? ($n \in R$, $n>0$)
$$\int_0^1x^{n-1}(1-x)^{n+1}dx$$

I was solving the following problem (as practice) in school:
Prove that the sum of $n+1$ terms of $$\frac{C_0}{n(n+1)} - \frac{C_1}{(n+1)(n+2)} + \frac{C_2}{(n+2)(n+3)}- \cdot\cdot\cdot = \int_0^1x^{n-1}(1-x)^{n+1}dx$$

Wolfram Alpha says that the integral evaluates to:
$$\frac{\Gamma(n)\Gamma(n+2)}{\Gamma(2n+2)}=\int_0^1x^{n-1}(1-x)^{n+1}dx$$

To reiterate... :
1) How can I evaluate the indefinite integral of the above version?
2) How can I evaluate the definite integral?
3) How to prove the LHS - RHS equality in the aforementioned problem?

REPLY [1 votes]: There's not a lot that can be said with respect to most of your questions here without appealing to special functions: necessary because of the integral and functions involved, but perhaps unsatisfying as a result.
The most important function involved here is the beta function, defined by
$$\text B(x,y) = \int_0^1 t^{x-1}(1-t)^{y-1}dt$$
This has a close relationship with the gamma function $\Gamma(x)$ (a generalization of the factorial to any complex number that is not a non-positive integer) as
$$\text B(x,y) = \frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}$$
First we'll answer your simpler question however.

How can I evaluate the definite integral?

You have
$$\mathcal I := \int_0^1x^{n-1}(1-x)^{n+1}dx$$
A simple tweak of rewriting $n+1 = (n+2)-1$ allows us to claim that
$$\mathcal I = \text B(n,n+2) = \frac{\Gamma(n)\Gamma(n+2)}{\Gamma(2n+2)}$$
To see this, just let $x=n,y=n+2$ in the original definition of the function I gave you.

How can I evaluate the indefinite integral of the above version?

One may define the "incomplete" beta function as
$$\text B_z(x,y) = \int_0^z t^{x-1}(1-t)^{y-1}dt$$
This is an antiderivative (obviously, per the fundamental theorem of calculus), but not necessarily the entire class of them. Ben Longo in the comments suggests $B_z(n,n+1) - B_z(n+1,n+1)$ as one, but I'm not sure how they arrived at this answer. I think it's safe to say, though, that any antiderivative will likely rely on more special functions if not boil down to manipulations of the above function in some way.

How to prove the LHS - RHS equality in the aforementioned problem?

To restate the problem in language more familiar to most, $C_r  := \, _n C_r = \binom n r$ (the $n$ being omitted because it's implied I guess) and thus we seek to show
$$\sum_{k=0}^{n+1} \binom n k \frac{(-1)^k}{(n+k)(n+k+1)} = \int_0^1x^{n-1}(1-x)^{n+1}dx$$
To prove this equality, expand the parenthetical in the integral using the binomial expansion formula of $(a+b)^n = \sum_{k=0}^n \binom n k a^k b^{n-k}$:
$$\mathcal I := \int_0^1x^{n-1}(1-x)^{n+1}dx =  \int_0^1x^{n-1} \sum_{k=0}^{n+1} \binom {n+1} k (-1)^k x^kdx$$
You can bring the $x^{n-1}$ into the summation by distributing it, and then exchange the sum and integral (with no issue since the sum is finite and the interval is finite). Then we just evaluate as normal.
$$\begin{align}
\mathcal I &= \int_0^1 \sum_{k=0}^{n+1} \binom {n+1} k (-1)^k x^{n+k-1}dx \\
&= \sum_{k=0}^{n+1} \binom {n+1} k (-1)^k \int_0^1 x^{n+k-1}dx \\
&= \sum_{k=0}^{n+1} \left. \binom {n+1} k \frac{ (-1)^k}{n+k} x^{n+k} \right|_{x=0}^1\\
&= \sum_{k=0}^{n+1} \binom {n+1} k \frac{ (-1)^k}{n+k}
\end{align}$$
This is similar to our intended sum, but not quite the exact same. But some manipulations can be done to it. Begin by pulling out the first term of the sum for simplicity, and then use Pascal's identity - $\binom p q + \binom p {q-1} = \binom{p+1}{q}$ - to split up the binomial coefficient. Then we can distribute and make our sum into two separate ones. This brings us to this:
$$\mathcal I = \frac 1 n + \sum_{k=1}^{n+1} \binom n k \frac{ (-1)^k}{n+k} + \sum_{k=1}^{n+1} \binom n {k-1} \frac{ (-1)^k}{n+k}$$
For now, we'll reabsorb the $1/n$ into the left-hand sum, to start it back at $k=0$. The second we'll reindex with $m=k-1$.
$$\mathcal I = \sum_{k=0}^{n+1} \binom n k \frac{ (-1)^k}{n+k} + \sum_{m=0}^{n} \binom n {m} \frac{ (-1)^{m+1}}{n+m+1}$$
Now, an interesting fact. $\binom p q$, by convention, is defined to be $0$ whenever $q>p$. For instance, $\binom 4 5 = 0$. We'll abuse that fact here, and add an additional term into the end of the right-hand sum. It'll be $0$ since the coefficient will be $\binom{n}{n+1} = 0$, but it'll make life easier later on by ensuring the bounds of the sum are the same. Similarly, for intuition, let's rename $m$ back to $k$ since it's just a dummy variable really.
$$\mathcal I = \sum_{k=0}^{n+1} \binom n k \frac{ (-1)^k}{n+k} + \sum_{k=0}^{n+1} \binom n {k} \frac{ (-1)^{k+1}}{n+k+1}$$
At this point, we use one of the factors of $-1$ from the right-hand sum to allow us to subtract that whole sum, and then combine the sums into a single one:
$$\mathcal I = \sum_{k=0}^{n+1} \binom n k (-1)^k \left( \frac{1}{n+k} - \frac{1}{n+k+1} \right)$$
Now we just combine the two fractions into one to complete the proof!
$$\mathcal I = \sum_{k=0}^{n+1} \binom n k \frac{(-1)^k }{(n+k)(n+k+1)}$$
Thus, in summary,
$$\int_0^1x^{n-1}(1-x)^{n+1}dx = \sum_{k=0}^{n+1} \binom {n+1} k \frac{ (-1)^k}{n+k} = \sum_{k=0}^{n+1} \binom n k \frac{(-1)^k }{(n+k)(n+k+1)}$$

Finally, a huge thanks to Brian M. Scott, who showed me how to prove the two sums above were equal (see here)!


TITLE: Adjoint of the Coupled Covariant Derivative on Spinors
QUESTION [4 upvotes]: I want to understand the proof for a $C^0$ bound of solutions to the Seiberg-Witten equations.
Among other places, it can be found in Kronheimer, Mrowka: "The genus of embedded surfaces in the projective plane", it is Lemma 2 therein.
One step in the proof goes as follows:
$$
\Delta \left| \Phi \right|^2
=
2 \langle \nabla_A^* \nabla_A \Phi , \Phi \rangle - 2 \langle \nabla_A \Phi, \nabla _A \Phi \rangle.
$$
(This step with context is provided in the picture below)
The proof that this is true comes from using the definition $\Delta = - \sum_i \nabla_i \nabla_i$ and using that $\nabla_A$ is metric.
But I'm puzzled by the result.

Why is the right hand side not constant $0$?
  It should be, as $\langle \nabla_A^* \nabla_A \Phi , \Phi \rangle=\langle  \nabla_A \Phi , \nabla_A \Phi \rangle$ by the definition of adjoint.

REPLY [1 votes]: Without knowing the exact context, I would bet that $\nabla^*$ is not a pointwise adjoint on each fiber, but rather it is the $L^2$ adjoint, meaning $$\int \langle \nabla^* \phi , \psi \rangle = \int \langle \phi , \nabla\psi \rangle,$$
and since the theorem is about a $C^0$ bound you are working pointwise.
I don't know if it's as simple to define a pointwise adjoint for a differential operater, because $\nabla \phi$ depends on the local behavior of $\phi$.


TITLE: Help calculating $\int_C e^{-1/z}\sin(1/z)dz$ over the unit circle?
QUESTION [4 upvotes]: I found the integral
$$
\int_C e^{-1/z}\sin(1/z)dz
$$
over the circle $|z|=1$ while doing some problems in Schaum's Outline for Complex Variables.
This integral has me stumped. The answer is $2\pi i$, but I can't see why. There are no poles, so I don't think I can apply the residue theorem. Reparametrizing with $z=e^{it}$ for $t\in(0,2\pi)$ looks very messy.
How can this integral be approached? I tried to find the Taylor series, and the first few terms are
$$
-\frac{1}{2z^2}-\frac{2}{3!z^3}-\cdots
$$
so $0$ looks like an essential singularity, but I don't know if that's useful.

REPLY [4 votes]: With a change of variables $z\mapsto\frac1z$
$$
\begin{align}
\int_Ce^{-1/z}\sin(1/z)\,\mathrm{d}z
&=\int_Ce^{-z}\sin(z)\frac{1}{z^2}\,\mathrm{d}z\\
&=\int_C\left(\frac1z-1+\frac{z}{3}+\dots\right)\,\mathrm{d}z\\
&=2\pi i
\end{align}
$$
Note that the change of variables reverses the direction of the path.

REPLY [2 votes]: My Laurent series centered at $z=0$ of $ e^{-1/z}\sin(1/z)$ disagrees with yours: I have it as the product $\displaystyle\sum_{i=0}^{\infty} \dfrac{(-1)^i}{i!z^{i}}$ $\times$ $\displaystyle\sum_{j=0}^{\infty} \dfrac{(-1)^j}{(2j+1)!z^{2j+1}}$. The only $z^{-1}$ term of my product emerges when $j=0$ and $i=0$, and is equal to  $\dfrac{1}{z}$, where it seems you have no nontrivial term of that order.  I think that mine is correct, but perhaps we should both check our calculations?
In fact, the residue theorem is strong enough to apply in this case; $ e^{-1/z}\sin(1/z)$ has no poles and only one essential singularity at $z=0$, so our function is holomorphic on the complement of finitely many points in C, the unit circle centered at the origin.  As a result, we can compute a residue at $z=0$ as above and apply the residue theorem, which tells us that our integral is $2 \pi i$.


TITLE: Why does this question use multiplication instead of subtraction?
QUESTION [3 upvotes]: Ok so I'm reading a book right now that tackles pre-algebra and I stumbled on this example problem that goes like this.
Jerry bought a pie and ate 1⁄5 of it. Then his wife Doreen ate 1⁄6 of what was
left. How much of the total pie was left?
The authors solution is to solve it like this.
First, subtract 1/5 from 1/1 (pie) which equals 4/5, and then multiply 1/6 to 4/5 to get how much Doreen ate from the whole pie, 4/30.
My way obviously is to solve it like this.
First subtract 1/1 by 1/5 (the same with the author), but then I subtract 4/5 with 1/6, which gives me a totally different answer, 19/30.
So my questions are these,
1.) Why does subtracting one fraction to another not work in this scenario. (Because I have a different result)
2.) Obviously (for me) I should subtract based on the question, but why does the author use multiplication instead?
3.) And why does multiplying instead of subtraction work?

REPLY [4 votes]: Here, I recommend we use variables.
Let $p$ represent the pie that is being eaten (somewhat timidly).
Jerry eats $1/5$ of it, so $1-1/5 = 4/5$ of the original pie is left: $4p/5$.
The his wife comes and eats $1/6$ of what is left of the pie.
Take the remaining pie ($4p/5$), and take away $1/6$ of this new pie stuffs, not the original pie.
$(4p/5)(1-1/6) = 4p/5 \cdot 5/6 = 2p/3$. So two-thirds of the pie remains.

You are subtracting two fractions of the entire pie. The question asks you first about the enitre pie, then the remainder.
'Of' implies multiplication: $10\%\ \text{of}\ 500 = .1 \cdot 500 = 50$.
Multiplication is the only way it will work, because subtraction is the incorrect way to think about the wording of the problem.

Cheers!

REPLY [1 votes]: If you eat a fraction $q$ of something then what is left is $1-q$ of that something, that is to say you are left with the earlier amount of that something multiplied by $(1-q)$
In effect you subtract from $1$ and then multiply
So

They start off with $1$ pie and Jerry eats $\dfrac15$ of it, leaving $1 \times \left(1-\dfrac15\right) =\dfrac45$ of a pie
They then have  $\dfrac45$ of a pie and Doreen eats $\dfrac16$ of that, leaving $\dfrac45 \times \left(1-\dfrac16\right)=\dfrac23$ of a pie


TITLE: box with 2n cards, choose m.
QUESTION [1 upvotes]: This is a problem solved by bernoulli, and is given as an example in my textbook.But I'm having a little trouble understanding it.
In a box containing 2n cards, there are 2 cards marked 1, 2 cards marked 2, 2 marked 3 and so on. A set of m cards are drawn at random from the box. Find the expected number of pairs that still remain in the box.
My book says: "Define $X_i$ = 1 or 0 according as the ith pair remains in the box or not, i=1,...n." This makes sense to me, because Bernoulli solved this problem, so $X_i=1$ is the ith pair is there, $X_i=0$ is it's not. There are 2n cards, so n pairs.
"We want to calculate $E(X_1+...+X_n)$. But $E(X_i)=P(X_i=1)=$"
But then I am not sure how they got this:
Probably from some definition?
$$\frac{{2n-2 \choose m}}{{2n \choose m} } $$
I get the denominator, we have 2n cards and are choosing m. But I don't udnerstand why we have 2n-2 in the numerator
So I worked out the calculation myself:
$$=\frac{\frac{(2n-2)!}{m!(2n-2-m)!}}{\frac{2n!}{m!(2n-m)!}}$$
$$=\frac{(2n-2)!m!(2n-m)!}{m!(2n-2-m)!2n!}$$
Got the same answer as the book:
$$=\frac{(2n-m)(2n-m-1)}{(2n(2n-1))}$$
And the book then somehow gets this:
$$=\frac{(2n-m)(2n-m-1)}{(4n-2)}$$
Where did the n in the denominator go?
If you could help explain this I would be very greatful!

REPLY [1 votes]: There are $\binom{2n}{m}$ equally likely ways to pick $m$ objects from the $2n$ available. There are $\binom{2n-2}{m}$ ways to pick these objects so that a particular pair is unpicked. This is the number of "favourables." For the probability that the pair of $i$'s remains, divide.
The $n$ "disappeared" because we are calculating $E(X_1+\cdots +X_n)$, which by the linearity of expectation is $E(X_1)+\cdots +E(X_n)$. The expectations of the $X_i$ are all the same, they are what you calculated. So we obtain the expectation of the sum by multiplying $E(X_1)$ by $n$. So the denominator changes from $2n(2n-1)$ to $2(2n-1)$.


TITLE: Geodesic loops in Riemann homogeneous spaces
QUESTION [1 upvotes]: Let M be a Riemannian homogeneous space, i.e. the isometry group acts transitively. Prove: any geodesic loop (with possible angle at the starting point) is a closed geodesic (smooth at the starting point).
And there is a hint: prove and use the fact that the vector field associated to a one parameter group of isometries is a Jacobi field when restricted to any geodesic.
I just don't know how this hint comes into play..

REPLY [1 votes]: Here is my own answer:
Say $\gamma(s),s\in[0,a]$ is a geodesic loop starting at $\gamma(0)=p$. Consider any one parameter group of isometries $g_t$, since the isometry group acts transitively, $g_t p$ takes p to any direction in $T_p M$ as $g_t$ varies. Now note that $g_t \gamma$ is a geodesic variation which preserves length, apply the first variation formula for energy:
$$0=E'(0)=-\int_0^a<U(s),\gamma''(s)>ds+ <U,\gamma'>|_0^a=<U(0),\gamma'(a)-\gamma'(0)>.$$
where $U(s)=\frac{d}{dt}|_{t=0}g_t\gamma(s)$ is the variation vector field. $E'(0)=0$ because it preserves length, and $\gamma''(s)=0$ because it is geodesic. Now recall that $U(0)$ can be any vector in $T_pM$, which forces $\gamma'(a)=\gamma'(0)$. That's geometrically what we need to prove.


TITLE: Cliquewidth of Cographs + kv
QUESTION [8 upvotes]: I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (graphs which can be built by the operations of disjoint union and complementation, starting from isolated vertices) have cliquewidth at most 2. (Courcelle et al, Upper bounds to the clique width of graphs). Now consider some fixed non-negative integer k, and consider the class of graphs $\mathcal{G} _k$ of graphs such that for every $G = (V,E) \in \mathcal{G} _k$ there is a set $S$ of at most k vertices such that $G[V - S]$ is a cograph. Since the graph class $\mathcal{G} _k$ can also be seen as the class of graphs that can be built out of cographs by adding at most $k$ vertices, this class has also been called cographs + $kv$.
My question is: what is a tight bound on the cliquewidth of graphs in $\mathcal{G}_k$?
It is known that if a graph $G$ is obtained from $H$ by deleting $k$ vertices then $cw(H) \leq 2^k (cw(G) + 1)$. This shows that if a cograph $G$ can be obtained from a graph $H$ by deleting $k$ vertices, then $cw(H) \leq 2^k (3 + 1)$, and hence the cliquewidth of a graph in $\mathcal{G}_k$ is at most $2^k 4$. I am unsure whether this exponential dependency on $k$ is necessary. In this context I would also be interested in the maximum decrease in the cliquewidth by deleting a vertex; i.e. if we delete a single vertex from a graph, how much can the cliquewidth decrease?

REPLY [4 votes]: I think the exponential bound is necessary.  Here is why.
Consider the disconnected graph $G$ on $n$ vertices, labelled $1$ to $n$.  Denote the set of vertices that new vertex $i$ is connected to by $f(i)$, a subset of $\lbrace 1,2,\ldots,n \rbrace$.
The question then becomes: is it possible to find such a function $f$ so that the set $\lbrace f(i) \mid 1 \le i \le k \rbrace$ of subsets of $V(G)$ generates a set of subsets of size $2^k$?
With "generates" I mean the closure under the operation of taking pairwise subsets.
The idea here is that to distinguish between any subsets one needs to label them differently.  However, due to the way the cliquewidth operations are restricted, this can only happen if their intersection is constructed first, and then the remaining vertices.
As far as I can tell, this scenario is possible, but clearly the above is quite far from a rigorous construction of an example.


TITLE: Equation : $5^{2(x+1)} +621\times{10}^x=100\times4^x$
QUESTION [0 upvotes]: Find all integer roots of the equation :
  $$5^{2(x+1)} +621\times{10}^x=100\times4^x$$

It's easily seen that $x=0$ doesn't work.I feel there's no positive root for this equation but how to proceed?

REPLY [0 votes]: If $x\ge1$, the left hand side of $5^{2(x+1)}+621\times10^x=100\times4^x$ is odd while the right hand side is even, which is impossible, so we must have $x\le0$.  Writing $x=-u$, and multiplying both sides by $2^{2u}\times5^{2u}$ to make all the powers non-negative, the equation becomes
$$5^2\times2^{2u}+621\times10^u=2^2\times5^{2+2u}$$
or
$$621\times10^u=5^2(2^2\times5^{2u}-2^{2u})$$
The right hand side is divisible by $5^2$ but by no higher power of $5$.  So $u=2$ is the only possible integer solution.  And, indeed, $5^2(2^2\times5^4-2^4)=10^2(5^4-2^2)=10^2(625-4)=621\times10^2$.  Thus $x=-2$ is the sole integer solution.