TITLE: Microeconomics. How to solve mathematically Exchange/Edgeworth Box models.
QUESTION [0 upvotes]: Problems
Hey guys. First post here. So im an econ student and these are the questions i am faced with VS the answers that i am supposed to have. I understand Edgeworth Box models from the lecture notes they provided but there were no examples mathematically. it was just 100 drawings so im stumped when it comes to whats happening here. I'm assuming it has to do with the MRS of the goods but i really dont know where to start.
Any tips on how to solve these problems?
thank you

REPLY [0 votes]: As far as I can tell, in economics it is common practice to explain everything with pictures, without a single non-trivial formula.
Leaving no hope for any computational approach.
On the other hand, if a concrete algebraic or differential equations were used for the models, the complexity of all the derivations and proofs would be tremendous.
That's sort of justifies the explanations in terms of inequalities only.


TITLE: Determining a constant to a Bessel function solution to an ODE
QUESTION [1 upvotes]: I am using the generalized Bessel function to obtain a solution to an ODE. The derivative of the general solution is something like
\begin{align}
\frac{dT_{1}}{dx} =  \frac{3}{4}Ax^{\frac{1}{4}} \Big[c_1 I_{-\frac{1}{3}}\Big(Ax^{\frac{3}{4}}\Big) + c_2 I_{\frac{1}{3}}\Big(Ax^{\frac{3}{4}}\Big)\Big]
\end{align}
where A is a constant. Applying the boundary condition
\begin{align}
\frac{dT_{1}}{dx}\Big|_{x=0} = 0
\end{align}
results in
\begin{equation}
0 =  (0)^{\frac{1}{4}} \Big[c_1 I_{-\frac{1}{3}}\Big(0\Big) + c_2 I_{\frac{1}{3}}\Big(0\Big)\Big]
\end{equation}
where
\begin{equation}
I_{-\frac{1}{3}}\Big(0\Big) \longrightarrow   \infty
\end{equation}
\begin{equation}
I_{\frac{1}{3}}\Big(0\Big) \longrightarrow   0
\end{equation}
The problem is with the first zero on the right hand side. It seems like this would make the entire right hand side zero and make the boundary condition useless in determining the constants. However, I found this same problem in a textbook and they determined that $c_1=0$, but they did not give details and said they will let the reader verify this on their own. I can see where $c_1=0$ if the first zero is ignored but can that really be done? Is the zero really a problem and if so, what can be done about it?
If it is helpful, another boundary condition is
\begin{align}
\frac{dT_{1}}{dx}\Big|_{x=L} = 0
\end{align}
Any help would be appreciated.
Thanks

REPLY [0 votes]: Your case might be different from the case in the textbook because there is $x^{1/4}$ multiplying the Bessel function.
The function
$x^{\frac{1}{4}} I_{-\frac{1}{3}}\Big(Ax^{\frac{3}{4}}\Big)$
doesn't tends to infinity for $x$ tending to $0$.
$$c_1x^{\frac{1}{4}} I_{-\frac{1}{3}}\Big(Ax^{\frac{3}{4}}\Big)=\frac{c_1}{(2A)^{1/3}\Gamma(2/3)}+O(x^2)$$
So, the condition for this term to be equal to $0$ is $c_1=0$


TITLE: Proof for equality of energy for heat equation.
QUESTION [0 upvotes]: Given:
Heat equation: $(1)\begin{cases}\frac{\partial u}{\partial t }-\frac{\partial^2 u}{\partial x^2}=f\quad pp. \text{in}\quad  \Omega\times]0,T[\\
u=0\quad pp. \text{in}\quad  \partial\Omega\times]0,T[\\
u(x,0)=u_0(x)\quad pp. \text{in}\quad  \Omega
 \end{cases}$
Letting $u$ the solution of $(1)$ such that is a regulier in $\Omega\times]0,T[$ , I want to prove the following equality $(2)$ which is called "energy equality" of $(1)$:
$$\frac12\int_{\Omega} u(x,t)^2+\int_{0}^{t}\int_{\Omega}|\nabla(x,s)|^2 dx ds =\frac12\int_{\Omega} u_0(x)^2+\int_{0}^{t}\int_{\Omega} f(x,s)u(x,s)dxds\tag{2}$$. In my attempt I multipliedboth sides of $(1)$ by $u$ then using integration by part but i didn't come up to the desired equality ,I want to know its proof using clear steps because this equality is so important in my studies for evolution equation topics .However I made some search about this energy equality i didn't find its proof .Thanks in advanced

REPLY [2 votes]: The energy functional is :
$$E(t) = \frac 12 \int_\Omega u(x,t)^2$$
Assuming $u$ is regular enough, we have :
\begin{align}
\frac{\text dE}{\text dt} &= \int_\Omega u \frac{\partial u}{\partial t} \\
&= \int_\Omega u \left(f +\nabla^2 u\right)\\
&= \int_\Omega uf - |\nabla u|^2
\end{align}
were the last step is integration by part over $\Omega$, using $u= 0$ on $\partial \Omega$.
Therefore, we have :
$$E(t) + \int_0^t\int_\Omega |\nabla u|^2 = E(0) + \int_0^t\int_\Omega uf$$


TITLE: inhomogeneous heat equation with mixed boundary conditons
QUESTION [3 upvotes]: Solve $$U_{t}=U_{xx}+u$$ with mixed boundary conditions $$U_x(0,t)=0, U(l,t)=0$$
and initial condition $$U(x,0)=\varphi(x)$$
I know that I have to use separation of variables and I have an idea of how to do it when its either just Dirichlet or just Neumann but both together and with a source I have no idea any help would be appreciated.

REPLY [3 votes]: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\mrm}[1]{\,\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\partiald{\mrm{U}\pars{x,t}}{t} =
     \partiald[2]{\mrm{U}\pars{x,t}}{x} + \mrm{u}\pars{x,t}\,,\qquad
\left\lbrace\begin{array}{rcccl}
\ds{\left.\partiald{\mrm{U}\pars{x,t}}{x}\,\right\vert_{\ x\ =\ 0}} & \ds{=} &
\ds{\mrm{U}\pars{L,t}} & \ds{=} &  \ds{0}
\\[3mm]
\ds{\mrm{U}\pars{x,0}} & \ds{=} & \ds{\varphi\pars{x}}&&
\end{array}\right.}$.

First, we look for a lineal combination $\ds{A\sin\pars{kx} + B\cos\pars{kx}}$ which satisfies the homogeneous boundary conditions at
$\ds{x = 0\ \mbox{and}\ x = L}$.
$\ds{\left.\vphantom{\large A}0 = k\bracks{A\cos\pars{kx} - B\sin{kx}}
\right\vert_{\ x\ =\ 0}\,\,\, =\,\,\, kA}$ is satisfied with $\ds{k = 0}$ or $\ds{A = 0}$. $\ds{k = 0}$ just adds a constant term which vanishes out because $\ds{\mrm{U}\pars{L,t} = 0}$.
$\ds{B\cos\pars{kL} = 0}$ is satisfied whenever
$\ds{k \in W \equiv \braces{\pars{n + \half}\,{\pi \over L}\,,\ n = 0,1,2,\ldots}}$

Now, we are ready to write the general solution as
$\ds{\mrm{U}\pars{x,t} =
\sum_{k}A_{k}\pars{t}\cos\pars{kx}}$ where $\ds{k \in W}$. It satisfies:
\begin{equation}
\sum_{k}\totald{A_{k}\pars{t}}{t}\,\cos\pars{kx} =
-\sum_{k}A_{k}\pars{t}k^{2}\cos\pars{kx} + \mrm{u}\pars{x,t}
\end{equation}
Multiply both sides by $\ds{\cos\pars{qx}}$, where $\ds{q \in W}$, and integrate over $\ds{\pars{0,L}}$:
\begin{equation}
\totald{A_{q}\pars{t}}{t} =
-q^{2}A_{q}\pars{t} + \hat{\mrm{u}}_{q}\pars{t}\,,\qquad
\hat{\mrm{u}}_{q}\pars{t} \equiv
{2 \over L}\int_{0}^{L}\mrm{u}\pars{x,t}\cos\pars{qx}\,\dd x\tag{1}
\end{equation}
Also,
\begin{equation}
\varphi\pars{x} = \mrm{U}\pars{x,0} =
\sum_{k}A_{k}\pars{0}\cos\pars{kx}\quad\imp\quad
A_{k}\pars{0} =
{2 \over L}\int_{0}^{L}\varphi\pars{x}\cos\pars{kx}\,\dd x
\tag{2}
\end{equation}

