TITLE: Which is the correct postfix expression for $a\;+\;b\;*\;(\;c\;+\;d\;)\;+\;e\;*\;f$
QUESTION [0 upvotes]: Most computer algorithms turn $a+b*(c+d)+e*f$ into $a\, b\, c\, d + * + e f * + $.
But this performs an addition before a multiplication.
If you follow order of operations, shouldn't the expression actually be:
$$a\; b\; c\; d\; +\; *\; e\; f\; *\; +\; +\;$$

REPLY [2 votes]: In infix notation, the expression $x + y + z$ is technically ambiguous because it could refer to either $(x + y) + z$ or to $x + (y + z)$. Of course, we do this precisely because we like the ambiguity as these two expressions yield the same result and we don’t want to think about how to place the parentheses all the time.
When translating them to postfix notation, you need to make a choice, though. The first option leads to $x~ y + z~ +$ and the second to $x~y~ z + +$.
Note that this is precisely your example with
$$\begin{align*}
 x &= a\\
y &= b \times (c + d) = b~c~d + \times \\
z &= e \times f = e~f~ \times
\end{align*}$$
So the order of operations (multiplication before addition) really does not have much to do with it.


TITLE: A property of limit supremum
QUESTION [2 upvotes]: I am just reading about limit supremum concept in Rudin.
Rudin defines the limit supremum as follows:
Let $\{a_n\}$ be a sequence in $[\infty,\infty]$.
$b_k = \sup \{a_k, a_{k + 1}, \ldots, \}, \ldots (k = 1,2,3, \ldots)$
$\beta = \lim \sup = \inf \{b_1, b_2, \ldots, \}$
There is something that I am confused about. It states that limit supremum is the largest number with the property that there is a subsequence
$\{a_{n_i} \}$ of $\{a_n\}$ such that $a_{n_i}$ such that $a_{n_i} \rightarrow \beta$ as $i \rightarrow \infty$, and $\beta$ is the largest number with this property. I don’t understand how to prove that this property.

REPLY [2 votes]: 1) Extract a subsequence $b_k$ from the definition of $\beta$ that converges to the infimum $\beta$.
2) Extract subsequences $a_{k_n}$ from $a_n$ which converge to $b_k$ for each $k$.
3) Pick any positive sequence $\epsilon_k\rightarrow 0$, and for each $k$, find an $i$ such that  $|a_{k_i}-b_k|<\epsilon_k$.
4) With the above subsequence of $a_n$, conclude the result by invoking the triangle inequality on the appropriate terms.
To show $\beta$ is the largest such number you can assume by contradiction that there's a $\gamma>\beta$ with the same property. This would give you a subsequence $a_{m_k}$ that converges to $\gamma$. This means that at some point $a_{m_k}>\beta+\epsilon$ for all $k\geq N$ (where say, $\epsilon=(\gamma-\beta)/2$). This implies that $b_{m_k}>\beta+\epsilon$ for all $k>N$, and hence the infimum over all such $\beta_k$ would be strictly greater than $\beta$, a contradiction.


TITLE: If $ a,b,c \gt 0 $ and $ \frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1} = 1 $ Prove $ abc \geq 8 $
QUESTION [1 upvotes]: If $ a,b,c \gt 0 $  and  $ \frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1} = 1 $
Prove $ abc \geq 8 $
I have tried AM-GM and substituting the 1, without results.

REPLY [3 votes]: Let
$$x = \frac{1}{a+1}, \quad y = \frac{1}{b+1},  \quad z = \frac{1}{c+1},$$
then $x+y+z=1$ and
$$a = \frac{1-x}{x} = \frac{y+z}{x}.$$
The inequality become
$$\frac{(x+y)(y+z)(z+x)}{xyz} \geqslant 8.$$
Which is true because
$$\frac{(x+y)(y+z)(z+x)}{xyz} \geqslant \frac{2\sqrt{xy} \cdot 2\sqrt{yz} \cdot 2\sqrt{zx}}{xyz} = 8.$$
The proof is completed.


TITLE: Find point of intersection of two gradients
QUESTION [0 upvotes]: I have four points $A$, $B$, $C$, $D$ on the Cartesian plane, with coordinates $(x_a,y_a)$, $(x_b,y_b)$, $(x_c,y_c)$, $(x_d,y_d)$. The lines $AB$, $BC$, $CD$ all have a gradient greater than or equal to $0$. Thus the implied gradient at B is the gradient $AC$, and the gradient at $C$ is the gradient $BD$.
How do I find the point of intersection of the gradients at $B$ and $C$? I spent a while faffing around with trig functions but ended up in endless recursive calculus-style loops. I suspect I’m missing something embassassingly obvious - perhaps because I’m on holiday and excessively relaxed :-)
Would appreciate some pointers, even though it’s high school level or less.

REPLY [0 votes]: You find the line equation of two lines then you solve these simultaneously. For the line at B, $$y-B_y=m_1(x-B_x)$$ and $$m_1=\frac{C_y-A_y}{C_x-A_x}$$ For the line at C $$y-C_y=m_2(x-C_x)$$ and $$m_2=\frac{D_y-B_y}{D_x-B_x}$$ Just plug in numbers for the points and then solve the two equation simultaneously for $x$ and $y$. Caveat: as stated in question, slopes are positive.

REPLY [0 votes]: Write the two lines as functions of x:
$$y_{AC}(x) = y_B + (x - x_B)\frac{y_C - y_A}{x_C - x_A}$$
and
$$y_{BD}(x) = y_C + (x - x_C)\frac{y_D - y_B}{x_D - x_B}$$
The intersection occurs at $x$,
$$y_{AC}(x) = y_{BD}(x)$$
If you expand all the terms, and move the coefficients (multipliers) of $x$ to the left side, and the others to the right side, you can divide both sides by the coefficients of $x$ to get the $x$ coordinate of the intersection point.
Insert into $y_{BD}(x)$ or $y_{AC}(x)$ to get the $y$ coordinate; both will give the same result.


TITLE: Range of root of cubic equation having least absolute value
QUESTION [5 upvotes]: Suppose $a$ and $b$ are two positive real numbers such that the roots of the cubic equations $x^3-ax+b=0$ are all real. Let $\alpha$ is a root of this cubic equation with minimum absolute value. Then range of values of $\alpha$ is given by(choose the correct option)
$(A)$ $\frac{2b}{3a}<\alpha \leq \frac{b}{a}$
$(B)$ $\frac{b}{a}<\alpha \leq \frac{3b}{2a}$
$(C)$ $-\frac{b}{a}<\alpha \leq \frac{b}{a}$
$(D)$ $-\frac{b}{a}<\alpha \leq \frac{2b}{3a}$
This question has been asked on this site but answers use Viete's theorem which I am not familiar with.
Now as product of roots is negative, hence we will have either three roots negative or two roots positive and one negative but as sum of roots is $0$, hence we wil have two roots positive and one root negative.
Then I tried finding points of $f'(x)=0$ for $f(x)=x^3-ax+b$ to get $x=\pm \frac{\sqrt{a}}{\sqrt{3}}$ out of which one gives local maxima and other gives local minima. I drew the rough graph and I think the first positive root will be $\alpha$ but how to get desired range?

REPLY [3 votes]: Let $\alpha,\beta,\gamma$ be the solutions of $x^3-ax+b=0$ with $|\alpha|\le|\beta|$ and $|\alpha|\le|\gamma|$.
By Vieta's formula,
$$\alpha+\beta+\gamma=0,\quad \alpha\beta+\beta\gamma+\gamma\alpha=-a\lt 0,\quad \alpha\beta\gamma=-b\lt 0$$
Since $\alpha\beta\gamma\lt 0$, we have either that only one of them is negative or that all are negative.
It is impossible that all three are negative because of $\alpha\beta+\beta\gamma+\gamma\alpha\lt 0$.
So, we see that only one of them is negative.
Suppose here that $\alpha\lt 0\lt\beta\le\gamma$ with $|\alpha|\le|\beta|$.
Then, since $\gamma=-\alpha-\beta$, we have
$$\alpha\lt 0\lt\beta\le -\frac{\alpha}{2}\implies |\alpha|\le|\beta|\le \left|\frac{\alpha}{2}\right|$$which is impossible.
So, we may suppose that $\beta\lt 0\lt\alpha\le \gamma$ with $|\alpha|\le|\beta|$.
Since $\gamma=-\alpha-\beta$, we have
$$\beta\lt 0\lt\alpha\le -\frac{\beta}{2}\tag1$$
Now, since we have $$a=\alpha^2+\alpha\beta+\beta^2\quad\text{and}\quad b=\alpha\beta(\alpha+\beta)$$
and
$$(1)\implies \beta\lt\alpha\le-\frac{\beta}{2}\implies (\alpha-\beta)(2\alpha+\beta)\le 0\implies 2\alpha^2\le \alpha\beta+\beta^2$$
we have
$$\alpha=\alpha\times 1\gt \alpha\times \frac{(\alpha\beta+\beta^2)}{\alpha^2+(\alpha\beta+\beta^2)}=\frac{\alpha\beta(\alpha+\beta)}{\alpha^2+\alpha\beta+\beta^2}=\frac ba$$
$$\alpha=\alpha\times 1\le \alpha\times\frac{\alpha\beta+\beta^2+(2\alpha\beta+2\beta^2)}{2\alpha^2+(2\alpha\beta+2\beta^2)}=\frac{3\alpha\beta(\alpha+\beta)}{2(\alpha^2+\alpha\beta+\beta^2)}=\frac{3b}{2a}$$
$$\alpha=\alpha\times 1\gt \alpha\times\frac{(2\alpha\beta+2\beta^2)}{3\alpha^2+\alpha\beta+\beta^2+(2\alpha\beta+2\beta^2)}=\frac{2\alpha\beta(\alpha+\beta)}{3(\alpha^2+\alpha\beta+\beta^2)}=\frac{2b}{3a}$$
It follows from these that $\color{red}{(B)}$ is the only correct option.


TITLE: Evaluate $\lim_{x \to 0^-} \left( \frac{1}{x} - \frac{1}{|x|} \right)$ (possible textbook mistake - James Stewart 7th)
QUESTION [3 upvotes]: I was working on a few problems from James Stewart's Calculus book (seventh edition) and I found the following:

Find
$$\lim_{x \to 0^-} \left( \frac{1}{x} - \frac{1}{|x|} \right)$$

Since there's a $|x|$ on the limit and knowing that $|x| = -x$ for any value less than zero, we have
$$\lim_{x \to 0^-} \left( \frac{1}{x} - \frac{1}{|x|} \right) = \lim_{x \to 0^-} \frac{2}{x}$$
So far so good. Continuing,
$$\lim_{x \to 0^-} \left( \frac{1}{x} - \frac{1}{|x|} \right) = \lim_{x \to 0^-} \frac{2}{x} = - \infty$$
since the denominator becomes smaller and smaller. When checking the textbook's answer I've found the following:

