TITLE: For any odd integer $n > 2$, show that there isn't any positive integer $x$, such that $x^n + (x+1)^n = (x+2)^n$.
QUESTION [0 upvotes]: For any odd integer $n > 2$, show that there isn't any positive integer $x$, such that:
$$x^n + (x+1)^n = (x+2)^n$$
Writing it using Newton's binom, we obtain:
$$x^n = \sum_{i=1}^{n} \binom{n}{i} \cdot x^{n-i} \cdot (2^i - 1)$$
I don't know how to continue the problem. Can you help me, please? Thanks!

REPLY [1 votes]: Claim 1: If $x$ is even then the left side is odd but right side is even so no even solution.
Claim 2: If $x$ is odd, then $x \equiv \pm 1 \pmod{4}$. In which case (with $n$ being odd) we have left side is either $1+2^n \pmod{4}$ or $-1 \pmod{4}$, whereas the right side is $-1 \pmod{4}$ or $1 \pmod{4}$ respectively. For $n>2$ the two sides are not equal. Hence no solution.

REPLY [0 votes]: The reminders by $x$ is equal, then
$2^n=kx+1$
$LHD=x^n+(x+1)^n=x*(A(x)+n)+1$
$RHD=(x+2)^n=x(B(x)+2n)+kx+1=x(B(x)+2n+k)+1$
Since $n≠2n+k$, there doesn't such integers.


TITLE: How to get the properties of an ellipse with six points given.
QUESTION [2 upvotes]: I am looking for a way to calculate the lengths of both semi-axes and the rotation angle of the ellipse in the image as shown in this picture. Six points are given, with two pairs of points being equidistant from the center and exactly in opposition. The other two points have the same x-position and their distance A1-A2 is also known. The diameters of the ellipse that end at the given points are conjugate as you can see in this question. Thank you for your help.

REPLY [0 votes]: Thank you. I found a much easier way to get the properties of the ellipse using the Rytz's construction method.


TITLE: Is $\mathbb{R}$ an open ball in $\mathbb{R}$?
QUESTION [3 upvotes]: If we write $B(0,\infty)$ as the open ball then $\mathbb{R}$ is an open ball in $\mathbb{R}$. Is it correct?

REPLY [3 votes]: No, balls have finite radius. It is an open set however.


TITLE: $\lim_{n\rightarrow \infty }\frac{1}{n}\int_{Y<n} Y \, dP=0$?
QUESTION [3 upvotes]: $Y$ is a non-negative random variable, not necessary integrable. How to show
$$\lim_{n\rightarrow \infty }\frac{1}{n}\int_{Y<n}Y \, dP=0$$
My idea is to find a good upper bound that converges to zero. However, I didn't find a good one. My upper bound is
$$\frac{1}{n}\int_{Y<n}Y \, dP\leq \frac{1}{n}\int_{Y<n}n \, dP\leq \int_{Y<n}dP\leqslant 1.$$

