text:
\section{Information Extraction over a Noisy Channel}

We now discuss the case where the sender and receiver communicate via a noisy channel. We determine the maximum number of sequences that can be recovered by the receiver in any equilibrium of the game. We present a notion of the asymptotic rate of information extraction and we show that it is equal to the minimum of the information extraction capacity of the sender and the zero-error capacity of the noisy channel.

\subsection{Stackelberg equilibrium of the game}

Recall the definition of the perfectly decoded set $\Dscr(g_n,s_n)$ from \eqref{eq:decod-set-noisy}, when the receiver plays $g_n$ and the sender plays $s_n$. For any strategy $g_n$ of the receiver, consider $ \pbest(g_n) $ defined as
\begin{align}
   \pbest(g_n) = \arg \min_{s_n \in \best(g_n)} |\Dscr(g_n,s_n)|.  \label{eq:worst-best-resp}
\end{align}
Thus, $ \pbest(g_n) $ is the set of best responses which give the least objective value to the receiver. Let $$\Zscr(y) = \supp(P_{Z|Y}(\cdot | y)),$$ where $y$ is an input to the channel. Note that since the output space of the channel is $\Xscr^n$, $\Zscr(y) \subseteq \Xscr^n $ for all $ y $.

In the following theorem, we show that the receiver can at most recover $ \min\curly{\alpha(\Gs^n),\alpha(\Gc^n)} $ number of sequences in an equilibrium. The idea of the proof is as follows. We consider the independent sets in $\Gs^n$ and $\Gc^n$ of the size $\min\{ \alpha(\Gs^n),\alpha(\Gc^n)\}$ denoted as $I_{\mathsf{s}}^n$ and $I_{\mathsf{c}}^n$ respectively.  For every channel input sequence in $I_{\mathsf{c}}^n$, the receiver maps the corresponding output set to a unique sequence in $I_{\mathsf{s}}^n$. This establishes a one-to-one correspondence between the sequences in $I_{\mathsf{s}}^n$ and $I_{\mathsf{c}}^n$. Since $I_{\mathsf{s}}^n$ is an independent set in $\Gs^n$, the sender complies with the receiver and maps the sequences to their respective input sequences in $I_{\mathsf{c}}^n$. The receiver is thus able to recover the set $I_{\mathsf{s}}^n$ of size $\min\{ \alpha(\Gs^n),\alpha(\Gc^n)\}$.

\begin{theorem} \label{thm:stac-eq-recov-ind-no}
Let $n \in \Nbb$. Consider a sender with utility $\ut$ and let $\Gs^n$ be the corresponding sender graph. Let $\Gc^n$ be the confusability graph of the channel $P_{Z|Y}$. For all Stackelberg equilibrium strategies $g_n^*$ of the receiver,
  \begin{align}
  \min_{s_n \in \best(g_n^*)}|\Dscr(g_n^*,s_n)| = \min\{ \alpha(\Gs^n),\alpha(\Gc^n)\}. \non
  \end{align}
\end{theorem}
\begin{proof}
Consider a Stackelberg equilibrium strategy $ g_n^* $ of the receiver.  It is known from Lemma~\ref{lem:dec-set-ind-set}, that the set of perfectly recovered sequences from the sender can be at most $ \alpha(\Gs^n) $ and hence $ \min_{s_n \in \best(g_n^*)}|\Dscr(g_n^*,s_n)| \leq \alpha(\Gs^n) $. Further, at most $ \alpha(\Gc^n) $ sequences can be transmitted with zero error through the channel and hence for all $ s_n $, $ |\Dscr(g_n^*,s_n)| \leq \alpha(\Gc^n) $. Together, it follows that
    \begin{align}
  \min_{s_n \in \best(g_n^*)}|\Dscr(g_n^*,s_n)| \leq \min\{ \alpha(\Gs^n),\alpha(\Gc^n)\}. \non
    \end{align}
    We now show that equality holds in the above relation.

 Let $ d = \min\{ \alpha(\Gs^n),\alpha(\Gc^n)\} $. Clearly, there exists an independent set $ I_{\mathsf{s}}^n $ in $ \Gs^n $ such that $ |I_{\mathsf{s}}^n| = d $. Similarly, there exists an independent set $ I_{\mathsf{c}}^n $ in $ \Gc^n $ such that $ | I_{\mathsf{c}}^n| = d$.
  Let the sequences in the sets $I_{\mathsf{s}}^n$ and $I_{\mathsf{c}}^n$ be denoted as  $x^i$ and $y^i$ respectively, with  $i \in [d]$ and $x^i, y^i \in \Xscr^n$. With this convention, define the strategy $g_n$ as
  \begin{align}