Eqtn. $\ds{\pars{1}}$ is easily solved:
\begin{align}
\totald{\bracks{\exp\pars{q^{2}\, t}A_{q}\pars{t}}}{t} & =
\exp\pars{q^{2}\, t}\hat{\mrm{u}}_{q}\pars{t}\,,\qquad
\pars{~A_{k}\pars{0}\ \mbox{is given by}\ \pars{2}~}
\\[5mm] \imp
A_{q}\pars{t} & =
A_{q}\pars{0}\exp\pars{-q^{2}\, t} +
\int_{0}^{t}\exp\pars{-q^{2}
\pars{t - \tau}}\hat{\mrm{u}}_{q}\pars{\tau}\,\dd\tau
\\
& \hat{\mrm{u}}_{q}\pars{\tau}\ \mbox{is given in}\ \pars{1}.
\end{align}

The $\ds{\underline{final\ solution}}$ which satisfies the conditions at the top is given by:
\begin{align}
\color{#66f}{\mrm{U}\pars{x,t}} & =
\color{#66f}{\sum_{q}\bracks{A_{q}\pars{0}\exp\pars{-q^{2}\, t} +
\int_{0}^{t}\exp\pars{-q^{2}
\pars{t - \tau}}\hat{\mrm{u}}_{q}\pars{\tau}\,\dd\tau}\cos\pars{qx}}\,,\quad
q \in W
\\[5mm]
A_{q}\pars{0} & = {2 \over L}\int_{0}^{L}\varphi\pars{x}\cos\pars{qx}\,\dd x
\,,\qquad
\hat{\mrm{u}}_{q}\pars{t} \equiv
{2 \over L}\int_{0}^{L}\mrm{u}\pars{x,t}\cos\pars{qx}\,\dd x\,,\quad
q \in W
\end{align}


TITLE: Proving join and meet equality
QUESTION [1 upvotes]: Prove that in any lattice $L$, we have
\begin{equation} ( (x\wedge y) \vee (x \wedge z)) \wedge ( (x \wedge y) \vee (y \wedge z)) = x \wedge y\end{equation} for all $x, y, z \in L$.

I showed $(x\wedge y)\le (x\wedge y) \vee (x \wedge z)$ and $(x\wedge y)\le (x \wedge y) \vee (y \wedge z)$ to imply that $(x\wedge y)$ is a lower bound of the pair $(x\wedge y) \vee (x \wedge z)$ and $(x \wedge y) \vee (y \wedge z)$. But I cannot show that $(x\wedge y)$ is the glb of $(x\wedge y) \vee (x \wedge z)$ and $(x \wedge y) \vee (y \wedge z)$.

REPLY [1 votes]: We have that $x \wedge y \leq x$ and $x \wedge z \leq x$, so $(x \wedge y) \vee (x \wedge z) \leq x$. Similarly we get $(x \wedge y) \vee (y \wedge z) \leq y$. Putting this together we get
$$
((x \wedge y) \vee (x \wedge z)) \wedge ((x \wedge y) \vee (y \wedge z)) \leq x \wedge y,
$$
which together with the direction you proved completes the argument.


TITLE: Can we reduce the 3-nested summation into 2-nest summation?
QUESTION [0 upvotes]: My problem started with the first case that I have :
$$
I_{2}=a^{k_1} (a+b)^{k_2}
$$
Where $k_1,k_2$ are real positive integers. Using the series expansion :
$$
(a+b)^n=\sum_{i_1=0}^{n} \binom{n}{i_1} a^{n-i_1} b^{i_1}
$$
Therefore,
$I_2$ can be expressed as
$$
I_2=\sum_{i_1=0}^{k_2} \binom{k_2}{i_1} a^{k_1+k_2-i_1} b^{i_1}
$$
The second case is:
$$
I_3=a^{k_1} (a+b)^{k_2} (a+b+c)^{k_3}
$$
After using the series expansion 3 times, we get
$$
I_3=\sum_{i_1=0}^{k_2} \sum_{i_2=0}^{k_3} \sum_{i_3=0}^{k_3-i_2}
\binom{k_2}{i_1}\binom{k_3}{i_2}\binom{k_3-i_2}{i_3}
a^{k_1+k_2+k_3-i_1-i_2-i_3}
b^{i_1+i_3} c^{i_2}
$$
My question is how can we reduce the 3-nested sum into 2-nested sum? To be more specific, I really want to express $I_3$ as 2-nested sum.

REPLY [1 votes]: Temporarily write $r=a+b$.
$$(r+c)^{k_3}=\sum_{m=0}^{k_3}{k_3\choose m}r^mc^{k_3-m}$$
$$r^{k_2}(r+c)^{k_3}=\sum_{m=0}^{k_3}{k_3\choose m}r^{m+k_2}c^{k_3-m}=\sum_{m=0}^{k_3}{k_3\choose m}(a+b)^{m+k_2}c^{k_3-m}$$
This is $$\sum_{m=0}^{k_3}{k_3\choose m}\sum_{n=0}^{m+k_2}{m+k_2\choose n}a^nb^{m+k_2-n}c^{k_3-m}$$ So we get $$\sum_{m=0}^{k_3}\sum_{n=0}^{m+k_2}{k_3\choose m}{m+k_2\choose n}a^{n+k_1}b^{m+k_2-n}c^{k_3-m}$$


TITLE: Type for "ways values can be different"
QUESTION [8 upvotes]: I am looking for a concept in type theory that I am sure has probably been explored, but do not know the name behind.
Let's consider a ML-like language with product and sum types and a Hindley-Milner like type system. I'll use OCaml syntax.
I'm wondering about ways two different values can be different.
Use
My use case is writing "clearer" error messages in a xUnit-like library: if two values are different when they were expected to be equal, this can help build a clearer better message:
Before:

Values differ: expected {x = [1;2;3;4], y = "a long string"}, got {x = [1;2;3;3], y = "a long string"}

After:

Values differ: at position .x[3], expected 4, got 3.

(there might be a relation with functional lenses since we're ultimately constructing a lens to a smaller value which differs).
Product types
For example:
type p =
  { x : int
  ; y : string
  }

Equality can be defined as:
let equal a b =
  equal_int a.x b.x && equal_string a.y b.y

But it's also possible to reify the differences:
type delta_p =
  | Equal
  | Diff_x of int * int
  | Diff_y of string * string

let diff_p a b =
  if not (equal_int a.x b.x) then
    Diff_x (a.x, b.x)
  else if not (equal_string a.y b.y) then
    Diff_y (a.y, b.y)
  else
    Equal

(it might make sense to define a delta_int type as int * int to show that it is recursive)
Sum types
For a sum type there are more ways to differ: having a different constructor, or a different value
type s = X of int | Y of string

type ctor_s =
  | Ctor_X
  | Ctor_Y

type delta_s =
  | Equal
  | Diff_ctor of ctor_s * ctor_s
  | Diff_X of int * int
  | Diff_Y of string * string

let diff_s a b = match (a, b) with
  | X xa, X xb ->
    if equal_int xa xb then
      Equal
    else
      Diff_X (xa, xb)
  | (* Y case similar *)
  | X _, Y _ -> Diff_ctor (Ctor_X, Ctor_Y)
  | Y _, X _ -> Diff_ctor (Ctor_Y, Ctor_X)

What's the name of this concept? Where can I learn more about this?
Thanks!

REPLY [9 votes]: I think you are looking for a typed variant of anti-unification. Anti-unification can be described as follows. First, suppose that we have a grammar of terms as follows:
t ::= () | (t, t) | C t | X

Here, () and (t, t) denote units and pairs, C t is a term with a leading constructor, and X is a term variable, which could be substituted for any term.
The anti-unification problem says, if you give two terms t1 and t2, what is the least general term t such that there are substitutions s1 and s2 such that s1(t) = t1 and s2(t) = t2.
As a concrete example, given two terms
t1 = Cons(3, Cons(2, Cons(1, Nil)))
t2 = Cons(1, Cons(2, Cons(3, Nil)))

the anti-unification algorithm would return the anti-unifier
t = Cons(X, Cons(2, Cons(Y, Nil)))

because the substitutions s1 = [X:3, Y:1] and s2 = [X:1, Y:3] applied to t would give you t1 and t2 back. As an aside, we needed to  specify "least general" because otherwise:
t' = Z

with the substitutions s1 = [Z:t1] and s2 = [Z:t2] would do the trick.
Anti-unification was invented by Gordon Plotkin, and is a delightfully simple algorithm. Assume you have an injective name-generation function gen $: \mathrm{Term} \times \mathrm{Term} \to \mathrm{Var}$. Then we can find an antiunifier as follows
antiunify ()       ()         = ()
antiunify (t1, t2) (t1', t2') = (antiunify t1 t1', antiunify t2 t2')
antiunify (C t)    (C t')     = C (antiunify t t')
antiunify t        t'         = gen(t, t') -- default: t and t' dissimilar