REPLY [3 votes]: Here is a direct proof (which doesn't require any additional theorems such as the dominated convergence theorem):
Fix $\epsilon>0$. Since $A_n := \{n \leq Y < \infty\}$ is a sequence of decreasing sets satisfying $\bigcap_{n \in \mathbb{N}} A_n = \emptyset$, the continuity of the (probability) measure $\mathbb{P}$ gives
$$\lim_{n \to \infty} \mathbb{P}(n \leq Y < \infty) = 0;$$
in particular we can choose $N \in \mathbb{N}$ such that $\mathbb{P}(N \leq Y < \infty) \leq \epsilon$. Now
$$\begin{align*} \frac{1}{n} \int_{Y<n} Y \, d\mathbb{P} &= \frac{1}{n} \int_{Y<N} Y \, d\mathbb{P} + \int_{N \leq Y < n} \frac{Y}{n} \, d\mathbb{P} \\ &\leq \frac{N}{n} \underbrace{\mathbb{P}(Y < N)}_{\leq 1} + \mathbb{P}(N \leq Y < n) \\ &\leq \frac{N}{n} + \mathbb{P}(N \leq Y < \infty) \leq \frac{N}{n} + \epsilon. \end{align*}$$
Choosing $n$ sufficiently large, we get
$$\frac{1}{n} \int_{Y<n} Y \, d\mathbb{P} \leq 2 \epsilon.$$


TITLE: What is the probability distribution for the detection times of radioactive emissions from a radioactive sample?
QUESTION [2 upvotes]: Assume I have a radioactive sample composed of $N$ atoms of some type A. I know that if I measure at time t the number of atoms not already decayed, this number will be given by
$$
N(t) = N_0 \exp\left({-t/T}\right)
$$
where $T$ is the mean decay time and $N_0$ is the initial number of atoms A in the sample. However, say that I have a detector that allows me to detect every radioactive emission from the sample and also to measure the exact time at which this emission happens. I will continue this experiment until I have enough data to plot an histogram. On the $y$ axis I put the number of emission detected and on the $x$ axis the time in which the emission has been detected. What is the shape that I expect for this histogram?
I thought I will find a uniform distribution since the exact time in which each atom of the sample decay is completely random.
Another question is: what distribution I will find if I plot the temporal distances between detection times?
For example at $t_1$ I have measured an emission and at $t_2$ another one. The temporal distance is $t_2-t_1$. I iterate this process for each $t_i$ of the measurement for $i$ that goes from 1 to $n$, where $n$ is the number of emissions detected. Once I have the resulting temporal distances I plot the histogram.
Thanks.

REPLY [3 votes]: Poissonian vs. pure death process
Contrary to the immediate intuition (reflected in the comments and the earlier version of my own answer) we are not dealing here with a Poisson process, but with a pure death process (called so as a particular case of more general birth and death process). Both are Markovian processes, where the probability of the next event depends only on the parameters of the previous event. However, in a Poisson processes this probability does not depend on the total number of the previous events, whereas in the pure death process it is.
The probability of having $n$ non-decayed atoms is described by the following equations:
$$
\dot{p}_n(t) = -\lambda np_n(t) + \lambda (n+1)p_{n+1}(t), n>0,\\
\dot{p}_0(t) = \lambda p_1(t)
$$
The first term describes the reduction of the probability of having $n$ atoms due to the decay of one atom among $n$, the second term describes the increase of this probability via the decay of one atom among $n+1$. The difference with the Poisson process is the presence of factors $n$ and $n+1$ in the rates, reflecting the fact that the probability of an atom decaying is proportional to the number of atoms.
The equations above can be easily converted to the equation for the average number of atoms,
$$
N(t) = \sum_0^{N_0}p_n(t)
$$
with solution
$$
N(t)=N_0e^{-t/T}.
$$
Survival probability and transition probability
Thus, the survival probability, i.e., the probability that after a decay event at time $t'$ we do not observe another decay event till time $t$ is
$$
S(t|n,t')=e^{-\lambda n(t-t')},
$$
whereas the probability density of another decay at time $t$ is
$$
f(n-1, t|n, t') = -\frac{d}{dt}S(t|n,t') = \lambda n e^{-\lambda n(t-t')}
$$
Joint probability density of multiple events
The joint probability density of events occurring at times $t_M>t_{M-1}>...>t_2>t_1$, laying in the interval $[t_0, t]$, conditioned on having  $N_0$ atoms at $t_0$, is then given by
$$
f(t, t_M, t_{M-1}, ..., t_2, t_1|N_0)=\\S(t|t_M, N_0-M)f(N_0-M, t_M|N_0-M+1, t_{M-1})...f(N_0-2, t_2|N_0-1, t_1)f(N_0-1, t_1|N_0, t_0)=\\
S(t|t_M, N_0-M)\prod_{m=1}^Mf(N_0-m, t_m|N_0-m+1, t_{m-1})
$$
References
As a general (although a bit advanced) mathematical text on point processes and survival analysis I suggest
Aalen et al., Survival and event history analysis
Update
I add for completeness the solution for $p_n(t)$:
$$
P(n, t|N_0) = \begin{cases}
{N_0\choose n}e^{-n\lambda t}\left(1-e^{-\lambda t}\right)^{N_0-n}, \text{ for } n\leq N_0,\\
0, \text{ otherwise}.
\end{cases}
$$


TITLE: Sum of all distinct numbers made
QUESTION [0 upvotes]: Question:
Find the sum of all distinct four digit numbers that can be formed using
the digits 1; 2; 3; 4; and 5, each digit appearing at most once.
I have no clue as to where to begin this question. I know how to find the sum of the units place. However, how will I find this sum?

REPLY [1 votes]: Firstly, there are 120 possible permutations of numbers.
$(5*4*3*2)$
For any number generated, we can match up a pair which corresponds 1 to 5, 2 to 4, ...
e.g. (2354, 4312), (1234, 5432)
If we add up the pairs, we always get 6666 and using symmetry, the answer is $6666*(120/2)=6666*60$

REPLY [1 votes]: See get a number and you'll always see a number which will add with the first number to give $66666$ now total pairs are $60$ as total numbers are $120$ as exactly $2$ numbers give $66666$ so answer is $66666\cdot 60=3999960$


TITLE: The uniform convergence of a power series on a connected open set
QUESTION [1 upvotes]: The problem is to prove that
$$ \sum_{n=0}^\infty a_n(z-z_0)^n $$ uniformly converges on a connected open set $D$ if and only if it uniformly converges on $\overline{D}$.
The sufficiency is trivial.Since it uniformly converges on $\overline{D}$, it must uniformly converges on $D$. But the necessity seems hard to prove.
Please show me how to prove the problem.

REPLY [1 votes]: Given $\varepsilon>0$, there is some $N$ so that any two partial sums with at least $N$ terms differ by at most $\varepsilon$ on $D$. Note that partial sums are polynomials, and so continuous on all of $\mathbb{C}$. I'll let you take it from there.


TITLE: Let X be a Poisson random variable, show that $E[X^n] = \lambda E[(X+1)^{n-1}]$
QUESTION [2 upvotes]: I am struggling to understand some of the steps of the proof of this problem:

Let X be a Poisson random variable, show that $E[X^n] = \lambda
 E[(X+1)^{n-1}]$.

The proof:
$$
\begin{align*}
E(X^n) &\stackrel{(1)}=
e^{-\lambda} \sum_{j=0}^\infty j^n \frac{\lambda^j}{j!} \\ &\stackrel{(2)}=
e^{-\lambda} \sum_{j=0}^\infty j^n \frac{\lambda^j}{j!} \\ &\stackrel{(3)}=
e^{-\lambda} \sum_{j=1}^\infty j^{n-1} \frac{\lambda^j}{(j-1)!} \\ &\stackrel{(4)}=
\lambda e^{-\lambda} \sum_{j=1}^\infty j^{n-1} \frac{\lambda^{j-1}}{(j-1)!} \\ &\stackrel{(5)}=
\lambda e^{-\lambda} \left( \sum_{i=0}^\infty (i+1)^{n-1} \frac{\lambda^i}{i!} \right) \\ &\stackrel{(6)}=
\lambda E((X+1)^{n-1}).
\end{align*}
$$
Assuming the lines are numbered 1-6, I will try to explain and show where I'm stuck (the bolded parts):

This is just by definition, but I don't understand why it is necessarily going from 0 to infinity, and why does it look for $P(X=i), 0\leq i\leq \infty $ (hope my questions was clear)

Since for $j=0$ it doesn't contribute to the sum, I can omit it and count from 1

This line is not clear to me, why can I reduce the power and the denominator? doesn't make much sense to me

Nothing special here

We change the lower bound again to count from 0, why again I can simply add 1 to the power and denominator?

Why is this conclusion correct?

Thanks in advance!

REPLY [2 votes]: This is like for any set of numbers the sum of the numbers is taken when finding their mean. This comes from the definition of expected value.
Sure.
You're simply cancelling the $j$ from $j^n$ with the $j$ from $\frac{1}{j!}$. That is, $j^n = j^{n-1}j$ and $j! = j(j-1)!$.
Okay.
This is a basic change of index. The basic form for this is $\sum_{k=2}^{\infty}k = \sum_{j=1}^{\infty}(j+1)$.
We substitute line 5 into the original form to get this result.


TITLE: Can the vertex angle of an isosceles triangle be found without the law of cosines (no calculator)?
QUESTION [0 upvotes]: If we know three sides of an isosceles triangle, can we find the measure of the angles without using a calculator (that means no law of Cosines/Sines).

REPLY [0 votes]: Yes.  We can use the law of sines.
That is, choose two sides of unequal lengths $a$ and $b$.  Let $\alpha$ and $\beta$ denote the measures of their respective opposite angles$.  Then we have:
$$\frac{\sin(\alpha)}{a} = \frac{\sin(\beta)}{b}$$
If $a < b$, then $2\alpha + \beta = 180^\circ$ since the triangle is isosceles.  From here, we have $\beta = 180^\circ - 2\alpha$.  Plug this into the above, and we have an equation with a single unknown.


TITLE: extract x: $((x+y)^n - x^n)^{1/n}$ expressed in the form $ba^{c}$ where all that matters is b contains x
QUESTION [2 upvotes]: I've done a bit of calculus/diff.eq./lin.alg. in the past. But that was a long time ago and to be honest I was always better at the actual applying than the pure math.
Anyway, I have a function which I am trying to get into a certain form. I want to do this by isolating/extracting one variable.
I've been trying on paper, Mathematica, Wolfram|Alpha and it's just not making sense to me anymore.
Here's the function:
$$((x+y)^n - x^n)^{1/n}$$
And I'm trying to extract the x out of this so I get something of the form:
$$xa^\text{exponent}$$
Whatever the exponent is or 'a' is or if x has any +something/-something/divided by/exponents, or even if 'a' still contains x's I want x times something to an exponent.
What I have come up with myself so far is driving me mad: I get two forms for 'a' depending on if I do
$$(xa)^{1/n}$$
or
$$x(a^{1/n})$$
As I said, I am really rusty and tried a lot of things which I think are oh-so wrong, but this is what I got trying to extracate x:
$$x^n ((1+((1/x)y)^n -1)^{1/n}$$
OR
$$x^n ((((1/x) + ((1/(x^n))y))^n)-1)^{1/n}$$
I'm not too proud to say I even got:
$$x((1+(1/x)y)^n - x(1/n))^{1/n}$$
I'm doing this all for a hobby programming project of mine (lead android programmer) and I just can't get it to  work out ... plus I would like to be sure the answer is correct!
If it helps, $x$,$y$ and $n$ are all positive integers. $y<x$ and $y\geq 1$, $x\geq3$ and $n\geq2$.

REPLY [1 votes]: Consideration of the issue function
$$f(x,y,n) = x\left(\left(1+\dfrac yx\right)^n-1\right)^{\frac1n}\tag1$$
in the form of
$$f(x,y,n) = x a^{\text{exponent}}$$
is equivalent to looking for the presentation
$$\left(1+\dfrac{y}x\right)^n-1 = a^b.\tag2$$
Exact approach is $b=1$ and the form $(1),$ wherein $(2)$ allows factorization
$$\left(1+\dfrac{y}x\right)^{2k+1}-1 = \left(\dfrac{y}x+1-1\right) {\left(\left(\dfrac{y}x+1\right)^2-2\left(\dfrac{y}x+1\right)\cos\dfrac{2\pi}{2k+1}+1\right)}\times
{\left(\left(\dfrac{y}x+1\right)^2-2\left(\dfrac{y}x+1\right)\cos\dfrac{4\pi}{2k+1}+1\right)}\dots
\times\left(\left(\dfrac{y}x+1\right)^2-2\left(\dfrac{y}x+1\right)\cos\dfrac{2k\pi}{2k+1}+1\right),$$
or
$$\left(1+\dfrac{y}x\right)^{2k+1}-1 = \dfrac{y}x {\left(\left(\dfrac{y}x\right)^2+4\left(\dfrac{y}x+1\right)\sin^2\dfrac{\pi}{2k+1}\right)}\times
{\left(\left(\dfrac{y}x\right)^2+4\left(\dfrac{y}x+1\right)\sin^2\dfrac{2\pi}{2k+1}\right)}\dots
\left(\left(\dfrac{y}x\right)^2+4\left(\dfrac{y}x+1\right)\sin^2\dfrac{k\pi}{2k+1}\right),\tag3$$
in the case of odd $n=2k+1,$
and
$$\left(1+\dfrac{y}x\right)^{2k}-1 = \left(\left(\dfrac{y}x+1\right)^k-1\right)\left(\left(\dfrac{y}x+1\right)^k+1\right)\tag4$$
in the case of even $n=2k.$
And there are approximations
$$\left(1+\dfrac{y}x\right)^n\approx e^{(ny)/x},\quad f(x,y,n)\approx x\left( e^{\frac {ny}x}-1\right)^{\frac1n},\quad \text{ if }\ \dfrac {ny}x \approx 1,\ n >> 1,\tag{5}$$
$$\left(1+\dfrac{y}x\right)^n-1 \approx \dfrac {ny}x,\quad f(x,y,n)\approx x\left(\dfrac{ny}x\right)^{\frac1n},\quad \text{ if }\ \dfrac {ny}x << 1.\tag{6}$$
On the other hand, the polynomial $(2)$ reduces to the degree $(n-1),$ so the consideration in the form of
$$f(x,y,n) = x^{\frac{n-1}n} a^{\frac1n}\tag7$$
can be useful too. In this case
$$a = x\left(\left(1+\dfrac{y}x\right)^n-1\right),\tag8$$
$$a = y\left(n +\binom{n}{2}\dfrac yx +\dots + \binom{n}{n-2}\left(\dfrac yx\right)^{n-3} + n\left(\dfrac yx\right)^{n-2} + \left(\dfrac yx\right)^{n-1}\right).\tag9$$


TITLE: Proof that $f'(X_{0}) = 0$ under those conditions
QUESTION [0 upvotes]: Let $F$ be a differentiable  function   $$ F:\mathbb{R} \to \mathbb{R}$$
and $$ \lim_{x \to -\infty} F(x) = \lim_{x \to \infty} F(x) = a \in \mathbb{R}$$
Prove that there exists a ${x_0} \in \mathbb{R} $ such that  $f'({x_0}) = 0$
$\textbf{My Try} $
let $ R \in \mathbb{R}$ and  $R >0$
$ \lim_{x \to -\infty} F(x)= a $ $\Rightarrow$    it exists an ${x_1}$ so that for all $x <-R$  ,$ x<{x_1}$ and $f({x_1})= a + \epsilon$
$ \lim_{x \to \infty} F(x)= a $ $\Rightarrow$    it exists an ${x_2}$ so that for all $x >R$  ,$ x>{x_2}$ and $f({x_2})= a + \epsilon$
because  ${x_1} <{x_2}$ $\Rightarrow$ it exist an ${x_0} \in ({x_1},{x_2})$ so that $F'(x_0) = \frac{F({x_2})-F({x_1})}{{x_2}-{x_1}}=\frac{a + \epsilon-(a + \epsilon)}{{x_2}-{x_1}}=0 \Rightarrow  F'x_{0})=0$
Is that correct?

REPLY [0 votes]: Your argument is not rigorous enough since such $x_1$ may not exists for an arbitrary $\epsilon$.
You may consider the following hint:
WLOG, we assume $F$ is not a constant function, otherwise it is trivial.
Then you can show $F$ obtains either the global maximum (if there exists $y\in \mathbb{R}$ such that $F(y)>a$) or global minimum (if there exists $y\in \mathbb{R}$ such that $F(y)<a$).
Since $F$ is defined on $\mathbb{R}$ (there is no end-point of the domain) and $F$ is differentiable, the global extremum must be a local extremum and at that point, $F'(x_0)=0$.
Please let me know if there is anything unclear.


TITLE: Homotopy groups of quotient groups.
QUESTION [4 upvotes]: I'd like to ask how to compute homotopy groups of quotient groups, whose homotopy groups I already know. I found this answer, but I don't understand how to derive the homotopy group of $\pi_n (G/H)$ using the long exact sequence.

In general, if I know $\pi_n(G)$ and $\pi_n(H)$, can I compute $\pi_n(G/H)$?

What if $\pi_n(G)$ is trivial?
Or $\pi_n(H)= \mathbb{Z}_N$?
What about a combination of the two?
Any special cases that are easy?
What about $n=1$?

I know these are many questions so to clarify, in principal I'd like the most general answer but if one is not known, then any examples where a computation can be done is acceptable.

REPLY [2 votes]: For the cases you're interested in $H$ is discrete which simplifies the situation a lot. In this case most of the long exact sequence in homotopy vanishes and we get that $G$ and $G/H$ have the same $\pi_n, n \ge 2$, so the only thing left to do is analyze $\pi_1$. Here the long exact sequence ends
$$1 \to \pi_1(G) \to \pi_1(G/H) \to H \to 1$$
so we get that $\pi_1(G/H)$ is an extension of $H$ by $\pi_1(G)$. Furthermore in all the examples you've named $\pi_1(G)$ vanishes so we just get that $\pi_1(G/H)$ is $H$.


TITLE: Proving $f(z)$ is continuous on whole complex plane
QUESTION [0 upvotes]: Question: define a function,
$$f(z)=\begin{cases}\frac{z \text{ Re(z)}}{|z|}&\text{ if $z≠0$}\\0, &\text{ if $z=0$}\end{cases}$$
Then prove or disprove $f(z)$ is continuous in entire complex plane.
We can see by definition of $f$ it is not constant function, so we can't use Liouville's theorem to prove $f$ is constant :-(
So I think we have to go by definition. I know, the function $f(z)$ is said to be continuous at $z=z_0$ if for given ε>0 we can find δ>0 such that,
$|f(z)-f(z_0)|<ε$ whenever $|z-z_0|<δ$
Now here to prove the continuity of $f(z)$ on whole complex plane, we just need to check continuity of $f(z)$ at $z=0$ only(?is am I correct)
Now,
$|f(z)-f(0)|=|\frac{z\text{ Re(z)}}{|z|}|$
$≤\frac{|z\text{ Re(z)}|}{|z|}$
$≤|Re(z)|$
But I end up with no conclusion? :-( is $f$ is continuous? I tried it, but didn't able to go further, Please help me...

REPLY [2 votes]: No, it is not enough to prove that it is continuous at $0$. But outside $0$ it is continuous, becaue you can obtain $f$ from continuous functions using multiplication and division.
At $0$ it is continuous, because it follows from what you did that$$|z|<\varepsilon\implies\bigl|f(z)\bigr|<\varepsilon,$$since$\bigl|f(z)\bigr|\leqslant|z|$.


text:
\section{Results}
\newcommand{\CFP}{{C_{\mathsf{FP}}}}
\newcommand{\CL}{{C_{\mathsf{L}}}}

In this section, we present our results on disjunct matrices, list-disjunct matrices, group testing, and heavy hitters, based on the definitions given in the preliminaries. In what follows, $C, \CL,\CFP> 1 $ are absolute constants. All our results assume, without loss of generality that $k \leq \gamma n$ for some absolute constant $\gamma$, otherwise storing the identity matrix is asymptotically the best solution. Our starting point and one of our strongest tools is the following theorem.

\begin{theorem}\label{thm:main_tool}
There exists a Monte-Carlo construction of a $(k, \CL k\log(n/k)  )$-list-disjunct matrix $M \in \{0,1\}^{m\times n}$ with $m = C \cdot k\log(n/k)$, allowing decoding in time $O(k \log (n/k))$. $M$ is the vertical concatenation of $\log(n/k)$ matrices $M^{(\log k)},\ldots, M^{(\log n)}$ such that (i) each such submatrix has $C k$ rows and exactly $1$ non-zero per column, (ii) every such submatrix can tolerate up to $\CFP \cdot k$ false positives.

Furthermore, $M$ can be stored in $O(k \log (n/k))$ space, and for every $\ell$ and every choice of $B = O(k\log(n/k))$ columns $i_1,i_2,\ldots,i_B \subseteq [n]$, we can find the rows $q_{i_1}, \ldots, q_{i_B} \subseteq [Ck]$ where the aforementioned columns have the non-zero element in $M^{(\ell)}$ in time
\[	O\left( k \log^2 \left(\frac{n}{k}\right) \cdot \log^2( k \log\left(\frac{n}{k}\right)) \cdot \log \log\left( k \log \left(\frac{n}{k}\right)\right) \right).\]
\end{theorem}

The last sentence of the above theorem, namely the claim about storing the matrix $M$ in small space and the fast batch location, is particularly important for our application to the heavy hitters problem. For the group testing applications, this property will be irrelevant. The matrix $M$ will be also called the \emph{identification} matrix.

\subsection{Disjunct and List-Disjunct Matrices}

\begin{theorem}[List-Disjunct Matrices]\label{thm:list_disjunct}
There exists a Monte-Carlo construction of a $(k,k)$-list-disjunct matrix $M \in \{0,1\}^{m \times n}$ with $m = O(k \log (n/k))$, that allows decoding in $O(k \log^2(n/k))$ time\footnote{For ease of exposition, we chose to give a construction of list-disjunct matrices with $\ell = k$.}.
\end{theorem}

In comparison, the best previous construction of efficiently decodable list-disjunct matrices requires either $k^2 \poly(\log n)$ decoding time and $O(k \log n \cdot \log \log_k n)$ rows \cite{icalp11}, or $O(k\log^2(n/k))$ rows and decoding time (\cite{icalp11} gives another construction using Parvaresh-Vardy codes with much less clean time and measurement bounds and polynomial in $k$ decoding time).

\begin{theorem}[Disjunct Matrices]\label{thm:disjunct}
There exists a Monte-Carlo construction of a $k$-disjunct matrix $M \in \{0,1\}^{m \times n}$ with $m = O(k^2 \mathrm{min}\{ \log n, (\log_k n)^2 \} )$, that allows decoding in $O(m + k \log^2 (n/k))$ time.
\end{theorem}

The best previous constructions of efficiently decodable disjunct matrices are: i) The results from \cite{indyk2010efficiently}, which achieves $m=O(k^2 \log n)$ rows and $\Omega(k^4 \log n)$ decoding time, ii) The result from \cite{icalp11} which achieves $O(k^2\log n + k \log n \cdot \log \log_k n)$ rows and $m\log^2 n$ decoding time. We strictly improve upon the measurement and the decoding time complexity of previous work, obtaining the cleanest bounds.

\begin{theorem}[Explicit Disjunct Matrices]\label{thm:deterministic_disjunct}
We can construct in polynomial time in $n$ a $k$-disjunct matrix with $m= O(k^2 \log n)$ rows that allows decoding in time $m\cdot \poly(\log n)$, unless
\[k \in \left[ \frac{C\log n}{\log \log n}, \left(\frac{C\log n}{ \log \log n}\right)^{1+o(1)}\right],\] where the $o(1)$ term is $\Theta\left(\frac{(\log \log \log n)^2}{\log \log n}\right)$.
\end{theorem}

Of course, the small intermediate range of $k$ where the above result does not apply
can be eliminated by slightly rounding $k$ up to $k^{1+o(1)}$, resulting in $m=k^{2+o(1)} \log n$ rows and $m \cdot \poly(\log n)$ decoding time for all $k$.

\subsection{Heavy Hitters in the Strict Turnstile Model}

\begin{theorem} (``For-all'' Heavy Hitters) \label{thm:heavy_hitters}
There exists a streaming algorithm with space usage $O(k \log (n/k))$, which keeps a (non-linear) representation of a vector $x \in \mathbb{R}^n$, and upon query, if $x \in \mathbb{R}^n_+$ then \emph{always} returns a list $L$ of size $O(k)$ which contains every $(1/k)$-heavy hitter. The query time is $O(k \poly( \log n))$ and the update time is $\tilde{O}( \log (n/k) \cdot \log^2 k )$.

\end{theorem}

In contrast to the result appearing in \cite{lnw17} which achieved $\Omega(n \log n)$ query time and $O(k \log (n/k))$ update time, our algorithm achieves nearly optimal query and update time. The non-linearity of the sketch does not play a role in the number of measurements, but only to achieve the desired update time. It is shown in \cite[Theorems 4,5]{lnw17} that if we drop the assumption of the strict turnstile model or additionally demand accurate estimates (up to $(1/k) \|x\|_1$) of the coordinates in $L$, then there exists no such linear sketch unless it has $\Omega(k^2)$ rows.

The next result is a streaming algorithm for the more common version of the heavy hitters problem, where one wants to find every $(1/k)$-heavy hitter and no $i$ with $x_i \leq (1/(2k)) \|x\|_1$. This greatly improves upon the scheme appearing in \cite{NNW12} which has the same space usage but requires $\Omega( n k )$ query time\footnote{The results in \cite{NNW12} satisfy a stronger guarantee, referred to as the ``tail'' guarantee in the sparse recovery literature. It is not hard to see that our arguments can facilitate that guarantee as well, but for ease of exposition we chose to present only the more standard guarantee of the heavy hitters problem.}.

\begin{theorem} (``For-all'' Heavy Hitters with Estimates) \label{thm:heavy_hitters_estimates}

There exists a streaming algorithm using space usage
\[	O\left(k^2 \cdot \mathrm{min}\left\{ \log n , \left( \frac{\log n}{\log k + \log \log n}\right)^2 \right\} \right),	\]

 which keeps a (non-linear) representation of a vector $x \in \mathbb{R}^n$, and upon query, if $x \in \mathbb{R}^n_+$ then \emph{always} returns a list $L$ containing every $(1/k)$-heavy hitter, and no $i\in [n]$ with $x_i \leq (1/(2k)) \|x\|_1$. Moreover, for every $i \in L$ it returns an estimate $x_i'$ with $ x_i \leq x_i' \leq x_i + (c/k)\|x\|_1$, where $c$ is an arbitrarily small absolute constant $c<1$.
The query time is $k^2 \poly( \log n)$ and the update time is $O(k \cdot \mathrm{min}\left\{ \log n ,\left( \frac{\log n}{\log k + \log \log n}\right)^2 \right\} ) + \tilde{O}(  \log ^3n  )$.

\end{theorem}

\begin{remark}
One could also ask whether the update time of $k$ on the above theorem is necessary, or more interestingly, one can decode $k$-disjunct matrices and perform queries for heavy hitters faster than quadratic time in $k$. After all, as will be revealed in Section~\ref{sec:obtain}, we need to point query only $O(k )$ coordinates, so it is not immediately evident that the quadratic time-bound in $k$ is necessary (we might need $\Omega(k^2)$ measurements, but an algorithm might not need to read all of them). However, it seems that performing point-queries is indeed a bottleneck, since i) an easy argument (which we leave to the reader) shows that any $k$-disjunct matrix must have at least $n-m$ columns of sparsity at least $k$, and ii) any $(1/k)$-incoherent matrix (from which known heavy hitters sketches follow) must have column sparsity $\Omega(k)$ as long as $m \leq n / \log k$ \cite[Theorem~10]{nelson2013sparsity}. This constitutes strong evidence that it is impossible to beat quadratic decoding/ query time and linear (in $k$) update time, unless using a near-linear in $n$ number of measurements.
\end{remark}