g_n(z)  = \left\{
    \begin{array}{c l}
      x^i & \mbox{if} \; z \in \Zscr(y^i)  \\%\%; \mbox{for}\; 1 \leq i \leq d \\
      \Delta & \mbox{if} \; z \notin \bigcup_{i=1}^{d} \Zscr(y^i)
    \end{array}
\right.. \label{eq:str-of-rec}
  \end{align}
  We show that the strategy $ g_n $ of the receiver ensures that all strategies $s_n$ in the set of best responses $ \best(g_n) $ are such that $\Zscr(s_n(x^i)) = \Zscr(y^i)$ for all $i \in [d]$. Fix an index $ i $, let $ s_n $ be any strategy for the sender and let     $s_n(x^i) = y^* \in \Xscr^n$. Notice that if $ \Zscr(y^*) \nsubseteq \bigcup_{j=1}^{d} \Zscr(y^j)$, then $g_n(z) = \Delta$ for some   $z \in \Zscr(y^*)$, $ z \notin \bigcup_{j=1}^{d} \Zscr(y^j)$. This gives that $\expec{\ut_n(g_n(Z),x^i)} = -\infty $.  Thus, $ y^* $ is such that $ \Zscr(y^*) \subseteq \bigcup_{j=1}^{d} \Zscr(y^j) $.

  Writing $\Zscr(y^*) = \bigcup_{j=1}^{d}\Zscr(y^*) \cap \Zscr(y^j)$, it follows that
    \begin{align}
      &    \expec{\ut_n(g_n(Z),x^i)}  \non \\
                &=\sum_{z \in \;\bigcup_{j=1}^{d}\Zscr(y^*) \cap \Zscr(y^j)} P_{Z|Y}(z|y^*)\ut_n(g_n(z),x^i) \non \\

          &= \sum_{j=1}^{d}\sum_{z \in \Zscr(y^*) \cap \Zscr(y^j)} P_{Z|Y}(z|y^*)\ut_n(x^j,x^i). \non
    \end{align}
The last equation follows from the definition of $g_n$. Since $I_{\mathsf{s}}^n$ is an independent set in $\Gs^n$,  $\ut_n(x^j,x^i) < \ut_n(x^i,x^i) = 0 $ for all $j \neq i$ and hence
    \begin{align}
&      \sum_{j=1}^{d}\sum_{z \in \Zscr(y^*) \cap \Zscr(y^j)} P_{Z|Y}(z|y^*)\ut_n(x^j,x^i) \leq 0 \non

    \end{align}
    with equality if and only if $ \Zscr(y^*) = \Zscr(y^i) $. Thus, the strategy $ y^* $ is such that  $ \Zscr(y^*) = \Zscr(y^i) $. Clearly, this holds for all $ s_n \in \best(g_n) $ and for all  $ i \in [d] $.

It easy to see that the utility of the sender and the receiver do not depend on the exact choice of $ y^* $ so long as $ \Zscr(y^*)=\Zscr(y^i) $. Hence, without loss of generality, we consider $ s_n $ to be such that $s_n(x^i) = y^i$ for all $ i \in [d] $.
    Thus, when the sequence $x^i \in I_{\mathsf{s}}^n$ is observed by the sender, it encodes it as $y^i$. The channel generates an output $z$, which belongs to the support set $\Zscr(y^i)$. The receiver maps all such $z$ to $x^i$ thereby ensuring $\Pbb(\wi{X} = x^i | X = x^i) = 1$ for all $i \in [d]$. Thus, for all $x^i \in I_{\mathsf{s}}^n$ and  $s_n \in \best(g_n)$,  $x^i \in \Dscr(g_n,s_n)$. Hence $\Dscr(g_n,s_n) \supseteq I_{\mathsf{s}}^n$ for all $s_n \in \best(g_n)$. Since $|I_{\mathsf{s}}^n| = d$,  $|\Dscr(g_n,s_n)| \geq d$. Using $|\Dscr(g_n,s_n)| \leq d = \min\{\alpha(\Gs^n),\alpha(\Gc^n)\}$, it follows that for all Stackelberg equilibrium strategies $g_n^*$, $ \min_{s_n \in \best(g_n^*)}|\Dscr(g_n^*,s_n)| = \min \{\alpha(\Gs^n),\alpha(\Gc^n)\}$.
  \end{proof}

  Thus, from the strategy defined in \eqref{eq:str-of-rec}, it can be observed that the receiver decodes meaningfully only for a subset of sequences. In particular, it chooses $d$ number of inputs, $y^i $ with $ i \; \in [d]$, which can be distinguished from each other and maps the respective support sets, $\Zscr(y^i)$, to $d$ distinct sequences $x^i$. For the rest of the outputs from the channel, the receiver declares an error $\Delta$. In response, the optimal strategy for the sender is (without loss of generality) such that it maps the sequences $x^i$ to the inputs $y^i$. Also, for all strategies $ s_n $ and for all $x \in \Xscr^n \setminus \{x^i\}_{ i \in [d] }$, $s_n(x) = y^*$, where $y^*$ is such that $\Zscr(y^*) \subseteq \bigcup_{j=1}^{d} \Zscr(y^j)$. This is because for any other input $y' \neq y^*$, if $\Zscr(y') \nsubseteq \bigcup_{j=1}^{d} \Zscr(y^j)$, then the channel output $z$ may lie outside $\bigcup_{j=1}^{d} \Zscr(y^j)$ for which $g_n(z) = \Delta$ and the corresponding utility is $-\infty$.

\subsection{Asymptotic rate of information extraction}

The following is a generalization of the information extraction capacity of a sender.
\begin{definition}[\textit{Asymptotic rate of information extraction}] \label{defn:max-rate}
Let $\{g_n^*\}_{n \geq 1}$ be a sequence of Stackelberg equilibrium strategies for the receiver and let $ \{R(g_n^*)\}_{n \geq 1} $ be the corresponding sequence of rate of information extraction. The asymptotic rate of information extraction, denoted by $\Rscr$, is given as
  \begin{align}
    \Rscr = \lim \sup_{n} R(g_n^*). \non
  \end{align}
\end{definition}
When the channel is noiseless, this quantity is equal to the information extraction capacity of the sender. We now use the results derived in the last section to determine the asymptotic rate of information extraction $\Rscr$ for the noisy channel case.
\begin{theorem} \label{thm:limit-D-min-of-capa}
Consider a sender with utility $\ut$ and let $\Gs$ be the corresponding sender graph. Let $\Gc$ be the confusability graph of the channel $P_{Z|Y}$. Then the asymptotic rate of information extraction is given as
  \begin{align}
    \Rscr = \min\{\capacity, \Theta(\Gc)\}. \non
  \end{align}
\end{theorem}
\begin{proof}
  Let $\{g_n^*\}_{ n \geq 1}$ be a sequence of Stackelberg equilibrium strategies for the receiver. From Theorem~\ref{thm:stac-eq-recov-ind-no},
  \begin{align}
\min_{s_n \in \best(g_n^*)}|\Dscr(g_n^*,s_n)| = \min \{\alpha(\Gs^n),\alpha(\Gc^n)\}. \non
  \end{align}
It can be shown that, for a discrete memoryless channel given by \eqref{eq:dmc-defn}, the graph $\Gc^n$ is same as the graph constructed by taking $n$-fold strong product of $\Gc$  \cite{shannon1956zero}, \ie, $     \Gc^n = \Gc^{\boxtimes n} $.

  Thus, $ \min_{s_n \in \best(g_n^*)}|\Dscr(g_n^*,s_n)| = \min \{\alpha(\Gs^n),\alpha(\Gc^{\boxtimes n})\}$  and hence
  \begin{align}
    R(g_n^*) &=   \min_{s_n \in \best(g_n^*)} |\Dscr(g_n^*,s_n)|^{1/n} \non \\

    &= \min\curly{ \alpha(\Gs^n)^{1/n},\alpha(\Gc^{\boxtimes n})^{1/n}}. \non
  \end{align}
The claim follows after taking the limit.
\end{proof}

The above result states that given a sender with information extraction capacity $\capacity$, the zero-error capacity of the channel should be at least this number in order to extract maximum possible information from the sender. Alternatively, given the channel, the asymptotic rate of information extraction from any sender is bounded by the zero-error capacity of the channel. As long as both quantities are greater than unity, the receiver can extract exponentially large number of sequences from the sender.