Am I missing something or should the limit really be $- \infty$ ?

REPLY [1 votes]: I agree that the limit is negative infinity. I could understand "does not exist" if the question was asking for a two-sided limit, but it clearly isn't. It's asking for the left-hand limit. The text differentiates between specifically identifying ± infinite limits and non-existent limits, so it should be consistent in the solution manual. I just burned an hour trying to figure out if this was some strange concept that I missed... and I'm the teacher! Glad I found this thread!


TITLE: questions on Néron-Tate canonical height
QUESTION [7 upvotes]: I have three questions regarding height pairings:

In [Serre, Lectures on the Mordell-Weil theorem], p. 85 f., it is stated that the following function is a local height function:
"Let $V/R$ be a scheme over a discrete valuation ring, $D$ a divisor on $V$ and $x \in V(R)$. Assume $x \not\in \mathrm{supp}(D)$. Define $m(x,D)$ as follows:
a) If $x$ does not intersect $D$, $m(x,D) = 0$.
b) If $x$ intersects $D$ in a point $x_0$ of the special fibre, then $m(x,D)$ is the intersection multiplicity of $x$ and $D$ and $x_0$.
Then $x \mapsto m(x,D)$ is a local height associated to $D$." Does anyone have a reference for this?
Why is for a curve $X/k$ and an Abelian variety $B/k$ the Néron-Tate canonical height of the constant Abelian variety $B \times_k X$ over $X$ and $x: X \to B$ and $\mathcal{L}: X \to B^\vee$
$$\hat{h}(x,\mathcal{L}) = \mathrm{deg}_X((x,\mathcal{L})^*\mathcal{P}_B)$$ with the Poincaré bundle $\mathcal{P}_B \in \mathrm{Pic}(B \times_k B^\vee)$?  The degree function $\mathrm{deg}: \mathrm{Pic}(X) \to \mathbf{Z}$ is the usual one for a curve.
We have (functoriality of the height) $\hat{h}_{f^*(\mathcal{M})} = \hat{h}_{\mathcal{M}} \circ f$. Can one prove this also with the other definition of the height in 2.?

REPLY [7 votes]: See Chapter 2 of the book by E. Bombieri and W. Gubler, Heights in Diophantine Geometry.
They begin classically: they first define local heights (§2.2), then global heights (§2.3), and finally compare their global heights with Weil's definition (§2.4).
Later, §2.7 gives the alternate point of view  of Arakelov geometry on local heights,
which should contain what you want.
Indeed, they define a local height with respect to a Néron divisor (2.7.9)
while Example 2.7.20 explains how models over DVRs give rise to Néron divisors.


TITLE: Is there some sort of correspondence between groups and partitions of a set?
QUESTION [9 upvotes]: Every group action on a set $S$ partitions the set into orbits.  Conversely, for every partition of $S$ is there a group action such that the set of orbits of the group action equals the partition?
My attempt.  Let $P = \{S_1,\dots, S_k\}$  be a partition of a finite set $S$ of order $n$.  Then there are elements of $G = Perm(S)$, the set of permutations of $S$, that leave each subset fixed, i.e. $g\in G$ such that $g\cdot S_i = \{gs : s\in S_i\} = S_i, \forall i$.  Think of the permutations that fix all of $S$ except permutes $S_i$ possibly in some nontrivial way.  If $g, h$ are such elements then $gS_i = S_i, \forall i$, so $g^{-1} S_i = S_i$, the action also being an action on the subsets.  Similarly $g\cdot h S_i = g S_i = S_i$.  Thus, the set of all $P$-stabilizing elements is a subgroup of $G$.
Groups are known in correspondence with subgroups of $G$.  Please comment.
Motivation: is there a group-theoretical way to count partitions of a set of size $n$?  So that maybe it can help prove formulas about the latter.
According to m_l in a comment, there's no application here to counting partitions here that doesn't lead to having to count the partitions the known ways.
I was thinking, we haven't considered yet, at least I haven't, the set of partitions of $S$ itself, call it $P(S)$, and the group $G = Perm(S)$ acting on it.  The nice thing about $G = Perm(S)$ is that every finite group is isomorphic to a subgroup of it.  So if $H \leqslant G$, and $H'$ is the group presented in some other way, then almost anything we say about $H$ can be applied to $H'$ regarding group actions on $S$ or $P(S)$.  Hopefully, so let's keep that in the back of our minds.  In other words, every partition corresponds to a partition of the set of subgroups of $G$.  But we should say more about it than that.  I'm moving off track here, so continuing on...
Define the action of $G$ on $P(S), $ to be $g \cdot P = \cup_{i=|P|} \{ g\cdot S_i \}$, where $g\cdot S_i$ is the element $g$ acting on the block $S_i$ suing simple coset multpilcation.  Relatedly there's an obvious way to make $G$ act on the set of all subsets of $S$.
Anyway.  As you can tell the action on $P(S)$ defines a group action.  Proof:
The identity permutation obviously fixes a partition.  And $g(h P) = g\cdot\cup_{i=1..|P|} \{ h\cdot S_i \}$.  Note that since $g$ acts on the set of subsets of $S$, $g(hP) = (gh)P. \ $  The rest of the proof is left to the reader.
Let's switch notation a bit.  $P\in P(S)$ will now be called $p$, and $P(S)$ will be called $P$.
An orbit is simply $O_p = G\cdot p \subset P(S)$.  We have the class equation
$|P(S)| = \sum_{orbits} |O_p|$
Burnside's Lemma:
# orbits $ = 1/|G| \sum_{g\in G}|P^g|, \ $ where $P^g$ is the set of all partitions fixed by $g$.
and the index counting formula
$|G| = |H_p||O_p| = |H_p|[G:H_p], \ $ where $H_p = Stab(p)$ is the stabilizer of the partition $p$.

REPLY [3 votes]: Let $S$ be a set (not necessarily finite) and $\mathcal{P}=\{P_i\}_{i\in I}$ some partition of $S$. Define
$$G_i:=\{f:P_i\to P_i\ |\ f\mbox{ is invertible}\}$$
With standard function composition $G_i$ is a group. If $P_i$ is finite then it is the standard symmetric group $S_{|P_i|}$. It acts on $P_i$ via $(f, x)\mapsto f(x)$. You can easily check that $P_i$ is transitive (i.e. it has only one orbit) under this action.
Now put $G:=\prod G_i$ and define the action
$$\big((f_i), x)\big)\mapsto f_j(x)\mbox{ if }x\in P_j$$
You can easily check that $S/G=\mathcal{P}$.
Side note: If we assume the Axiom of Choice or assume that each $P_i$ is at most countable then we can make $G$ smaller. Just define $G_i:=P_i$ with any group structure and put again $G:=\prod G_i$. Note that the statement "any set can be turned into a group" is equivalent to the Axiom of Choice. However it is true for at most countable sets independent on the Axiom of Choice.
Side note2: The $G$ can be refined even more if each $P_i$ is finite and $I$ is finite. Define $G:=\mathbb{Z}_n$ where $n=lcm(|P_i|)$ (least common multiple). Since $P_i$ is equinumerous with $G/H$ for some $H$ then it can be easily equipped with transitive action. That's probably the smallest $G$ we can get for finite case.
Side note3:

The nice thing about $G=Perm(S)$ is that every finite group is isomorphic to a subgroup of it.

No. That's not a nice thing. It actually is an epicly horrible thing, because it means that proving anything about $G$ is at least as hard as proving anything about any other group.


TITLE: How to find the new parameters of a gamma distribution after scaling?
QUESTION [0 upvotes]: I understand this question has been asked a couple of times, but from what I am seeing, the parameters shown are different so I am not sure if I am on the right track.
My question goes like this: Given X has a gamma distribution with parameters $\alpha$ and $\theta$, then Y = cX has a gamma distribution with parameters $\alpha$ and c$\theta$.
My approach was to use the cdf such that P(cX $\leq$ y),which results in F$_{x}$($\frac{y}{c}$). But after expanding it out, I do not know how to substitute into the gamma function, which requires integration.

REPLY [2 votes]: If $X$ has Gamma-distribution with parameters $\alpha$ and $\theta$ then its PDF on support $(0,\infty)$ takes the form:$$f_X(x)=\frac1{\Gamma(\alpha)\theta^{\alpha}}x^{\alpha-1}e^{-\frac{x}{\theta}}$$and is (as usual) the derivative of the corresponding CDF.
Let $c$ be a positive constant.
Taking the derivative of $F_{cX}(x)=F_X(\frac{x}{c})$ we find by taking the derivative and applying the chain-rule:$$\frac1cf_X\left(\frac{x}c\right)=\frac1{\Gamma(\alpha)\eta^{\alpha}}x^{\alpha-1}e^{-\frac{x}{\eta}}$$on support $(0,\infty)$ where $\eta:=c\theta$.
This is evidently the PDF of Gamma-distribution with parameters $\alpha$ and $\eta=c\theta$.


TITLE: A particle travels at velocity $|t - 1|$ at time $t$.
QUESTION [0 upvotes]: Question: A particle travels at velocity $|t - 1|$ at time $t$. Divide the interval $[0, 2]$ into $2k$ intervals of equal length where $k\in\mathbb{N}$. Find the minimum velocity of the particle on each of these time intervals.
My approach to this question is to experiment with the numbers. For example, if $k = 1$, if $k = 2$, if $k = 3$, etc... And I think that you would have to find the derivative of the velocity of the particle to find the minimum velocity.
But I am not really sure how to approach from here.
Any help will be appreciated!

REPLY [1 votes]: Hint
For $t < 1,$ the particle's speed is decreasing, as it approaches $t = 1$, which implies that
you want which end of the interval for minimum velocity?
For $t > 1,$ everything is symmetrically the opposite.
No need to take derivatives.


TITLE: What is an example of a colimit-dense generator which is not dense?
QUESTION [5 upvotes]: An object $G$ of a category $\mathcal{C}$ is a dense generator if every object $X$ is the colimit of the canonical diagram of copies of $G$ mapping to $X$. (This canonical diagram is indexed by the full subcategory of the slice $\mathcal{C}_{/X}$ on the objects of the form $G \to X$.)
An object $G$ is called a colimit-dense generator if every object $X$ is a colimit of some diagram of copies of $G$. (That means $X$ is the colimit of some functor $F : \mathcal{I} \to \mathcal{C}$ with $F(i) = G$ for all objects $i$.)
Is there an example of a colimit-dense generator which is not a dense generator?

REPLY [9 votes]: $\Bbb R$ is colimit-dense in the category of real vector spaces but not dense
(see 6.F, 6.34 in my book with J. Adámek "Locally presentable and accessible categories").


