TITLE: Derivation of the irreducible representations of SO(3)
QUESTION [0 upvotes]: Is there a way to derive the representations of $SO(3)$ without the usual method with the ladder operators which also gives the ones of $SU(2)$?
The usual way to do these calculations is to start from the commutation relations of the Lie algebra associated with $SU(2)$ (or that of $SO(3)$, which is the same given that $\mathfrak{so}(3) \approx \mathfrak{su}(2)$ as far as I understand) and from there to go throught the ladder-operators-thing to obtain all of the representations of $SU(2)$. Is there another way to derive the representations of $SO(3)$ which is specific of $SO(3)$ and not also applicable to $SU(2)$?

REPLY [2 votes]: Be careful.  It may be the case that $\mathfrak{su}(2)=\mathfrak{so}(3)$, but it is not the case that $SU(2)=SO(3)$.  $SU(2)=\mathrm{Spin}(3)$ and $\rho :SU(2)\rightarrow SO(3)$ is the two-sheeted universal cover of $SO(3)$.  It thus turns out that only the integer spin representations of $SU(2)$ factor through $\rho$ to give well-defined representations of $SO(3)$.
Concretely, the spherical harmonics $Y_{\ell m}(\theta ,\phi )$ span an irreducible representation of $SO(3)$ in $L^2(S^2)$.  This representation has spin $\ell$ (dimension $2\ell +1$), and this yields all the finite-dimensional irreducible complex representations of $SO(3)$.  Note that $\ell$ must be an integer in this context (and so it does not give you all the irreducible representations of $SU(2)$).


TITLE: Optimization with continuous and discrete variables
QUESTION [0 upvotes]: I am trying to maximize the following problem:
$$
\sum_{t=1}^T{z_t g_t + (1-z_t) h_t(x_t) }
$$
with respect to $z_t$ which is a vector of 0 and 1 only and $x_t$ which is a vector of $\mathbb{R}^T$. $h_t$ is a known vector of concave function and $g_t$ is a known vector. The initial state ($t=0$) is perfectly known.
In words, I would like to find the path for $x_t$ but allowing for discrete choice, i.e. if I choose $z_t = 1$, then I do not update the value of $x_t$ and $x_t = x_{t-1}$ but if I choose $z_t=0$ I maximize with respect to $x_t$.
What is the best method to do this? I have found solutions for a full discrete choice model but not for a model that mixes a continuous and discrete variable.
Thanks
T.

REPLY [1 votes]: Introduce a new variable $y_t$ to represent the summand so that the objective is to maximize $\sum_t y_t$.  We want to enforce
$$y_t=\begin{cases}g_t &\text{if $z_t=1$}\\h_t(x_t) &\text{if $z_t=0$}\end{cases}$$
You can do this via the following big-M constraints:
\begin{equation}
(\ell_t-g_t)(1-z_t) \le y_t - g_t \le (u_t-g_t)(1-z_t)\\
(g_t - u_t) z_t \le y_t - h_t(x_t) \le (g_t - \ell_t)z_t,\\
\end{equation}
where $\ell_t$ and $u_t$ are (constant) lower and upper bounds on $h_t(x_t)$:
$$\ell_t \le h_t(x_t) \le u_t.$$
Now the objective and some constraints are linear.  If all $h_t$ are linear functions, then you can solve the whole problem with a MILP solver.  Otherwise, use a MINLP solver.


TITLE: Questions on conditions for convexity of a real function
QUESTION [0 upvotes]: We have a function $f:[0,1] \rightarrow \mathbb{R}$.
We know it is continuous on $[0,1]$.  Aside from a set $S$ of measure $0$, we can compute its right derivative, and can show that this right derivative is non-decreasing on $[0,1] \setminus S$.
Is this sufficient to show that $f$ is convex on $[0,1]$?
[If possible, it would be helpful to know also if my reasons for thinking $S$ has measure $0$ are correct: we have another function $g:[0,1] \rightarrow [0,1]$ which is monotonically non-decreasing everywhere in $[0,1]$. We can show that $S$ is equal to those locations where $g$ is discontinuous. I believe this is sufficient to show that $S$ has measure $0$ but it would be great if someone could confirm?]
Many thanks for any comments!

REPLY [1 votes]: Take the Cantor function $c$. This has zero derivative ae. (hence non-decreasing), but is not convex (since it is constant on some intervals).
A real valued monotonic function can only have a countable number of discontinuities, which has measure zero.


TITLE: (Inequality) $p \cdot (z-x) \leq \frac{a}{R} | z- x| \Leftrightarrow |p|\leq \frac{a}{R}$
QUESTION [0 upvotes]: I need to solve this inequality:
Let $z \in \mathbb{R}^N$ and $a,R > 0$, prove that
$$(\forall x\in B_R(z)) \quad p \cdot (z-x) \leq \frac{a}{R} | z- x|  \ \Longleftrightarrow  \ |p|\leq \frac{a}{R} $$
Its seem to be very elementary inequality but I can't solve it :(.
Any help will be appreciated.

REPLY [0 votes]: By the dot product rule
$$p\cdot (z-x)=|p||z-x|\cos\theta$$
where $\theta$ is the angle between the vector $p$ and $z-x$. Now let
$$|p|\leq\frac{a}{R}\Rightarrow |p||z-x|\leq\frac{a}{R}|z-x|$$
But $$p\cdot (z-x)=|p||z-x|\cos\theta\leq|p||z-x|$$
So $$p\cdot(z-x)\leq\frac{a}{R}|z-x|$$
This is about this direction, but I cant see the other direction. Because lets say
$$p\cdot(z-x)\leq\frac{a}{R}|z-x|\Rightarrow |p||z-x|\cos\theta\leq\frac{a}{R}|z-x|\Rightarrow |p|\cos\theta\leq\frac{a}{R}$$
But this does not ensure $|p|\leq\frac{a}{R}$ because you could have $\cos\theta=1/2$ and $|p|=\frac{2a}{R}$.


TITLE: Prove correctness of the following algorithm for computing Fibonacci numbers
QUESTION [0 upvotes]: I am a student studying for my BS in Computer Science. We recently got asked this question in on of my class and with no book to reference I am going to ask it here for a little help. I know I will have to use induction but I don't really understand how
Input: a, a natural number
Output: F_a, the ath Fibonacci number
Let i=1
While i<=a do
  if i=1 or i=2, then Fib(i)<-1
  else Fib(i)<-Fib(i-1)+ Fib(i-2)
  i <- i+1
end
Print Fib(a)

REPLY [0 votes]: Input: a, a natural number
Output: F_a, the a'th Fibonacci number

1 Let i = 1
2
3 While i <= a do
4
5  if i = 1 or i = 2 then Fib[i] <- 1
6
7  else Fib[i] <- Fib[i - 1] + Fib[i - 2]
8
9  i <- i + 1
10
11 end
12
13 Print Fib[a]

First determine what you are trying to prove:

At line 12, $\operatorname{Fib}[a] = F_a$

Now consider some assumptions you will need to prove it:
$$F_a = F_{a - 1} + F_{a - 2}$$
$$F_1 = 1$$
$$F_2 = 1$$
To prove this kind of statement, you need to establish what is called a loop invariant.  This is a statement for which, if it is true at the start of 1 pass of the loop (line 4), then it is true at the end of that pass of the loop (line 10).  Here your primary loop invariant is:
$$\forall j ~:~ 1 \le j < i \implies \operatorname{Fib}[j] = F_j \tag{L}$$
After using the definition of the fibonacci sequence to prove that (L) is a loop invariant, if you can prove that (L) holds at line 2 (before the loop) then it must hold at line 12 (after the loop).
Furthermore, the loop condition at line 3 implies that at line 12 $\lnot (i \le a)$.
So you are left with two statements being true at line 12:
$$\begin{cases}
\forall j ~:~ 1 \le j < i \implies \operatorname{Fib}[j] = F_j \\
i > a
\end{cases}$$
Those two together are enough to establish that at line 12, $\operatorname{Fib}[a] = F_a$.
To prove that the program terminates, you need to establish a decreasing ordinal during the loop.  So to establish halting you need to prove that $a - i + 1$ is always positive and decreasing during the loop.
Aside, this is also why most people don't bother attempting to prove things about procedural programs, but rather prefer functional programs.


