TITLE: Integrate $\int \frac {dx}{\sqrt {(x-a)(x-b)}}$ where $b>a$
QUESTION [3 upvotes]: Integrate: $\displaystyle\int \dfrac {dx}{\sqrt { (x-a)(x-b)}}$ where $b>a$
My Attempt:
$$\int \dfrac {dx}{\sqrt {(x-a)(x-b)}}$$
Put $x-a=t^2$
$$dx=2t\,dt$$
Now,
\begin{align}
&=\int \dfrac {2t\,dt}{\sqrt {t^2(a+t^2-b)}}\\
&=\int \dfrac {2\,dt}{\sqrt {a-b+t^2}}
\end{align}

REPLY [1 votes]: Proceeding further from where you left
$$
\int \dfrac {2\,}{\sqrt {a-b+t^2}}\ dt
$$
$$
\int \dfrac {2}{\sqrt {(t)^2 + (\sqrt{a-b}) ^2}}\ dt
$$
Using
$$
\int \frac{1}{\sqrt{x^2 + a ^ 2}} = \log({x+\sqrt{x^2+a^2}})
$$
It becomes
$$
2 \cdot {\log (t+\sqrt{t^2 + (\sqrt{a-b}) ^2})}
$$
Then substitute back the value of t .
And you get the required result .


TITLE: Fining the sum of a series .
QUESTION [2 upvotes]: I'm solving a probability problem and the expected value of a random variable is this series I need some hint to find the sum of it.
$\displaystyle \sum_{n=1}^{\infty}\frac{n}{2^n}$

REPLY [1 votes]: hint
For $x\in(-1,1)$,  we have
$$x+2x^2+3x^3+...=x(1+2x+3x^2+...)$$
$$=x\frac{d(x+x^2+x^3+...)}{dx}$$
$$=\frac{x}{1-x}+\frac{x^2}{(1-x)^2}$$
Now, you choose the right $x$.


TITLE: Closed but not rational points of a real cubic
QUESTION [5 upvotes]: In Mumford's Red Book of Varieties and Schemes, page 102, he gave the example of the closed but not rational points (that is to say points having residue field the complex field and not the real field) of the cubic $y^2=x^3−x$ on the real field : I have some difficulty to recover by elementary methods the figure he traced.
Especially, he seems to imply that these closed points formed the region $y^2>x^3−x$ in the real plane (which looks like the cylinder he pictured in the projective plane). Can somebody give me a simple explanation ? (I suppose the maximal ideals of the spectrum of the algebra defined by the cubic have to be parametrized the right way ?)

REPLY [12 votes]: I don't know what Mumford had in mind, but here (in some detail) is a down-to-earth way to topologically identify this space with a cylinder.
Let $C$ be our projective cubic curve with affine equation $y^2=x^3-x$.  We're considering complex conjugate pairs of points on $C$, that is, pairs $\{(x,y), (\bar x,\bar y)\}$ of solutions of $y^2=x^3-x$.  While those points are not real, the line joining them is real: there are real numbers $a,b,c$, not all zero, such that the line $l_{a,b,c}: aX + bY + c = 0$ passes through $(x,y)$ and $(\bar x, \bar y)$, and the coefficient vector $(a,b,c)$ is determined uniquely up to multiplication by a nonzero scalar.  That is, $(a:b:c)$ is a well-defined point in the "dual projective plane" ${\bf P}^*$ of lines on the projective plane with coordinates $(x:y:1)$ where $C$ lives.  Now these points $(x,y)$ and $(\bar x, \bar y)$ are on $l_{a,b,c} \cap C$, which contains three points in all, so there is a third point $(x_0,y_0) =: p_0$, necessarily real.  Conversely, any line $l$ meets $C$ in at least one real point, and if there is only one such point (and $l$ is not tangent to $C$ at that point) then the other two points of $l \cap C$ constitute a closed-but-not-rational point of $C$.
That is,

the space we're looking for is homeomorphic with the subset, call it $S$, of ${\bf P}^*$ consisting of lines whose real intersection with $C$, with multiplicity, has size $1$