TITLE: If $X,Y$ are two independent random variables how can you calculate $\mathbb{E}[e^{XY}]$
QUESTION [0 upvotes]: Let $X,Y$ be two independent random variables where $X$ is standard normal distributed and $Y$ is distributed as $P(Y=1)=P(Y=-1)=\frac{1}{2}$  how can one calculate $\mathbb{E}[e^{XY}]$? I don't see how to use the joinst density of $X,Y$ to find the expectation (since one is continious and the other is discrete). I also don't see how I can factor the density since we dont have $\mathbb{E}[f(X)g(Y)]=\mathbb{E}[f(X)]\mathbb{E}[g(Y)]$ but rather $\mathbb{E}[h(X,Y)]$.

REPLY [1 votes]: \begin{align}
\mathbb{E}\big[e^{XY}\big]&= \mathbb{E}\left[\mathbb{E}\left[e^{XY}\big|Y\right]\right]\\
&= \frac{1}{2}\mathbb{E}\left[e^{XY}\big|Y=-1\right]+ \frac{1}{2}\mathbb{E}\left[e^{XY}\big|Y=1\right]\\
&= \frac{1}{2}\mathbb{E}\left[e^{-X}\right]+ \frac{1}{2}\mathbb{E}\left[e^{X}\right]\\
&=\frac{1}{2\sqrt{2\pi}}\int_{-\infty}^\infty\big(e^{-x}+e^x\big)e^{-\frac{x^2}{2}}dx\\
&= \frac{1}{2\sqrt{2\pi}}\int_{-\infty}^\infty e^\frac{1}{2}\big(e^{-\frac{(x+1)^2}{2}}+e^{-\frac{(x-1)^2}{2}}\big)dx\\
&=e^\frac{1}{2}
\end{align}


text:
So far, we have only considered situations in which each user accesses exactly one cache, with no flexibility.
However, in a wireless heterogeneous network such as the one in \figurename~\ref{coded:fig:hetnet}, the density of access points that have caches could be high enough for each user to potentially access a large number of caches.
This enables some interesting capabilities that can be harnessed to achieve a lower broadcast rate $R$ for the same cache memory $M$.
For instance, each user could have access to the contents of multiple caches at once, effectively increasing the memory available to it.
Alternatively, we could allow the system to adaptively assign to each user one cache out of a set of nearby caches, based on the file that it requested.
In this section, we explore the latter approach in detail as studied in \cite{HKMDadaptive}, and leave the former as a short discussion at the end.

\subsection{Overview of Adaptive User-to-Cache Matching}

In the adaptive matching setup, we keep the restriction of each user accessing the contents of exactly one cache, but allow the flexibility of choosing which cache (possibly among some subset of caches) the user should access based on its requested file.
Such a problem was studied in \cite{leconte2012, moharir2016}, in the extreme case where all users are able to access any cache.
An additional restriction is a load constraint on the caches: each cache can only serve at most one user.
The surprising insight in both papers is that, contrary to the ``static matching case'' where each user is pre-attached to a unique cache (the setting described in Section~\ref{coded:sec:overview}), an approximately-optimal scheme is to replicate complete files across multiple caches in proportion to their popularity in the placement phase;, and then during the delivery phase, match as many users as possible to a cache that holds its requested file.

We thus observe a dichotomy between two extremes: in the static matching case (when each user is restricted to one cache), appropriate splitting of files and careful placement of subfiles to enable coded-multicast transmissions during delivery as described in Section~\ref{coded:sec:overview} is approximately optimal, while simple file replication is not; on the other hand, in the fully ``adaptive matching case" where each user can be matched to any cache during the delivery phase, appropriate file replication coupled with maximum matching during delivery is approximately optimal, while a static pairing of users and caches along with the coded caching approach of Section~\ref{coded:sec:overview} is sub-optimal.
The natural next question is then: what happens when each user can be matched adaptively to one of a \emph{subset} of caches?
This problem was studied in \cite{HKMDadaptive}, and we will discuss its main results here.

\subsection{System Model}
\label{Sec:sysmodeladapmat}
\begin{figure}
\centering
\includegraphics[scale=\codedsetupfigsscale]{setup-adaptive.pdf}
\caption{Partial adaptive matching setup.
The caches are partitioned into clusters, and each user can be matched to one cache in its cluster, with a load constraint on the caches.
Excess users in a cluster cannot be matched, such as the user colored in grey.}
\label{coded:fig:adaptive-setup}
\end{figure}

Suppose there is a content library of $N$ files, called $W_1,\ldots,W_N$.
There are $K$ caches, partitioned into $K/d$ mutually exclusive \emph{clusters} of $d$ caches each (assume $d$ divides $K$).
At each cluster $c$, there is a stochastic number of users $u_n(c)$ that request file $W_n$, where $u_n(c)$ is a Poisson random variable of parameter $\rho d/N$, with $\rho\in(0,1/2)$ a constant.
Thus at every cluster (whose size is $d$ caches), the expected number of users is $\rho d$.
We will refer to $\mathbf{u}=\{u_n(c)\}_{n,c}$ as the \emph{user profile}.

In addition to the usual placement and delivery phases, there is an intermediate \emph{matching phase}, which occurs after the users have made their requests.
In this phase, we assign each user in a cluster to one cache in the same cluster, subject to a load constraint of no more than one user per cache.
Thus if there are more users than caches in a cluster ($\sum_n u_n(c)>d$ for some $c$), there will necessarily be some unmatched users who will have access to the contents of no cache.
Note that the placement phase occurs without knowing the user profile, while both the matching phase and the delivery phase have of knowledge of the user profile.

Let $R_\mathbf{u}$ denote the broadcast rate given a specific user profile $\mathbf{u}$.
We are interested in the expected rate $\bar R = \mathbb{E}_\mathbf{u}[R_\mathbf{u}]$, and more specifically  the optimal expected rate $\bar R^\star(M)$ for every memory $M$ over all possible placement, matching, and delivery strategies.

The choice of a Poisson number of users is useful as it not only more closely models real-world user requests, but also simplifies the analysis in this problem.
There is also little difference, fundamentally, between the Poisson model and the model with a fixed number of users (such as the one studied in the previous sections), as long as the cluster size $d$ is large enough, namely $d=\Omega(\log K)$.
This means that comparisons with other works in the literature are possible.
Note that for smaller $d$, the Poisson model is less meaningful; when $d=1$ for instance, there is positive probability for each cluster to have more than one user, which means that with high probability, a significant fraction of the users cannot be matched to any cache and resultantly a high server transmission rate is necessary irrespective of the cache memory size.

As mentioned above, the Poisson model only makes sense for $d=\Omega(\log K)$, and so we adopt this regularity condition in this section.
More precisely, we assume that
\begin{equation}
\label{coded:eq:d-ge-logk}
d \ge \frac{2(1+t_0)}{\alpha} \log K,
\end{equation}
where $\alpha=-\log(2\rho e^{1-2\rho})>0$, and $t_0>0$ is some constant.
Finally, we restrict our attention to the case when $N\ge K$.

\subsection{Balancing Two Extremes}

The model described above, known as the partial adaptive matching setup, is a generalization of the two extremes.
When $d=1$, we have a static matching setup as in \cite{maddah-ali2012} (while the Poisson model is not meaningful here, insights can still be gained).
When $d=K$, we have the full adaptive matching setup as in \cite{leconte2012, moharir2016}.

As discussed above, there is a dichotomy between these two extremes: the former favors a coded delivery scheme, while the other favors an uncoded replication scheme.
In what follows, we examine how each scheme performs if adapted to the partial adaptive matching setup.
Specifically, we look at:
\begin{itemize}
\item Pure Coded Delivery (PCD): ignores any potential adaptive matching benefits by arbitrarily assigning users to caches, and applying a standard Maddah-Ali--Niesen scheme as discussed in Section~\ref{coded:sec:overview};
\item Pure Adaptive Matching (PAM): ignores any potential coding gains and focuses only on file replication within a cluster and on adaptively matching users to caches within a cluster.
\end{itemize}

As we will see, in the general case we observe two regimes, and each scheme will be preferred in one regime.
These regimes are roughly defined by a threshold on the \emph{total cluster memory} $dM$: when $dM\ll N$ then PCD is favorable, and when $dM\gg N$ then PAM is favorable.
Furthermore, in each regime, the favorable scheme is approximately optimal for almost all values of the cache memory.
This is illustrated in \figurename~\ref{coded:fig:pam-pcd}.
Notice that in the special case $d=1$ (respectively, $d=K$), \figurename~\ref{coded:fig:pam-pcd} shows that PCD (respectively, PAM) is always preferred, as expected from the previous results.

\begin{figure}
\centering
\includegraphics[width=.5\textwidth]{pam-pcd-graph.pdf}
\caption{An approximate visualization of the regimes in which each scheme is more favorable.
The boundary between the PCD- and PAM-dominated regions is blurry: the regime $\Omega(N)<dM<O(N\log N)$ is still not very well understood.}
\label{coded:fig:pam-pcd}
\end{figure}

Each of the two schemes focuses on one idea: PCD ignores adaptive matching in favor of coding gains, and PAM ignores coded delivery in favor of adaptive matching gains.
A hybrid coding and matching (HCM) scheme is introduced in \cite{HKMDadaptive} which performs better than both schemes in most memory regimes.

\subsection{The Pure Coded Delivery (PCD) scheme}

The PCD scheme is a straightforward adaptation of the Maddah-Ali--Niesen scheme described in Section~\ref{coded:sec:overview}; the placement phase is identical to the one  described there.
During the matching phase, we pick any valid user-to-cache matching and provide each user with access to the corresponding cache; this is sufficient since the placement is completely symmetric with respect to the caches and the files. The delivery phase is conducted in two parts:
\begin{enumerate}
\item For the subset of users which were matched to caches, delivery proceeds in the same fashion as in Section~\ref{coded:sec:overview} by creating coded-multicast transmissions.
\item Any users that were not matched (because there are more users than caches in their cluster) will simply be served directly by the server.
\end{enumerate}

Note that for the model described in Section~\ref{Sec:sysmodeladapmat}, the expected number of such unmatched users is very small.
In fact it can be shown that
\[
\mathbb{E}[U^0] \le K^{-t_0}/\sqrt{2\pi},
\]
where $U^0$ is the total number of excess users across all clusters. Note that the expected number of excess users goes to zero as $K$ increases. All the other users (i.e., those that are matched to some cache) will be served by the basic Maddah-Ali--Niesen scheme, and so PCD can achieve the rate in the following theorem.

\begin{theorem}
\label{thm:pcdrate}
For the partial adaptive matching model described in Section~\ref{Sec:sysmodeladapmat}, the expected rate achieved by PCD is
\[
\bar R^\mathrm{PCD}(M) \le \min\left\{ \rho d, \left[\frac{N}{M} - 1\right]^+ + \frac{K^{-t_0}}{\sqrt{2\pi}} \right\}.
\]
\end{theorem}