TITLE: What is wrong with the derivation?
QUESTION [0 upvotes]: I want to evaluate
$$\int_0^{\infty}\frac{e^{jtx}}{(1+x)^2}\,dx$$
where $j=\sqrt{-1}$ and $t$ is a real number. I did this change of variables $y=1/(1+x)$, which resulted in the integration
$$-\int_0^1e^{jt/y}\,dy=\frac{1}{jt}$$
As you can see, the original integral is actually the characteristic function of a random variable with a PDF $f_X(x)=(1+x)^{-2}$, and one of the properties of the characteristic function is that its value at $0$ is $1$, which isn't the case in my result, and the characteristic function always exists.
What's wrong with the derivation?
EDIT 1: I evaluated $dy=\frac{dx}{(1+x)^2}$, while it should be $dy=\frac{-dx}{(1+x)^2}$. So, the integral becomes
$$\int_0^1e^{jt/y}\,dy=\frac{-1}{jt}$$
EDIT 2: I forgot to the scaling factor $e^{jt}$, but the final result is still true. So, the integral is
$$e^{jt}\int_0^1e^{jt/y}\,dy=\frac{-1}{jt}$$
EDIT 3: The indefinte integral is evaluated as
$$e^{jt}\int e^{jt/y}\,dy = \frac{-e^{jt}}{jt}\,y^2e^{jt/y}$$

REPLY [2 votes]: You evaluate the integral
as if the function was
$e^{jty}$.


TITLE: Why is a nontrivial finite group is nilpotent if every maximal subgroup is normal?
QUESTION [2 upvotes]: In the following proof

I understand the above proof up to the part where it says "by Sylow theory $N(M)=M$", could someone explain to me why is this true. We have just started learning about group theory and few days ago we started learning about the first and second Sylow theorms but I am not sure which one of them implies that $N(M)=M$
Thanks.

REPLY [2 votes]: This is due to the following.
Lemma Let $G$ be a finite group, $P \in Syl_p(G)$ and $H \leq G$ with $N_G(P) \subseteq H$. Then $N_G(H)=H$.
Proof Let $x \in N_G(H)$. Since $P \subseteq N_G(P) \subseteq H$, $P \in Syl_p(H)$. Since $x$ normalizes $H$, $P^x \in Syl_p(H)$, so by Sylow theory, $P^x=P^h$ for some $h \in H$. This means $xh^{-1} \in N_G(P)$, which implies $x \in hN_G(P) \subseteq H$. Conversely, $H \subseteq N_G(H)$ follows from the definition. Hence we are done.


TITLE: How to solve $n < 2^{n/8}$ for $n$?
QUESTION [10 upvotes]: This is from an exercise (1.2.2) in introduction to algorithms that I'm working on privately.
To find at what point a $n \lg n$ function will run faster than a $n^2$ function I need to figure out for what value $n$
$8n^2 > 64n \lg n$
(with lg here being the binary log)
after some elementary simplification we get
$n > 8\lg n$
Playing around with properties of log I can further get this to
$n^8 < 2^n$
or
$n < 2^{n/8}$
While I'm sure it's something very elementary I've lost somewhere over the years, after checking out a few logarithm tutorials I'm just not finding how to get any further on this.
Any help with solving for $n$ would be appreciated.

REPLY [8 votes]: The Lambert $W$ function can be used to solve equations of the form $p^{ax+b} = cx+d.$  In fact, the Wikipedia page gives the solution to $n = 2^{n/8}$ to be
$$n = \frac{-8}{\ln 2} W\left(\frac{-\ln 2}{8}\right).$$
Via Mathematica, which implements the $W$ function as ProductLog, this comes out to be 43.5592 (although you have to take the lower branch of the $W$ function), in agreement with the Newton iteration solution Theo Buehler mentions.


TITLE: Spectrum of a Markov kernel acting on $L^2$
QUESTION [0 upvotes]: Let $P$ be a Markov kernel on a measurable space $(E,\mathcal E)$ admitting an invariant probability measure $\pi$. $P$ acts on $L^2(\pi)$ via $$Pf:=\int\kappa(\;\cdot\;{\rm d}y)f(y).$$ The invariance means that $\int\kappa f\:{\rm d}\pi=\int f\:{\rm d}\pi$. Let $L^2_0(\pi):=\left\{f\in L^2(\pi):\int f\:{\rm d}\pi=0\right\}$. I've read the following:

