TITLE: Central Limit Theorem for Divisor function
QUESTION [3 upvotes]: A famous result by Erdős and Kac (https://en.wikipedia.org/wiki/Erdős–Kac_theorem) states that the number of prime factors of a "random" positive integer is approximately normally distributed. Namely, if $\Omega(n)$ denotes the total number of prime factors of $n$, then for any $a$,
$$\frac{1}{x}\#\{n \leq x : \frac{\Omega(n)-\log \log n}{\sqrt{\log \log n}} \leq a\} \to \int_{-\infty}^{a}\frac{1}{\sqrt{2\pi}}e^{-t^2/2}dt, $$
as $x\to \infty$.
I was wondering if there is a similar result for $\log d(n)$, where $d(n) = \sum_{d|n} 1$.

REPLY [4 votes]: It is important to recognize the intuition being used in this problem, before we come to the actual proof.
In fact, a lot of probabilistic number theory is based around some very simple intuition and reasoning involving distinct primes.
First, let me put a setting in place. We consider the set $\{1,2,...,n\}$ as a sample space with the uniform probability measure.
On this, we can define the following random variable : for $m \in \mathbb N$, $I_m(x)=0$ if $m \nmid x$ and $I_m(x)=1$ if $m | x$. The question is : if $p_1\neq p_2$ are distinct primes, then what is the relationship between $I_{p_1}$ and $I_{p_2}$?
The answer is actually quite simple : for large enough $n$, we have $E[I_{p_1}] \approx \frac{1}{p_1}$ , $E[I_{p_2}] \approx \frac 1{p_2}$ and $$E[I_{p_1}I_{p_2}] = E[I_{p_1p_2}] \approx \frac 1{p_1p_2} \approx E[I_{p_1}]E[I_{p_2}]$$
and therefore, $I_{p_1}$ and $I_{p_2}$ are (we've approximated, since the probabilities are not exact) weakly dependent for large enough $n$. (The exact notion of weak independence is established by a concrete bound for $|E[I_{p_1}I_{p_2}] - E[I_{p_1}]E[I_{p_2}]|$, which is quite easy to calculate).
This particular idea is fundamental. Let's quickly see why.
Note : The idea quickly generalizes to a family of such variables i.e. for distinct primes $p_1,...,p_n$, the family $I_{p_1},...,I_{p_n}$ is "weakly" dependent in that none of the random variables affect the other to a great degree for large $n$, with a concrete result easily providable.

Consider the quantity $\Omega(n)$, the number of distinct prime divisors of $n$. Now, the question is : given a prime $p$,does $p$ divide $n$? Now, we look over all primes $p$. In other words, fixing a $m$, for $n>m$ the value of the random variable $\sum_{p \text{ prime}} I_p$  is $\Omega(m)$!
But now, because of what we've written earlier, $\sum_{p \text{ prime}} I_p$ is the sum of a weakly dependent collection of random variables.
Now, we all know that if the random variables were independent, then the CLT would apply. However, the CLT does apply in weaker conditions where the dependence is present but really low.
But let's imagine independence did apply. If it did,then let $S_n = \sum_{k=1}^{n} I_{p_k}$. We have $E[S_n] = \sum_{k=1}^n \frac 1{p_k}$ (doesn't use independence), and it's well known that this behaves like $\log \log p_k$ to the first order (a proof using the prime number theorem to a first order correction is one way of doing this). What about $Var(S_n)$? Well, IF the random variables were weakly dependent, THEN the variance is the sum of variances, and we've got indicator random variables so the variance is quite clearly $Var(S_n) = \sum_{k=1}^n \frac {p_k-1}{(p_k)^2}$, which once again (basically because $p_k-1 \approx p_k$ will cancel the $p_k$ in the denominator) will look like $\log \log p_k$.
Therefore, we know that if CLT applied then $\frac{S_n - E(S_n)}{\sqrt{Var(S_n)}} \to N(0,1)$. Applying that here, and noting that $\Omega(n) = S_n$, we have
$$
\frac{\Omega(n) - \log \log n}{\sqrt{\log \log n}} \to N(0,1)
$$
and now , all that is left to see is that some variant of the CLT is available that works for weakly dependent RVs.

What about $d(n)$ then? Here, we need a way of counting the multiplicity of a prime. What kind of random variable counts multiplicity of a prime dividing a uniformly randomly chosen number? Well, to see this let's fix a prime $p$ and a large integer $k$.
It's easy to see that in the interval $\{1,...,p^k\}$, exactly $1$ element has multiplicity $k$, $p-1$ have multiplicity $k-1$, $p(p-1)$ have multiplicity $k-2$ , ,... , $p^{k-1}(p-1)$ have multiplicity $0$. Writing this as a probability vector after dividing by $p^k$ gives :
$$
\left[1 - \frac 1p , \frac 1p\left(1 - \frac 1p\right), \frac 1{p^2}\left(1-\frac 1p\right) , ... , \frac{1}{p^k}\right]
$$
which, barring the $k$-multiplicity part, clearly resembles a geometric distribution with success probability $1 - \frac 1p$.
And therefore, define geometric random variables $G_p$ for each prime $p$, given by $G_p(k)$ as the multiplicity of $p$ dividing $k$.
Now, it is quite clear that $G_p$ and $G_{p'}$ are weakly dependent for $p \neq p'$ (Explicit bounds are elementary). But here's the interesting point : for large primes $p$, it's extremely unlikely that $p$ will even divide a randomly chosen number, and it's even more unlikely that the multiplicity is bigger than $1$. Therefore, for all purposes, we must imagine that for large $p$, the value of $G_p$ is almost always $0$ or $1$. Explicit bounds will be available, once again!
With that, let's think about $\log d(n)$. Because $d$ is weakly multiplicative and $d(p^k) = k+1$, it is quite clear that $\log d(n) = \sum_{i} \log (G_{p_i}+1)$.
Now, let's repeat the CLT rigmarole. $d(n)$ is like the sum of weakly dependent random variables, so let's find their expectation and variance.
But HOW? We've got a logarithm of a Geometric random variable, and let's say that calculations get complicated quite quickly!
So we go back to our intuition : recall what I said about the geometric random variable nearly always being $0$ or $1$? Well, this means that we should be looking to compare the lower order behaviours of $\log(1+G_{p_i})$ with the random variable $\log(1+I_{p_i})$, where we note that $G_{p_i} = I_{p_i}$ with really high probability for large primes $p_i$.
Therefore, with this intuition, the expectations and variance will hopefully match with that of $\log(1+I_{p_i})$ up to the first order! The expectation of $\log (1+I_{p_i})$ is $\frac{\log 2}{p_i}$. The variance is $(\log 2)^2\frac 1{p_i}\left(1 - \frac 1{p_i}\right)$. Taking the sum over the primes, we get approximately $\log 2 (\log \log n)$ and noting that $\sum \frac 1{p_i^2}<\infty$ we get approximately $(\log 2)^2 \log \log n$ for the variance.
Once again, the heuristics apply and if the dependencies and the bounds work out, we should get $\frac{\log d(n) - \log 2\log \log n}{(\log 2)\sqrt{\log \log n}} \to N(0,1)$.
Of course, that's the heuristics. We learnt a lot from here , the main points being :

Independence of prime division counting indicator random variables.

Imagining the CLT held and seeing what happens.

Powers via geometric random variables.

The log - geometric approximation by the aforementioned indicators.

It is a good instructive exercise to see what one can do with similar additive functionals, like the sum of divisors function.
So what about the main proof?

At this point, I felt like I would be able to elementarily derive moment bounds which are required to solve this question from the approximations I made above. However, to be honest I just got so lost in the calculation! So I decided to make use of machinery.
Machinery, which is actually very heavy, and found as Theorem 3.1 of
Billingsley, Patrick, The probability theory of additive arithmetic functions, Ann. Probab. 2, 749-791 (1974). ZBL0327.10055.
which I state verbatim (note that it's a vast generalization of what we actually need!).

Suppose that $f_n$ are completely additive functions i.e. $f_n(ab)=f_n(a)+f_n(b)$ for $a,b$ coprime, and define
$$
A_n = \sum_{p \leq n} \frac{f_n(p)}{p} \\
B_n = \sqrt{\sum_{p \leq n}\frac{f_n^2(p)}{p}}
$$
suppose , furthermore that

$\lim_{m \to \infty} \frac{f_n(m)}{B_n} \to 0$.
$\max_{p \leq n} \frac{|f_n(p)|}{B_n} \to 0$.
Then
$$
\frac{f_n-A_n}{B_n} \to N(0,1)
$$

However, the proof isn't staggeringly difficult from what we have discussed! Indeed, IF random variables supported on different primes were independent, then $A_n$ is the exact mean and $B_n$ is the approximate variance (once you make $1 - p^{-1} \approx 1$ for large primes $p$) of each $f_n$. The proof is literally nothing but making sure that the dependence is weak enough for the moments to reflect , up to their first order, the products of the individual moments.
So what one does is considers an alternate family of random variables $g_n$, which are actually independent. How? quite simple : we first make each $f_n$ into a sum-of-weakly-dependent random variables, then we replace each random variable by independent instances of the "rough" random variable that they "should" ideally be (so replace $I_p$ by an actual independent Bernoulli random variable with parameter $1-\frac 1p$, and likewise the Geometric case). Now, we get a sum of independent random variables, for which we apply a traditional CLT (turns out Lyapunov's CLT works). So the CLT implies that the moments for the independent sum converge.
Now, we just make sure that the moments for the independent and the dependent case differ by something that vanishes in the limit, and that gives the result.
Let's apply this to our situation : we have $f_n \equiv f = \log d$, the divisor function. Let's calculate $A_n$ and $B_n$ for this.
Indeed, we first have
$$
A_n = \sum_{p \leq n} \frac{\log d(p)}{p} = \log 2\sum_{p \leq n} \frac 1p = \log 2 \log \log n + O(1/n) \\
B_n^2 = (\log 2)^2\sum_{p \leq n} \frac 1p = (\log_2)^2 \log \log n + O(1/n)
$$
Fix an $m$, then $d(m)$ is constant while $B_n \to \infty$ so the first condition is quite clearly satisfied. The second maximum is just , well, $d(p)=2$ so it's $\frac{2}{B_n}$ which goes to $0$ as $n \to \infty$. Hence, the conditions are satisfied and we are done!
Let me know if :

A more elementary proof is required : I can try to follow Billingsley's proof and provide it.

More explanation is needed in certain parts.


TITLE: How do I get an answer of $14$ using simpsons rule for $\frac{152e}{180n^4}<.0001$
QUESTION [1 upvotes]: I must have the algebra wrong somewhere but here is the original equation:
$$\frac{152e}{180n^4}<.0001$$
If I then multiply like this:
$$152e<.0001(180)n^4$$
Which then gives:
$$152e < .0018n^4$$
And then dividing:
$$\frac{152e}{.0018} < n^4$$
And then taking the fourth root:
$$\sqrt[4]{\frac{152e}{.0018}}< \sqrt[4]{n^4}$$
And I get about $n = 46.338$
But the book gives a solution of $14$.  Can someone explain where I went wrong?

REPLY [2 votes]: $\dfrac{152 \mathrm{e}}{180n^4}<0.0001$
$152 \mathrm{e} < 0.018n^4$
$\dfrac{152 \mathrm{e} }{0.018} < n^4$
$n > \sqrt[4]{22954.38}$
$n > 12.31$
This still doesn't explain why the solution is listed as $14$, though.


TITLE: If $A$ and $B$ are connected subsets of $\mathbb R$ then $A+B$ is also connected
QUESTION [0 upvotes]: My attempt:
We know that singletons and intervals are only connected subsets of $\mathbb R$. They all are convex sets. So $A$ and $B$ are also convex sets.
Now we show that $A+B$ is convex.
Let $x_1+y_1,x_2+y_2\in A+B$, so that $x_i \in A, y_i \in B, i=1,2$.
Let $0\leq t\leq 1$.
Then
$\begin{align}
& t(x_1+y_1)+(1-t)(x_2+y_2)\\
& =tx_1+ty_1+(1-t)x_2+(1-t)y_2\\
& = (tx_1+(1-t)x_2)+(ty_1+(1-t)y_2)\\
&\in A+B\end{align}\\$
$A+B$ is convex hence it is path connected and hence connected.
Is this correct?

REPLY [4 votes]: The sum of convex sets is indeed convex (in all vector spaces over $\Bbb  R$ generally), and the proof is fine. But here we can also use that the map $s:\Bbb R^2 \to \Bbb R$ given by $S(x,y)=x+y$ is continuous and when $A$ and $B$ are (path-)connected so is $A \times B$ and $A+B=s[A \times B]$ and we use that continuous images of (path-)connected spaces are again (path-)connected. This idea will also work for the sum of compact sets e.g.


TITLE: $\frac{d}{dt} (A+t B)^p\,\text{ for } p\geq 1$
QUESTION [13 upvotes]: Given two positive self-adjoint operators $A,B$ on a Hilbert space. Let $p\geq 1$.
I would like to calculate $$\frac{d}{dt}|_{t=0} (A+tB)^p,$$
where the power is defined through the spectral theorem. The difficulty is that $A$ and $B$ do not commute in general. Is there a nice formula for that?
I thought about using some integral representation of $x^p$, which hopefully would make the differentiation easier, but I was not successful.
Update:
Thanks for your answers. In my case, I actually only need it for $p\in [1,2)$. Using $y^p = \frac{\sqrt 3}{2\pi}\int_{0}^\infty dx \,\frac{y^2 x^{p-2}}{x+y}$, I thought about writing $C:=A+tB$ as $$C^p = \frac{\sqrt 3}{2\pi}\int_0^\infty C^2 x^{p-2} (x+C)^{-1} dx.$$
That might also work. I am still happy about other suggestions.

REPLY [4 votes]: I give you the answer in the finite dimensional case, and let you adapt it to the Hilbert space case. Let $f$ be an analytic function; in your case $f(t)=t^p$.
First of all, choose an orthonormal basis in which $A=:D$ is diagonal. Then form the matrix
 $f^{[1]}(D)\in{\bf M}_n({\mathbb C})$ by
$$f^{[1]}(D)_{jk}=\left\{\begin{array}{lr}
f'(d_j), & k=j, \\ \\ \frac{f(d_j)-f(d_k)}{d_j-d_k}, & k\ne j,\end{array}\right.$$
where we identify
$$\frac{f(b)-f(a)}{b-a}:=f'(a),$$
if $b=a$. Then the differential of $H\mapsto f(H)$, taken at $D$, is
$${\rm D}f(D)B=f^{[1]}(D)\circ B,
$$
where $A\circ B$ denotes the Hadamard product.
Edit. As noticed by Suvrit, this is Daleckii-Krein Formula.


TITLE: Is S is a subspace of$ \mathbb{P}[x]$?
QUESTION [0 upvotes]: Consider $\mathbb{P}_n[x]$ and $\mathbb{P}[x] $ over $\mathbb{R}.$
Is  $  S= \{ p(x) \mid p(x) \in \mathbb{P}[x] \text{ has degree 3}\}$ is a  subspace of $\mathbb{P}[x]$?

My attempt :  i thinks  yes  because by fundamental theorem  of algebra   every  odd degree  polynomial has  atleast one  root  that  mean $p(x) = x^3 +ax +b =0$ which implies $p(x)=0$
Is its true ??

REPLY [1 votes]: Unfortunately it is not true. One of the requarements is that $0$ is in subspace and that is not true in your case. Polynomial $0$ is not $3$.rd degree polynomial.
Or other reason, it is not closed for the operation $+$. Say $p(x)=-x^3+2$ and $q(x)=x^3$ are in $S$ but their sum $p(x)+q(x)=2$ is not.


TITLE: If a filter has a unique ultrafilter extending it, then it is that ultrafilter (prove without $\sf{AC}$)
QUESTION [6 upvotes]: I am not certain if $\sf AC$ (or more conservatively, $\sf UF=$ there is an ultrafilter extending any given filter) is necessary to prove the following statement:

For filters $F,G$ with $\bigcup F=\bigcup G$, say that $F$ extends $G$ if $F\supseteq G$. If $G$ has a unique ultrafilter extension $F$, then $F=G$.

My approach: Let $X=\bigcup F=\bigcup G$, and suppose $F$ is an ultrafilter extension of the filter $G$ with $x\in F$, $x\notin G$. Then $G\cup\{X\setminus x\}$ is a filter subbase, and $$H=\Big\{y\subseteq X\ \Big|\ \exists^{\rm fin}t\subseteq G\cup\{X\setminus x\}:\bigcap t\subseteq y\Big\}$$ is a filter that extends $G$. Now $X\setminus x\in H$ and $X\setminus x\notin F$, so $F$ cannot be an extension of $H$. Thus any ultrafilter extending $H$ would be a counterexample to the uniqueness of ultrafilters extending $G$.
Is there a way to make this final step without having to invoke $\sf UF$, by somehow taking advantage of the given ultrafilter extension $F$? I am envisioning some small modification of $F$ to change it into another ultrafilter for which $x\in F$ and $X\setminus x\in F'$.

REPLY [4 votes]: Suppose we are in a model where the following is true:

There are no free ultrafilters on $\Bbb N$.
There exists an amorphous set.

First of all note that if $A$ is amorphous, then $A$ carries exactly one free ultrafilter, all the cofinite subsets. Then in this model $A\cup\Bbb N$ has only one unique ultrafilter, all those containing a cofinite subset of $A$.
Consider now the filter $F=\{A\cup M\mid M\text{ is a cofinite subset of }\Bbb N\}$. Then $F$ is not free and can be extended to only one free ultrafilter, but consider now the filter $G$ generated by adding $\Bbb N$ to $F$, that filter cannot be extended anymore to free ultrafilters.
So you do need to use some part of the axiom of choice to prove that, and indeed the cleanest part is the ultrafilter lemma.


TITLE: Simple harmonic motion qsn
QUESTION [0 upvotes]: Have been stuck with this question from classical mechanics under the simple harmonic motion the question is saying that if $$y=a\cos(\omega t)+b\sin(\omega t)$$ show it represents simple harmonic motion also find its amplitude, period and frequency. how can I show that it represents the simple harmonic motion?

REPLY [1 votes]: A system described by a function $x(t)$ exhibiting simple harmonic motion obeys the following differential equation
$$\frac{\text d^2x}{\text dt^2}=-Cx$$
where $C$ is some constant. The idea here is that there is a force that is trying to restore the system to equilibrium ($x=0$), and this force is proportional to how far away the system is from this equilibrium.
If you can verify that your solution obeys this differential equation, then you have shown it describes simple harmonic motion. I will leave that to you to figure out.


TITLE: Inverse by left multiplication but not right?
QUESTION [2 upvotes]: Suppose $T: V \rightarrow W$ and  $U: W \rightarrow V$ are linear transformations. It is known that $ U = T^{-1}$ if $UT = I_V$ and $TU = I_W$.
Is it possible to then also have a transform $Z: W \rightarrow V$ such that $ZT = I_V$ but $TZ \neq I_W$ (and likewise, $TZ = I_W$ but $ZT \neq I_V$)?

REPLY [1 votes]: If W, V are not the same dimension...e.g. suppose $V$ is $\mathbb R^3$ and $W$ is $\mathbb R^2$
Then there can exist $T, U$ such that $TU = I_W$  but since the rank of $T$ has rank less than $3$ it is not possible for $UT$ to be rank $3$ and be an the identity matrix of $\mathbb R^3$


TITLE: understand an answer to linear span of polynomal subspace exercise
QUESTION [0 upvotes]: i am looking at an answer to an exercise who asks to find a linear span for, and I don't really understand the solution
$$p(x) = ax^3 + bx ^2 + cx + d$$
and this is the solution i see
$$ p(x) \in M \leftrightarrow p(x) = p(x-1)$$
$$ \leftrightarrow ax^3 + bx^2 + cx +d = a(x-1)^3 + b(x-1)^2 + c(x-1) + d $$
$$\leftrightarrow ax^3 + bx^2 + cx + d = ax^3 + (b-3a)x^2 + (3a-2b+c)x+b-a-c+d$$
$$\leftrightarrow b-3a = b, 3a-2b+c = c, b-a-c+d = d $$
$$ \leftrightarrow a=b=c=0 $$
$$p(x) = d$$
$$Sp\{1\} = \{p(x) = d | d \in \mathbb{R}\} $$
now the thing that I don't really understand start from the third line how did they reach this equation? $$ax^3 + (b-3a)x^2 + (3a-2b+c)x+b-a-c+d$$ and how did they find the span from it?

REPLY [1 votes]: They are using
$a(x-1)^3+b(x-1)^2+c(x-1)+d=a(x^3-3x^2+3x-1)+b(x^2-2x+1)+cx-c+d$
$\hspace{2.5 in}=ax^3+(b-3a)x^2+(3a-2b+c)x+b-a-c+d$,
so setting the coefficients of the same powers of x equal to each other gives
$\;\;\;b-3a=b, \;\;c=3a-2b+c, \;\;d=b-a-c+d$.
Then $a=0$ from the 1st equation, so $b=0$ from the 2nd equation, and then $c=0$ from the 3rd equation.
Therefore $p(x)=ax^3+bx^2+cx+d=0x^3+0x^2+0x+d=d=d(1)$,
so the vector $\{1\}$ spans the subspace M.


text:
(*  Title:       Conflict analysis/Main Result
    Author:      Peter Lammich <peter.lammich@uni-muenster.de>
    Maintainer:  Peter Lammich <peter.lammich@uni-muenster.de>
*)
section "Main Result"
theory MainResult
imports ConstraintSystems
begin
text_raw \<open>\label{thy:MainResult}\<close>

text \<open>At this point everything is available to prove the main result of this project:
  {\em The constraint system @{term RUV_cs} precisely characterizes simultaneously reachable control nodes w.r.t. to our
  semantic reference point.}

  The ,,trusted base'' of this proof, that are all definitions a reader that trusts the Isabelle prover must additionally trust, is the following:
  \begin{itemize}
    \item The flowgraph and the assumptions made on it in the \<open>flowgraph\<close>- and \<open>eflowgraph\<close>-locales. Note that we show in Section~\ref{sec:Flowgraph:ex_flowgraph}
      that there is at least one non-trivial model of \<open>eflowgraph\<close>.
    \item The reference point semantics (@{term refpoint}) and the transitive closure operator (@{term trcl}).
    \item The definition of @{term atUV}.
    \item All dependencies of the above definitions in the Isabelle standard libraries.
  \end{itemize}
\<close>
theorem (in eflowgraph) RUV_is_sim_reach:
  "(\<exists>w c'. ({#[entry fg (main fg)]#},w,c')\<in>trcl (refpoint fg) \<and> atUV U V c')
    \<longleftrightarrow> (\<exists>Ml Me. (entry fg (main fg),Ml,Me)\<in>RUV_cs fg U V)"
\<comment> \<open>The proof uses the soundness and precision theorems wrt. to normalized paths (@{thm [source] flowgraph.RUV_sound}, @{thm [source] flowgraph.RUV_precise}) as well as the normalization result,
  i.e. that every reachable configuration is also reachable using a normalized path (@{thm [source] eflowgraph.normalize}) and, vice versa, that every normalized path is also a usual path (@{thm [source] ntr_is_tr}).
  Finally the conversion between our working semantics and the semantic reference point is exploited (@{thm [source] flowgraph.refpoint_eq}).\<close>
  (is "?lhs \<longleftrightarrow> ?rhs")
proof
  assume ?lhs
  then obtain w c' where C: "({#[entry fg (main fg)]#}, w, c') \<in> trcl (tr fg)" "atUV U V c'" by (auto simp add: refpoint_eq)
  from normalize[OF C(1), of "main fg", simplified] obtain ww where "({#[entry fg (main fg)]#}, ww, c') \<in> trcl (ntr fg)" by blast
  from ntrs.gtr2gtrp[where c="{#}", simplified, OF this] obtain s' ce' wwl where 1: "c'=add_mset s' ce'" "ww = map le_rem_s wwl" "(([entry fg (main fg)], {#}), wwl, s', ce') \<in> trcl (ntrp fg)" by blast
  with C(2) have 2: "atUV U V ({#s'#}+ce')" by auto
  from RUV_sound[OF 1(3) 2] show ?rhs by blast
next
  assume ?rhs
  then obtain Ml Me where C: "(entry fg (main fg), Ml, Me) \<in> RUV_cs fg U V" by blast
  from RUV_precise[OF C] obtain wwl s' c' where P: "(([entry fg (main fg)], {#}), wwl, s', c') \<in> trcl (ntrp fg)" "atUV U V ({#s'#} + c')" by blast
  from gtrp2gtr[OF P(1)] have "({# [entry fg (main fg)] #}, map le_rem_s wwl, {#s'#}+c') \<in> trcl (ntr fg)" by (auto)
  from ntr_is_tr[OF this] P(2) have "\<exists>w c'. ({#[entry fg (main fg)]#}, w, c') \<in> trcl (tr fg) \<and> atUV U V c'" by blast
  thus ?lhs by (simp add: refpoint_eq)
qed

end

subset_name: curated


TITLE: $\mathcal{D}$-classes
QUESTION [2 upvotes]: Let $$\alpha = \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
1&3&3
\end{array}\right) \in \mathcal{T}_3\text{.}$$
(a) Show that the $\mathcal{D}$-class of $\alpha$ contains all those elements of $\mathcal{T}_3$ which have the same rank (cardinality of their image) as $\alpha$.
(b) Show that the $\mathcal{D}$-class of $\alpha$ contains 3 $\mathcal{R}$-classes and 3 $\mathcal{L}$-classes and that it has 2 element $\mathcal{H}$-classes.
How to do (b)?
From (a) we have that $D_{\alpha} = \{ \beta \in \mathcal{T}_3 : | \text{Im}( \beta )| = 2 \}$.
Explicitly then:
$$D_{\alpha} = \left\{ \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
1&1&2
\end{array}\right), \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
1&2&1
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
2&1&1
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
2&2&1
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
2&1&2
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
1&2&2
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
3&3&1
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
3&1&3
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
1&3&3
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
1&1&3
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
1&3&1
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
3&1&1
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
2&2&3
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
2&3&2
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
3&2&2
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
3&3&2
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
3&2&3
\end{array}\right) , \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
2&3&3
\end{array}\right) \right\}$$