Using this result and the bounds from earlier sections,  the following results follow.
\begin{theorem}
  Consider a sender with utility $ \ut $ and let $ \Gs $ be the corresponding sender graph. Let $ \utsym $ be its symmetric part and let $ \Gsym $ be the corresponding sender graph. Let $ \Gc $ be the confusability graph of the channel $P_{Z|Y}$.
  \begin{enumerate}
  \item If $ \Theta(\Gsym) \leq \Theta(\Gc)$, then
  \begin{align}
  \Rscr = \capacity. \non
  \end{align}
  \item If $\Gamma(\ut) \geq \Theta(\Gc)$, then
\begin{align}
\Rscr = \Theta(\Gc). \non
\end{align}
\end{enumerate}
\end{theorem}
\begin{proof}
The proofs follow by using Theorem~\ref{thm:limit-D-min-of-capa} along with Theorem~\ref{thm:upper-bnd-Shannon-cap-symm} for part 1) and Theorem~\ref{thm:cap-lower-bound} for part 2) respectively.
\end{proof}
The above result states that if the Shannon capacity of the symmetric sender graph is less than the zero-error capacity of the channel, then the asymptotic rate of information extraction is simply the information extraction capacity of the sender. The second part of the theorem states that the receiver can recover an exponential number of sequences even when the information extraction capacity of the sender is less than the zero-error capacity of the channel, provided $\Theta(\Gc) > 1$.

This concludes our analysis on this topic of information extraction from a strategic sender. We have seen that the strategic setting demands a new line of analysis, that uses in part the traditional tools of information theory, but is rooted in concepts of game theory. It also leads to new concepts. Our main take away is that the \textit{information extraction capacity of the sender}, a concept we defined and introduced in this paper, appears to be a fundamental quantity. It plays a role loosely analogous to that of the entropy of a source, characterizing the extent of information the sender can provide (or can be extracted from it).  Future research will reveal the extent to which this analogy holds.

config: arxiv


TITLE: Compute the gradient of a function in squared 2-norm
QUESTION [0 upvotes]: I have a function $f(x)$ in the $2$-norm
$$   f(x)= \frac{1}{2}\cdot \big\|Ax−b\big\|^2$$
How can i compute it's gradient?

REPLY [0 votes]: A simple but labor-intensive way is to develop the expression $\frac{1}{2}\cdot \big\|Ax-b\big\|^2$ as follows and then calculate the partial derivatives.
\begin{align}
f(x)=
&
\frac{1}{2}\cdot \big\|Ax-b\big\|^2
\\
=&
\frac{1}{2}\cdot \big\langle Ax \;\big|\; Ax\big\rangle
- \big\langle Ax \;\big|\; b\big\rangle
+\frac{1}{2}\cdot \big\langle b \;\big|\; b\big\rangle
\\
=&
\frac{1}{2}\cdot
\Big\langle (A_{ij})_{m\times n}\cdot(x_{i1})_{n\times 1}
\;\Big|\;
(A_{ij})_{m\times n}\cdot(x_{i1})_{n\times 1}\Big\rangle
\\
&\qquad\qquad
-
\Big\langle (A_{ij})_{m\times n}\cdot(x_{i1})_{n\times 1}
\;\Big|\;
(b_{i1})_{m\times 1} \Big\rangle
+
\frac{1}{2}\cdot
\Big\langle (b_{i1})_{n\times 1}
\;\Big|\;
(b_{i1})_{m\times 1}
\Big\rangle
\\
=&
 \frac{1}{2}\cdot
 \Big\langle
 \Big(\sum_{p=1}^{n}A_{ip}\cdot x_{p1}\Big)_{m\times 1}
 \;\Big|\;
 \Big(\sum_{q=1}^{n}A_{iq}\cdot x_{q1}\Big)_{m\times 1}
\Big\rangle
 \\
 &\qquad\qquad
 -
 \Big\langle
 \Big(\sum_{\ell=1}^{n}A_{i\ell}\cdot x_{\ell 1}\Big)_{m\times 1}
 \;\Big|\;
 (b_{i1})_{m\times 1}
 \Big\rangle
 +
\frac{1}{2}\cdot
\Big\langle (b_{i1})_{m\times 1}
\;\Big|\;
(b_{i1})_{m\times 1}
\Big\rangle
\\
=&
\frac{1}{2}\sum_{i=1}^{m}\sum_{p=1}^{n}\sum_{q=1}^{n}
A_{ip}\cdot x_{p1}\cdot A_{iq}\cdot x_{q1}
-
\sum_{i=1}^{m}\sum_{\ell=1}^{m}
A_{i\ell}\cdot x_{1\ell}\cdot b_{1 i}
+\frac{1}{2}\sum_{i=1}^{m}b_{1i}b_{1i}
\end{align}


TITLE: Calculating presentations for the normal subgroup of a semidirect product
QUESTION [6 upvotes]: Let $G$ be a group with a finite presentation $\langle S \cup S' | R \cup R'\rangle$.  Assume that I happen to know that $G$ is the semidirect product of a normal subgroup $N$ and another subgroup $H$.  Furthermore, assume that $H$ is the subgroup generated by $S'$ and that $H \cong \langle S' | R' \rangle$.  Is there any algorithm to calculate a presentation for $N$?  Assume that we know how to solve all the standard problems (the word problem, the conjugacy problem, the membership problem for $H$ and $N$, etc) in $G$ itself.
Here is an easy example to show what kinds of issues arise.  Let $G$ be the free group on two letters $x$ and $y$.  We then have a split short exact sequence
$$1 \rightarrow N \rightarrow G \rightarrow H \rightarrow 1,$$
where the group $H$ is the cyclic group generated by $y$ and $N$ is an infinite rank free group (it consists of all words in $x$ and $y$ the sum of whose $y$-exponents is $0$).  The moral is that we cannot hope for a finite presentation for $N$, and our algorithm must return an infinite presentation.
EDIT : Here's two nice examples of what I am talking about.  First, let $G = PSL_2(\mathbb{Z})$ and let $H = PSL_2(\mathbb{Z}/2\mathbb{Z})$.  Then it turns out that $H$ is isomorphic to the symmetric group on $3$ letters and there is a splitting of the natural surjection $G \rightarrow H$.  How can one compute the kernel of this map?
For another example, let $G = SP_4(\mathbb{Z})$ and let $H = SP_4(\mathbb{Z}/2\mathbb{Z})$.  Then $H$ is isomorphic to the symmetric group on $6$ letters (this comes from the action on odd theta characteristics), and there is a splitting of the homomorphism $G \rightarrow H$.  How can one compute the kernel of this map?
As you might guess from these examples, I have in mind applications to the theory of modular forms.  I am looking for practical algorithms for computation, not theoretical results.