It is also worth noting that any subsequent improvement of sketches that enable $\ell_1$ point-queries immediately translates, via our framework, to a streaming algorithm with sublinear query time. Thus, we may consider the problem of sublinear-time query time essentially closed, up to logarithmic factors.

\subsection{Error-Correcting Disjunct Matrices}

We give the following two constructions of efficiently decodable matrices. The first is particularly efficient for false negatives, while the second for false positives. Both results are significantly faster than what was attainable by previous techniques using the same number of rows. We find it quite interesting that while we are able to construct fast error-correcting disjunct matrices with respect to either false positives or false negatives, we cannot construct fast error-correcting disjunct matrices that can facilitate both simultaneously, see an explanation in Section~\ref{sec:error}. It would be interesting to have a combination of these methods which could give the best of both worlds.

\begin{theorem}(False Positives)\label{thm:error_list}
There exist Monte-Carlo constructions of
\begin{enumerate}
\item A $(k,k,e_0,0)$-list-disjunct matrix with $m = O(k \log (n/k) + \log_k n \cdot e_0 )$ rows which allows decoding in time $O(k^{\alpha} \cdot m )$, for any constant $\alpha>0$.
\item A $k$-disjunct matrix with $m = O(k^2 \log n + \log_k n\cdot  e_0)$, which can tolerate up to $e_0$ false positives and allows decoding in time $O(m \cdot \log n))$.
\end{enumerate}
\end{theorem}

The first result of the preceding theorem improves by almost a $k$ factor what is attainable by the techniques in \cite{icalp11,bondorf2019sublinear} (see also the comment following); the techniques in \cite{cai2013grotesque,cai2017efficient,lee2019saffron} result in schemes with a strictly larger number of rows\footnote{In fact, those results can be immediately obtained by the standard construction augmented with the code in \cite{s96}, see also discussion in Section~\ref{sec:tech}.}. For both results in Theorem~\ref{thm:error_list}, the argument in \cite{icalp11} obtains near-linear decoding albeit with a slight loss of $\log \log_k n$; \cite{cai2013grotesque,cai2017efficient,lee2019saffron} can be modified to obtain near-linear decoding but with a $\log n$ factor overhead in the measurement complexity.

\begin{theorem}(False Negatives) \label{thm:error_dis}
There exists a Monte-Carlo construction of a $k$-error-correcting disjunct matrix achieving $m = O(k^2 \log n + k\cdot  e_1)$, which can tolerate up to $ke_1$ false negatives and allows decoding in time $O(m \cdot \poly(\log n))$.
\end{theorem}

This theorem improves upon what was known and achievable using previous techniques, both in terms of measurements and decoding time, and achieves the optimal dependence in terms of $e_1$, the number of false negatives.

\paragraph{Comment on the conversion in \cite{icalp11}.} The authors in \cite{icalp11}, using a black-box conversion (Section~3 and subsection~5.2), claim a construction of $(k,n,e_0,e_1)$-list-disjunct matrices with $m=O(k \log n \cdot \log \log_k n + \log \log_k n \cdot e_0 + k \log \log_k n \cdot e_1)$ rows and $m^2 \poly(\log m)$ decoding time; this can be derived by Corollary~12 in that paper by plugging in an optimal construction of error-correcting list-disjunct matrix (in the same spirit as Corollaries 13~and~14, but without the demand of explicitness). However, we note that Theorem~11 in that paper is incorrect (in that the disjunctness property with the given adversarial error bounds $e_0, e_1$ indeed hold combinatorially, but the given decoding algorithm cannot attain the reported error tolerance), and thus Corollaries 12,~13, and 14, as well as Corollary~22 and Theorem~24 are not fully correct with respect to all parameters. The reason is that in Theorem~11 the authors write down the recursive relation in terms of the universe size, but it should also incorporate the number of false positives and false negatives; i.e., $t(i,e_0,e_1)$ instead of $t(i)$. This translates to the existence of a $(k,n,e_0,e_1)$-list-disjunct matrix with $m=O( k \log n \cdot \log \log_k n + \log_k n \cdot e_0 + \log_k n \cdot e_1)$ rows instead; the $\log \log_k n$ factors in the false positives and false negatives in Corollaries 12,~13, and 14 (which are written down as $\log \log n$ factors) should be $\log_k n$ instead, and the $\log \log n$ factors in Corollary~22 and Theorem~24 should be $\log n$. To be more descriptive, the conversion in Theorem~12, Corollary~12 from \cite{icalp11} builds a binary recursion tree with $\log_k n$ nodes, and uses $O(k \log(n^{1/2^i}/k) + e_0 + ke_1)$ rows for every node in the $i$-th level of the tree; thus, the factor $k \log n$ is indeed multiplied by the number of levels; i.e., $\log \log_k n$, but the factor that multiplies $e_0+ke_1$ is the \emph{total~number~of~nodes}, which is $\log_k n$. Another way to see why the bound claimed in \cite{icalp11} is not achievable by that construction, observe that an adversary can put all their available false negatives and/or false positives in the list-disjunct matrix in one of the leaves of the recursion tree, totally sabotaging the decoding procedure.

\subsection{Resolving the ``For-Each'' Case of Group Testing}

\begin{theorem} \label{thm:group_testing_for_each}
There exists a randomized construction of a matrix $\{0,1\} \in \mathbb{R}^{m \times n}$ with $m = O(k \log n)$ such that the following holds. Given $y = M \odot x$ with $|\mathrm{supp}(x)| \leq k$, we can find $x$ in time $O(k \log n)$, with failure probability $e^{-\Omega(k)} +  \frac{1}{\poly(n)}$.
\end{theorem}

This theorem improves upon the recent work of \cite{bondorf2019sublinear}, which achieved the same number of rows but required quadratic running time in $k$. Our result essentially settles the non-uniform case of the group testing problem.

\subsection{$\ell_2/\ell_2$ Compressed Sensing}\label{subsec:ell2}

One of the central problems in compressed sensing is the design of an $\ell_2/\ell_2$ scheme, which is a matrix $\Phi \in \mathbb{R}^{m \times n}$, such that given $y = \Phi x$ we can find $x'$ satisfying
	\[	\mathbb{P}\left \{	\|x-x'\|_2^2 \leq (1+\epsilon) \mathrm{min}_{\mathrm{k-sparse~}z} \|x-z\|_2^2	\right\} \geq 1- \delta.	\]

The goal is to randomly design $\Phi$ satisfying the above with the optimal number of rows, and enabling computation of such an $x'$ in sublinear-time (it can be proved that it suffices to pick $x'$ to be $O(k)$-sparse). Almost all sublinear-time algorithms (precisely, all but \cite{NakosS19}) proceed by reducing the problem to the construction of an $\ell_2/\ell_2$ weak identification)system\footnote{The authors in~\cite{ps12,glps17} define it in a slightly different way, and use slightly different terminology at places, but the essence of the property they demand is the same.}. This is a matrix $\Psi \in \mathbb{R}^{m \times n}$ such that given $y= \Psi x$ we can find $x'$ satisfying $\|(x-x')_{-k/2}\|_2 \leq (1+\epsilon) \|x_{-k}\|_2$ with probability $1-\delta$; recalling that $x_{-k}$ is the vector that occurs after zeroing out the $k$ largest in magnitude coordinates in $x$. For yet another intriguing consequence of our techniques, we give the strongest weak identification $\ell_2/\ell_2$ system available in the literature. On how that translates to $\ell_2/\ell_2$ schemes, we refer the reader to Section~\ref{sec:ell2}.

\begin{theorem}\label{thm:ell2}
There exists a randomized construction of an $\ell_2/\ell_2$ weak identification system with \[m = O\left((k/\epsilon) \log(n/k) + \frac{1}{\epsilon} \cdot \frac{\log (n/k)}{ \log \log (n/k)}\cdot \log(1/\delta)\right),\] which allows finding the desired $x'$ in time $O(m \log^2 m)$.
\end{theorem}

A comparison with previous work follows.
\begin{itemize}

\item The construction in \cite{glps12} requires $m=\Theta((k/\epsilon) \log(n/k)\cdot \log(1/\delta))$.

\item The construction in \cite{lnw17} achieves $m=O((k/\epsilon) \log(n/k) + \epsilon^{-1}\log(n/k)\log(1/\delta))$, but in order to run in near-linear time in $m$ storing an additional inversion table of size $\Omega(n)$ is required.

\item The strongest result in \cite{ps12,gnprs13} obtains \[m = O(\epsilon^{-4} k \log(n/k) (\log_k n)^\alpha + \epsilon^{-1}\poly(\log n)\log (1/\delta))\] and decoding time $\Omega( (k/\epsilon)^{2^{1/\alpha}}) \poly(\log n))$, for any $a<1$. The main source of sub-optimality is the invocation of a list-recoverable code based on the Loomis-Whitney inequality~\cite{nprr18}.
\end{itemize}

To the best of our knowledge, our work is the first to construct a near-optimal weak system with near-optimal decoding time (without using an additional inversion table as in~\cite{lnw17}). In fact, we are able to obtain stronger results for the general $\ell_2/\ell_2$ problem, but the argument is very lengthy and somewhat outside the scope of the technical contribution of this paper, so we decided to leave the most general result for a future publication.

config: arxiv


TITLE: Trigonometric functions limit to complex infinity
QUESTION [3 upvotes]: It is well-known that trigonometric functions oscillate on the real axis and the limit does not exist as the argument approaches infinity.
However, I suspect that a limiting value exist if the argument approaches any complex infinity that is not real, i.e.
$$\lim_{r\to\infty} f(re^{i\theta})$$ is suspected to exist for $\theta \ne n\pi$, where $f$ is a trigonometric function.
I confirmed it is the case for $\tan (z)$ by decomposing it into real and imaginary parts.
For real part:
$$\lim_{r\to\infty}\frac{\sin 2r\cos\theta}{\cos 2r\cos\theta+\cosh 2r\sin \theta}=0$$ which is straightforward.
For imaginary part:
$$\lim_{r\to\infty}\frac{\sinh 2r\sin\theta}{\cos 2r\cos\theta+\cosh 2r\sin \theta}=\text{sgn}(\sin\theta)$$
Thus $$\lim_{r\to\infty}\tan(re^{i\theta})= \text{sgn}(\sin\theta)i$$
My questions are:

Are the above calculations correct?

Is there an easier way to compute the limit, other than decomposing it into real and imaginary parts?

Indeed, the limits should be well known. Are there some reliable references that summarize the results for various trigonometric functions?

Thanks in advance.

