TITLE: How can I prove this equation is solvable?
QUESTION [2 upvotes]: Given any integers $a, b, c$ and any prime $p$ not a divisor of $ab$,
show that $ax^2+by^2=c  \mod p$ is solvable...
I think this is combinatorial number theory.. but i don't know what to do..

REPLY [1 votes]: We have the equation $y^2=f(x)$ over the field $\mathbb{F}_p$, for a quadratic polynomial $f$, since $ab\neq 0$ in $\mathbb{F}_p$. Assume first that $p>2$. Over  $\mathbb{F}_p$ the quadratic polynomial $f$ attaines $(p+1)/2$ different values. Since there are exactly $(p-1)/2$ non-squares in $\mathbb{F}_p$, at least one value of $f$ must be a square, say $f(r)=s^2$. But then $(r,s)$ is a solution. Now assume that $p=2$. Plugging in $x=0$, $x=1$ etc. it is easy to see that there is a solution, too (the only conic without a "solution", i.e., an affine point over $\mathbb{F}_2$ is $y^2=x^2+x+y+1$).


text:
\section{Primitive of One plus x Squared over One plus Fourth Power of x}
Tags: Primitives involving Reciprocals

\begin{theorem}
:$\displaystyle \int \frac {x^2 + 1} {x^4 + 1} \rd x = \frac 1 {\sqrt 2} \map \arctan {\frac 1 {\sqrt 2} \paren {x - \frac 1 x} } + C$
\end{theorem}

\begin{proof}
We have:
{{begin-eqn}}
{{eqn	| l = \int \frac {x^2 + 1} {x^4 + 1} \rd x
	| r = \int \frac {1 + \frac 1 {x^2} } {x^2 + \frac 1 {x^2} } \rd x
}}
{{eqn	| r = \int \frac {1 + \frac 1 {x^2} } {\paren {x - \frac 1 x}^2 + 2} \rd x
	| c = [[Completing the Square]]
}}
{{end-eqn}}
Note that, by [[Derivative of Power]]:
:$\dfrac \d {\d x} \paren {x - \dfrac 1 x} = 1 + \dfrac 1 {x^2}$
So, we have:
{{begin-eqn}}
{{eqn	| r = \int \frac 1 {u^2 + 2} \rd u
	| c = [[Integration by Substitution|substituting]] $u = x - \dfrac 1 x$
}}
{{eqn	| r = \frac 1 {\sqrt 2} \map \arctan {\frac 1 {\sqrt 2} u} + C
	| c = [[Primitive of Reciprocal of x squared plus a squared/Arctangent Form|Primitive of $\dfrac 1 {x^2 + a^2}$]]
}}
{{eqn	| r = \frac 1 {\sqrt 2} \map \arctan {\frac 1 {\sqrt 2} \paren {x - \frac 1 x} } + C
}}
{{end-eqn}}
{{qed}}
[[Category:Primitives involving Reciprocals]]
3qaf3meifuscsjq7r1xd4isj2pp0y51
\end{proof}

config: wiki


TITLE: What is dimension of annihilator of general subset of vector space?
QUESTION [2 upvotes]: Definitions:
Let $V$ be a vector space over $\mathbf{F}$ and $U$ a subset of $V$.
The annihilator of $U$, denoted $U^0$ is $$U^0=\{\varphi:V\rightarrow \mathbf{F} \ \ | \ \varphi|_U = 0 \}.$$
Motivation:
In general, we know that the annihilator $U^0$ is a subspace of $V$.
When $U$ is a subspace of $V$, we also know that
$$\text{dim } U^0 = \text{dim } V - \text{dim } U.$$
I'm trying to gain an intuition/ understanding of the annihilator of a general subset.  That is why I am asking this question.
Question:
What is the dimension of $U^0$ when $U$ is not a subspace?
As a more specific example, what is the dimension of the annihilator of the unit sphere $\mathbf{S} \subset \mathbf{R}^3$ in 3-space?
Idea:
Maybe it should be related to the co-dimension of the smallest subspace of $V$ containing $U$.  I know this is easy to determine, and it seems like a linear functional that annihilates one of this subspace should annihilate $U$.