REPLY [1 votes]: If you have explicit finite presentations of G and H is small and finite, then you should be able to just ask GAP or magma for a presentation of the kernel of the projection.  This is another disguise of the Schreier transversal.  Let me know if you want code sample or algorithmic references.  This will likely fail for things like Sp(6,13) which are simply too large, but I think it should work out for Sym(3) and Sym(6).


TITLE: Biconditional Introduction in natural deduction
QUESTION [3 upvotes]: I'm working on a first-order logic question and I'm a little stuck as to what I should be assuming in my first subproof (this is always my problem). I'm supposed to prove this biconditional argument with no premises.

$P → (Q → R)) \leftrightarrow ((P ∧ Q) → R)$

I know that in order to do this, I need to prove that [P → (Q → R))] → [((P ∧ Q) → R)] ^ [((P ∧ Q) → R)] → [P → (Q → R))].
If I'm starting with my first subproof assuming P → (Q → R)), what is the next thing I need to assume so I can end up proving ((P ∧ Q) → R)? This is my thought process, but I get stuck at the point where I need to prove a →Intro.

P → (Q → R))
     P
     Q→R  →Elim 1
        Q
        P^Q  ^Intro 2,4
        R  →Elim 3,4

After this I'm not quite sure what to do - how can I isolate it out so that R is the consequence of both P and Q?

REPLY [1 votes]: It seems you really got it. Indeed, for a formal derivation using natural deduction in the general case, we just need to observe the logical form of the goals and decide which rules to use.
In your particular case, the statement you want to prove has the form of a biconditional $\phi \leftrightarrow \psi$, so we just have to prove that $\phi \rightarrow \psi$ and $\psi \rightarrow \phi$ holds first and appy the biconditional introduction rule:

$\frac{\frac{D}{\phi \rightarrow \psi}, \frac{D'}{\psi \rightarrow \phi}}{\phi \leftrightarrow \psi}$

Now we just observe the logical form of $\phi$ and $\psi$ and proceed with the other steps.


TITLE: How to enclose a ball more than once with a surface homeomorphic to $S^2$? In 3D.
QUESTION [1 upvotes]: In 3 dimensional space, how to enclose a monopole (either point-like or ball-like, both types exist.) more than once with a surface homeomorphic to $S^2$?

REPLY [1 votes]: If $M$ is a three-manifold and $B$ is a (smoothly embedded, tame) three-ball in $M$, then just take level surfaces of the distance function from $B$. That is, take the surfaces
$$S_\epsilon = \{p\in M\ |\ d(p,B) = \epsilon\}.$$
For small $\epsilon$, all $S_\epsilon$ will be diffeomorphic to $\partial B = S^2$.


TITLE: Combining two DFAs into an NFA to recognize concatenation
QUESTION [2 upvotes]: Suppose we have two separate DFAs that each recognize their own language. What is the most efficient way to combine these two DFAs into one NFA that recognizes the concatenation of both languages?

REPLY [5 votes]: To make an NFA for the concatenation of $A$ and $B$, put the states of $A$ and $B$ together.
Keep all the transitions of $A$ and of $B$, and
add $\epsilon$-transitions from the final states of $A$ to the initial state  of $B$.
Make the initial state of the combined machine the same as the initial state of $A$.
Make the final states of the combined machine the same as the final states of $B$.
This construction probably appears in your book, as part of the proof that regular expressions are equivalent to NFAs. The proof must include a method for converting a regular expression of the form $AB$ to an NFA, given NFAs for regular expressions $A$ and $B$.  It certainly appears in the Hopcroft and Ullman book.


TITLE: Very simple question regarding sum/difference identity
QUESTION [1 upvotes]: If I have $\sin(0.7x-47t+C)$ where do I carry my constant $C$? The same with my sum-to-product identities.
This problem is showing up for me because I'm studying mechanical waves at the moment.
I thank you in advance.

REPLY [1 votes]: Using the fact that $\sin(\alpha+\beta) = \sin\alpha\cos\beta + \cos\alpha\sin\beta$, we can separate the constant $C$:
$$\sin\big((0.7x-47t)+C\big) = \sin(0.7x-47t)\cos C + \cos(0.7x-47t)\sin C$$
You might find the Wikipedia page on trigonometric identities useful.


TITLE: Probability of an event happening N or more times
QUESTION [14 upvotes]: I need to determine the probability of an event happening N or more times over M iterations. I know the probability of the event in question happening and its likelihood does not change over time.
For example, say I am rolling a six-sided die and I want to know what is the probability that over the course of 100 rolls I'll roll a 1 or a 2 at least 75 times?
Is there a nice and tidy formula for computing such probabilities?
Thanks

REPLY [1 votes]: For a simple formula, Hoeffding's inequality might be helpful.


TITLE: How to "formally" prove that $x(t)=\frac{1}{4}(2-t)^2\theta(2-t)$ solves $\dot{x}=-\text{sgn}(x)\sqrt{|x|},\,x(0)=1$?
QUESTION [1 upvotes]: How to "formally" prove that $x(t)=\frac{1}{4}(2-t)^2\theta(2-t)$ solves $\dot{x}=-\text{sgn}(x)\sqrt{|x|},\,x(0)=1$? (with $\theta(t)$ the standard unitary step function).
I have found the equation studying these paper by V. T. Haimo:  Finite Time Differential Equations and Finite Time Controllers, and I believe the finite duration solution is given by:
$$x(t)=\frac{1}{4}(2-t)^2\theta(2-t)$$
Which I found from the comparison with the other equation $\dot{y}=-\sqrt{y},\,y(0)=1$ which solution is $y(t) = \frac{1}{4}(2-t)^2$.
Actually, the first solution I found was:
$$x(t) = \frac{1}{4}\left(1-\frac{t}{2}+\left|1-\frac{t}{2}\right|\right)^2,$$
and so far, I have not been able to formally prove that $x(t)$ is the "true" solution, even when graphically is obvious (and theoretically, since ODEs stands Locally the Existence and Uniqueness of solutions, I believe it fits).
For every try, to made coincident both parts of the equation (right and left hand sides), I have to made an illegal operation like:

assuming that is equivalent to use $\text{sgn}(x(t)\cdot\theta(2-t)) \cong \text{sgn}(x(t))\cdot\theta(2-t)$
assuming that is equivalent to use $\theta(t) = \frac{1+\text{sgn}(t)}{2}$ or $\theta(t) = \frac{1}{2}\left(1+\frac{1}{\text{sgn}(t)}\right)$
assuming that is equivalent to use $\text{sgn}(x(t)) \cong \frac{1}{\text{sgn}(x(t))}$
assuming that is equivalent to use $\int \theta(t)\,dt = \int \theta^n(t)\,dt,\quad n\in \mathbb{Z}^+$

And other similar things which I beforehand know are mistaken (just by taking their derivatives I know it leads to different functions), but when displayed on graphs, they take the same values. So I know I am making mistakes (since this are distributions instead of functions and I don´t know how to formally work with them), but also because of been "vague" with the treatment have let me find the previous candidates to the solution, so I don´t know if I am finding something or it is everything wrong (maybe it is just the same as taking the solutions piecewise, but at least the differential equations at first doesn't look to be defined piecewise - at least for me, since I know beforehand that a finite duration solution will lead to definition issues on the diff. eq. since it becomes zero forever after the ending time, $t_F = 2$ on this example).
Hope you can elaborate on how to prove it explaining why the listed things are conceptually different (I am asking here for the "prove", not an explanation of how to find it, this because of my lack of background, it will be more useful to see how it is done and then try to search for the missing things I need to look for to understand the explanations).  Beforehand thanks you very much.

REPLY [1 votes]: Since $x(0)=1>0$, then one can see the solution is decreasing to zero and then stays there when it reaches this value. So, the differential equations simplifies to $\dot{x}=-\sqrt{x}$.
This can be rewritten as $$\dfrac{dx}{\sqrt{x}}=-ds$$ and integrating yields
$$\int_{x(0)}^{x(t)}\dfrac{dx}{\sqrt{x}}=-\int_0^tds$$ which yields
$$2(\sqrt{x(t)}-1)=-t.$$ Reorganizing and squaring then yields
$$x(t)=\dfrac{1}{4}(2-t)^2$$ but this is only valid for $t\in[0,2]$. For $t>2$, $x(t)=0$, so we multiply that expression by $\theta(2-t)$ to get the final result.
The expression you found with the absolute values is also valid and is equivalent to the one using the Heaviside function.


TITLE: Probability of Winning in Sports
QUESTION [5 upvotes]: In sports such as volleyball (prior to 1999), you can score a point only if it is your turn, with turns alternating until a point is scored. Suppose your probability of scoring a point when it is your turn is $p$, and your opponent's probability of scoring a point when it is her turn is $q$. Find a formula for the probability $S$ that you are the first to score the next point, assuming it is currently your turn.
I have little experience with probability problems, so any help would be well appreciated!

REPLY [9 votes]: Assume the probability of you scoring the next point if it is your turn now is $x$.
The probability is p that you score immediately. The probability is $(1-p)(1-q)$ that you don't score, then your opponent doesn't score, and it's your turn again to win with probability $x$.
So $x = p + (1-p)(1-q) x$, and you calculate $x$ from that getting $x  = \frac p{ p + q - pq}$


TITLE: How to predict change in angles by moving a node (D)
QUESTION [0 upvotes]: ay I have two fixed points F and A, and I move node D (which is connected to A by node J and connected to F by node H and K (review added pictures)), how could I predict how the angles would change?
Is there any way to say how much I need to move my node to get specified angles?
Hope you guys understand, and please let me know if I am unclear.
Angles before moving D
Angles after moving D

REPLY [0 votes]: Just define two vectors which are connected to your point D, $\vec{DH}=\vec{H}-\vec{D}$ and $\vec{DJ}=\vec{J}-\vec{D}$, then take the dot product between the two, divide by the magnitude of both vectors and then take the inverse cosine of the ratio. The result is the angle between the two vectors. After you move D, repeat the process to get the new angles.


TITLE: Reading the Masters: Which works are the most cited in the History of Mathematics?
QUESTION [5 upvotes]: I was thinking about Abel's advice to read the masters, yet many people claim that reading the old masters (Euclid, Archimedes, Newton, Euler, Gauss, Lagrange, and so on) is not a good idea today, for various reasons.  However, if one were to read, or at least have reference to, the most often cited, and original, books in mathematics, wouldn't there be much to gain?
For example, I expect Euclid's Elements to be on the list.  Newton's Principia, particularly his Treatise on Fluxions, is valuable historically, rightly as the origins of calculus, but never cited for a reference in modern calculus texts, thus would not be on the list.  Gauss's Disquisitiones Arithmeticae, should be on the list.  Dickson's Histories of the Theory of Numbers is a nice reference to have as well... it's very often cited.
So what are the most referenced works in Mathematics?  Which works would be "the base of the reference tree"?

REPLY [1 votes]: The notion that Euclidean geometry is "still the same" is a bit naive. A pass through Moise's book "Elementary Geometry from an Advanced Standpoint" will convince you of this. In particular, modern Euclidean geometry relies pretty solidly on the notion of measure -- the length of a line, the measure of an angle -- rather than on ideas of proportion as an abstract way of comparing things. This modern approach allows one to use algebraic methods to prove many things more easily.
In much the same way, learning projective geometry from Hartshorne's little book shows you the connections between various geometric things (Fano's Axiom, for instance, or Pappus' Theorem) and the underlying algebraic properties of an algebraic entity $F$ that's associated to a (rich enough) projective geometry (e.g., for geometries that satisfy Pappus' Theorem, the associated $F$ might have a commutative multiplication operation, although I may be misremembering this -- it might be that the operation is associative). You can read a lot of early but well-developed projective geometry texts that will not tell you about this because the formal notions of abstract algebra hadn't yet been developed.
I'm definitely keen on reading older texts, but there's a lot to be said for modern "revisionist" views as well. I'd prefer to read Milnor and Stasheff's Characteristic Classes to anything Whitney wrote, despite my huge admiration for Witney's work on sphere bundles (and almost anything else, too!).


text:
\begin{document}
\newtheorem{theorem}{Theorem}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}

\begin{center}
{\Large
A sign-reversing involution to count labeled \\
lone-child-avoiding trees    \\
}

\vspace{5mm}
David Callan  \\
\noindent {\small Department of Statistics,
University of Wisconsin-Madison,  Madison, WI \ 53706}  \\
{\bf callan@stat.wisc.edu}  \\
June 24 2014
\end{center}

\begin{abstract}
We use a sign-reversing involution to show that trees on the vertex set $[n]$, considered to be rooted at 1, in which no vertex has exactly one child are counted by $\frac{1}{n}\sum_{k=1}^{n} (-1)^{n-k}\binom{n}{k}\frac{(n-1)!}{(k-1)!} k^{k-1}$. This result corrects a persistent misprint in the Encyclopedia of Integer Sequences.

\end{abstract}

\vspace{2mm}

\section{Introduction} \label{intro}

\vspace*{-4mm}

A graph is said to be \emph{series-reduced} or \emph{homeomorphically irreducible} if no vertex has degree 2, and a tree is a connected graph with no cycles.
Several kinds of series-reduced trees have been enumerated, such as
\emph{free} (sequence \htmladdnormallink{A000014}{http://oeis.org/A000014} in OEIS \cite{oeis}\,),
\emph{rooted} (\htmladdnormallink{A059123}{http://oeis.org/A059123}),
\emph{labeled} (\htmladdnormallink{A005512}{http://oeis.org/A005512}), and
\emph{rooted labeled} (\htmladdnormallink{A060313}{http://oeis.org/A060313}),
the latter two differing only by a factor of the number of vertices.
A \emph{planted} tree is a rooted tree in which the root has degree 1.
Series-reduced planted trees are counted by
\htmladdnormallink{A001678}{http://oeis.org/A001678}.
Let us say a rooted tree is \emph{lone-child-avoiding} if no vertex has exactly one child.
A series-reduced planted labeled tree on vertex set $\{0,1,2,\dots,n\}$ with root 0 is equivalent to
a lone-child-avoiding tree on $[n]:=\{1,2,\dots,n\}
$: delete the root and its one edge and re-root the new tree at the child of the old root.

The number of lone-child-avoiding
rooted trees on $[n] $ is, of course, $n$ times the number of such trees with root 1.
We will show that the latter are counted by the alternating sum
\begin{equation}\label{eq1}
\frac{1}{n}\sum_{k=1}^{n} (-1)^{n-k}\binom{n}{k}\frac{(n-1)!}{(k-1)!} k^{k-1}\, ,
\end{equation}
correcting an erroneous entry in OEIS that has stood for 40+ years, namely
\htmladdnormallink{A002792}{http://oeis.org/A002792}, which is
 1, 0, 1, 1, 13, 51, 601, 4806, 39173, 775351 (that's all)  and surely should be  the sequence
1, 0, 1, 1, 13, 51, 601, 4803, 63673, 775351, $\dots$
(\htmladdnormallink{A108919}{http://oeis.org/A108919}) generated by (\ref{eq1}).

While the standard methods of recurrence relations and generating functions
can readily be applied to our problem (see \cite{meir}, \cite[Ex. 3.3.26]{gj} for similar applications), we will use a sign-reversing involution.
Section \ref{configs} introduces weighted objects whose total weight is obviously given by (\ref{eq1}).
Section \ref{invol} then presents a sign-reversing involution to show that the total weight is also equal to the number of trees being counted.

\section[G-configurations]{\protect{$\mbf{G}$}-configurations} \label{configs}

\vspace*{-4mm}

A rooted $G$-configuration of size $n$ is a hybrid graph object on the vertex set $[n]$ with $n-1$ edges, some of which are directed and some not as follows. The undirected edges
form a tree on some nonempty subset $V$ of $[n]$ with some element $r$ of $V$
designated as the root of the tree. There is exactly one directed edge (arc) from
each vertex in $[n]\, \backslash \,V$ to $[n]\, \backslash \,\{r\}$ (thus no arc goes into the root)
and no two arcs end at the same vertex.
We distinguish between \emph{tree} vertices (in the tree) and \emph{arc} vertices (that start an arc).
Figure 1 shows an example.

\begin{center}
\begin{pspicture}(-8,-2.1)(5,3.7)

\psdots(-2,2)(0,3)(2,2)(1,1)(2,1)(3,1)(2,0)
{\psset{linewidth=1.5pt}
\psdots(0,3)}
\psline(-2,2)(0,3)(2,2)(1,1)
\psline(2,0)(2,1)(2,2)(3,1)

\psbezier[linewidth=1pt,linecolor=blue,showpoints=false,arrowsize=1.5pt 2.5]{<-}(-7.1,3.1)(-7.4,3.6)(-6.6,3.6)(-6.9,3.12)

\psbezier[linewidth=1pt,linecolor=blue,showpoints=false,arrowsize=1.5pt 2.5]{<-}(-5.4,3.1)(-5.0,3.4)(-4.5,3.4)(-4.1,3.1)

\psbezier[linewidth=1pt,linecolor=blue,showpoints=false,arrowsize=1.5pt 2.5]{->}(-5.4,2.9)(-5.0,2.6)(-4.5,2.6)(-4.1,2.9)

\rput(-7,2.7){\textrm{{\blue \small $8$}}}
\rput(-5.7,3){\textrm{{\blue \small $9$}}}
\rput(-3.7,3){\textrm{{\blue \small $14$}}}

\rput(-3.8,2){\textrm{{\blue \small $5$}}}
\rput(-2,-0.3){\textrm{{\blue \small $2$}}}
\rput(-0.5,-0.3){\textrm{{\blue \small $6$}}}
\rput(1,-0.3){\textrm{{\blue \small $12$}}}

\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-3.4,2)(-2.2,2)

\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-1.9,0)(-0.6,0)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-0.4,0)(0.9,0)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](1.1,0.1)(1.9,.9)

\rput(0,3.3){\textrm{{\small $1$}}}
\rput(-1.9,1.7){\textrm{{\small $3$}}}
\rput(2.2,2.3){\textrm{{\small $10$}}}
\rput(1,0.7){\textrm{{\small $4$}}}
\rput(3,0.7){\textrm{{\small $11$}}}
\rput(2.2,0.7){\textrm{{\small $7$}}}
\rput(2,-0.3){\textrm{{\small $13$}}}

{\psset{linecolor=blue}
\psdots(-2,0)(-0.5,0)(1,0)
\psdots(-7,3)(-5.5,3)(-4,3)(-3.5,2)}

\rput(-1.5,-1.5){\textrm{{\small A G-configuration ( = rooted $G$-configuration with root 1) of size 14}}}
\rput(-1.5,-2.1){\textrm{{\small {\blue arcs and arc vertices in blue}}}}

\end{pspicture}
\end{center}
\centerline{Figure 1}

\vspace*{2mm}

The number of G-configurations of size $n$ with $k$ tree vertices is $\binom{n}{k}$ [\,choose tree vertices\,]
$\times\, k^{k-1}$ [\,form rooted tree, Cayley's formula \cite[Chap.\,30]{bookproofs}\,] $\times\, \underbrace{(n-1)(n-2)\  \cdots\ }_{n-k}$
[\,choose arcs\,].

Now we restrict the root to be 1. A (plain) $G$-configuration is a rooted
$G$-configuration whose root is 1, dividing the count by a factor of $n$. Assign a weight of $(-1)^{n-k}$
to each $G$-configuration of size $n$ with $k$ tree vertices. Thus the total weight of all
$G$-configurations of size $n$ is given by (\ref{eq1}).

\section{A sign-reversing involution} \label{invol}

\vspace*{-4mm}

We now define a sign-reversing involution on all $G$-configurations of size $n$ except the ones
whose tree has $n$ vertices and no lone children. The involution converts a lone child to an
arc vertex or vice versa, thereby changing the sign of the weight. The vertex $m$ to be
converted is the maximum among all the arc vertices and the lone-child vertices.
This maximum exists unless all vertices are in the tree and none is a lone child.

Suppose first that $m$ is an arc vertex. Either $m$ is a vertex in a cycle comprised of arcs or there is a path from $m$ along arcs terminating at some tree vertex $c$. In both cases, remove the arc that starts at $m$.
Then, in the first case, insert $m$ into the tree as the lone child of the root,
redirecting into $m$ all the edges that originally
went into the root (Figure 2a). An original arc $m\to m$ is lost, but an arc $a\to m$ with $a\ne m$ is retained.

\begin{center}
\begin{pspicture}(-8,-0.4)(8,3.3)

{\psset{linewidth=1.5pt}
\psdots(-2.5,3)
\psdots(4.5,3)}

\psdots(-3,1)(-3,2)(-2,1)(-2,2)

\psline(-3,1)(-3,2)(-2.5,3)(-2,2)(-2,1)

\psbezier[linewidth=1pt,linecolor=blue,showpoints=false,arrowsize=1.5pt 2.5]{->}(-4,3.1)(-4.5,3.6)(-5.5,3.6)(-6,3.1)

\rput(-3,.7){\textrm{{\small $4$}}}
\rput(-2.75,1.9){\textrm{{\small $7$}}}
\rput(-1.75,1.9){\textrm{{\small $9$}}}
\rput(-2,.7){\textrm{{\small $5$}}}
\rput(-2.5,3.3){\textrm{{\small $1$}}}

\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-5.9,3)(-5.1,3)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-4.9,3)(-4.1,3)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-3.9,2)(-3.1,2)

\rput(-6,2.7){\textrm{{\blue \small $3$}}}
\rput(-5,2.7){\textrm{{\blue \small $2$}}}
\rput(-4,2.7){\textrm{{\blue \small $8$}}}
\rput(-4,1.7){\textrm{{\blue \small $6$}}}

\psdots(4,0)(4,1)(4.5,2)(5,1)(5,0)
\psline(4,0)(4,1)(4.5,2)(5,1)(5,0)
 \psline(4.5,2)(4.5,3)

{\psset{linecolor=blue}
\psdots(2,2)(3,2)(3,1)
\psdots(-6,3)(-5,3)(-4,3)(-4,2) }

\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](2.1,2)(2.9,2)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](3.1,2)(4.4,2)

\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](3.1,1)(3.9,1)

\rput(2,1.7){\textrm{{\blue \small $3$}}}
\rput(3,1.7){\textrm{{\blue \small $2$}}}
\rput(3,0.7){\textrm{{\blue \small $6$}}}

\rput(0.0,1){\textrm{$\rightarrow$}}

\rput(4,-.3){\textrm{{\small $4$}}}
\rput(4.25,.9){\textrm{{\small $7$}}}
\rput(5.25,.9){\textrm{{\small $9$}}}
\rput(5,-.3){\textrm{{\small $5$}}}
\rput(4.5,3.3){\textrm{{\small $1$}}}
\rput(4.8,2.1){\textrm{{\small $8$}}}

\rput(-4.5,-0.2){\textrm{{\small $9$ is not a lone child,}}}
\rput(-4.5,-0.7){\textrm{{\small and so $m=8$}}}

\end{pspicture}
\end{center}
\centerline{Figure 2a}

\vspace*{2mm}

In the second case, insert $m$ into the tree as the lone child of $c$,
redirecting into $m$ all the original child edges of $c$ (Figure 2b).

\begin{center}
\begin{pspicture}(-8,-1.9)(8,3.3)

{\psset{linewidth=1.5pt}
\psdots(-1.5,3)
\psdots(4.5,3)}

\psdots(-1.5,3)(-1.5,2)(-2,1)(-1,1)(-1,0)

\psline(-1.5,3)(-1.5,2)(-2,1)
\psline(-1.5,2)(-1,1)(-1,0)

\rput(-6,2.3){\textrm{{\blue \small $6$}}}
\rput(-5,2.3){\textrm{{\blue \small $9$}}}
\rput(-4,2.3){\textrm{{\blue \small $3$}}}
\rput(-3,2.3){\textrm{{\blue \small $4$}}}
\rput(-3,1.3){\textrm{{\blue \small $8$}}}

\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-5.9,2)(-5.1,2)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-4.9,2)(-4.1,2)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-3.9,2)(-3.1,2)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-2.9,2)(-1.6,2)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](-2.9,1)(-2.1,1)

\rput(-1.5,3.3){\textrm{{\small $1$}}}
\rput(-1.2,2){\textrm{{\small $7$}}}
\rput(-2,0.7){\textrm{{\small $2$}}}
\rput(-0.7,1){\textrm{{\small $10$}}}
\rput(-1,-.3){\textrm{{\small $5$}}}

\psdots(4.5,2)(4.5,1)(4,0)(5,0)(5,-1)

{\psset{linecolor=blue}
\psdots(2,2)(3,0)(3,1)(3,2)
\psdots(-6,2)(-5,2)(-4,2)(-3,2)(-3,1)}

\psline(4.5,3)(4.5,2)(4.5,1)(5,0)(5,-1)
\psline(4.5,1)(4,0)

\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](2.1,2)(2.9,2)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](3.1,2)(4.4,2)

