TITLE: Complement of a set and inverse image.
QUESTION [7 upvotes]: I'm currently taking a real analysis class and we are working on measurable functions (the notes can be found here under "Measurable Functions"; the exercise is the first one on the last page).

$$\text{Let }f:E \to \mathbb{R}\text{ and }A\subseteq \mathbb{R}.\\\text{
Show that }f^{-1}(A^{C}) = E - f^{-1}(A).$$

I can easily visualize that this is indeed true (I drew a graph), but I'm unsure how to approach the proof. This chapter is dealing with measurable functions, however we do not have in the hypothesis that $f$ is measurable, and I'm not sure this is even needed in proving the claim.
My first strategy was assuming in two cases that $A$ is closed and open (therefore $A^{C}$ is open and closed respectively) and then going from there using neighborhoods, but this route seems like I'm making the problem harder than it is. I'm also unsure if I could prove the claim this way.
I'm also curious if I can prove this equality by basic set inclusion, i.e.: an element from set $A$ is in set $B$ and vice versa.
Any assistance in approach would be greatly appreciated.
EDIT: Also, I believe this could be a simple property of preimages and such, but still I'm unsure how to approach.

REPLY [0 votes]: Here's another way to think about it that might help.
Let $g$ be an indicator function defined as follows.
$$ \begin{align} g(x) = 1 & \;\; \text{if and only if} \;\; f(x) \in A \\ g(x) = 0 & \;\; \text{otherwise} \end{align} $$
$f^{-1}(A^C)$ is $g^{-1}(0)$ and $E - f^{-1}(A)$ is $E - g^{-1}(1)$ . Since the image of $g$ is $\{0, 1\}$ everything that isn't sent to $1$ is sent to $0$. Therefore $g^{-1}(0)$ is equal to $E - g^{-1}(1)$. Therefore, as desired
$$ f^{-1}(A^C) = E - f^{-1}(A)$$
Another way of looking at it is, since $f^{-1}(A^C)$ and $f^{-1}(A)$ are disjoint and $f$ is a total function on $E$ (presumably), the following is true because, forall $x$ in $E$, $f$ either sends $x$ to $A$ or it doesn't.
$$ f^{-1}(A^c) \sqcup f^{-1}(A) = E $$
$\sqcup$ denotes the disjoint union.


text:
\section{LS-CS stability}
aa

\subsection{LS-CS (dynamic CS-residual) algorithm}
LS-CS uses partial knowledge of support in a different way than modified-CS.
The LS-CS algorithm \cite{just_lscs} is the same as the dynamic modified-CS algorithm but with step \ref{modcsstep} replaced by

\bi
\item {\em CS-residual step. }
\bi
\item Use $T:=\Nhat_{t-1}$ to compute the initial LS estimate, $\xhat_{t,\text{init}}$, and the LS residual, $\tty$, using
\label{initls}
\bea
(\xhat_{t,\text{init}})_{T} \se {A_{T}}^\dag y_t, \ \ (\xhat_{t,\text{init}})_{T^c} = 0 \nn \\
\tty \se  y_t - A \xhat_{t,\text{init}}
\label{deftty0}
\eea
\item Do CS on the LS residual, i.e.  solve (\ref{simplecs}) with $y= \tty$ and denote its output by $\betahat_t$. Compute
\bea
\xhat_{t,\CSres} : = \betahat_t + \xhat_{t,\text{init}}.
\label{xhatcsres}
\eea
\ei
\ei

The CS-residual step error can be bounded as follows. The proof follows in exactly the same way as that given in \cite{just_lscs} where CS is done using Dantzig selector instead of (\ref{simplecs}). We use (\ref{simplecs}) here to keep the comparison with modified-CS easier.

\begin{theorem}[CS-residual error bound \cite{just_lscs}]
If  $\|w\| \le \eps$, $\delta_{2|\Delta|} < \sqrt{2}-1$ and $\delta_{|T|} < 1/2$,
\label{lscsbnd}
\bea
&& \|x_t - \xhat_{t,\CSres}\| \le C'(|T|,|\Delta|) \eps +  \theta_{|T|,|\Delta|} C''(|T|,|\Delta|) \|x_\Delta\| \nn \\
&& C'(|T|,|\Delta|)  \defn C_1(2|\Delta|) + \sqrt{2} C_2(2|\Delta|) \sqrt{\frac{|T|}{|\Delta|}} \nn \\
&& C''(|T|,|\Delta|) \defn 2 C_2(2|\Delta|) \sqrt{{|T|}}, \ \text{where} \nn \\
&& \text{$C_1(S)$ is defined in (\ref{defC1s}),~}  C_2(S) \defn 2\frac{1 + (\sqrt{2}-1) \delta(S)}{1 - (\sqrt{2}+1) \delta(S)}
\eea
\end{theorem}

\subsection{Stability result for LS-CS (dynamic CS-residual)}
The overall approach is similar to the one discussed above for modified-CS. The key difference is in the detection condition lemma, which we give below.