The first equality in (22.2.3) holds since they've argued that $L^2_0(\pi)$ is a reducing subspace for $P$. But how does the second equality follow? Moreover, I've often read that $\operatorname{Spec}\left(P\mid L^2_0(\pi)\right)\subseteq[-1,1)$ (so, $1$ is excluded from the spectrum when restricting to $L^2(\pi)$. How does this follow?

Note that $$U:L^2(\mu)\to L^2(\mu)\;,\;\;\;f\mapsto\langle1,f\rangle_{L^2(\mu)}1$$ is an orthogonal projection with $\mathcal N(U)=L^2_0(\mu)$. So, $1-U$ is the orthogonal projection of $L^2(\mu)$ onto ${\mathcal R(U)}^\perp=L^2_0(\mu)$. Now, if $\lambda\in\mathbb R$, then $\lambda-\left.P\right|_{{L^2_0(\mu)}^\perp}$ is injective if and only if \begin{equation}\begin{split}\{0\}&=\mathcal N\left(\lambda-\left.P\right|_{{L^2_0(\mu)}^\perp}\right)\\&=\left\{g\in\mathcal R(U):(\lambda-P)g=0\right\}\\&=\left\{Uf:f\in L^2(\mu)\text{ and }(\lambda-P)Uf=0\right\}\\&=\left\{Uf:f\in L^2_0(\mu)\text{ and }(\lambda-P)Uf=0\right\}\\&\;\;\;\;\;\;\;\;\;\;\;\;\uplus\left\{Uf:f\in L^2(\mu)\setminus L^2_0(\mu)\text{ and }(\lambda-P)Uf=0\right\}\\&=\left\{0\right\}\uplus\left\{\langle1,f\rangle_{L^2(\mu)}1:f\in L^2(\mu)\setminus L^2_0(\mu)\text{ and }\lambda=1\right\}\\&=\left\{0\right\}\uplus\left\{c:c\in\mathbb R\setminus\{0\}\text{ and }\lambda=1\right\}\\&=\begin{cases}\mathbb R&\text{, if }\lambda=1\\\{0\}&\text{, otherwise}\end{cases},\end{split}\tag1\end{equation} where we've used that $P1=1$ (and we treat $c\in\mathbb R$ as the constant function $E\ni x\mapsto c$).

So, we can conclude that $\lambda\in\mathbb R$ is contained in the point spectrum of $\left.P\right|_{{L^2_0(\mu)}^\perp}$ if and only if $\lambda=1$. How can we conclude?

REPLY [2 votes]: Two remarks too long to be posted as comments.

To claim that the spectrum of a Markov operator with respect to a finite stationary measure is real one has to assume that it is self-adjoint (equivalently, that the chain is reversible). For such operators geometric ergodicity is indeed equivalent to the fact that 1 does not belong to the spectrum in $L^2_0$ (since the spectrum is closed, it means that there is a spectral gap separating the spectrum from 1).
If the state space is infinite, then it is well possible that there is no spectral gap in spite of irreducibility of the operator. There are examples like this even for countable state spaces.


TITLE: Describing points on Earth's surface visible from space
QUESTION [6 upvotes]: I'd like to describe the points on Earth's surface that are visible to a viewer who is 100 miles above the North Pole. I'm assuming a spherical Earth and radius of 3960 miles if it's needed. My thoughts are that you'll be able see a portion of the Earth, all the way to a "horizon", and this horizon can be described by a circle. Is there any way to find the equation of this circle? All I really need is the radius to do this. I just don't seem to have enough information to find the distance from the viewer to the horizon, which seems like the most direct way forward. Is there something else I can do? Thanks so much!

REPLY [5 votes]: As BeaumontTaz suggested, I've written an answer to my own question.
First, draw a triangle with vertices the viewer, the center of the Earth, and a point on the Earth's surface. This is a right triangle because a radius and tangent line form a right angle at the point of tangency. The hypotenuse is 4060 miles, the longer leg is 3960 miles, and the short leg is 895.545 miles (from the Pythagorean theorem). The angle at the viewer can be found by the law of cosines and is equal to $77.257^\circ$. Next the radius of the circle we are interested in is the length of the altitude drawn to the side with length 4060 miles. The length of this altitude is $895.545\sin 77.257=873.487$ miles. Then the equation for the circle we are looking  for is $x^2+y^2=762979$ and it is $3862$ miles above the center of the Earth.


text:
\shrink
\section{Conclusions}
\label{sec:conclusions}
\shrink
We have proposed a general framework for designing certifiable algorithms for a broad class of robust geometric perception problems. From the primal perspective, we apply Lasserre's hierarchy of moment relaxations, together with basis reduction, to construct tight semidefinite relaxations to nonconvex robust estimation problems.

From the dual perspective, we use SOS relaxation to convert the certification of a given candidate solution to a convex feasibility SDP, and then we leverage Douglas-Rachford Splitting to solve the feasibility SDP and compute a suboptimality for the candidate solution.

Our primal relaxation is tight, and our dual certification is correct and scalable.

config: arxiv


TITLE: Into a given circle, inscribe a triangle, given the sum of two of its sides and the angle opposite to one of them.
QUESTION [2 upvotes]: I'm stuck at this problem for hours. This is from a book from Kiselev's geometry.

REPLY [1 votes]: By  drawing a tangent to the given circle, take a chord which forms with the tangent the given angle. This chord is one of the sides of the given sum. Note that all the inscribed angles intercepting the corresponding arc are congruent to the given angle.
Let $P$ and $Q$ be the endpoints of the chord. From $P$ extend the chord outside the circle to obtain a segment $RQ$ of length equal to the given sum. Let $S$ be the intersection of the arc and the  circle centred at $P$ of radius $RP$. Then $\triangle PQS$ is the required triangle.


TITLE: Understanding the definition of row echelon form from Golan.
QUESTION [2 upvotes]: The definition is given below:

But I do not understand what is $s(i)$ and how to know it, could anyone give me a numerical example to explain the definition,please?

REPLY [1 votes]: It means that for each row $i$,  all elements before a certain column $j=s(i)$ are $0$, and that the function $i\longmapsto j=s(i)$ is (strictly) increasing, i.e. the number of $0$s at the beginning of a row is increasing.
This condition is not satisfied in the counterexample they give, as $s(1)=1, s(2)=3, s(3)=3, s(4)=5$.


TITLE: Determining Laurent Series expansion and residues
QUESTION [1 upvotes]: Determining Laurent Series expansion and residues of $f(z)=\frac{z}{(z+1)(z+2)}$ around $z = -2$. What is the validity of the expanded region? What is $res(f, -2)$??

REPLY [3 votes]: This is simple pole (because $z$ and $z+1$ do not have zeros at $z=-2$ and $z+2$ have zero of order 1), so Laurent series principal part converge everywhere.
Hence residue is $\lim\limits_{z\rightarrow -2}(z+2)\frac{z}{(z+1)(z+2)}=2$. So principal part is $\frac{2}{z+2}$.
Take that part off give you $\frac{z}{(z+1)(z+2)}-\frac{2}{z+2}=-\frac{1}{z+1}$.
A simple way to find Taylor series of this is to "shift" the whole thing so that instead of $z=-2$ we get $z=0$. In other word, we find Taylor series expansion of $-\frac{1}{z-1}=\frac{1}{1-z}$ around $0$. This, as it turn out, is a geometric series, so it's just $\sum\limits_{n=0}^{\infty}z^{n}$ with convergence in $|z|<1$. Now shift it back to get $-\frac{1}{z+1}=\sum\limits_{n=0}^{\infty}(z+2)^{n}$.
So the whole series is $\frac{2}{z+2}+\sum\limits_{n=0}^{\infty}(z+2)^{n}$ and converge at $0<|z+2|<1$.


TITLE: Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
QUESTION [33 upvotes]: Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And what is the answer if $\mathbb{Q}$ is replaced by $\mathbb{Z}$?
The motivation for this question is Jonas Meyer's comment on the question
Polynomial bijection from $\mathbb{Q} \times \mathbb{Q}$ to $\mathbb{Q}$
which says that the explicit determination of an injective polynomial mapping
$f: \mathbb{Q}^2 \rightarrow \mathbb{Q}$ is already difficult, and that
checking whether the polynomial $x^7+3y^7$ is an example is also.
Added on Aug 8, 2013: SJR's nice answer still leaves the following 3 problems open:

Is there at all an injective polynomial mapping from $\mathbb{Q}^2$ to $\mathbb{Q}$?
Would a positive answer to Hilbert's Tenth Problem over $\mathbb{Q}$ imply that
surjectivity of polynomial functions $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is
algorithmically decidable?
Hilbert's Tenth Problem over $\mathbb{Q}$.

REPLY [28 votes]: We treat all four problems in turn. In all that follows $n>1$.
Surjectivity over $\mathbb{Q}$:
If there is an algorithm to test whether an arbitrary polynomial with rational coefficients is surjective as a map from $\mathbb{Q}^n$ into $\mathbb{Q}$ then Hilbert's Tenth Problem for $\mathbb{Q}$ is effectively decidable.
Proof: Let $g(x_1,\ldots,x_n)$ be any nonconstant polynomial with rational coefficients. We want to construct a polynomial $H$ that is surjective if and only if $g$ has a rational zero.
First we define an auxillary polynomial $h$ as follows;
$$h(y_1,\ldots,y_6):=y_1^2+(1-y_1y_2)^2+y_3^2+y_4^2+y_5^2+y_6^2.$$
The point of the definition is that $h(\mathbb{Q}^6)$ is precisely the set of positive rationals. This follows from Lagrange's four-square theorem and from the fact that $y_1^2+(1-y_1y_2)^2$ is never 0 but takes on arbitrarily small positive values at rational arguments.
Next, let $a$ be any positive rational such that $a$ is not the square of a rational, and such that for some tuple $b\in \mathbb{Q}^n$, it holds that $g(\bar{b})^2<a$. Define the polynomial $H$ as follows:
$$H(x_1,\ldots,x_n,\bar{y}):=g(\bar{x})^2(g(\bar{x})^2-a)h(\bar{y}).$$
Of the three factors that make up $H$, the only one that can vanish is $g(\bar{x})^2$. Therefore if $H$ is surjective then $g$ has a rational zero. Conversely if $g$ has a rational zero then $H$ is surjective: Obviously $H$ takes on the value 0. To obtain any rational $r\ne 0$ as a value of $H$, choose $\bar{b}\in \mathbb{Q}^n$ such $g(\bar{b})^2-a$ has the same sign as $r$ and such that $g(\bar{b})\ne 0$, and then choose values for the tuple $\bar{y}$ so that $h(\bar{y})$ is whatever positive rational it needs to be.
Surjectivity over $\mathbb{Z}$:
There is no algorithm to test surjectivity of a polynomial map $f:\mathbb{Z}^n\to \mathbb{Z}$.  The proof is  by  reduction to Hilbert's Tenth Problem.
Let  $g(x_1,\ldots,x_n)$ be a polynomial with integer coefficients. Then $g$ has an integral zero if and only if $h:=x_{n+1}(1+2g(x_1,\ldots,x_n)^2)$ is surjective. For if $g$ has an integral zero $\bar{a}$, then $h(x_1,a_1\ldots,a_n)=x_1$: therefore $h$ is surjective. Conversely, if $h$ is surjective then choose $\bar{a}\in  \mathbb{Z}^n$ such that $h(\bar{a})=2.$ Then $a_{n+1}(1+2g(a_,\ldots,a_n)^2)=2$, which is possible only if $g(\bar{a})=0$.
Injectivity over $\mathbb{Z}$:
There is no algorithm to test injectivity (also by reduction to HTP).
We shall make use of the non-obvious fact that there are polynomials $\pi_n$ mapping $\mathbb{Z}^n$ into $\mathbb{Z}$ injectively. Such maps are constructed in a paper by Zachary Abel
here.
Let $g(x_1,\ldots,x_n)$ be a polynomial with integer coefficients. Let $h$ be the polynomial $gg_1$, where $g_1$ is obtained by  substituting $x_1+1$ for $x_1$ in $g$. The point of this definition is that $g$ has an integral zero if and only if $h$ has at least two different integral zeros.
Define the polynomial $H(x_1\ldots,x_n)$ as follows:
$$H(\bar{x}):=\pi_{n+1}(x_1h(\bar{x}),\ldots,x_nh(\bar{x}),h(\bar{x})).$$
We claim that $g$ has an integral zero if and only if the polynomial $H(\bar{x})$ does not define an injective map from $\mathbb{Z}^n$ into $\mathbb{Z}$. This gives the reduction of the injectivity problem to Hilbert's Tenth Problem.
To prove the claim, suppose, for the left-to-right implication, that $g$ has an integral zero $\bar{a}$. Then $h(\bar{a})=0$, and $h$ has a different integral zero, call it $\bar{b}$. But then
$$H(\bar{a})=H(\bar{b})=\pi_{n+1}(\bar{0}),$$
so $H$ is not injective.
For the right-to-left implication, suppose that $H$ is not injective, and fix two different tuples $\bar{a},\bar{b}\in \mathbb{Z}^n$ such that $H(\bar{a})=H(\bar{b})$. Since $\pi_{n+1}$ is injective, the following equations hold:
\begin{align*}
a_1h(\bar{a})&=b_1h(\bar{b})\\
&\,\vdots\\
a_nh(\bar{a})&=b_nh(\bar{b})\\
h(\bar{a})&=h(\bar{b})
\end{align*}
If $h(\bar{a})$ was not 0, then by dividing each of the first $n$ equations by $h(\bar{a})$, it would follow that the tuples $\bar{a}$ and $\bar{b}$ were identical, a contradiction. So $h(\bar{a})=0$, hence $g$ has an integral zero.
Injectivity over $\mathbb{Q}$:
The same technique that we used over $\mathbb{Z}$ works perfectly well, assuming that we have polynomials $\pi_n$ mapping $\mathbb{Q}^n$ into $\mathbb{Q}$ injectively. The existence of such polynomials is, it seems, an open question. But if there are no such polynomials then the decision problem for injectivity disappears!


TITLE: Derivative of function defined on two different coordinate charts on each one.
QUESTION [2 upvotes]: I'm reading Milnor's Lectures on h-cobordism and got stuck with part of proof of lemma 2.6 which reduces to folowing problem:
Let's consider some smooth manifold $M$ with boundary and two coordinate charts $(U, h), (U', h')$ intersecting themselves on $\partial M$ such that $h:p\mapsto (x_1(p),\ldots, x_n(p))$ $h':p\mapsto (x_1'(p),\ldots, x_n'(p))$ respectively maps $U,U'$ onto $D^n \cap \mathbb{R}_+^n$. If $f,f':M \to \mathbb{R}$ are such that $f=\pi_n \circ h, f'=\pi_n \circ h'$ ($\pi_n$ states for projection on $n$-th coordinate) then for $p \in \partial M \cap U \cap U'$ one has $\frac{\partial f}{\partial x_n}(p)=1$ and $\frac{\partial f'}{\partial x_n}(p)>0$.
The first part is clear for me because  $\frac{\partial f}{\partial x_n}(p)=\frac{\partial x_n}{\partial x_n}(p)=1$ but I cannot come up with formal proof of the inequality. I'm not really familiar with such reasonings so I'd like to see formal proof with explanation. Thanks in advance.