\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](3.1,0)(3.9,0)
\psline[linecolor=blue,arrows=->,arrowsize=3pt 3.5](3.1,1)(4.4,1)

\rput(4.5,3.3){\textrm{{\small $1$}}}
\rput(4.8,2){\textrm{{\small $7$}}}
\rput(4.8,1.1){\textrm{{\small $9$}}}
\rput(4.2,-.1){\textrm{{\small $2$}}}
\rput(5.3,-0.1){\textrm{{\small $10$}}}
\rput(5,-1.3){\textrm{{\small $5$}}}

\rput(2,2.3){\textrm{{\blue\small $3$}}}
\rput(3,2.3){\textrm{{\blue\small $4$}}}
\rput(2.8,1){\textrm{{\blue\small $6$}}}
\rput(2.8,0){\textrm{{\blue\small $8$}}}

\rput(0.8,1){\textrm{$\rightarrow$}}

\rput(-3,-1.2){\textrm{{\small lone-child vertices: 5,\, 7,}}}

\rput(-3,-1.7){\textrm{{\small and so $m=9$ and $c=7$}}}

\end{pspicture}
\end{center}
\centerline{Figure 2b}

\vspace*{2mm}

After the conversion, $m$ has become a lone-child vertex in the tree and is still the max among the arc and lone-child vertices. The  conversion map is clearly reversible, and so defines an involution that changes the sign of the weight. Thus all weights cancel out except those  of the trees we wish to count, all of whose weights are 1, and the total weight, (\ref{eq1}), is the number of our trees.