\begin{lemma}[Detection condition for LS-CS]
Assume that $\|w\| \le \eps$, $|T| \le S_T$ and $|\Delta| \le S_\Delta$.
Let $b:=\|x_\Delta\|_\infty$. For a $\gamma \le 1$, let $\Delta_1:=\{i \in \Delta: \gamma b \le |x_i| \le b \}$ and let $\Delta_2:= \Delta \setminus \Delta_1$. Assume that $|\Delta_1| \le S_{\Delta_1}$ and $\|x_{\Delta_2}\| \le \kappa$.
\\
All $i \in \Delta_1$ will definitely get detected at the current time if
$\delta{(2S_\Delta)} < \sqrt{2}-1$, $\delta{(S_T)} < 1/2$,
\label{detectcond_lscs}
\bea
&&   \theta{(S_T,S_\Delta)} \sqrt{S_{\Delta_1}} C''(S_T,S_\Delta) < {\gamma} \ \ \text{and} \nn \\
&& \max_{|\Delta| \le S_\Delta} \frac{ \alpha_{add} + C'(S_T,|\Delta|)\eps  + \theta{(S_T,|\Delta|)} C''(S_T,|\Delta|) \kappa }{\gamma - {\theta{(S_T,|\Delta|)}} \sqrt{S_{\Delta_1}} C''(S_T,|\Delta|)} < b \ \  \nn
\label{detcond_lscs}
\eea
where $C'(.,.)$, $C''(.,.)$ are defined in Theorem \ref{lscsbnd}.
\end{lemma}

{\em Proof: }
From Theorem \ref{lscsbnd}, if $\|w\| \le \eps$, $\delta{(2|\Delta|)} < \sqrt{2}-1$, $\delta{(|T|)} < 1/2$, then $\|x - \xhat_{CSres}\| \le C'(|T|,|\Delta|) \eps +  \theta{(|T|,|\Delta|)} C''(|T|,|\Delta|) \|x_\Delta\|$.
Using $\|x_\Delta\|  \le \sqrt{|\Delta_1|} b + \|x_{\Delta_2}\|$, fact \ref{det1} of Sec. \ref{stab_modcs} and the fact that for all $i \in \Delta_1$, $|x_i| \ge \gamma b$, we can conclude that all $i \in \Delta_1$ will get detected if $\delta{(2|\Delta|)} < \sqrt{2}-1$, $\delta{(|T|)} < 1/2$ and $\alpha_{add} + C' \eps + \theta C'' \|x_{\Delta_2}\| + \theta C'' \sqrt{|\Delta_1|} b < \gamma b$. The third inequality holds if ${\theta} \sqrt{|\Delta_1|}C'' < {\gamma}$ and $\frac{\alpha_{add} + C' \eps + \theta  C'' \|x_{\Delta_2}\|}{\gamma - \theta \sqrt{|\Delta_1|} C''} < b$.