Augmenting this algorithm to return the two substitutions s1 and s2 I leave as an exercise.


TITLE: Finding period of $g(x)=\cos2x+\cos(\frac{2x}{3})+\cos(\frac{2x}{5})$
QUESTION [1 upvotes]: Determine the period of,
$$g(x)=\cos2x+\cos(\frac{2x}{3})+\cos(\frac{2x}{5})$$
My thinking is that if three periodic functions $f_1(x), f_2(x), f_3(x)$ have periods $T_1, T_2, T_3$ then the period of the function $g(x)=f_1(x)\pm f_2(x) \pm f_3(x)$ is L.C.M. (Least common multiple) of $T_1, T_2, T_3$.
Using the equation that $P = \frac{2\pi}{B}$
So $f_1(x) = \cos2x$ then $f_1(x) = 2 \cos x$, then the period of that would be $\pi$
So $f_2(x) = \cos(\frac{2x}{3})$, then $f_2(x) = \frac{2}{3}\cos x$ , then the period would be $3\pi$
So $f_3(x) = \cos(\frac{2x}{5})$, then $f_3(x) = \frac{2}{5}\cos x$, then the period would be $5\pi$
So then the LCM of $f_1(x), f_2(x), f_3(x)$ would be $15\pi$.
I am not sure if this method is correct or if there is another method to use like taking,
$\cos(2x)=\cos(2(x+k\pi)) = \pi $

REPLY [0 votes]: Your method is correct. Alternatively:
$$g(x+T)=\cos{(2x+2T)}+\cos{(\frac{2x}{3}+\frac{2T}{3})}+\cos{(\frac{2x}{5}+\frac{2T}{5})}=g(x),$$
if $T=15\pi$.


TITLE: Is $f(x-at)$ a solution to the heat equation?? ($u_t=u_{xx}$)
QUESTION [2 upvotes]: Show that the heat equation $u_t = u_{xx}$ has solutions of the form $u(x, t) = f (x − at)$ where $a$ is a constant. Show that $a$ can have any value, real or complex, and describe the behavior of the solutions in both cases.

I'm a little unsure of what this question is looking for? Because when I plug f into the heat equation I'm left with $-af_t=f_{xx}$
Any guidance would be appreciated

REPLY [2 votes]: HINT
To elaborate on the discussion in the messages, let $u(x,t) = f(x-at)$ for some twice differentiable function $f$ and a constant $a \in \mathbb{C}$. Note that
$$
u_t = \frac{\partial u}{\partial t}
    = \frac{\partial f(x-at)}{\partial t}
    = f'(x-at) \frac{\partial [x-at]}{\partial t}
    = -a f'(x-at).
$$
Can you use a similar technique (Chain Rule, really) to compute $u_x, u_{xx}$ and verify that this form of $u$ indeed satisfies the desired equation?


TITLE: Arcing through an inductor
QUESTION [1 upvotes]: When a current is passed through an inductor coil, potential difference across it is given as $$V=L\frac{dI}{dt} \, .$$
Now, if we suddenly disconnect the coil from the circuit, the current will instantaneously go to zero and potential difference across it would approach infinite as $\frac{dI}{dt}\rightarrow\infty$. This will ionise the surrounding air and sparks will be produced.
My question is that if we repeat the above procedure in vacuum, would the sparks be produced?

REPLY [1 votes]: My question is that if we repeat the above procedure in vacuum, would
  the sparks be produced?

Not in perfect vacuum, because there is no gas to ionize. An understanding of this behavior can be attained by studying Paschen's Law (see http://en.wikipedia.org/wiki/Paschen%27s_law), which describes the breakdown voltage for given distance and pressure.


TITLE: Find all $a \in \mathbb R$ such that $3x^5 - 5x^3 + a = 0$ has exactly two real roots.
QUESTION [2 upvotes]: Find all $a \in \mathbb R$ such that $3x^5 - 5x^3 + a = 0$ has exactly two different real roots.
My attempt: This equation has to have one double root and one single root. I have no idea how to move on from this.

REPLY [1 votes]: All the answers thus far involve taking the derivative.  But the problem can be solved without using derivatives.
To have an even number of real roots the quintic equation gas to have a double root, meaning there is a squared factor.  Thus
$3x^3-5x^3+a=(x-r)^2(bx^3+cx^2+dx+e)$
Then expanding the product and matching like degree terms gives:
Degree 5:  $b=3$
Degree 4:  $-2rb+c=-6r+c=0, c=6r$
Degree 3:  $r^2b-2rc+d=3r^2-12r^2+c=-5, d=9r^2-5$
Degree 2:  $r^2c-2rd+e=6r^3-18r^3+10+e=0, e=12r^3-10$
Degree 1: $r^2d-2re=-15r^4+15r^2=0$
We have rederived the usual derivarive equation up to a constant factor which is, of course, irrelevant.  In general, when we require a polynomial function $P(x)$ to have a maximum or minimum at $(x_0,y_0)$, we impose the requirement that $x_0$ be a double root for $P(x)-y_0=0$, and without calculus an analysis like the one above gives the same equation as $P'(x)=0$ for $x_0$.
Then in this case, $r=0$ or $\pm 1$ whereupon, as in other answers, these values substituted for $x$ give $a=0$ or $\pm 2$.  These must still be checked, because the squared factor is only a necessary condition;  it turns out insufficient in the case of one root in the original problem.


TITLE: Definition of Conditional Expectation and its Uniqueness
QUESTION [3 upvotes]: there are many questions on Mathexchange, e.g. Definition of conditional expectation, discussing the definition of conditional expectation. In most cases the random variable which is later named "conditional expectation" is assumed to be a measurable $\Omega\rightarrow\mathbb R$ function. In some lecture notes (that are maybe too advanced for me) conditional expectation is defined to be a $\Omega\rightarrow\mathbb R^n$ measurable function -- but imposes in the definition that this function is a.e. unqiue. For me it feels that we do not need a.e. uniqueness in the definition but that it can be proven (I failed though). So how is uniqueness of conditional expectation proven in $\mathbb R^n$ or even more general, in Banach spaces?
Edit: Interestingly, this five-year-old question receives some attention now. The conditional expectation $Z$ of a random variable $X:\Omega\rightarrow S$ given a sub-$\sigma$-algebra $\mathcal G$ satisfies $$\int_G Z\,\mathrm dP = \int_G X\,\mathrm dP$$ for all $G\in\mathcal G$. The common notation is $\mathbb E[X\mid\mathcal G] := Z$.
It can be shown in the case $S = \mathbb R$ that if such a random variable exists, it is unique. The proof can be found e.g. here: Proof that conditional expectation is defined uniquely almost everywhere? This proof does not work for $S = \mathbb R^n$, or more general $S = $ some Banach space. The question is: how can I prove uniqueness in these cases?

REPLY [0 votes]: The additional imposed condition (of the uniqueness up to a set of measure zero) in the definition for $\mathbb{R}^n$ might be just a way of phrasing it and condensing several statements into one. I am not aware of any principal difference between conditional expectations of variables taking values in $\mathbb{R}$ and $\mathbb{R}^n$. There could be some room for a formal subtlety of whether you define the expectation as a random variable or as a class of equivalence of random variables. I believe it is most convenient to define the conditional expectation as any representative of the equivalence class, and then proceed to establishing that if the measurable spaces are nice, then we can choose representatives from the classes of equivalence in such a way that the family of functions $$\Sigma\ni A \mapsto P(A|t):=\mathbb{E}[1_{A}| T=t],\quad \forall t\in \mathrm{range}(T)$$ has the properties we expect from a conditional probability measure $P(\cdot|t)$. Here $\mathbb{E}[1_{A}| T=t]$ is a measurable function from $\mathrm{range}(T)$, which are defined using Doob-Dynkim lemma, as described in this Wikipedia article. Note that $\mathbb{E}[1_{A}| T]$ and $\mathbb{E}[1_{A}| T=t]$ are different objects. See e.g. Chapter 2.5 in Testing Statistical Hypotheses by Lehmann and Romano for details on choosing the right representatives from the equivalence classes.
 Your question about proving the uniqueness up to a set of measure zero is answered here.  [Edit]