REPLY [0 votes]: By linearity, if a linear map $L$ vanishes on a vector $v$ (that is, $L(v)=0$) then it has to vanish on the whole line $\Bbb R v$ (called the line "spanned by $v$").
Therefore $U^0=(\operatorname{Span}U)^0$ where $\operatorname{Span}U$ is the smallest linear subspace that contains $U$. From then on you can apply your formula, since $\operatorname{Span}U$ is a linear subspace.
So all you have to do is understand what the subspace spanned by the sphere is.


TITLE: How to show implication for equivalent equations?
QUESTION [2 upvotes]: What does it mean for one event  to cause another event  — for example, smoking () to cause cancer ()? There is a long history in philosophy, statistics, and the sciences of trying to clearly analyze the concept of a cause. One tradition says that causes raise the probability of their effects; we may write this symbolically is
(|)>().(1)
Another way to formulate a probabilistic theory of causation is to say that
(|)>(|^).(2)
I know that equation (1) implies that (|)>().
Show that equation (1) implies equation (2)

REPLY [1 votes]: By the law of total probability, we can relate $P(E)$ to $P(E\mid C)$ and $P(E\mid C^c)$
$$P(E) = P(E\mid C)P(C) + P(E\mid C^c)(1-P(C)) = P(C)[P(E\mid C) - P(E\mid C^c)] + P(E\mid C^c) $$
Using our assumption $P(E\mid C) > P(E)$ we get:
$$P(C)[P(E\mid C) - P(E\mid C^c)] + P(E\mid C^c) = P(E) < P(E\mid C)$$
Collecting conditional probabilities on either side of the inequality we get
$$  P(E\mid C^c)- P(C)P(E\mid C^c)  < P(E\mid C) - P(C)P(E\mid C) $$
Finally, we factor out $1-P(C)$ on both sides:
$$ (1-P(C))P(E\mid C^c) < (1-P(C))P(E\mid C)$$
Assuming $P(C) < 1$ ($P(C)=1$ would make it omnipresent and not a typical "cause"), we can divide by the strictly positive value $1-P(C)$ to get our implication:
$$P(C) < 1 \text{ and } (1-P(C))P(E\mid C^c) < (1-P(C))P(E\mid C) \implies P(E\mid C^c) < P(E\mid C)\;\; \square$$


TITLE: Inclusion $O(2n)/U(n)\to GL(2n,\mathbb{R})/GL(n,\mathbb{C}) $
QUESTION [4 upvotes]: How to show, that an inclusion of homogenious spaces $$O(2n)/U(n)\to GL(2n,\mathbb{R})/GL(n,\mathbb{C}) $$ is homotopy equivalence? The big space is the space of complex structures on $\mathbb{R}^{2n}$. This is an exercise in the book of McDuff and Salamon on symplectic topology, and they recommend to use polar decomposition, but it gives a deformational retraction $GL(2n,\mathbb{R}) \to O(2n)$, but does not give a map of homogenious spaces, since it is not $GL(n,\mathbb{C})$-equivariant.

REPLY [3 votes]: You could probably write down an explicit homotopy inverse, but here is a quick way of seeing this:
We have fiber bundles $O(2n)/U(n) \rightarrow BU(n) \rightarrow BO(2n)$ and $GL_{2n}(\mathbb{R})/GL_{n}(\mathbb{C}) \rightarrow BGL_{n}\mathbb{C} \rightarrow BGL_{2n}\mathbb{R}$ and a map from the first to the second which induces homotopy equivalences on the base and total space, whence the fibers are homotopy equivalent.


TITLE: Find all subgroups of GL(3,7) with a Sylow 3-subgroup of order 27
QUESTION [1 upvotes]: I want to use GAP to study all subgroups of GL(3,7) with a Sylow 3-subgroup of order 27. How can I do it? Thanks.

REPLY [2 votes]: Just so that the question is answered, this group is small enough that one can easily compute all subgroups of the group $G$, and select those of a suitable order. This is easiest done in an isomorphic permutation group.
gap> G:=GL(3,7);;
gap> iso:=IsomorphismPermGroup(G);;p:=Image(iso);
<permutation group of size 33784128 with 2 generators>
gap> u:=List(ConjugacyClassesSubgroups(p),Representative);;
gap> u:=Filtered(u,x->Size(x) mod 27=0 and Size(x) mod 81<>0);;
gap> Length(u);
163
gap> u:=List(u,x->PreImage(iso,x));;