REPLY [0 votes]: I've had to change accounts as I can't access my email account so I can't reply to any posts because I'm not using the account I originally asked the question from!
So:
$\beta \in R_{\alpha} \iff \text{Ker}(\beta)$ has classes $\{1\},\{2,3\}$ and $\beta \in L_{\alpha} \iff \text{Im}(\beta) = \{1,3\}$
$$R_{\alpha} = \left\{ \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
1&2&2
\end{array}\right), \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
2&1&1
\end{array}\right), \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
1&3&3
\end{array}\right), \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
3&1&1
\end{array}\right), \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
2&3&3
\end{array}\right), \left(\begin{array}{@{\,}c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\;\; }c@{\,}}
1&2&3\\
3&2&2
\end{array}\right) \right\}$$


TITLE: Onto property of the function
QUESTION [0 upvotes]: How can we prove the onto property of this non-homogeneous function
$$f(x)= (|x|^{p-2} + |x|^{q-2}) x \quad \text{for} \quad x \in \mathbb{R} \quad \text{where} \quad p, q >1.$$
Any ideas (without performing any complicative calculations)?

REPLY [1 votes]: HINT
Since $f(0)=0$ and $f(x) \to \infty$ as $x \to -\infty$, IVT implies $\mathbb{R}^+ \subset \mathrm{Im}(f)$.
Can you do the other side?