REPLY [4 votes]: You can base all calculations on the fact that $e^{iz} \to \infty$ as $z \to \infty$ with $-\pi+\varepsilon<\arg{z}<\varepsilon$ and $e^{iz} \to 0$ as $z \to \infty$ with $\varepsilon<\arg{z}<\pi-\varepsilon$ (this follows because $\lvert e^{i(x+iy)} \rvert = e^{-y}$). For example,
$$ \tan{z} = \frac{e^{iz}-e^{-iz}}{i(e^{iz}+e^{-iz})} = -i\frac{e^{2iz}-1}{e^{2iz}+1}, $$
which tends to $i$ for $\varepsilon<\arg{z}<\pi-\varepsilon$ and $-i$ for $-\pi+\varepsilon<\arg{z}<\varepsilon$.
Similarly, for the other functions, $\cos{z}$ and $\sin{z}$ both tend to $\infty$ for $z \to \infty$ with $\arg{z}$ bounded away from $0$ and $\pi$. Therefore their reciprocals $\csc{z}$ and $\sec{z}$ both tend to $0$ in the same region.
Lastly, $\cot{z}=1/\tan{z}$, so it tends to $-i$ for $\varepsilon<\arg{z}<\pi-\varepsilon$ and $i$ for $-\pi+\varepsilon<\arg{z}<\varepsilon$.


TITLE: What is $\Bbb E(X)$?
QUESTION [2 upvotes]: Let there be $100$ balls in a box out of which $50$ are red and $50$ are green. Pick $75$ balls at random from the box and throw them away. Now pick one ball at random from the remaining balls in the box. Let $X$ be the random variable which takes the value $100$ when the ball drawn is red in colour and takes the value $25$ if the ball drawn is green in colour. Find the expectation $\Bbb E(X).$
My attempt $:$ Let $Y$ denote the number of red balls thrown away. Then the number of green balls thrown away is $75-Y.$ Clearly $Y \geq 25.$ So \begin{align*} \Bbb P(X=100) & = \sum\limits_{n=25}^{49} \Bbb P(X=100 \mid Y=n)\ \Bbb P(Y=n) \\ & = \sum\limits_{n=25}^{49} \frac {\binom {50-n} {1}} {\binom {25} {1}} \times \frac {\binom {50} {n}} {\binom {100} {n}}  \end{align*}
Similarly \begin{align*} \Bbb P(X=25) & = \sum\limits_{n=25}^{49} \Bbb P(X=25 \mid (75-Y) = n)\ \Bbb P((75-Y) = n) \\ & = \sum\limits_{n=25}^{49} \Bbb P(X=25 \mid Y = 75-n)\ \Bbb P(Y = 75-n) \\ & = \sum\limits_{n=25}^{49} \frac {\binom {50-n} {1}} {\binom {25} {1}} \times \frac {\binom {50} {75-n}} {\binom {100} {75-n}} \end{align*}
Then the required expectation would be $$100\ \Bbb P(X=100) + 25\ \Bbb P(X=25).$$ But the computation is very tough. Is there any simpler way to approach the problem?
Any help will be highly appreciated. Thank you very much.

REPLY [2 votes]: It seems to me that red and green are indistinguishable in this scenario. Whatever the probability of picking a red ball is, it must be equal to the probability of picking a green ball. So $$P(X=100) = P(X=25) = 1/2$$
Which implies
$$E(X) = 100\cdot P(X=100) + 25 \cdot P(X=25) = 62.5$$

A simple script confirms that the expectation is indeed $62.5$. You can also double check by computing the probability. Using your terminology,
$$P(Y=n) = \frac{{75 \choose n} \cdot {25 \choose 50-n}}  {100\choose 50} $$
So that
$$P(X=100) = \sum_{n=25}^{50} \frac{50-n}{25} \cdot \frac{{75 \choose n} \cdot {25 \choose 50-n}}  {100\choose 50} $$
And you can check numerically that this is equal to $1/2$


TITLE: Extremum - relationship between cartesian and polar coordinates
QUESTION [0 upvotes]: If I find local minimum or maximum of function in polar coordinates, can I say that it is the same as in cartesian coordinates ?

REPLY [0 votes]: Definition: $x$ is a local maximum for $f$ if there exists a neighborhood $U$ of $x$ such that:
$$\forall y \in U:~f\left(y\right)\leq f\left(x\right)$$
Does this look coordinate-dependent?
For definitions look here.


TITLE: Can someone point me in the direction of why $\sum\limits_{n=0}^{T-1}A(1+R)^n = A\frac{(1+R)^T-1}{R}$
QUESTION [1 upvotes]: Before you ask, this isn't a homework question, I am just curious.
I was trying to derive an expression for compound interest with evenly spaced deposits.
I reached the point: $F = I(1+R)^T + \sum\limits_{n=0}^{T-1}A(1+R)^n$
I = Initial deposit
A = Annual deposit
R = Interest rate
T = Period
Obviously this isn't the most easy expression to work with so I looked up the correct answer which is apparently:
$F = I(1+R)^T + A\frac{(1+R)^T-1}{R}$
Apparently these expression are equivalent, so my question is, how do I get from:
$\sum\limits_{n=0}^{T-1}A(1+R)^n$ to $A\frac{(1+R)^T-1}{R}$?

REPLY [2 votes]: this is a standard geometric series summation. let the first term be $a$ and the factor of increase be $x$. suppose there are $n-1$ increases, then:
$$
S = a + ax + ax^2 + \cdots + ax^{n-1}
$$
multiply by $x$
$$
Sx = ax + ax^2 + ax^3 + \cdots + ax^n
$$
subtract the first from the second:
$$
S(x-1) = ax^n -a
$$
this is the trick! all terms cancel except the two extremes.
simplifying:
$$
S = a\frac{x^n-1}{x-1}
$$
since in your case we have
$$
x=1+R \\
T=n
$$
the formula becomes:
$$
S= A\frac{(1+R)^T-1}{R}
$$

REPLY [1 votes]: Your function is basically in the form of a geometric series, which we can write as
$$ S = \sum_{n=0}^{N} ar^n $$
for first term $a$ and common ratio $r$. The easiest way to see how to compute the sum is to write it out longhand, multiply it by $r$, and then subtract:
$$ \begin{align*}
S &= a + ar + ar^2 + \dotsb + ar^n \\
rS &= \phantom{a+{}} ar+ ar^2 + \dotsb + ar^n + ar^{n+1} \\
(r-1)S &= -a + ar^{n+1} \\
S &= a\frac{r^{n+1}-1}{r-1}
\end{align*}$$


TITLE: Proof of the inner regularity of the Haar measure on $\mathbb{R}/\mathbb{Z}$
QUESTION [1 upvotes]: Let $m$ be the Lebesgue measure on $[0,1)$, which is the fundamental domain of $\mathbb{R}/\mathbb{Z}$. Consider the bijection $\iota:\mathbb{R}/\mathbb{Z}\to[0,1)$ and define a measure $\mu$ on $\mathbb{R}/\mathbb{Z}$ with $\mu(E)=m(\iota(E))$ for any Borel set $E\subset\mathbb{R}/\mathbb{Z}$. I would like to show that $\mu$ is a Haar measure. But I'm stuck with showing the inner regularity  of $\mu$ (yes, I would like to show directly that $\mu$ is a Radon measure).
For instance, let $E =[0.2, 0.8] \hbox{ mod } 1$. Then clearly by the inner regularity of Lebesgue measure, one has
$$m(\iota(E))=\sup\{m(K):K\subset \iota(E), K\textrm{ compact in } [0,1)\}.$$
However, how can I show that
$$m(\iota(E))=\sup\{m(\iota(K))\:K\subset E, K\textrm{ compact in } {\mathbb R}/{\mathbb Z}\}?$$

REPLY [0 votes]: All you really need is the inner regularity of Lebesgue measure.
The bijection $i: \mathbb{R}/\mathbb{Z} \rightarrow [0,1)$ is not continuous, but its inverse is.  Hence the preimage of any compact set in $[0,1)$ is compact in $\mathbb{R}/\mathbb{Z}$.  On the other hand, $K$ could be a compact set in $\mathbb{R}/\mathbb{Z}$, but $\iota(K)$ need not be compact.
If $E \subseteq \mathbb{R}/\mathbb{Z}$, then the (Lebesgue) measure $s := m(\iota(E))$ of $\iota (E)$ is the supremum of $m(C)$, as $C$ runs through all compact subsets of $\mathbb{R}$ which are contained in $\iota(E)$.  Such compact sets are necessarily contained in $[0,1)$, so $ m(\iota(E))$ is the supremum of $m(C)$, as $C$ runs through all compact sets of $[0,1)$ which are contained in $\iota(E)$.
Let $S = \sup \{ m(\iota(K)) : K \subseteq E \textrm{ and is compact } \}$.  If $C \subseteq \iota(E)$ is compact, then $K = \iota^{-1}(C)$ is compact in $\mathbb{R}/\mathbb{Z}$ and contained in $E$, with $m(C) = m(\iota(K))$, so certainly $S \geq s$ (you are taking a supremum over more things).
To show that $S$ does not strictly exceed $s$, it suffices to show that for any compact set $K$ contained in $E$, the measure of $\iota(K)$ can be approximated  from below by compact sets in $[0,1)$ which are contained in $E$.  But this is clear, because $\iota(K)$ can be approximated by compact sets in $[0,1)$ which are contained in $\iota(K)$ (hence in $E$).


TITLE: existence of antiderivatives of nasty but elementary functions
QUESTION [5 upvotes]: In discussing with my honors calculus class the fact that some continuous elementary functions do not have an elementary antiderivative, I realized I was unsure whether every discontinuous elementary function has an antiderivative at all.
The answer may depend on the precise definition of elementary function one uses.  Note that the elementary function $\sqrt{x^2}/x$ equals +1 or -1 according to whether $x$ is positive or negative, and is undefined at $x=0$.  Of course this particular discontinuous elementary function has an antiderivative on its domain.  But once you have discontinuous functions like this, and you have trig functions, and you start forming compositions, you can get fairly nasty functions with infinitely many discontinuities, and it's not obvious to me that a function of this kind with domain $D$ necessarily has an antiderivative on $D$.

REPLY [1 votes]: "Integration in finite terms" uses an exact definition of the class of elementary functions. According to J. F. Ritt, $\exp$, $\ln$ and the algebraic functions are analytic almost everywhere, and therefore the elementary functions.
"Integration in finite terms" treats only formal antiderivatives. Clearly, the concrete antiderivative depends on the concrete domain of the function in the integrand. If you integrate functions by applying other methods, you have also make decisions about the domain of the functions.