finds 163 classes of subgroups.  If the group gets bigger and calculating all subgroups becomes infeasible, one could try to compute the potential Sylow subgroups first (from the subgroups of a Sylow subgroup of $G$), and use IntermediateSubgroups to find all subgroups above, and finally fuse under the conjugaction action:
gap> s:=SylowSubgroup(p,3);
<permutation group of size 81 with 4 generators>
gap> m:=MaximalSubgroupClassReps(s);
[ <permutation group with 3 generators>, <permutation group with 3 generators>
    , <permutation group with 3 generators>,
  <permutation group with 3 generators> ]

Fuse under full group:
gap> m:=List(SubgroupsOrbitsAndNormalizers(p,m,false),x->x.representative);
[ <permutation group of size 27 with 3 generators>,
  <permutation group of size 27 with 3 generators>,
  <permutation group of size 27 with 3 generators> ]
gap> int:=List(m,x->IntermediateSubgroups(p,x).subgroups);;
gap> int:=Unique(Concatenation(int));;
gap> int:=Filtered(int,x->Size(x) mod 81<>0);;

Again eliminate conjugates.
gap> int:=List(SubgroupsOrbitsAndNormalizers(p,int,false),x->x.representative);;
gap> Length(int)+Length(m);
163


text:
\section{Connections with Optimal Estimation}\label{sec:optimality}

In this last section, we study the optimal estimator for the vector source $\mathcal{X}(\Omega,F)$ characterized by a zero-mean Gaussian distribution $F$, and show that certain limiting versions of this estimator correspond to the nearest subspace and thresholding estimators studied in Sections \ref{sec:sufML} and \ref{sec:sufTH}.

Our first result describes the optimal estimator associated with our distortion metric \eqref{eq:distortion}. The proof, which  follows directly from the Bayesian formulation of the problem, is left as an exercise.

\begin{prop}\label{prop:optGaussianS}
Let $\bX \in \mathbb{R}^n$ be a random vector whose sparsity pattern $\bS$ is distributed uniformly over $\mathcal{S}^n_k$ and whose nonzero elements $\{X_i:  i \in \bs\}$ are standard Gaussian random variables, and let $$\bY = \sqrt{\gamma} \cdot A \bX + \sqrt{1-\gamma} \cdot \bW$$ for some $\gamma \in (0,1)$ where $A \in \mathbb{R}^{m \times n}$ is a known sampling matrix and $\bW$ is a standard Gaussian random vector. For any distortion $\alpha \in [0,1]$, the sparsity pattern estimate $\hat{\bS}$ that minimizes the error probability $\Pr\{d(\bS,\hat{\bS}) > \alpha\}$ corresponds to the estimator
\begin{align}\label{eq:sopt}
\hat{\bs}_{\gamma,\alpha}^\text{\normalfont OPT}(\by,A,k) & \in \arg \max_{\bs \in \mathcal{S}^n_k }  \sum_{\bs' \in B_\alpha(\bs)} \exp\left\{\psi(\bs') \right\}
\end{align}
where $B_\alpha(\bs) = \{ \bs' \in \mathcal{S}^n_k : d(\bs,\bs') \le \alpha\}$ and
\begin{align*}
\psi(\bs)= -{\textstyle \frac{1}{2}} \left[  \| \Sigma_{\bs}^{-1/2} \by \|^2+ \log  \left| \Sigma_{\bs} \right| \right]
\end{align*}
with $\Sigma_{\bs} = \gamma A_{\bs} A_{\bs}^T + (1-\gamma) I_m$.
\end{prop}

Unlike the nearest subspace and thresholding estimators, the optimal Gaussian estimator \eqref{eq:sopt} depends on the SNR parameter $\gamma$ as well as the distortion bound $\alpha$. One consequence of this dependence is that the optimal estimate is not invariant to scalings of the samples $\by$. Another consequence is that it is not possible in general for a single sparsity pattern estimate $\hat{\bs}$ to be uniformly optimal for all distortions $\alpha \in [0,1)$.