as opposed to size $3$.
One way to describe $S$ is to start from $p_0 = (x_0,y_0)$.  It is geometrically clear that this point must be on the infinite component of $C$, call it $C_0$: the other component $C_1$ is a closed curve in the affine plane ${\bf R}^2$, so any line meets it with even total multiplicity.  Given $p_0$, the lines through $p_0$ constitute a real projective line, which is topologically a circle and the lines through $p_0$ that meet $C_0$ in two other points $q,q'$ constitute the union of two closed arcs, one for lines where $q,q' \in C_0$ and the other for lines where $q,q' \in C_1$.  [The boundary points correspond to the four points $q$ whose tangent passes through $p$, which are the solutions of $2q=-p$ in the group law of $C$.]  So the lines through $p_0$ in $S$ constitute two open intervals.  Now the subtlety is that when $p_0$ goes around the closed curve $C_0$, these two intervals switch as each of the boundary points makes a complete cycle around $C_0$ or $C_1$, so we must traverse $C_0$ twice to traverse our cylinder once.  In effect we're getting a Möbius band cut down the middle, which is indeed a cylinder (with a "full twist", true, but that is an artifact of the embedding in three-dimensional space that we use to visualize $S$).
For a different kind of explicit picture of $S$, note that a real cubic polynomial has one real root (with multiplicity) if and only if its discriminant is negative.  So we can describe $S$ by eliminating of the variables from $aX+bY+c=0$, substituting into $Y^2=X^3-X$, computing the discriminant $\Delta$ of the resulting cubic, and plotting the region $\Delta < 0$.  For example, in the affine piece $b \neq 0$ of ${\bf P}^*$, we may set $b=1$, compute $Y = -(aX+c)$, find that
$$
\Delta = -27c^4 - 4(ac)^3 + 30(ac)^2 + 4 a^5 c + 24 ac + a^4 + 4
$$
(I didn't promise it would be pretty), and ask www.wolframalpha.com
plot(-27*c^4-4*a^3*c^3+30*a^2*c^2+4*a^5*c+24*a*c+a^4+4 < 0)

to get a picture with two blue components that join up at infinity to form a topological cylinder:
 (source)
[The two visible cusps come from the inflection points where $p=q=q'$, which are real 3-torsion points on $C$; there's a third such singularity at infinity.  This means that of the two boundary components of $S$ (it looks like four but they pair up at infinity) the one containing the cusps is $C_0$, and the other is $C_1$.]  Try also
plot(-27*c^4-4*a^3*c^3-30*a^2*c^2+(24*a-4*a^5)*c+a^4-4 < 0)

for the picture arising from the curve $y^2=x^3+x$ with only one real component; this time it is a Möbius band embedded in ${\bf P}^*$ so that there boundary and the complement have only one component each:
 (source)
To connect this with the usual (but less elementary) picture of an elliptic curve over ${\bf C}$ as a complex torus: as Lubin noted, the complex locus of $C$ is isomorphic as a Riemann surface with ${\bf C} / L$ where $L$ is the Gaussian lattice ${\bf Z} + {\bf Z} i$; this is consistent with complex conjugation, and the real locus consists of the cosets mod $L$ of the complex numbers of integral or half-integral imaginary part, constituting the components $C_0$ and $C_1$ respectively.  We're looking to identify the conjugate pairs $\{(z,\bar z)\} \bmod L$ with a cylinder; in terms of the group law the real point $p_0$ associated above to $\{(z,\bar z)\}$ is $-2 \phantom. {\rm Re}(z)$, which as before can only be on $C_0$ and goes around $C_0$ twice (and in the opposite direction, as it happens) as $z$ goes around the cylinder once.


TITLE: Applying a function on any multiset of real numbers
QUESTION [0 upvotes]: I would like to define a function whose domain is any multiset of real numbers and image is a real number.
To my understanding, the domain of a function that can be applied on any set of real numbers is the power set $\mathcal{P}(\mathbb{R})$. Is it correct? If yes, is there an equivalent "power multiset" and what is its notation?

REPLY [0 votes]: In the article Mathematics of Multisets by A. Syropoulos, this is defined as follows:

Assume that $A$ is a set, then $\mathcal{P}^A$ is the set of all multisets which have $A$ as their support set.


TITLE: Induction with multiple variables
QUESTION [0 upvotes]: Let the function g : R $\rightarrow$ R satisfy $g(xy) = x \cdot g(y) +y \cdot g(x)$ for all
real numbers x and y.
Prove $g(u^n) = nu^{n-1}g(u)$, for all positive integers $n$ and all real numbers $u$.
the Inductive step for me is a bit tricky, the base case is straightforward:
$g(1^{1})$ = $1\cdot 1^{0}\cdot g(1)$
$g(1) = g(1)$
Now, I believe I have a fundamental misunderstanding of what induction looks like. Of course in this case it means to try and compute $u+1$ and $n+1$, but plugging it in and doing all the algebra isn't working for me.
Any hints, tips, suggestions?
Edit:
Going off of what voldemort said, $u$ is fixed and we're only trying to prove the induction step for n+1. I get the following:
$g(u^{n+1}) = (n+1)\cdot u^n\cdot g(u)$
However, I'm unsure of how to algebraically deal with exponents in side functions.

REPLY [1 votes]: Let $f:\mathbb R\to\mathbb R$ be a function satisfying $f(xy)=x\cdot f(y)+f(x)\cdot y$ for all $x,y\in\mathbb R$.

Claim: For all $n\in\mathbb N$ and $u\in\mathbb R$ we have $f(u^n) = nu^{n-1} f(u)$.

Proof. Let $u\in\mathbb R$ be any real number. Proceed by induction on $n$.
For $n=1$ the claim is
$$
f(u^1) = 1\cdot u^0 f(u),
$$
which is true, since $u^0=1$ and $u^1=u$.
Now let the claim hold for a fixed $n\in\mathbb N$, then
$$
f(u^{n+1}) = f(u^n u) = f(u^n) u + u^n f(u) = nu^{n-1} f(u) u + u^n f(u) = (n+1)u^n f(u)
$$
as desired. $\square$


TITLE: Does not $0\mid 0$ contradicts that divisibility by zero is undefined?
QUESTION [2 upvotes]: Does not $0\mid 0$ contradicts that divisibility by zero is undefined?

Could anyone clarify this for me please?

REPLY [5 votes]: Given integers $a$ and $b$, we say that $a$ divides $b$ if there is an integer $c$ with $b=ac$.  This is purely multiplicative, no division around.
So, by our definition, is it true that $0$ divides $0$?  Yes, because $0=0 \cdot 1$.  Done.
Again, none of this was phrased with division.


TITLE: Is there such an $x$ that both $2^{\frac{x}{3}}$ and $3^{\frac{x}{2}}$ are simultaneously rational?
QUESTION [18 upvotes]: I'm having difficulty with the following problem:

Is there such an $x$ that both $2^{\frac{x}{3}}$ and $3^{\frac{x}{2}}$ are simultaneously rational, for $0<x<1$?

I've tried proving by contradiction but the idea failed. Any help is appreciated!

REPLY [6 votes]: Negative answer follows from the four exponentials conjecture. Indeed, it's well-known that $\frac{\log 2}{3},\frac{\log 3}{2}$ are linearly independent over $\mathbb Q$ (a relation between them would imply an equality of the form $2^a=3^b$ for $a,b\in\mathbb N_+$ which clearly cannot happen). Further, it's easy to see $x$ must be irrational too, so that $1,x$ are linearly independent over $\mathbb Q$. Now the conjecture mentioned implies that one of the following numbers is transcendental:
$$\begin{align*}
e^{1\cdot\frac{\log 2}{3}} &=2^{1/3},\\
e^{1\cdot\frac{\log 3}{2}} &=3^{1/2},\\
e^{x\cdot\frac{\log 2}{3}} &=2^{x/3},\\
e^{x\cdot\frac{\log 3}{2}} &=3^{x/2}.\end{align*}$$
The first two numbers are clearly algebraic, so we conclude we can't have the latter two simultaneously rational.
It should be noted that the four exponentials conjecture is still wide open, despite the fact there are some very similar results which have been proven. A related question, asking when $2^x,3^x$ can be both integral, is also well-known and open.


TITLE: Prove two triangular properties about set distances.
QUESTION [2 upvotes]: In particular, I need to prove the following: $d(A_1,B_1)+d(A_2,B_2)\geq d(A_1\cup A_2,B_1\cup B_2)$ and $d(A_1,B_1)+d(A_2,B_2)\geq d(A_1\cap A_2,B_1\cap B_2)$.
Reading from Baby Rudin, it seems these require knowing properties of symmetric differences, namely $S(A_1,B_1) \cup S(A_2,B_2) \text{ contains }
 S(A_1\cup A_2,B_1\cup B_2),
S(A_1\cap A_2,B_1\cap B_2), \text{ and }S(A_1\setminus A_2,B_1\setminus B_2)$

REPLY [0 votes]: By the definition of an outer measure(particularly monotonicity and subadditivity), it suffices to show that $$S(A_1 \cup A_2, B_1 \cup B_2) \subseteq S(A_1, B_1) \cup S(A_2, B_2).$$
If $x \in S(A_1 \cup A_2, B_1 \cup B_2)$, then WLOG we can assume $x \in (A_1 \cup A_2) \setminus (B_1 \cup B_2)$. Then $x \in A_1$ or $x \in A_2$ so again we can ssume WLOG that $x \in A_1$. Since $x \in A_1$ and $x \notin B_1 \cup B_2$ so $x \notin B_1$. Hence. $x \in A_1 \setminus B_1 \subseteq S(A_1,B_1). $
The other inequality is very similar. No assumption of measurability is necessary.


TITLE: Show that $(T_{ij})=\begin{pmatrix} \alpha &\omega &0\\-\omega & \alpha &0\\ 0 &0& \beta \end{pmatrix}$
QUESTION [2 upvotes]: A tensor has components $T_{ij}$ with respect to Cartesian coordinates
   $x$. If the tensor is invariant under arbitrary rotations around the
   $x_3$-axis, show that it must have the form $$(T_{ij})=\begin{pmatrix}
 \alpha &\omega &0\\-\omega & \alpha &0\\ 0 &0& \beta \end{pmatrix}$$

Surely we want $\begin{pmatrix} \cos\theta &\sin\theta &0\\-\sin\theta & \cos\theta&0\\ 0 &0& 1\end{pmatrix}\begin{pmatrix} T_{11} &T_{12} &T_{13}\\T_{21}& T_{22}&T_{23}\\ T_{31}&T_{32}&T_{33}\end{pmatrix}=\begin{pmatrix} T_{11} &T_{12} &T_{13}\\T_{21}& T_{22}&T_{23}\\ T_{31}&T_{32}&T_{33}\end{pmatrix}$ but we then have $(\cos\theta )T_{11}+(\sin\theta) T_{21}=T_{11}$ and $(\cos\theta) T_{21}-(\sin\theta) T_{11}=T_{21}$ which eventually leads to $1-\cos\theta=\cos\theta-1$ which must hold for all $\theta$ which is clearly wrong, unless $T_{11}/T_{21}=0$ which again is wrong.
What am I doing wrong? Is my approach fundamentally wrong? I imagine I am underestimating the question quite a but (if this method were to work that would make the question far easier than expected), I suspect there's a lot more to the question I'm not considering or my approach is wrong altogether.
Any help would be much appreciated
Thank you

REPLY [1 votes]: I think your calculation is right.
Let $R_\theta$ be a $2\times 2$ rotational matrix, observe that
\begin{align}
R_\theta M = M \ \ \Rightarrow \ \ (I-R_\theta)M= 0
\end{align}
for all $\theta \in [0, 2\pi)$ implies $M = 0$.
I think you might be confusing something here.


TITLE: Must be Bayes' theorem
QUESTION [2 upvotes]: A professor gave me the following question a week earlier that he himself was doubtful about. I gave it quite a lot of thought but couldn't come up with any way to solve the question. Here it is:-
$Q.$A wallet containing $16$ currency notes - $4$ each of $Rs. 10$, $Rs. 20$, $Rs. 50$ and $Rs. 100$ - is kept on a table in a dark room. The maid of the house steals $2$ notes from the wallet which are apparently not visible to her (i.e. she doesn't know which notes she has taken) and leaves the room. After some time the owner of the wallet comes into the room and draws $2$ notes from the wallet. After coming out of the room, he finds that the amount in his hand is $Rs. 200$. So find the probability that the notes the maid has stolen comprises of two $Rs. 100$ notes.
During discussion of this question with my friends one of them said that since two $Rs. 100$ notes are surely left, the probability should be $$P=\frac {\binom 42}{\binom {14}2}=\frac 6{91}.$$ But the answer given is $\frac 1{91}$. I think that to solve this question one will have to use Bayes' theorem. But where and how should I use it?

REPLY [3 votes]: I like Brian’s answer, but if you’re uncomfortable with the idea of counting the number of ways the maid can do something in the past, here’s another way to look at it.
Call the bills the maid took $b_1$ and $b_2$, and the ones the owner took $b_3$ and $b_4$. The question is then this: Given an arrangement $b_1, b_2,\dots,b_{16}$ of the bills where $b_3=b_4=100$, what is the probability that $b_1=b_2=100$?
Equivalently, of all possible arrangements of these 14 bills: four $10$s, four $20$s, four $50$s, and the two $100$s that are not in positions $3$ and $4$, what fraction have the two $100$s first?
There are $\dfrac{14!}{4!4!4!2!}$ arrangements of the bills, and the number of them with the two $100$s first is the number of arrangements of four $10$s, four $20$s, four $50$s, or $\dfrac{12!}{4!4!4!}$, so the answer is
$$\left.{\dfrac{12!}{4!4!4!}}\middle/{\dfrac{14!}{4!4!4!2!}}\right.=\frac{12!2!}{14!}=\frac{1}{91}.$$


TITLE: Uniform stability of equilibrium
QUESTION [3 upvotes]: I have been given the following definition for uniform stability: the equilibrium state $x_e$ is uniformly stable, if for any $\epsilon > 0$ there is a $\delta > 0$ such that
$$\|x(0)-x_e\|<\delta~~\Rightarrow ~~\|x(t)-x_e\|<\epsilon, ~~\forall t\geq 0$$
In my opinion this definition does not have anything to do with stability. Imagine a system with $x(t)$ going to infinity and $x(t) \geq 10^{100} ~~\forall t \geq 0$ and $x_e = 0$.
Then the system would be uniformly stable following the above definition, as for any $\epsilon$ I can use $\delta = 10^{100}$ and that would fulfill the implication. The reason is that $x(0) - x_e$ is never smaller than $10^{100}$ so the left side of the implication is always false and therefore the implication always true.
What am I missing here?

REPLY [1 votes]: I think you are missing a quantifier about the curves $x(t)$. Something like: for all $\epsilon>0$, there exists a $\delta>0$ such that for all integral curves $x:\mathbb{R}\to\mathbb{R}$,
$$\|x(0)-x_e\|<\delta~~\Rightarrow (\forall t\geq 0,\|x(t)-x_e\|<\epsilon).$$
Then this precisly says that, if you start near enough you equilibrium, you stay arbitrarily close to it the whole time.


TITLE: How to calculate the derivative of following integral?
QUESTION [2 upvotes]: I did an exercise which would like to calculate the derivative in $x$ of the integral $$T(x) = \int\limits_0^{1} t^2 (1-t)^3 (t-x)^4 dt,$$
Of course, I showed that $$\dfrac{d}{dx} T(x) = - 4 \int\limits_0^{1} t^2 (1-t)^3 (t-x)^3 dt . $$
The problem is that I'd like a general resultat which can give a method to determinate the derivative in $x$ of the integral $T_1(x) = \int\limits^1_0 f(t, x) dt$ where $f(t,x) $ is a polynomial function of $t$ and $x$.
My question: Is there a resultat to determinate the derivative in $x$ of the integral $T_1(x) = \int\limits^1_0 f(t, x) dt$ where $f(t,x) $ is a polynomial function of $t$ and $x$?
Thank you very much for your interests!

REPLY [1 votes]: In general, if $a$ and $b$ are constants, and
$$F(x)=\int_a^b f(x,t)dt$$
then
$$F'(x)=\int_a^b\frac{\partial}{\partial x}f(x,t)dt$$
for a sufficient function $f$. Here $\frac{\partial}{\partial x}$ denotes the partial derivative. More details can be found here.


TITLE: How does the area of moving circle change?
QUESTION [1 upvotes]: We know that the area of a circle at rest frame is
$$A=\pi x^2$$ from $\pi xy$ where y=x
If I move this circle with velocity $v$ in the x-direction, I would expect to see a contraction (I'm not talking about optical observation since in that case it will still look like a circle) in the x-direction and nothing on y-direction so my area will be
$$A=\pi x'y$$
Since length in y-direction hasn't changed and $x'=x{\sqrt{1-\frac{v^2}{c^2}}}$, area of a moving circle would be
$$A=\pi x^2 \sqrt{1-\frac{v^2}{c^2}}$$
I couldn't find anything on internet about contractions in area, this above reasoning would be how I would attack the problem, is that correct?

REPLY [0 votes]: It might be better to rephrase your question to read 'How does the area of a circle change when it is considered from a reference frame moving relative to it?' The key point which @user12262 makes is that the circle itself does not change in its rest frame- in other frames it appears to be shortened in one direction, the direction and extent of the distortion varying according to the velocity of the frames. The apparent change in shape is caused by the fact that in any moving frame the leading edge of the circle is viewed at an earlier time than the trailing edge.


text:
\begin{document}

\title{ Bounds on Codes Based on Graph Theory }

\author{
\authorblockN{Salim Y. El Rouayheb}
\authorblockA{ECE Department \\
Texas A\&M University \\
College Station, TX 77843 \\
salim@ece.tamu.edu} \and
\authorblockN{Costas N. Georghiades}
\authorblockA{ECE Department \\
Texas A\&M University \\
College Station, TX 77843 \\
georghiades@ece.tamu.edu} \and
\authorblockN{Emina Soljanin}
\authorblockA{Math. Sc. Center \\
Bell Labs, Lucent \\
Murray Hill, NJ 07974 \\
emina@lucent.com}\and
\authorblockN{Alex Sprintson}
\authorblockA{ECE Department \\
Texas A\&M University \\
College Station, TX 77843 \\
spalex@ece.tamu.edu}
 }

\maketitle
\begin{abstract}

Let $A_q(n,d)$ be the maximum order (maximum number of codewords) of
a $q$-ary code of length $n$ and Hamming distance at least $d$. And
let $A(n,d,w)$ that of a binary code of constant weight $w$.
Building on results from algebraic graph theory and
Erd\H{o}s-ko-Rado like theorems in extremal combinatorics, we show
how several known bounds on $A_q(n,d)$ and $A(n,d,w)$ can be easily
obtained in a single framework. For instance, both the Hamming and
Singleton bounds can derived as an application of a property
relating the clique number and the independence number of vertex
transitive graphs. Using the same techniques, we also derive some
new bounds and present some additional applications.
\end{abstract}

\section{Introduction}
Let $\Sigma=\{0,1,\dots,q-1\}$ be an alphabet of order $q$. A
$q$-ary code $C$  of length $n$ and order $|C|$  is a subset of
$\Sigma^n$ containing $|C|$ elements (codewords). The weight
$wt(c)$ of a codeword $c$ is the number of its non-zero
entries. A $w$ constant weight code is a code where all the
codewords have the same weight $w$. The Hamming distance
$d(c,c')$ between two codewords $c$ and $c'$ is the number of
positions where they have different entries. The minimum
Hamming distance of a code $C$ is the largest integer $\Delta$
such that $\forall c,c'\in C, d(c,c')\geq \Delta$.

Let $A_q(n,d)$  be the maximal number of codewords that  a $q$-ary
code of length $n$ and minimum Hamming distance $d$ can possibly
contain (\cite[Chapter 17]{McWilliams}). $A(n,d,w)$ is defined
similarly for  binary codes with constant weight $w$. Finding the
values of  $A_q(n,d)$ and $A(n,d,w)$ is a basic problem in
``classical" coding theory \cite{Sloane,McWilliams}.

Finding a general exact expression for the maximal order of
codes is a difficult task. In fact, it was described in
\cite{Ahlswede2}, as ``a hopeless task". For this reason, much
of the research done has focused on bounding these quantities.

The dual problem, consisting of finding the maximal order of a set
of codewords satisfying an upper bound on their pairwise Hamming
distance (anticodes), is well studied in extremal combinatorics.
Surprisingly enough, it has a closed form solution \cite{Ahlswede,
Ahlswede2, Frankl}.

Using tools from algebraic graph theory, we draw a link between the
maximal order of codes and that of anti-codes. Then using results
like the celebrated Erd\H{o}s-ko-Rado theorem, we rederive some
known inequalities on $A_q(n,d)$ and $A(n,d,w)$ and other similarly
defined quantities and give some new bounds.

This paper is organized as follows. In Section \ref{graphintro}
we briefly introduce some of the needed background in graph
theory. In Section \ref{secbound} we show how the tools
introduced can be used to derive upper bounds on $A_q(n,d)$. In
Sections \ref{secconstant} and \ref{secdouble} we derive bounds
 on the maximal size of constant and doubly
constant weight codes, respectively. In Section \ref{secapp},
we show how the described techniques can be used to solve other
problems. We conclude in Section \ref{secconc}, where we
summarize our results and present some open questions.

\section{Graph Theory Background\label{graphintro}}

We start by giving a brief summary of some graph theoretical
concepts and results that will be  needed in this paper. For more
details, we refer the interested reader to \cite{Diestel} and
\cite{Godsil}.

Let $G(V,E)$ be an undirected graph, where $V$ is its vertex set and
$E$ is its edge set ($E\subseteq V\times V$). We also use
$\mathrm{V}(G)$ to denote the vertex set of $G$ and $\mathrm{E}(G)$
its edge set.

If $\{u,v\}$ is an edge in
$G$, i.e.\ $\{u,v\}\in E(G)$, we say that the vertices $u$ and $v$
are adjacent and write $u \sim v$.

The complement of a  graph $G$ is the graph $\bar{G}$ defined over
the same vertex set but where two vertices are adjacent in $\bar{G}$
iff they are not in $G$. We denote by $\omega(G)$ the \emph{clique
number} of a graph $G$, defined as  the largest number of vertices
of $G$ that are pairwise adjacent. In contrast  $\alpha(G)$, the
\emph{independence number} of $G$, is  the largest number of
vertices in $G$ such that no two of them are adjacent. It can be
easily seen that $\alpha(G)=\omega(\bar{G})$. In addition, the
\emph{chromatic number} $\chi(G)$ of $G$ is the minimum number of
colors needed to color its vertices such that different colors are
assigned to adjacent vertices.

\begin{definition}[Graph Automorphism  \cite{Godsil}]
Let $G(V,E)$ be a graph and $\phi$ a bijection from $V$ to
itself. $\phi$ is called an \emph{automorphism} of $G$ iff
$$\forall u,v\in V, u\sim v \Leftrightarrow \phi(u)\sim \phi(v).$$
\end{definition}\vspace{1.5mm}
The set of all automorphisms of $G$ is a group under composition; it
is called the automorphism group of $G$ and it is denoted Aut$(G)$.
For example, the complete graph on $n$ vertices $K_n$ has $S_n$, the
symmetric group of order $n$, as its automorphism group. In other
words, Aut$(K_n)\cong S_n$.

\begin{definition}[Vertex Transitive Graph \cite{Godsil}]
We say that graph $G(V,E)$ is vertex transitive iff
$$\forall u,v\in V, \exists \phi \in \text{Aut}(G)\text{ s.t. }\phi(u)=v.$$

\end{definition}\vspace{1.5mm}

\begin{definition}[Cayley Graphs]
Let $H$ be a group and $S\subset H$ such that $S$ is closed under
inversion and the identity element of $H$ $1_H \notin S$. The Cayley
graph $\mathcal{C}(H,S)$ is the graph with vertex set $H$ and where
for any $g,h\in H$, $g \sim h$ iff $hg^{-1}\in S$.
\end{definition}\vspace{1.5mm}

Next, we give without a proof an important result from \cite{Godsil}
(Lemma 7.2.2) that will be instrumental in deriving our results.

\begin{theorem}\label{corTrans}
Let $G(V,E)$ be a vertex transitive graph, then
$$\alpha(G)\omega(G)\leq |V(G)|.$$
\end{theorem}

\section{Bounds on Codes\label{secbound}}
\begin{definition}[Hamming Graph \cite{Sloane}]
The Hamming graph $H_q(n,d)$, $n\in
\mathbb{N}$ and $1\leq d\leq n$, has as vertices  all the $q$-ary
sequences of length $n$, and two vertices are adjacent iff
their Hamming distance is larger or equal to $d$. That is,
$V(H_q(n,d))=\Sigma^n$, where $\Sigma=\{0,1,\dots,q-1\}$.
and $u\sim v$ iff $d(u,v)\geq d$.
\end{definition}\vspace{1.5mm}

Recall that $A_q(n,d)$  denotes the maximum number of codewords in a
q-ary code of length $n$ and minimum Hamming distance $d$. When the
subscript is omitted we assume $q=2$, i.e. $A(n,d)=A_2(n,d)$. It can
be easily seen that $A_q(n,d)=\omega(H_q(n,d))$.

Let $S_{n,d}$, $1\leq d\leq n$, be a subset of the group
$(\mathbb{Z}_q^n,+)$, where addition is done modulo $q$, such that
$S_{n,d}=\{s\in \mathbb{Z}_q^n; wt(s)\geq d \}$. It is easy to check
that $S_{n,d}$ is closed under inversion and does not contain the
identity element (the all zero sequence). The next lemma asserts
that the Hamming graph is in fact a Cayley graph.
\begin{lemma}\label{HammingCayley}
$H_q(n,d)=\mathcal{C}(\mathbb{Z}_q^n,S_{n,d}).$
\end{lemma}\vspace{1.5mm}
\begin{proof}
Take $\Sigma=(\mathbb{Z}_q,+)$. The result then follows easily from
the fact that $\forall x,y \in \mathbb{Z}_q^n, $ $d(x,y)=wt(x-y)$.
\end{proof}

\begin{lemma}\label{transhamming}
The Hamming graph $H_q(n,d)$ is vertex transitive.
\end{lemma}\vspace{1.5mm}
\begin{proof}
Follows From Lemma \ref{HammingCayley} and the fact that Cayley
Graphs are vertex transitive \cite[Thm.~3.1.2]{Godsil}.

For a clearer presentation, we also give here a direct proof.
 Take $\Sigma=(\mathbb{Z}_q,+)$.
And $\forall u,v,x\in \Sigma^n$, define the function
$\phi_{u,v}(x)=x+v-u$. $\phi_{u,v}(x)$ is an automorphism of
$H_q(n,d)$. In fact,
$d(\phi_{u,v}(x),\phi_{u,v}(y))=d(x+v-u,y+v-u)=\text{wt}(x+v-u
-(y+v-u))=\text{wt}(x-y)=d(x,y)$. Also, $\phi_{u,v}(x)$ takes $u$ to
$v$.
\end{proof}

\begin{corollary}\label{hammingineq}
$ A_q(n,d) \alpha(H_q(n,d))\leq q^n$
\end{corollary}
\vspace{1mm}
\begin{proof}
Follows from Lemma  \ref{transhamming} and Thm.~\ref{corTrans}.
\end{proof}

Notice that $\alpha(H_q(n,d))$, the independence number of the
Hamming graph $H_q(n,d)$, is actually the maximum number of
sequences such that the Hamming distance between any two of them is
at most $d-1$. Following \cite{Ahlswede}, we define  $N_q(n,s)$ to
be the maximum number of $q$-ary sequences of length $n$ that
intersect pairwise (have the same entries) in at least $s$
positions. It follows that
\begin{equation}\label{equInd}
    \alpha(H_q(n,d))=N_q(n,t); \quad  \text{with }t=n-d+1
\end{equation}

\begin{lemma}[Singleton Bound]\label{lemSingleton}
$A_q(n,d)\leq q^{n-d+1}$
\end{lemma}\vspace{1.5mm}
\begin{proof}
Consider the set $T(n,t)$ of $q$-ary sequences of length $n$ that
all have the same element in the first $t=n-d+1$ entries. By
definition, $N_q(n,t)\geq |T(n,t)|= q^{n-t}$. Then, by
(\ref{equInd}) and Corollary \ref{hammingineq}, $A_q(n,d)\leq
\frac{q^n}{q^{n-t}}=q^{n-d+1}$.
\end{proof}

\begin{lemma}[Hamming Bound]\label{lemHamming}
\[
    A_q(n,d)\leq
    \frac{q^n}{\sum_{i=0}^{\lfloor\frac{d-1}{2}\rfloor}\binom{n}{i}(q-1)^i}.
\]
\end{lemma}\vspace{1.5mm}
\begin{proof}The proof is similar to that of Lemma~\ref{lemSingleton} and is done
by finding a different lower bound on $N_q(n,t)$. In fact,
consider the ball  $B(n,r)=\{x\in\Sigma^n;wt(x)\leq r \}$. By
the triangle inequality,  $\forall x,y\in B(n,\lfloor
\frac{d-1}{2}\rfloor), d(x,y)\leq d-1$. Therefore $N_q(n,t)\geq
|B(n,\lfloor \frac{d-1}{2}\rfloor)|$, and
$A_q(n,d)\leq\frac{q^n}{ B(n,\lfloor \frac{d-1}{2}\rfloor)}$.
\end{proof}

The number $N_q(n,t)$ is well studied in extremal combinatorics
\cite{Ahlswede} \cite{Frankl}, and a closed form for it is
known. Thus, exact expressions of $N_q(n,t)$ can be used to
derive better upper bounds on $A_q(n,d)$. For instance, if
$n-t$ is even, $N_2(n,t)=\sum_{i=0}^{\frac{n-t}{2}}
\binom{n}{i}$. Thus, in this case, $B(n,\lfloor
\frac{d-1}{2}\rfloor)$ is a maximal anticode. However, when
$n-t$ is odd, $N_2(n,t)= 2 \sum_{i=0}^{\frac{n-t-1}{2}}
\binom{n-1}{i}$ \cite[Thm.~Kl]{Ahlswede} and
\cite{Kleitman}. Therefore, we obtain the following lemma.

\begin{lemma}\label{firstbound}
\begin{equation}\label{binaryb}
    A(n,d)\leq
    \frac{2^{n-1}}{\sum_{i=0}^{\frac{d-2}{2}}\binom{n-1}{i}}, \quad \text{if $d$ is even}.
\end{equation}
\end{lemma}\vspace{1.5mm}

Notice that the above bound is tighter than the Hamming bound for even $d$ since
$$ 2 \sum_{i=0}^{\frac{d-2}{2}} \binom{n-1}{i}
-\sum_{i=0}^{\frac{d-2}{2}} \binom{n}{i}
=\binom{n-1}{\frac{d-2}{2}}>0.$$
This new improved Hamming
bound was recently proven in \cite{Matsumoto} using different
techniques than the one presented here.

Next we give a new upper bound on $A_q(n,d)$ for alphabets of
arbitrary size.
\begin{lemma}
For $q\geq 3$, $t=n-d+1$ and $r=\lfloor \min\{\frac{n-t}{2},
\frac{t-1}{q-2}\}\rfloor$,

\begin{equation}\label{qarybound1}
 A_q(n,d)\leq\frac{q^{t+2r}}{\sum_{i=0}^{r}\binom{t+2r}{i}(q-1)^i}.
\end{equation}
\end{lemma}\vspace{1.5mm}

\begin{proof}
The proof follows from Corollary \ref{hammingineq} and Thm.~2 in
\cite{Frankl} or the Diametric Theorem of \cite{Ahlswede}.
\end{proof}

Note that for $q\geq t+1$, $N_q(n,t)=q^{n-t}$ \cite[Corollary
1]{Frankl}, i.e. a maximal anticode would be the trivial set
$T(n,t)$ described in the proof of Lemma~\ref{lemSingleton}. In
this case, the bound of (\ref{qarybound1}) boils down to the
Singleton bound.

For $d$ even and $n$ not much larger than $t$, the next lemma
provides an improvement on the Hamming bound for nonbinary
alphabets.

\begin{lemma}\label{lemHamming2}
For $d$ odd and $n\leq t+1+\frac{\log t}{\log (q-1)}$
\begin{equation}
A_q(n,d)\leq \frac{q^{n-1}}{\sum_{i=0}^{\frac{d-2}{2}}
\binom{n-1}{i}(q-1)^i}
\end{equation}
\end{lemma}\vspace{1.5mm}
\begin{proof}
Under the conditions of this lemma,
$N_q(n,t)=q\sum_{i=0}^{\frac{d-2}{2}} \binom{n-1}{i}(q-1)^i$
\cite[Eq.\ 1.7]{Ahlswede}. The result then follows from  Corollary
\ref{hammingineq}.
\end{proof}

\section{Bounds for Constant Weight Codes\label{secconstant}}

Let $A(n,2\delta,w)$ be the maximum possible number of
codewords in a  \emph{binary} code of  length $n$, constant
weight $w$ and minimum distance $2\delta$ \cite{Sloane, Vardy}.

Define the graph $K(n,2\delta,w)$ as the graph whose vertices
are all the binary sequences of length $n$ and weight $w$ and
where two vertices $u,v$ are adjacent iff $d(u,v)\geq 2\delta$.
It can be easily seen that
$A(n,2\delta,w)=\omega(K(n,2\delta,w))$.

Let $\binom{[n]}{w}$ denote the set of all subsets of
$[n]=\{1,2,\dots,n\}$ of order $w$. There is a natural bijection
$\nu$ between $\mathrm{V}(K(n,2\delta,w))$ and  $\binom{[n]}{w}$.
Namely, $\forall u \in \mathrm{V}(K(n,2\delta,w))$, $\nu(u)=U=\{i;
u(i)=1\}$.

\begin{lemma}\label{lemequivalence}
$\forall p,q\in  \mathrm{V}(K(n,2\delta,w)), p\sim q$ iff $|P\cap
Q|\leq w-\delta$ where $P=\nu(q)$ and $Q=\nu(q)$.
\end{lemma}\vspace{1.5mm}
\begin{proof}
$2\delta\leq d(p,q)=|(P\cap \bar{Q})\cup (\bar{P}\cap Q)|=2w-2|P\cap
Q|.$
\end{proof}

\begin{lemma}\label{lemXtrans}
$K(n,2\delta,w)$ is vertex transitive.
\end{lemma}\vspace{1.5mm}
\begin{proof}
For any two vertices $p,q$ of $K$, any bijection on $[n]$ such that
the image of $P=\nu(p)$ is $Q=\nu(q)$, takes $p$ to $q$ and belongs
to $Aut(K)$.
\end{proof}

The first result that follows directly  from Lemma \ref{lemXtrans}
is the Bassalygo-Elias inequality \cite{Vardy}. We first recall some
additional  results in graph theory.
\begin{definition}[Graph Homomorphism]
Let $X$ and $Y$ be two graphs. A mapping $f$ from $\mathrm{V}(X)$ to
$\mathrm{V}(Y)$ is a homomorphism if $\forall x,y\in \mathrm{V}(X)$
 $x\sim y \Rightarrow f(x)\sim f(y).$
\end{definition}

\begin{theorem}\label{lem7}
If $Y$ is vertex transitive and there is a homomorphism from $X$ to
$Y$, then
\[
    \frac{|V(X)|}{\alpha(X)}\leq  \frac{|V(Y)|}{\alpha(Y)}
\]
\end{theorem}
\begin{proof}
An application of Lemma 7.14.2 in \cite{Godsil}.
\end{proof}

\begin{lemma}[Bassalygo-Elias inequality]\label{lemElias}
\[
  A(n,d)\leq \frac{2^n}{\binom{n}{w}}A(n,d,w)
\]
\end{lemma}\vspace{1.5mm}
\begin{proof}
Consider the two graphs $Y=\bar{H}(n,d)$ and $X=\bar{K}(n,d,w)$. $Y$
is vertex transitive. Since $X$ is an induced subgraph of $Y$, the
inclusion map is a homomorphism that takes $X$ to $Y$. The result
then follows from applying Thm.~\ref{lem7}.
\end{proof}

By the same token, we can show the below equalities

\begin{lemma}\label{inequalities}
\begin{align}
\label{mybound} A(n,d,w)&\leq \frac{n-w+1}{w} A(n,d+2,w-1)\\
\label{mybound2}A(n,d,w)&\leq \frac{n+1}{w+1}A(n+1,d+2,w+1)\\
   \label{johnson1} A(n,d,w)&\leq \frac{n}{w}A(n-1,d,w-1)\\
   \label{johnson2} A(n,d,w)&\leq \frac{n}{n-w} A(n-1,d,w)
    \end{align}
\end{lemma}\vspace{1.5mm}
\begin{proof}
We start by proving inequality \ref{mybound}. Let $\phi$ be a
mapping from $\binom{[n]}{w-1}$ to $\binom{[n]}{w}$, such that
$\forall P\in \binom{[n]}{w-1}, P\subset\phi(P)$. $\phi$ is a
homomorphism from $K(n,d+2,w-1)$ to $K(n,d,w)$. In fact, $\forall
P,Q\in K(n,d+2,w-1)$ such that $P\sim Q, |\phi(P)\cap\phi(Q)|\leq
|P\cap Q|+2\leq w-1-(d+2)/2+2=w-d/2$ (by Lemma
\ref{lemequivalence}). Therefore, $\phi(P)\sim\phi(Q)$. The
inequality then follows by applying Thm.~\ref{lem7}.

To prove  inequality \ref{mybound2}, take the homomorphism $\phi$
from $K(n+1,d+2,w+1)$ to $K(n,d,w)$ to be
$\phi(X)=X\setminus\{\max_{x\in X} x\}, \forall X\in
\binom{[n+1]}{w+1}$.

The rest of the inequalities can be proved similarly by considering
the  corresponding graphs and taking the homomorphism to be the
inclusion map.
\end{proof}

The first two inequalities are new, whereas inequalities
\ref{johnson1} and \ref{johnson2} were first proven by Johnson in
\cite{Johnson}.

Similarly, we can show the following inequalities regarding
$A_q(n,d)$.

\begin{lemma}\label{inequalities2}
\begin{align*}
    A_q(n,d)&\leq \frac{1}{q} A_q(n+1,d+1)\\
    A_q(n,d)&\leq q A_q(n-1,d)\\
    A_q(n,d)&\leq \frac{q^n}{(q-1)^n} A_{q-1}(n,d,w)
\end{align*}
\end{lemma}\vspace{1.5mm}

\begin{lemma}\label{thconst}
Let $t=w-\delta+1$.
\begin{equation}\label{boundconst}
  A(n,2\delta,w)\leq  \frac{\binom{n}{w}}{\binom{n-t}{w-t}}
\end{equation}
\end{lemma}\vspace{1.5mm}

\begin{proof}
Let $G=K(n,d,w)$. Since $G$ is vertex transitive, we have
$$A(n,2\delta,w)\alpha(G)\leq |V(G)|=\binom{n}{w}.$$

Define $M(n,w,s)$ as in \cite{Ahlswede2} to  be the  maximum number
of subsets of $[n]$ of order $w$ that intersect pairwise in at least
$s$ elements. By Lemma \ref{lemequivalence}, $\alpha(G)=M(n,w,t)$.
But, $M(n,w,t)\geq \binom{n-t}{w-t}$ (for instance, consider the
system of all subsets of $[n]$ of order $w$ that contain the set
$\{1,2,\dots,t\}$).
\end{proof}

The bound of Lemma \ref{thconst} is actually the same as the one in
Thm.~12 in \cite{Vardy} which was given with a different proof.

One can improve on the bound of Lemma \ref{thconst} by using
the exact value of $M(n,w,t)$ \cite{Ahlswede2}. It is known
that for $n\geq (w-t+1)(t+1)$, $M(n,w,t)=\binom{n-t}{w-t}$
\cite{Erdos, Wilson}. However, this is not the case for lower
values of $n$.

\begin{lemma}
Let $t=w-\delta+1$ and $r=\max\{0, \lceil
\frac{\delta(w-\delta)}{n-d}-1 \rceil\}$, then

\begin{equation}\label{boundconst}
  A(n,2\delta,w)\leq
  \frac{\binom{n}{w}}{\sum_{i=t+r}^{w}\binom{t+2r}{i}\binom{n-t-2r}{w-i}};
\end{equation}
with $\binom{n}{k}=0$ when $k> n$.
\end{lemma}\vspace{1.5mm}
\begin{proof}(sketch)
$A(n,d,w)\leq \frac{\binom{n}{w}}{M(n,w,t)}$, then use the exact
value of $M(n,w,t)$ given by the main theorem of \cite{Ahlswede2}.
\end{proof}

\section{Bounds for Doubly Bounded Weight Codes\label{secdouble}}

Let $T(w_1,n_1,w_2,n_2,d)$ be the maximum number of codewords in a
doubly constant weight binary code of minimum distance $d$, length
$n=n_1+n_2$ and constant weight $w=w_1+w_2$,  where the first $n_1$
entries of each codewords have exactly $w_1$ ones \cite{Lev}.
$T'(w_1,n_1,w_2,n_2,d)$ is defined similarly but where the first
$n_1$ entries of each codewords have at most $w_1$ ones
\cite{Vardy}.

\begin{lemma}
\begin{align}
\label{levineq}A(n,d,w)&\leq
\frac{\binom{n_1+n_2}{w_1+w_2}}{\binom{n_1}{w_1}\binom{n_2}{w_2}}T(w_1,n_1,w_2,n_2,d)\\
\label{myineq}A(n,d)&\leq
\frac{2^n}{\sum_{i=0}^{w_1}\binom{n_1}{i}\binom{n_2}{w_1+w_2-i}}T'(w_1,n_1,w_2,n_2,d)
\end{align}
\end{lemma}\vspace{1.5mm}
\begin{proof}
Same as Lemma \ref{lemElias}.
\end{proof}

Note that inequality (\ref{levineq}) was first proven in
\cite{Lev}, whereas inequality (\ref{myineq}) is new. Several
other bounds on $T(w_1,n_1,w_2,n_2,d)$ known in literature,
such as Theorem~36 in \cite{Vardy}, can be also easily
obtained in the same way. The next lemma establishes some
additional new bounds. \small

\begin{lemma}\vspace{-3mm}
\begin{align*}
T(w_1,n_1,w_2,n_2,d)&\leq \binom{n_2}{w_2}A(n_1,w_1,d-2w_2)
    \text{ if }
    d-2w_2\geq 0\\
    T(w_1,n_1,w_2,n_2,d)&\leq \binom{n_1}{w_1}A(n_2,w_2,d-2w_1)
    \text{ if }
    d-2w_1\geq 0\\
    T(w_1,n_1,w_2,n_2, d)&\leq \frac{n_1-w_1+1}{w_1} T(w_1-1,n_1,w_2,n_2, d+2)\\
T(w_1,n_1,w_2,n_2, d)&\leq
\frac{n_1+1}{w_1+1}T(w_1+1,n_1+1,w_2,n_2, d+2)\\
     T(w_1,n_1,w_2,n_2, d)&\leq \frac{n_2-w_2+1}{w_2} T(w_1,n_1,w_2-1,n_2, d+2)\\
T(w_1,n_1,w_2,n_2, d)&\leq
\frac{n_2+1}{w_2+1}T(w_1,n_1,w_2+1,n_2+1, d+2)
    \end{align*}
\end{lemma}\vspace{1.5mm}
\normalsize

\section{Other Applications}\label{secapp}

In this section we demonstrate how the above techniques can be
helpful in solving other problems. For instance, we show how to
compute $N_q(n,1)$, the maximum number of $q$-ary sequences of
length $n$ intersecting pairwise in at least one position
\cite{Ahlswede}.

\begin{lemma}\label{lemberge}
$N_q(n,1)=q^{n-1}$
\end{lemma}\vspace{1.5mm}
\begin{proof}
Let $G=H_q(n,n)$; $N_q(n,1)=\alpha(G)$. Now, consider the set
of $q$ sequences where the entries in the $i$-th sequence are
all the same and equal to $i$, hence $\omega(G)\geq q$. But
$\omega(G)\leq q$ since the first entries of all sequences in a
clique in $G$ should contain different letters. Therefore,
$\omega(G)=q$. By Lemma \ref{transhamming}, we get
$N_q(n,1)\leq q^{n-1}$. But $N_q(n,1)\geq q^{n-1}$(see the
proof of Lemma~\ref{lemSingleton}).
\end{proof}

The next lemma gives the chromatic number of certain Hamming graphs.
\begin{lemma}\label{lemchro}
$\chi(H_q(n,d))=q^{n-d+1}$, for $q\geq n-d+2$, $1\leq d \leq n$.
\end{lemma}\vspace{1.5mm}
\begin{proof}
From the definitions, it follows that for any graph $G$,
$\chi(G)\geq \frac{|\mathrm{V}(G)|}{\alpha(G)}.$ But,
$\alpha(H_q(n,d))=q^{d-1}$ \cite[Corollary 1]{Frankl}. Therefore,
$\chi(H_q(n,d))\geq\frac{q^n}{q^{d-1}}= q^{n-d+1}$.

Let $\phi$ be a mapping from $\Sigma^n$ to $\Sigma^{n-d+1}$
consisting of deleting the last $d-1$ entries of a sequence. $\phi$
is a homomorphism from $H_q(n,d)$ to $H_q(n-d+1,1)=K^{n-d+1}$, where
$K^\ell$ is the complete graph on $\ell$ vertices. Therefore,
$\chi(H_q(n-d+1,1))\leq \chi( K^{n-d+1})=q^{n-d+1}$ \cite[Lemma
1.4.1]{Godsil}.
\end{proof}

Let  $v(G)$ be the Lov\'{a}sz upper bound \cite{x} on the zero error
capacity $\Theta(G)$ \cite{Shannon} of a graph $G$. We recall the
following two results of \cite{x}.

\begin{lemma}\label{Lov1}

$\alpha(G)\leq \Theta(G)\leq v(G)$
\end{lemma}

\begin{theorem}\label{Lov2}
If $G(V,E)$ is vertex transitive then $v(G) v(\bar{G})=|V|$.
\end{theorem}
In the following, we give a partial answer to  a question
raised in the conclusion of \cite{x}, namely ``Find further
graphs with $v(G)=\Theta(G)$".

\begin{lemma}\label{lemvt1}
The following graphs satisfy $v(G)=\Theta(G)$
\begin{enumerate}
  \item $H_q(n,d)$ when there exists a q-ary perfect code of length $n$ and minimum
distance $d$.
\item $H_q(n,d)$ when $q\geq n-d+2$ and there exists a q-ary MDS code
of length $n$ and minimum distance $d$.
\item $H_q(n,n)$.
\end{enumerate}
\end{lemma}
\begin{proof}
Let $G$ be a vertex transitive  graph such that $\alpha
(G)\alpha(\bar{G})=|\mathrm{V}(G)|$. Then, applying Lemma
\ref{Lov1} to $G$ and $\bar{G}$ and multiplying the two
resulting equations we get
$\frac{\Theta(G)}{v(G)}=\frac{v(\bar{G})}{\Theta(\bar{G})}\geq
1$. Therefore, $\Theta(G)=v(G)$. One can check that the graphs
$G$ belonging to the three families mentioned above satisfy
$\alpha (G)\alpha(\bar{G})=|\mathrm{V}(G)|$.
\end{proof}

\section{Conclusion }\label{secconc}
We constructed vertex transitive graphs where a code corresponds to
a clique and an anti-code  to an independent set. Thus, we
established a connection between the maximal order of  codes and
that of anti-codes. Using intersection theorems for systems of
finite sets and that of  finite sequences, we  provided a framework
where several known bounds on code size follow easily and  new
inequalities can be derived.

Several questions naturally arise here.

\begin{enumerate}
  \item What are  the zero error capacities of the graphs $H$ and $K$ and their
complements $\bar{H}$ and $\bar{K}$? What are   the values of the
$v$ function of these graphs.  Note, that these quantities can be
useful to derive bounds for $A_q(n,d)$ and $A(n,d,w)$ using Lemma
\ref{Lov1} and Thm.~\ref{Lov2}.
  \item From a graph theoretical
standpoint, trying to extend the result of Lemma \ref{lemchro} by
finding the chromatic number of the above graphs is also an
interesting question, and can have  applications to coding theory
and cryptography.
\item Perfect codes are codes who achieve the Hamming bound. We
gave here many upper bounds lower than the Hamming bound in specific
cases (Lemma~\ref{firstbound}, (\ref{qarybound1}), Lemma~\ref{lemHamming2}
and (\ref{boundconst})); thus ruling out the existence of perfect
codes there. It is an interesting question to find whether there
exist "nearly perfect codes" that can achieve these new bounds.
\end{enumerate}

config: arxiv


TITLE: Mass points of a Mass-spring model
QUESTION [0 upvotes]: Let's say I have a mass spring model like the one in the picture below:

So, there are 3 parts of the spring joined together in an equilateral triangular manner. Each of the joints has a mass of $m$. The resting length of each of the springs is $l$. The top joint point of the spring is fixed to the ceiling.
Now, if I were to pull both the lower points of the spring model such that each of the springs extend proportionally by $\Delta l$ change of length, and release. Now, I want to find an equation for Point A (indicated in the picture above) under gravity and sprint forces when springing back to position. The assumption is all the angles remain at $60$ degrees in every iteration when it springs back.
What I did is:
Let $k$ be the elasticity of the spring.
Then, for the X-axis component of the equation,
$k \cdot \Delta l \cdot cos(60) + k \cdot \Delta l = m\cdot a_x$
The acceleration of the spring going back to original x position would then be dividing both sides by the mass $m$.
For the Y-axis component of the equation with consideration of gravity as $g$,
$k \cdot \Delta l \cdot sin(60) + k \cdot \Delta l - mg = m\cdot a_y$
Similar to the X-axis, I thought I would consider the total of the extended length plus the projection from the x-axis onto the y-axis, and then minus the gravity resistance.
However, it turns out that I am wrong for the Y-axis component. The given answer is:
X: $k \cdot \Delta l \cdot cos(60) + k \cdot \Delta l = m\cdot a_x$
Y: $mg - k \cdot \Delta l \cdot sin(60) = m\cdot a_y$
I don't understand why is it so for the Y-axis, especially when the the gravity turns out to minus the projection and the extended $\Delta l$ is not added as part of the force.

REPLY [2 votes]: you have taken the right approach by summing the forces and setting that equal to mass times acceleration.
For the Y-component you have included a $k$ $⋅$ $\Delta{l}$ which should not be there. In the X-direction, this term represents the force contribution from the bottom spring (the horizontal one), however this spring does not contribute at all to forces in the Y-direction (because it lies completely in the X-direction) thus has no effect on the Y-axis equation.
Also, in the diagram you provided, the Y-axis points down. You wrote your equations as though the Y-axis points up, and this has caused a sign error. Gravity points down along the positive Y-direction, thus the $mg$ term should be positive. An extension of the spring by $\Delta$$l$ leads to a restoring force that will pull point A in the negative Y-direction, thus the $k$ $⋅$ $\Delta{l}$ $⋅$ $sin(60)$ term must have a minus sign.


text:
\section{Applications and numerical experiments}
\label{sec:appli}

In this section, we discuss the application of the optimal sampling strategies derived in Section~\ref{sec:optimal_drawing} to three concrete case studies. Firstly, we consider the setting of isolated measurements from the one-dimensional Fourier-Haar transform and derive an explicit sampling probability that promotes the recovery of signals that are sparse in levels  (Section~\ref{sec:applications_mri_iso}). Secondly, the case of two-dimensional Fourier-Haar transform with block-structured measurements is discussed in Section~\ref{sec:application_MRI}, of considerable interest in MRI. In particular, we analyze the setting where the Fourier space is sampled using random {vertical (or horizontal)} lines and where the signal exhibits a particular type of sparsity in levels (see Definition~\ref{def:sparsity_in_levels_2D}). Thirdly, we illustrate how the proposed derivation of optimal sampling measures can be applied to devise adaptive sampling strategies for one-dimensional function approximation from pointwise data (Section~\ref{sec:adaptive}).

\subsection{Performing isolated measurements with Fourier-Haar transform}
\label{sec:applications_mri_iso}

Let us consider the finite-dimensional setting \ref{iso_finite_setting} described in Section \ref{subsec:sampling} {and let $n = 2^{J+1}$ for some $J \in \Nbb$}.
Set $A_0$ to be the Fourier-Haar transform, i.e.\ $A_0 = {\mathcal{F}} H^* = \replacemath{(a_1 | a_2 | \hdots | a_n)^*}{(d_1 | d_2 | \hdots | d_n)^*}$ where $\mathcal{F} \in \Cbb^{n\times n}$ is the Fourier matrix {relative to frequencies $\{-n/2 +1, \ldots, n/2\}$} and $H^* \in \Rbb^{n\times n}$ is the inverse Haar transform. The matrix $A_0$ could be naturally chosen to model the acquisition in MRI, where the measurements are performed in the Fourier domain, and where MR images are considered sparse in the wavelet domain. In this framework, we aim at reconstructing the wavelet coefficients $x$ of the MR image.

First, we introduce the notion of sparsity in levels for the coefficient vector $x$. We define the levels $(\Omega_j)_{0\leq  j \leq J}$ as the partition of $\{1, \hdots , n \}$ corresponding to the subbands of the Haar transform, defined as $\Omega_0 := \{1,2\}$ and, for $j = 1,\ldots,J$, as
$$
\Omega_j := \{2^{j}+1,\ldots,2^{j+1}\}.
$$
The subband $\Omega_0$ corresponds to the scaling function and to the Haar mother wavelet. The subsequent subbands $\Omega_j$ with $j\geq 1$ correspond to wavelet functions dyadically refined at level $j$ (see \cite{adcock2016note} for further details).
The vector $x$ is assumed to be sparse in levels, i.e.\ denoting by $S$ the support of $x$, we suppose
\begin{align*}
|S \cap \Omega_j| = s_j,
\end{align*}
meaning that restricted to the $j$-th level $\Omega_j$, $x$ is $s_j$-sparse.

In order to devise effective sampling strategies, we  partition the set of Fourier frequencies into frequency subbands $(W_j)_{0\leq j \leq J}$, defined as $W_0 := \{0,1\}$ and, for $j = 1,\ldots, J$, as
$$
W_j := \{-2^j+1,\ldots,-2^{j-1}\} \cup \{2^{j-1}+1\ldots,2^j\}.
$$
Notice that for every $j = 0,\ldots,J$ we have
$$
|\Omega_j| = |W_j|= 2^{\max(1,j)}.
$$
For the sake of simplicity, we will relabel the Fourier  frequencies $\{-n/2 +1 ,\ldots, n/2\}$ as $\{1,\ldots,n\}$. With this convention, we  denote as $j : \{1, \hdots , n \} \to \{0 , \hdots , J\}$ the function that maps a Fourier frequency to the corresponding frequency band, i.e.\ $j(k) = \ell$ if $k \in W_\ell$.

In this setting, local coherence upper bounds are explicitly computable. We recall the following estimate, corresponding to \cite[Lemma 1]{adcock2016note}:
\begin{equation}
\label{eq:localcoherenceFH}
\mu_{j,\ell} := \max_{k \in W_j} \max_{i\in \Omega_\ell} |({\mathcal{F}}H^*)_{ki}|^2 \leq C \cdot 2^{-j} 2^{-|j-\ell|},
\end{equation}
where $C>0$ is a universal constant.

\paragraph{Application of the theory} Suppose that random isolated measurements are performed in the Fourier domain according to some probability distribution $\pi$ (we note in passing that, although useful for illustrative purposes, sampling single points in the Fourier domain is not feasible in practice). Then, thanks to the local coherence upper bound \eqref{eq:localcoherenceFH}, one can estimate the quantity $\Theta(S,\pi)$ {as} (see \cite[Corollary 4.4]{boyer2017compressed})
\begin{align}
\Theta(S,\pi) = C \max_{1\leq k \leq n } \frac{1}{\pi_k} 2^{-j(k)} \sum_{p=0}^J 2^{-|j(k)-p|/2} s_p.
\end{align}
As a consequence, the probability \replace{}{distribution} minimizing $\Theta(S,\pi)$ in this setting can be written as follows (see Lemma~\ref{lem:max_over_simplex}):
\begin{align}
\forall k \in \{1,\hdots , n \}, \quad \pi^{\Theta}_k = \frac{2^{-j(k)} \sum_{p=0}^J 2^{-|j(k)-p|/2} s_p}{\sum_{\ell=1}^n 2^{-j(\ell)} \sum_{p=0}^J 2^{-|j(\ell)-p|/2} s_p}.
\end{align}
Note that the drawing probability \replace{}{distribution} is a function of the frequency level.
Assuming that $\sgn(x_S)$ is a Steinhaus or Rademacher sequence and employing Theorems \ref{thm:noiseless} and \ref{thm:noisy}, the required number of measurements needed to ensure exact or stable and robust recovery with probability $1-\varepsilon$ is
\begin{align}
\label{eq:bound_m_iso_mri}
m \gtrsim \sum_{j=0}^J \left( s_j + \sum_{p=0 \atop p \neq j}^J 2^{-|j-p|/2} s_p \right) \cdot \ln^2(6n/\varepsilon),
\end{align}
which matches results in \cite[Corollary 4.4]{boyer2017compressed} and \cite{adcock2017breaking}.

Replacing $\Theta(\pi,S)$ with $\Lambda(\pi,S)$ leads to an improvement of condition \eqref{eq:bound_m_iso_mri}, at the price of an extra assumption on the sparsity in levels of the signal.

\begin{corollary}
\label{corol:mri_iso_lambda}
Let $A_0 = FH^*$ be the one-dimensional Fourier-Haar transform and consider the splitting of the Haar and of the Fourier spaces into subbands $(\Omega_j)_{0 \leq j \leq J}$ and $(W_j)_{0 \leq j \leq J}$ as described above. Suppose that $x \in \Cbb^{n}$ is an $S$-sparse vector with random signs and sparsities in levels $(s_j)_{0\leq j \leq J}$.
Fix $\varepsilon \in (0,1)$.
Then, condition \eqref{cond:killthethetalog} holds if
\begin{align}
\label{cond:killthetalog_mri_iso}
\min_{0\leq j \leq J} s_{j}  + \sum_{j'\neq j}  {s}_{j'}  2^{-|j-j'|} \gtrsim \ln({3}n/\varepsilon).
\end{align}
In this case, $\Lambda(S,\pi)$ can be chosen as follows
\begin{align}
\Lambda({S},\pi) = \max_{1\leq k \leq n } \frac{1}{\pi_k} 2^{-j(k)} \sum_{p=0}^J 2^{-|j(k)-p|} {s}_p.
\end{align}
Then, the probability minimizing $\Lambda({S},\pi)$ is
\begin{align}
\forall k \in \{1,\hdots , n \}, \quad \pi^{\Lambda}_k = \frac{2^{-j(k)} \sum_{p=0}^J 2^{-|j(k)-p|} s_p}{\sum_{\ell=1}^n 2^{-j(\ell)} \sum_{p=0}^J 2^{-|j(\ell)-p|} s_p},
\end{align}
and the recovery guarantees of Theorem \ref{thm:killthetalog} hold with probability at least $1-\varepsilon$ if
\begin{align}
\label{eq:bound_m_iso_mri2}
m \gtrsim  \sum_{j=0}^J \left({s}_j + \sum_{p=0 \atop p \neq j}^J 2^{-|j-p|} {s}_p \right) \cdot \ln({3}n/\varepsilon).
\end{align}

\end{corollary}

The proof of this result is given in Appendix \ref{proof:mri_setup_iso}. Condition \eqref{cond:killthetalog_mri_iso} can be easily verified in practice.
Note that by \eqref{eq:bound_m_iso_mri2}, we improved \eqref{eq:bound_m_iso_mri} (and, consequently, the state-of-the-art results in \cite{boyer2017compressed} and \cite{adcock2017breaking} when the signal is sparse with random signs) by (i) decreasing the interferences between different levels and (ii) removing a log factor.

\paragraph{Numerical experiments} In this part, we illustrate the improvement in recovery when the sampling strategy \replace{is taking}{takes} into account local coherences of the measurement vectors \emph{and} the structured sparsity of the signal to reconstruct. With this aim, we generate 100 random {signals with} wavelet coefficients in dimension $n=2048$ with $s/n \approx 6\%$ and having a  sparsity in levels structure as in Figure \ref{fig:boxplot_15meas}(a) with 4 subbands in total.
We compare three different sampling schemes where isolated samples are randomly drawn according to:
\begin{itemize}
\item the probability \replace{}{distribution} minimizing the global coherence of each measurement vector: $\forall k \in \{ 1 , \hdots , n \}$,
$$ \pi_k^\infty = \frac{\| \replacemath{a}{d}_{k} \|_\infty^2}{\sum_{p=1}^n \| \replacemath{a}{d}_p \|_\infty^2};
$$
\item the probability \replace{}{distribution} minimizing $\Theta(S,\pi)$: $\forall k \in \{ 1 , \hdots , n \}$,
$$ \pi_k^\Theta = \frac{\| \replacemath{a}{d}_{k} \|_\infty \sum_{j=0}^J s_j \| \replacemath{a}{d}_{k,\Omega_j} \|_\infty}{\sum_{p=1}^n \| \replacemath{a}{d}_{p} \|_\infty \sum_{j=0}^J s_j \| \replacemath{a}{d}_{p,\Omega_j} \|_\infty};
$$
\item the probability \replace{}{distribution} minimizing $\Lambda(S,\pi)$: $\forall k \in \{ 1 , \hdots , n \}$,
$$ \pi_k^\Lambda = \frac{\sum_{j=0}^J s_j \| \replacemath{a}{d}_{k,\Omega_j} \|_\infty^2}{\sum_{p=1}^n  \sum_{j=0}^J s_j \| \replacemath{a}{d}_{p,\Omega_j} \|_\infty^2}.
$$
\end{itemize}
\replace{}{These three sampling distributions can be computed in the case of the Fourier-Haar transform.  This is illustrated in Figure~\ref{fig:proba_profile_iso_mri} for the 1D structured-sparsity pattern described in Figure \ref{fig:boxplot_15meas}(a). One can clearly see in Figure \ref{fig:proba_profile_iso_mri} that a certain prior on the sparsity structure in this case inclines the sensing in the low frequency domain.}
\replace{Numerical}{Reconstruction} results are shown in Figure \ref{fig:boxplot_15meas}(b). \replace{}{For the same amount of measurements,} the sampling strategy minimizing the bound on $\Theta (S,\pi)$ proposed in this paper is outperforming  the standard CS strategy taking only into account the global coherence. In this setting, sampling according to $\Lambda (S,\pi)$ improves the reconstruction quality compared to the $\Theta (S,\pi)$-based strategy.

\begin{figure}
\begin{tabular}{ccc}
\includegraphics[width=0.33\linewidth]{images/proba_coherence_1D_2048.pdf} &
\includegraphics[width=0.33\linewidth]{images/proba_theta_1D_2048.pdf}  &
\includegraphics[width=0.33\linewidth]{images/proba_lambda_1D_2048.pdf}  \\
{\centering (a) $\pi^\infty$} & {\centering (b) $\pi^\Theta$} & {\centering (c) $\pi^\Lambda$} \\
\includegraphics[width=0.33\linewidth]{images/proba_coherence_3D.pdf} &
\includegraphics[width=0.33\linewidth]{images/proba_theta_3D.pdf}  &
\includegraphics[width=0.33\linewidth]{images/proba_lambda_3D.pdf}  \\
{\centering (d) $\pi^\infty$} & {\centering (e) $\pi^\Theta$} & {\centering (f) $\pi^\Lambda$}
\end{tabular}
\caption{\label{fig:proba_profile_iso_mri} Comparison between sampling probabilit\replace{ies}{y distributions} chosen according to different strategies\replace{ for 1D signals (a,b,c) or 2D signals (d,e,f), that are sparse in levels}{: in (a,b,c) for 1D signals with structured sparsity described in Figure \ref{fig:boxplot_15meas}(a), in (d,e,f) for 2D signals with the corresponding tensorized structured sparsity}.
In (a) and (d), the sampling probability \replace{}{distribution} $\pi^\infty$ is optimized to minimize the global coherence, i.e.\ $\pi_k \propto \|a_k\|_\infty^2$;
in (b) and (e), the sampling probability \replace{}{distribution} $\pi^\Theta$ is optimized to minimize an upper bound to $\Theta(S,\pi)$, i.e.\ $\pi_k \propto \|a_k\|_\infty \sum_{j=0}^J s_j  \|a_{k,\Omega_j} \|_\infty$; in (c) and (f), the sampling probability \replace{}{distribution} $\pi^\Lambda$ is optimized to minimize an upper bound to $\Lambda(S,\pi)$, i.e.\ $\pi_k \propto \sum_{j=0}^J \|a_k\|_\infty \|a_{k,\Omega_j} \|_\infty^2$; the probability \replace{densities}{distributions} in (d), (e), and (f) are constructed accordingly in the 2D case.}
\end{figure}

\begin{figure}
\begin{tabular}{cc}
\includegraphics[height=6cm]{images/struct_sparsity_1D.pdf} &
\includegraphics[height=6cm]{images/boxplot_1D_25p.pdf} \\
{\text{(a)}} & {\text{(b)}}
\end{tabular}
\caption{\label{fig:boxplot_15meas}
Boxplot of reconstruction PSNR in (b) of 100 random signals of length $n=2048$ having a structured sparsity in the wavelet decomposition as in (a) ($s/n=6\%$) from 25\% measurements drawn according to $\pi^\infty$, $\pi^\Theta$ and $\pi^\Lambda$ as in Figure \ref{fig:proba_profile_iso_mri} (a,b,c). In (a), we represent the {sparsity in levels structure of the randomly generated signals. The plot represents the} percentage of nonzero coefficients {for each} subband. }
\end{figure}


TITLE: "Right" Way of Introducing Modular Forms to Undergraduate Audience?
QUESTION [8 upvotes]: I am giving an extremely short talk (~12 minutes) in a few weeks in which I need to be able to introduce and motivate the idea of a classical modular form to an audience of undergraduates in as short a time as possible. I was intending to introduce modular forms as functions on lattices, following Serre's presentation in A Course in Arithmetic - this seems like the shortest path to motivating the particular symmetries that we require of modular forms. Does anyone else have any good ideas? Particularly, if there is a way of motivating forms of higher levels and of half-integral weight through the same idea of a function on lattices, I'd like to hear about it.

REPLY [1 votes]: I would suggest pointing out the trigonometric analogy (as JSE suggested) and mentioning that modular forms also have Fourier expansions, by virtue of invariance under upper-triangular matrices.  Since you want to introduce weights, I also suggest including a computation of the differential d(az+b/cz+d) to motivate the appearance of the factors (cz+d)^k.  This lets you describe weight k forms as k/2-fold polydifferentials or sections of a pluricanonical bundle (and are in general not differential forms, since you use tensor powers instead of wedges).  Your time constraint is rather unrealistic, but modular forms of half-integral weight can be motivated by theta functions of odd-dimensional lattices.  I don't know how to phrase this in the language of lattices in C.
Higher level forms can be introduced as functions on a space of pairs (or more generally, diagrams) of lattices with isogenies of a fixed type between them.  I suppose it's a rather awkward perspective, but it's hard to introduce a new language in 12 minutes.


TITLE: How to find f(x+a)?
QUESTION [1 upvotes]: Let f be a function defined by $$f(x)=\int_1^x\frac{e^t}{t}dt,x>0$$
Then we have to find the value of $$\int_1^x\frac{e^t}{t+a}dt$$
Here's what I did:
$$f(x)=\int_1^x\frac{e^t}{t}dt=\int_1^x\frac{e^{t+a}}{t+a}d(t+a)=$$
$$\implies\ \int_1^x\frac{e^t}{t+a}dt=e^{-a}f(x)$$
However, these are the options given:
a)$e^a[f(x+a)-f(1+a)]$
b)$e^{-a}[f(x+a)-f(1+a)]$
c)$e^a[f(x)-f(1+a)]$
d)$e^{-a}[f(x+a)-f(a)]$
(The square brackets are just for enhancing readability, not the floor function)
How do I proceed?