I don't feel qualified to talk about general Banach spaces, but the starting point is the Bochner Integral.


TITLE: Information theoretic interpretation of Stirling's formula
QUESTION [2 upvotes]: I am looking for an interpretation of Stirling's formula using information theory.
Suppose you have $n$ different objects and $n$ different labels. There are $n!$ different ways of assigning the labels to the objects, provided that no two different objects get assigned the same label. The corresponding entropy is thus $\log_2(n!)$.
This entropy is less than or equal to the sum of the entropies of each object. Fixing an object, there are $n$ possible labels, each occurring with equal probability. So each object has entropy $\log_2(n)$.
We thus get $\log_2(n!) \leq n\log_2(n)$.
My question is how to get the next term in Stirling's formula ($-n\log_2(e)$) at least intuitively, and using information theory, when $n$ is large?

REPLY [2 votes]: Just for fun: it is enough to exploit the prime number theorem $\pi(n)\sim\frac{n}{\log n}$. Legendre's theorem on $\nu_p(n!)$ ensures
$$ n! = \prod_{p\leq n} p^{\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p^2}\rfloor+\ldots}\leq \prod_{p\leq n}p^{\frac{n}{p-1}} $$
which is a rather crude bound, but already sufficient:
$$ \log(n!) \leq n\sum_{p\leq n}\frac{\log(p)}{p-1}=n\sum_{m\leq n}\mathbb{1}_p(m)\frac{\log m}{m-1}\stackrel{\text{SBP}}{=}\underbrace{n\pi(n)\frac{\log n}{n-1}}_{O(n)}+n\sum_{m\leq n-1}\pi(m)\left[\frac{\log m}{m-1}-\frac{\log(m+1)}{m}\right].$$
Here $\mathbb{1}_p$ is the characteristic function of primes, $\pi$ is the prime-counting function and $\text{SBP}$ stands for summation by parts. In the last sum the main term behaves like $\frac{1}{m}+O\left(\frac{\log m}{m^2}\right)$, hence
$$\log(n!) = O(n)+n\sum_{m\leq n-1}\frac{1}{m} =n\log(n)+O(n).$$
Of course this is extreme cheating: historically speaking, weak forms of the PNT were derived from the asymptotics for $n!$ or $\binom{2n}{n}$, while here we performed just the opposite. A more elementary approach is to consider that
$$ \frac{4^n}{\sqrt{n+1}}<\binom{2n}{n}=\frac{(2n)!}{n!^2}<4^n $$
where the inequality on the right is trivial and the inequality on the left follows from $\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^2$ and Cauchy-Schwarz. By the theory of moments, the previous inequality holds for non-integer values of $n$, too, so by letting $L(n)=\log(n!)$ we have
$$ L(n)-2 L(n/2) < n\log(2), $$
$$ 2L(n/2)- 4L(n/4) < n\log(2), $$
$$ 4L(n/4)- 8 L(n/8) < n\log(2), $$
$$ \ldots $$
and
$$ L(n) - 2^k L\left(\frac{n}{2^k}\right) \leq kn\log(2). $$
By picking $k\approx \log_2(n)=\frac{\log(n)}{\log(2)}$ the claim $L(n)\sim n\log n$ is proved.


TITLE: How to solve $ x^2=19 \mod 25$. Modular of prime power.
QUESTION [0 upvotes]: Is this method correct?
$x^2=19 \mod 25, x^2=44 \mod 25, x^2=69 \mod 25, x^2=94 \mod 25, x^2=119 \mod 25, x^2=144 \mod 25$
Therefore, $x=12 \mod 25, x= 13 \mod 25$.
Or should I have to split $x^2 = 19 \mod 25$ into $x^2= 19 \mod 5, x^2 = 19 \mod 5$.
$x^2= 19 \mod 5$ gives $x=2 \mod 5$,  $x= 3 \mod 5$.
By using $x=2 \mod 5 , x= 3 \mod 5$ I would arrive at the same $x = 12 \mod 25, x= 13 \mod 25$.
Using the second method, I found $x=5k+2$, $x=5k+3$. By substituting this in $x^2=19mod25$ I get $20k+4 = 19 mod 25$ which gives $4k = 3 mod 5$. Therefore, $k = 2$ which provides $x=12$. Similarly, when I substitute $x=5k+3$ in $x^2=19mod25$ I get $x=13$
Are both ways correct?

REPLY [1 votes]: The first method is correct. Essentially, what you're doing is that
$$x^2\equiv 144\pmod{25}\\
\implies (x-12)(x+12)\equiv0\pmod{25}$$
Now product of two numbers is divisible by $25$ means either both of them are divisible by $5$ (which is not possible here because their difference is $24$ which is not divisible by $5$) or one of the numbers is divisible by $25$. So the required solution is $x\equiv12\ \text{or}\ 13\pmod{25}$.
Edit:
Now that the question is edited, what OP meant in the second method is clearer now. So that is also right.


TITLE: Compute $\| T \|$ with the norm $\| \cdot \| := \max_{j=1,\ldots,n} (|\cdot_j|)$
QUESTION [4 upvotes]: Let $A \colon = [\alpha_{ij}]_{m\times n}$ be a given $m \times n$ matrix of real numbers.
Let $\mathbb{R}^n$ be the normed space of all ordered $n$-tuples of real numbers with the norm defined as follows:
$$\Vert x \Vert_{\mathbb{R}^n} \colon= \max_{j=1, \ldots, n} \left( \vert \xi_j \vert \right) \ \ \ \forall x \colon= (\xi_1, \ldots, \xi_n) \in \mathbb{R}^n.$$
Let $\mathbb{R}^m$ be the normed space of all ordered $m$-tuples of real numbers with the norm defined as follows:
$$\Vert y \Vert_{\mathbb{R}^m} \colon= \max_{i=1, \ldots, m} \left( \vert \eta_i \vert \right) \ \ \ \forall y \colon= (\eta_1, \ldots, \eta_m) \in \mathbb{R}^m.$$
Let the operator $T \colon \mathbb{R}^n \to \mathbb{R}^m$ be defined as
$$T(x) \colon= Ax \ \ \ \forall x \in \mathbb{R}^n;$$
where $x$ and $y$ are to be written as column vectors and $Ax$ denotes the usual matrix product. Of course, $T$ is linear.
What is $\Vert T \Vert$?
Here we are using the following definition for $\Vert T \Vert$:
$$\Vert T \Vert \colon= \sup \left\{ \ \frac{\Vert T(x)\vert_{\mathbb{R}^m}}{\Vert x \Vert_{\mathbb{R}^n}} \ \colon \ x \in \mathbb{R}^n, \ x \neq \theta_{\mathbb{R}^n} \ \right\}. $$
Here $\theta_{\mathbb{R}^n} $ denotes the zero vector in $\mathbb{R}^n$.
My effort:
For any $x \colon= (\xi_1, \ldots, \xi_n ) \in \mathbb{R}^n$, we have
\begin{eqnarray*}
\Vert T(x) \Vert_{\mathbb{R}^m}
&=& \max_{i=1, \ldots, m} \left( \left\vert \sum_{j=1}^n \alpha_{ij} \xi_j \right\vert \right) \\
& \leq & \max_{i=1, \ldots, m} \left( \sum_{j=1}^n \vert \alpha_{ij} \xi_j \vert \right) \\
&=&  \max_{i=1, \ldots, m} \left( \sum_{j=1}^n  \left( \vert \alpha_{ij} \vert \cdot \vert \xi_j \vert \right) \right) \\
&\leq & \Vert x \Vert_{\mathbb{R}^n} \cdot \max_{i=1, \ldots, m} \left( \sum_{j=1}^n \vert \alpha_{ij} \vert \right).
\end{eqnarray*}
If $x$ is not the zero vector, then upon deviding by the norm of $x$ and then taking the supremum of the quantity on the left hand side, we obtain
$$\Vert T \Vert \leq \max_{i=1, \ldots, m} \left( \sum_{j=1}^n \vert \alpha_{ij} \vert \right). $$
How to show that
$$\Vert T \Vert = \max_{i=1, \ldots, m} \left( \sum_{j=1}^n \vert \alpha_{ij} \vert \right)? $$