Since we only know that $|T| \le S_T$, $|\Delta| \le S_\Delta$,  $|\Delta_1| \le S_{\Delta_1}$ and $\|x_{\Delta_2}\| \le \kappa$, we need the above inequalities to hold for all values of  $|T|,|\Delta|,|\Delta_1|,\|x_{\Delta_2}\|$ satisfying these upper bounds. This leads to the conclusion of the lemma. The left hand sides (LHS) of all the required inequalities, except the last one, are non-decreasing functions of  $|\Delta|,|T|,|\Delta_1|$ and thus we just use their upper bounds. The LHS of the last one is non-decreasing in $|T|,|\Delta_1|,\|x_{\Delta_2}\|$, but is not monotonic in $|\Delta|$ (since $C'(|T|,|\Delta|)$ is not monotonic in $|\Delta|$). Hence we explicitly maximize over $|\Delta| \le S_\Delta$.

$\blacksquare$

The stability result then follows in the same fashion as Theorem \ref{stabres_modcs}. The only difference is that instead of Lemma \ref{detectcond_modcs}, we use Lemma \ref{detectcond_lscs} applied with $S_T=S_0, S_\Delta=k_1(d_0)$, $b=d_0M/d$, $\gamma=1$, $S_{\Delta_1}=S_a$ and $\kappa = \sm(d_0)$.

\begin{theorem}[Stability of LS-CS]
Assume Signal Model \ref{sigmod2} and $\|w\| \le \eps$. If the following hold for some $1 \le d_0 \le d$,
\ben
\item  {\em (add/del thresholds) } (same condition as in Theorem \ref{stabres_modcs})
\item {\em (no. of measurements, $n$) } $n$ is large enough so that
\label{measmodel_lscs}
\ben
\item $\delta{(2k_1(d_0))} < \sqrt{2}-1$ and $\delta{(S_0+S_a + f)} < 1/2$

\item $ \theta{(S_0,k_1(d_0))} \sqrt{S_a} C''(S_0,k_1(d_0))   <  1$
\label{measmodel_lscs_2}
\een

\item {\em (SNR and $n$) } $(d_0M/d) \ge \max(\tilde{G}_1,\tilde{G}_2)$, where
\label{add_del_lscs}
\bea
&& \tilde{G}_1 \defn
\max_{|\Delta| \le k_1(d_0)} \nn \\ &&
 [\frac{ \alpha_{add} + C'(S_0,|\Delta|)\eps  + \theta{(S_0,|\Delta|)} C''(S_0,|\Delta|) \sm(d_0) }{\gamma - {\theta{(S_0,|\Delta|)}} \sqrt{S_a} C''(S_0,|\Delta|)}] \nn \\
&& \tilde{G}_2 \defn \alpha_{del} + \sqrt{2} \eps + 2{\theta{(S_0+S_a+f,k_2(d_0))}} \sm(d_0) \nn
\eea

\item {\em (initialization) }  (same condition as in Theorem \ref{stabres_modcs})
\een
then, all conclusions of Theorem \ref{stabres_modcs} and Corollary \ref{stabres_modcs_cor} hold for LS-CS, except the second claim of Corollary \ref{stabres_modcs_cor}, which is replaced by $\|x_t - \xhat_{t,\CSres}\| \le \max_{|\Delta| \le k_1(d_0)} [ C'(S_0,|\Delta|)\eps  + \theta{(S_0,|\Delta|)} C''(S_0,|\Delta|)[e(d_0)+S_a (d_0M/d)^2]]$.
\label{stabres_lscs}
\end{theorem}

\subsection{Implications of the Results and Comparisons}
Both the stability results provide sufficient conditions under which the number of misses is less than $(2d_0-2)S_a$ and the number of extras is zero.
From our discussion in the introduction, stability is meaningful only if $(2d_0-2)S_a \ll S_0$.
From \cite{icipmodcs}, we know that support changes slowly, i.e. $S_a \ll S_0$. Also, usually it is valid to assume that either $2dS_a \ll S_0$ (only a small number of coefficients are increasing or decreasing) or $M$ is large enough to ensure that $d_0 \ll d$. Either of these ensures $(2d_0-2)S_a \ll S_0$.

For modified-CS, under Signal Model \ref{sigmod2}, ``stability" is ensured under the following fairly mild assumptions: (a) the addition/deletion thresholds are appropriately set (conditions \ref{addthresh} and \ref{delthresh});  (b) the noise is bounded and the number of measurements, $n$, is large enough for condition \ref{measmodel} to hold; and (c) for a given support change rate, $S_a$, and magnitude change rate, $M/d$, the worst-case noise power, $\eps^2$ is small enough and $n$ is large enough to ensure that condition \ref{add_del} holds.

The main difference for LS-CS stability is that the detection condition is much stronger (compare Lemma \ref{detectcond_lscs} with Lemma \ref{detectcond_modcs}). This is because CS-residual error depends on $\|x_\Delta\|$, while there is no such dependence for modified-CS. Thus LS-CS needs an extra condition on $\theta{(S,S')}$ given in condition \ref{measmodel_lscs_2} of Theorem \ref{stabres_lscs}, which may not hold if $n$ is too small.
Also, when $n$ is just large enough for condition \ref{measmodel_lscs_2} to hold,  $\tilde{G}_1$ (defined in condition \ref{add_del_lscs}) may be very large and thus LS-CS will need higher signal increase rate, $M/d$, for its condition \ref{add_del_lscs} to hold.

When $n$ is large enough (for stability), it is easy to set $\alpha_{add}$ so that there are few false detections, $f$, compared to $S_0$, e.g. in our simulations, the average value of $f$ was less than 1 when $S_0=20$. Now, $f \ll S_0$ along with $(2d_0-2)S_a \ll S_0$ (discussed earlier) implies that the requirements of Theorem \ref{stabres_modcs} on $n$ (condition \ref{measmodel}) are {\em significantly weaker} than those for the corresponding CS result \cite{candes_rip} which requires $\delta(2S_0) \le \sqrt{2}-1$.
The same is true when comparing the LS-CS requirements with those for CS, as long as $M/d$ is large enough to ensure that $d_0$ is small enough for its conditions \ref{measmodel_lscs_2} and \ref{add_del_lscs} to hold.

config: arxiv


text:
\paragraph{Distributionally robust learning under adversarial perturbation.}
We now demonstrate the framework of \sfg in Algorithm~\ref{alg:sgd} in a non-convex setting.

For simplicity, we consider a MNIST binary classification task with a two-layer neural network.
We emphasize that the deliberate choice of this simple architecture ablates factors known to implicitly influence robustness, such as regularization and dropout.
The data set contains images of zero and one (i.e., two classes).
Each image $x$ is represented by $x\in[0,1]^{28 \times 28}$.

The test data is perturbed by an \emph{unknown} disturbance, i.e., $\tilde x_\mathrm{test} : = x + \delta$ where $x\sim P_{\mathrm{test}}$ is the unperturbed test data and $\delta$ is the perturbation.
In the plots, $\delta$ is generated by the PGD algorithm~\cite{madryDeepLearningModels2019} using projected gradient descent to find the worst-case perturbation within a box $\{\delta:\|\delta\|_\infty\leq \Delta\}\}$.
We compared \sfg (\kdro) with ERM and PGD (cf. \cite{madryDeepLearningModels2019,madryAdversarialRobustnessTheory}).
Note

the overall loss of PGD is an average loss instead of a worst-case one. Hence it is already less conservative than RO.

We train a classification model $g_\var\colon x \mapsto y$ using SFG-DRO in Algorithm~\ref{alg:sgd}, with the SA subroutine of \cite{lanAlgorithmsStochasticOptimization2020a}.
During training, we set the ambiguity size of \sfg as $\epsilon=0.5$ and domain \domain to be norm-balls around the training data $\domain=\{\zeta = X + \delta: \|\delta\|_\infty\leq 0.5\}$ where $X$ is the training data.

Figure~\ref{fig:mnist_viz}~(left) plots unperturbed test samples.

Figure~\ref{fig:mnist_curve} shows the classification error rate as we increase the magnitude of the perturbation $\Delta$.

We observe that ERM attains good performance when there is no test-time perturbation but quickly underperforms as the noise level increases.
PGD

is the most robust under large perturbation, but has the worst nominal performance.

\sfg possesses improved robustness while its performance under no perturbation does not become much worse.

This is consistent with our theoretical insights into RO and DRO.


TITLE: How to show $ \sin x \geq \frac{2x}{\pi}, x \in [0, \frac{\pi}{2}]$?
QUESTION [4 upvotes]: I have tried the following:
$$
f(x) = \sin x-\frac{2x}{\pi} \\
f'(x)= \cos x-\frac{2}{\pi} \\
f''(x) = -\sin x \leq 0
$$
But this doesn't seem to be heading in the right direction as it would appear $f'(x)$ is decreasing and has a zero within the domain, so I'm not sure how this might be used to prove the inequality.

REPLY [3 votes]: Let
$$f(x) = \frac{\sin{x}}{x} \quad\implies f'(x) = \frac{g(x)}{x^2}~~ \text{with} \quad g(x) = x\cos{x} -\sin{x} $$
and
$$g'(x) = -x\sin{x}\le 0$$
For $x \in [0,\frac{\pi}{2})$, we have $g'(x) \le 0$, then $g$ is decreasing whereas  $g(0) = 0 $.
Thus $g(x) \le 0$ on this interval. As a result, $f'(x) \le 0$ too, hence $f$ is decreasing on $[0,\frac{\pi}{2}]$. That is $$\frac{\sin{x}}{x} =f(x) \ge f(\pi/2) =\frac{2}{\pi}~~for ~~~0\le x\le \pi/2$$


TITLE: Estimate the number of elements by random sampling with replacement
QUESTION [3 upvotes]: Setup:

$N$ numbered balls are in a bag. $N$ is unknown.
Pick a ball uniformly at random, record its number, replace it, shuffle.
After $M$ samples, of which we noticed $R$ repeated numbers, how can we estimate the value of $N$?

Clearly, after we've covered the set, only repeats will appear. However, there is a vanishingly small probability we've just missed one.
Simplification:
Assume we know $N<n^\star$, which should make it easy to compute $P(N=n|R=r,M=m)$ for all $n<n^\star$.
Possibly related:

probability distribution of coverage of a set after X independently, randomly selected members of the set. Though $N$ is known and coverage is estimated? Here we'd like to estimate $N$.

How many random samples needed to pick all elements of set?
Not the same problem, however.

The exact probability of observing x unique elements after sampling with replacement from a set with N elements, A sub-problem? Could we compute the probability $N=n$ by using an answer to this question.

Application:
Estimating the number of webcomics when I'm pressing "random," assuming random is uniform over the comics.

REPLY [2 votes]: Chance of getting a repeat = (M-R)/N which we are going to call a "failure". Call this probability (M-R)/N = (1-P). Now the number of successful draws we have had (without getting a repeat) is M-R. Call this K. Now we just have  a negative binomial distribution with R failures occurring.
The mean of the neg. binomial distribution is the number of successes before the Rth failure. In this case M-R. So M-R = pR/(1-p) with p being defined above.
$$
   \ M-R = (1 - (M-R)/N))R / (M-R)/N
$$
$$
\ = (R - (M-R)R/N) * (N / (M-R)) = NR/(M-R) - R = M - R
$$
$$
\ = M = NR/(M-R) = M^2 - RM = NR --> N = (M^2/R) - M
$$


TITLE: Why are the coefficients of the base states of a qubit complex numbers?
QUESTION [1 upvotes]: Why are qubits represented as $$\left|{q}\right\rangle = \alpha\left|{0}\right\rangle+\beta\left|{1}\right\rangle\equiv\alpha\left[{1 \ 0}\right]^T+\beta\left[{0 \ 1}\right]^T; \alpha,\beta\in\mathbb{C}$$ rather than $$\left|{q}\right\rangle = a\left[{1 \ 0 \ 0}\right]^T+b\left[{0 \ 1 \ 0}\right]^T+c\left[{0 \ 0 \ 1}\right]^T; a,b,c\in\mathbb{R}\text{ ?}$$
Wouldn't these to representations be equivalent (assuming $\alpha^2+\beta^2=1$ and $a^2+b^2+c^2=1$)? If so, what is the mathematical (not physical) reason for choosing the former representation?

REPLY [3 votes]: Since $|q\rangle$ is an element of $\mathbb{C}^2$, $\alpha$ and $\beta$ are complex you have 4 degrees of freedom in total.
The group acting on qubits is the unitary group $\text{U}(2)$, with a 4 dimensional Lie algebra, given you the possibility to alter all coefficients $\alpha=\alpha_1+i\alpha_2$ and $\beta=\beta_1+i\beta_2$.
Your real representation has only 3 dimensional and is therefore not enough. I also found it strange, since 1 of these degrees, the complex phase $e^{-i\phi}$ is physically not measurable, but if you work with more than 1 qubit, it becomes important, for example $\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$ and $\frac{1}{\sqrt{2}}(|00\rangle-|11\rangle)$ are orthogonal, but differ only in the phase of one qubit.
If you work with density operators $|q\rangle\langle q|$ a phase factor $e^{-i\phi}$ (1 degree of freedom) cancels and gives a 3 dimensional representation for 1 qubit.


TITLE: Veličković's model game
QUESTION [3 upvotes]: This question is about the argument for Lemma 3.7 in Forcing axioms and stationary sets (MSN) by Boban Veličković.
He defines a game $G_\alpha$ between two players, playing objects in $H_\kappa$, depending on a function $F : [\kappa]^{<\omega} \to \kappa$. At stage $n$, Player I plays an interval of ordinals $I_n$ below $\kappa$ and an ordinal $\xi_n \in I_n$.  Player II plays an ordinal $\mu_n$.  $\min(I_{n+1})$ must be above $\mu_n$.  Player I wins if the closure $M$ of $\{ \xi_n : n < \omega \} \cup \alpha$ under $F$ is contained in $\bigcup_n I_n$, and $M \cap \omega_1 = \alpha$.
Now I understand the argument for why player I has a winning strategy when we ignore the requirement on $\alpha$.  For the $\alpha$-indexed games, he says: Let $A_F$ be the set of $\alpha<\omega_1$ such that player II has a winning strategy $\sigma_\alpha$. "Since $A_F$ has cardinality $\leq \aleph_1$, there is a strategy $\sigma$ which dominates all the $\sigma_\alpha$.  It follows that $\sigma$ is a winning strategy for II in $G_\alpha$ for every $\alpha \in A_F$."
What does it mean to say that a strategy "dominates" a lot of other ones (for the same player), and why does such $\sigma$ exist?

REPLY [4 votes]: What constitutes a partial play doesn't depend on $\alpha$.  And $\kappa$ is assumed to have cofinality strictly larger than $\aleph_1$.  So he means:  define $\sigma$ applied to a partial play to just be some ordinal below $\kappa$ that is above all the outputs of the $\aleph_1$-many strategies $\sigma_\alpha$.
(And it is easy to see that for any fixed $\alpha$, if $\sigma_\alpha$ is a winning strategy for II in the game $G_\alpha$, then so is any function from partial runs into $\kappa$ that is $\ge \sigma_\alpha$.)


TITLE: Geometric description of the domain of a function
QUESTION [0 upvotes]: A real function f of two real variables is given by $$f(x,y)=\sqrt{4 \sqrt{3}y-13x^2-7y^2-6 \sqrt{3}xy-4x}$$ Give a thorough geometric descrition of the domain of f using terms as open, ended, finite, infinite limited, connected and non conncted.
  Note: The terms have been directly translated and might not be the exact appropriate translation for for mathematics. Original language is Danish where Open: Åben, Ended: Afsluttet, Finite: Begrænset, infinite: Ubegrænset, Connected: Sammenhængene Non connected: Ikke-sammenhængene

How can this question be approached?

REPLY [0 votes]: If you take a pure translation
$$ x = p - \frac{1}{2} \; \; , \; \; y = q + \frac{\sqrt 3}{2} \; \; ,  $$
you reach
$$ 13 p^2 + 6 pq \sqrt 3 + 7 q^2 \leq 4 \; \; .  $$
Follow with a pure rotation,
 $$ p =  \frac{u \sqrt 3 - v}{2} \; \; , \; \; q =  \frac{u + v\sqrt 3}{2} \; \; ,  $$
you reach
$$ 4 u^2 + v^2 \leq 1 \; \; .  $$
Which is an ellipse with its interior. Closed, bounded, and connected.
Depends which order you are writing the rotation, anyway the matrix
$$
\left(
\begin{array}{rr}
\frac{\sqrt 3}{2} & - \frac{1}{2} \\
\frac{1}{2} & \frac{\sqrt 3}{2}
\end{array}
\right)
$$
is orthogonal, top row is sine and cosine of $120^\circ$


TITLE: Circular Wilson Loop in AdS/CFT
QUESTION [2 upvotes]: I'm trying to get the AdS solution to the circular wilson loop. The standard AdS metric is:

$ds^2 = \frac{L^2}{z^2}(\eta_{\mu \nu} dx^{\mu} dx^{\nu} + dz^2)$

If I take the circle of radius R at the x1,x2 plane I can choose polar coordinates:

$x_1 = R cos(\theta)$, $x_2 = R sin(\theta)$
$ds^2 = \frac{L^2}{z^2}(-dt^2 + dr^2 + r^2d\theta^2 + dx3^2 + dz^2)$

Now i want to find the area that minimizes the Nambu-Goto action:

$S_{NG} = \int d\sigma d\tau \sqrt{g}$

Where g is the usual pullback: $g_{ab} = G_{\mu \nu} \partial_a X^{\mu} \partial_b X^{\nu}$. Now my fields are $X^{\mu} = (t,r,\theta,x3,z(r))$ and I choose the gauge where: $\sigma = r$, $\tau = \theta$ from where i get:

$S_{NG} = \int dr d\theta \frac{L^2 r}{z^2} \sqrt{1 + z'^2}$

From where I see that the Hamiltonian is conserved and we get:

$H = \frac{-L^2 r}{z^2} \frac{1}{\sqrt{1+z'^2}}$

But the answer is $S_{NG}= \sqrt{\lambda} (\frac{R}{z_0}-1)$ and I don't know where the problem is.

REPLY [2 votes]: The Nambu-Goto action (including normalization) is
$$
S_{NG} = \frac{1}{2\pi \alpha'}\int dr d\theta \frac{L^2 r}{z^2} \sqrt{1 + z'^2}=\frac{L^2}{\alpha'}\int dr \frac{r}{z^2} \sqrt{1 + z'^2}
$$
The corresponding Hamiltonian is not conserved as the Lagrangian is explicitly $r$-dependent. You can however see that a solution to the equations of motion
$$
0=\frac{d}{dr}\frac{\partial L}{\partial z'}-\frac{\partial L}{\partial z}
$$
with the boundary condition $z(r=R)=0$ is given by $z(r)=\sqrt{R^2-r^2}$. Pluggin this back into the Nabu-Goto action (cutting off the integal at $z=z_0$, i.e. at $r=\sqrt{R^2-z_0^2}$ in order to regularize), leads to the following integral to be evaluated
$$
S_{NG}=\frac{L^2}{\alpha'}\int_0^{\sqrt{R^2-z_0^2}}dr\,\frac{R r}{(R^2-r^2)^{3/2}}=\frac{L^2}{\alpha'}\left(\frac{R}{z_0}-1\right).
$$
From the basic holographic relation $\frac{L^4}{\alpha'^2}=g_{YM}^2 N=\lambda$, we see that the prefactor is $\sqrt{\lambda}$


TITLE: The roots of quadratic equation $3x^2 - 5x - k = 0$ are $m/3$ and $m + 3$. Find the values of $m$ and $k$
QUESTION [3 upvotes]: Can someone please help me solve this equation. Please put in your working as well so I can see how to do this because this equation has been driving me crazy for days!

REPLY [1 votes]: Sum of roots of a quadratic equation $= -$( coefficient of $x$ / (coefficient of $x^2$)
So, in your case:
$\frac{5}{3}=m+3+\frac{m}{3}$. This will give you the value of $m$.
Further,
Product of roots of quadratic equation = constant term / coefficient of $x^2$.
Again, in your case:
$(m+3)(\frac{m}{3})=k$.
Since you know the value of $m$ from previous equation, you can get $k$ now.


TITLE: Closed form expression for the gamma function for complex numbers $s=a+ib$ with $b≠0$
QUESTION [2 upvotes]: Let us consider the famous gamma function.
My question is:
Is it possible to derive a closed expression for the gamma function for complex numbers $s=a+ib$ with $a≠1/2$, $b≠0$.
I know that such a closed form exists for integer values of $x=n$ for which $G(n)=(n-1)!$. Also, some non integers values have a closed form. Also if $a=1/2$ then a closed form exists. See this link:
https://mathoverflow.net/questions/112682/riemann-siegel-function-and-gamma-function

REPLY [2 votes]: The $\Gamma$ function lacks a closed form containing only elementary functions. Here are the equivalent formulas of the $\Gamma$ function however:
$$\Gamma(z)=\int_{0}^{+\infty}t^{z-1}e^{-t}dt$$
$$\Gamma(z)=\frac1z\prod_{n=1}^{\infty}\frac{(1+\frac1n)^z}{1+\frac zn}$$
$$\Gamma(z)=\frac{e^{-\gamma z}}{z}\prod_{n=1}^{\infty}\frac{e^{\frac zn}}{1+\frac zn}$$
where $\gamma$ is the Euler–Mascheroni constant. Of course we can relate the $\Gamma$ function with elementary functions via the following indentity:
$$\Gamma(1-z)\Gamma(z)=\frac{\pi}{\sin \pi z}$$
We also have Riemann's functional equation
$$\zeta(s)=2^s\pi^{s-1}\sin\frac{\pi s}2\Gamma(1-s)\zeta(1-s)$$
which relates the $\Gamma$ and the $\zeta$ functions.
If by closed form we mean an expression containing only elementary functions then no, $\Gamma$ has no such form. For more information read this


TITLE: Does de morgans law apply to literals within brackets?
QUESTION [1 upvotes]: This is the example I have, however, in the second line de morgans law does not turn the literals x,z, and y into not x,z,y. Why is this? Does deMorgans law not apply to those literals for some special reason?
≡ ∃x, y, ¬(¬(x < y) ∨ ∃z (x < z ∧ z < y)) (by p ⇒ q ≡ ¬p ∨ q)
≡ ∃x, y, ((x < y) ∧ ∀z (x ≥ z ∨ z ≥ y)) (byDeMorgan’s law)

REPLY [1 votes]: 1. Because negation is applied to formulas, and $x, y, z$ are not formulas.
$x$, $y$ and $z$ are variables. Variables are terms. Terms are those strings of symbols of the langauge which stand for objects. Here, the objects for which $x, y, z$ stand are numbers, so we can do $<$ etc. between them.
By definition, terms can be

a variable -- e.g. $x, y, z$,
an individual constant, which stands for one particular object -- e.g. $0$ could be a constant representing the object $0$, or
a function symbol applied to some terms -- e.g. $\text{add}$ could be the addition function which adds to terms, then $\text{add}(x,y)$,
  or more conveniently written as $x+y$, would also be a term, i.e. an
  expression which stands for some number again.

Next to terms, there are formulas. Formulas are those strings of symbols of the language which represent truth values. The formulas of first-order logic are inductively defined:

A predicate or relation symbol applied to a suitable tuple of terms is a formula -- so for example, since $x$ and $y$ and terms, putting
  the relation symbol $<$ between them yields a formula $x < y$,
  which stands for a truth value -- "true" if $x$ is strictly smaller
  than $y$ and "false" otherwise.
If $\phi$ is a formula, then $\neg \phi$ is a formula. Since we just established that $x < y$ is a formula, $\neg(x < y)$ is also a
  formula.
If $\phi, \psi$ are formulas, then $\phi \land \psi, \phi \lor \psi, \phi \to \psi$ are also formulas.
If $\phi$ is a formula and $x$ a variable, then $\forall x \phi$ and $\exists x \phi$ are also formulas.
Nothing else is a formula.

The important part here is 2.: $\neg \phi$ yields a formula if $\phi$ is a formula. But $x$ and $y$ are not formulas, but terms. So writing $\neg x$ or $\neg y$ is not just nonsensual -- because we can't negate something that doesn't have a truth value, and $x$ and $y$ don't represent truth values, but objects (e.g. numbers) -- it is simply not a formula of predicate logic at all, by the way the language of predicate logic is defined.
I would recommend you to have a second close look at the basic definitions like term or formula in your textbook and make sure you understood these definitions -- it is important to know what a formula is at all before you start evaluating complex propositions.

2. Because the De Morgan rule only changes the formula on the outermost level, and we do not pass the negation symbol arbitrarily deep down into the subformulas.
The De Morgan law applied here states that

$\neg(A \lor B) \equiv \neg A \lor \neg B$

In your case, $A$ is the formula $¬(x < y)$, and $B$ is the formula $∃z (x < z ∧ z < y)$. The precise equivalence steps of your formula are
$\neg A \quad \text{(after De Morgan)}\\
\equiv \neg \neg (x < y) \\
\equiv x < y \quad \text{by double negation elimination}$
and
$\neg B  \quad \text{(after De Morgan)}\\
\equiv \neg \exists z(x < z \land <y) \\
\equiv \forall z \neg (x < z \land z < y) \quad \text{by $\neg \exists z C \equiv \forall z \neg C$}\\
\equiv \forall z (\neg(x < z) \lor \neg (z < y)) \quad \text{by De Morgan on C}\\
\equiv \forall z(x \geq z \lor z \geq y) \quad \text{negation of $<$ is $\geq$}$
which is why your formula
$\exists x y \neg (A \lor B)$
eventually ends up as
$\equiv \exists x y (\neg A \land \neg B)\\
\equiv \exists x y (x < y \lor \forall z(x \geq z \lor z \geq y)$
The important point here is that the new negation $\neg$ in front of $\neg(x < y)$ introduced by the De Morgan rule is where it stops. The negation is applied to $A$, which is $\neg(x < y)$ and that's it. We do not pass on the the negation arbitrarily deep into the formula. For example, if instead of $\neg(x < y)$ we had $A :\equiv P(x) \to (Q(y) \lor R(z)))$, then $\neg A$ would be $\neg(P(x) \to (Q(y) \lor R(z))$; we would not carry the negation deeply into the formula like $(\neg P(x) \to (\neg Q(y) \lor \neg R(z)))$ or something. Any modification of the subformula inside the negation would be different rule applications, like the conversion $\neg \exists z C \equiv \forall z \neg C$ and the second De Morgan rule above, but these are different steps. The De Morgan rule above says to put another negation in front of $\neg (x < y)$ and that's it, we do not pass the negation sign deeper down into the formula except when we apply other rules on it in a new step. So even if $x$ and $y$ were formulas, there would be no reason to apply $\neg$ to them -- we already did that on the outside and that's where the De Morgan rule stops.


TITLE: Is division purely an arithmetic operator? Is it not the combination of arithmetic operation and relational operation?
QUESTION [1 upvotes]: An algorithm for computing the ratio of two positive numbers is the following: determine the number of times that the divisor can be subtracted from the numerator, until the accumulated effect of the subtraction operations produces a value less than the denominator.  So, to obtain the ratio (i.e. quotient), we perform an arithmetical operation (specifically,  subtraction) and also a comparison (to find whether the net result of subtraction is less than the divisor or not).
In this sense, is the division algorithm that was described above purely arithmetical, or is it a combination of an arithmetical operation and a comparison operation?

REPLY [1 votes]: I think most people would consider division a "basic arithmetic operation" in its own right. However, let's say we don't: what distinctions can we draw?
One precise sense in which division is not "arithmetically built from" addition, multiplication, and subtraction (say) is that there is no way to compose those functions to produce division. This leads into the idea of distinguishing between kinds of definability, which is a fundamental concept in logic and universal algebra. In the relevant jargon we could say for example that in $(\mathbb{R}; +,\times,-)$ division is definable but not term definable.
(Note that in the above I'm talking about exact division of real numbers, in contrast with your OP, but the result holds whichever notion we use.)
Another sense in which division isn't "purely arithmetic" is that (again, in the context of $\mathbb{R}$) it is partial: division by zero isn't allowed (while by contrast addition, subtraction, and multiplication are total). This winds up having universal-algebraic consequences: fields do not form a variety - roughly, this means that the basic axioms of division can't be boiled down to simple equations.


TITLE: Specialization of curves defined over function field
QUESTION [0 upvotes]: Let $C$ and $D$ be two algebraic curves defined over a function field $K(t)$ ($K$ is a number field). Suppose that $C$ and $D$ are isomorphic. We can specialize the curves to values in $K$ (nonformally this can be done by just pluggin in a number in $K$ instead of $t$). This scenario is the same as reducing from a generic fiber to a special fiber. Is it true that the specialization of the isomorphism will remain an isomorphism for all but finitely many values in $K$?
I am not sure if this is a natural thing to do, or if this is the best way to present the question. I appreciate any help on this.

REPLY [3 votes]: Writing out the isomorphism and its inverse map, all one has to do is to care that the denominators of the finitely many coefficients from $K(t)$ which appear in these two maps don't vanish under the specialization.


TITLE: Question about the determinant of an upper triangular matrix
QUESTION [1 upvotes]: I was watching an online lecture on the properties of determinants and at 27:00 in this lecture: https://www.youtube.com/watch?v=srxexLishgY&t=4s, the professor did a step which I don't understand.
If $A = \begin{pmatrix}d1 & 0 & 0\\ 0 & d2 & 0\\ 0 & 0 & d3\end{pmatrix} $, then according to the lecturer, $A=d1 *d2 *d3 \begin{pmatrix}1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\end{pmatrix}$, this was then used to show that the determinant of an upper triangular matrix can be written as the product of the leading diagonal
. However I thought if a matrix is multiplied by a number, all elements of the matrix are multiplied by it. Is this just wrong?

REPLY [0 votes]: you are right about multiplying a matrix by a constant.
The professor in the video is also right, because he is calculating the determinant of the matrix.


TITLE: prove that the BM25 scoring function is probabilistic?
QUESTION [1 upvotes]: Wiki says that this function is based on a probabilistic retrieval framework. However, how do you prove that the score is a probability. The ranking function is defined as follows:

Given a query $Q$ containing keywords $q_1,...,q_n$ the score of the
  document $D$ is given as above.
$$score(D, Q)=\sum_{i=1}^n IDF(q_i) . \frac{f(q_i, D)\cdot(k_1+1)}{f(q_i, D)+k_1\cdot(1-b+b\cdot \frac{|D|}{avgdl})}$$
where:

$f(q_i, D)$ is the frequency that keyword $q_i$ appears in document $D$.
$|D|$ is the length of the document (document size).
$avgdl$ is the average document length in the corpus (i.e. collection of documents).
$k_1$ & $b$ are free parameters
$IDF(q_i)$ is the inverse document frequency function. This is defined as follows: $$IDF(q_i)=\log\frac{N-n(q_i) +0.5}{n(q_i)+0.5}$$

where:

$N$ is the total number of documents in the corpus
$n(q_i)$ is the number of documents which contain keyword $q_i$

There are various ways of computing IDF. However in an abstract sense, $$IDF=\frac{total\, no.of\,documents}{no.\,of\,documents\,which\,contain\,term\,q_i}$$
To me the inverse ($IDF^{-1}$) appears to give a probabilistic value. I can't predict anything about the second product in the equation either.
In tests I have observed that the score gives values $=> 0$ (not something between $0<score<1$).

REPLY [0 votes]: $$\frac{\text{no. of documents which contain term } q_i} {\text{total no. of documents}}$$ is the probability that a single document, sampled uniformly from the corpus, turns out to contain the term $q_i$.
$$\log\frac{n(q_i)+0.5}{N-n(q_i) +0.5}$$ is not a probability as it may be positive or negative (for example when $n(q_i) \gt \frac12N$) , and may be greater than or less than $1$ in magnitude.  But it may be close to the first within a restricted range of interest.
The score does not need to be a probability.  Its primary purpose is for ranking documents given particular queries, and in some circumstances it can be seen as a measure of relevant information.