TITLE: When do the eigenkets of an operator form a(n) (orthogonal) basis for the Hilbert space?
QUESTION [2 upvotes]: When do the eigenkets of an operator form a(n) (orthogonal) basis for the Hilbert space? Is it always the case when the operator is Hermitian? Does the operator need to be Hermitian?

REPLY [2 votes]: Does the operator need to be Hermitian?

No, the operator doesn't need to be Hermitian. Here is an example.

Is it always the case when the operator is Hermitian?

No, the operator also needs to be compact. In the finite case, however, you don't need this extra hypothesis.

When do the eigenkets of an operator form a basis for the Hilbert space?
When is this basis orthogonal?

In general, the Spectral Theorem (at least, the version useful to the study of Hilbert spaces in quantum mechanics) tells us that if an operator is compact and normal, its eigenkets will form an orthonormal basis for the Hilbert space (see Kowalski's Spectral Theory, p. 20). I don't know if one could find a different version of the Spectral Theorem, with weaker hypotheses, that doesn't give you orthonormality, but I can't see why that would be useful.


text:
\section{Open Projection and Closed Graph Implies Quotient is Hausdorff}
Tags: Quotient Spaces

\begin{theorem}
Let $\mathcal R\subset X\times X$ be an [[Definition:Equivalence Relation|equivalence relation]] on a [[Definition:Topological Space|topological space]] $X$.
Let $X/\mathcal R$ be the [[Definition:Quotient Topology/Quotient Space|quotient space]].
Let $p$ denote the [[Definition:Quotient Mapping|quotient mapping]].
Let:
:$\mathcal R$ be [[Definition:Closed Set (Topology)|closed]] in $X\times X$
:$p$ be [[Definition:Open Mapping|open]]
Then $X/\mathcal R$ is [[Definition:Hausdorff Space|Hausdorff]].
\end{theorem}

config: wiki


TITLE: A little help with $p$-group, normal series, trivial action on factor groups.
QUESTION [3 upvotes]: Here is what I assume:
$P$ is a $p$-group and there is a series of subgroups $P_0\unlhd P_1\unlhd \cdots\unlhd P_m = P$ such that $P_i\unlhd P$ for each $0\le i\le m$ and $P_0\le \Phi(P)$. We also have $G\le\text{Aut}(P)$ such that $G$ normalizes each $P_i$. Let $H\le G$ be the subgroup of those $\alpha\in G$ that acts trivially on $P_i/P_{i-1}$ for each $1\le i \le m$.
We note that there is a normal series of $P/\Phi(P)$:
$$1 = P_0\Phi(P)/\Phi(P) \unlhd P_1\Phi(P)/\Phi(P) \unlhd \cdots \unlhd P_m\Phi(P)/\Phi(P) = P/\Phi(P).$$
And here is what I want to show:

that $H/C_H(P/\Phi(P))$ normalizes $P_i\Phi(P)/\Phi(P)$ for each $i$ and
that $H/C_H(P/\Phi(P))$ acts trivially on $(P_{i+1}\Phi(P)/\Phi(P))/(P_i\Phi(P)/\Phi(P)) \cong P_{i+1}\Phi(P)/P_i\Phi(P)$ for each $i$.

I think it should be obvious, and I get why $H/C_H(P/\Phi(P))$ normalizes $P_i\Phi(P)/\Phi(P)$ since $H$ acts on $P/\Phi(P)$ and so $H/C_H(P/\Phi(P))$ acts on $P_i\Phi(P)/\Phi(P)$ via
$$xy\Phi(P) \stackrel{\alpha C_H(P/\Phi(P))}{\longmapsto} (x\alpha)(y\alpha)(\Phi(P)\alpha) \in P_i \Phi(P)/\Phi(P),$$
because $x\in P_i$ which is normalized by $\alpha\in H$ and $y\in \Phi(P)$ is normalized by $H$.
But I can't see why $H/C_H(P/\Phi(P))$ acts trivially on $P_{i+1}\Phi(P)/P_i\Phi(P)$... Can someone help?

REPLY [1 votes]: I'll write $x^\alpha$ instead of $x\alpha$ so that my holomorphs are multiplicative (you may be writing $P/\Phi(P)$ as row vectors, thinking more additively).
Acting trivially ($\alpha$ on $P_i/P_{i-1}$) means $[x,\alpha] := x^{-1} x^\alpha \in P_{i-1}$ for every $x \in P_i$. Normalizing ($\alpha$ on $P_i$) means $[x,\alpha] \in P_i$ for every $x \in P_i$.
Now $\alpha$ acts trivially on $P_i\Phi(P)/P_{i-1}\Phi(P)$ since $[x, \alpha ] \in P_{i-1}$ for every $x \in P_{i-1}$ and $[y,\alpha] \in \Phi(P)$ for every $y \in \Phi(P)$.
Then just use that $[xy,\alpha] = [x,\alpha][[x,\alpha],y][y,\alpha] \in P_{i-1} P_{i-1} \Phi(P)$ since $y$ (and all of $P$) normalizes $P_{i-1}$.


TITLE: Find all positive integers k and l such that $3^k - 2^l = 1$
QUESTION [5 upvotes]: Possible Duplicate:
$|2^x-3^y|=1$ has only three natural pairs as solutions

As the title says:
Find all positive integers k and l such that $3^k-2^l=1$
In previous questions it is proved that $2^l+1$ is divisible by $27$ iff it is divisible by $19$, though I'm not sure how that is meant to help.
I've brute forced it, and got that $k = l = 1$ works, as does $k = 2$ and $l = 3$, but I can't figure out how to prove that these are the only solutions.
Any help would be  much appreciated

REPLY [2 votes]: If by "iff" you mean "if and only if" (just to be sure, I didn't learn maths with english) then your problem is almost solved :
take your original equation, and pass $2^l$ to the other side of the equal.
$3^k$ and $2^l +1$ are equal if they have the same prime dividers.
What are the prime divider of $3^k$? Only 3.
What are the prime divider of $27$? Only 3.
So you can use your previous questions to find other possibility :
$2^l + 1$ must be a multiple of 19, and must be an odd number.
How many solutions of this sub-question can you find ?
Once you have them it should be easy to find the corresponding value for $k$.


TITLE: Sum of cells on infinite board is even
QUESTION [7 upvotes]: Let $a,b,c$ be pairwise relatively prime positive integers. In an infinite checker board (infinite in all directions), each cell contains an integer. The sum of the integers in any $a\times a$ square is even, in any $b\times b$ square is even, and in any $c\times c$ square also even. Does it always follow that all numbers on the board are even?
If $a=1$ then all the numbers must be even. For higher $a,b,c$, we probably have to take overlapping squares of sizes $a,b,c$ to deduce that some cells are even. But it is not clear which ones.

REPLY [2 votes]: Suppose that we put a light under each cell in this infinite grid, all of the lights starting off. We can, at will, switch all the state of all the lights in any $a\times a$, $b\times b$, or $c\times c$ square - that is, any light in this square that was on is turned off, and any light that was off is turned on. So, by choosing appropriate squares in succession, we may try to obtain various complex patterns of cells. However, what is of note here, is that the sum of the values in the lighted squares is always even, since, working in $\mathbb{Z}/\mathbb{2Z}$ - that is, considering only the parity of values - adding a value is the same as subtracting it, so when we flip all the lights in a square, the change in parity is the same regardless of whether lights were flipped on or off.
Now, if we can use this process to produce a lighted $1\times 1$ square, we win, since this implies that the sum of the lighted squares - of which there is but one - is even, and hence that square is even. To do this, notice that by switching $b$ side-by-side $a\times a$ squares, we could create a $ab\times a$ rectangle of lighted points. Similarly, we can create a $ab\times b$ rectangle by switching $a$ side-by-side $b\times b$ squares. Suppose we overlayed these such that two of their corners matched up and one was within the other - now we have a $ab\times|b-a|$ rectangle, since we basically lighted the bigger rectangle, then switched off lights in the smaller rectangle, but they had the same width, and hence yielded a rectangle. If we stacked one rectangle atop the other, we would have an $ab\times a+b$ rectangle. By similar reasoning, we can construct an $ab\times |k_1a + k_2b|$ rectangle for any $k_1,k_2\in \mathbb{Z}$. Since $a$ and $b$ are coprime, there exists a pair of integers $k_1$ and $k_2$ such that $k_1a+k_2b=1$, thus, by layering a lot of $a\times a$ and $b\times b$ squares, we get a $ab\times 1$ rectangle. Similarly, we may construct $bc\times 1$ and $ca\times 1$ rectangles. Then, when we layer these, we can get any rectangle expressible as, for $k_1,k_2,k_3\in\mathbb{Z}$:
$$(k_1ab + k_2bc + k_3ca)\times 1$$
and since $\gcd(ab,bc,ca)=1$, there exist $k_1,k_2,k_3$ such that the above simplifies to
$$1\times 1$$
implying that we can, by switching lights this way, yield a $1\times 1$ lighted square which must contain an even number. By translating this solution around, we can prove this of every square.


TITLE: Elementary Proof of Riemann-Roch for Compact Riemann Surfaces
QUESTION [28 upvotes]: I am supposed to give a talk about the Riemann-Roch theorem to a seminar of first and second year graduate students. I want to do Riemann-Roch for compact Riemann surfaces, but I am open to perhaps doing the version for projective curves.
I assume the crowd knows little algebraic geometry. I assume however, knowledge of elementary differential geometry, sheaves, cohomology and complex analysis.
I am looking for an elementary proof (especially because I want time to be able to work out some examples). Any references?

REPLY [2 votes]: Here is one that is not elementary.  Joe Polchinski mentions a derivation of Riemann-Roch via Feynman Path integrals.  Unfortunately most people don't know what "ghosts" are and try to do String Theory without them.
https://physics.stackexchange.com/questions/110322/number-of-zero-modes-on-the-sphere
It is worked out in Chapter 5 of Polchinski's String Theory Vol 1 - he is trying to talk about the Moduli space of Riemann Surfaces


TITLE: Estimate password entropy by "trying out" passwords
QUESTION [0 upvotes]: The entropy of a password of a fixed length $n$ and $c$ possible characters is calculated by $n*log_2(c)= log_2(c^n)$, see also here:
https://ritcyberselfdefense.wordpress.com/2011/09/24/how-to-calculate-password-entropy/
Assuming that I have a kind of "blackbox" that has unknown requirements on a password, especially like:
Min occurences of a certain group of characters, different possible characters for different character positions, etc.
I can give this blackbox a password that I generated and ask if it is an accepted one or not.
Is it possible to estimate the entropy of the "room" of available passwords by generating an amount of random passwords (lets say 1 million) and see how many have been accepted? What I do know of the room of available passwords is which characters may be used, so I only have to try passwords with these characters, not with the whole UTF-8 table.
From this ratio $r$ of tried and accepted password, I can calculate the entropy with a formular like this:
$e_{estimated} = log_2(r*c^n)$
From my tests this formular works quote well for an estimation of the entropy.
I am looking for another formular that can tell me how many passwords I have to try to make an assumtion like this:
With a probability of $p$, $|e_{actual} - e_{estimated}| < epsilon$
Is something like this even possible?

REPLY [1 votes]: Yes, this is entirely possible.  As long as your test passwords are randomly distributed in the space, you will get the measure you are seeking.  The hard part comes if the requirements on passwords allow most or very few of them to pass.  You will detect that, but will not get a good measure.
As an example, let us assume a character set of $26$ upper case letters, $26$ lower case letters, $10$ numbers and $10$ symbols, for a total of $62$ characters, and passwords $12$ characters long.  If the requirement is just one symbol or number, there are $62^{12}\approx 3.23 \cdot 10^{21}$ character strings, of which $62^{12}-52^{12}\approx 2.84 \cdot 10^{21}$ are valid passwords.  That is about $90\%$ valid, and your sampling will work well.  If we allowed all passwords, your sampling would show that but you might worry that since you only sampled a tiny fraction of the space there are some invalid ones out there.
To estimate the error, you can use the binomial distribution.  If you do $N$ samples and the fraction of valid passwords is $p$, the standard deviation of the number of valid ones found is $\sqrt{Np(1-p)}$  This is valid when $N$ is large and $p, 1-p$ are not too close to zero.  Since $\sqrt {p(1-p}$ has a maximum of $1/2$, you can say the standard deviation of the fraction of valid passwords is less than $2/\sqrt N$


TITLE: Continuously differentiable interpolation
QUESTION [1 upvotes]: I have real values $y_i$ given on uniform grid. I want to build interpolating function $f(x)$ such that:

$f(x) = y_i$, when $x=i$,
$f$ is continuously differentiable.

Instead of using famous cubic-splines, I would like to find a technique meeting the following requirement:
$f$ is linear in $y_i$ values and depends only on $y_j$ where $j \le x$, i.e. has form $$f(x) = \sum_{j=1}^{\lfloor x\rfloor} a_j\left(x\right) \cdot y_j$$

REPLY [1 votes]: You can certainly try Lagrange interpolation polynomial. It's polynomial therefore continuously differentiable.


TITLE: Resistance of an object with arbitrary shape
QUESTION [3 upvotes]: Suppose to have a conductor with a non-trivial geometry, like the one in the picture:

The shape does not really matter for this question, as long as you suppose to have at least one "hole" in the $z-x$ plane and the sectional area is not constant along the $y$ direction.
I want to calculate the effective resistance of this conductor, that can be supposed to be homogeneous with conductivity $\sigma$, between the two extreme points on the $y$ axis.
Normally, to calculate the resistance of a material, I would proceed in the following way:

Solve numerically the Laplace equation $\nabla^2V=0$ with boundary conditions:

$V(x,y=0)=1$ and $V(x,y=L)=0$
$\nabla V \cdot \hat n=0$ at every other boundary

Integrate the Ohm's law
$$ I=\int \mathbf J \cdot d\mathbf S = \int \sigma \mathbf E\cdot d\mathbf S =-\int \sigma \nabla V \cdot d\mathbf S = \Delta V/R$$
Solve with respect to $R$

If the section $A$ was constant this algorithm would give you the well-known formula $R=\rho\frac{L}{A}$, but it's clear that in this case is not appliable since the section is different at different $y$ points.
How is then possible to calculate $R$?
Without any holes, I think the formula
$$R=\int_0^LdR=\int_0^L\rho\frac{dy}{A(y)}$$
should work, but I have the feeling that if I have a bifurcation things become more complicated.

REPLY [1 votes]: Using a numerical model of current flow in a conductor with such a geometry, we can calculate the resistance. The Laplace equation is solved, with the boundary conditions formulated by the author. It will be enough to calculate the total current in the initial and in the final section (for comparison). In fig. The distribution of potential and current density is shown at $\sigma =1$. In this case $I=-\int {\sigma \nabla V \vec {dS}} =0.133\sigma \delta$, $\delta $ - is thickness.


TITLE: Working backwards with Venn Diagrams
QUESTION [0 upvotes]: Each of the 30 students in a class plays at least one of squash, hockey and tennis.
18 students play squash
19 students play hockey
17 students play tennis
8 students play squash and hockey
9 students play hockey and tennis
11 students play squash and tennis
Find the number of students who play all three sports.

I've tried working backwards, putting $x$ in the middle, then $8-x$, $9-x$ and $11-x$ further outwards, but I can't seem to deduce the outermost circles. I wonder what I'm missing?

REPLY [1 votes]: While your approach would work for two sets, it does not work for three sets.
Consider the following diagram.

Suppose we wish to count $|A \cup B \cup C|$.  If we simply add the number of elements in each set, we will count each element that is in two sets twice, once for each set to which it belongs.  Since we only want to count such elements once, we must subtract the number of elements that are in two sets from the total.  However, if we do so, we count each element that is all three sets three times when we add the number of elements that are in each set, once for each set to which it belongs, then subtract it three times when we subtract the number of elements that are in two sets, once for each of the $\binom{3}{2} = 3$ pairs of sets to which it belongs.  Therefore, we have not counted such elements at all.  We want to count them once, so we add them to the total.  Doing so yields
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$
This is the Inclusion-Exclusion Principle for three sets.
Let $S$ be the set of students who play squash, $H$ be the set of students who play hockey, and $T$ be the set of students who play tennis.  We are given
\begin{align*}
|S \cup H \cup T| & = 30\\
|S| & = 18\\
|H| & = 19\\
|T| & = 17\\
|S \cap H| & = 8\\
|S \cap T| & = 11\\
|H \cap T| & = 9
\end{align*}
You wish to find $|S \cap H \cap T|$, which you can determine using the equation above by setting $A = S$, $B = H$, and $C = T$.


TITLE: Are all pseudovectors in 3D cross products of vectors?
QUESTION [1 upvotes]: I have been taught that all cross-products of two vectors in 3D are pseudovectors because they don't change direction under a parity transformation. But, are must all pseudovectors be cross products of vectors or can do pseudovectors that can't be written as cross products exist?

REPLY [0 votes]: "can [do] pseudovectors that can't be written as cross products exist" needs clear definition.  If I have a pseudovector $\vec a$ I can complete an orthogonal triad with $\vec b$ and $\vec c$, then choose the lengths of $\vec b$ and $\vec c$ so $b \times \vec c=\vec a$.  I don't think that answers your question.  Another way to get a pseudovector is to multiply a vector by a pseudoscalar, but that just pushes the issue down the line.  Where do we get a pseudoscalar?  One way is by the triple product of three vectors, but that involves a cross product.  I can certainly define an object $\vec A$ to be a pseudovector and have certain components in a particular reference system.  Can that be written as a cross product by the process I described?


text:
\begin{document}

\maketitle

\begin{abstract}
  We consider the rational subset membership problem for
  Baumslag-Solitar groups. These groups form a prominent class
  in the area of algorithmic group theory, and they were recently
  identified as an obstacle for understanding the rational subsets of
  $\GL(2,\Q)$.

  We show that rational subset membership for Baumslag-Solitar groups $\BS(1,q)$
  with $q\ge 2$ is decidable and $\PSPACE$-complete. To this end, we introduce a
  word representation of the elements of $\BS(1,q)$: their pointed expansion
  (PE), an annotated \(q\)-ary expansion.  Seeing subsets of \(\BS(1,q)\) as word
  languages, this leads to a natural notion of PE-regular subsets of
  \(\BS(1, q)\): these are the subsets of \(\BS(1,q)\) whose sets of PE are regular
  languages.  Our proof shows that every rational subset of $\BS(1,q)$ is
  PE-regular.

  Since the class of PE-regular subsets of $\BS(1,q)$ is well-equipped
  with closure properties, we obtain further applications of these
  results. Our results imply that (i)~emptiness of Boolean
  combinations of rational subsets is decidable, (ii)~membership to
  each fixed rational subset of $\BS(1,q)$ is decidable in logarithmic
  space, and (iii)~it is decidable whether a given rational subset is
  recognizable. In particular, it is decidable whether a given
  finitely generated subgroup of $\BS(1,q)$ has finite index.
\end{abstract}

\iflongversion
  \makeatletter
  \newpage
  \pagenumbering{gobble}
  \vskip0.7\bigskipamount
  \noindent
  \rlap{\color{lipicsLineGray}\vrule\@width\textwidth\@height1\p@}
  \hspace*{7mm}\fboxsep1.5mm\colorbox[rgb]{1,1,1}{\raisebox{-0.4ex}{
    \large\selectfont\sffamily\bfseries Contents}}
  \setcounter{tocdepth}{2}
  \setlength{\cftbeforesecskip}{0em}
  \vskip3pt

  {\renewcommand{\familydefault}{\sfdefault}\sffamily
    \@starttoc{toc}}
  \makeatother
\fi

\newpage
\pagenumbering{arabic}
\setcounter{page}{1}

\section{Introduction}
\input{intro}
\section{Basic notions}\label{sec:prelim}
\input{prelims}
\section{Main results}\label{results}
\input{results}

\input{closure-properties}

\section{Every rational subset of BS(1,\,\emph{q}) is effectively PE-regular}\label{rational-to-regular}

\input{rational-to-regular}

\section{Complexity}\label{complexity}
\input{complexity}

\section{Recognizability}\label{recognizability}
\input{recognizability}

\bibliographystyle{plainurl}
\bibliography{bibliography}

\iflongversion\else
  \appendix
  \section{Missing proofs from \cref{results}}\label{appendix-results}
  \input{appendix-results}
  \section{Missing proofs from \cref{rational-to-regular}}\label{appendix-rational-to-regular}
  \input{appendix-rational-to-regular}
  \section{Missing proofs from \cref{complexity}}\label{appendix-complexity}
  \input{appendix-complexity}

  \section{Missing proofs from \cref{recognizability}}\label{appendix-recognizability}
  \input{appendix-recognizability}

\fi

\end{document}

config: arxiv


TITLE: Prove or disprove f is contractant
QUESTION [0 upvotes]: Let $(E,\|.\|)$ is a normed vector space, $A\in E$ such that $A$ is compact. Let $f:A\to A$ such that $$\forall(x,y)\in A, x\neq y \Rightarrow \|f(x)-f(y)\| <\|x-y\|$$
  Is $f$ contractant?

As I know, a function $g$ is contractant iff there exist $k\in (o,1)$ such that $\|g(x)-g(y)\| \le k\|x-y\|$. But I can't find a such $k$ that makes $f$ contractant. Can we conclude that $f$ is not contractant?

REPLY [1 votes]: HINT take $f(x)=x^2/2$ on $[0,1]$  not a contraction


TITLE: solution of differential equation of the form f(x,y)/g(x,y)
QUESTION [2 upvotes]: If I'm given a differential equation of the form,
$\frac{dy}{dx} = \frac{a_1x+b_1y+c_1}{a_2x+b_2y+c_2}$
that apparently can't be homogenized, will the differential equation always be solvable?
For example, if I'm given the equation,
$\frac{dy}{dx} = \frac{x+2y-3}{2x+y-3}$
How am I supposed to solve it?
N.B. This isn't a homework question. I'm just curious whether this type of equations are solvable or not.

REPLY [1 votes]: $$\frac{\mathrm d y}{\mathrm d x}=\frac{ax+by+c}{k(ax+by)+d}=\frac{ax+by+c}{k(ax+by+C)}$$
with $C=\frac{d}{k}$ is solvable with the change of function :
$$Y(x)=ax+by+C \quad\to\quad y=\frac{Y-ax-C}{b}$$
$$\frac{\mathrm d Y}{\mathrm d x}-a=\frac{Y-C+c}{kY}=$$
$$\frac{\mathrm d Y}{\mathrm d x}=\frac{(1+ak)Y-C+c}{kY}$$
This is a separable ODE.
$$x=\int \frac{kY}{(1+ak)Y-C+c}=k\frac{(1+ak)Y+(c-C)\ln|(1+ak)Y-C+c|}{(1+ak)^2}+\text{ constant}$$
The inverse function $Y(x)$ involves the Lambert's W function.


TITLE: Characterization of finite VC-dimension
QUESTION [1 upvotes]: I have heard the following claim (which I hope to repeat correctly)

A graph $E\subseteq U\times V$ has finite VC-dimension if and only if there is a largest $n$ such that all graphs $G\subseteq X\times Y$ with $|X|,|Y|<n$ can be embedded in $E\subseteq U\times V$.

I forgot where I heard it. No proof or reference was given.

REPLY [2 votes]: First let me make sure that we agree about what it means for a bipartite graph $E \subseteq U\times V$ to have finite VC-dimension. It'll be useful to fix some notation.
For $v\in V$, let $E_v = \{u\in U\mid uEv\}$. Let's say $E$ is extensional if $E_v = E_{v'}$ implies $v = v'$.
For $A\subseteq U$, we say $E$ shatters $A$ if for all $B\subseteq A$ there exists $v_B\in V$ such that $B = A\cap E_{v_B}$. We say $E$ has finite VC-dimension if there is some $n\in \omega$ such that no subset of $U$ of size $n$ is shattered by $E$. Otherwise, $E$ has infinite VC-dimension.
Next let me point out that for a bipartite graph $E\subseteq U\times V$,  "there is a largest $n$ such that all bipartite graphs $G\subseteq X\times Y$ with $|X|,|Y|<n$ can be embedded in $E$" is equivalent to the simpler statement "there is some finite bipartite graph which cannot be embedded in $E$".
So we want to show that $E$ has finite VC-dimension if and only if there is some finite bipartite graph which cannot be embedded in $E$. Equivalently, $E$ has infinite VC-dimension if and only if every finite bipartite graph can be embedded in $E$.
This is actually pretty straightforward, up to a wrinkle about extensionality.
$(\Leftarrow)$: Suppose every finite bipartite graph can be embedded in $E$. Let $n\in \omega$. Let $A$ be a set of size $n$, and consider the bipartite graph $G\subseteq A\times \mathcal{P}(A)$, with $G = \{(a,B)\mid a\in B\}$. Then there is an embedding of $G$ into $E$, i.e., injective functions $f\colon A\to U$ and $g\colon \mathcal{P}(A)\to V$ such that $aGB$ if and only if $f(a)Eg(B)$. Now $E$ shatters $f(A)$, since for $B\subseteq f(A)$, $f(A)\cap E_{g(f^{-1}(B))} = B$. Since $E$ shatters a set of every finite size, $E$ has infinite VC-dimension.
$(\Rightarrow)$: Suppose $E$ has infinite VC-dimension. Let $G\subseteq X\times Y$ be a finite bipartite graph. Note that we can extend $G$ to a finite extensional bipartite graph in the following way: For each $y\in Y$, add a new element $x_y$ to $X$, which is related by $E$ only to $y$. So we may assume $G$ is extensional. Let $n = |X|$. Since $E$ has infinite VC-dimension, there is some set $A\subseteq U$ of size $n$ which is shattered by $E$. Let $f\colon X\to A$ be any bijection. Now for each $y\in Y$, there is some $v_y\in V$ such that $E_{v_y}\cap A = f(G_y)$. Defining $g(y) = v_y$ (which is one-to-one because $G$ is extensional), the maps $f\colon X\to U$ and $g\colon Y\to V$ gives an embedding of $G$ into $E$.


TITLE: integrating an expression with alomst quadratic denominator including Chebyshev polynomials of the first kind
QUESTION [1 upvotes]: As a part of my research (in array processing - the specifics are not too exciting :-)), I cant resolve one specific integral.
Assume $r\in\left[0 ,1\right]$, $N\in\mathbb{N}$.
The basic form  is
$$
\int_{\cos{(x)}=-1}^{\cos{(x)}=1}{
\frac{
1-\cos{\left(Nx\right)}
}{
N^{2}\left(1-\cos{(x)}\right)
+r^{2}\left(1-\cos{\left(Nx\right)}\right)
-Nr\left(1-\cos{(x)}-\cos{\left(Nx\right)}+\cos{\left(\left(N-1\right)x\right)}\right)
}
dx
}.
$$
Searching for hints, I came across the very informative "How to expand $\cos{(nx)}$ with $\cos{(x)}$?" discussion which lead me to investigate the expression using Chebyshev polynomials of the first kind, in light of the fact that $\cos(nu)=T_n(\cos(u)),$ but still no luck.
Anyhow, as can be seen in the wikipedia page (Chebyshev polynomials ),
$$
T_n(x)= \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} (x^2-1)^k x^{n-2k},
$$
and plugging it into the basic integral results in
$$
\int_{-1}^{1}{
\frac{
1-T_N(x)
}{
N^{2}\left(1-x\right)
+r^{2}\left(1-T_N(x)\right)
-Nr\left(1-x-T_N(x)+T_{N-1}(x)\right)
}
\frac{-1}{\sqrt{1-x^{2}}}
dx
}.
$$
Considering also the Chebyshev polynomials of the second kind,
$$
U_{N}\left(x\right)=\frac{\left(x+\sqrt{x^{2}-1}\right)^{N+1}-\left(x-\sqrt{x^{2}-1}\right)^{N+1}}{2\sqrt{x^{2}-1}},
$$
and the equality
$$
T_{N+1}(x) = xT_{N}(x)-\left(1-x^{2}\right)U_{N-1}(x)
$$
results in
$$
\int_{-1}^{1}{
\frac{
1-T_N(x)
}{
N^{2}\left(1-x\right)
+r^{2}\left(1-T_N(x)\right)
-Nr
\left(
1-x+\sqrt{1-x^{2}}
\left(\left(x+\sqrt{x^{2}-1}\right)^{N}-\left(x-\sqrt{x^{2}-1}\right)^{N}\right)
\right)
}
\frac{-1}{\sqrt{1-x^{2}}}
dx
},
$$
which has (as the headline states) "almost" quadratic form of the denominator.
This is where I am stuck and if someone has an idea for solving it I will be thrilled.
Thank you.