REPLY [1 votes]: First, I believe that you need that $U \cap U'$ not only intersects $\partial M$, but that it does so in an nontrivial way, so that $h' \circ h^{-1}$, which is defined on
$$
V = h(U \cap U') \subset D^n \cap \mathbb R^n_{+}
$$
has the property that $V$ contains
$$
W \cap  \mathbb R^n_{+}
$$
where $W$ is an open set in $\mathbb R^n_{+}$ that intersects the hyperplane $H = \{ (a_1, \ldots, a_n) | a_n = 0 \}$ in an open set in that hyperplane. Informally, $h(v)$ contains a "substantial piece" of boundary rather than just a single point. Maybe this is a consequence of your assumptions...but I'm not certain of that.
Once you have this, the rest isn't too bad:
Let $p \in \partial M$, and let $q$ and $q'$ denote the images of $p$ under $h$ and $h'$, respectively, with $q \in W$.
The map $g = h' \circ h^{-1}$ on $W$ is required, as a chart, to be a diffeomorphism, and to send the hyperplane $H$ to the hyperplane $H$. Consider the action of $dg$ on the vectors $e_1, \ldots, e_n$ at $q$.
For $i = 1, \ldots, n-1$, the curve $\gamma: [-1, 1] \to \mathbb R^n: t \mapsto q + te_i$ lies in $H$, so $g \circ \gamma$ is a curve in $H$, with $(g \circ \gamma)(0) = q'$. [You should verify this, just to be sure you've got the notation down.] The derivative of $g$ at $q$ therefore takes the vector $e_i$ to a vector $e'_i$ at $q'$, and $e'_i$ lies in $H$.
Since $dg$ is a diffeomorphism, $dg(q)$ must be an isomorphism of vector spaces, so
$$
e_n' = dg(q)[e_n]
$$
must be a vector at $q'$ that's not in the span of $e'_1, e'_2, \ldots, e'_{n-1}$, which is $H$ (why?). It's therefore got a nonzero component in the $n$ coordinate direction. Furthermore, since $\pi_n(g(q)) = 0$, but $\pi_n(g(s)) \ge 0$ for every $s$, this nonzero coordinate must be positive.
Now...let's look at $f'(s) = \pi_n \circ h'(s) $. The definition of
$$
\frac{\partial f'}{\partial x_n}(p)
$$
is that it's the derivative of
$$
f' \circ h^{-1}(a_1, \ldots, a_n)
$$
with respect to $a_n$ at the point $q$, or equivalently, it's
$$
d(f' \circ h^{-1})(q)[e_n],
$$
the derivative of the map at $q$ (which is a linear transformation on vectors) applied to the vector $e_n$.
Let's rewrite that function:
$$
f' \circ h^{-1} =  (\pi_n \circ h') \circ h^{-1} = \pi_n \circ g
$$
Now $g$ and $\pi_n$ are both maps of Euclidean space, so the chain rule applies:
\begin{align}
d(\pi_n \circ g)(q) &= d\pi_n(g(q)) \cdot dg(q)
\end{align}
The first factor here is just the linear map that extracts the $n$th coordinate, i.e, I'm saying that
$$
d\pi_n(g(q)) = \pi_n
$$
(which is generally true for linear maps).
So now we have
\begin{align}
d(\pi_n \circ g)(q)[e_n]
&= \pi_n (  dg(q)[e_n] ).
\end{align}
But the argument to $\pi_n$ is a vector that we just showed earlier has a nonzero and indeed positive $n$th component, so this expression is $> 0$, as required.


TITLE: Estimate the surface integral over a hemisphere of a scalar function, given four points of the function.
QUESTION [0 upvotes]: Let H be the part of the surface $x^2+y^2+z^2=50$ defined for $z ≥ 0$, and suppose $f$ is
a continuous function with
$f (3, 4, 5) = 7$, $f(3, −4, 5) = 8$, $f(−3, 4, 5) = 9$, and $f(−3, −4, 5) = 12$.
By dividing H into four patches, estimate the value of $\iint_H f(x,y,z)dS$.
I tried to solve this problem given, that for a scalar function $f(x,y,z)$,
$$\iint_H f(x,y,z)dS=\iint_Df(x,y,z) \lvert r_u\times r_v\rvert dudv$$
where $r(u,v)$ is a parametrisation of the surface.
I used spherical coordinates to parameterise the surface by
$r(\theta,\phi)=\sqrt{50}\cos(\theta)\sin(\phi)i+\sqrt{50}\sin(\theta)\sin(\phi)j+\sqrt{50}\cos(\phi)k$ for $0≤\theta≤2\pi$ and $0≤\phi≤\pi/2$.
However I am not sure how to use the given points of $f$ to estimate this integral.

REPLY [1 votes]: Why parameterize?! You don't have $f$ at all, so why even think about computation. The given sample points are uniformly distributed over the sphere. So divide the sphere into 4 equal patches each containing one of the sample points. By the very definition of integral, a reasonable approximation to $\int_Sf$ will be $$f(point_1)*Area_1 + f(point_2)*Area_2+\cdots +f(point_4)*Area_4 \ .$$
Since we have a nice sphere, each area is $1/4$ the surface area of sphere of radius $\sqrt{50}$. Plug things in.
Added: By the way, this is the same as averaging the four values and multiplying the result by the surface area of the sphere -- which is the same as integrating the constant function equal to the average.


TITLE: $\sigma$-algebra generated by a subset of a set
QUESTION [0 upvotes]: Let $\Omega$ = {1,2,3,4} and consider the collection of subsets of $\Omega$,
$\mathcal A$={{1,2}}.
The problem is to find the $\sigma$-algebra $\mathcal F$ generated by $\mathcal A$.
I know this is a very basic question, but it is difficult for me to understand the concept of $\sigma$(X). If someone can explain the details of it, I will be greatly grateful.

REPLY [0 votes]: The definition says that $\sigma(\mathcal{A})$ is the smallest $\sigma$-algebra on $\Omega$ which contains $\mathcal{A}$ (that is, contains all the subsets of $\Omega$ that are the elements of $\mathcal{A}$.
Before going on, try to answer: How many elements are there in $\mathcal{A}$ (that is, what is $\#\mathcal{A}$)? Is it $1$ or $2$?
Now remember that a $\sigma$-algebra must contain complements of each of its members and also must contain the union of any finite or countably infinite collection of them.
So we have that:

$\{1,2\}$ must belong to $\sigma(\mathcal{A})$ (because it is an element of $\mathcal{A}$);
$\Omega \setminus \{1,2\}=\{3,4\}$ must belong to $\sigma(\mathcal{A})$ (since it is a $\sigma$-algebra);
And you must always have $\Omega$ itself, since it is the union of any set and its complement; and also the empty set $\emptyset$, which is the complement of $\Omega$.

So we have that $$\sigma(\mathcal{A})\supset \big\{\emptyset,\{1,2\},\{3,4\},\Omega\big\}.$$ But is it enough?
Well, try to prove or convince yourself that this is in fact a $\sigma$-algebra, and so we have a $\sigma$-algebra containing $\mathcal{A}=\big\{\{1,2\}\big\}$. But we've seen that we can't exclude any of those sets (that is, those elements of the $\sigma$-algebra): so there can't be a smaller $\sigma$-algebra containing $\mathcal{A}$. Then, actually $$\sigma(\mathcal{A}) =\big\{\emptyset,\{1,2\},\{3,4\},\Omega\big\}.$$


TITLE: What makes electrons in the conduction band conductive?
QUESTION [6 upvotes]: We say electrons must jump from the valence band to conduction band in order to be conductive. Why is that the case and why can't electrons in the valence bands themselves be conductive?
Is it because more energy levels are available unoccupied in the conduction band and electrons literally have a lot more room to roam around? If that is the case, then why doesn't the valence band of Silicon (3p band) be conductive despite being just 33% occupied ?
What core concept of conductivity and/or band theory am I missing? Please elucidate.
Also can we explain the drift of electrons in a metal under an electric field in terms of transition between various close energy levels within the same conductive band?

REPLY [2 votes]: As @Custer explained previously,

it would be wrong to directly link any atomic energy levels to solid state energy levels. That mapping just does not work.

Here, I will try to elucidate it with an intuitive example.
One form of elemental carbon is diamond, where every tetrahedral carbon center combines with 4 other carbon atoms as shown below.

A total of 8 electrons are involved in the above bonding (4 from central $C$ atom and 1 each from the $C$ atoms in the corners). Likewise, 8 atomic orbitals are involved in the process, giving rise to 8 new molecular orbitals.

The 8 electrons occupy the molecular orbitals in the order of increasing energy levels. Thus, 4 bonding orbitals are filled with electrons and the 4 anti-bonding orbitals are empty. Also note, there is a big difference in energy between the bonding and anti-bonding orbitals.
Just as one central $C$ atom and 4 corner $C$ atoms gave rise to 4 $\phi$ and 4 $\phi^{*}$ molecular orbitals at 4 different energy levels, increasing the number of $C$ atoms in the material would form multitude of $\phi$ and $\phi^{*}$ molecular orbitals at varied energy levels, as shown below. In a group of $n$ carbon atoms bonded together, each atom will contribute 4 orbitals and 4 electrons. There will be 2n bonding molecular orbitals, each filled with 2 electrons, and 2n empty anti-bonding orbitals. When the number of carbon atoms in the material approaches infinity ($n → ∞$), the energy differences between bonding molecular orbitals becomes vanishingly small, essentially becoming a continuum. The same is true for the energy differences between the anti-bonding orbitals. Thus, the filled molecular orbitals and the empty molecular orbitals become two, separated bands with a gap in between.

Note that $1s$ atomic orbitals of $C$ also form bonding and anti-bonding orbitals during covalent bonding. Their bands, which are not shown above, occur below the filled band. Also note, since, $C-C$ bond has a considerable bond strength, the band gap between the filled and empty bands shown above is considerably large. Silicon, whose crystalline form also assumes diamond like molecular configuration, has a relatively weaker $Si-Si$ bond due to which its band gap is smaller than diamond's.
I hope this gives you an intuition on why one-to-one mapping of atomic energy levels with solid state energy levels would be wrong. For e.g., carbon's $2s, 2p_{x}, 2p_{y}$, and $2p_{z}$ atomic orbitals, all contribute to both of its filled and empty bands, i.e., the same set of atomic orbitals contribute to two different bands. Likewise, it might also be possible that bands contributed by two different sets of orbitals overlap, in which case it technically is a single band.
In the case of metals, although no such covalent $\sigma$ bonds occur between the atoms as in diamond or silicon, the core concept of band formation remains essentially the same.
Density of states
We know each band is composed of multitude of states, where no two electrons can occupy the same state. Also for some value of energy in a band, there exists more states than the other. The density of states function $g(E)$ is a probability distribution function such that,
$$\int_{E_1}^{E_2}g(E).dE$$ gives the number of states in the energy range $E_1$ to $E_2$ per unit volume of material. It should come no surprise that for energies inside a band gap, $g(E) = 0$.
Filling of electrons in bands
At thermodynamic equilibrium, the probability that a state of energy $E$ is filled with an electron is given by the Fermi-Dirac distribution
$$f(E)=\frac {1}{1+ e^{(E-\mu)/(k_{B}T)}}$$
The number of electrons in the energy range $E_1$ to $E_2$ per unit volume of material should be
$$\int_{E_1}^{E_2}g(E).f(E)dE$$
And, the density of electrons in the material should be
$$\frac{N}{V} = \int _{-\infty }^{\infty }g(E).f(E)\,dE$$
The function $f(E)$ looks as follows at $T=0K$, i.e., when the electrons in the solid assume their ground states due to no possible thermal excitation.
for $E>\mu$, $f(E) = 0$
for $E<\mu$, $f(E) = 1$
for $E=\mu$, $f(E) = indeterminate$
This value of $\mu$ is called Fermi level, below which all electronic states must be filled at $0K$ and above which all states must be empty.
N.B. No states are allowed in band gaps, i.e., the gaps are always empty.
When $T ≠ 0K$, at Fermi level, function $f(E)$ returns $\frac{1}{2}$, implying that if there are electronic states allowed at Fermi level, half of the states must be occupied at all temperatures.
If the Fermi level lies in a band gap, the band immediately below it is called the valence band. Valence in the sense that it is the highest energy band electrons occupy at ground state of the solid. Similar terminologies are valence shell, the highest energy shell occupied by electrons in an atom at ground state, and valence orbitals, the highest energy orbitals occupied by electrons. Likewise, if the Fermi level lies within a band, then this band would be the valence band.
Please note, it would be wrong to blindly map the valence orbitals of an atom to the valence band of the solid formed of those atoms as discussed previously.
The basis of conductivity
We talked about band as essentially being a continuum of energy eigenstates. It can also be talked about as an almost continuous collection of momentum eigenstates (i.e., just as energy levels, only certain momenta are allowed for an electron). For every eigenstate there is an another with an equal and opposite momentum, i.e., if we populate every momentum eigenstate in a band, the net momentum of electrons will be zero.
If a band is not that populated, then under the influence of electric field, the electrons can redistribute themselves to appropriate unoccupied energy/momentum eigenstates within that band. Whereas, if the band is densely populated, there are not much free states available for redistribution. The more free states are available within a band, the more conductive it becomes.
Note that electrons can also lose their energy/momenta as thermal losses due to collisions with kernels in the lattice. This causes them to shift to a lower energy state within the band, and they can drift under the field once again. Likewise, electrons whose momenta are directed such that they decelerate under the field also will have their energy/momenta lost.
All in all, this net motion of electrons (drift velocity) is what's needed to sustain an electric current.
What determines the conductivity of a band?

In metals, the fermi level $(E_F)$ passes through the valence band. As $T$ becomes greater than $0$, the electrons just below $E_F$ surpass the level and shift to higher energy states within the band. As there are a lot of unoccupied eigenstates within the band allowing redistribution under an electric field, the valence band is the conduction band for metals.
In semi-metals, $E_F$ passes through the trough of the valence band which has bimodal density of states. So, they need to be at somewhat a higher temperature than metals to be conductive (so that the electrons under $E_F$ can shift to energy levels with greater density of states allowing them to be more conductive). Technically, this bimodal valence band is also the conduction band.
In semi-conductors, $E_F$ lies in the band gap. All states in the band below $E_F$ (the valence band) are filled at $0K$ and the band is not conductive. At higher temperatures, however, the electrons can have enough energy to surpass the band gap and shift to the immediately higher unoccupied band. The electrons in this higher band, now become conductive, and so the band is called the conduction band.
In insulators (e.g., diamond), the $E_F$ passes through a very large band gap. The valence band is filled and non-conductive, and the occupancy of electrons in the band immediately higher than $E_F$, even at higher temperature, is almost null because of the very large band gap that needs to be surpassed. This higher band is what we refer to as conduction band, although no appreciable conduction takes place here. This should be an example to the fact that just as extremely populated bands, extremely non-populated bands are non-conductive too.


TITLE: Slope of this tangent
QUESTION [1 upvotes]: Okay I have to find the slope of this tangent to the curve $y=\int_0^x \frac{dx}{1+x^3}$ at the point where $x=1$.
My try- I integrated the expression and differentiated it afterwards to get the slope. But I'm not getting the correct answer on putting $x=1$ in the final expression that I'm getting after integration and diffrentiation.
Someone please help me out. Is there some other procedure to do questions like this?

REPLY [2 votes]: By the fundamental theorem of calculus:
$$\frac{dy}{dx} = \frac{1}{1+x^3} \Rightarrow \frac{dy}{dx}\bigg|_{x=1} = \frac{1}{1+1^3} = \frac{1}{2}$$


TITLE: Expected Maximum of Three Numbers that Sum to 1
QUESTION [3 upvotes]: I've been working on a programming project on classification with 3 classes, and I'm interested in comparing my results to what I'd expect from pure noise. So I have the following question:
Let $X,Y,Z$ be uniformly distributed over $\{(x,y,z)\in [0,1]^3:x+y+z=1\}$. What is $E \max (X,Y,Z)$?
Thanks
Sorry for editing after the fact. I'm also interested in $E(-X \log ( X )-Y\log ( Y )-Z \log (Z))$

REPLY [2 votes]: If $(X,Y,Z)$ is uniformly distributed in $T=\{(x,y,z)\in[0,1]^3 : x+y+z=1\}$, then $(X,Y)$ is uniformly distributed in $T'=\{(x,y)\in[0,1]^2 : x+y\leqslant 1\}$, and $Z=1-X-Y$ a.s., thus
$$\mathbb{E}f(X,Y,Z)=2\iint_{T'}f(x,y,1-x-y)\,dx\,dy.$$
A simplification by symmetry, $\mathbb{E}\max\{X,Y,Z\}=6\,\mathbb{E} Z[X\leqslant Y\leqslant Z]$, gives
$$\mathbb{E}\max\{X,Y,Z\}=12\iint_{T''}(1-x-y)\,dx\,dy,$$
where
$$T''=\{(x,y) : 0\leqslant x\leqslant y\leqslant 1-x-y\}=\{(x,y) : 0\leqslant x\leqslant y\leqslant(1-x)/2\}.$$
This is easily computed, giving $\color{blue}{\mathbb{E}\max\{X,Y,Z\}=11/18}$.
For $\mathbb{E}(-X\log X-Y\log Y-Z\log Z)=3\,\mathbb{E}(-X\log X)$ (as noted in comments),
$$\iint_{T'}(-x\log x)\,dx\,dy=\int_0^1x(1-x)(-\log x)\,dx=\Gamma(2)(2^{-2}-3^{-2})=\frac{5}{36}$$
which gives $\color{blue}{\mathbb{E}(-X\log X-Y\log Y-Z\log Z)=5/6}$.


TITLE: Probability of a path
QUESTION [0 upvotes]: Let's say I have quantum particle and I wanted to find the probability that this particle goes through a chosen path. Is this practically possible?

REPLY [1 votes]: You express yourself not correctly from the point of view of the quantum mechanics. A particle doesn't "go through a chosen path". It's correct to say that a quantum particle "can be found on some path".
To give you an example, assume a beam splitter, $BS$, a detector $A$ oriented toward the lower face of the $BS$ and a detector $B$ oriented toward the upper face of the $BS$. Assume that a quantum particle impinges on the $BS$. We say that the particle may be reflected by the $BS$, or transmitted. But that is not rigorous. If the particle is detected at some time $t$ by the detector $A$, nothing ensures that if it were detected at a time $t - dt$ it would have been detected also by the detector $A$. We cannot say about a quantum particle that it has a trajectory.
A trajectory is a continuous track in the space, characterized at any time $t$ by a position $\vec r(t)$ and a velocity $\vec v(t)$.
Now, to your question within the above specifications, if you know the wave-function $\psi (\vec r, t)$, you can calculate at any time $t$ the probability to find the particle at the position $\vec r$.


TITLE: How to use the Prime Number Theorem in order to prove Selberg's Formula?
QUESTION [7 upvotes]: I`m reading Melvin B. Nathanson's "Elementary Methods in Number Theory"
and I can't think of a way of deducing Selberg's formula (9.3) from the prime number theorem.
This is one of the tasks left for the reader at the end of chapter 9.3 (The Elementary Proof).
$$(9.3) \qquad \qquad \vartheta(x) \log x + \sum_{p \leq x}(\log p) \vartheta(x/p) = 2x\log x +O(x)$$
Simply replacing $\vartheta(x)$ by $x + o(x)$ results in error terms of order $o(x\log x)$ which are
strictly worse than error terms of order $O(x)$.
I feel like I'm missing something rather simple, but I've been wasting just a little too much time on
that exercise.
Thanks in advance!

REPLY [6 votes]: The $O(x)$ term can be refined by completely elementary means that are not at all complicated.  Filip Saidak (On the prime number lemma of Selberg, Math. Scand. 103 (2008), no. 1, 5–10) proved a much clearer connection between Selberg's result and the prime number theorem.  He stated this for $\psi(x) = \sum_{n\leq x}\Lambda(n)$, but this holds with trivial modifications for $\vartheta(x)=\sum_{p\leq x}\log p$.
If $\vartheta(x):=\sum_{n\leq x}\Lambda(n) = x + E(x)$, then
$\vartheta(x)\log x + \sum_{p\leq x} (\log p)\vartheta(x/p)=2x\log x -(2\gamma+1)x+O(E(x)(\log x)^2)$,
where $\gamma$ is the Euler-Mascheroni constant.  So if all that you know is that $E(x) = o(x)$, then you cannot recover Selberg's result.  Selberg's breakthrough that $-(2\gamma+1)x+O(E(x)(\log x)^2) = O(x)$ appears to be equivalent to the stronger estimate $E(x) \ll x/(\log x)^2$.

REPLY [2 votes]: Edit: Answer to GH from MO by author.
Edit2: Changed a sign.
Let
$$l(n)=\left\{\begin{array}{11} \log p, & if\ n = p\ prime \\ 0, & else. \end{array}\right.$$
Then
$$\sum_{pq\leq x}(\log p)(\log q)=\sum_{n\leq x}(l\ast l)(n)$$
So far, so good. However, using Dirichlet's hyperbola identity, I only obtain
$$\sum_{n\leq x}(l\ast l)(n)=2\sum_{p\leq x^\frac{1}{2}}(\log p)\vartheta(\frac{x}{p})-\vartheta(x^\frac{1}{2})^2 $$, where obviously $\vartheta(x^\frac{1}{2})^2=O(x)$.
Thus I am back at my original problem, as I would have to show
$$\sum_{p\leq x^\frac{1}{2}}(\log p)\vartheta(\frac{x}{p})=\frac{1}{2}x\log x+O(x)$$
Where do I fail to see the shortpath? Thanks for answering anyways, appreciate it!


TITLE: Is there a Mistake in this article of Barret et al.
QUESTION [1 upvotes]: In their article "On the spectral radius of a {0,1) Matrix Related to Mertens' Function", Barret et al. assert an inequality just at the end of p. 156.
Apparently, this inequality comes from the Abel summation formula applied to
$C(n, k+1) = \sum_w ( C(w, k) - C(w, k-1)) ([n/w] - 1)$,
which yields in this case to
$C(n,k+1) = \sum_w C(w,k) ([n/w] - [n/(w+1)])$.
And apparently, they allow themselves to replace the term $[n/w]-[n/(w+1)]$ by $n/w - n/(w+1)$, upon transforming the equality into an inequality.
That is, they consider that
$[n/w]-[n/(w+1)] \leq n/w - n/(w+1)$.
But this is false, as can be seen for example with n = 10 and w = 3 or n = 15 and w = 3.  Am I missing something?

REPLY [2 votes]: The key here is to perform the two steps (Abel transform, and dealing with the floors) in the other order.
Namely, first, handle the floors:
$$
\sum_{w} c(w,k) \left( \left\lfloor \frac{n}{w} \right\rfloor - 1\right)
\leq \sum_{w} c(w,k) \cdot \frac{n}{w}
$$
and then perform the Abel transform. This way, you avoid the troublesome (and, indeed, false) inequality at the end.


TITLE: General Question(s) on Bloch's Theorem
QUESTION [7 upvotes]: (Apologies for the long set-up, I wanted to make sure the question was properly motivated. Skip to the bottom for the actual question.)
Bloch's theorem is a foundational theorem in solid-state physics. It states, given a single-particle Hamiltonian $H = T + V$ with a periodic potential,
$$
V(\vec{r}+\vec{R}) = V(\vec{r}),
$$
the eigenstates of $H$ can always be chosen to satisfy
$$
\psi_{n\vec{k}}(\vec{r} + \vec{R}) = e^{i \vec{k} \cdot \vec{R}} \psi_{n\vec{k}}(\vec{r}) .
$$
Here, $\vec{R}$ refers to a vector in the Bravais lattice, which defines the periodicity of $V$. The theorem is easy to prove: it essentially follows from choosing eigenstates which are simultaneous eigenstates of the discrete translation operators. Alternatively, it follows by simply rewriting the Hamiltonian in Fourier space, where it is immediately seen that $V$ connects only states differing in momentum by a reciprocal lattice vector $\vec{K}$; therefore $H$ can be block diagonalized into sectors labeled by momenta $\vec{k}$ in the first Brillouin zone, each $\vec{k}$th sector containing all momentum eigenstates differing from $\vec{k}$ by a reciprocal lattice vector.
There are a number of statements which commonly follow the proof of Bloch's theorem (for example, see the discussion in Ashcroft and Mermin). First, it is claimed that the additional index $n$ used to resolve any degeneracies in the crystal momentum $\vec{k}$ is necessarily discrete. This is argued by considering the differential equation obeyed by the cell-periodic Bloch function $u_{n\vec{k}}(\vec{r}) = e^{-i\vec{k} \cdot \vec{r}} \psi_{n\vec{k}}(\vec{r})$:
$$
\left[ \frac{1}{2m} \left( -i \hbar \vec{\nabla} + \hbar \vec{k} \right)^2 + V(\vec{r}) \right] u_{n\vec{k}}(\vec{r}) = \varepsilon_{n\vec{k}} u_{n\vec{k}}(\vec{r})
$$
together with the boundary condition $u_{n\vec{k}}(\vec{r} + \vec{R}) = u_{n\vec{k}}(\vec{r})$. It is then claimed that since $u_{n\vec{k}}(\vec{r})$ satisfies this eigenvalue problem in a single unit cell, the spectrum of solutions for fixed $\vec{k}$ must be discrete, and the additional index $n$ used to label this spectrum can be chosen as a discrete index. The second statement commonly made is that for given $n$, the Bloch wavefunctions can always be chosen to be periodic in the Brillouin zone: $u_{n,\vec{k} + \vec{K}} = u_{n\vec{k}}$.
Both of these points are central to the theory of band structure. Together with the assumption that the eigenvalues $\varepsilon_{n\vec{k}}$ vary continuously with $\vec{k}$, the first point states that the spectrum of $H$ is organized into bands. The second point states that these bands are always periodic in the Brillouin zone.
Here are the questions, which I hope are sufficiently closely related to comprise one overall question:

How can I see more precisely that the spectrum in $n$ is discrete for a fixed crystal momentum $\vec{k}$? In other words, given the above differential equation for the cell-periodic Bloch function, is there a way to show that the eigenvalue spectrum of the differential equation is discrete?
While it's perfectly clear that I can take the crystal momenta to lie within the Brillouin zone, how can I see that each band must strictly be periodic in the Brillouin zone? For example, consider a one-dimensional problem for ease of visualizing the bands. Why can't the $n$th band start at some fixed energy $\varepsilon_{n, -\pi / a}$, increase monotonically with $k$, and end at $\varepsilon_{n,\pi / a} = \varepsilon_{n+1, -\pi / a}$, so that each band continuously wraps into the next one?

REPLY [7 votes]: Question 1
The functions
$
\newcommand{\bfr}{\mathbf{r}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfK}{\mathbf{K}}
u_{n,\bfk}
$ are solutions to the third equation in the question. Everything in that equation, including $V$ and $u$, is assumed to be invariant under $\bfr\to \bfr+\bfR$ for lattice vectors $\bfR$. Therefore, for each value of $\bfk$, that equation defines an eigenvalue problem on a compact manifold (specifically a torus) consisting of points $\bfr$ modulo the vectors $\bfR$. Here's the key: for any given value of $\bfk$, the differential operator in that equation is self-adjoint and elliptic, and

The eigenvalues$^\dagger$ of a self-adjoint elliptic differential operator on a compact manifold are discrete.

$^\dagger$  In physics, the word "eigenvalue" is often used loosely, referring also to elements of the continuous part of an operator's spectrum. That's how I'm using the word here, so the statement isn't just a tautology.
This is one of those general theorems in the phycisist's standard toolkit, with many applications. For a more precise statement and an outline of the proof, see theorem 1.46 on page 47 in

Kottke (2016), "Linear Analysis on Manifolds: Notes for Math 7376, Spring 2016" (https://ckottke.ncf.edu/neu/7376_sp16/lacm.pdf).

The proof is not short, so I won't try to reproduce it here.
 Question 2
The condition $u_{n,\bfk+\bfK}=u_{n,\bfk}$ shown in the question might be a typo (?). The correct statement is that we can take
$$
\psi_{n,\bfk+\bfK}(\bfr)=\psi_{n,\bfk}(\bfr).
\tag{1}
$$
This is equation 8.50 in Ashcroft and Mermin's Solid State Physics, 1976. To see why equation (1) is valid, let
$$
\psi_{n,\bfk}(\bfr)=\exp(i\bfk\cdot\bfr)u_{n,\bfk}(\bfr)
\tag{2}
$$
be any solution of the original Schrödinger equation (not shown in the question), where $u_{n,\bfk}(\bfr)$ is invariant under $\bfr\to\bfr+\bfR$. We can obviously rewrite (2) as
$$
\psi_{n,\bfk}(\bfr)=\exp\big(i(\bfk+\bfK)\cdot\bfr\big)
\Big(\exp(-i\bfK\cdot\bfr)u_{n,\bfk}(\bfr)\Big).
\tag{3}
$$
The combination $\exp(-i\bfK\cdot\bfr)u_{n,\bfk}(\bfr)$ is still invariant under $\bfr\to \bfr+\bfR$, so given any complete basis of solutions (2) for each $\bfk$ in the first Brillouin zone, we can simply define the Bloch wavefunctions for the other Brillouin zones by
$$
\psi_{n,\bfk+\bfK}(\bfr)\equiv
 \exp\big(i(\bfk+\bfK)\cdot\bfr\big)
 u_{n,\bfk+\bfK}(\bfr)
\tag{4}
$$
for all $\bfk$ in the first Brillouin zone and for all reciporocal lattice vectors $\bfK$, with
$$
u_{n,\bfk+\bfK}(\bfr)
\equiv\exp(-i\bfK\cdot\bfr)u_{n,\bfk}(\bfr).
\tag{5}
$$
Equations (3)-(5) imply equation (1). To be consistent with how we defined $\psi_{n,\bfk+\bfK}$, we can also define
$$
\epsilon_{n,\bfk+\bfK}\equiv\epsilon_{n,\bfk}
\tag{6}
$$
for all $\bfk$ in the first Brillouin zone and for all reciporocal lattice vectors $\bfK$. We can take (1) and (6) to depend smoothly on $\bfk$ within the first Brillouin zone, but this does not imply that $\epsilon_{n,\bfk}$ is a smooth function of $\bfk$ when $\bfk$ crosses a zone boundary! Here's the key point:

The choices (1) and (6) enforce periodicity in $\bfk$ instead of enforcing smoothness in $\bfk$ at the zone boundaries.

We can think of equations (1) and (6) as defining how the wavefunctions and bands are indexed in the other Brillouin zones, given a choice of indexing in the first Brillouin zone. With this definition, the index $n$ may jump when tracing a band smoothly (differentiably) across a zone boundary, as anticipated in the question. Alternatively, we could have used a different definition in which they are taken to vary smoothly with $\bfk$ across all zones, for each $n$, but that way of indexing things might not agree with the one defined by (1) and (6). Both ways of indexing things are legitimate, but they're not necessarily equivalent.
To see that they're not always equivalent, consider the case $V=0$. This is periodic with respect to any lattice, so choose an arbitrary lattice and consider equations (1) and (6). If we had indexed the bands to be smooth for all $\bfk$, then $\epsilon_{n,\bfk}$ would be a quadratic function of $\bfk$ that increases without bound as $|\bfk|$ increases. That's not consistent with (6), so this is a case where enforcing periodicity is not the same as enforcing smoothness.


TITLE: Constructing a continuous function whose graph seems 'special'
QUESTION [5 upvotes]: I've been reading through Zorich's "Analysis I" book recently, and I came across this nice little exercise.
Let $f: [0,1]\to \mathbb R$ be a continuous function such that $f(0)=f(1)$. Show that

for any $n\in \mathbb N$ there exists a horizontal closed interval of length $\frac 1n$ with endpoints on the graph of this function;
if the number $\ell$ is not of the form $\frac 1n$ there exists a function of this form on whose graph one cannot inscribe a horizontal chord of length $\ell$.

The first part can be proven like this:
Consider $g: [0,(n-1)/n] \to \mathbb R$ given by $g(x) = f(x) - f(x+1/n)$. Then
$$\sum_{k=0}^{n-1} g(k/n) = 0$$
and therefore either all of these points are zero or there exists both a point where $g$ is positive and a point where $g$ is negative. By continuity, there must then also be a point where $g = 0$. So we are done.
Now, the second statement seemed rather counterintuitive, and I have given it some time now, but don't see a counterexample for $\ell < 1/2$.
(For $\ell > 1/2$ the function $f(x) = \sin(2\pi x)$ will do.)
Can anyone help me out?
Cheers,

REPLY [5 votes]: Try $f(x) = \sin^2(\pi x/\ell) - x \sin^2(\pi/\ell)$