To determine whether or not the optimal Gaussian estimator is significantly better than estimators that do not depend on the parameters $\gamma$ or $\alpha$, it is useful to consider the bounds on the operational sampling rate distortion functions illustrated in Figures~\ref{fig:f2} and \ref{fig:f3}. Since the lower bounds in these figures apply universally to any estimator, including the optimal Gaussian estimator, the relative tightness of the upper and lower bounds shows that near-optimal performance can be attained using the nearest subspace estimator in the high SNR setting and the thresholding estimator in the low SNR setting.

One explanation for this behavior is provided by the following non-asymptotic result which shows that the optimal Gaussian estimator converges pointwise to the nearest subspace estimator as $\gamma \rw 1$ and to the thresholding estimator as $\gamma \rw 0$. The proof of this result is rather long and and can be found in \cite{RG_asilomar09}.

\begin{theorem}\label{thm:optimality}
Let $\by \in \mathbb{R}^m,A \in \mathbb{R}^{m \times n}$ and $k \in \{1,2,\cdots,n\}$ be fixed inputs. Let $\alpha \in [0,1)$ be a fixed distortion.
\begin{enumerate}
\item
If the nearest subspace estimator is unique, then
\begin{align} \label{eq:highSNR}
\lim_{\gamma \rw 1} \hat{\bs}_{\gamma,\alpha}^\text{\normalfont OPT}( \by,A,k) = \hat{\bs}^\text{\normalfont NS}(\by,A,k).
\end{align}
\item
If the thresholding estimator is unique and the columns of $A$ are equal magnitude, then
\begin{align}\label{eq:lowSNR}
\lim_{\gamma \rw 0} \hat{\bs}_{\gamma,\alpha}^\text{\normalfont OPT}( \by,A,k)  = \hat{\bs}^\text{\normalfont TH}(\by,A,k).
\end{align}
\end{enumerate}
\end{theorem}

We first address the high SNR convergence \eqref{eq:highSNR} shown in Theorem \ref{thm:optimality}.
For the special case of exact recovery ($\alpha = 0$), this result is not particularly surprising, in part because the nearest subspace estimator corresponds to the maximum likelihood estimate of the vector $\bx$. What is less obvious, and in fact significantly more difficult to prove, is that this convergence occurs universally for all distortion bounds $\alpha$. This result is interesting because it explains why the nearest subspace algorithm performs so well in the high SNR setting for a large range of distortions. Nevertheless, it is important to keep in mind that the rate at which the probability of error tends to zero still depends on the distortion bound $\alpha$ (see for instance, the example given in \cite[Proposition 2]{RG_asilomar09}).

Next, we address the low SNR convergence \eqref{eq:lowSNR} shown in Theorem \ref{thm:optimality}. In this case, the log likelihood function $\exp\{ \psi(\bs)\}$ becomes proportional to $\|\bA_{\bs}\by\|^2$ as $\gamma \rw 0$. Using the fact that $\|\bA_{\bs}\by\|^2$ can be expressed as a sum over terms indexed by the indices in $\bs$ shows that the convergence occurs uniformly for all $\alpha$. What is particularly interesting about this result is that it shows that near-optimal estimation in the low SNR setting can be achieved using a computationally efficient estimator.

config: arxiv


TITLE: Radiative Cooling of metal object
QUESTION [2 upvotes]: We have this experiment where a metal bar is heated and then we have to make a model for the cooling that occurs. We get numbers for how long it takes the metal bar to cool from 200 to 100 degrees Celsius, and we have to calculate how long it takes for the object to cool to 50 degrees. Now, I want to calculate what the cooling would be like if it was only radiative. I know that $T(t)=T_0+(T_s−T_0)e^{−kt}$ is the formula for cooling by convection, so I'm wondering what the equivalent of that is for radiative cooling. In other words, what is the formula for radiative cooling?