REPLY [2 votes]: It suffices to show that at least one $x$ with $\|x\|_{\mathbb{R}^n}=1$ achieves the specific bound. Let
$$i^*=arg\max_{i=1,2,\ldots,m}\sum_{j=1}^n{|a_{ij}|}$$
i.e. $i^*$ is the index of the row of $A$ with the largest sum of absolute values of its elements. Then, if we select $\xi_j=sign(a_{i^*j}$) we have that $\|x\|_{\mathbb{R}^n}=1$  and
$$\bigg|\sum_{j=1}^{n}{a_{i^*j}\xi_j}\bigg|=\sum_{j=1}^n{|a_{i^*j}|}=\max_{i=1,2,\ldots,m}\sum_{j=1}^n{|a_{ij}|}$$
Thus the vector $x^*:=[sign(a_{i^*1}),\ldots,sign(a_{i^*n})]^T$ achieves your bound and therefore $\max_{i=1,2,\ldots,m}\sum_{j=1}^n{|a_{ij}|}$ is  indeed the induced matrix norm.


TITLE: Why do some accept zero as a natural number but others don't?
QUESTION [4 upvotes]: I have had many teachers who have told me that zero is a natural number but then there is those teachers who say its not. why is that ?

REPLY [2 votes]: I think that modern definitions include zero as a natural number. But sometimes, expecially in analysis courses, it could be more convenient to exclude it.
Pros of considering $0$ not to be a natural number:

generally speaking $0$ is not natural at all. It is special in so many respects;
people naturally start counting from $1$;
the harmonic sequence $1/n$ is defined for any natural number n;
the $1$st number is $1$;
in making limits, $0$ plays a role which is symmetric to $\infty$, and the latter is not a natural number.

Pros of considering $0$ a natural number:

the starting point for set theory is the emptyset, which can be used to represent $0$ in the construction of natural numbers; the number $n$ can be identified as the set of the first $n$ natural numbers;
computers start counting by $0$;
the rests in the integer division by a $n$ are $n$ different numbers starting from $0$ to $n-1$;
it is easier to exclude one defined element if we need naturals without zero; instead it is complicated to define a new element if we don't already have it;
integer, real and complex numbers include zero which seems much more important than $1$ in those sets (those sets are symmetric with respect to $0$);
there is a notion to define sets without $0$ (for example $\mathbb R_0$ or $\mathbb R_*$), or positive numbers ($\mathbb R_+$) but not a clear notion to define a set plus $0$;
the degree of a polynomial can be zero, as can be the order of a derivative;

I have seen children measure things with a ruler by aligning the $1$ mark instead of the $0$ mark. It is difficult to explain them why you have to start from $0$ when they are used to start counting from $1$. The marks in the rule identify the end of the centimeters, not the start, since the first centimeter goes from 0 to 1.
An example where counting from $1$ leads to somewhat wrong names is in the names of intervals between musical notes: the interval between C and F is called a fourth, because there are four notes: C, D, E, F. However the distance between C and F is actually three tones. This has the ugly consequence that a fifth above a fourth (4+3) is an octave (7) not a nineth! On the other hand if you put your first finger on the C note of a piano your fourth finger goes to the F note.
I would say that in the natural language the correspondence between cardinal numbers and ordinal numbers is off by one, thus distinguishing two sets of natural numbers, one starting from 0 and one starting from 1st. The 1st of January was day number $0$ of the new year. And zeroth has no meaning in the natural language...


TITLE: Example on Lebesgue Outer Measure
QUESTION [0 upvotes]: Give an example of a sequence $\{E_i\}$ of disjoint sets such that $m^*(\cup_{i=1}^{\infty}E_i)<\sum_{i=1}^{\infty}m^*(E_i)$.

REPLY [1 votes]: According to this post here: Vitali set of outer-measure exactly $1$., you can construct a Vitali set for $[0,1]$ with Lebesgue outer measure equal to $1$. On the other hand the Lebesgue outer measure coincide with Lebesgue measure for $[0,1]$ so: $m^*([0,1])=1$. Moreover this interval can be written as the union of disjoint Vitali sets (Vital set and its rational translation). Let $r_i$ be the enumeration of rationals and let $V_i$ be the rational translation of Vitali set by $r_i$. So we have $\displaystyle  [0,1]=\bigcup_{i=1}^{\infty} V_i$.
But then
$$
\displaystyle 1=m^*(\bigcup_{i=1}^{\infty}V_i)<\sum_{i=1}^{\infty}m^*(V_i)=\sum_{i=1}^{\infty}1\rightarrow \infty
$$
Another way, is to use usual Vitali set construction over $[0,1]$. Now again set $r_i$, the enumeration of rationals, and $V_i$, the rational translation of Vitali set by $r_i$. We have $\displaystyle  [0,1]=\bigcup_{i=1}^{\infty} V_i$ therefore  $\displaystyle 1=m^*(\bigcup_{i=1}^{\infty}V_i)$, however
$$
\sum_{i=1}^{\infty}m^*(V_i)=\sum_{i=1}^{\infty} m^*(V)=\infty \times m^*(V).
$$
This has two consequences. Firstly $m^*(V)$ cannot be zero because this will contradict the sub-additivity property of outer measures. Secondly because $m^*(V)\neq 0$ then $\sum_{i=1}^{\infty}m^*(V_i)=\infty$ which means:
$$
\displaystyle 1=m^*(\bigcup_{i=1}^{\infty}V_i)<\sum_{i=1}^{\infty}m^*(V_i)= \infty
$$


TITLE: The number of one-dimensional vector spaces in a field
QUESTION [0 upvotes]: Let $p$ be a prime number, $F=F_p$ a field with $p$ elements. $V$ is a vector space, $n$-dimensional over $F$. Calculate the number of one-dimensional vector spaces in $V$.
I tried to solve it, but without a success, I can't use Burnside's lemma because we didn't prove it. I would like to get help with this question.
Thanks

REPLY [2 votes]: Hints:
== Every $\;1$-dimensional subspace of $\;V\;$ is of the form ${}$ Span$\,\{v\}\;,\;\;0\neq v\in V\;$
== There are exactly $\;p-1\;$ vectors in $\;U:=$Span $\,\{v\}\;$ for which their span equals $\;U\;$ itself.

REPLY [0 votes]: The number of elements in $V$ is $p^n$. An one-dimensional subspace has $p$ elements. The intersection of two different one-dimensional subspaces has only one element ($0$), and every non-zero element generates an one-dimensional subspace.
Then, if $k$ is the number of such subspaces:
$$p^n=kp-(k-1)=1+k(p-1)$$
Therefore,
$$k=\frac{p^n-1}{p-1}=\sum_{j=0}^{n-1}p^j$$


TITLE: Rank and Range?
QUESTION [0 upvotes]: Let $F$ from $\mathbf{R}^3$ to $\mathbf{R}^3$ defined by
$F(x, y, z)=(x^3+y+z, y^3+y, x^3-y^3+z)$.
(a) Calculate the Jacobian of $F$. Determine the rank of $F'(x)$. On what set is the rank constant?
(b) Describe the range of $F$, and describe the level set $F^-1(30, 10, 20)$.
I have calculated the Jacobian to be $0$. I have some troubles on determining the rank and range.

Here is how I calculate the Jacobian:
Jacobian Calculate

And I just realized that if the Jacobian is $0$, this matrix is not invertible, right? Can someone check my Jacobian please?