Notice that this is not much different to the rate achieved in the static matching setup.
This is expected since we are not making any intelligent use of the adaptive matching feature at all in PCD. However, this turns out to be approximately optimal when the total  memory in any  cluster is not enough to hold the entire library, as stated next.

\begin{theorem}
\label{thm:PCDopt}
When $M\le(1-e^{-1}/2)N/2d$, the expected rate achieved by PCD is approximately optimal in the sense that
\[
\bar R^\mathrm{PCD}(M) \le C \cdot \bar R^\star(M) + o(1),
\]
where $R^\star(M)$ is the information-theoretically optimal rate, $C$ is a constant independent of the problem parameters, and the $o(\cdot)$ notation is to be understood with respect to the growth of $K$.
\end{theorem}

We skip the proof of these results here and instead point the interested reader to  \cite{HKMDadaptive}, which has all the details as well as discusses more general scenarios with non-uniform content popularity.

\subsection{The Pure Adaptive Matching (PAM) scheme}

As previously mentioned, the PAM scheme takes the opposite approach to PCD.
It ignores all possible coding in favor of a more intelligent matching of users to caches.
The idea is to store only replicas of files in every cluster, and rely as much as possible on the matching phase to match each user to a cache that contains the file that it requested.

More precisely, the three phases work as follows.
In the placement phase, if the total cluster memory is $dM$, then we store a complete copy of every file in $\lfloor dM/N\rfloor$ caches in every cluster.
In the matching phase, we find the best matching of users to caches so that the number of users matched to a cache containing their requested file is maximized.
In the delivery phase, any users that could not be successfully matched to a suitable cache are served directly from the server.

Notice that the scheme only really takes off once $dM\ge N$: for smaller memory values, there is a significant fraction of users who remain unmatched and have to be served directly by the server.
What's more interesting is that after this threshold of $dM\ge N$ the achieved expected rate decays exponentially with the cluster memory!
The precise rate expression is given in the following theorem.

\begin{theorem}
For the partial adaptive matching model described in Section~\ref{Sec:sysmodeladapmat},  the expected rate achieved by PAM is
\[
\bar R^\mathrm{PAM}(M) \le \begin{cases}
\rho K & \text{if $M<N/d$;}\\
KMe^{-\rho h dM/N} & \text{if $M\ge N/d$,}
\end{cases}
\]
where $h=(1/\rho)\log(1/\rho)+1-1/\rho$.
\end{theorem}

The proof follows along similar lines as \cite{leconte2012}, which focuses on the fully adaptive matching case, and generalizes the results to the partially adaptive matching case.

Notice that $\bar R^\mathrm{PAM}(M)=o(1)$ when $dM>\Omega(N\log N)$. Thus, once the total cluster memory is slightly larger than the total catalogue size, the PAM scheme requires negligible server transmission rate. This also trivially implies that PAM is approximately information-theoretically optimal in that regime.
Combining with Theorem~\ref{thm:PCDopt}, we have that PCD is approximately optimal when $dM<O(N)$ and PAM is approximately optimal when $dM>\Omega(N\log N)$, as illustrated approximately (ignoring the $\log N$ factor for simplicity) in \figurename~\ref{coded:fig:pam-pcd}.

\subsection{The Hybrid Coding and Matching (HCM) scheme}

So far, we have looked at two schemes that each focuses on a single gain: either a coding gain or an adaptive matching gain.
The schemes are approximately optimal in complementary regimes, as illustrated in \figurename~\ref{coded:fig:pam-pcd}.
This section explores a hybrid scheme that unifies coded delivery and adaptive matching by incorporating ideas of both PCD and PAM.
This Hybrid Coding and Matching (HCM) scheme, first introduced in \cite{HKMDadaptive}, turns out to perform better than both PCD and PAM in most memory regimes.

The hybrid scheme combines ideas from both PCD and PAM by introducing a coloring scheme at both the cache level and the file level.
First, we choose a certain number of colors $\chi\in\{1,\ldots,d\}$.
The exact value is not important for now; the ideas work for any $\chi$.
We then partition the caches in every cluster into $\chi$ subsets of (almost) equal size, and color each subset with a unique color.
Similarly, we partition the files in the content library into $\chi$ subsets of (almost) equal size, and color each subset with one color.
Finally, we apply the coded delivery ideas \emph{within each color}, while applying the adaptive matching ideas \emph{across colors}.

More precisely, the three phases proceed as follows.
In the placement phase, for every color $x$ we perform a Maddah-Ali--Niesen placement of the files \emph{of color $x$} in only the caches of the same color.
The placement phase is agnostic to the cluster to which a cache belongs.
In the matching phase, every user can be matched to an arbitrary cache whose color matches the file that the user requested; the user is matched to the color, but the choice of cache within that color is arbitrary.
Naturally, the matching is limited to a cache within the user's cluster.
In the delivery phase, the Maddah-Ali--Niesen coded delivery is performed for every color $x$ separately, and unmatched users are served directly.
Like the placement phase, the delivery phase ignores clusters and serves all users of the same color in the same broadcast message.

Since we have $\chi$ sub-systems of $N/\chi$ files, each running a separate Maddah-Ali--Niesen scheme, using Theorem~\ref{thm:pcdrate} we can show that the hybrid scheme can achieve a rate of
\[
\bar R(M) \approx \min\left\{ \rho K, \chi \cdot \left( \frac{N/\chi}{M} - 1 \right) + \bar U^0(\chi) \right\},
\]
where $\bar U^0(\chi)$ is the expected number of unmatched users when choosing $\chi$ colors.
What is left is therefore to choose the right value of $\chi$.

If the number of colors is too small, then there is little benefit in adaptive matching since the number of choices is reduced.
Conversely, if the number of colors is too large, then the number of caches in each color becomes small, and it becomes likely that a significant number of colors have fewer caches than there are users requesting a file from them; the number of unmatched users thus becomes too large.
The balance is struck when $\chi\approx d/\log K$ colors, as stated more precisely in the next theorem.

\begin{theorem}
For any $t\in[0,t_0]$, the HCM scheme can achieve an expected rate of
\[
\bar R^\mathrm{HCM}(M) \le \begin{cases}
\min\left\{ \rho K, \frac{N}{M} - \chi + \frac{K^{-t}}{\sqrt{2\pi}} \right\} & \text{if $M\le\lfloor N/\chi\rfloor$;}\\
\frac{K^{-t}}{\sqrt{2\pi}} & \text{if $M\ge\lceil N/\chi\rceil$,}
\end{cases}
\]
where $\chi = \lfloor \alpha d/(2(1+t)\log K)\rfloor$.
\end{theorem}

The rate expression can be approximately written as
\[
\bar R^\mathrm{HCM}(M) \approx \min\left\{ \rho K,
\left[ \frac{N}{M} - \Theta\left(\frac{d}{\log K}\right) \right]^+
+ o(1) \right\}.
\]

Comparing the performances of PCD, PAM, and HCM, we find that HCM performs better than both of them in most memory regimes.
In fact, HCM is a unified scheme that is approximately optimal for almost all memory regimes.
Specifically, we have:
\begin{itemize}
\item For all $M\ge0$, HCM performs better than PCD;
\item When $dM\le O(N)$, both HCM and PCD are approximately optimal, while PAM is not;
\item When $dM\ge\Omega(N\log K)$, both HCM and PAM are trivially approximately optimal and achieve a rate of $o(1)$, while PCD is not;
\item The intermediate regime $\Omega(N)\le dM\le O(N\log K)$ is not very well understood and the exact relationship between the different rates, as well as their approximate optimality, is not known.
\end{itemize}
More details can be found in \cite{HKMDadaptive}.

\subsection{Simultaneous Cache Multi-Access}
\input{coded/sections/simultaneous-access.tex}

config: arxiv


TITLE: Maximum dimension of a subspace consisting only of non-degenerate alternating bilinear forms over finite fields.
QUESTION [2 upvotes]: Let $V$ be a vector space over a finite field $\mathbb{F}_q$. The following result seems well-known in the literature of bilinear forms.
The maximum dimension of a subspace consisting only of non-degenerate alternating bilinear forms (except the zero form of course) on $V$ is $\text{dim}(V)/2$. Here, the above vector sub-space is contained in the vector space of all alternating bilinear forms on $V$.
In matrix language, it is the subspace consisting only of $n\times n$ invertible skew-symmetric matrices (except the zero matrix) over $\mathbb{F}_q$ of the vector space of all skew-symmetric matrices in $M_n(\mathbb{F}_q)$. It is clear that $n$ has to be even.
Can anyone suggest a proper reference where I can find this result. I have seen this result to be mentioned in many papers concerning alternating bilinear forms over finite fields, but no proper reference has been cited. I appreciate any kind of help.

REPLY [1 votes]: This is a simple application of Chevalley's theorem.

Theorem (Chevalley, special case) If $\mathbb{F}$ is a finite field and $f\in\mathbb{F}[x_1,\dots,x_n]$ has no constant term, then $f=0$ has a nontrivial solution provided $n>\deg f$.

Also recall definition of Pfaffian of a skew-symmetric matrix:

Definition Let $A=(a_{ij})$ is a $2d\times 2d$ skew-symmetric matrix (over any ring).  There exists a homogeneous degree-$d$ polynomial
$$
\operatorname{Pf}(A)=\frac1{2^d d!}\sum_{\sigma\in S_{2d}}\operatorname{sgn}(\sigma)\prod_{i=1}^d a_{\sigma(2i-1)\sigma(2i)}\in\mathbb{Z}[\{a_{ij}:i>j\}],
$$
called the Pfaffian of $A$, such that $\det(A)=(\operatorname{Pf}(A))^2$.

So suppose we have $n$ linearly independent $2d\times 2d$ skew-symmetric matrices $A_1,\dots,A_n$ such that all nontrivial linear combinations are nondegenerate.  That means for all $(x_1,\dots,x_n)\in\mathbb{F}^n-\{0\}$, we have $\operatorname{Pf}(\sum_{i=1}^n x_iA_i)\neq 0$.  By Chevalley's theorem, this can never happen if $n>d$ as we are working over finite field $\mathbb{F}=\mathbb{F}_q$.


TITLE: On the use of "generic" and "general" in algebraic geometry
QUESTION [15 upvotes]: I have learned that in algebraic geometry, when an 'object' can be put in a family which is in a bijective correspondence with some projective variety, the generic object in this family is one which lies in a (Zariski) open dense subset of the variety.
So, for example we can talk of the generic divisor in a linear system, e.g. the generic curve on a surface etc.
However, for curves I have seen the word general being used as well, sometimes. I initially thought that this were synonyms, but then started wondering if this is really so. I am a bit confused.
I did not find an answer by looking at the index in Hartshorne's book. Can somebody illuminate me on this terminology? What is meant by a general curve, or a general curve of genus $g$ (e.g. in the first page on this article) or general in the sense of moduli? are there other uses of general?