REPLY [1 votes]: If you assume that the object radiates as a blackbody, then the Stefan-Boltzmann Law tells you that the power radiated by the object will be
$P = A \sigma T^4$
where $A$ is the surface area, $\sigma$ is the Stefan-Boltzmann constant, and $T$ is the temperature.  If your object is not a blackbody, you can parameterize the above equation with an additional constant, $\epsilon$, called the emissivity.
From this you should be able to figure out the temperature as a function of time by knowing that the thermal energy is proportional to temperature and that the power is equal to the time derivative of energy.

REPLY [0 votes]: The answer lies in your previous question.
Use the heat loss function for radiative cooling and plug it into the differential equation I set up for you in the answer. Then integrate.


TITLE: Why is the Hilbert curve called like that?
QUESTION [1 upvotes]: Everywhere the function $H\colon\mathcal{I}\to Q=[0,1]\times[0,1]$ is called the Hilbert curve. Is this a historical thing because normally one would call $H\colon\mathcal{I}\to Q$ maybe the Hilbert path and $H(\mathcal{I})$ the Hilbert curve.
Right now I am writing my bachelor thesis and I am unsure wether I should explain the term "Hilbert curve" as the function itself and not the image which would be just $[0,1]\times[0,1]$.

REPLY [4 votes]: In some contexts people are careful to distinguish between a function and its graph, while in others they aren't.  Moreover, even in the former circumstance, which of the two is known as the "curve" also varies according to context.  In topology a "curve" is typically a function $\gamma : I \to X$, whereas in geometry that function would be called a "parameterization" and its image would typically be called a curve.
The upshot is that you can typically count on definitions to be consistent within a particular paper or book, but not across mathematics in general.  This may not be an ideal state of affairs, but it's what we have to work with.
What this means for your talk is that you can call the two whatever you prefer but you should take care to explain the convention you're using if it's important to the talk.


TITLE: Looking to calculate the diameter of a graph of $2^{2016}$ binary strings.
QUESTION [3 upvotes]: Compute the diameter of the graph G with $V (G) = \{0, 1\}^{2016}$ in which
two binary strings are connected if and only if they coincide in at most
one coordinate.
What I know right now: each vertex is connected to 2017 others and there are $2^{2016}$ total vertices.

REPLY [2 votes]: For each string $A$ and $k\in\{1,2,3\dots 2016\}$ we define $A_k$ as the string that coincides with $A$ in position $k$ only and $A_0$ as the string that coincides in zero positions. Therefore a path from string $A$ can  be described uniquely by a list of integers between $0$ and $2016$.
Given two strings $A$ and $B$, let $ \{a_1,a_2\dots a_n\}$ be the set of positions at which they differ if $A$ and $B$ differ at $1008$ or less positions and $\{a_1,a_2\dots a_n\}$ be the set of positions at which $A$ and $B$ are equal if they are equal at $1008$ or less positions.
Then if we start at $A$ and do moves $a_1,a_2\dots a_{n}$ we end up at either $B$ or $B_0$, in the first case we have given a path with $1008$ edges or less , in the second case, if we do moves $a_1,a_2\dots a_n,0$ we have a path from $A$ to $B$ with $1008$ edges or less. This works in every case except when $A$ and $B$ differ in exactly $1008$ positions, in this case notice we get a path of length $1008$ by doing the moves in $\{1,2,3\dots 2016\}\setminus\{a_1,a_2\dots a_n\}$.
Now notice that if $A$ and $B$ are two strings and $A$ shares $n$ positions with $B$ then the number of positions in which $A_k$ is equal to $B$ is:

$2016-n$ if $k=0$
$2016-n+1$ if $k\neq 0$ and $A$ and $B$ are equal at position $k$
$2016-n-1$ if $k\neq 0$ and $A$ and $B$ have different position $k$.

So if $n'$ is the number of positions in which $A_k$ and $B$ are equal we have $|n'-(2016-n')|\leq |n-(2016-n)|+2$.
Take two strings $A$ and $B$ differing in $1008$ positions. Then if $A'$ is a vertex reached from $A$ with less than $1008$ moves and $n'$ is the number of positions in which $A'$ differs from $B$ we obtain $|n'-(2016-n')|<2016$. Implying $A'\neq B,B_0$.
This proves the diameter is $1008$.