REPLY [0 votes]: System won't let me write a comment, so I have to write a solution instead.
Turns out the Jacobian is $0$. I think this means that your operator is not invertible, but that's perfectly fine for calculating range and rank.
Notice that the three terms are linearly correlated, that is why you have Jacobian to be $0$. And that is why you are asked to do the rank and range. (If the operator is invertible, than range is $\mathbb{R}^3$ and rank is $3$, it's trivial then.


text:
\section{Additional material for the introduction}\label{app:intro}

\paragraph*{Other works on parameterized dynamic data structures.}
To give a broader background, we review some results on dynamic data structures for parameterized problems that are not directly relevant to the motivation of our work.

Dvo\v{r}\'ak and T\r{u}ma~\cite{DvorakT13} investigated the problem of counting occurrences (as induced subgraphs) of a fixed pattern graph $H$ in a dynamic graph $G$ that is assumed to be sparse
(formally, always belongs to a fixed class of bounded expansion $\Cc$). They gave a data structure that maintains such a count with amortized update time $\Oh(\log^{c} n)$, where the constant $c$
depends both on $H$ and on the class $\Cc$. As classes of bounded treedepth have bounded expansion (see~\cite{NesetrilM12}), by taking $H$ to be a path on $k$ vertices we obtain
a data structure for the dynamic $k$-path problem in graphs of treedepth smaller than $k$ with amortized polylogarithmic update time, where the degree of the polylogarithm depends on $k$.
Note that this result is significantly weaker than the one provided by us and by Alman et al.~\cite{AlmanMW17}, though it is obtained using very different tools.
The result of Dvo\v{r}\'ak and T\r{u}ma~\cite{DvorakT13} is based on a data structure of Brodal and Fagerberg~\cite{BrodalF99} for maintaining a bounded-outdegree orientation of a graph of bounded degeneracy, which also can be considered a dynamic parameterized data structure.

The dynamic setting for parameterized vertex cover and other vertex-deletion problems was first considered by Iwata and Oka~\cite{IwataO14}. As explained in Section~\ref{sec:introduction}, this work was continued and  significantly extended by Alman et al.~\cite{AlmanMW17}.
More recent advances include dynamic kernels for hitting and packing problems in set systems with very low update times~\cite{BannachHRT19},
and work on monitoring timed automata in data streams~\cite{GrezMPPR20}. Also, Schmidt et al.~\cite{SchmidtSVZK20} investigated a combination of parameterization and the concept of $\mathsf{DynFO}$.
This setting is, however, somewhat different, as the main focus is on performing updates that can be described using simple logical formulas, and not necessarily executable efficiently in the classic sense.

\paragraph*{Comparison with Dvo\v{r}\'ak et al.~\cite{DvorakKT14}.}
We present a quick overview of the approach that Dvo\v{r}\'ak et al.~\cite{DvorakKT14} used in their dynamic treedepth data structure. While doing this, we explain how our techniques differ and improves upon this approach. In this overview, we assume familiarity with $\MSO_2$ and basic understanding of $\MSO_2$-types.

We assume the following setting. We have a dynamic graph $G$, a fixed $\MSO_2$ sentence $\varphi$, and a parameter $d$ so that the treedepth of $G$ is promised to always be upper bounded by $d$ at all times. Our goal is to maintain a fully dynamic data structure $\Dt_\varphi[F,G]$ that maintains a recursively optimal elimination forest $F$ of $G$ and an answer to the query whether $G\models \varphi$. Let $q$ be the maximum of $d$ and the quantifier rank (i.e. maximum number of nested quantifiers) in $\varphi$. Note that thus, $q$ is {\em{at least}} $d$.

With each vertex $u\in V(G)$, let us associate a graph $G_u$ defined as in Section~\ref{secov:data} or Section~\ref{sec:data-structure}: $G_u$ has vertex set $\SReach_{F,G}(u)\cup \desc_F(u)$ and edge set comprising of all the edges of $G$ with at least one endpoint in $\desc_F(u)$.
The idea is to associate with each vertex $u$ the {\em{type}} of $G_u$, which is a piece of information that concisely describes all the properties of $G_u$ needed both for the task of computing the treedepth,
and for verifying satisfaction of $\varphi$.
In the work of Dvo\v{r}\'ak et al.~\cite{DvorakKT14}, this type is the $\MSO_2$ type of $G_u$ of quantifier rank $q$. The number of such types is bounded by a function of $q$ only, but this function is non-elementary: it is a tower of height $q$, which is not smaller than $d$.

We note that in~\cite{DvorakKT14},
this is presented somewhat differently. Namely, the type of $G_u$ is maintained implicitly by storing a bounded-size {\em{$S$-code}}: a representantive subgraph of $G_u$ having the same $\MSO_2$-type of quantifier rank $q$ as $G_u$, obtained by trimming superfluous subtrees in $F$.

Now, basic compositionality and idempotence properties of $\MSO_2$ imply that in order to compute the type of $G_u$, it suffices to know the multiset of types of graphs $G_v$ for all children $v$ of $u$ in $F$.
Moreover, there is a threshold $\tau$ depending on $d$ and $\varphi$ such that within this multiset, each type appearing more than $\tau$ times can be treated as if it appeared exactly $\tau$ times.
This can be related to the discussion of compositionality and idempotence in Sections~\ref{secov:data} and~\ref{sec:data-structure}.
Thus, for every vertex $u$ one can compute the type of $G_u$ from the types associated with the children in constant time, assuming we know the multiplicity of each type among the children up to the threshold $\tau$. This applies even though the number of children is unbounded. Intuitively, this allows efficient recomputation of the types upon modifications of the forest $F$, through a bucketing approach similar to that presented in Sections~\ref{secov:data} and~\ref{sec:data-structure}.

Thus, the design of the data structure itself in~\cite{DvorakKT14} is similar to ours: every vertex remembers all its children, but these children are partitioned into buckets (represented in~\cite{DvorakKT14} using {\em{merge nodes}}) according to their types. Note that thus, the number of buckets per vertex is bounded by a non-elementary function of $q\geq d$. The basic idea of achieving update time independent of $n$ is the same: during modifications of the elimination forest, we operate on whole buckets. Thus, re-attaching a whole bucket at a different place of the elimination forest can be done using a single operation in constant time.

The implementation of updates in~\cite{DvorakKT14} is, however, very different to ours and works roughly as follows. Suppose $F$ is a tree for simplicity. First, one finds a {\em{candidate new root}}: a vertex that may be the new root of an optimal elimination tree after the update.
Now comes the main trick: being a candidate root can be expressed by a (quite complicated) $\MSO_2$ formula of quantifier rank $d$,
hence we can use the types of rank $q\geq d$, stored in the data structure before the update, we can locate a candidate root.
Once the new root is located, we iteratively move the new root up the tree. During this process we need to fix a bounded number of subtrees, which can done by recursion, because each of the trees that needs to be fixed is of height at least one smaller. All in all, this update thus uses a fairly convoluted recursion scheme, where the number of recursive calls heavily depends on the number of types that the data structure keeps track of.

Thus, the aspect that contributes the most to the time complexity is the number of types on which the data structure relies, which directly corresponds to the number of buckets stored per vertex.
As we explained above, Dvo\v{r}\'ak et al.~\cite{DvorakKT14} use $\MSO_2$ types of a quantifier rank $q\geq d$, whose number is a tower of exponentials of height $q$. Note that the assumption that $q\geq d$ is necessary to be able to efficiently evaluate the $\MSO_2$ query locating a new root, which is needed in the update operation.

In our data structure, we are much more frugal when defining types of vertices for the purpose of maintaining a recursively optimal elimination forest. More precisely, we show that it is enough to classify each vertex $u$ according to (1) the treedepth of the subgraph induced by the descendants of $u$, including $u$;
and (2) the set of ancestors of $u$ that are adjacent to $u$ or any of its descendants. This gives only $d\cdot 2^d$ different types.
Moreover, we perform the update in a different way than Dvo\v{r}\'ak et al.: to construct an elimination forest $\wh{F}$ of the updated graph,
we extract a {\em{core}} $K\subseteq V(G)$ of size $d^{\Oh(d)}$ that contains both endpoints of the updated edge,
compute an optimum elimination forest $F^K$ of $G[K]$ using the static algorithm of Reidl et al.~\cite{ReidlRVS14} in time $2^{\Oh(d^2)}$, and construct $\wh{F}$ by re-attaching parts of $F$ lying outside of $K$ to $F^K$.
While this method is conceptually simpler than the approach used in~\cite{DvorakKT14}, justifying the correctness requires a quite deep and technical dive into the combinatorics of treedepth and of elimination forests. This analysis is explained in Sections~\ref{secov:cores} and~\ref{sec:cores}.
We remark that the concept behind the construction of the cores is analogous to that behind the construction of the $S$-codes in~\cite{DvorakKT14}, but we execute it so that the size of the core is much smaller. We also use the cores in a quite different way.

As far as augmentation of the data structure with a dynamic programming procedure is concerned, this is automatic in the approach of Dvo\v{r}\'ak et al.~\cite{DvorakKT14} for $\MSO_2$-expressible problems. Namely, the data structure anyway stores all the information about $\MSO_2$-types up to quantifier rank $q$, so the answers to all boolean $\MSO_2$ queries up to this quantifier rank are explicitly maintained. This, of course, comes at the cost of a huge explosion of complexity due to maintaining a partition into types that is potentially much finer than needed for the problem we are interested in. The language of configuration schemes and its implementation in the dynamic treedepth data structure via {\em{mugs}}, which we present in Section~\ref{sec:dp}, is designed to remedy this complexity explosion. Namely, it allows one to design a dynamic programming procedure and automatically combine it with the dynamic treedepth data structure so that the overhead in the update time paid for augmentation is polynomial in the number of states.

config: arxiv


TITLE: Algebraic closure of $\mathbb{C}(t)$
QUESTION [1 upvotes]: Let $\mathbb{C}(t)$ be the field of rational functions $f(t) = \frac{p(t)}{q(t)}$ with $p,q\in\mathbb{C}[t]$.
For instance, the function $g(t) = \sqrt{t}$ does not belong to $\mathbb{C}(t)$ but is lies in its algebraic closure $\overline{\mathbb{C}(t)}$ since it is a zero of the polynomial $X^2-t\in\mathbb{C}(t)[X]$.

Question. Is it correct to think of elements of $\overline{\mathbb{C}(t)}$ as functions $h = h(t)$ with values in
$\mathbb{C}$ such that $P(h(t)) = 0$ for some $P\in \mathbb{C}(t)[X]$?

REPLY [4 votes]: Elements of $\overline{C(t)}$ are not really functions since they do not have a common domain that would allow to add and multiply them. One way to think of $\overline{C(t)}$ is to consider the field of all formal Puiseux series centered at some point, so that addition and multiplication is well defined on them, and then take the subset consisting of those series which satisfy algebraic equations over $C(t)$. This definition depends on the starting point, but different points will lead to isomorphic fields which are different realizations of this algebraic closure.


TITLE: Transforming two 3D vectors into each other gives different Euler angles
QUESTION [0 upvotes]: Lets take two vectors A and B represented in x,y,z(metres) and Euler angles XYZr(deg) as
A =

   -0.0036    0.1235   -0.9213  120.2176   -0.4881  -87.1283

B =

   -0.1241   -0.0112   -1.1028  -58.4000    1.6000   92.1000

Converting them to 4x4 Homogeneous matrix gives
M_A =

    0.0501    0.9987   -0.0085   -0.0036
    0.5023   -0.0326   -0.8641    0.1235
   -0.8632    0.0390   -0.5033   -0.9213
         0         0         0    1.0000

M_B =

   -0.0366   -0.9989    0.0279   -0.1241
    0.5245    0.0046    0.8514   -0.0112
   -0.8506    0.0458    0.5238   -1.1028
         0         0         0    1.0000

Transform B into A and A into B gives
M_BA = inv(M_B) * M_A
M_AB = inv(M_A) * M_B

M_BA =

    0.9959   -0.0868   -0.0248   -0.0882
   -0.0873   -0.9960   -0.0185   -0.1114
   -0.0231    0.0206   -0.9995    0.2131
         0         0         0    1.0000

M_AB =

    0.9959   -0.0873   -0.0231    0.0830
   -0.0868   -0.9960    0.0206   -0.1230
   -0.0248   -0.0185   -0.9995    0.2088
         0         0         0    1.0000

Converting M_BA and M_AB into Euler angles gives
angles_BA =

  178.9396   -1.4222    4.9837

angles_AB =

 -178.8198   -1.3244    5.0105

I was thinking that angles_BA and angles_AB should be same. But, they are not.
Why there is a difference between angles_BA and angles_AB ??

REPLY [1 votes]: You have two isometric transformations, $A$ and $B$,
each of which is a combined translation and rotation.
Let's define some useful notation.
Define $T_{X,Y,Z}$ as the matrix for a translation by $X$ units in the $x$ direction,
$Y$ units in the $y$ direction, and $Z$ units in the $z$ direction.
Define $R_{x;\theta}$ as the matrix for a rotation by the angle $\theta$ around the $x$ axis; likewise $R_{y;\theta}$ and $R_{z;\theta}$ for rotations around the $y$ and $z$ axes, respectively.
Also, let's write our angles in radians.
With a little help from WolframAlpha, I think I have deduced that $A$ is actually the transformation whose matrix is
$$
M_A = T_{-0.0036,0.1235,-0.9213} R_{x;2.09819} R_{y;-0.008519} R_{z;-1.52068}.
$$
That is, first you rotate by $-1.52068$ radians around the $z$ axis;
then $-0.008519$ radians around the $y$ axis; then $2.09819$ around the $x$ axis;
and finally you translate by the vector $(-0.0036,0.1235,-0.9213)^T.$
Note that the matrix on the right is the one whose transformation is applied first, because you apply the transformation by putting any coordinates you want transformed in a column vector on the right side of the matrix $M_A,$
and when you expand $M_A$ into a product of component transformations like this the rightmost matrix is closest to the column vector and is the first to be multiplied with it.
We could also say that $A$ is a rotation by $2.40815$ radians ($137.977$ degrees) around the axis through the origin in the direction of the vector
$(0.674519, 0.638394, -0.370778)^T,$
followed by a translation by the vector $(-0.0036,0.1235,-0.9213)^T.$
Similarly, the matrix for $B$ is
$$
M_B = T_{-0.1241,-0.0112,-1.1028} R_{x;-1.01927} R_{y;0.0279253} R_{z;1.60745}.
$$
Now suppose we have a figure $F$ that is transformed by the rotation-translation $A$ into the figure $F_A$, whereas the rotation-translation $B$ transforms the figure $F$ into $F_B.$ Then the transformation that maps $F_B$ to $F_A$ is $B^{-1}$ followed by $A$, and the matrix of that transformation is $M_A M_B^{-1}$ (because, again, the matrix on the right is the matrix for the transformation that occurs first).
The matrix $M_B^{-1} M_A$ is something else altogether. I don't think it does what you think it does.
But since you are asking about a particular matrix you call $M_{BA} = M_B^{-1} M_A$, let's work with that matrix. This matrix works out to the following matrix product:
$$
M_{BA} = T_{-0.0882,-0.1114,0.2131} R_{x;3.12309} R_{y;-0.0248221} R_{z;0.086982}.
$$
Now you should expect that $M_{AB} = M_A^{-1} M_B$ is the inverse of $M_{BA},$
and indeed it is.
You can confirm this by multiplying the two matrices together.
But
$$
M_{AB} = T_{0.0830,-0.1230,0.2088} R_{x;-3.12099} R_{y;-0.0231151} R_{z;0.0874497}.
$$
As you observed, the angles do not match up in any obvious way.
The reason for mismatched angles is that
$$
\left(R_{x;3.12309} R_{y;-0.0248221} R_{z;0.086982}\right)^{-1}
\neq R_{x;3.12309}^{-1} R_{y;-0.0248221}^{-1} R_{z;0.086982}^{-1}.
$$
That is, you don't reverse a sequence of rotations around the $x$ axis, then the $y$ axis, then the $z$ axis by making a sequence of equal (or opposite) rotations around the $x$ axis, then the $y$ axis, then the $z$ axis.
If you want to re-use the angles, write
$$
\left(R_{x;3.12309} R_{y;-0.0248221} R_{z;0.086982}\right)^{-1}
 = R_{z;0.086982}^{-1} R_{y;-0.0248221}^{-1} R_{x;3.12309}^{-1}.
$$
That is, you can undo the sequence of rotations by exactly reversing the last rotation first, and then the second rotation, and then finally the first rotation.
But if you insist on rotating around the $x$ axis first both times, both for $M_{BA}$ and also for the inverse transformation $M_{AB},$ you need different sets of angles.
This will generally be true for all but the simplest cases.
Neither matrix multiplication nor transformations in three-D space are commutative in general; in most cases, it matters in what order you do them.
Notice that the components of the translation also don't match;
this is again because the transformations do not commute.
In most cases, if you want to reverse a rotation-and-then-translation using the inverse of the original translation, you have to apply the inverse translation first.


TITLE: How can one calculate the Möbius function $\mu(a_1,a_i)$ for all $i \in \{1, ..., 10\}$ of this poset?
QUESTION [1 upvotes]: I've seen this partially ordered set in our combinatorics script and it says that it is obvious how to calculate the möbius function $\mu(a_1,a_i)$ for all $i \in \{1, ..., 10\}$.
Here's the Hasse diagram of the Poset, but I don't know how to calculate the möbius function.

I know that the möbius function is multiplicative and that the sum of the Möbius function over all positive divisors of $n$ is  zero except when $n=1$. But that still doesn't help me.

REPLY [3 votes]: You are confusing two different (but related) meanings of the term Möbius function: the number-theoretic Möbius function and the poset-theoretic Möbius function.
The poset-theoretic Möbius function is defined recursively on interval $[x,y]$ of a poset as follows: $\mu([x,x]) = 1$ and when $x < y$,
$$
\mu([x,y]) = - \sum_{x \leq z < y} \mu([x,z]).
$$
One famous poset is the divisibility poset, in which the elements are the natural numbers (excluding zero), and $x \leq y$ if $x \mid y$ (i.e., if $x$ divides $y$). This poset is self-similar, in the sense that the subposet consisting of all elements above some $x$ is isomorphic to the entire poset, and for this reason $\mu([x,y])$ depends only on $y/x$, i.e., there is a function $\mu_{\mathbb{N}}$ such that $\mu([x,y]) = \mu_{\mathbb{N}}(y/x)$. This function is the number-theoretic Möbius function.


TITLE: Show that $\{E\cap B\mid B\ borel\}=\sigma (\{O\cap A\mid O\ open\}).$
QUESTION [0 upvotes]: I have a problem to show that $$\{E\cap B\mid B\ borel\}=\sigma (\{O\cap E\mid O\ open\}).$$
What I did is : Let $A\in \{E\cap B\mid B\ borel\}$. Then, $A=E\cap B$ for a certain borel $B$. Since a borelien is a (at most countable) union for open, we have that $B=\bigcup_{i\in\mathbb N}O_i$ where $O_i$ open. Therefore $A=\bigcup_{i\in\mathbb N}E\cap O_i\in \sigma (\{E\cap O\mid O\ open\}).$
For the converse inclusion, I wanted to do as following. Let $A\in \sigma (\{O\cap E\mid O\ open\})$. I thought that it mean that $A=\bigcup_{i\in\mathbb N}E\cap O_i$ for some $E\cap O_i$, but I heard that it doesn't mean this. So what does it mean ?
For example, I know that the field of borel set is the field generated by the open. Then all element of this field can be written as $\bigcup_{i=1}^\infty O_i$ where $O_i$ open, no ? But here isn't it the field generated by $O\cap E$ ? i.e. can be written as $\bigcup_{i=1}^\infty O_i\cap E$ ?

REPLY [1 votes]: To prove that $\{E\cap B\mid B\ borel\}=\sigma (\{O\cap A\mid O\cap E\}$ you must prove first that $\{E\cap B\mid B\ borel\}$ is indeed a field (otherwise inclusion or equality has no sense).
Then, if $\mathcal A$ is a set, the $\sigma (\mathcal A)$ is the field generated by $\mathcal A$. This doesn't mean that elements of $\sigma (\mathcal A)$ are countable union of element of $\mathcal A$ ! It mean that
1) $A^c\in \sigma (\mathcal A)$ whenever $A\in\mathcal A$.
2) $\emptyset$ and the set on which you defined your field is in $\sigma (\mathcal A)$
3) $\bigcup_{i=1}^\infty A_i\in \mathcal A$ for all $A_i\in \mathcal A$.
For the borel, it's not true that if $B$ borel, then $B=\bigcup_{i=1}^\infty O_i$ for opens $O_i$ (for example $B=\{0\}$ is borel which is not open). The only thing you can say it's that $\bigcup_{i=1}^\infty O_i$ for $O_i$ open is borel.
Let prove your claim
I think that $\mathcal A:=\{E\cap B\mid B\ borel\}$ is defined on $E$. It's clear that $E$ and $\emptyset$ are in $\mathcal A$ since $E=E\cap \mathbb R$ and $\emptyset=E\cap\emptyset$. Let $A\in \mathcal A$, i.e. there is $B$ borelien s.t. $A=E\cap B$. Then, $A^c=E^c\cup B^c.$
Remember, we are in $E$, then $E^c=\emptyset$ and thus $A^c=E\cap B^c$. Since $B^c$ is borel, $A^c$ in $\mathcal A$.
Finally, if $A_i=E\cap B_i$ for $i\in\mathbb N$, since $\bigcup_{i\in\mathbb N}B_i$ is borel, the claim follow.
The fact that $\sigma (\{O\cap E\mid O\ open\})\subset \{B\cap E\mid B\ borel\}$ is obvious since an open is borel. I let your do the last inclusion.