TITLE: Proving a curve is a geodesic.
QUESTION [3 upvotes]: I am really stuck on the following question.
Let $ \ \gamma : I \longrightarrow M \ $ be a non-constant (i.e  $ \ \gamma'\ $  is not identically zero) geodesic. Show that a reparametrization $\ \gamma \circ h : J \longrightarrow M \ $ is a geodesic if and only if $ \ h: J \longrightarrow I \ $ is of the form $h(t) = at+b \ $ with $ \ a, b \in \mathbb{R}$.
Does anyone have any idea how to prove this?

REPLY [3 votes]: For $h: J\rightarrow I$ such that $s=h(t)$, we use $'$ to denote $\frac{d}{dt}$ and $\cdot$ to denote $\frac{d}{ds}$. Then  we have
$$(\gamma\circ h)'(t)=h'(t)\dot{\gamma}(s)$$
by chain rule.
Therefore, we have
$$\nabla_{(\gamma\circ h)'(t)}(\gamma\circ h)'(t)=
\nabla_{h'(t)\dot{\gamma}(s)}\Big(h'(t)\dot{\gamma}(s)\Big)$$
$$=
h'(t)\nabla_{\dot{\gamma}(s)}\Big(h'(t)\dot{\gamma}(s)\Big)=
h'(t)^2\nabla_{\dot{\gamma}(s)}\dot{\gamma}(s)+\frac{d}{ds}\big(h'(t)\big)\dot{\gamma}(s).$$ Since $\gamma(s)$ is geodesic, $\nabla_{\dot{\gamma}(s)}\dot{\gamma}(s)=0$, which implies that
$$\tag{1}\nabla_{(\gamma\circ h)'(t)}(\gamma\circ h)'(t)=\frac{d}{ds}\big(h'(t)\big)\dot{\gamma}(s).$$
Therefore, if $(\gamma\circ h)(t)$ is geodesic, i.e. $\nabla_{(\gamma\circ h)'(t)}(\gamma\circ h)'(t)=0$  if and only if
$$\tag{2}\frac{d}{ds}\big(h'(t)\big)=0.$$
Integrating it, we have
$h'(t)=a$, which implies that
$h(t)=at+b$ for some constant $a, b\in\mathbb{R}$. Conversely, if $h(t)=at+b$ for some constant $a, b\in\mathbb{R}$, then $(2)$ is satisfied, which implies that the expression in $(1)$ is zero, i.e. $(\gamma\circ h)(t)$ is geodesic.


TITLE: Find an equation for the surface with all points which are equidistant of $(-1,0,0)$ and the plane $x=1$
QUESTION [2 upvotes]: Find an equation for the surface with all points which are equidistant of $(-1,0,0)$ and the plane $x=1$. Draw the surface.
First, this is the graph I've depicted:

Some ideas to find such equation and the corresponding graph for the surface?

REPLY [2 votes]: If $z$ is not considered standard a 2D definition of parabola can be obtained by setting equal distances as:
$$x = -\frac{y^2}{4} $$
So with z considered it becomes a 3D generalized surface of revolution as a paraboloid rotated about $x$ axis vertically up  :
$$ (x,y,z) = (-2,2,2)$$
$$x = -\frac{y^2+z^2}{4} $$
$ yz $ plane is horizontal, $x$ axis is vertical as shown.


TITLE: Finite subgroups of SO(3) are defined by ramified coverings of Riemann spheres
QUESTION [4 upvotes]: As it is known from the classification of finite subgroups of $SO(3)$ (for example, here on page 3), there are such groups $G$ and their orders $e_i$ of stabilizer subgroups of point of set $S$ which contains points that are fixed by some nontrivial element of $G$:

Cyclic: n, n
Dihedral: 2, 2, n/2
Tetrahedral: 2, 3, 3
Octahedral: 2, 3, 4
Icosahedral: 2, 3, 5

It is easy to check that there are all possible cases of orders $e_i$ using Riemann-Hurwitz formula for ramified covering $X \rightarrow X/G$ by this subgroup ($n=|G|$ and $g=g(X/G)$):
$$2 = n (2-2g) - \sum \frac{n}{e_i}(e_i-1)$$
There is $\frac{n}{e_i}$ is size of orbit and $e_i$ is ramification index equal to size of stabilizer subgroup.
I am interesting whether it is possible to prove that there is only one group of defined orders of stabilizers - my plan is like this:

Let X, Y be two Riemann spheres with finite subgroups G, H with equal orbit sizes
Then both $X/G$ and $Y/H$ are of genus 0 so Riemann spheres
If there are three orbits, there are three branch points on $X/G$ and $Y/H$ so one can identify this points using 3-transitivity of $PSL(2,C)$
I suppose that one can also identify two ramified coverings of Riemann sphere by other Riemann sphere with equal ramification, but I have no idea how
Then $G$ is the group of deck transformations of this covering

REPLY [3 votes]: The classical Galois theory of covering spaces probably applies to do what you want in part 4.
Pop out the singular points on the base, and their inverse images up stairs, and now you have a classical covering space.  The group of deck transformation
of the covering $p:E\rightarrow B$ where $B,E$ are connected, locally path connected and Hausdorff, is isomorphic to $N(p_{\#}\pi_1(E,e))/p_{\#}\pi_1(E,e)$ where the normalizer $N(p_{\#}\pi_1(E,e))$ means the normalizer in $\pi_1(B,b)$, where of course we chose a basepoint $b\in B$ and a basepoint $e\in p^{-1}(b)$.
The fundamental group of the base in this case is an $n$-punctured sphere. It has presentation, $$\pi_1(S^2-\{n \ \mathrm{points}\})=\langle x_i|\prod_{i=1}^nx_i=e\rangle.$$
The generators correspond to a loop coming from the basepoint, and going around a deleted point. If you choose them carefully the last loop is the inverse of the product of the first $n-1$, leading to the presentation above.
Naming the ramification index of each point you popped out allows you to name a normal subgroup of  $\pi_1(S^2-\{n \ \mathrm{points}\})$. Specifically the normal subgroup generated by $x_i^{e_i}$.
Since this subgroup is normal, it's normalizer is all of
$$\pi_1(S^2-\{n \ \mathrm{points}\})=\langle x_i|\prod_{i=1}^nx_i=e\rangle.$$
So the group of deck transformations is going to be,
$$G(p,E)=\langle x_i|\prod_{i=1}^nx_i=e, x_i^{e_i}=e\rangle.$$
In the cases where you are interested except for the cyclic group, you have classical triangle groups, and the presentation above from the branching data is exactly the classical presetation so they are isomorphic.
For instance in the case of ramification indices $2,3,5$ the presentation is
$$ \langle x_1,x_2,x_3| x_1x_2x_3=e, x_1^2=e,x_2^3=e,x_3^5=e\rangle,$$
the standard presentation of the icosahedral group.
The cyclic group also gets the classical presentation by this procedure.
Get careful with the theory of covering spaces, and be careful with your branch points and you will have a proof.


TITLE: What is the probability that 2 people don't meet at the gym in a given week?
QUESTION [0 upvotes]: Lindsey randomly selects two distinct days each week to go rock-climbing at the gym. Jess randomly selects three distinct days each week to climb at the same gym. What is the probability that Lindsey and Jess will both be at the gym on the same day at least once in any given week? Express your answer as a common fraction.
I thought the answer should be 1-36/2401
$P(Meet >=1) = 1-P(Meet=0)$
The probability of meeting 0 times is just the probability of any arrangment of meeting times the number of ways we can choose 5 unique days out of the week.
$P(Meet=0) = 3/7 * 2/7 *1/7 *2/1 * 1/7 * C^7_5$
$=6*6/7^4$
$=36/2401$
However, the correct answer is 5/7. What is wrong with my methodology?

REPLY [2 votes]: Jess picks $3$ days.  We want the probability that Lindsay picks a day that Jess has picked.  It's easier to compute the complement.  The probability that Lindsay picks both days from the two that Jess hasn't picked is $${{4\choose2}\over{7\choose2}}={{4\cdot3}\over{7\cdot6}}=\frac27$$ so the probability we seek is $$1-\frac27=\frac57$$
EDIT
When I woke up this morning, I realized how you were attempting to do the problem, or at least I think I do.  You want to say, for any five days of the week, compute the probability that Jess and Lindsay pick those five days, and then multiply by the number of ways to choose five days.  That will work, but you've computed the probability incorrectly.
Suppose the five days have been chosen.  Jess can choose three of these days in ${5\choose3}$ ways and he can choose three days of the week in ${7\choose3}$ ways, so the probability of success is $${{5\choose3}\over{7\choose3}}$$  Then Lindsay must choose the remaining two days, and he has ${7\choose2}$ choices, so the probability that he chooses the remaining two days is $${1\over{7\choose2}}$$  Now, we must add these probabilities up for every possible choice of five days and there are ${7\choose5}={7\choose2}$ such choices.  Altogether, we have a probability of $$
{{5\choose3}\over{7\choose3}}{1\over{7\choose2}}{7\choose2}=
{{5\choose3}\over{7\choose3}}=
{{5\cdot4\cdot3}\over{7\cdot6\cdot5}}={2\over7}$$
I think that the basic flaw in your approach is trying to do the problem too quickly.  It seems to me that you are writing down calculations without stopping to think what they mean, or why they should be correct.  This is very tempting, I know, but you should resist the temptation.  Try to get into the habit of writing down, in words, what you are doing, and why it is correct.  If you don't, you may find that when you go back and look at the calculation later, you may find that you can't understand it, even if it is correct, or that you can't figure out why you thought it was correct, if it was wrong.  This has happened to me many times.
Also, of course, if you don't do this, it is harder to communicate with others.  Look how long it's taken me to figure out the gist of your calculations.  Somebody smarter than I would have seen it it a lot sooner no doubt, and I may have been sleepy yesterday, but even so, it shouldn't have taken so long.
I hopes this helps.


text:
\section{The character variety and Goldman's symplectic structure}\label{charGs}

\subsection{The character variety}\label{charvar}

References for this section include \cite{goldmannature}, \cite{porti}, \cite{Gsl2} and \cite{dumas}.

Let $G = \PSL_2(\C)$ and $\RS$ be the set of group homomorphisms from $\pi := \pi_1(S)$ to $G$.
It has a natural structure of a complex affine algebraic set as follows. Choose a finite presentation
$\pi = \langle \gamma_1, \dots, \gamma_N ~|~ (r_i)_{i\in I} \rangle$
of $\pi$. Evaluating a representation $\rho\in\RS$ on the generators $\gamma_k$ embeds ${\cal R(S)}$ as an algebraic subset of $G^N$.
This gives $\RS$ an affine structure indeed because of the identification $\PSL_2(\C) \approx \SO_3(\C)$ (given by the adjoint representation of
$\PSL_2(\C)$ on its Lie algebra $\mathfrak{g} = \slC$). One can check that this structure is independent of the presentation.

$G$ acts algebraically on $\RS$ by conjugation. The character variety ${\cal X}(S)$ is defined as the quotient in the sense of invariant theory.
Specifically, the action of $G$ on $\RS$ induces an action on the ring of regular functions $\C[\RS]$. Denote by $\C[\RS]^G$ the ring of invariant
functions, it is finitely generated because $\RS$ is affine and $G$ is reductive.
\begin{lemma}[see e.g. \cite{porti}]
 In fact, it is generated in this case ($G=\PSL_2(\C)$) by a finite number of the complex valued functions on $\RS$ of the form
$\rho \mapsto \mathrm{tr}^2(\rho(\gamma))$.
\end{lemma}

$\XS$ is the affine set such that $\C[\XS] = \C[\RS]^G$, it is called the \emph{character variety} of $S$.
A consequence of the lemma is that the points of $\XS$ are in one-to-one correspondence with
the set of \emph{characters}, {\it i.e.} complex-valued functions of the form $\gamma \in \pi \mapsto \mathrm{tr}^2(\rho(\gamma))$.

The affine set $\XS$ splits into two irreducible components $\XS_l \cup \XS_r$, where elements of $\XS_l$
are characters of representations that lift to $\SL(2,\C)$.

The set-theoretic quotient $\RS /G$ is rather complicated, but $G$ acts freely and properly on the subset $\RS^s$ of irreducible\footnote{
A representation $\rho : \pi \to \PSL_2(\C)$ is called \emph{irreducible} if it fixes no point in $\CP$.} (``stable'')
representations, so that the
quotient $\RS^s/G$ is a complex manifold.
Furthermore, an irreducible representation is determined by its character, so that $\XS^s := \RS^s/G$ embeds (as a Zariski-dense open subset) in the smooth locus
of $\XS$. Its dimension is $6g-6$. Let us mention that more generally, $\XS$ is in bijection with the set of orbits of ``semistable'' ({\it i.e.} reductive
\footnote{A nontrivial representation $\rho : \pi \to \PSL_2(\C)$ is called \emph{reductive} if it is either irreducible of it fixes a pair of distinct points
in $\CP$.})
representations.

It is relatively easy to see that the Zariski tangent space at a point $\rho \in \RS$ is described as
the space of crossed homomorphisms $Z^1(\pi, \mathfrak{g}_{\mathrm{Ad}\circ\rho})$
 ({\it i.e.} $1$-cocycles in the
sense of group cohomology), specifically maps $u : \pi \rightarrow \slC$ such that
$u(\gamma_1 \gamma_2) = u(\gamma_1) + \mathrm{Ad}_{\rho(\gamma_1)}u(\gamma_2)$ \footnote{where of course $\mathrm{Ad} : G \to \mathrm{Aut} \mathfrak{g}$
is the adjoint representation. \label{adjointdef}}.
The subspace corresponding to the tangent space of the $G$-orbit of $\rho$ is the
space of principal crossed homomorphisms $B^1(\pi, \mathfrak{g}_{\mathrm{Ad}\circ\rho})$ ({\it i.e.} $1$-coboundaries in the
sense of group cohomology), specifically maps $u : \pi \rightarrow \slC$ such that
$u(\gamma) = \mathrm{Ad}_{\rho(\gamma)}u_0 - u_0$ for some $u_0 \in\slC$. Hence for (at least) smooth points $[\rho] \in \XS$, the tangent space
is given by $T_{[\rho]}\XS = H^1(\pi,\mathfrak{g}_{\mathrm{Ad}\circ\rho})$.

\subsection{The complex symplectic structure on the character variety}

By the general construction of \cite{goldmannature}, the character variety enjoys a complex symplectic structure defined in this situation as follows.

Recall that the Lie algebra $\mathfrak{g} = \slC$ is equipped with its complex Killing form $B$ \label{killingdef}. It is a non-degenerate complex bilinear symmetric form preserved
by $G$ under the adjoint action. Let $\tilde{B}=\frac{1}{4} B$, it is explicitly given by $\tilde{B}(u,v) = \mathrm{tr}(uv)$ where $u, v\in \slC$
are represented by trace-free $2 \times 2$ matrices.

One can compose the standard cup-product in group cohomology with $\tilde{B}$
\footnote{It would look somewhat more natural to use the actual Killing form $B$ instead of $\tilde{B} = \frac{1}{4}B$, but we choose to go
with $\tilde{B}$ because it is the convention used by most authors. Moreover, it gives a slightly simpler expression of our theorems \ref{main1},
\ref{main2} and \ref{main3}.} as ``coefficient pairing'' to get a dual pairing
\begin{equation}H^1(\pi,\mathfrak{g}_{\textrm{Ad} \circ \rho}) \times H^1(\pi,\mathfrak{g}_{\textrm{Ad} \circ \rho}) \stackrel{\cup}{\to}
H^2(\pi,\mathfrak{g}_{\textrm{Ad} \circ \rho} \otimes \mathfrak{g}_{\textrm{Ad} \circ \rho}) \stackrel{\tilde{B}}{\to} H^2(\pi,\C) \cong \C ~.\end{equation}

This pairing defines a non-degenerate complex bilinear alternate $2$-form on
the complex vector space $H^1(\pi,\mathfrak{g}_{\textrm{Ad} \circ \rho}) \approx T_{[\rho]}\XS$.
It globalizes into a non-degenerate $2$-form $\omega_G$ on $\XS^s$. By arguments of Goldman (\cite{goldmannature}) following Atiyah-Bott (\cite{AB})
this form is closed, in other words it is a complex symplectic form on the smooth quasi-affine variety $\XS^s$ \label{gsdef}
\footnote{In fact, it defines an algebraic tensor on the whole character variety, see \cite{goldmannature}.}.

\subsection{Holonomy of projective structures}\label{holonomy}

Just like any geometric structure, a complex projective structure $Z$ defines a \emph{developing map}
and a \emph{holonomy representation} (see e.g. \cite{thurston}). The developing map is a locally injective projective map
$f : \tilde{Z} \rightarrow \CP$
and it is equivariant with respect to the holonomy representation $\rho : \pi \rightarrow \PSL_2(\C)$ in the sense that
$f \circ \gamma = \rho(\gamma) \circ f$ for any
$\gamma \in \pi$.

Holonomy of complex projective structures defines a map
\begin{equation*}
\hol : \CPS \rightarrow \XS~.
\end{equation*}
It is differentiable and its differential is ``the identity map'' in the sense that
it is the canonical identification
$$d\hol : T_Z\CPS = \check{H}^1(Z,\Xi_Z) \stackrel{\sim}{\rightarrow} H^1(\pi,\mathfrak{g}_{\textrm{Ad} \circ \rho}) = T_{[\hol(Z)]}\XS~.$$
A consequence of this observation is that $\hol$ is a local biholomorphism.

The holonomy representation $\rho$ of a complex projective structure satisfies the following properties:
\begin{itemize}
 \item[$\bullet$] $\rho$ is liftable to $\SL_2(\C)$ (a lift is provided by the monodromy of the Schwarzian equation).
 The image of the holonomy map thus lies in the irreducible component $\XS_l$ of $\XS$.
 \item[$\bullet$] The action of $\Gamma := \rho(\pi)$ on hyperbolic $3$-space $\HH^3$ does not fix any point or ideal point,
 nor does it preserve any geodesic. Representations having this property are called non-elementary. They are in particular irreducible representations,
hence smooth points of the character variety as expected.
\end{itemize}
Conversely, {Gallo}-{Kapovich}-{Marden} showed that any non-elementary liftable representation is the holonomy of a complex
projective structure (\cite{gallo}).

Although the holonomy map $\hol : \CPS \rightarrow \XS$ is a local biholomorphism, it is neither injective nor a covering onto its image (\cite{hejhal}).
Nonetheless, we get a complex symplectic structure on $\CPS$ simply by pulling back that of $\XS^s$ by the holonomy map. Abusing notations, we will still
call this symplectic structure $\omega_G$. Alternatively, one could directly define $\omega_G$ on $\CPS$ in terms of the exterior product of $1$-forms with
values in some flat bundle
(recall that $T_Z \CPS = \check{H}^1(Z,\Xi_Z)$, where $\Xi_Z$ is the sheaf of projective vector fields on $Z$, see section \ref{pif}).
We will consider $\omega_G$ as the \emph{standard complex symplectic structure on $\CPS$} (notably because it does not depend on
any choice).

\subsection{Fuchsian structures and a theorem of Goldman}\label{fuchhol}

Let $\FS$ be the space of marked hyperbolic structures on $S$ (we abusively use the same notation as for the Fuchsian space). More precisely, $\FS$
is the space of complete hyperbolic metrics on $S$ quotiented by $\mathrm{Diff}^+_0(S)$.
In terms of geometric structures, $\FS$ is the
deformation space of $(\HH^2,\PSL_2(\R))$-structures on $S$ (this is a consequence of Cartan-Hadamard's theorem).
Holonomy identifies $\FS$ as the connected component of the character variety ${\cal X}(S,\PSL_2(\R))$ corresponding
to faithful and discrete representations. $\FS$ is sometimes called the Fricke space of $S$.

The uniformization theorem states that there is a unique hyperbolic metric in each conformal class of Riemannian metrics on $S$.
Since $S$ is oriented, the choice of a conformal structure on $S$ is equivalent to that of a complex structure on $S$.
The uniformization theorem thus
provides a bijective map $$u : \TS \to \FS~.$$
By definition of the Fuchsian section $\sigma_{\cal F}$, the map $u$ is precisely identified as $\sigma_{\cal F}$ if hyperbolic structures are considered
as special examples of complex projective structures. Putting it differently, the following diagram commutes:
\begin{equation}\xymatrix{
\CPS \ar[rr]^{\hol} & & {\cal X}(S,\PSL_2(\C))\\
\TS \ar[rr]^{u} \ar[u]^{\sigma_{\mathcal{F}}} & & \FS \hookrightarrow {\cal X}(S,\PSL_2(\R))~. \ar[u]^\iota
}\end{equation}
It is derived from this diagram that $\sigma_{\cal F}$ is a maximal totally real\footnote{see
section \ref{ancont} for a definition of this notion and a different argument for this fact.}
analytic embedding of $\TS$ in $\CPS$.

By Goldman's general construction in \cite{goldmannature} (described above
in the case of $G =\PSL_2(\C)$),
${\cal X}(S,\PSL_2(\R))$ is equipped with a real symplectic structure $\omega_{G,\PSL_2(\R)}$. Of course
 it is just the restriction of the symplectic structure $\omega_G = \omega_{G,\PSL_2(\C)}$ on ${\cal X}(S,\PSL_2(\R))$.
Recall that $\TS$ is also equipped with a symplectic structure, the Weil-Petersson K\"ahler form $\omega_{WP}$.
In the same paper, Goldman shows that they are the same. More precisely, this is expressed in our setting as follows:
\begin{theorem}[Goldman \cite{goldmannature}]
\begin{equation}\label{wgfsss}
 {(\sigma_{\cal F})}^* \omega_{G} = \omega_{WP}~.
\end{equation}
\end{theorem}

\subsection{A Lagrangian embedding}

Let $\hat{M}$ be a compact $3$-manifold as in section \ref{cphyp}. We will use here the same notations as in section \ref{cphyp}, let us briefly recall these.
The boundary $\partial \hat{M}$ is the disjoint
union of $N$ surfaces $S_k$ of genera at least $2$. The Teichm\"uller space of the boundary is given by
${\cal T}(\partial \hat{M}) = {\cal T}(S_1) \times \dots \times {\cal T}(S_N)$, and similarly
${\cal CP}(\partial \hat{M}) = {\cal CP}(S_1) \times \dots \times {\cal CP}(S_N)$. The forgetful projection is the holomorphic map
$p = p_1 \times \dots \times p_N : {\cal CP}(\partial \hat{M}) \to {\cal T}(\partial \hat{M})$, and
$\beta : {\cal T}(\partial \hat{M}) \to {\cal CP}(\partial \hat{M})$ is the ``simultaneous
uniformization section''.

By Goldman's construction discussed above, ${\cal CP}(\partial \hat{M})$ is equipped with a complex symplectic structure $\omega_G$, which is obtained here as
\begin{equation} \omega_G = {\pr_1}^* {\omega_G}^{(1)} + \dots + {\pr_N}^* {\omega_G}^{(N)}~, \end{equation}
where ${\omega_G}^{(k)}$ is the complex symplectic structure on ${\cal CP}(S_k)$
and  $\pr_k$ is the $k^{\textrm{th}}$ projection map ${\cal CP}(\partial \hat{M}) \to {\cal CP}(S_k)$.

There is a general argument, discovered in this setting by Steven Kerckhoff, which shows that
\begin{theorem}\label{lagemb}
$\beta : {\cal T}(\partial \hat{M}) \to {\cal CP}(\partial \hat{M})$
is a Lagrangian embedding.
\end{theorem}
Although this is
a consequence of our theorem \ref{puuff}, we briefly explain this nice argument, based on Poincar\'e duality in cohomology.
This could be done directly on the manifolds ${\cal HC}(M)$ and ${\cal CP}(\partial \hat{M})$, but we prefer
to transport the situation to character varieties, where it is simpler.

Recall that the simultaneous uniformization
section $\beta$ was defined as the composition $\beta = \psi \circ \varphi^{-1}$, where $\psi : {\cal HC}(M) \to {\cal CP}(\partial \hat{M})$ is the map
which assigns the induced projective structure on $\partial \hat{M}$ to each cocompact hyperbolic structure on the interior $M$ of $\hat{M}$, and
$\varphi = p \circ \psi : {\cal HC}(M) \to {\cal T}(\partial \hat{M})$ is a biholomorphism. By definition, the embedding $\beta$ is Lagrangian if it is isotropic
 ($\beta^*\omega_G = 0$) and $\dim {\cal CP}(\partial \hat{M}) = 2 \dim {\cal T}(\partial \hat{M})$. We already know the second
statement to be true (see section \ref{pif}). It remains to show that $\beta$ is isotropic, but since $\phi$ is a diffeomorphism, this amounts
to showing that $\psi : {\cal HC}(M) \to {\cal CP}(\partial \hat{M})$ is isotropic.

 Let us have a look at the equivalent statement on holonomy: there is a commutative
diagram $$\xymatrix{
{\cal HC}(M) \ar[d]^{\hol} \ar[rr]^\psi& & \ar[d]^{\hol} {\cal CP}(\partial \hat{M})\\
{\cal \hat{X}}(M,\PSL_2(\C)) \ar[rr]^{f} & & {\cal X}(\partial \hat{M},\PSL_2(\C))~,
}$$ where $f : {\cal X}(M,\PSL_2(\C)) \to {\cal X}(\partial \hat{M},\PSL_2(\C))$ is the map between character varieties induced by
the ``restriction'' map $\iota_* : \pi_1(\partial \hat{M}) \to \pi_1(\hat{M})$\footnote{Note that if $\partial \hat{M}$ is disconnected, we define
its fundamental group $\pi_1(\partial \hat{M})$ as the free product of the fundamental groups of its components, so that a representation $\rho : \pi_1(\partial
\hat{M}) \to \PSL_2(\C)$ is just a $N$-tuple of representations $\rho_k : \pi_1(S_k) \rightarrow \PSL_2(\C)$.}. Since the property of being isotropic is local,
it is enough to show the following proposition:

\begin{propo}\label{holag}
The map $f : {\cal X}(\hat{M},\PSL_2(\C)) \to {\cal X}(\partial \hat{M},\PSL_2(\C))$ is isotropic.
\end{propo}
\begin{proof}
Let $[\rho] \in {\cal X}(\hat{M},\PSL_2(\C))$. The map
$$df : T_{[\rho]} {\cal X}(\hat{M},\PSL_2(\C) \to T_{[\rho \circ \iota_*]} {\cal X}(\partial \hat{M},\PSL_2(\C))$$
is the map $\alpha$ that appears in long exact sequence in cohomology of the pair $(M, \partial M)$ as follows. This exact diagram shows a piece of this
sequence written in terms of group cohomology, where vertical arrows are given by Poincar\'e duality:
\begin{small}
$$\xymatrix{
H^1(\pi_1(\hat{M}),\mathfrak{g}_{\mathrm{Ad}\circ\rho}) \ar[r]^\alpha \ar[d] & H^1(\pi_1(\partial \hat{M}),\mathfrak{g}_{\mathrm{Ad}\circ\rho}) \ar[r]^\beta \ar[d] &
H^2(\pi_1(\hat{M}),\pi_1(\partial \hat{M}); \mathfrak{g}_{\mathrm{Ad}\circ\rho}) \ar[d]\\
H^2(\pi_1(\hat{M}),\pi_1(\partial \hat{M}) \ar[r]^{\beta^*}; \mathfrak{g}_{\mathrm{Ad}\circ\rho})^* &
H^1(\pi_1(\partial \hat{M}),\mathfrak{g}_{\mathrm{Ad}\circ\rho})^* \ar[r]^{\alpha^*} &
H^1(\pi_1(\hat{M}),\mathfrak{g}_{\mathrm{Ad}\circ\rho})^*
}$$
\end{small}
Note that if $u\in H^1(\pi_1(\partial \hat{M}),\mathfrak{g}_{\mathrm{Ad}\circ\rho})$,
the Poincar\'e dual of $u$ is defined by the relation
$\langle u^*, v \rangle = \tilde{B}(u \cup v) \cap [\partial \hat{M}]$
for all $v \in H^1(\pi_1(\partial \hat{M}),\mathfrak{g}_{\mathrm{Ad}\circ\rho})$,
where $[\partial \hat{M}]$ is the fundamental class of $\partial{\hat M}$. This is precisely
saying that $\langle u^*, v \rangle = \omega_G(u,v)$. It follows that $\alpha$ is isotropic: using the commutativity and
exactness of the diagram, we can write
\begin{eqnarray*}
 \omega_G(\alpha(u),\alpha(v)) & = & \langle \alpha(u)^*,\alpha(v) \rangle\\
 & = & \langle \beta^*(u^*),\alpha(v) \rangle\\
 & = & \langle u^*,\beta \circ \alpha(v) \rangle\\
 & = & 0~.
\end{eqnarray*}
\end{proof}

\begin{remark}
Note that in the quasi-Fuchsian situation $M = S \times \R$, Theorem \ref{lagemb} is trivial, or rather its formulation in terms of
holonomy (cf. Proposition \ref{holag} above). Indeed, the map $f : {\cal X}(\hat{M},\PSL_2(\C)) \to {\cal X}(\partial \hat{M},\PSL_2(\C))$
in that case is just the diagonal
embedding of ${\cal X}(\pi,\PSL_2(\C))$\footnote{where $\pi=\pi_1(\hat{M})=\pi_1(S)$.} into
${\cal X}(\pi,\PSL_2(\C)) \times {\cal X}(\pi,\PSL_2(\C))$\footnote{Here ${\cal X}(\pi,\PSL_2(\C)) \times {\cal X}(\pi,\PSL_2(\C))$ is
equipped with with the complex symplectic structure ${\pr_1}^*\omega_G-{\pr_2}^*\omega_G$
(the minus sign is due to the opposite orientation of $\partial^+ \hat{M}$ and $\partial^- \hat{M}$). The fact that the diagonal
is Lagrangian is a particular case of the following general fact: if $(X,\omega)$ is a symplectic
manifold and $X\times X$ is equipped with the symplectic structure ${\pr_1}^*\omega-{\pr_2}^*\omega$, then the graph of a function $h : X\to X$ is a
Lagrangian submanifold of $X\times X$ if and only if $h$ is a symplectomorphim.}.
\end{remark}

config: arxiv


TITLE: What will be the negation of this statement:
QUESTION [13 upvotes]: Every street in the city has at least one house in which we can I find a person who is rich and beautiful or highly educated and kind.

Negation: 'There exists a street in the city where in every house we can find no person who is rich and beautiful or highly educated and kind.'
Is the negation correct? Please someone check...
Thank you..

REPLY [1 votes]: It's roughly the correct negation.  Your negation has a few further implications than the direct logical inverse.
The original statement:

Every street in the city has at least one house in which we can find a person who is rich and beautiful or highly educated and kind.

The obvious exact negation:

Not every street in the city has at least one house in which we can find a person who is rich and beautiful or highly educated and kind.

Your negation:

There exists a street in the city where in every house we can find no person who is rich and beautiful or highly educated and kind.

There is a possibility with the exact negation that every street in the city with houses has at least one house in which (etc.), and that the only counterexample to the original claim is a street without any houses.  Your negation precludes this possibility by implication.
If a street has no houses, it is not true to say "in every house on this street we can find no person who is rich, etc."  It is true to say, "in no house on this street we can find a person who is rich, etc."  The first implies the existence of the set "houses on this street."  The latter does not.

Modifying the exact negation by progressive changes, retaining exact meaning:

Not every street in the city has at least one house in which we can find a person who is rich and beautiful or highly educated and kind.
There exists a street in the city which does not have at least one house in which we can find a person who is rich and beautiful or highly educated and kind.
There exists a street in the city where in no house can we find a person who is rich and beautiful or highly educated and kind.

This is really as far in as you can push the negation without any alteration of meaning.  Any further and you imply the existence of sets that may or may not exist.
If we allow that, we may as well also allow "there is a" instead of "there exists a," despite the ambiguity regarding quantity (exactly one or at least one?).  So then we get the following much sloppier sort-of-negation of the original, which implies existence of sets all over the place which were not required to exist by the ACTUAL negation:

There is a street in the city where in all the houses it has, we can't find a person who is rich and beautiful or highly educated and kind.
There is a city street with houses in all of which we can't find a person who is rich and beautiful or highly educated and kind.

Now we've implied houses, let's imply people.  (There don't have to be ANY people per the original negation.)

There is a street in the city with its houses all full of people who are poor or ugly, and stupid or mean.


TITLE: Bounds for duplicate finding with limited independence
QUESTION [3 upvotes]: (This is a follow up to this previous question on math.stackexchange.com.)
Assume a process that samples uniformly at random from the range $[1,\ldots,n]$. I am interested in the time to find a duplicate given only that the sampling process is $k$-independent for $k\geq 2$. That is I would like to find the expected time and tail bounds for the time until a sample matches one of the samples taken before.
If the sampling process is fully independent then it is well known that the expected time is $\Theta(\sqrt{n})$. Further you can compute upper and lower bounds for $P(X \geq x)$ fairly straightforwardly giving you good tail bounds on the probability that you need many more than the expected value. Here $X$ is the r.v. which represents the number of samples to get a duplicate.
My question is how to analyse the problem if the sampling process is only $k$-independent.  What are upper and lower bounds for the expected time to get a duplicate and can we get good tail bounds?
The link at the top shows that for pairwise independence the mean can be greater than $n$.  Is this true for $k >2$?  For an arbitrary fixed $k$, does the $\Omega(\sqrt{n})$ lower bound we get for full independence still hold? This is clearly not true for $k=1$ (see comment below) but is it true for all $k \geq 2$?  Alternatively, does anyone know of a $k$-independent process that takes less than order $\sqrt{n}$ steps to find a duplicate on average?
EDIT 1: Added reference request tag and final sentence. Maybe someone has worked on similar problems before?
EDIT 2: Lower bound question answered in the affirmative by Douglas Zare.

REPLY [2 votes]: For $k \ge 4$, the expected time until the first duplicate is $O(\sqrt{n})$. This leaves the case $k=3$ [Edit: The case of $k=3$ is resolved below with a construction with expected first duplicate at about $n/4$].
Let $D_i$ be the number of duplicates in the first $i$ values. The expected time until the first duplicate equals $\sum_{i=0}^n P(D_i = 0)$. We can use the second moment method to estimate these probabilities well enough when $k\ge 4$.
$E(D_i) = {i \choose 2}/n$.
$E(D_i^2) = {i \choose 2}^2/n^2 + {i \choose 2}(1/n - 1/n^2)$.
$\text{Var}(D_i) = E(D_i^2) -E(D_i)^2 = {i \choose 2}(1/n - 1/n^2) \le {i \choose 2}/n$.
So, $0$ is at least $\sqrt{{i \choose 2}/n}$ standard deviations away from the mean of $D_i$. By Chebyshev's inequality, $P(D_i =0)$ is at most $n/{i \choose 2} \le \frac{2n}{(i-1)^2}$. As a probability, it is also at most $1$, and we'll use that estimate for small $i$.
$$\sum_{i=0}^n P(D_i = 0)$$
$$\le \sum_{i=0}^{\lceil \sqrt{2n}\rceil} 1 + \sum_{i=\lceil \sqrt{2n}\rceil+1}^n \frac{2n}{(i-1)^2}$$
$$ \le 3 + \sqrt{2n} + \int_{\sqrt{2n}}^n \frac {2n}{x^2}dx$$
$$ = 1 + 2\sqrt{2n}.$$
This is about a factor of $4\sqrt{2}$ off of the lower bound in the comments.

To solve the $k=3$ case, we'll construct some processes which are not $3$-independent, then take a mixture which is $3$-independent and which has an expected first duplicate of about $n/4$.
For simplicity, we'll ignore times beyond $n$. Any random prefix on the first $n$ can be extended by appending an independent uniform sequence, and the choice of extension has no effect on the expected first duplicate.
Consider random functions $f$ which are symmetric both on the domain $\lbrace 1,...,n \rbrace$ and range $\lbrace 1,...,n \rbrace$. Such a function corresponds to a $3$-independent process if and only if $P(f(1) = f(2) = f(3)) = 1/n^2$ and $P(f(1)=f(2)\ne f(3))=(n-1)/n^2.$
Let $f_0$ denote random bijections between the domain and range. $P(f_0(1) = f_0(2) = f_0(3))=0.$ $P(f_0(1)=f_0(2)\ne f_0(3))=0.$
Let $f_1$ denote random constant maps. $P(f_1(1) = f_1(2) = f_1(3))=1.$ $P(f_1(1)=f_1(2)\ne f_1(3))=0.$
Suppose $n = 9m$. Choose a random set partition of $\lbrace 1,...,n \rbrace$ into $3m$ pairs and $m$ triplets. Choose $4m$ distinct values for the parts, and let $f_2$ take these values on the parts. $P(f_2(1) = f_2(2) = f_2(3)) = m/{n \choose 3} \approx \frac 2{3n^2} \lt 1/n^2.$ $P(f_2(1)=f_2(2)\ne f_2(3)) = \frac{2}{3} \frac{1}{n}+ \frac{1}{3} \frac{2}{n-1} \frac {n-3}{n-2}  = \frac{4(n^2-3n+1)}{3 n(n^2-3n+2)}\approx \frac{4}{3n} \gt (n-1)/n^2.$ The first term, $\frac{2}{3n},$ corresponds to the possibility that $1$ is part of a pair and $2$ is the second point in the pair. The second term corresponds to the possibility that $1$ and $2$ are part of a triplet and $3$ is not the third point of the triplet.
$(1/n^2, (n-1)/n^2)$ is in the convex hull of $(0,0)$, $(1,0)$, and $(m/{n \choose 3},\frac{2}{3} \frac{1}{n}+ \frac{1}{3} \frac{2}{n-1} \frac {n-3}{n-2})$. So, some mixture of $f_0$, $f_1$, and $f_2$ is $3$-independent. Specifically,
$$\frac{n^4-13n^2+16n-4}{4n^4-12n^3+4n}f_0 + \frac{n^2-5n+2}{2n^4-6n^3+2n^2}f_1 + \frac{3n^3 - 12n^2+15n-6}{4n^3-12n^2+4n}f_2 $$
is $3$-independent. This mixture gives a weight of $1/4 + o(1)$ to $f_0$, which has expected first duplicate time of $n+1$, so the expected first duplicate of the mixture is at least $(1/4+o(1))n$.
We can use slightly different set partitions when $n$ is not a multiple of $9$. The $2/3:1/3$ split into pairs and triplets was not optimized, so perhaps some other ratio would give a better proportion of $f_0$ in the mixture, hence a better coefficient of $n$ in the expected time of the first duplicate.


TITLE: What is the name of this solid?
QUESTION [2 upvotes]: You have a sphere.
Take it and drill a hole along a diameter. You have a torus.
Then rotate the sphere 90 degrees and drill along another diameter. There are now two perpendicular, intersecting cylindrical holes in the sphere. You now have a ___.

REPLY [1 votes]: A $\chi = 1 $ "torus" may be. With a single hole what you are left with is homeomorphic to a torus. Depending on whether there is drilled one,two.. holes we have a doubly, triply connected surfaces/solids as 2-torus/ 3 -torus etc. They are topologically characterized by Euler characteristic $ V+F-E-2 =\chi$ that is respectively as solid, Clifford torus,.. $1,0,-1,-2$ depending on the number of drillings done on the sphere. Also it is the genus of surface, the number of handles you add or connect to the un-drilled solid.


TITLE: Does $(x) = x$ follow from the axioms of the real numbers, or is it actually an axiom?
QUESTION [3 upvotes]: I'm working through a real analysis book. I'm still at the very beginning, and the current section is about the real number system. Specifically, the author lists 11 axioms (associativity, commutivity, identities, etc.).
However, I can't figure out how to show that $(x) = x$. Do we just assume this is true? By $(x)$, I just mean $x$ with parentheses.
The book I'm reading is Foundation of Mathematical Analysis by Richard Johnsonbaugh. I'm in chapter 3, The Real Number System.
This book does not go through the set-theoretic construction of the real number system, but rather it simply lists axioms. The axioms are as follows:
A1: There is a binary operation called addition and denoted + such that if $x$ and $y$ are real numbers, $x+y$ is a real number.
A2: Addition is associative. $$(x+y) + z = x + (y+z)$$
A3: Addition is commutative. $$x+y = y + x$$
A4: An additive identity exists. There exists a real number denoted 0 which satisfies $$x+0 = x = 0+x.$$
I could list the rest of the axioms, but I'm not sure it would help with this discussion.

REPLY [2 votes]: $(x) = x$ is purely a point of mathematical grammar, and has nothing to do with real numbers or arithmetic. The parentheses don't actually mean anything: they just enforce grouping. e.g. because of the parentheses, one cannot read $(1+2)\times 3$ as the sum of $1$ and $2 \times 3$.
Actually, depending on the fine details of grammar, $(x)$ might even be grammatically incorrect; e.g. one form of the grammar for fully parenthesized arithmetic expressions only puts parentheses around the result of a binary operation, so $(x)$ doesn't make sense because there is no operation appearing in $x$.


text:
\section{Baire Space iff Open Sets are Non-Meager}
Tags: Baire Spaces, Non-Meager Spaces

\begin{theorem}
Let $T = \struct {S, \tau}$ be a [[Definition:Topological Space|topological space]].
Then $T$ is a [[Definition:Baire Space (Topology)|Baire space]] {{iff}} every [[Definition:Non-Empty Set|non-empty]] [[Definition:Open Set (Topology)|open]] set of $T$ is [[Definition:Non-Meager Space|non-meager]] in $T$.
\end{theorem}

\begin{proof}
We prove the [[Definition:Contrapositive Statement|contrapositive]]:
:$T$ is not a [[Definition:Baire Space (Topology)|Baire space]] {{iff}} there exists a [[Definition:Non-Empty Set|non-empty]] [[Definition:Open Set (Topology)|open]] set of $T$ which is [[Definition:Meager Space|meager]] in $T$.
We have by [[Definition:Baire Space (Topology)/Definition 3|definition of Baire space]]:
:$T$ is a Baire space {{iff}} the [[Definition:Interior (Topology)|interior]] of the [[Definition:Set Union|union]] of any [[Definition:Countable|countable set]] of [[Definition:Closed Set (Topology)|closed sets]] of $T$ which are [[Definition:Nowhere Dense|nowhere dense]] is [[Definition:Empty Set|empty]].
Therefore:
:$T$ is not a Baire space {{iff}} the [[Definition:Interior (Topology)|interior]] of the [[Definition:Set Union|union]] of some [[Definition:Countable|countable set]] of [[Definition:Closed Set (Topology)|closed sets]] of $T$ which are [[Definition:Nowhere Dense|nowhere dense]] is [[Definition:Non-Empty Set|non-empty]].
We have by [[Definition:Meager Space|definition of meager]]:
:$A$ is meager in $T$ {{iff}} it is a [[Definition:Countable Union|countable union]] of [[Definition:Subset|subsets]] of $S$ which are [[Definition:Nowhere Dense|nowhere dense]] in $T$.
Here $I$ denotes a [[Definition:Countable|countable]] indexing set.
=== Sufficient Condition ===
Suppose $T$ is not a [[Definition:Baire Space (Topology)|Baire space]].
Then there is a [[Definition:Countable|countable set]] of [[Definition:Closed Set (Topology)|closed sets]] of $T$ which are [[Definition:Nowhere Dense|nowhere dense]] with the [[Definition:Interior (Topology)|interior]] of its [[Definition:Set Union|union]] [[Definition:Non-Empty Set|non-empty]].
Let $\FF = \set {F_i: i \in I}$ be such a set.
Then $\paren {\bigcup \FF}^\circ$ is a [[Definition:Non-Empty Set|non-empty]] [[Definition:Open Set (Topology)|open set]].
Consider the set $\FF' = \set {F_i \cap \paren {\bigcup \FF}^\circ: i \in I}$.
From [[Intersection is Subset]]:
:$F_i \cap \paren {\bigcup \FF}^\circ \subseteq F_i$ for any $i \in I$
Since $F_i$ are [[Definition:Nowhere Dense|nowhere dense]], so is $F_i \cap \paren {\bigcup \FF}^\circ$.
We have:
{{begin-eqn}}
{{eqn | l = \bigcup \FF'
      | r = \bigcup_{i \mathop \in I} \paren {F_i \cap \paren {\bigcup \FF}^\circ}
}}
{{eqn | r = \paren {\bigcup \FF}^\circ \cap \bigcup_{i \mathop \in I} F_i
      | c = [[Intersection Distributes over Union/Family of Sets|Intersection Distributes over Union]]
}}
{{eqn | r = \paren {\bigcup \FF}^\circ \cap \bigcup \FF
}}
{{eqn | r = \paren {\bigcup \FF}^\circ
      | c = [[Set Interior is Largest Open Set]]; [[Intersection with Subset is Subset]]
}}
{{end-eqn}}
Therefore $\bigcup \FF'$ is [[Definition:Meager Space|meager]] in $T$.
Hence we have shown the existence of a [[Definition:Non-Empty Set|non-empty]] [[Definition:Open Set (Topology)|open]] set of $T$ which is [[Definition:Meager Space|meager]] in $T$.
{{qed|lemma}}
=== Necessary Condition ===
Suppose there exists a [[Definition:Non-Empty Set|non-empty]] [[Definition:Open Set (Topology)|open]] set of $T$ which is [[Definition:Meager Space|meager]] in $T$.
Let $\displaystyle A = \bigcup_{i \in I} A_i$ be such a set.
Then $A$ is a [[Definition:Non-Empty Set|non-empty]] [[Definition:Open Set (Topology)|open set]], and $A_i$ are [[Definition:Nowhere Dense|nowhere dense]] for every $i \in I$.
Thus for every $i$, $\paren {A_i^-}^\circ = \O$.
By [[Closure of Topological Closure equals Closure]]:
:$\paren {\paren {A_i^-}^-}^\circ = \paren {A_i^-}^\circ = \O$.
By [[Set is Closed iff Equals Topological Closure]], $A_i^-$ are [[Definition:Closed Set (Topology)|closed sets]] of $T$ which are [[Definition:Nowhere Dense|nowhere dense]].
We also have:
{{begin-eqn}}
{{eqn | l = A
      | r = A^\circ
      | c = [[Interior of Open Set]]
}}
{{eqn | r = \paren {\bigcup_{i \in I} A_i}^\circ
}}
{{eqn | o = \subseteq
      | r = \paren {\bigcup_{i \in I} A_i^-}^\circ
      | c = [[Set is Subset of its Topological Closure]]; [[Set Union Preserves Subsets/Families of Sets|Set Union Preserves Subsets]]; [[Interior of Subset]]
}}
{{end-eqn}}
Hence there is a [[Definition:Countable|countable set]] of [[Definition:Closed Set (Topology)|closed sets]] of $T$ which are [[Definition:Nowhere Dense|nowhere dense]] with the [[Definition:Interior (Topology)|interior]] of its [[Definition:Set Union|union]] [[Definition:Non-Empty Set|non-empty]].
Therefore $T$ is not a [[Definition:Baire Space (Topology)|Baire space]].
{{qed}}
\end{proof}

config: wiki


TITLE: Pappos Theorem and distance of points
QUESTION [2 upvotes]: Let be $CDEB$ a parallelogramm.
$F,G$ any points on the inner lines $DE$, $CB$ like in the picture.

How can I show, that $CJ$=$KE$ ?
I thought about using Pappos Theorem, which states, that $H$ and $I$ are colinear..
but how do I proceed for the distances?

REPLY [2 votes]: Let $M$ be the intersection of the diagonals $CE$, $BD$. By Pappus' theorem the points $CG \cap FD = H$, $CE \cap BD=M$, and $FE \cap BG=I$ are collinear.
We see now that $C$ is symmetric to $E$ and $J$ is symmetric to $K$ with respect to $M$. In particular $CJ=KE$.


TITLE: Simplifying the following expression algebraically
QUESTION [1 upvotes]: This is for a class on logic gates and boolean expressions, the expression I was given is the following:
$$x'y'z'+w'x'yz'+wx'yz'$$
I have done one other question like this so far and I struggled with it, so far I have only been able to do the following:
$$x'z'(y'+w'y+wy)$$
I'm not entirely sure if I'm even allowed to remove the common elements the way I did here but it was the first thing I noticed, after that I did the following:
$$x'z'(y' + y)$$
I know that $w'y+wy = y$ so I placed that there and I know that $y + y'$ is always true so the final answer I arrived at was:
$$ x'z'$$
I don't know exactly if everything I did is allowed, and I couldn't find an answer online either. Could someone confirm if I was able to do this question properly or point out to me where I messed up. Thank you very much

REPLY [1 votes]: You correctly notice you can collect $x'z'$; this leaves to simplify
$$
y'+w'y+wy=y'+y(w'+w)=y'+y1=y'+y=1
$$
so what remains is indeed $x'z'$.


TITLE: Norm inequality (supper bound)
QUESTION [1 upvotes]: Do you think this inequality is correct? I try to prove it, but I cannot. Please hep me.
Assume that $\|X\| < \|Y\|$, where $\|X\|, \|Y\|\in (0,1)$ and $\|Z\| \gg \|X\|,\|Z\| \gg \|Y||$.
prove that
$$\|X+Z\|-\|Y+Z\| \leq \|X\|-\|Y\|$$
and if $Z$ is increased, the left hand side become smaller.
I pick up some example and see that this inequality is correct but I cannot prove it.
Thank you very much.

REPLY [1 votes]: The inequality is false as stated. Let
$$ \begin{align}
X &= (0.5,0)\\
Y &= (-0.7,0)\\
Z &= (z,0), 1 \ll z
\end{align}$$
This satisfies all the conditions given. We have that
$$ \|X + Z\| - \|Y + Z\| = z + 0.5 - (z - 0.7) = 1.2 \not\leq -0.2 = \|X\| - \|Y\| $$

From the Calculus point of view, in $n$ dimensions, we can write
$$ \|X\| = \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2} $$
We have that when $\|X\| \ll \|Z\|$, we can approximate $\|X+Z\| \approx \|Z\| + X\cdot \nabla(\|Z\|)$. Now, $\nabla(\|Z\|) = \frac{Z}{\|Z\|}$ by a direct computation, so we have that
$$ \|X + Z\| - \|Y + Z\| \approx (X-Y) \cdot \frac{Z}{\|Z\|} $$
From this formulation we see that even in the cases where $X,Y$ are infinitesimal the inequality you hoped for cannot hold true. However,
the right hand side of this approximation can be controlled by Cauchy inequality to get (using that $Z / \|Z\|$ is a unit vector).
$$ (X-Y) \cdot \frac{Z}{\|Z\|} \leq \|X - Y\| $$
So perhaps what you are thinking about is the following corollary of the triangle inequality
Claim: If $X,Y,Z$ are vectors in $\mathbb{R}^n$, then
$$ \|X + Z\| - \|Y + Z\| \leq \|X - Y \| $$
Proof: We write
$$ X + Z = (X - Y) + (Y + Z) $$
so by the triangle inequality
$$ \|X + Z\| = \|(X - Y) + (Y+Z)\| \leq \|X - Y\| + \|Y + Z\| $$
rearranging we get
$$ \|X + Z\| - \|Y + Z\| \leq \|X - Y\| $$
as desired.
Remark: if we re-write the expression using $-Z$ instead of $Z$, the same claim is true in an arbitrary metric space: Let $(S,d)$ be a metric space. Let $x,y,z$ be elements of $S$. Then
$$ d(x,z) - d(y,z) \leq d(x,y) $$.


TITLE: Given a positive definite matrix $A$, how can I find a matrix $S$ such that $A=S^TS$ and $S$ has following restrictions?
QUESTION [1 upvotes]: My former question on this problem was not that popular, I was asking to prove the existence and uniqueness of a upper triangular matrix $S$ with positive entries on diagonal such that $A=S^TS$ for a positive definite Hermitian matrix. Now I am asking about an algorithm for this problem:
Task: Given a positive definite Hermitian $A$ find a upper triangular $S$ with positive entries on the diagonal such that $A=S^TS$.
My thoughts: In the first task part I proved that when I use Gram-Schmidt orthogonalization, then transform matrix is upper diagonal with positive entries on diagonal, so it seems that $S$ should be gotten using Gram-Schmidt.
Actually I can always find an arbitrary matrix $S$: since $A$ is Hermitian, I can consider it as structure matrix for scalar product, and in basis of eigenvectors of $A$, each multiplied with $|\lambda_i|^{-\frac12}$ (corresponding eigenvalue), (call this basis $C$) structure matrix is identity matrix, so $A=S^TES=S^TS$, but $S$ isn't upper diagonal with positive diagonal entries in general. So I should find a basis $B$ such that if I apply Gram-Schmidt on it, then I get $C$, and structure matrix of mentioned scalar product in basis $B$ is matrix $A$. I hope idea is clear.
Thanks in advance!

REPLY [1 votes]: This is Cholesky decomposition.


TITLE: Show a function's inverse is injective iff the function is surjective
QUESTION [0 upvotes]: Can anyone help me with this question?

Let $f:E\to F$. Consider $f^{-1}:\mathcal{P}(F)\to\mathcal{P}(E)$ as a function from $\mathcal{P}(F)$ to $\mathcal{P}(E)$. Show $f^{-1}$ is injective if and only if $f$ is surjective.

Any help would be much appreciated!
Note: I am brand new to set theory

REPLY [3 votes]: Suppose $f$ were not surjective. Then there is $b \in F$ such that $f(a) \not = b$ for all $a \in E$. That is, there is $b \in F$ such that $f^{-1}(\{ b \})$ is empty. What is another set which has empty preimage?
Suppose $f^{-1}$ were not injective. Then there are $A, B$ distinct such that $f^{-1}(A) = f^{-1}(B)$. Equivalently, $\{ x \in E \vert f(x) \in A \} = \{ x \in E \vert f(x) \in B \}$. But $A \not = B$, so $(A \cup B) \setminus (A \cap B)$ is nonempty; and anything in that set is not hit by $f$.
This demonstrates a useful principle: if you're trying to prove things like "for all…" iff "for all…", then it's often easier to prove the contrapositive both ways. That way you can work with "there exists…" iff "there exists…", which is usually easier because you have some concrete objects to work with.


TITLE: Compute a Gröbner basis for $I=\langle f_1,f_2,f_3\rangle$.
QUESTION [0 upvotes]: Using lexicographic order compute a Gröbner basis for
  $$I=\langle f_1=xy^2-xy+y,f_2=xy-z^2,f_3=x-yz^4\rangle\subset \Bbb R[x,y,z]$$

I was strictly using these notes to compute a Gröbner basis.

When the computation gets messy I used a computer software at least to know the answer, but the software gave me
$$\{z^8-z^6-2 z^4-z^2, y-z^6+2 z^4, x-z^6+z^4+z^2\}$$
as a Gröbner basis, which I wouldn't even imagine, because the elements in $I$ are not included. I was expecting the answer to be like $\langle f_1,f_2,f_3,\ldots\rangle$.

Edited: How can I compute a Gröbner basis by hand?

REPLY [2 votes]: The Gröbner basis depends on the monomial order you choose. If you use lexicographical order you do get (in M2; commented out -- is the answer):
R=QQ[x,y,z,MonomialOrder=>Lex];
I=ideal(x*y^2-x*y+y,x*y-z^2,x-y*z^4);
gens gb I -- | z8-z6-2z4-z2 y-z6+2z4 x-z6+z4+z2 |
J=ideal oo
I==J -- true

But if you use graded reverse lexicographical order (default for M2):
R=QQ[x,y,z];
I=ideal(x*y^2-x*y+y,x*y-z^2,x-y*z^4);
gens gb I -- | y2-2z2+x+y xy-z2 x2-2z2-2x+y yz2-z2+y xz2-2z2-x+y z4-z2-x+y |
J=ideal oo
I==J -- true

In either case the ideals are the same, what needs to be true for a Gröbner basis (that it is a generating set and) that the initial terms generates the initial ideal for that monomial order.
This means that your original generators could be part of the list but that the initial terms aren't needed for generating the initial ideal.


TITLE: Real Analysis Absolute values
QUESTION [0 upvotes]: Someone please help me with detailed explanation on how to solve this problem.
For all $a, b \in \Bbb R$, show that;
$$
| a - b | \geq | a | - | b |
$$

REPLY [2 votes]: Using the triangle inequality:
$$|a|=|a-b+b|\leq |a-b|+|b|$$
Thus $|a|-|b|\leq |a-b|$.
Similarly you can prove that $|b|-|a|\leq |a-b|$
So we have $\left||a|-|b|\right|\leq |a-b|$ which is the reverse triangle inequality.


TITLE: Splitting of Short Exact sequence
QUESTION [5 upvotes]: Suppose $d_1d_2=n$ and let $0 \to d_1\mathbb Z_n \overset {i} \to \mathbb Z_n \stackrel {d_2\cdot} \to d_2\mathbb Z_n\to 0$ be a short exact sequence. Show that sequence splits iff $\gcd(d_1,d_2)=1$.

Suppose s.e.s. split then $\mathbb Z_n=d_1\mathbb Z_n +d_2\mathbb Z_n$, hence $1=d_1a+d_2b$ hence $\gcd=1$. How to prove the converse?

REPLY [0 votes]: Or, alternatively to  Nitrogen's: you are looking for a section of the multiplication by $d_2$ map. Therefore you are looking for an element $x$ such that $$d_1x \equiv 0\pmod n$$ (because $d_2$ has order $d_1$) and such that $$d_2x \equiv d_2 \pmod n.$$ Dividing through, this is equivalent to solving $x \equiv 0 \pmod {d_2}$ and $x \equiv 1 \pmod {d_1}$, which is possible if $d_1$ and $d_2$ are coprime. In any event,  $x = b d_2$, where $b$ is as  above (i.e., so  your section is  $k\,d_2 \mapsto k\,x$, for $k \in \mathbb Z$).


TITLE: Can we convert a non-nonvex function x'Dy to convex
QUESTION [1 upvotes]: Consider a vector of variables $x$ and $y$ and a matrix $D$. The objective function $x^TDy$ is not convex. Can we make it convex by log transformation like in Geometric programming?
The actual optimization problem is equation 9 and the conditions are in equation 6,7 and 8 of the link https://hal.inria.fr/hal-01109774/document

REPLY [1 votes]: The logarithmic transformation is the key tool to convert geometric programming to convex. Let us write a posynomials function to optimize is given by $$f_0(x)=\sum_{n=1}^{N}{c_n{x{_n}^{a^n}}}$$ This can be converted by change of variable $y=\ln(x)$ to  $$f(y)=\ln{f_0(e^y)}=\ln(\sum_{n=1}^{N}{e^{a_n{y{_n}+b_n}}})$$ where $b_n=\ln(c_n)$
Now let us try to write $x^TDy$ in the above form. Let use try to do for a simple $2X2$ matrix. For variable $x$ and $y$ and $d_1$ $d_2$ $d_3$ and $d_4$ are element of $D$ we can explicitly write it as
$x^TDy={d_1}{x_1}{y_1}+{d_3}{x_2}{y_1}+{d_2}{x_1}{y_2}+{d_4}{x_2}{y_2}$
If we replace the variable $y_1$ and $y_2$ by $x_3$ and $x_4$ the equation is $x^TDy={d_1}{x_1}{x_3}+{d_3}{x_2}{x_3}+{d_2}{x_1}{x_4}+{d_4}{x_2}{x_4}$
and it appears naively that it is of the form $$f_0(x)=\sum_{n=1}^{N}{c_n{x{_n}^{a^n}}}$$ where some of the $a_n$ are $0$. Consider the the first of  $x^TDy$ which is ${d_1}{x_1}{x_3}$ for this term we must have $a^2=0$. But in this case we cannot write the second term of $x^TDy$ . Therefore, the bottom line is that we cannot write the $x^TDy$  in the form
$$\sum_{n=1}^{N}{c_n{x{_n}^{a^n}}}$$
This means we cannot convert a function of the form $x^TDy$  to convex by logarithimic transformation.


TITLE: Let $V_i\subset K$ be a family of valuation rings associated to field $K$. $D=\bigcap_iV_i$. Is $\mathrm{Frac}(D)=K$?
QUESTION [1 upvotes]: Let $V_i\subset K$ be a family of valuation rings (not necessarily discrete) associated to the field $K$. Set $D=\bigcap_iV_i$, where index $i$ may run through an infinite set. Is $\mathrm{Frac}(D)=K$?

For finite intersection case, the book has shown that $\mathrm{Frac}(D)=K$ as each $V_i$ is a localization of $D$ at a maximal ideal. However, consider $Z=\cap_{p}Z_p$ where index $p$ runs through all primes of $Z$. Then it seems plausible that $Frac(D)=K$ still. I have to note that $Z,Z_p$ are noetherian but there are non-noetherian valuation rings.
Ref. Nagata, Local Rings Chpt 1, Sec 11.

REPLY [3 votes]: Take the example $K=\mathbb{C}(X)$, and consider the discrete $\mathbb{C}$-valuations, which are given by the $(X-a)$-adic valuation $v_a$ for each $a\in \mathbb{C}$, and the valuation at infinity $v_\infty$ which is just minus the degree.
Then the intersection of the valuation rings associated to all $v_a$ consists of the rational fractions having no pole, which means it is $\mathbb{C}[X]$. But then the intersection with the valuation associated to $v_\infty$ is just $\mathbb{C}$ since polynomials have nonnegative degree.
So the total intersection is just $\mathbb{C}$, and obviously does not have $\mathbb{C}(X)$ as its fraction field.


TITLE: Trying to find a left adjoint
QUESTION [5 upvotes]: Let $\mathsf{Idem}$ be the category of sets that come with an idempotent endomorphism, i.e. the objects are pairs $(A,e)$ where $A$ is a set and $e:A \to A$ is an idempotent. The morphisms $f:(A,e) \to (B,d)$ are morphisms $f: A \to B$ in $\mathsf{Set}$ such that $df = fe$. Let $U\colon \mathsf{Idem} \to \mathsf{Set}$ be the forgetful functor.
I would like to find a left adjoint $F$ for this functor. I tried the functor $F$ where $F (A) = (A , 1_A)$ on objects, and $F( f\colon A \to B ) = f: (A, 1_A) \to (B, 1_B)$, on morphisms, but I can see no isomorphism $$\mathsf{Idem} ((A,1_A), (B,e)) \cong \mathsf{Set}(A,B).$$ I initially thought to send a map $f\colon (A,1_A) \to (B,e)$ to $ef\colon A \to B$, and a map $g\colon A\to B$ to $g\colon (A, 1_A) \to (B, 1_B)$ but this doesn't seem to be right.
Does anyone have any advice about how to find such a left adjoint? I am not sure how to spot one. It seems that the functor has to incorporate some information about all the idempotents because we need $$\mathsf{Idem} \left( FA, (B,e) \right) \cong \mathsf{Idem} \left( FA, (B,e') \right) \cong \mathsf{Set}(A,B),$$
if $e, e'$ are two different idempotents. Any help would be appreciated.

REPLY [6 votes]: Let $F(A)=A\times\{0,1\}$, with $p:F(A)\to F(A)$ given by $p((x,t))=(x,0)$ (for any $x\in A$, $t\in\{0,1\}$). If $B$ is a set with an idempotent map $e:B\to B$ then any map $g:A\to B$ gives us $g':F(A)\to B$, defined by $g'(x,1)=g(x)$, $g'(x,0)=e(g(x))$, which makes $F$ left adjoint to $U$.


TITLE: Let $L=\lim_{x\to 0} \frac{ a-\sqrt {a^2-x^2} -\frac{x^2}{2}}{x^4}$, $a>0$. If $L$ is finite, find $a$ and $L$
QUESTION [3 upvotes]: I need a hint to start this question, because I have no idea how to do it. It’s a $\frac 00$ form, so L’Hospital can be applied, but that would be extremely tedious. Expansion can’t be used because there is no function to use it for. How do I start it?

REPLY [2 votes]: Hint: you rewrite your limit as follows
$$L=a {1-\left(1-{x^2\over a^2}\right)^{1\over 2}-{x^2\over 2}\over x^4}$$
and you expand using
$$\begin{align}
(1-x)^\alpha=1-&\alpha x\\
+&{\alpha(\alpha-1)\over 2}x^2+o(x^2)
\end{align}$$
and you replace x in the expansion by $x^2/a^2$


TITLE: Convergence in a compact subset of $\mathbb{R}$
QUESTION [0 upvotes]: My professor asked me to prove or disprove the following claim:
Let $C \subset \mathbb{R}$ be a compact set. Let $x_n\in C$, be a sequence such that
$$\lim_{n \to \infty} |x_{n+1} - x_n| = 0. \quad (1)$$
Then $x_n \to x$ for some $x \in C$.
My analysis:
The existence of a limit point is assured by the property of compactness (every sequence has a limit point). We worked on disproving the claim. To do this, we assumed that the sequence had 2 limit points and there were 2 subsequences that were converging to those points. However we had difficulty disproving $(1)$.
On the other hand, while trying to prove it, assume a subsequence $x_{n_k} \to x$. Then
$$|x_n - x| \leq |x_n - x_{n_k}| + |x_{n_k} - x|$$
The second term goes to $0$ as $k$ becomes large. For now assume $k$ large enough so that second term is $< \varepsilon/2$. Let $n>n_k$. But handling the first term is quite hard. Triangle inequality yields
$$|x_n - x_{n_k}| \leq \sum_{l=n_k}^{n-1}|x_{l+1}-x_l|\leq (n-n_k)\varepsilon$$
However it seems pointless to take $n$ or $k$ large at this step.
We tried several counterexample attempts but none successful. Could someone kindly offer a hint as to proceed? We would appreciate it.
Update:
Thanks to von Eitzen.
By mean value theorem,
$$|\sin(\sqrt{n+1}) - \sin(\sqrt{n})|= \frac{|\cos(\sqrt{\theta})|}{2\sqrt{\theta}}\leq\frac{1}{2\sqrt{n}}$$
where $n\leq \theta \leq n+1$. So the sequence $\sin (\sqrt{n})$ is valid but it does not converge. Thanks.

REPLY [0 votes]: $\lim_{+\infty}|x_{n+1}-x_n|=0$ doesn't mean $(x_n) $ is Cauchy.
it will be true if
$$|x_{n+1}-x_n|\le K|x_n-x_{n-1}|$$ with $K\in (0,1) $.


TITLE: Computing the Expectation of the Square of a Random Variable: $ \text{E}[X^{2}] $.
QUESTION [44 upvotes]: What is the rule for computing $ \text{E}[X^{2}] $, where $ \text{E} $ is the expectation operator and $ X $ is a random variable?
Let $ S $ be a sample space, and let $ p(x) $ denote the probability mass function of $ X $.
Is
$$
\text{E}[X^{2}] = \sum_{x \in S} x^{2} \cdot p(x),
$$
or do I also need to square the $ x $ appearing in $ p(x) $?

REPLY [34 votes]: In general, if $ (\Omega,\Sigma,P) $ is a probability space and $ X: (\Omega,\Sigma) \to (\mathbb{R},\mathcal{B}(\mathbb{R})) $ is a real-valued random variable, then
$$
\text{E}[X^{2}] = \int_{\Omega} X^{2} ~ d{P}.
$$
Although this formula works for all cases, it is rarely used, especially when $ X $ is known to have certain nice properties.
Examples:

If $ X $ is a discrete random variable (i.e., its cumulative distribution function (cdf) is a step-function) and $ p $ is its probability mass function (pmf), then we can use the formula
$$
\text{E}[X^{2}] = \sum_{x \in \text{Range}(X)} x^{2} \cdot p(x).
$$
If $ X $ is an absolutely continuous random variable (i.e., its cdf is an absolutely continuous function), then it possesses a probability density function (pdf) $ f $. We thus have the formula
$$
\text{E}[X^{2}] = \int_{\mathbb{R}} x^{2} f(x) ~ d{\mu(x)},
$$
where $ \mu $ is the standard Borel measure on $ \mathbb{R} $. Of course, if $ f $ is continuous, then we can simply compute the improper Riemann integral
$$
\text{E}[X^{2}] = \int_{- \infty}^{\infty} x^{2} f(x) ~ d{x}.
$$


text:
This paper gives the first logarithmic regret bounds for $Q$-learning in both finite-horizon and discounted tabular MDPs. Below we list some future directions that we believe are worth exploring.

\paragraph{$H$ dependence}
The dependency on $H$ in our regret bound for episodic RL is $H^6$, which we believe is suboptimal.
As discussed in \cite{max2019nonasymptotic}, improving the $H$ dependence is often a challenging task.
Recently, \citet{zhang2020optimal} showed a model-free algorithm can achieve near-optimal regret in the worst case using the idea of reference value function.
It would be interesting to apply this idea to improve the $H$ dependence in our logarithmic regret bound.

\paragraph{Function Approximation}
Lastly, we note that recently researchers found the sub-optimality gap assumption is crucial for dealing with large state-space RL problems where function approximation is needed.
\citet{du2019q} presented an algorithm that enjoys polynomial sample complexity if there is a sub-optimality gap and the environment satisfies a low-variance assumption.
\citet{du2019good,du2020agnostic} further showed this assumption is necessary in certain settings.
There is another line of works putting certain low-rank assumptions on MDPs~\citep{krishnamurthy2016pac,jiang2017contextual,dann2018oracle,du2019provably,sun2018model,misra2019kinematic}.
It would be interesting to extend our analysis to these settings and obtain logarithmic regret bounds.


TITLE: For which $p$ and $q$ polynomials $x^q-1$ and $(x+1)^q-1$ are coprime in $F_p[x]$?
QUESTION [3 upvotes]: It easy to prove that polynomials $x^q-1$ and $(x+1)^q-1$ are coprime in $\mathbb{Q}[x]$ if $(q,6)=1$, since they don't have a common zero in $\mathbb{C}$, this can be seen geometrically.
My question is to check for which $p,q$ those polynomials are coprime in $F_p[x]$ for prime $p$?
For small values of $p$ and $q$ it is not hard to check this, for example if $p=29$ $q=7$ the polynomials do not have common zeroes and it is not hard to conclude from this that the polynomials are coprime in $F_p[x]$. But for general $p,q$ it is not easy to check if there is a common root.
I would appreciate if someone could help me with this problem, or suggest some related results, literature.

REPLY [1 votes]: When $2^q \equiv 1\  (\operatorname{mod}\ p)$, both polynomials have a root $x=1$.
Also, when $q=2$, we can check that there is a common factor only when $p=3$.  When $q=3$, there is a common factor only when $p=2$.
Putting those cases aside, consider when the cyclotomic polynomial $\Phi_q$ is irreducible modulo $p$.  This occurs when $p$ is a primitive root $(\operatorname{mod}\ q)$.  If $\Phi_q \mid ((x+1)^q-1) $, then $\Phi_q \mid ((x+1)^q-1 - (x^q-1)) = (qx^{q-1}+\cdots + qx+1)$.  This can only happen if ${q\choose k} \equiv q \equiv 1 \ (\operatorname{mod}\ p)$ for all $1\leq k \leq q-1$.
If $p=2$, then $q$ must be a Mersenne prime, which cannot happen for $q>3$ (because we assumed that $2$ is a primitive root).  If $p$ is odd, then, since $q>2$, we have ${q\choose 2} \equiv q\ (\operatorname{mod}\ p)$ gives us $q\equiv 3\ (\operatorname{mod}\ p)$, contradiction.
This is not a complete solution, because $\Phi_q$ may be reducible.  But it gives us a few things to work with:
Common Factor When:

$2^q \equiv 1\  (\operatorname{mod}\ p)$
$p=2$, $q=3$
$p=3$, $q=2$

No Common Factor When:

$p\neq 3$, $q=2$
$p\neq 2$, $q=3$
$p$ is a primitive root modulo $q$, $q\geq 5$