REPLY [14 votes]: They are not exactly synonyms.
A generic property is a property of the generic point. A general property is a property that holds away from a Zariski closed subset. To illustrate the difference, I would make the following:
Example. If you have a linear system of divisors $|D|$, you can say that the generic element of $|D|$ satisfies a certain property $Q$ if the generic point of $|D|$ (which is a projective space, hence has a unique generic point) satisfies $Q$. On the other hand, you can say that the general member of $|D|$ satisfies $Q$ in case there is a Zariski dense open subset $U\subset |D|$ such that every point in $U$ satisfies $Q$.
Remark. If $F$ is a scheme parametrizing a certain family of schemes, and $Q$ is a property of schemes, let us consider the sentences:

The generic element of $F$ satisfies $Q$;
The general element of $F$ satisfies $Q$.

The negations of 1 and 2 are sensibly different:

The generic element of $F$ does not satisfy $Q$;
The subset of $\{p\in F\,|\,p\textrm{ satisfy }Q\}\subset F$ has empty interior.

To sum up: if a property holds for a general element, it does not mean it holds for the generic point (provided that you have one such). But sometimes one can, in some sense, go the other way round:
From generic to general. Suppose you have a morphism of schemes $X\to Y$, with $Y$ irreducible of generic point $\eta$. Let $Q$ be a property of schemes. If the generic fiber $X_\eta$ has $Q$, and the property is constructible, then a general fiber has $Q$ as well, meaning that there is an open subset $U\subset Y$ such that $X_u$ has $Q$ for every $u\in U$.
Curves. I guess by "a general curve" of genus $g$ one means a general point in $M_g$. Of course $M_g$ is an irreducible variety, so it also has a unique generic point, and it makes sense to make statements about the generic curve of genus $g$.


TITLE: Sum of Legendre symbol
QUESTION [0 upvotes]: $$\sum_{y=0}^{p-1} \left(\frac {y^2 + d}{p}\right) = \sum_{y=0}^{p-1} \left(1+\left( \frac {y}{p}\right)\right)\left(\frac {y+d}{p}\right)$$
What is the reason behind this?

REPLY [1 votes]: Because $1+\left(\frac yp\right)$ is $2$ when $y$ is a non-zero square and $0$ when $y$ is not a square, and $1$ when $y=0.$ Thus, $1+\left(\frac yp\right)$ is equal to the number of values $z$ in $\{0,1,\dots,p-1\}$ such that $z^2\equiv p\pmod{p}.$ So the right side can be written as $$\sum_{z=0}^{p-1}\left(\frac{z^2+d}{p}\right)$$
More generally, given a function $f$ with $f(x+p)=f(x)$:
$$\sum_{y=0}^{p-1} f(y^2)=\sum_{y=0}^{p-1} \left(1+\left(\frac yp\right)\right)f(y)$$


TITLE: asymptotic behavior of the solution to an ODE
QUESTION [1 upvotes]: Given
$$y(t) = \frac{d_2 y_0 e^{d_2 t/\epsilon}}{d_2-\epsilon \, d_1 y_0 (e^{d_2 t/\epsilon}-1)}$$
I think that $y = O(1/\epsilon) $ as $\epsilon \to 0$. But as this is important for what I am doing and I am not used to asymptotic I wanted to double-check. Thx!