TITLE: When are subcategories of continuous functors reflective?
QUESTION [3 upvotes]: Let $J$ be a collection of small categories (to be thought of as diagrams in a category). Let $C$ be a small category with all $J$-limits (i.e. for every $J_0 \in J$ and every functor $F:J_0\rightarrow C$, $\lim F$ exists in $C$). Let $D$ be any category with all $J$-limits (such as Set).
Consider the category $[C,D]_J$ of functors from $C$ to $D$ which preserve all $J$-limits, with natural transformations as morphisms.
Question: What conditions on $J$ must hold in order for $[C,D]_J$ to be a reflective subcategory of $[C,D]$ (the category of all functors from $C$ to $D$)?
I ran into this question when investigating the case of two collections of diagrams $J \subseteq J'$, so that $[C,D]_{J'} \subseteq [C,D]_J$ (assuming $C$ and $D$ have all $J'$-limits). Since all these categories are full subcategories, it turns out that $[C,D]_{J'}$ is a reflective subcategory of $[C,D]_{J}$ if $[C,D]_{J'}$ is a reflective subcategory of $[C,D]$. (if $U_2$ is fully faithful, and $U_3 = U_2 \circ U_1$ has a left adjoint $F_3$, then $U_1$ has a left adjoint: $F_3 \circ U_2$.

REPLY [5 votes]: When $D$ has copowers, the reflectivity of continuous functors can be seen as a case of the orthogonal subcategory problem. This problem asks whether the full subcategory $\mathcal{X}_\Gamma$ of a category $\mathcal{X}$ on the objects orthogonal to a set of morphisms $\Gamma$ is reflective. There are many hypotheses that ensure a positive answer, a famous one being the condition that $\mathcal{X}$ is a locally presentable category and $\Gamma$ is a small set.
The problem so reduces because we can show that a  functor $G : C \to D$ preserves the limit of $F : J_0 \to C$ if and only if it is orthogonal in the functor category $[C,D]$ to the morphisms
$$\text{colim}_j C(Fj,-)\cdot d \longrightarrow C(\text{lim}_j Fj,-)\cdot d$$
for each $d\in D$. Letting $\Gamma$ be the set of these morphisms for all $F \in J$, we have therefore that the full subcategory $[C,D]_J$ of the $J$-continuous functors is the orthogonal subcategory $[C,D]_\Gamma$.
Hence (keeping your assumptions of smallness) the full subcategory $[C,D]_J$ is reflective in $[C,D]$ if $D$ is a locally presentable category and $J$ is a small set.
The classic paper on this subject is

Freyd, P. J.; Kelly, G. M. Categories of continuous functors. I. J. Pure Appl. Algebra 2 (1972), 169--191.

where more general hypotheses are considered,
and see

Kelly, G. M. A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on. Bull. Austral. Math. Soc. 22 (1980), no. 1, 1--83.

(in particular section 12) for a more complete and cleaner treatment.


text:
\section{Some Interrelated Polynomial Invariants}
\label{sec:polynomials}

We present a further sampling of graph polynomials here.  They are each
related in some way to the Tutte polynomial, and have additional
relations among themselves.  These relations lead to combinatorial
insights as results for any one polynomial then inform those related
to it.

 \subsection{Characteristic  and Matching Polynomials}
 \index{polynomial!characteristic}
 \index{polynomial!matching}

 The characteristic and matching polynomials are particularly
 interrelated, so we treat them together here, beginning with the
 characteristic polynomial $f(G;x)$ already introduced in
 Definition~\ref{adjpolys}.  Note that $f(G;x)$ is a monic polynomial
 of   degree $n$. Furthermore, since the adjacency matrix $A$ is real and
 symmetric, all its  eigenvalues are real, and thus all the zeros of
 $f(G;x)$ are real.

 By using properties of
 determinants we can find interpretations of the coefficients of
 $f(G;x)$ in terms of the \emph{principal minors} of $A$. A principal
 minor of order $r$ is the determinant of an $r\times r$ submatrix of $A$
 obtained by choosing $r$ rows and  columns with the same set of
 indices.
 \begin{proposition}\label{CharPolyMinors}
  Suppose that $f(G;x)=\sum_{i=0}^{n} a_{i}x^{n-i}$. Then $(-1)^{i}a_{i}$ is
  equal to the sum of the principal minors of $A$ with order $i$.
 \end{proposition}
 This property of the  characteristic polynomial can be found, for
 example, in Horn and Johnson~\cite{HJ90}.

 Since the diagonal elements of $A$ are all zero, we have that
 $a_1=0$. The principal minors of order two and three which are not
 zero are of the form $|J-I|$, where $J$ is the matrix having all
 entries +1 and $J-I$ has order 2 or 3. The $2\times 2$ submatrices $J-I$
 of $A(G)$ correspond naturally to the edges of $G$ and the $3\times 3$
 submatrices $J-I$ correspond to the $K_3$ subgraphs of $G$. Thus
 $c_{2}=-|E(G)|$ and
 $-c_{3}$ is  twice the number of $K_3$ subgraphs of $G$.

 A \emph{linear
 subgraph}\index{linear subgraph}\label{linear_subgraph} of $G$ is a
 subgraph whose components are edges or cycles.  An expression for the
 coefficients of $f(G;x)$ in terms of linear subgraphs is given in the
 following.
  \begin{proposition}\label{CharPolyCoefficients}
 The coefficients of the characteristic polynomial may be expressed as
 \[
  (-1)^{i}a_{i} =
    \sum_{\Lambda} (-1)^{r(\Lambda)} 2^{r^{*}(\Lambda)} ,
\]
  where $r$ is the rank function and the sum is over all linear  subgraphs $\Lambda$ of $G$ having
  $i$ vertices.
\end{proposition}

 Note that because $\Lambda$ is a linear subgraph,
 $r^{*}(\Lambda)$ is simply the number of components in $\Lambda$
 that are cycles. The proof of Proposition~\ref{CharPolyCoefficients}
 uses Proposition~\ref{CharPolyMinors} and
 can be found in Harary~\cite{Har62}, while a detailed history of this result
is given by Cvetkovi\'c, Doob, and Sachs~\cite{CDS80}.

 As with the Tutte polynomial  we also have
 some reduction formulas and an expression for the derivative of the
 characteristic polynomial.
\begin{theorem}\label{CharPolyProperties}
The characteristic polynomial of a graph satisfies the following
identities:
\begin{enumerate}
\item $f(G\cup H;x)=f(G;x)f(H;x)$, \label{CharPolyMult}
\item $f(G;x)= f(G\setminus e,x)- f(G-{u}-{v};x)$ if $e=\{u,v\}$ is
 a cut-edge  of $G$; \label{CharPolyLinear}
\item $\frac{\partial}{\partial x} f(G;x)=\sum_{v\in
    V(G)}f(G-{v};x)$. \label{CharPolyDerivative}
\end{enumerate}
\end{theorem}

A proof of these properties can be found in
Godsil~\cite{God93}. Item~\ref{CharPolyMult}
is an  easy exercises in matrix theory, as in Horn and
Johnson~\cite{HJ90}. Item~\ref{CharPolyLinear} can be proved by using
Proposition~\ref{CharPolyCoefficients}
and considering the linear subgraphs of $G$ that use the edge $e$ and
the ones that do not use it. The result follows because $e$ is in no cycle of
$G$ if and only if it is a cut-edge. Item~\ref{CharPolyDerivative} can
be proved by using
Proposition~\ref{CharPolyMinors} since any principal minor of order $i$ is
counted $n-i$ times in the right hand side of the formula in
Item~\ref{CharPolyDerivative}.

 Given a graph $G$, the collection of  (unlabeled)
 subgraphs $G-v$, for $v\in V(G)$, is called the \emph{deck}
 \index{graph!deck} of
 $G$, and the individual subgraphs are called
 \emph{cards}.\index{graph!card} Thus, the deck for a graph on $n$ vertices
 consists of $n$ graphs, each
 of which has $n-1$ vertices.
 Ulam's reconstruction conjecture in \cite{Ula60} asserts that any finite graph
 $G$ with more than two vertices is uniquely determined by its deck,
 see~\cite{Ula60}, and we call any graph that satisfies the
 conjecture
 \emph{reconstructible}\index{graph!reconstructible}. Similarly, an
 invariant of $G$ which can be deduced from the
 deck is called reconstructible.

 Clearly, the number $n$ of vertices of a graph is
 reconstructible. Also, as every edge is present in exactly $n-2$ cards,
 the number of edges is also reconstructible. The following useful
 example of reconstructibility is due to Kelly~\cite{Kel57}.
\begin{lemma}[Kelly's lemma] Let $G$ and $H$ be graphs, and let
 $\nu(H,G)$ denote the number of
 subgraphs of $G$ isomorphic to  $H$.  Then
 \[
   (|V(G)|-|V(H)|)\nu(H,G)=\sum_{v\in V(G)} \nu(H,G-v) .
\]
\end{lemma}
 The proof is by a double counting argument, and it follows that
 $\nu(H,G)$ is reconstructible whenever $|V(H)|<|V(G)|$.

 Tutte  proved in~\cite{Tut67} that  the Tutte polynomial is
 reconstructible,  and thus  the chromatic polynomial, the flow
 polynomial,  the number of spanning trees and any invariant mentioned
 in the previous chapter are also reconstructible. Tutte  also proved that
 the characteristic polynomial is reconstructible in~\cite{Tut79}.

\begin{theorem}\label{CharPolyReconstructible}
The characteristic polynomial of a graph is reconstructible.
\end{theorem}

 For the proof, note that we have immediately from
 Theorem~\ref{CharPolyProperties} that $f'(G;x)$ is
 reconstructible. It then remains to prove that the constant term of
 $f(G;x)$ is reconstructible. But by Proposition~\ref{CharPolyMinors},
 this is the same as proving that $|A(G)|$ is reconstructible. Then,
 using Theorem~\ref{CharPolyCoefficients} and an extension of Kelly's
 lemma (see~\cite{Koc81}), the problem is reduced to proving that the
 number of  Hamiltonian cycles is reconstructible.  A complete proof
 of Theorem~\ref{CharPolyReconstructible} based on the proof in
 Kocay~\cite{Koc81}, can be found  in~\cite{God93}.

 Let us turn now to the matching polynomial.
 An $i$-\emph{matching}\index{matching@$i$-matching} in a graph $G$ is
 a set of $i$
 edges, no two of which
 have a vertex in common. Let $\Phi_{i}(G)$ denote the number of
 $i$-matchings, and set $\Phi_{0}(G)=1$. Thus
 $\Phi_{1}(G)=m$ is the number of edges of $G$, and if $n$, the number
 of vertices, is even, then
 $\Phi_{n/2}(G)$ is the number of perfect matchings of $G$.

\begin{definition}
Let $G$ be a graph.  Then the
 matching polynomial\index{polynomial!matching}
 \index{matching polynomial}  of $G$ is
\[
   \mu(G;x)=\sum_{i\geq 0} (-1)^{i} \Phi_{i}(G) x^{n-2i} .
\]
\end{definition}

A more natural polynomial might be the \emph{matching generating
 polynomial},\index{matching generating polynomial}
 \index{polynomial!matching generating} given as the
 generating function of
 $i$-matchings by
\[
    g(G;x)=\sum_{i\geq 0} \Phi_{i}(G) x^{i} .
\]
 However, the two polynomials are related by the identity
\[
      \mu(G;x)=x^{n}g(G;(-x)^{2}) ,
\]
  so there is no essential difference between them.

 The matching polynomial is also known as the \emph{acyclic
 polynomial}\index{polynomial!acyclic} in Gutman and
 Trinajsti\'c~\cite{GT76},
 \emph{matching defect polynomial}\index{polynomial!matching defect}
 in Lov\'asz and Plummer~\cite{LP86} and \emph{reference
 polynomial}\index{polynomial!reference} in Aihara~\cite{Aih76}. It
 has appeared independently in several different contexts.
 In combinatorics, it was probably introduced by Farrell in~\cite{Far79a},
 but since the matching polynomial is essentially the same as the rook
 polynomial\index{polynomial!rook} for bipartite graphs (see
 Farrell~\cite{Far88}),  then its
 origin can be traced back  at least to Riordan~\cite{Rio58}. In statistical
 physics it  appears because of  the monomer-dimer problem and was
 introduced by
 Heilmann and Lieb in~\cite{HL70} and independently by Kunz
 in~\cite{Kun70}.  Finally, in theoretical chemistry was introduced by Hosaya
 in~\cite{Hos71} and later in connection with the so-called
 topological resonance energy by Gutman, Milun and Trinajsti\'c
 in~\cite{GT76,GMT76,GMT77} and independently by Aihara
 in~\cite{Aih76}. For a  full account of the history of the matching
 polynomial
 see Gutman~\cite{Gut91}.

 As with the Tutte and characteristic polynomials, we have some
 reduction formulas for the matching polynomial. The proof of the
 following theorem can be found in Godsil~\cite{God93}.
\begin{theorem}
 The matching polynomial satisfies the following identities:
 \begin{enumerate}
 \item $\mu(G\cup H;x)=\mu(G;x)\mu(H;x)$,\label{MatchPolyDisjoint}
 \item $\mu(G;x)=\mu(G\setminus e;x)-\mu(G-{u}-{v};x)$ if $e=\{u,v\}$ is
 an edge  of $G$,\label{MatchPolyDeletionEdge}
\item $\mu(G;x)=x\mu(G-{u};x)-\sum_{\{u,v\}\in E(G)}
  \mu(G-{v}-{u};x)$, if $u\in V(G)$, \label{MatchPolyDeletionVertex}
\item $\frac{\partial}{\partial x} \mu(G;x)=\sum_{v\in
    V(G)}\mu(G-{v};x)$. \label{MatchPolyDerivative}
 \end{enumerate}
\end{theorem}
 To choose an $i$-matching in $G\cup H$ you need to choose an
 $s$-matching in $G$ and a $t$-matching in $H$ such that
 $s+t=i$. Item~\ref{MatchPolyDisjoint} then
  follows by the fundamental counting
 principle. For Item~\ref{MatchPolyDeletionEdge}, notice that the set of
 $i$-matchings can be partitioned into those $i$-matchings that use the
 edge $e$ and those that do not use
 it. Item~\ref{MatchPolyDeletionVertex} follows similarly. Finally,
 every $i$-matching of
 $G$ with $i<n/2$ is counted $n-2i$ times in the right-hand side of
 the formula in Item~\ref{MatchPolyDerivative}, so the result follows.

 When the graph $G$ is a forest, a linear subgraph of $G$ with $j$ vertices

 corresponds to a matching covering $j$ vertices, with
 $j$ even. Thus, Proposition~\ref{CharPolyCoefficients} has the
 following corollary, observed by Hosaya~\cite{Hos71}  and by Heilmann
 and Lieb~\cite{HL72}.

\begin{corollary}\label{MatchPolyCharPoly}
 If $G$ is a forest then $f(G;x)=\mu(G;x)$.
\end{corollary}

  An  unexpected property of the matching polynomial, proved by
 Heilmann and Lieb~\cite{HL72},  is that all its zeros
 are real, and furthermore the zeros for any graph $G$ interlace with
 the zeros of any of the cards in its deck.  The same paper also gives
 bounds for the zeros.

 \begin{theorem} \label{MatchPolyzeros}
  For any graph $G$, the matching polynomial $\mu(G;x)$ has only real
  zeros. Furthermore, if
  $u$ is any vertex in $G$ and if $a_1,a_2,\ldots, a_n$ are the zeros
  of  $\mu(G;x)$ while the zeros of $\mu(G-{u};x)$ are
  $a'_1,a'_2,\ldots, a'_{n-1}$, then
 \[
    a_1\leq a'_1\leq a_2\leq a'_2\leq \ldots\leq a'_{n-1}\leq a_{n} ,
 \]
 that is, the zeros of $\mu(G;x)$ and $\mu(G-{u};x)$ interlace.
 \end{theorem}

 \begin{theorem}
 The (real) zeros, $a_1,a_2,\ldots, a_n$, of $\mu(G;x)$,  satisfy
\[        |a_i|<  2\sqrt{maxdeg(G)-1}. \]

 \end{theorem}

We outline a proof of
 Theorem~\ref{MatchPolyzeros} from Godsil~\cite{God81b} that uses some of the
 results already
 mentioned for $\mu(G;x)$ and $f(G;x)$. First, given a graph $G$ and a
 vertex $u$ in $G$, the
 \emph{path tree}\index{path tree} $T(G,u)$ is the tree that has as
 its vertices the paths in $G$
 which start at $u$, and where two such vertices are
 joined by an edge if one represents a maximal proper subpath
 (i.e. all but the last edge) of the other. We then have
 the following proposition from~\cite{God81b} that leads to a proof of
 Theorem~\ref{MatchPolyzeros}.

\begin{proposition} Let $u$ be a vertex in a graph $G$, let $T=T(G,u)$ be
 the path tree of $G$ with respect to $u$, and let $u^{\prime}$ be the
 vertex of $T$ corresponding to the path of length 0 beginning at
 $u$. Then
\[
   \frac{\mu(G-u;x)}{\mu(G;x)} = \frac{\mu(T-u^{\prime};x)}{\mu(T;x)} =
   \frac{f(T-u^{\prime};x)}{f(T;x)} .
\]
\end{proposition}
 The last equality follows from
 Corollary~\ref{MatchPolyCharPoly}. Because all the roots of the
 characteristic  polynomial are real, we conclude that all zeros and
 poles of the  rational function ${\mu(G-u;x)}/{\mu(G;x)}$
 are real. An induction argument on the number
 of vertices in $G$ then yields the conclusion that all the zeros of
 $\mu(G;x)$
 are real.

 An  interesting combinatorial consequence of
 Theorem~\ref{MatchPolyzeros} is the following result of Heilmann and
 Lieb~\cite{HL72}, which gives a stark contrast with how little is known
 about the coefficients of the chromatic polynomial.

 \begin{theorem}
 For any graph $G$, the sequence $\Phi_{0}(G)$, $\Phi_{1}(G)$,
 $\ldots$ of coefficients of $g(G;x)$ is log-concave, that is
 $\Phi_i^{2}\geq \Phi_{i-1}\Phi_{i+1}$.
 \end{theorem}

  The characteristic polynomial has been well studied, particularly with
  respect to graphs with the same characteristic polynomial.
  Godsil~\cite{God93} gives a thorough treatment of both the
  characteristic and
  the matching polynomials. Another  good reference for the
  characteristic polynomial is Biggs~\cite{Big96}. Just as the matching
  polynomial is a way to study the matchings of a graph, the
  characteristic polynomial is a way to study the spectra of the
  adjacency matrix of a graph. Cvetkovi\'c, Doob, and Sachs have
  written a book~\cite{CDS80} dedicated to
  the spectra of the adjacency matrix, and Lov\'asz and
  Plummer~\cite{LP86} have a book
  devoted to the theory of matchings.   Furthermore, although  the
  characteristic
  polynomial is not a complete invariant of graphs, it is conjectured
  that the characteristic polynomial of a graph $G$ is reconstructible
  from its polynomial deck, i.e. from the set
  of characteristic polynomials of the cards of $G$.  See Gutman and
  Cvetkovi\'c~\cite{GC75} for the conjecture,
  and then Cvetkovi\'c and Lepovi\'c~\cite{CL98}, where it is proved in
  the case of trees.

 \subsection{Ehrhart Polynomial}

 A \emph{convex polytope}\index{polytope!convex} $P$ is the convex
 hull of a finite set of
 points in ${\mathbb  R}^m$. We denote the interior
 of $P$ (in the usual topological sense) by $P^o$. A convex polytope $P$ is said to be a
 rational or integral polytope if all its vertices have rational or
 integral coordinates, respectively. We write $d=\dim P$ and call $P$
 a $d$-polytope.

 For $P\subset {\mathbb  R}^m$ a rational $d$-polytope and $t$ a
 nonnegative integer
 we define the functions $i(P;t)=|tP\cap{\mathbb Z}^m |$ and
 $\overline{i}(P;t)=|tP^o\cap{\mathbb Z}^m |$,
 where $tP=\{ta| a\in P\}$ is the $t$-fold dilatation of $P$.
 Ehrhart proved in~\cite{Ehr67a, Ehr67b} that these functions are
 \emph{quasi-polynomials},\index{polynomial!quasi-}
 that is, they are of the form
\[
    c_d(t)t^d+c_{t-1}(t)t^{d-1}+\ldots+c_0(t) ,
\]
 where  each $c_i(t)$ is a periodic function with integer period. Since
 $i(P;t)$ is a quasi-polynomial, it can be defined for all $t\in
 {\mathbb Z}$. In fact, we have the following
 reciprocity law due to Ehrhart~\cite{Ehr67c}:

\[
        i(P;-t)=(-1)^{d}\,\overline{i}(P;t) .
\]
 For more on this beautiful theory see the monograph by Ehrhart~\cite{Ehr77}.

 From Ehrhart~\cite{Ehr67a,Ehr67b} (also see Stanley~\cite{Sta96}),
 we have that when $P\subset {\mathbb  R}^m$ is an integral
 $d$-polytope,
 then $i(P;t)$ and $\overline{i}(P;t)$ are polynomials,
  which leads to the following definition of the Ehrhart polynomial.

\begin{definition}
Let $P$ be an integral convex $d$-polytope.  Then the Ehrhart
polynomial of $P$ is
  \[
       i(P;t)=c_0+c_1t+\ldots +c_{d-1}t^{n-1}+c_{d}t^n.
 \]
 \end{definition}

From the early works of
 Ehrhart~\cite{Ehr67a} and Macdonald~\cite{Mac71} it is known that
 $c_0=1$ and

 $c_d=\mbox{vol}(P)$,  and  that $c_{d-1}$ is half of the surface area
 of $P$, normalized with respect to the sub-lattice on each face of
 $P$.  Specifically, $c_{d-1}=1/2\sum_{F}\mbox{vol}_{d-1}(F)$, where $F$
 ranges over all facets of $P$ and the volume of a facet is measured
 intrinsically with respect to the lattice ${\mathbb Z}^m\cap L_F$,
 where $L_F$ is the affine hull of $F$.  The other coefficients were
 not well understood, until the later
 work of Betke and Kneser~\cite{BK85}, Pommersheim~\cite{Pom93},
 Kantor and Khovanskii~\cite{KK93}
 and Diaz and Robins~\cite{DR97}, but
 such interpretations go beyond  the scope of this chapter. For the
 complexity of computing these coefficients see Barvinok~\cite{Bar94}.

 In the special case that $P$ is a \emph{zonotope} there
 is a combinatorial interpretation for the coefficients of the Ehrhart
 polynomial.  First
 recall that if  $A$ is an $r\times m$ real matrix
 written in the form $A=[a_1,...,a_r]$,  then it defines a
 \emph{zonotope}\index{zonotope} $Z(A)$ which
 consists of those  points $p$ of ${\mathbb R}^m$ which can be
 expressed in the form
 \[
     p=\sum_{i=1}^m\lambda_ia_i, \quad 0\leq\lambda_i\leq 1.
 \]
 In other words, $Z(A)$ is the {\it Minkowski sum} of the line
 segments  $[0,a_i]$, for $1\leq i\leq n$. For more on zonotopes,
 see McMullen~\cite{McM71}.

 When $A$ has integer entries, Stanley~\cite{Sta80}, using
 techniques  from Shephard~\cite{She74}, proved that $i(P;t)=\sum_{X}
 f(X)t^{|X|}$, where $X$ ranges over all linearly independent subsets
 of columns of $A$ and where $f(X)$ denotes the greatest common
 divisor of all minors of sizes $|X|$ of the matrix $A$.

 When $A$ is a \emph{totally unimodular matrix},
\index{matrix!totally unimodular} that is, the determinant of every
square submatrix is 0 or $\pm 1$, then $Z(A)$ is described
 as a \emph{unimodular zonotope}.\index{zonotope!unimodular}  For
 these polytopes the previous result shows that
 \[
      i(Z(A);t)=\sum^r_{k=0}f_k\,t^k,
 \]
 where $f_k$ is the number of subsets of columns of the
 matrix $A$ which are linearly independent and have cardinality $k$.
 In other words, the Ehrhart polynomial $i(Z(A);t)$ is the generating
 function of the number of independent sets in the regular matroid
 $M(A)$.

 The incidence matrix $D(G)$ of a graph $G$ is totally unimodular, a
 long-standing result
 due to Poincar\'e~\cite{Poi01} with a modern treatment given by
 Biggs~\cite{Big96}. A
 linearly independent subset of columns in $D$
 corresponds to a subset of edges with no cycle. Thus, the coefficient
 $f_k$ in
 this case is the number of spanning forests of $G$ with exactly $k$
 edges. From the previous chapter  we know that
 $T(G;x+1,y)=\sum_{k=0}^{r}f_{k}x^{r-k}$, where $r$ is the rank of the
 graph
 $G$. With these ingredients we get the following relations with the
 Tutte polynomial from Welsh~\cite{Wel97}.

 \begin{theorem} \label{reciprocity}
  If $G$ is a graph and $D$ is its incident matrix then the Ehrhart
 polynomial of the unimodular zonotope $Z(D)$ is given by
 \[
     i(Z(D);t)=t^{r}T(G;1+\frac{1}{t},1),
 \]
 where $r$ is the rank of $G$.
 \end{theorem}
 In this case, the zonotope $Z(D)$ is a
 $r$-polytope in ${\mathbb  R}^n$, where $n$ is the number of vertices
 of $G$.

 The reciprocity law of Theorem~\ref{reciprocity} leads to the
 following geometric result,
 also from Welsh~\cite{Wel97}.
\begin{corollary}
  If $D$ is the incidence matrix of a  rank $r$ graph $G$ with $n$
 vertices then for any positive integer $\lambda$ the number of
 lattice points of ${\mathbb R}^n$ lying strictly inside the zonotope
 $t Z(D)$ is given by
 \[
     \overline{i}(Z(D);t)=(-t)^{r}T(G;1-\frac{1}{t},1).
 \]
\end{corollary}
 In particular we have that the number of lattice points strictly
 inside $Z(D)$ is  $(-1)^{r}T(G;0,1)$.

\subsection{The Topological Tutte Polynomial of Bollob\'as and Riordan}
\index{polynomial!topological Tutte}

  The classical Tutte polynomial discussed in the previous chapter is
  an invariant of abstract graphs, so it encodes
  no information specific to graphs embedded in surfaces.  In
  \cite{BR01,BR02},
  Bollob\'{a}s and Riordan generalize the classical Tutte polynomial to
  topological graphs,\index{topological graphs}
  \index{graph!topological} that is, graphs embedded in
  surfaces. In \cite{BR01},
  Bollob\'{a}s and Riordan define the {\em cyclic graph
  polynomial},\index{cyclic graph polynomial}
  \index{polynomial!cyclic graph} a three
  variable deletion/contraction invariant for graphs embedded in
  oriented surfaces.  They extend this work in \cite{BR02}, using a
  different approach,
   with the four variable {\em ribbon graph polynomial}.
  \index{ribbon graph polynomial}\index{polynomial!ribbon graph}
  Both of these  polynomials extend the classical Tutte
  polynomial, but in such a way that topological information about the
  embedding is encoded.  The version for oriented surfaces is subsumed
  by the version for arbitrary surfaces, so we focus on the latter
  here. The ribbon graph polynomial is also
  sometimes called the \emph{Bollob\'{a}s-Riordan polynomial}
  \index{polynomial!Bollob\'{a}s-Riordan}after
  the authors or the \emph{topological Tutte polynomial} to emphasize
  that it simultaneously  encodes   topological information
  while generalizing the classical Tutte polynomial.

  First recall that a cellular embedding \index{cellular embedding}
  of a graph in an orientable or
  unorientable surface can be specified by providing a sign for each
  edge and a rotation scheme \index{rotation scheme}for the set of
  half edges at each vertex, where
  a rotation scheme is simply a cyclic ordering of the half edges about a
  vertex.  This is equivalent to a {\em ribbon} (or {\em fat}) {\em graph},
  \index{ribbon graph}\index{fat graph} which is a
  surface with boundary where the vertices are represented by a set of
  disks and the edges by ribbons, with the ribbon of an edge with a
  negative sign having a half-twist. This can also be thought of as taking a
  slight `fattening' of the edges of the graph as it is embedded in the
  surface, or equivalently as `cutting out' the graph together with a small
  neighborhood of it
  from the surface.  Figure~\ref{Fig:fatgraph} shows a graph with
  two vertices and two
  parallel edges, one positive and one negative.  It is embedded on a
  Klein bottle, and the ribbon graph is a M\"obius band with boundary.

   \begin{figure}[hbtp]
     \begin{center}

         \includegraphics{FigA.pdf}
       \caption{A ribbon graph which is a M\"obius band with
         boundary}\label{Fig:fatgraph}
     \end{center}
   \end{figure}

  In addition to the usual graphic characteristics such as number of
  vertices, connected components, rank, and nullity  for a ribbon
  graph $G$ we
  also consider $bc\left( G \right)$, the number of boundary
  components \index{boundary components} of
  the surface, and $t(G)$, an index of the
  orientability of the
  surface.  The value of $t(G)$ is 0 if the surface is
  orientable, and 1
  if it is not.  Thus, $t(G)$ is 1 if and only if  for
  some cycle in $G$,
  the product of the signs of the edges is negative.

   \begin{definition}\label{ribbon graph poly}
  \index{topological Tutte polynomial}
  \index{polynomial!topological Tutte} Let $G$ be a ribbon
  graph, that is, a graph
  embedded in a surface. Then the topological Tutte polynomial of
  Bollob\'as and Riordan is given by
  \begin{equation*}
   \begin{split}
   R(G;x,y,z,w) &= \sum_{A \subseteq E( G)}
                 (x - 1)^{r( G ) - r( A )}
                 y^{n(A)} z^{\kappa(A) - bc(A) + n(A)}
                   w^{t(A)}\\
                &\in Z[x,y,z,w]/\vphantom {Z[x,y,z,w]}
                  \langle w^2  - w\rangle .
   \end{split}
  \end{equation*}

  \end{definition}

  As previously, $r(A)$, $\kappa(A)$, $n(A)$, and now also
  $bc(A)$ and
  $t(A)$, refer to the spanning subgraph of $G$ with
  edge set $A$,
  here with its embedding inherited from $G$.

  Clearly, by comparing with the rank-nullity generating function
  definition of the classical Tutte polynomial given in the previous
  chapter, this generalizes the
  classical Tutte polynomial.  Like the classical Tutte polynomial,
  $R(G;x,y,z,w)$
  is multiplicative on disjoint
  unions and one point joins of ribbon graphs. More importantly, it
  retains the essential properly of obeying a deletion/contraction
  reduction relation.

  We must first define deletion and contraction in the context of
  embedded graphs. The ribbon graph resulting from deleting an edge is
  clear, but contraction requires some care.  Let $e$ be a non-loop
  edge.  First assume the sign of $e$ is positive, by flipping one
  endpoint if necessary to remove the half twist (this reverses
  the cyclic order of the half edges at that vertex and toggles their
  signs). Then $G/e$ is formed by
  deleting $e$ and identifying its endpoints into a single vertex $v$.
  The cyclic order of edges at $v$ comes from the original cyclic order
  at one endpoint, beginning where $e$ had been, and continuing with the
  cyclic order at the other endpoint, again beginning where $e$ had
  been.

  \begin{theorem}\label{ribbon delete-contract}
  If $G$ is a ribbon graph, then
   \[ R(G;x,y,z,w) = R(G/e;x,y,z,w) + R(G-e;x,y,z,w)\]
   if $e$ is an ordinary edge and $R(G;x,y,z,w) =$
  $xR(G/e;x,y,z,w)$ if   $e$ is a bridge.
  \end{theorem}

  The proof depends on a careful analysis of how each of the relevant
  parameters
  $r(A)$, $\kappa(A)$, $n(A)$, $bc(A)$ and
  $t(A)$ changes with the deletion
  or contraction of an edge.

  Repeated application of this theorem reduces a ribbon graph to a
  disjoint union of embedded \emph{blossom graphs},
  \index{blossom graph}\index{graph!blossom} that is, graphs each
  consisting of a single vertex with some number of loops.  Because of
  the embedding, the loops are signed, and there is a rotation system of
  half-edges about the single vertex.  Not surprisingly, the topological
  information is distilled into these minors of the original graph, and
  to complete a deletion/contraction linear recursion computation, it
  is necessary to specify an evaluation of these
  terminal forms.

  Signed chord diagrams \index{chord diagram} provide a useful device
  for determining the
  relevant parameters of an embedded blossom graph.  Recall that a
  \emph{chord  diagram} consists of a circle with $n$ symbols on its
  perimeter, with
  each symbol appearing twice and a chord drawn between each pair of
  like symbols.  A \emph{signed chord diagram}
  \index{chord diagram!signed}\index{signed chord diagram} simply has
  a sign on   each chord.
  A signed chord diagram $D$ corresponds to an embedded blossom graph
  $G$ by assigning a symbol to each loop and arranging them on the
  perimeter of the circle in the chord diagram in the same order as
  the cyclic order of the half-edges
  about the vertex.  A chord receives the same sign as the loop it
  represents.  If we `fatten' the chords as in
  Figure~\ref{Fig:figureB}, with a negative
  chord receiving a half-twist, then $bc(G)$ is equal to the number of
  components in the resulting diagram, which is denoted
  $bc(D)$.
  Similarly, since $G$ has only one vertex, $n(G)$ is the number of
  edges of $G$, which is the number of chords of $D$, so we denote this
  by $n(D)$.  We also set
  $t(D)=t(G)$, and note that
  $t (D) = 0$   if all
  chords of $D$ have a positive sign, and $t(D)=1$
  otherwise.  This,
  combined with the definition of $R(G;x,y,z,w)$ above, gives the
  following evaluation for these terminal forms.
   \begin{figure}[hbtp]
     \begin{center}
       \includegraphics{FigB.pdf}

       \caption{A signed blossom graph, its signed chord diagram, and
         the boundary components of the signed chord
         diagram}\label{Fig:figureB}
     \end{center}
   \end{figure}

  \begin{theorem}\label{blossom eval}
   If $G$ is an embedded blossom graph with
  corresponding signed chord diagram $D$, then
  \[
   R(G;x,y,z,w) = \sum_{D' \subseteq D} y^{n(D')}
                                      z^{1- bc(D')+ n(D')}
                                      w^{t(D')},
  \]
  where the sum is over all subdiagrams $D'$ of $D$.
  \end{theorem}

Theorems~\ref{ribbon delete-contract} and~\ref{blossom eval} taken
together give a linear recursion definition for $R(G;$ $x$, $y$, $z$, $w)$.
There are a number of technical considerations, similar to the care
  that must be taken in contracting edges, but nevertheless many other
  properties analogous to those of the classical Tutte polynomial hold. For
  example, $R(G;x,y,z,w)$ has
  a spanning tree expansion, a universality property, and duality
  relation (in addition to the Bollob\'{a}s and Riordan's originating work
  in \cite{BR01, BR02}, see also recent work by Chmutov \cite{Chm} and
  Moffatt
  \cite{Mof08}).  Furthermore, Chmutov and Pak \cite{CP07}, and
  Moffatt \cite{Mof,Mof08} have shown that $R(G;x,y,z,w)$ also extends
  the relation between the classical Tutte polynomial and the Kauffman
  bracket and Jones polynomial of knot theory due to
  Thistlethwaite~\cite{Thi87} and Kauffman~\cite{Kau89}.

 \subsection{Martin, or Circuit Partition,
   Polynomials}\label{sec:cpp}

In his 1977 thesis, Martin~\cite{Mar77} recursively defined
polynomials $M(G,x)$ and $m(\vec{G};x)$ that encode, respectively,
information about the families of circuits in 4-regular Eulerian
graphs and digraphs. Las Vergnas subsequently found a state model
expression for these polynomials, extended their properties to general
Eulerian graphs and digraphs, and
further developed their theory (see \cite{Las79, Las83, Las88}).  Both
Martin~\cite{Mar78} and Las Vergnas~\cite{Las88} found combinatorial
interpretations for some small integer evaluations of the polynomials,
while combinatorial interpretations for all integer values as well as
some derivatives were given in \cite{E-M00, E-M04a, E-M04b}, and by
Bollob\'{a}s~\cite{Bol02}.

Transforms of the Martin polynomials, $J(G;x)$ and $j(\vec{G};x)$,
given in \cite{E-M98}, and then aptly named
circuit partition polynomials in \cite{ABS00}, facilitate these
computations, and for this reason we give the definitions below in
terms of $J$ and $j$.
Like many of the polynomials surveyed here, the circuit partition
polynomials have several definitions, including linear recursion
formulations, generating function formulations, and state model
formulations.  We give the state model definition, and refer the
reader to ~\cite{E-M04a, E-M04b} for the others.

As with other state model formulations, we must first specify what we
mean by a state of a graph (or digraph) in this context.  Here an
Eulerian graph \index{graph!Eulerian} must have vertices all of even
degree, but it need not be connected.  An Eulerian digraph
\index{Eulerian digraph}\index{graph!Eulerian digraph} must have the
indegree equal to the outdegree at each vertex, and again need not be
connected.

\begin{definition} \label{cpp graph state}
 An \textit{Eulerian graph state}\index{Eulerian graph state}
 of an Eulerian graph $G$ is the result of replacing each
$2n$-valent vertex $v$ of $G$ with $n$
2-valent vertices joining pairs of half edges originally adjacent to $v$.
An Eulerian graph state of an Eulerian digraph $\vec {G}$ is defined
similarly, except here each incoming half edge must be paired with an
outgoing  edge.
\end{definition}

Note that a Eulerian graph state is a disjoint union of cycles, each
consistently oriented in the case of a digraph.

\begin{definition} The circuit partition polynomial.
   \index{circuit partition polynomial}
   \index{polynomial!circuit partition} Let $G$
  be an Eulerian graph, let $St(G)$ be the set of states of $G$, and
  let $c(S)$ be the number of components in a state $S \in St(G)$.
  Then the circuit partition polynomial has a state model formulation
  given by
\[
J(G;x) =
\sum\limits_{S \in St(G)}{x^{c(S)}}.
\]

The circuit partition polynomial is defined similarly for Eulerian
digraphs as
\[
j(\vec {G};x) = \sum\limits_{S \in St(\vec{G})}{x^{c(S)}}.
\]
\end{definition}

The transforms between the circuit partition polynomials and the original
Martin polynomial, as extended to general Eulerian graphs and digraphs
by Las Vergnas, are:

\begin{equation}
 J(G;x) = xM\left( {G;x + 2} \right), \text{ for }G \text{ an Eulerian
 graph, and }
\end{equation}
\begin{equation}\label{jm}
j(\vec {G};x) = xm\left(
{\vec {G};x + 1} \right) \text{ for } \vec {G} \text{ an Eulerian digraph}.
\end{equation}

The circuit partition polynomials have `splitting' formulas, analogous
to Tutte's identity for the chromatic polynomial given in the previous chapter, proofs for
which may be found in \cite{E-M98, E-M04b}.  These formulas derive
from the Hopf algebra structures of the generalized transition
polynomial discussed in Subsection~\ref{gen_transition_poly},
but may also be proved combinatorially, as by
Bollob\'as~\cite{Bol02} and \cite{E-M04b}.

\begin{theorem}\label{cppsplit} Let $G$ be an Eulerian graph and
  $\vec{G}$ be an Eulerian digraph.  Then

\[
J(G;x + y) = \sum {J\left( {A;x}
\right)J\left( {A^c;y} \right)},
\]
where the sum is over all subsets $A \subseteq E(G)$ such that $G$
restricted to both $A$ and $A^c = E(G)-A$ is Eulerian. Also,
\[
j(\vec {G};x + y)
= \sum {j\left( {\vec {A};x} \right)j\left( {\vec {A}^c;y} \right)},
\]
where the sum is over all subsets $\vec {A} \subseteq E(\vec {G})$
such that $\vec {G}$ restricted to both $\vec {A}$ and $\vec {A}^c$ is
an Eulerian digraph.
\end{theorem}

The connection between the circuit partition polynomial of a digraph
and the Tutte polynomial of a planar graph $G$ is through the oriented
medial graph $\vec{G}_{m}$ described in the previous chapter.
Martin~\cite{Mar77} proved the following, which we extend to the
circuit partition polynomial via (\ref{jm}).

\begin{theorem}\label{Tutte-Martin}

Let $G$ be a connected planar graph, and let $\vec {G}_m$ be its oriented
medial graph. Then relationships among the Martin polynomial, circuit
partition polynomial, and Tutte polynomial are:
\[
j(\vec {G};x)= x m(\vec {G}_m ;x+1) = xt(G;x+1,x+1).
\]
\end{theorem}

The proof of this theorem depends on a fundamental observation
relating deletion/contraction in $G$ with choices of configurations at
a vertex in an Eulerian graph state of $\vec {G}_m $, as illustrated
in Figure~\ref{Fig:TutteMartinfig}.  Theorems \ref{cppsplit} and
\ref{Tutte-Martin} combine to give the basis for many of the
combinatorial interpretation of the Tutte polynomial along the line $y
= x$ described in the previous chapter.  For more details, see
Martin~\cite{Mar77, Mar78}, Las Vergnas~\cite{Las79, Las83, Las88},
Bollob\'as~\cite{Bol02}, and also~\cite{E-M98, E-M00,E-M04a,
  E-M04b}.

 \begin{figure}[hbtp]
     \begin{center}

         \includegraphics[width=0.9\textwidth]{TutteMartinfig.pdf}
       \caption{An edge $e$ in a planar graph $G$, with the
         corresponding vertex $v$ in the oriented medial graph
         $\vec{G}_m$ (dotted edges).  Deleting $e$ corresponds to one
         possible configuration at $v$ in an Eulerian graph state of
         $\vec{G}_m$, while contracting $e$ corresponds to the
         other}\label{Fig:TutteMartinfig}
     \end{center}
   \end{figure}

Evolving from the relation between the Tutte and Martin polynomials is
the theory of isotropic systems, \index{isotropic system} which
unifies essential properties of 4-regular graphs and pairs of dual
binary matroids. A series of papers throughout the 1980's and 1990's,
including work by Bouchet \cite{Bou87a}, \cite{Bou87b}, \cite{Bou88},
\cite{Bou89}, \cite{Bou91},\cite{Bou93}, as well as Bouchet and Ghier
\cite{BG96}, and Jackson \cite{Jac91}, significantly extends the
relationship between the Tutte polynomial of a planar graph and the
Martin polynomial of its medial graph via the theory of isotropic
systems.

 \subsection{Interlace Polynomial}

In \cite{ABS00}, Arratia, Bollob\'as and Sorkin
defined a one-variable graph polynomial motivated by questions
arising from DNA sequencing by hybridization
addressed by Arratia, Bollob\'as, Coppersmith and Sorkin in
\cite{ABCS00}, an application we will return to in
Section~\ref{sec:applications}.
 In \cite{ABS04b}, Arratia, Bollob\'as, and Sorkin defined a
two-variable interlace polynomial, \index{interlace polynomial} and
showed that the original polynomial of
\cite{ABS00} is a specialization of it, renaming the original one-variable
polynomial as the vertex-nullity interlace polynomial
\index{vertex-nullity interlace polynomial}
\index{polynomial!vertex-nullity} due to its
relationship with the two-variable generalization.

Remarkably, despite very different terminologies, motivations and
approaches, the original vertex-nullity interlace polynomial of a
graph may be realized as the Tutte-Martin polynomial
\index{Tutte-Martin polynomial}\index{polynomial!Tutte-Martin} of an
associated isotropic system (see Bouchet
\cite{Bou05}). For exploration of this relationship, see the works
mentioned in Subsection \ref{sec:cpp}, as well as Aigner \cite{Aig00},
Aigner and Mielke \cite{AM00}, Aigner and van der Holst \cite{AvdH04},
Allys \cite{All94}, and also Bouchet's series on multimatroids
\cite{Bou97,Bou98a,Bou98b,Bou01}.

Both the vertex-nullity interlace polynomial of a graph and the
two-variable interlace
polynomial may be defined recursively via a
pivot operation. \index{pivot operation} This pivot is defined as
follows.  Let $vw$ be an edge of a graph $G$, and let $A_v$,
$A_w$ and $A_{vw}$ be the sets of vertices
in $V(G)\setminus \{v,w\}$
adjacent to $v$ only, $w$ only,
and to both $v$ and $w$, respectively.  The pivot operation ``toggles"
the edges among $A_v$,  $A_w$ and $A_{vw}$, by deleting existing
edges and inserting
edges between previously non-adjacent vertices.
The result of this operation
is denoted $G^{vw}$.  More formally,  $G^{vw}$  has the same vertex
set as $G$, and edge
set equal to the symmetric difference $E(G)\Delta   S$, where $S$  is the
complete tripartite graph with vertex classes
$A_v$,  $A_w$ and $A_{vw}$. See Figure~\ref{Fig:pivotfig}.\\

 \begin{figure}[hbtp]
     \begin{center}

         \includegraphics[width=0.9\textwidth]{pivotfig.pdf}
       \caption{Pivoting on the edge $vw$. $A_{v}$,  $A_{w}$ and
         $A_{vw}$  are the  sets of vertices of $G$
         adjacent to $v$ only, $w$ only, and to both $v$ and $w$,
         respectively.  These sets are constant in all the diagrams.
         Vertices of $G$ adjacent to neither $v$ nor $w$ are omitted.  Heavy
         lines indicate that all edges are present, and dotted lines
         represent non-edges. Note interchange of edges and non-edges
         among $A_{v}$, $A_{w}$ and $A_{vw}$}\label{Fig:pivotfig}
     \end{center}
   \end{figure}

Also, $G^a$ is the {\em local complementation}
\index{local complementations} of $G$, defined
as follows. Let $N(a)$ be the neighbors of $a$, that is, the set
$\{w\in V: a {\text{ and }}w {\text{ are joined by an edge}}\}$.
The graph $G^a$ is equal to $G$ except
that

we ``toggle" the edges among the neighbors of $a$,
switching edges to non-edges and vice-versa.

\begin{definition}
Let $G$ be a graph of order $n$, which may have loops, but no multiple
loops or multiple edges.  The two-variable interlace polynomial may be
given recursively by $q(E_n)=y^n$ for $E_n$, the edgeless graph  on
$n\geq 0$ vertices, with
\[
q(G)=q(G- a)+q(G^{ab}- b)+((x-1)^2-1)q(G^{ab}- a- b), \\
\]
\noindent
for any edge $ab$ where neither $a$ nor $b$ has
a loop, and
\[
q(G)=q(G- a)+(x-1)q(G^a- a), \\
\]
\noindent
for any looped vertex $a$.
\end{definition}

Alternatively, the interlace polynomial has the following generating
function representation.

\begin{definition} Let $G$ be a graph of order $n$, which may have
  loops, but no multiple loops or multiple edges.  Then the
  two-variable interlace polynomial may be given by

\begin{equation*}
  q(G;x,y)=\sum_{S\subseteq
  V(G)}(x-1)^{r(\left. G \right|_S)}(y-1)^{n(\left. G
  \right|_S)},\end{equation*}
\noindent
where $r(\left. G \right|_S)$ and $n(\left. G
\right|_S)=|S|-r(\left. G \right|_S)$ are, respectively,
the ${\mathbb F}_2$-rank and
nullity of the adjacency
matrix of $\left. G \right|_S$, the subgraph of $G$ restricted to $S$.
\end{definition}

\begin{definition}\label{vertexnullity}
The vertex-nullity interlace polynomial is defined recursively as:
$$
q_N(G;x)=
\begin{cases}
x^n {\text{ if }}G=E_n, {\text{ the edgeless graph on $n$ vertices}}\\
q_N(G- v;x)+q_N(G^{vw}- w;x) {\text{ if }}vw\in E(G).
\end{cases}
$$

\end{definition}

This polynomial was shown to be well defined by Arratia, Bollob\'as,
and Sorkin for all simple graphs in \cite{ABS00}, and then was shown
in \cite{ABS04b} to be a specialization of the two-variable interlace
polynomial as follows.

\begin{equation*}
q_N(G;y)=q(G;2,y)=\sum_{W\subseteq V(G)}(y-1)^{n(\left. G \right|_W)}.
\end{equation*}

An equivalent formulation for $q_N(G;x)$  for simple graphs is given
by Aigner and van der Holst in
\cite{AvdH04}.

A somewhat circuitous route through the circuit partition polynomial
relates the vertex-nullity interlace polynomial to the Tutte
polynomial. \index{Tutte polynomial}\index{polynomial!Tutte} First
recall that a {\em circle graph}\index{circle graph} on $n$ vertices
is a graph $G$
derived from a chord diagram.

Two vertices $v$ and $w$ in $G$ share an edge if and only if their
corresponding
chords intersect in the chord diagram. Note that $G$ is necessarily simple.

For circle graphs, the vertex-nullity
interlace polynomial and the circuit partition polynomial
are related
by the following theorem, noting that
although $\vec{G}$ may be a multigraph, $H$ is necessarily
simple.

\begin{theorem}(Arratia, Bollob\'as and Sorkin \cite{ABS00}, Theorem
  6.1).\label{A}
If $\vec{G}$  is a $4$-regular Eulerian digraph, $C$ is any Eulerian
circuit of $\vec{G}$, and  $H$ is the circle graph of the chord diagram
determined by $C$,
 then $j(\vec{G};x)=xq_N(H;x+1)$.
\end{theorem}

This now allows
us to relate the vertex-nullity interlace polynomial
to the Tutte polynomial, \index{Tutte polynomial}\index{polynomial!Tutte}
a relation proved in \cite{E-MS07} and also observed by Arratia,
Bollob\'as and Sorkin at the end of
Section $7$ in \cite{ABS04b}.

\begin{theorem}\label{B}
If $G$ is a planar graph, and $H$ is the circle graph of some Eulerian
circuit of  $\vec{G}_m$,
then $q_N(H;x)=t(G;x,x)$.
\end{theorem}

\begin{proof}
By Theorem~\ref{A}, $j(\vec{G}_m;x)=xq_N(H;x+1)$, but
recalling that the circuit partition and Martin polynomials are
simple translations of each other,
we have from Theorem~\ref{Tutte-Martin} that
$j(\vec{G}_m;x)=xm(\vec{G}_m;x+1)$, and hence
$q_N(H;x)=m(\vec{G}_m;x)=t(G;x,x)$.
\end{proof}

The interlace polynomial has generated further interest and other
applications in
Balister, Bollob\'as, Cutler, and Pebody \cite{BBCP02},
and Balister, Bollob\'as, Riordan, and Scott \cite{BBRS01}, Glantz
and Pelillo \cite{GP06}, Ellis-Monaghan and Sarmiento \cite{E-MS07}.


TITLE: A typo-free detail oriented prime conjecture
QUESTION [4 upvotes]: I've grossly overstated things in my two posts before the last one. Thank you for providing references that have returned me to reality.

Conjecture For arbitrary integers $\ 0 \le k \le m\ $ there exists
integer $\ n\ge m\ $ such that for every natural number $\ s\ $ at
least one of the numbers
$$\ p(x+s+1)-p(x+s)\ \ne\ p(x+1)-p(x) $$
where $\ k\le x < n$.

Here, $\ p(0)=2, p(1)=3,\ldots\ $ is the strictly increasing sequence of all prime numbers.

An assembler-like equivalent formulation:
Conjecture'
$$ \forall_{m\in\mathbb Z_{\ge 0}}\,\forall_{k\in 0..m}\,
\exists_{n\in\mathbb Z_{\ge m}}\,\forall_{s\in\mathbb N}\,
\exists_{x\in k..n\!-\!1} $$
$$ p(x+s+1)-p(x+s)\ \ne\ p(x+1)-p(x) $$

Here (Perl notation),

$$\ u..v\ :=\ \{x\in\mathbb Z:\ u\le x\le v\} $$

REPLY [0 votes]: NOTATION:
$u_0\ \ldots\ u_n\,\ $ and $\ v_0\ \ldots\ v_n\,\ $ are arbitrary finite strictly increasing sequences of non-negative integers, of the same sequence's length $\ n+1$.
$p(0)=2, p(1)=3, \ldots\ $ is the strictly increasing sequence of all
(consecutive) primes.
$ p(u_0)\ \ldots\ p(u_n)\,\ $ and $\,\ p(v_0)\ \ldots\ p(v_n)\ $ are
arbitrary finite strictly increasing sequences of primes (not necessarily
consecutive), where the length of the two sequences is the same, namely
$\ n+1.$
The goal: We will see that under certain additional assumptions, the
above two finite sequences are identical; in particular when one of them is assured to exist as an extension of a different shorter sequence.

Wojowu has posted his answer in the Q&A style. He deserves a more rounded presentation. Let me be the first one to do it. It'll be but a presentation. The results are exclusively due to Wojowu (Wojciech Wawrów).
Theorem 1 Assuming our NOTATION, if there exists a prime $\ q\ $
such that for every integer $\ x\ $ there exists at least one integer (index)
$\ a(x)\ $ such that
$$ p(u_{a(x)})\ \equiv x\ \mod q $$
and if there exists an integer $\ s\in\mathbb Z\ $ such that
$$\forall_{t=0}^n\quad p(v_t) = p(u_{s+t}) $$
and
$$ \forall_{t=1}^n\quad p(v_t)-p(v_{t-1})\ =\ p(u_t)-p(u_{t-1}) $$
then $\ s=0$.
Remark The last assumption can be written equivalently as
$$ \forall_{t=1}^n\quad p(v_t)-p(u_t)\ =\ p(v_{t-1})-p(u_{t-1}) $$
Proof (of Theorem 1) Let the assumptions of the theorem hold. By the above Remark,
for every integer $\ x\ $ there exists at least one integer (index)
$\ b(x)\ $ such that
$$ p(v_{b(x)})\ \equiv x\ \mod q $$
The terms in each prime sequence that are $\ 0 \mod q\ $
are simply equal to $\ q.\ $ If integer  $\ s\ $ were different from $\ 0\ $
then the same prime $\ q\ $ would appear twice -- $\ s\ $ places apart -- in the increasing sequence of all primes; that would be a contradiction.
End of Proof

More NOTATION: Given integers $\ 0\le m\le n,\ $ prime sequence
$ p(u_0)\ \ldots\ p(u_n)\,\ $ is called to be the minimal $n$-extension
of a strictly increasing sequence $ p(u_0)\ \ldots\ p(u_m)\,\
 \Leftarrow:\Rightarrow$
$$ \forall_{k=m+1}^n\quad u_k=u_m+k-m, $$

Theorem 2 For every strictly increasing finite prime sequence $ p(u_0)\ \ldots\ p(u_m)\,\ $ there exists a minimal extension $ p(u_0)\ \ldots\ p(u_n)\,\ $ which is lonely, meaning that it is the only prime sequence $ p(v_0)\ \ldots\ p(v_n)\,\ $ such that there exists an integer $\ s\in\mathbb Z\ $ such that
$$\forall_{t=0}^n\quad p(v_t) = p(u_{s+t}) $$
and
$$ \forall_{t=1}^n\quad p(v_t)-p(v_{t-1})\ =\ p(u_t)-p(u_{t-1}). $$
Proof For $n$ large enough all residue classes \mod p(u_0) appear
in $ p(u_0)\ \ldots\ p(u_n)\,\ $ (by Dirichlet Theorem). This, by Theorem 1,
makes sequence $ p(u_0)\ \ldots\ p(u_n)\,\ $ lonely. End of Proof


TITLE: Prime numbers and divisibility related problem
QUESTION [1 upvotes]: If $p, q$ are primes such that $p\nmid (n-1)$, but $p \mid (n^q-1)$, then show that $q \mid p-1$.
My approach:
Given $p \nmid n-1$, but $p \mid (n^q-1)$ implies $p \mid (n^{q-1}+n^{q-2}+...+n+1)$
Say $ (n^{q-1}+n^{q-2}+...+n+1)= kp$. Now if we assume, $p \mid n$, it forces to have $p \mid 1$, implying $p=1$. Then our proof is obviously complete.
If $p \nmid n$, then from Fermat's theorem, we have:   $$ n^{p-1}=1+k_1p$$
So, again, in the question it is given that $$n^{q}=1+k_2p$$
Let us assume there exists some $x$ such that  $n^{x}=1+k_3p \Rightarrow k_3p=(n-1) (n^{x-1}+n^{x-2}+...+n+1)$ .  Again $p \nmid (n-1)$ implies $p \mid  (n^{x-1}+n^{x-2}+...+n+1)$
if $x<q$,
we have $$ (n^{q-1}+n^{q-2}+...+n+1)= kp$$
$$\Rightarrow (n^{q-1}+n^{q-2}+...+n^x)+(n^{x-1}+n^{x-2}+...+n+1)=kp$$
Now  $p \mid  (n^{x-1}+n^{x-2}+...+n+1)$  implies, $p \mid (n^{q-1}+n^{q-2}+...+n^x)$, which is not possible as $p \nmid n$ and $p \mid (n^{q-1}+n^{q-2}+...+n+1)$
If $x>q$
We have $$ n^{x-1}+n^{x-2}+...+n+1= k_3p$$
$$ \Rightarrow (n^{x-1}+n^{x-2}+...+n^q)+(n^{q-1}+n^{q-2}+...+n+1)= k_3p$$
$$  \Rightarrow (n^{x-1}+n^{x-2}+...+n^q)=k_4p$$
Again $p \nmid n$ and $p \mid (n^{q-1}+n^{q-2}+...+n+1)$  force to have $x$ is a multiple of $q$.
If we take $x=p-1$, our proof is complete.
Is it correct?

REPLY [3 votes]: Let $r$ be minimal among all natural numbers $k$ such that $$n^k\equiv 1\pmod{p}$$
The number $r$ is usually called order of $n$ modulo $p$.

Lemma If $n^s\equiv 1\pmod{p}$ then $r\mid s$.
Proof  Write $s=l\cdot r+o$ where $o$ is remainder when $s$ is divided by $r$, so $0\leq o<r$.
Then we have $$1\equiv n^s\equiv (n^r)^l\cdot n^o \equiv n^o \pmod p$$
If $o>0$ then we have smaller number than $r$ such that $n^o\equiv 1\pmod{p}$
thus $o=0$.

Back to the problem: Since $n^q\equiv 1\pmod p$ thus by lemma $r\mid q$. So $r=1$ or $r=q$. But $r$ can not be $1$, since if $r=1$ we get $p\mid n-1$ which is not true. So $r=q$.
Now by Fermat little theorem we have $n^{p-1}\equiv 1\pmod{p}$, so by lemma we have also $r\mid p-1$ and thus $q\mid p-1$.