TITLE: Minimal polynomial for an invertible matrix and its determinant
QUESTION [2 upvotes]: So here's one that I can't quite crack:

Let $A\in M_n(\mathbb{F})$ be an invertible matrix with integer eigenvalues. Its minimal
  polynomial is $m_A(\lambda)=\lambda^k+b_{k-1}\lambda^{k-1}+...+b_0$. Prove that $detA$ is divisible by $b_0$.

I'm afraid I don't quite see the connection between the minimal polynomial and the determinant.
All I know is that for an invertible matrix $b_0 \neq 0$, but I can't find a way to relate that to the determinant.
Any tips and guidance would be much appreciated!
Thanks in advance.

REPLY [0 votes]: All roots of the minimal polynomial are eigenvalues, so here that (monic) polynomial is of the form $\prod_{i=1}^k(X-a_i)$ for some sequence $(a_1,\ldots,a_k)$ of integers, all eigenvalues, with maybe some repetitions. Then $b_0= \prod_{i=1}^k(-a_i)$. For the characteristic polynomial the situation is the same, but maybe with more repetitions of certain eigenvalues. The constant term then is an integer multiple of $b_0$, and on the other hand the constant term of the characteristic polynomial is $\det(-A)$. The result follows.


TITLE: Gradient of scalar function defined using the $\mbox{diag}$ operator
QUESTION [1 upvotes]: Let $f : \mathbb R^n \to \mathbb R$ be defined by
$$f(x) := \left( c - M \mbox{diag} (x) x \right)^\top \left( c - M \mbox{diag} (x) x \right)$$
where $k \times n$ matrix $M$ and $k$-vector $c$ are given. What is the derivative of $f$ with respect to $x$?
If I wanted to to find the $x$ that makes $\nabla f (x) = 0$, what would it be? Please note that $M$ is not square, and therefore, its inverse doesn't exist.