REPLY [2 votes]: It looks like you are doing a substitution in
$$\begin{align}
f(x) &= \int_{1}^x \frac{e^t}{t}\; dt = \int_{1 + a}^{x+a}\frac{e^{t+a}}{t+a}\; dt \\
&= -\int_{1}^{1+a} \frac{e^{t+a}}{x+a}\; dt + \int_1^{x+a} \frac{e^{t+a}}{t+a}\; dt. \\
&= -e^a\int_{1}^{1+a} \frac{e^{t}}{t+a}\; dt + e^a\int_1^{x+a} \frac{e^{t}}{t+a}\; dt. \\
\end{align}
$$
Can you take it from here?


TITLE: Inverse z-transform by convolution method
QUESTION [2 upvotes]: I've been asked to find the poles, impulse response of a system (in digital signal processing).
The transfer function was,
$$H(z) = \frac{z^2+z}{z^2-z+0.5}$$
I solved it by the partial fractions method as follows.
$$\color{blue}{H(z) = \frac{z(z+1)}{z^2-z+0.5}}$$
$$\begin{align} &\Rightarrow \frac{H(z)}{z} = \frac{z+1}{z^2-z+0.5}=\frac{z+1}{\left(z-(0.5+0.5i)\right)\left(z-(0.5-0.5i)\right)}
\\ &\Rightarrow \frac{z+1}{\left(z-(0.5+0.5i)\right)\left(z-(0.5-0.5i)\right)} = \frac{A}{z-(0.5+0.5i)} +\frac{A^*}{z-(0.5-0.5i)}\\ & \\
& A = 0.5 - 1.5i \text{ and } A^* = 0.5+1.5i \\ &
\\& \Rightarrow H(z) = (0.5-1.5i)\frac{z}{z-(0.5+0.5i)} + (0.5+1.5i)\frac{z}{z-(0.5-0.5i)} \\&
\\& \Rightarrow \color{blue}{h(n) = \left[(0.5-1.5)(0.5+0.1i)^n +(0.5+1.5i)(0.5-0.5i)^n\right]u(n)}\end{align}$$
(This can be further reduced to terms containing $\cos(kn)$ and/or $\sin(kn)$ but that wasn't required.)

Then as a continuum, I've been asked to find the impulse response (Inverse z-transform of $H(z)$) by convolution method.
We have,
$$H(z) = \frac{z(z+1)}{z^2-z+0.5}$$
If it were of the form, $\frac{z^2}{(z-a)(z-b)}$, we can consider $F(z) = \frac{z}{z-a}$ and $G(z) =\frac{z}{z-b}$, find $f(n) = a^nu(n)$ , $g(n) = b^nu(n)$. Then the inverse could be found by convoluting $f(n)$ and $g(n)$ easily.
But in this case, the term $z+1$ in the numerator makes it difficult to rewrite $H(z)$ as a product of 2 functions of $z$ whose inverse z-transform is known.

Can somebody help in finding $2$ such functions so that it could be evaluated by convolution method ? Or is it impossible to find the inverse z-transform of this function by convolution?

I also thought of using the fact $Z(a^n \sin(\omega n)) = \dfrac{az\sin\omega}{z^2-2az\cos\omega + a^2}$, but this left me behind with $z+1$.

REPLY [0 votes]: Thanks to my professor for providing me a hint (To split $\dfrac{z+1}{z-b}$ into $\dfrac{z}{z-b}$ and $\dfrac{1}{z-b}$ and then convolute)
$$ H(z) = \dfrac{z(z+1)}{z^2-z+0.5} = \dfrac{z(z+1)}{\left(z-(0.5+0.5i)\right)\left(z-(0.5-0.5i)\right)}$$
Let $a= 0.5+0.5i$ and $b= 0.5-0.5i$.
$$H(z) = \dfrac{z}{z-a}\cdot\dfrac{z+1}{z-b}$$
Let
$$\begin{align} & H_1(z) = \dfrac{z}{z-a} \Rightarrow \color{blue}{h_1(n) = a^nu(n) }\\&H_2(z) = \dfrac{z+1}{z-b}=\dfrac{z}{z-b}+z^{-1}\cdot\dfrac{z}{z-b}\Rightarrow \color{green}{h_2(n) = b^nu(n)+b^{n-1}u(n-1)}\\&
\\& h(n) = \color{blue}{h_1(n)}*\color{green}{h_2(n)} = \sum_{k=-\infty}^{\infty}a^ku(k)b^{n-k}u(n-k) + \sum_{k=-\infty}^{\infty}a^ku(k)b^{n-k-1}u(n-k-1)
\\&\Rightarrow h(n) =\sum_{k=0}^na^kb^{n-k} + \sum_{k=0}^{n-1}a^kb^{n-k-1} = b^n\sum_{k=0}^n\left(\frac{a}{b}\right)^k + b^{n-1}\sum_{k=0}^{n-1}\left(\frac{a}{b}\right)^k
\\&\Rightarrow\color{red}{h(n) = \left[\frac{a^{n+1}-b^{n+1}}{a-b} +\frac{a^n - b^n}{a-b}\right]u(n) = \left[\frac{a^n(a+1)-b^n(b+1)}{a-b}\right]u(n)}\end{align} $$
Subbing $a$ and $b$,
$$\begin{align}& h(n) = \frac{(0.5+0.5i)^n(1.5+0.5i)-(0.5-0.5i)^n(1.5-0.5i)}{i}u(n)
\\& \Rightarrow\color{blue}{h(n) = \left[(0.5+0.5i)^n(0.5-1.5i)+(0.5-0.5i)^n(0.5+1.5i)\right]u(n)}\end{align}$$


TITLE: Polynomial with "symmetrical" coefficients, and $\gcd(p,p')$
QUESTION [2 upvotes]: Consider the following polynomial:
$p(x) = x^6+x^5+2x^4+x^3+2x^2+x+1$. I would like to calculate $\gcd(p,p')$.
With Euclid's GCD algorithm, the calculation becomes very complicated, very quickly. I was wondering if the fact that the coefficient vector is "palindromic" could be of some use, but I didn't notice any interesting pattern while I was doing the calculation. Is there anything I'm missing?

REPLY [1 votes]: $p(x)=x^6 + x^5 +  x^4 +x^4+ x^3 + x^2 +x^2+ x + 1$
$p(x)=x^4(x^2+x+1)+x^2(x^2+x+1)+1(x^2+x+1)=(x^2+x+1)(x^4+x^2+1)=(x^2+x+1)[(x^4+2x^2+1)-x^2]=(x^2+x+1)[(x^2+1)^2-x^2]=(x^2+x+1)(x^2+x+1)(x^2-x+1)=(x^2+x+1)^2(x^2-x+1)$
$p'(x)=2(x^2+x+1)(2x+1)(x^2-x+1)+(x^2+x+1)^2(2x-1)=(x^2+x+1)(6 x^3-x^2+3 x+1)$
Let $q(x)=6x^3-x^2+3x+1$
$q(\pm1)\ne 0;\;q\left(\pm\frac12\right)\ne 0;\;q\left(\pm\frac13\right)\ne 0;\;q\left(\pm\frac16\right)\ne 0$
$q(x)$ has no rational roots therefore it is irreducible in $\mathbb{Q}$
$\text{GCD}(p(x),p'(x))=x^2+x+1$
Hope this helps


TITLE: How to prove an Isomorphism for a G/N (N normal) to H subgroup of G
QUESTION [0 upvotes]: Let G be a group and let $N \subseteq  G$ be a normal subgroup. Suppose there is a subgroup $H \subseteq G$ such that:
$$ HN= G $$
$$ H \cap  N = \{e \} $$
Prove tat H is a system of representatives for the cosets of N in G, and that $ G/N \cong H$.
Does anyone know how I should do this?

REPLY [0 votes]: It's a direct application of the second isomorphism theorem. It states:
Let $G$ be a subgroup, $H$ be a subgroup of $G$ and $N$ be a normal subgroup of $G$. Then $H/{H \cap N} \cong HN/N$. This isomorphism is given by sending $h(H \cap N)$ to $hN$.
In your case, $H \cap N$ is trivial, so $H/{H \cap N}=H$ and since $HN = G$, $HN/N = G/N$. So
$$H/{H \cap N} = H \cong HN/N = G/N, \ h \mapsto hN.$$


TITLE: What is a differential operator?
QUESTION [2 upvotes]: Let $X$ be a real $C^{\infty}$-manifold.
Define $C_c^{\infty}(X)$ to be the $\mathbb{C}$-vector space of all morphisms of manifolds $X \rightarrow \mathbb{C} = \mathbb{R}^2$ which are compactly supported.
What is the meaning of a differential operator on $C_c^{\infty}(X)$?

REPLY [3 votes]: Those functions having compact support or not is irrelevant, the definition is the same, so let us focus on the larger space $C ^\infty (X)$.
A linear map $P : C ^\infty (X) \to C ^\infty (X)$ is a differential operator if and only if in every patch of coordinates $U$ we can write, for all smooth $f$ (and in multi-index notation),
$$(Pf) (x) = \sum _{|\alpha| \le N_U} c_\alpha (x) (\partial _\alpha f) (x)$$
for some $N_U \in \Bbb N$ (that may depend on $U$) and $c_\alpha \in C ^\infty (U)$ for all $\alpha$.
If the $N_U$ (that correspond to all the coordinate patches) are bounded by some $N$, then we say that $P$ has order at most $N$. Notice that the maximum order $N_U$ may, in principle, vary from one coordinate patch to another.


TITLE: Finding a conformal mapping with certain points explicitly mapped
QUESTION [2 upvotes]: I have experience finding mappings from a domain in $\mathbb{C}$ to another domain in $\mathbb{C}$ by composing conformal maps that I do know. However, I do not have any experience with the following type of problem and am curious how to enforce the conditions that certain points map to certain points.

Find a conformal map that sends the upper half plane $\{\Im z > 0\}$ to the unit disk $\{|z| < 1\}$ such that it sends $1 + i$ to $0$ and $−1 +i$ to $1/\sqrt{2}$.

My first idea was to use the conformal mapping
$$G(z) = \cfrac{z-i}{z+i}$$
which maps the upper half plane to the unit disk. Multiply it by a scaling factor $\alpha$ with $|\alpha| = 1$ will preserve this mapping, but I'm not sure how to proceed or even if this is the correct idea in the first place.

REPLY [0 votes]: You need a special bilinear transformation of the type $w(z)=k.\frac{z-a}{z-\overline{a}}$ where $a$ is a zero of $w(z)$. In your case $a=1+i$
so $w(z)=k.\frac{z-(1+i)}{z-(1-i)}$. To determine $k$, use $w(-1+i)=\frac{1}{\sqrt 2}$


TITLE: Fock space vs. wavefunctionals
QUESTION [11 upvotes]: There are at least two representations of the Hilbert spaces of quantum field theory. For a scalar field, we have
The Fock space representation, such that every state is represented as the Fock space of 'one particle' representations,
$$\mathcal H = \bigoplus_{n = 0}^\infty \text{Sym}(\mathcal H_1^{\otimes n})$$
with $\mathcal H_1^0 = \mathbb C$ and $\mathcal H_1 = \mathcal L^2(\Bbb R^3)$.
The wavefunctional representation, such that every state is represented by a functional on the space of configurations of the field on $\Bbb R^3$ which is square integrable with respect to some measure
$$\mathcal H = \mathcal L^2(\mathcal F[C(\Bbb R^3)], d\mu[\phi])$$
Since those two representations describe the same theory, I am guessing that there is some isomorphism between the two, but what would it be?

REPLY [7 votes]: The two representations are not equivalent, except for free fields, and hence in perturbation theory.
Nonperturbatively, the Fock space representation is inappropriate (because of Haag's theorem, which asserts that the Hilbert space of an interacting relativistic quantum field theory has no natural Fock space structure; see the discussions at Haag's theorem and practical QFT computations and State space of interacting theories) whereas the wave functional representation (i.e., the functional Schroedinger picture) may still work - it can capture a lot of nonperturbative information such as instantons.
In the functional Schroedinger picture, states of a QFT are treated as functionals of the field coordinates in the same way as states in QM are treated as functions of the position coordinates. A thorough discussion of the functional Schroedinger picture is in the article by Jackiw,  Analysis on infinite dimensional manifolds: Schrodinger representation for quantized fields (p.78-143 of the linked document). A problem is that the infinite-dimensional measure is not really well-defined, it is given formally (i.e., nonrigorously) by a functional integral.


TITLE: The Cause of lightning and charge distribution in clouds
QUESTION [4 upvotes]: I was going through this video about lightning and I couldn't understand some points .
1:  What caused the water molecules in ice crystals to be arranged in that specific pattern i.e. having positive charges at its boundary and negative in the inner region ?

2: Also WHY do the crystals break (which created or may have led to the distribution of charges in the way given in the figure) ? (Since the outer regions have positive charges two crystals approaching each other should finally come at rest before striking each other and no collision should occur).

I have also referred to the Wikipedia page and still have the same confusion . What is the cause of  distribution of charges in saich a pattern  (as shown in the figure) ?

REPLY [0 votes]: Assuming that the lightning occurs at the boundary or near boundary between the region of sky experiencing cold weather and the region of sky experiencing warm or hot weather, winds from the warmer side tends to move to the cold side. I'm the same manner, wind from the cold side moves towards the warmer side. When these winds (cold and warm) meet, they tend to collide which due to charges carried by them produces "sparks" due to friction between them. These sparks are seen as lightning.
It is important to understand that these winds are the ones driving clouds thus it could be the reason you have lightning on a cloudy day.


TITLE: Absolutely continuous and derivative of measure
QUESTION [0 upvotes]: Let $\mu$ be a Borel measure on $[1,2]$ such that $\mu(a,b)=Ln(b)-Ln(a)$ for every $a,b\in[1,2]$.Show that $\mu<<\lambda$,where $\lambda$ is the lebesgue measure,and find $d\mu/d\lambda$.
If we can prove that $\mu<<\lambda$,then we can define $h(x)=\mu[1,x]$.So we know for bounded interval $[a,b]$ in $[1,2]$ we have $\int_{[a,b]} h'(x)d\lambda=\mu([a,b])$.And this quality is valid for every borel set in $[1,2]$.$d\mu/d\lambda=\dfrac{1}{x}$.I don't know how to prove the $\mu$ is absolutely continuous with respect to $\lambda$.

REPLY [1 votes]: If you want to directly prove it, you can suppose $\lambda(E)=0$. Take a cover of $E$ by open intervals $I_k$ with $\sum_k \lambda(I_k)<\epsilon$. Find a bound for $\sum_k \mu(I_k)$ (probably something like $\sum_k \mu(I_k) < C \epsilon$). Conclude that $\mu(E)=0$.
If you want to indirectly prove it, you can just note that you've already written down $\frac{d \mu}{d \lambda}$, and therefore if $\lambda(E)=0$ then $\mu(E)=\int_E \frac{d \mu}{d \lambda} d \lambda = 0$.


TITLE: Solving a challenging differential equation
QUESTION [5 upvotes]: How would one go about finding a closed form analytic solution to the following differential equation?
$$\frac{d^2y}{dx^2} +(x^4 +x^2+x+c)y(x) =0 $$
where $c\in\mathbb{R}$

REPLY [2 votes]: This is the way I would do it.
Let $p(x)=x^4+x^2+x+c$. Put $z=y'$. Then the equation is equivalent to the system
$$
\begin{bmatrix}y\\ z\end{bmatrix}'=\begin{bmatrix}0&1\\-p(x)&0\end{bmatrix}\,\begin{bmatrix}y\\ z\end{bmatrix}.
$$
Let us write $A(x)$ for the $2\times 2$ matrix above. For a given vector $\begin{bmatrix}c_1\\ c_2\end{bmatrix}$, a solution will be given by
$$
e^{B(x)}\,\begin{bmatrix}c_1\\ c_2\end{bmatrix},
$$
where $B'(x)=A(x)$. That is $B(x)=\begin{bmatrix}0&x\\-q(x)&0\end{bmatrix}$, with $q(x)=x^5/5+x^3/3+x^2/2+cx$. If I didn't make a mistake, the exponential is
$$
e^{B(x)}=\begin{bmatrix}\cos\sqrt{xq(x)}&\sqrt\frac{x}{q(x)}\,\sin\sqrt{xq(x)}\\
-\sqrt\frac{q(x)}{x}\,\sin\sqrt{xq(x)}&\cos\sqrt{xq(x)}\end{bmatrix}.
$$
As $y$ will be the first coordinate of $e^{B(x)}\begin{bmatrix}c_1\\ c_2\end{bmatrix}$, we get
$$
y(x)=c_1\,\cos\sqrt{\frac{x^6}5+\frac{x^4}3+\frac{x^3}2+cx^2}+c_2\,\frac{\sin\sqrt{\frac{x^6}5+\frac{x^4}3+\frac{x^3}2+cx^2}}{\sqrt{\frac{x^5}5+\frac{x^3}3+\frac{x^2}2+cx}}.
$$