REPLY [1 votes]: A numerically achieved analytical answer:
sweeping many $[N,r]$ sets in MATHEMATICA, revealed that the finite integral (i.e. integration from $x=0$ to $x=2\pi$) can be expressed as $$ \int_{0}^{2\pi}(...) = \frac{2\pi}{r^{2}-\left(N-1\right)r+N} $$ which is very nice and perfectly fits the fact that for $r=0$ it should be equal to $2\pi/N$.
Now that I have the answer, should someone have an idea for analytical way of solving the integral, I will be very glad to hear about it.
Thanks
Itay.


TITLE: Sample Size Estimation with unknown variance
QUESTION [0 upvotes]: After spending a lot of time I'm still nowhere.
What I have:
Let d denote the desired margin of error so that the interval for µ is of width 2d. Let (1 − α)
denote the probability associated with the margin of error. Then
$(\frac{z_{α/2}σ}{d})^2$
Using the estimator $X∼N(θ, θ(1 − θ)/n)$
Do I simply plug this into $(\frac{z_{α/2}σ}{d})^2$ ?
2nd Question. What happens to n if there is no idea about the value of $θ$?

REPLY [0 votes]: Yes, if you mean what I think you mean. Your work was a little hard for me to follow. This is how I would do it:
$$P(|\theta-\hat\theta|<d|) = P(|X-\hat X|< nd) = P\left(\frac{|X-\hat X|}{\sigma_x} < \frac{nd}{\sigma_x}\right) < z_{\alpha/2}$$
where $n\theta = \hat X$ and $n\hat\theta = X$.