REPLY [3 votes]: For typing convenience, define the variables
$$\eqalign{
X &= {\rm Diag}(x) \\
y &= (MXx-c) \;&=\; M(x\odot x)-c \\
w &= M^Ty \\
}$$
where $\odot$ is the elementwise/Hadamard product.
Write the function in terms of these variables. Then find its differential and gradient.
$$\eqalign{
f &= y:y \\
df &= 2y:dy \\
 &= 2y:M(2x\odot dx) \\
 &= 4M^Ty:(x\odot dx) \\
 &= (4x\odot w):dx \\
\frac{\partial f}{\partial x}
 &= (4x\odot w) \\
 &= 4XM^Ty \\
 &= 4XM^T(MXx-c) \\
}$$
In some of the steps above, a colon is used to denote the trace/Frobenius product, i.e.
$$\eqalign{
A:B &= {\rm Tr}(A^TB)
}$$
The properties of the trace allow terms such products to be rearranged in many different ways.
$$\eqalign{
A:B &= B:A \;=\; B^T:A^T \\
A:BC &= B^TA:C \;=\; AC^T:B \\
}$$
Update
Set the gradient to zero and solve for $x$.
$$\eqalign{
M^Ty &= 0 \\
M^TM(x\odot x) &= M^Tc \\
x &= \Big(M^+c + (I-M^+M)\,a\Big)^{1/2} \\
}$$
where $M^+$ is the pseudoinverse and the square root function is applied element-wise.
The $a$-vector is arbitrary and can be used to eliminate negative elements before taking the square root.
A second (trivial) solution is $\,x=0$.