TITLE: Find $f^{(k)}(0)$ of $f(x)=\frac{\sin x}{x}$ for $x\neq 0$ and $f(0)=1$.
QUESTION [0 upvotes]: I'm stuck with this problem:

If $f(x)=\frac{\sin x}{x}$ for $x\neq 0$ and $f(0)=1$, find $f^{(k)}(0)$. Hint: Find the power series of f.

I tried to solve it by writing down the Taylor series of $$\sin x = \sum_{n=0}^\infty \frac{(-1)^n x^{2n+1}}{(2n+1)!}=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\frac{x^9}{9!}-...$$
After that I divided the whole series by $x$: $$\frac{\sin x}{x}=\sum_{n=0}^\infty \frac{(-1)^n x^{2n}}{(2n+1)!}=f(x)$$. The problem is that when I plug in $0$ in $f(x)$, I get $f(0)=$undefined. Also, When I differentiate and plug in $0$ I always get $0$, what am I doing wrong? How can I solve this? Thanks.

REPLY [1 votes]: Hint: If you know that $$f(x) = \sum\limits_{k=0}^{\infty}a_{k}x^{k},$$ then $$a_{k} = \dfrac{f^{(k)}(0)}{k!}.$$
(Try and show this!)
Also remember that if you are plugging in $x = 0$ to a term of a power series where the power of $x$ is $0$, the term should be $1$, not $0$ (i.e. substituting $x = 0$ into something like $x^{k}$ when $k = 0$ should be treated as $1$, not $0$).
For example, if $g(x) = \sum\limits_{k=0}^{\infty}\frac{1}{k!}x^{k}$, then if you substitute $x = 0$, what do you get?