$$z_{\alpha/2} = \frac{nd}{\sigma_x}$$
Now $\sigma_x^2 \approx n\theta(1-\theta)$, so
$$z_{\alpha/2} = \frac{\sqrt{n_{min}}d}{\sqrt{\theta(1-\theta)}}$$
$$\sqrt{n_{min}} = \sqrt{\theta(1-\theta)}\frac{z_{\alpha/2}}{d}$$
$$n \geq n_{min} = \theta(1-\theta)\left(\frac{z_{\alpha/2}}{d}\right)^2$$

You have to do something to get information about the value of $\theta$. Take a preliminary sample, estimate it based on preexisting data, or make a guess.


TITLE: $(a\vec{x}+b\vec{v})$ and $(b\vec{x}+a\vec{v})$ are orthogonal. How would you show that $\vec{x}=\vec{0}=\vec{v}$
QUESTION [0 upvotes]: Suppose that $\vec{x}$, $\vec{v}$ ∈ $\Bbb{R^2}$ are vectors such that for every choice of scalars $a, b ∈ \Bbb{R}$, the vectors $(a\vec{x}+b\vec{v})$
and $(b\vec{x}+a\vec{v})$ are orthogonal. How would you show that $\vec{x}=\vec{0}=\vec{v}$
I did the dot product of both vectors, and expanded but i have reached a point where im stuck

REPLY [0 votes]: Let $f(a,b)=(a\vec x+b\vec v)\cdot(b\vec x+a\vec v)=0$
We have forall $a,b$ that $\quad f(a,b)-f(a,-b)=2ab\left(\lVert\vec x\lVert^2+\lVert\vec v\lVert^2\right)=0\iff \vec x=\vec v=\vec 0$