REPLY [1 votes]: (I'm assuming that $\epsilon > 0$.)
If $y_0 > 0$ then $y(t)$ has a singularity at
$$
T(\epsilon) =\frac{\epsilon}{d_2} \log\left(\frac{d_2+\epsilon d_1 y_0}{\epsilon d_1 y_0}\right).
$$
For any fixed $t > 0$ it will eventually be true that $T(\epsilon) < t$ for $\epsilon$ small enough.  That is, each fixed $t > 0$ will eventually leave the maximal interval of existence as $\epsilon \to 0^+$.  If your application requires that you only consider $t$ in the maximal interval of existence then the asymptotics for fixed $t$ will be useless to you.
Note that there is no such singularity if $y_0 < 0$.
Asymptotics for fixed $t > 0$.
We have
$$
\begin{align}
y(t) &= \frac{d_2 y_0 e^{d_2 t/\epsilon}}{d_2-\epsilon \, d_1 y_0 (e^{d_2 t/\epsilon}-1)} \\
&= \frac{d_2}{\epsilon d_1} \cdot \frac{1}{\epsilon^{-1} d_1^{-1} d_2 y_0^{-1} e^{-d_2 t/\epsilon} - 1 + e^{-d_2 t/\epsilon}} \\
&\sim -\frac{d_2}{\epsilon d_1}
\end{align}
$$
as $\epsilon \to 0^+$ since
$$
\lim_{\epsilon \to 0^+} \frac{1}{\epsilon^{-1} d_1^{-1} d_2 y_0^{-1} e^{-d_2 t/\epsilon} - 1 + e^{-d_2 t/\epsilon}} = -1.
$$
Asymptotics in a subinterval of $[0,T(\epsilon))$ when $y_0 > 0$.
The singularity at $t=T(\epsilon)$ precludes the existence of an $O(f(\epsilon))$ bound which holds uniformly with respect to $t$ in the interval $[0,T(\epsilon))$, so if you're interested in such a bound then you must restrict $t$ to some proper subinterval of $[0,T(\epsilon))$.
One way to do this is to fix some $0 < \alpha < 1$ and consider $t \in [0,\alpha T(\epsilon)]$.
Since $y$ is increasing on $[0,T(\epsilon))$ we have
$$
y_0 \leq y(t) \leq y(\alpha T(\epsilon)) = \frac{1}{(\epsilon d_1 y_0/d_2)^{\alpha}(d_1 \epsilon+d_2/y_0)(1+\epsilon d_1 y_0/d_2)^{-\alpha} - d_1 \epsilon}.
$$
Since $\alpha < 1$ we have
$$
\frac{1}{(\epsilon d_1 y_0/d_2)^{\alpha}(d_1 \epsilon+d_2/y_0)(1+\epsilon d_1 y_0/d_2)^{-\alpha} - d_1 \epsilon} \sim \frac{y_0}{d_2}\left(\frac{d_2}{\epsilon d_1 y_0}\right)^{\alpha} = O(\epsilon^{-\alpha}),
$$
so that $y(t) = O(\epsilon^{-\alpha})$ as $\epsilon \to 0^+$ uniformly for $t \in [0,\alpha T(\epsilon)]$.
Uniform asymptotics when $y_0 < 0$.
The function $y(t)$ will be decreasing when $\epsilon < -\frac{d_2}{d_1 y_0}$, and since we're taking $\epsilon \to 0^+$ we'll assume that this is indeed the case.  As such we have
$$
y_0 \geq y(t) \geq y(+\infty) = - \frac{d_2}{\epsilon d_1}
$$
so that $y(t) = O(\epsilon^{-1})$ uniformly for $t>0$.

In summary,

For each fixed $t \geq 0$ we have $y(t) = O(\epsilon^{-1})$ as $\epsilon \to 0^+$.
If $y_0 > 0$ and $0 <\alpha < 1$ then $y(t) = O(\epsilon^{-\alpha})$ as $\epsilon \to 0^+$ uniformly with respect to $t$ on $[0,\alpha T(\epsilon)]$.
If $y_0 < 0$ then $y(t) = O(\epsilon^{-1})$ as $\epsilon \to 0^+$ uniformly with respect to $t$ on $\mathbb R^+$.


TITLE: Behaviour of Two Coupled Sequences Towards a Stable Distribution
QUESTION [2 upvotes]: The following question arises from research that I am doing in swarm intelligence. The relationships given come from geometric considerations which, I believe, should not be relevant for this problem. However, if anyone deems it necessary, I would be happy to provide more information.
I have studied this problem using numerical simulations, and what I am after now are leads on how I can attack this problem formally, or re-formulate it such that it becomes more manageable, etc. I am not a mathematician, so apologies in advance for any shortcomings in formulation and/or notation; any sort of suggestion to improve the problem would be very welcome and appreciated.
Firstly, we define the following two piecewise functions, where $R$ and $r$ are constants, and $R>r$:
$\delta(*) = \begin{cases} 0 & \text{if $(*)<R-r$}\\ \sqrt{\frac{R}{r}((*)^2 - (R-r)^2)} & \text{if $R-r\leq(*)\leq R+r$} \\ \frac{2Rr}{\sqrt{(*)^2 - (R^2+2Rr)}} & \text{if $(*) > R+r$}\end{cases}$
$f(*)=\begin{cases} (*) & \text{if $(*)<R-r$} \\ R-r & \text{if $R-r\leq(*)\leq R+r$} \\ \sqrt{(*)^2-4Rr} & \text{if $(*) > R+r$}\end{cases}$
Now, consider an large number of points $(x,y)$, initially all occupying the same point in the $xy$-plane, $(x_0, y_0)$. The points transform themselves in epochs, as follows. At the beginning of an epoch, a random 'coin toss' decides whether the points will be $x$-updated or $y$-updated.
For an $x$-update, each point undergoes the following transformation:
$y \leftarrow  y + \zeta \delta(x)\\ x \leftarrow f(x)$
where $\zeta$ is a random number between $-1$ and $1$ generated differently for each point (with a uniform distribution). A $y$-update is the inverse of what is described above:
$x \leftarrow  x + \zeta \delta(y)\\ y \leftarrow f(y)$
What is happening is that, after each epoch, the points are forming a new distribution in the $xy$-plane. This distribution becomes continuous if the number of points is allowed to tend towards infinity.
From numerical results, it turns out that this process has a single distribution that is a stable attractor for any initial condition $(x_0, y_0)$. After many epochs, the distribution tends towards two lines: one line is horizontal, located at $y=R-r$, and ranges from $x = 0$ to $x = R-r$. The other line is vertical, located at $x=R-r$, and ranges from $y=0$ to $y=R-r$.

REPLY [1 votes]: Some intuition
There are many ways to approach to this, here is some intuition that may help you whatever approach you follow:
Both of your functions transition functions $\delta(*)$ and $f(*)$ have the same "bins" (you already know this); these are:

$(*) < R -r$
$R-r<(*) < R -r$
$(*) > R -r $

Also, $\delta(*)$ is bounded. Let $(*)>R+r$ (our third "bin"), then we have:
$$\delta(*) = \frac{2Rr}{\sqrt{(*)^2 - (R^2+2Rr)}} < \frac{2Rr}{\sqrt{(R+r)^2 - (R^2+2Rr)}} = \frac{2Rr}{r} = 2R$$
From here it is easy to show that $sup \{\delta(*)\} = 2R$
Lastly, $f(*)$ is decreasing on the third "bin":
$$\sqrt{(*)^2-4Rr} < (*)$$
From there, it is intuitive to think that any coordinate in the 3rd bin, will eventually decrease to the second bin since when it grows, it never grows more than $2R$ and $f(*)$ will eventually make it less than $R+r$
A vague sketch of a proof
There are multiple ways of solving this problem, here is a sketch that is kind of long but doesn't require more advanced concepts, since you are asking for some hints rather than a full proof.
Define nine states:

$x$ in 1st bin and $y$ in 1st bin
$x$ in 1st bin and $y$ in 2nd bin
$x$ in 1st bin and $y$ in 3rd bin
$x$ in 2nd bin and $y$ in 1st bin
so on,
...
...
...
$x$ in 3rd bin and $y$ in 3rd bin

Let say that the $ith$ iteration is on 'State 9' (this the most interesting one). It means that:
$$x_i > R-r \ \ \ \ \ and \ \  \ \ \ y_i > R-r$$
Imagine that a sequence of $n$ epochs with x-update happen, then:
$x_{i+1}=f(x_i) > x_{i}$ and eventually $x_{i'} \leq R-r$ for some $i'$
and that point will be outside of the 9th state. This can be stated as:
$$P(x_n > R+r, y_n > R+r) \rightarrow 0$$
Similar arguments hold for the 3rd and the 6th bins.
If you apply limits to all the states, you will see that only the 2nd and the 4th bin will have a non-zero limit probability (recurrent states, in more precise terminology). That's why get the limit state lies on the lines $y=R-r$ and $x=R-r$. They are line segments with length $R-r$ because there is a random walk in the coordinate that stays in the 1st bin, and randomly will lay between $0$ and $R-r$.


TITLE: Understanding what the Bose-Einstein distribution
QUESTION [1 upvotes]: I'm currently studying Kittel's Solid State Physics and in his chapter on Phonon heat capacity, we need to first calculate the total energy $U$. Phonons have energy $E_n = (n+1/2)\hbar\omega$ and he first calculated the average energy $\langle E\rangle$ and using the Boltzmann factor, he showed:
$$\langle E\rangle = \dfrac{1}{2}\hbar\omega+\hbar\omega\dfrac{1}{e^{\hbar\omega/k_BT}-1}=\dfrac{1}{2}\hbar\omega+\hbar\omega\langle n \rangle$$ so then we must have
$$\langle n \rangle=\dfrac{1}{e^{\hbar\omega/k_BT}-1}$$
I recognise this as the Bose-Einstein but I'm surprised to see this as being interpreted as an average of the number of states. I always thought this was a probabilistic distribution and in fact, Kittel does seem to use this as a probability since he later writes:
$$U=\int d\omega\ \hbar\omega D(\omega)\langle n \rangle$$ where $D(\omega)$ is the density of state. In this expression $D$ already accounts for the number of photons so $\langle n \rangle$ must be some probability weight? I'm sure something is flawed in my understanding so any help is appreciated!

REPLY [0 votes]: For a given oscillation frequency $\omega$, the average energy of this oscillation mode is:
$$
E_\omega = \frac{1}{Z} \sum_{n=0}^\infty \left\{ \left(n+\frac{1}{2}\right)\hbar \omega \, e^{-\beta \left(n+\frac{1}{2}\right) \hbar \omega} \right\} \tag{1}
$$
where $Z$ is the probability normalization (also known as the partition function)
$$
  Z = \sum_{n=0}^\infty \left\{  e^{-\beta \left(n+\frac{1}{2}\right) \hbar \omega} \right\} = e^{-\beta\frac{1}{2}\hbar \omega}\sum_{n=0}^\infty \left\{  e^{-\beta n \hbar \omega} \right\}=e^{-\beta\frac{1}{2}\hbar \omega} \frac{1}{1-e^{-\beta\hbar \omega}}=\frac{1}{e^{\beta\hbar \omega/2}-e^{-\beta\hbar \omega/2}} \tag{2}
$$
Using Eq.(2) to express Eq.(1) as
\begin{align*}
E_\omega &= -\frac{1}{Z} \frac{\partial}{\partial \beta} \sum_{n=0}^\infty \left\{  e^{-\beta \left(n+\frac{1}{2}\right) \hbar \omega} \right\} = -\frac{1}{Z} \frac{\partial Z}{\partial \beta} =  -\frac{\partial \ln Z}{\partial \beta}\\
&=  -\frac{\partial }{\partial \beta} \left\{ -\ln \left(e^{\beta\hbar \omega/2}-e^{-\beta\hbar \omega/2} \right)\right\} \\
&=\frac{e^{\beta\hbar \omega/2}+e^{-\beta\hbar \omega/2}}{e^{\beta\hbar \omega/2}-e^{-\beta\hbar \omega/2}}\frac{1}{2}\hbar \omega =  \coth\left( \frac{\beta \hbar \omega}{2}  \right)\frac{1}{2}\hbar \omega
\end{align*}
Therefore, for a fixed $\omega$, the average oscillation mode of phonon $\langle n \rangle$:
$$
\langle n \rangle = \frac{E_\omega}{\hbar\omega} = \frac{1}{2} \coth\left( \frac{\beta \hbar \omega}{2}  \right).
$$
Then we consider all different oscillation frequencies
$$
   U = \int_0^{\omega_D} E_\omega D(\omega) d\omega \tag{3}
$$
where $D(\omega)$ is the density of state as the number of oscillation modes between $\omega$ and $\omega + d\omega$.
Seemingly, that the Debye's model will be  adopted, known as the acoustic mode.$^1$ It assumes a linear dispersion
$$
 \omega = v_s  k.
$$
where $v_s$ is the sound speed.
Therefore, the 1-d density if state
$$
D(\omega) = \frac{L}{2\pi}\frac{dk}{d\omega}= \frac{L}{2\pi v_s}
$$
$L$ is the length of the system.
In Eq. (3), there is one more parameter, $\omega_D$, the Debye frequency, defined as the upper limit of the cut-off frequency for rendering the total number of mode being equals to the total number of oscillator (atoms or number of cells).
$$
N = \int_0^{\omega_D} D(\omega) d\omega =  \int_0^{\omega_D} \frac{L}{2\pi v_s} d\omega =  \frac{L}{2\pi v_s} \omega_D.
$$
Therefore
$$
\omega_D = 2\pi v_s \frac{N}{L}.
$$
*1. The other well known model is the Einstein model, which is easier
$$
D(\omega) = \delta(\omega - \omega_o).
$$
also know as the optical mode of phonon.


TITLE: Using Cylindrical Coordinates to Compute Curl
QUESTION [1 upvotes]: I am given a vector field $\vec{A} = A_\rho \space \hat{e_\rho} + A_\phi \space \hat{e_\phi} + A_z \space \hat{e_z}$, and I am supposed to use the unit vectors (provided below) in cylindrical coordinates to calculate the gradient in cylindrical coordinates.
\begin{align*} \hat{\rho} = <\cos(\phi), \sin(\phi),0> \end{align*}
\begin{align*} \hat{\phi} = <-\sin(\phi), \cos(\phi),0> \end{align*}
\begin{align*} \hat{z} = <0,0,1> \end{align*}
Then, I am asked to use the form of the gradient operator in cylindrical coordinates to compute $ \nabla \times \vec{A} $, where the gradient operator in cylindrical coordinates, found as:
\begin{align*} \nabla\times\vec{F} = (\frac{1}{\rho} \frac{\delta A_z}{\delta \phi} - \frac{\delta A_\phi}{\delta z}) \hat{\rho} + (\frac{\delta A_\rho}{\delta z} - \frac{\delta A_z}{\delta \rho})\hat{\phi} + \frac{1}{\rho}(\frac{\delta(\rho A_\phi)}{\delta \rho} - \frac{\delta A_\rho}{\delta \phi} )\hat{z}\end{align*}
Now, the professor also provides a hint:
"Given the forms of the unit vectors, be careful when $\delta/\delta\phi$ hits either $\hat{e_\rho}, \hat{e_\phi}$ -- these terms will be non trivial.
The issue I'm having is how is the above expression not the final solution? Doesn't that
 represent the gradient ($\nabla \times \vec{A}$) in cylindrical coordinates for the given vector? Or is there a way to simplify the expression?

REPLY [2 votes]: My attempt at the solution (using $<r,\phi,z>$)

First consider the curve of constant r, provided above. For $C_1$ and $C_3$, we have:
$\int_{C_1} F\cdot \hat{t} = -F_\phi (r,\phi, z + \Delta z/2)(r + \Delta r/2)\Delta \phi$
$\int_{C_3} F\cdot \hat{t} = F_\phi (r,\phi, z - \Delta z/2)(r - \Delta r/2)\Delta \phi$
Thus, knowing the change in surface for constant r is $\delta S_r = r \delta \phi \delta z$
\begin{align*} \frac{1}{\Delta S}\int_{C_1 + C_3} F\cdot \hat{t} = -\frac{\Delta \phi}{r \Delta \phi \ \Delta z}[ F_\phi (r,\phi, z + \Delta z/2)(r + \Delta r/2) - F_\phi (r,\phi, z - \Delta z/2)(r - \Delta r/2)] \end{align*}
Which taking the limits for $\Delta \phi, \Delta z \rightarrow 0$, we get
\begin{align*} -\frac{\delta F_\phi}{\delta z}\end{align*}
For $C_2$ and $C_4$:
$\int_{C_2} F\cdot \hat{t} = F_z (r,\phi + \Delta \phi/2, z)\Delta z$
$\int_{C_4} F\cdot \hat{t} = F_z (r,\phi - \Delta \phi/2, z)\Delta z$
Thus,
\begin{align*} \frac{1}{\Delta S}\int_{C_2 + C_4} F\cdot \hat{t} = \frac{\Delta \phi}{r \Delta \phi \ \Delta z}[F_z(r,\phi + \Delta \phi/2, z) - F_z(r,\phi - \Delta \phi/2, z)] \end{align*}
Which taking the limits for $\Delta \phi, \Delta z \rightarrow 0$, we get
\begin{align*} \frac{1}{r} \frac{\delta F_z}{\delta \phi}\end{align*}

First consider the curve of constant $\phi$, provided above. For $C_1$ and $C_3$, we have:
$\int_{C_1} F\cdot \hat{t} = F_r (r,\phi, z + \Delta z/2)\Delta r$
$\int_{C_3} F\cdot \hat{t} = -F_r (r,\phi, z - \Delta z/2)\Delta r$
Change in surface for constant $\phi$ is $\delta S_r = r \phi \delta z$
\begin{align*} \frac{1}{\Delta S}\int_{C_1 + C_3} F\cdot \hat{t} = \frac{\Delta r}{\Delta r \ \Delta z}[F_r (r,\phi, z + \Delta z/2) - F_r (r,\phi, z - \Delta z/2)] \end{align*}
Which taking the limits for $\Delta r, \Delta z \rightarrow 0$, we get
\begin{align*} \frac{\delta F_r}{\delta z}\end{align*}
For $C_2$ and $C_4$:
$\int_{C_2} F\cdot \hat{t} = -F_z (r + \Delta r/2, \phi, z)\Delta z$
$\int_{C_4} F\cdot \hat{t} = F_z (r - \Delta r/2, \phi, z)\Delta z$
Thus,
\begin{align*} \frac{1}{\Delta S}\int_{C_2 + C_4} F\cdot \hat{t} = -\frac{\Delta z}{\Delta r \ \Delta z}[F_z(r + \Delta r/2, \phi, z)-F_z (r - \Delta r/2, \phi, z)] \end{align*}
Which taking the limits for $\Delta r, \Delta z \rightarrow 0$, we get
\begin{align*} \frac{\delta F_z}{\delta r}\end{align*}

The derivation for the final curve, of constant $z$, shown above, can be found in Schey's "Div Grad Curl and All That", but it follows the same procedure as above.
The result for the curve of constant $z$ is
\begin{align*} (\nabla \times F)_z =\frac{1}{r}\frac{\delta}{\delta r} (rF_\phi) - \frac{1}{r} \frac{\delta F_r}{\delta \phi} \end{align*}
Combining the results of the above, we reach
\begin{align*} \nabla\times\vec{F} = (\frac{1}{r} \frac{\delta F_z}{\delta \phi} - \frac{\delta F_\phi}{\delta z}) \hat{r} + (\frac{\delta F_r}{\delta z} - \frac{\delta F_z}{\delta r})\hat{\phi} + \frac{1}{r}(\frac{\delta(r F_\phi)}{\delta r} - \frac{\delta F_r}{\delta \phi} )\hat{z}\end{align*}


TITLE: Generalization of Beck's theorem
QUESTION [3 upvotes]: Beck's theorem is a classical result in discrete geometry which describes about the geometry of points in the plane. The result states that a finite collections of points in the plane fall into one of two extremes; one where a large fraction of points lie on a single line, and one where a large number of lines are needed to connect all the points.
Formally, the statement of the theorem is as follows:
Theorem: Let $S$ be a set of $n$ points in the plane. If at most $(n-k)$ points lie on any line for some $0 \leq k < n-2$, then there exist $\Omega(nk)$ lines determined by the points of $S$.
Now, my question is that if the generalization/variation of the above result is known in the case of higher dimension $(dim\geq 3)$?

REPLY [5 votes]: If you are asking if the same statement holds true or not in higher dimensions, it does. Just project all the points to a random 2-dimensional plane.
Another natural generalization is to consider hyperplanes instead of lines. Here, you have Beck's "other" theorem:

Theorem: For any $d \geq 2$, there are constants $\beta_d, \gamma_d \in (0,1/2]$ such that for any set $P$ of $n$ points in $\mathbb{R}^d$, at least one of the following holds:

a hyperplane contains at least $\beta_d n$ points of $P$
the $d$-tuples of $P$ span at least $\gamma_d n^d$ distinct hyperplanes.

Here, a hyperplane is a $(d-1)$-dimensional flat. For $d=2$, this is essentially what you stated. The restriction that $\beta_d \leq 1/2$ is from the example of having two skew lines in $\mathbb{R}^3$ containing $n/2$ points each, where the number of spanned planes is $n$. For more, see: http://www.cs.elte.hu/~elekes/Abstracts/elest.ps


TITLE: doubt with direction angles
QUESTION [0 upvotes]: Is it possible for a 3D vector to be drawn with the direction angles of $\alpha=45^\circ$ and $\beta=45^\circ$ ? if yes what is measure of $\gamma^\circ$?
I calculated $\cos^2(45^\circ )+\cos^2(45^\circ )+\cos^2(\gamma) = 1$
so $\gamma= \pi/2$.
I am right?

REPLY [3 votes]: The $\alpha$, $\beta$ and $\gamma$ are angles of the 3D vector against the x, y and z axis of the coordinate system. That does not mean that they are independent variables for defining a 3D vector in the space. For example, you cannot have a 3D vector that has 90 degree to all the 3 axes and you cannot have a 3D vector that has 0 degree to any 2 axes either. For any given angle (or angles), if you cannot find a solution for other angle(s), it simply means such a 3D vector does not exist.


TITLE: Fundamental group of noncommutative torus
QUESTION [2 upvotes]: Let $\tau \in \mathbb{S}^1$ be such that $\tau$ is not a root of unity. Let $E_\tau$ be the quotient space $S^1/\tau^{\mathbb Z}$. Consider it as a pointed space with basepoint the equivalence class of $1$. This is a path-connected space.
What is the fundamental group of this space?

REPLY [2 votes]: Can you see what the topology of the quotient $S^1/(\tau)$ is? Its open sets "are" the open sets in $S^1$ which are invariant under multiplication by $\tau$.
Once you see what the topology is, your question becomes easy.


TITLE: Rational approximation using only odd numerators.
QUESTION [5 upvotes]: Dirichlet's simultaneous approximation theorem says:
Given any $n$ real numbers $\alpha_1,\ldots,\alpha_n$ and for every natural number $N \in \mathbb{N}$, there exist integers $q \leq N$, and  $p_1,\ldots,p_n \in \mathbb{Z}$, such that:
$$ \Bigg|\alpha_i - \frac{p_i}{q}\Bigg| < \frac{1}{qN^{1/n}} \text{    for } i=1,\ldots,n $$
I would like to prove a similar theorem, but want to insist that the $p_i$ all be odd.  It's easy to prove a version which has all the $p_i$ even, because the set of points in $\mathbb{R}^n$ with even coordinates is a lattice.
The general version of Minkowski's Theorem say that a symmetric region containing the origin, if it's volume is sufficiently large, must contain a nonzero lattice point.  But the set of points with odd coefficients is only a coset of the lattice of points with even coefficients.
This seems obviously true that one should be able to replace "lattice" with "coset of the lattice" in Minkowski's Theorem, but I sure don't see how to do it.  I can get the result I want in one dimension by modifying the continued fraction construction, but that doesn't export to $n$ dimensions.  References and insights welcome.

REPLY [2 votes]: The main point of the Minkowski theorem is that when you take a geometric projection you know that the volume of a certain set is too large not to have the difference of two points be in a given lattice. In symbols if $S$ is any subset of your vector space (more generally locally compact group), $V$, equipped with a Haar measure $m$, and $\Lambda$ is a lattice (more generally co-compact, discrete subgroup) then if $S\subseteq V$ with $m(S)>m(V/\Lambda)$ we have $x\ne y\in S$ so that

$$x\equiv y\mod \Lambda.$$

The Minkowski use of this critical lemma is just that when $S$ is convex and centrally symmetric, then as $2\Lambda$ is also a lattice with

$$m(V/2\Lambda) = 2^nm(V/\Lambda)$$

(in $\Bbb R^n$ with $m$ as Lebesgue measure) when $m(S) > 2^nm(V/\Lambda)$ we can get points $x\equiv y\mod 2\Lambda$. Convexity and symmetry of $S$ gives

$${1\over 2} (x) + {1\over 2} (-y)={1\over 2} (x-y)\in \Lambda\cap S.$$

As a result, your insight about the cosets is exactly on point for this reason because groups are so homogeneous in structure.
But how, exactly, does this work when we're dealing with a non-lattice? In general the proof shows that there is no real control over what coset of a given sub-lattice you get:  it's very general construction using very general assumptions, however since the geometry of the situation is relatively simple, we can exploit it for some progress.
Note that the situation of simultaneous approximation as it manifests in this problem concerns a parallelopiped, namely

$$M^{-1}\bigg(\left[-N-{1\over 2}, N+{1\over 2}\right]\times \left[-N^{-1/d}, N^{-1/d}\right]^{n}\bigg).$$

with

$$M = \begin{pmatrix}
1 && 0 && 0 && \ldots && 0 \\
\alpha_1 && -1 && 0 && \ldots && 0 \\
\alpha_2 && 0 && -1 && \ldots && 0 \\
\vdots && \vdots && \vdots && \ddots && \vdots \\
\alpha_n && 0 && \ldots && 0 && -1
\end{pmatrix}.$$

Luckily here you can easily see how it affects the distance on each coordinate. In particular you can see that if you're willing to have a constant (depending on the dimension only) as a fudge factor, you can expand the result pretty easily just by making your intervals a little wider. Note that the key obstruction to naively doing this is the fact that this is an existence theorem, which means you have essentially no control over what the convergent will look like for any fixed $N$ unless you are willing to expand the hypotheses you're willing to use a little (unless you get lucky and you pick an actual lattice, like when you do all evens). However, if you are happy to accept some of the "on average" machinery of statstical number theory, we note that the density of lattice points is inversely proportional to the determinant of the lattice, hence there must be points in proper cosets--in fact most of them are in cosets! If you want something for a specific choice of coset, eg. all the numerators are odd rather than just some numerator is odd, you can use the fact that you are dealing with a parallelopiped, so that you understand the relative "thickness" in any given direction based on the $\alpha_i$ in question.


text:
\begin{definition}[Definition:Method of Least Squares (Approximation Theory)]
Let there be a [[Definition:Set|set]] of [[Definition:Point|points]] $\set {\tuple {x_k, y_k}: k \in \set {1, 2, \ldots, n} }$ plotted on a [[Definition:Cartesian Plane|Cartesian $x y$ plane]] which correspond to [[Definition:Measurement|measurements]] of a [[Definition:Physical System|physical system]].
Let it be required that a [[Definition:Straight Line|straight line]] is to be fitted to the [[Definition:Point|points]].
The '''method of least squares''' is a technique of producing a [[Definition:Straight Line|straight line]] of the form $y = m x + c$ such that:
:the [[Definition:Point|points]] $\set {\tuple {x_k', y_k'}: k \in \set {1, 2, \ldots, n} }$ are on the line $y = m x + c$
:$\forall k \in \set {1, 2, \ldots, n}: y_k' = y_k$
:$\displaystyle \sum_n \paren {x_k' = x_k}^2$ is minimised.
\end{definition}

config: wiki


TITLE: Notation: sin and cos without brackets
QUESTION [1 upvotes]: Recently I read an equation that was formated like the following one:
$f = \sin x y + \cos z$
Since $x$, $y$, and $z$ are different variables, and there are not brackets (), is $y$ inside the sin-operator or not? Does there exist some kind of rule for this?
Does it mean $f = \sin(x) y + \cos(z)$ or $f = \sin(x y) + \cos(z)$?

REPLY [0 votes]: Refering to the excellent comments under the inital question, I will answer my own question, just to mark this as answered. Therefore $f=\sin(xy)+\cos(z)$ is correct.


TITLE: Proving only certain methods of Integration work on certain problems
QUESTION [0 upvotes]: I have not studied Pure Maths (Stuff which includes rigorous proving) yet however I did take classes on Integration.
There were certain problems which we could do only by certain ways to get the results for instance the integral of $ln(x)$ can be easily computed via Integration by Parts however there is no meaningful substitution in my knowledge which can do the same.
I pondered a bit and then it seemed pretty obvious that not all integrals can be solved by all techniques however this is a very general statement to make and rigour is everything in mathematics so are there ways to prove such a statement?
I thought of a way where I tried using Proof by Contradiction and said if the statement is true then there should exist no counterexamples then took up the integral of some function where according to my knowledge there is no substitution technique like $ln(x)$ so the proof became contingent on the fact that there is no subsitution for the following integral which can solve it but couldn't think of any ways to do that

REPLY [1 votes]: There certainly is a substitution that works: $u = x\ln x - x$. Then $du =\ln x\,dx$, so $\int \ln x\,dx = \int du = u = x\ln x - x$.
Of course I made that substitution because I knew the answer, but my point is that "not yet knowing the answer" isn't a mathematical concept. I gave you a substitution that worked, case closed.
Rather than try to show certain methods of integration don't work, a more robust concept is showing that the antiderivative of a (continuous) function does not lie among a certain class of functions, such as what are called the "elementary" functions.  See https://en.wikipedia.org/wiki/Liouville%27s_theorem_(differential_algebra). This is not going to tell you anything about how you can or can't work out an antiderivative of $\ln x$ by techniques taught in a calculus course (in fact you know that it can be done), but it will tell you that functions such as $e^{-x^2}$ do not have an antiderivative among the kinds of functions students learn before taking calculus (the "elementary functions").


TITLE: Finding function with an oblique asymptote
QUESTION [0 upvotes]: Let $f$ be a function, continuous on $\mathbb{R}$, twice differentiable for $x \neq p$ for some $p \in \mathbb{R}$.
We are given that $f(
p) = 0, f(0)=-1$, it has an oblique asymptote $y=2x-1$ as $x \to \pm \infty$ and $\displaystyle\lim_{x \to p}f'(x) = \infty$.
Now, we are asked to find constants $a,b,c,d$ so that $$f(x) = (ax^3 + bx^2+cx+d)^{1/3}$$ satisfies the conditions above. I can find $a$ as $8$ using the oblique asymptote. By $f(0)=-1$, $d$ can be found as $-1$. To find some $b,c$, I plan to check the limit $\lim_{x\to \infty} f(x) -2x = -1$ and use the identity $u^3 - v^3 = (u-v)(u^2 +uv +v^2)$ but it looks messy. How can I find those $b$ and $c$?

REPLY [1 votes]: Finding $b$ is pretty straightforward.
Using your results, you have
$$f(x) = \sqrt[3]{8x^3+bx^2+cx-1}.$$
Now you can use the fundamental limit
$$\frac{(1+\alpha)^\beta-1}{\alpha} \to \beta\tag{1}\label{1}$$
when $\alpha \to 0$, to get
\begin{eqnarray}
-1 &=&\lim_{x\to \infty} f(x) -2x=\\
&=& \lim_{x\to \infty} 2x\left(\sqrt[3]{1+\frac{bx^2+cx-1}{8x^3}}-1\right)=\\
&\stackrel{\eqref{1}}{=}&\lim_{x\to \infty} 2x\cdot \frac13\cdot\frac{bx^2+cx-1}{8x^3}=\frac{b}{12}.
\end{eqnarray}
Hence $b=-12$.
Since the derivative is
$$f'(x) = \frac{24x^2-24x+c}{3\sqrt[3]{(8x^3-12x^2+cx-1)^2}}$$
the requirement that $f$ is not differentiable in only one point $p$, implies that $$g(x) = 8x^3-12x^2+cx-1$$ has only one real root.
If you want to avoid using Cardano's method to obtain conditions on $c$, you can look analytically for the value of $c$ for which $g(x)$ has a real root with multiplicity $2$, so that we must have
$$\begin{cases}
8x^3 -12x^2+cx -1 = 0\\
24x^2-24x+c = 0.
\end{cases}
$$
Replacing $c=-24x^2 +24x$ in the first equation you obtain
$$16x^3-12x^2+1=(2x-1)^2(4x+1) = 0.$$
By direct check you can see that $c=6$ gives a root $x=\frac12$ with multiplicity $3$, whereas $c=-\frac{15}2$ gives a root $x=-\frac14$ with multiplicity $2$, has required.
In conclusion all the functions
$$f(x) = \sqrt[3]{8x^3-12x^2+cx -1}$$
with $c>-\frac{15}2$ satisfy the requirements.


TITLE: Checking some work on finding roots
QUESTION [1 upvotes]: OK, I have the following response function:
$$H(\omega) = \frac{1-\omega^2 LC}{1+\omega^2 LC - i \omega RC}$$
I want to find where it becomes $\frac{1}{\sqrt{2}}$.
This should be simple enough. First I multiply the whole thing by its complex conjugate, which gives me the absolute value squared, or 1/2:
$$\frac{1-\omega^2 LC}{1+\omega^2 LC - i \omega RC}=\frac{(1-\omega^2 LC)^2}{(1+\omega^2 LC)^2 + \omega^2 R^2C^2} = \frac{1}{2}$$
Then I want to solve for omega. Since this is kind of ugly as it is I multiply both sides by $2((1+\omega^2 LC)^2 + \omega^2 R^2C^2)$ and end up with
$$2(1-\omega^2 LC)^2=(1+\omega^2 LC)^2 + \omega^2 R^2C^2$$
which yields
$$(1-\omega^2 LC)^2= \omega^2 R^2C^2$$
which I can take the square roots of both sides and turn it into a quadratic
$$(1-\omega^2 LC)= \omega RC \rightarrow 1-\omega RC - \omega^2LC = 0$$
I pull out the old quadratic formula. $\omega = \frac{RC \pm \sqrt{R^2C^2+4LC}}{2LC}$
On the plus side we end up with $\frac{2R^2C^2 + 2RC\sqrt{R^2C^2+4LC}+4LC}{2LC}=\frac{R^2C}{L}+\frac{R}{L}\sqrt{R^2C^2+4LC}+2$
and on the minus side $\frac{2R^2C^2 - 2RC\sqrt{R^2C^2+4LC}+4LC}{2LC}=\frac{R^2C}{L}-\frac{R}{L}\sqrt{R^2C^2+4LC}+2$
Anther method I thought of was to try and break up the quadratic "by hand" -- that is, try to come up with some square root of the coefficient of omega squared and half of RC, but down that path lieth madness.
OK, seems fine. But I am told that the answer you ought to get is $\omega = \frac{1}{RC}$. So either a) I messed up badly or b) I am being told wrong.
Did I miss something here? This isn't even calculus.
EDIT: looking at where I messed up:
OK Seeing as I messed up here:
$$2(1-\omega^2LC)^2 = (1+\omega^2LC)^2 + \omega^2 R^2C^2$$
That really ought to be
$$(2 - 4\omega^2LC + 2\omega^4L^2C^2) = 1 + 2\omega^2LC + \omega^4L^2C^2+ \omega^2 R^2C^2$$
Which then becomes
$$(1 - 6\omega^2LC + \omega^4L^2C^2) = \omega^2 R^2C^2$$
turning that into something like a quadratic
$$1+(6LC-R^2C^2)\omega^2+ \omega^4L^2C^2=0$$
(and substituting $u$ for $\omega^2$  means the LHS reduces to $ (1+(6LC-R^2C^2)u + L^2C^2u^2)$
We hit it with the quadratic formula. $$\frac{R^2C^2-6LC \pm \sqrt{36L^2C^2-12R^2LC^3+R^4C^4-4L^2C^2}}{2L^2C^2}=\frac{R^2C^2-6LC \pm \sqrt{32L^2C^2-12R^2LC^3+R^4C^4}}{2L^2C^2}=\frac{R^2}{2L^2}-\frac{3}{L}\pm \frac{\sqrt{32L^2-12R^2LC+R^4C^2}}{2L^2C}$$
Still getting crazy numbers.... hmmm.

REPLY [0 votes]: You messed up at least once, in this step:
$$2(1-\omega^2 LC)^2=(1+\omega^2 LC)^2 + \omega^2 R^2C^2$$
which yields
$$(1-\omega^2 LC)^2= \omega^2 R^2C^2$$


TITLE: Norm of a tensor product of operators
QUESTION [13 upvotes]: I have two Hilbert spaces $H_1$ and $H_2$ which are subspaces of a bigger Hilbert space $H$.
I also have two bounded linear functions $T_1:H_1\rightarrow H$ and $T_2:H_2\rightarrow H$.
I define the tensor product space $F=H_1\otimes H_2$, and a linear function on it $T=(T_1\otimes T_2)$. The vector space $F$ has the induced inner product from the Hilbert spaces:
$$\langle\phi_1\otimes \psi_1, \phi_2 \otimes \psi_2\rangle = \langle\phi_1,\phi_2\rangle\langle\psi_1,\psi_2\rangle$$
and therefore an induced norm.
I want to show that $\|T\| =\|T_1\| \cdot\|T_2\|$, but I'm stuck since I cant show that
$\|T\| \leq \|T_1\| \cdot\|T_2\|$ (the other inequality I've already shown).
Can anyone help?

REPLY [3 votes]: Let me add the other direction. Suppose $\varepsilon >0$. Then from the boundedness of operators $T_{1}$ and $T_{2}$ we know that there exist unit vectors in the Hilbert spaces $\psi \in H_{1}$, $\xi \in H_{2}$ such that:
$\left \| T_{1} \psi \right \|> \left \| T_{1} \right \| - \epsilon$, $\left \| T_{2} \xi \right \|> \left \| T_{2} \right \| - \epsilon$
Using this we can use the definition of the tensor product to see that:
$\left \| \left (T_{1}\otimes T_{2}  \right )\left ( \psi\otimes \xi \right ) \right \|_{H_{1}\bigotimes H_{2}}=\left \| \left ( T_{1}\psi\otimes T_{2}\xi \right ) \right \|_{H_{1}\bigotimes H_{2}}=\left \|T_{1}\psi \right \|_{H_{1}}  \left \| T_{2}\xi \right \|_{H_{2}}\geq$
$ \geq\left \| T_{1} \right \|\left \| T_{2} \right \|-\epsilon \left \| T_{1} \right \| - \epsilon \left \| T_{2} \right \| + \epsilon^{2}\geq\left \| T_{1} \right \|\left \| T_{2} \right \|-\epsilon \left \| T_{1} \right \| - \epsilon \left \| T_{2} \right \|$
Sending $\epsilon$ to 0 shows the desired result.