TITLE: Projective dimension of a sub-ideal
QUESTION [2 upvotes]: Let $\mathbf{k}$ be a field, and let $S=\mathbf{k}[x_1,x_2,\ldots,x_n]$. Let $I\subset J$ be finitely generated monomial ideals in $S$. Is it true that the projective dimension of $I$ is either smaller than or equal to the projective dimension of $J$?

REPLY [2 votes]: Interestingly, the equality you seek holds in one important special case. If $I$ is any monomial ideal and $J$ is the radical of $I$, then $pd_S(I)\leq pd_S(J)$. See the proof of Theorem 2.6 in this paper by Herzog-Takayama-Terai.


TITLE: The Geometry of Recurrent Families of Polynomials
QUESTION [3 upvotes]: The Chebyshev T-polynomials have at least two natural definitions, either via the characterizing property $\cos(n\theta) = T_n(\cos(\theta))$, which I will call the geometric definition, or via a recurrence relation $T_{n+1} = 2x\ T_n - T_{n-1}$. My question concerns the relationship between these two definitions, and specifically asks if other families of polynomials defined by similar recurrence relations have a natural geometric interpretation, similarly to how $T_n$ expresses the relation between x-coordinates of particular points on the circle.
Starting from the geometric definition of $T_n$, it is straightforward to derive the recurrent definition. Is there a natural way of going the other direction? One thought I have had is as follows. If we treat the $T_n$ as elements of the coordinate ring of the circle, then $T_n$ expresses the relationship between the two parameterizations of the x-coordinates given by $\theta \mapsto \cos(\theta)$ and $\theta \mapsto \cos(n\theta)$. Can we do the same sort of thing with other families of polynomials defined by similar recurrence relations (say, for simplicity, second-order linear polynomial recurrences with coefficients of degree $\leq 1$)?
One potential obstacle I have encountered is that $\cosh(n\theta) = T_n(\cosh(\theta))$ as well, so that the hyperbola $X^2 - Y^2 = 1$ is just as natural a choice as the circle for a geometric object associated to $T_n$.
Here's my main question: given a particular family of polynomials $P_n$ related by a polynomial recurrence of an appropriately "nice" type, can one associate one or more algebraic curves (or other geometric objects) so that $P_n$ expresses some relationship between various points on the curve?

REPLY [5 votes]: You have to realize that you are asking a really vague question. Specifically, you haven't defined "similar (nice) recurrence relation" and "some relationship between various points on the curve".
When you say similar recurrence relation, I believe the next step to generalizing Chebyshev polynomials is to consider orthogonal polynomials, which satisfy a recurrence relation, but at the same time they come from certain differential equations which sometimes allow us to express them using Rodrigues' formula. For Chebyshev polynomials, this connects their recurrence relation
$$T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)$$
to the formula
$$T_n(x)=\frac{\Gamma(1/2)\sqrt{1-x^2}}{(-2)^n \Gamma(n+1/2)}\frac{d^n}{dx^n}\left([1-x^2]^{n-1/2}\right).$$
Similar formulas apply to most families of orthogonal polynomials, however the formula $$T_n(x)=cos(n \arccos(x))$$ is a bit special and characteristic of Chebyshev polynomials. In fact if you had a family of polynomials $\{P_k\}_{k\geq 1}$ so that you could express them as $$P_n(x)=f(nf^{-1}(x))$$ for some function $f$, then they would trivially satisfy $P_n(P_m(x))=P_m(P_n(x))=P_{mn}(x)$ and by a result of Block and Thielman, these polynomials must coincide with a linear transformation of either the power sequence $\{x^k\}$ or the Chebyshev polynomials $\{T_k\}$.

Another perspective which sheds a little more light on the geometric properties of Chebyshev polynomials is Dessin d'enfant. The Belyi functions corresponding to trees are the Shabat polynomials which are generalizations of Chebyshev polynomials. I believe this is the right context to observe the symmetries of functional composition of Chebyshev functions. See these articles.