text:
# bijection = bijection + bijection on symmetric integer intervals

Given a bijection $f:\mathbb Z \to \mathbb Z$ where $\mathbb Z$ is the set of all integers, does there always exist two bijections $g:\mathbb Z \to \mathbb Z$ and $h:\mathbb Z \to \mathbb Z$ which satisfy $f(n) = g(n) + h(n), ~ \forall n \in \mathbb Z$ ?

Evidently it does while $\mathbb Z$ is replaced with the set of all rational numbers $\mathbb Q$, since $f(q) = 2f(q) - f(q), ~ \forall q \in \mathbb Q$. Nevertheless, $2f$ doesn't maps $\mathbb Z$ onto $\mathbb Z$, thus it's not a bijection on $\mathbb Z$; therefor we need a new construction for the $\mathbb Z$ case.

Firstly we note that   $0 = 0 + 0$   and \begin{align*} 1 &= (-2) + 3, &\qquad -1 &= 2 + (-3),\\ 2 &= 3 + (- 1), &-2 &= (-3) + 1,\\ 3 &= 1 + 2, &-3 &= (-1) + (-2). \end{align*}

It's easy to show that any bijections on the symmetric integer interval $[-3,3]$ can be represented as a sum of two bijections; or equivalently, all integers $a \in [-3,3]$ can be represented as a sum of two others, i.e., $a = b + c$ where $b, c \in [-3, 3]$, while $a,b,c$ exhausted the integer interval $[-3,3]$ respectively, and keeps $0 = 0 + 0$. For convenience, let's denote this fact as $[-3,3] = [-3,3] + [-3,3]$.

Suppose now we have $[-m, m] = [-m, m] + [-m, m]$, then we may obtain $$[-m + aL, ~ m + aL] = [-m + bL, ~ m + bL] + [-m + cL, ~ m + cL],\qquad L = 2m+1,$$ where $a,b,c \in [-n,n]$ for some positive integers $n$, provided $a = b + c$. Well, if $a,b,c$ form a representation, say, $[-n,n] = [-n,n] + [-n,n]$, then we may get a "larger" representation $$[-m - nL, ~ m + nL] = [-m - nL, ~ m + nL] + [-m - nL, ~ m + nL], \qquad L = 2m+1,$$ through the repeatedly use of "small" representations; and obviously, the larger representation "contains" the small representation as a "subrepresentation", since $0 = 0 + 0$. From now on, we may construct a representation $\mathbb Z = \mathbb Z + \mathbb Z$ by induction, start from $[-3,3] = [-3,3] + [-3,3]$. Thus we've proved that any bijections on $\mathbb Z$ can be represented as a sum of two bijections on $\mathbb Z$.

Now a problem rises:

for any integers $n > 2$, is there always a representation $[-n, n] = [-n, n] + [-n, n]$ ?

Note that by our means of "representation", $0 = 0 + 0$ is required; otherwise it's trivial; note also the above approach we've used for resolving the "$\mathbb{Z}$-representation problem" can't reach all cases.

-

Observation: It is sufficient to resolve the question for $f(n)=n$.

Proof idea: If $n=g(n)+h(n)$ for all $n$, then $f(n)=g(f(n))+h(f(n))$. Conversely, if $f(n)=g(n)+h(n)$ then $n=f(f^{-1}(n))=g(f^{-1}(n))+h(f^{-1}(n))$.

So, if some $f$ can be decomposed into two bijections $h$ and $g$, then every $f$ can be decomposed.

So resolving this question amounts to finding a permutation $g$ of $\mathbb{Z}$ for which $n \mapsto g(n)-n$ is also a permutation. Such permutations are called orthomorphisms.

UPDATE: I asked both Ian Wanless and Tony Evans about this, and they simultaneously pointed out that the existence of such an orthomorphism was proved in:

MR0040293 (12,670f) Bateman, P. T. A remark on infinite groups. Amer. Math. Monthly 57, (1950). 623–624. 20.0X

So we can conclude that, yes, it's always possible.

-
Thanks very much. But note that my question isn't about the case of the abelian group $\mathbb Z$, infact I've proved in above that there are orthomorphisms of $\mathbb Z$ by induction. Indeed my question is: for any $n>2$, is there always an "orthomorphism" of the integer interval $[−n,n]$, which keeps 0 as it's fixed point? Though $[-n,n]$ may not be a group, I think you know the mean of "orthomorphsim" in this context. By the way, sorry for my poor english. –  Triple.J Dec 13 '10 at 7:41
Hmm... I'm not 100% sure I understand. Perhaps you're after orthomorphisms of $Z_{2n+1}$ which always exist (the simplest examples are linear orthomorphisms, e.g. take $i \mapsto 2i \pmod {2n+1}$). Then instead use the reduced residue system {-n,...,n}. –  Douglas S. Stones Dec 13 '10 at 7:54
Yes, I know orthomorphisms of $\mathbb Z_{2n+1}$ always exist, and of $\mathbb Z_{2n}$ always dosen't exist. So if I ristrict my question on the residue system {-n,...,n} (mod 2n+1), we can get an orthomorphism easily; but how to transform these orthomorphisms to the orthomorphisms of integer intervals [-n,n], is not so easy. –  Triple.J Dec 13 '10 at 8:35
Okay, I think I understand now. The first question is the motivation, rather than the question you want answered. Give me a moment, I'm just fleshing out the details of a construction. In the meantime, could you tell me if you are insisting on having 0=0+0 as one of the equations? –  Douglas S. Stones Dec 13 '10 at 9:47
Hmm... I prepared a nice answer to the question, then realised you did require 0=0+0. Is there any motivation for this restriction, aside from wanting to make the question more difficult? –  Douglas S. Stones Dec 13 '10 at 10:34

Firstly, consider the case when we are not obliged to have the equation 0=0+0.

The question becomes: given $n \geq 1$ does there exist two permutations $g,h$ of $A:=\{-n,-n+1,\ldots,n\}$ such that $n=g(i)+h(i)$ where addition is addition over the integers (and therefore is not closed on $A$).

We can interpret an instance of this question as a set of $n$ non-attacking semiqueens on an $(2n+1) \times (2n+1)$ chessboard (with rows and columns indexed by $A$) such that no semiqueen is in cell $(i,j)$ whenever $i+j \not\in A$. [semiqueens move up-and-down, left-and-right and along one diagonal]

So the instance you cite above is illustrated by this figure:

Just as with orthomorphisms of $\mathbb{Z}_n$ we can find linear constructions:

So we can take the equations

• $0=n+(-n)$, $1=(n-1)+(-n+2)$, up to $n=0+n$, along with
• $-1=-n+(n-1)$, $-2=(-n+1)+(n-3)$, up to $-n=-1+(-n+1)$.

So, g(n) takes the values $\{n,n-1,\ldots,0\}$ in the first step and $\{-n,-n+1,\ldots,-1\}$ in the second and h(n) takes the values $\{-n,-n+2,\ldots,n\}$ in the first step and $\{n-1,n-3,\ldots,-n+1\}$ in the second step. Hence both g and h are bijections of $A$, and we can clearly see that $i \mapsto g(i)-h(i)$ is also a bijection.

So, yes, I guess it is easy in this case.

Warning: Although the motivation for this question was to prove the existence of an orthomorphism of $\mathbb{Z}$, this is insufficient to prove it.

Now lets consider the case when the equation 0=0+0 is required. We can generate some small random examples, for example, in GAP.

RandomPermutationList:=function(n)
local A,i,j,temp;
A:=List([1..n],k->k);
i:=n;
while(i>=2) do
j:=Random([1..i]);
if(j<i) then
temp:=A[i];
A[i]:=A[j];
A[j]:=temp;
fi;
i:=i-1;
od;
return A;
end;;

TripleJQuestion2:=function(n)
local A,B,p,q;
A:=Concatenation([-n..-1],[1..n]);
B:=List([1..2*n+1],i->-n-1+i);
while(true) do
q:=RandomPermutationList(2*n);
p:=Concatenation(List([1..n],i->A[q[i]]),[0],List([1..n],i->A[q[n+i]]));
if(Set(List([1..2*n+1],i->p[i]-B[i]))=B and p[n+1]=0) then return p; fi;
od;
return fail;
end;;

This was successful for $4 \leq n \leq 8$:

So, combined with the fact that there are many orthomorphisms of $\mathbb{Z}_n$, it seems very likely that an instance of the desired construction exists for all $n \geq 3$.

But, continuing further (i.e. finding a constructions for all $n \geq 3$) could require considerable effort. If you're really keen on resolving this problem, you could generate lots of random examples, and hope you could generalise enough of them to cover all $n \geq 3$. But why would you want to do this? It's not likely to give a surprising result, and it seems to be a fairly contrived problem (yes, the problem is harder if we assume the equation 0=0+0 is required, but why would anyone be interested in this problem?). And also, unless you somehow build these constructions recursively, you're probably not going to solve the orthomorphisms of $\mathbb{Z}$ existence question.

-
Thank you, Stones. Actually this problem is not so important, it's just a math puzzle. –  Triple.J Dec 13 '10 at 12:23

This question is ancient (for MSE), but I feel compelled to point out that an orthomorphism for $\mathbb Z$ is not even this complicated to construct; in fact it is amenable to a just-do-it proof:

As Douglas observed we can assume $f(n)=n$ without loss of generality. Now construct $g$ and $h$ in stages. In each stage we have already selected values of $g(n)$ and $h(n)$ at finitely many $n$. For each $k\in \mathbb Z$, according to your favorite enumeration of $\mathbb Z$, do:

1. If $g(k)$ and $h(k)$ are not yet defined, then define $g(k)=i$ and $h(k)=k-i$, where $i$ is prettiest integer such that $g$ does not already hit $i$ and $h$ does not already hit $k-i$.

(This assumes that prettiness well-orders $\mathbb Z$, but since that is the only demand on the concept, the reader will be able to select a suitable aesthetic here).

2. If $g$ does not yet hit $k$, then define $g(i)=k$ and $h(i)=i-k$ where $i$ is the prettiest integer such that $g(i)$ and $h(i)$ are still undefined and $h$ does not already hit $i-k$.

3. As 2, but mutatis mutandis with $g$ and $h$ swapped.

After $\omega$ many steps, $g$ and $h$ are total (because of step 1), surjective (because of step 2 and 3, respectively), and injective (by construction because only values that are not already hit will be chosen).

Before iterating over the $k$s we can select finitely many (consistent) values for $g$ and $h$ just as we please -- so achieving $0=0+0$ if one wants that is trivial.

-


text:
Acceleration due to gravity

# acceleration due to gravity

April 1, 2018
April 1, 2018

## Acceleration due to gravity

Today post is all about acceleration due to gravity, In this post you will learn, what is acceleration due to gravity ? How its value is 9.8 m/s², acceleration due to gravity has fixed value, Why and how its value varies at different point location and due to Earth rotation, How acceleration due to gravity is a gravitational field, You will learn all concepts about of acceleration due to gravity, so lets start.

### What is acceleration due to gravity ?

Gravity is a force with which Earth attract every other object towards it centre. Earth has created this gravity around its surrounding. This property of the Earth is due to heavy mass of the Earth, Because compare to the Earth mass, all other objects masses are small near its surrounding, Hence all other masses falls towards centre of the Earth.

 Acceleration due to gravity
From the figure above Earth is pulling you with force mg, you also know from the law of gravitation force between two masses, you can refer previous post for  the value of force between Earth and man shown in figure will be F= GMₑm/(Rₑ + h)²
here value of h is very small compare to radius of Earth Rₑ so h is neglected,
Hence F =  GMₑm/Rₑ² , Now both force will be equal as per statement.
GMₑm/Rₑ²  = mg   or  g =    GMₑ/Rₑ² , this is important formula where G is universal gravitational constant G = 6.67×10⁻¹¹ Nm²/kg², Rₑ is radius of Earth approx Rₑ = 6400 km,
Rₑ = 6.4×10⁶ m , Mₑ is mass of Earth approx Mₑ = 6×10²⁴ kg .
Now after putting all the values in above formula g =  6.67×10⁻¹¹x6×10²⁴/(6.4×10⁶)²
g  = 9.8 m/s², remember this value of g is near the earth surface only.
Suppose if h is very high then you can’t neglect value of h, so in this case g =  GMₑ/(Rₑ + h)², Now as the value of h increases then value of g will decreases, So you can’t say value of g is constant.
On increasing the value of h from the surface of the Earth value of g will decrease. You will see how the value of g decreases as moving from the surface of the Earth in this post later.
Now see below picture and find weight.

 Weight at Mars

As from the question, You have to find the weight of same man at Mars, his weight is given at Earth is 70 N.
Interesting now scientist are planing to move to Mars booking are going on for Mars journey, But at present very costly in million \$, which is not possible for a average men.
So you should know what will be your weight at Mars ?
You know weight at Earth is mg w = mg, now weight at Mars will be w’ = mg’ here g will be different from Earth so take as (g’).
w’/w  = mg’/mg  = g’/g  ( You know that mass is not changed anywhere in the universe )

w’/w  = g’/g   you have calculated g value at Earth surface g  = GMₑ/Rₑ² , Similarly for Mars
g’  = GMₘ/Rₘ²  put this value of g and g’ in the expression.

w’/w  = g’/g  =  (GMₘ/Rₘ² )/(GMₑ/Rₑ²)  =  (Mₘ/Mₑ)x(Rₑ/Rₘ)²  now from question given that Mars mass is 10 times less than Earth so Mₑ = 10Mₘ and radius of Mars is 1.8 times less than radius of Earth Rₑ = 1.8Rₘ , now put this values in above expression you will get.
w’/w  = (Mₘ/Mₑ)x(Rₑ/Rₘ)²   =  (Mₘ/10Mₘ)x(1.8Rₘ/Rₘ)² =  3.24/10 = 0.324
w’/w  =  0.324   =  w’ = wx0.324 = 70x0.324  = 22.68 N .
Hence weight at Mars for same person will be w’ = 22.68 N  which is approximately  3 times less than weight at Earth .
So you will feel less attracted at Mars, you will feel more free. At moon your weight will be 6 times less than weight at the Earth, So acceleration due to gravity varies.

### Variation in gravity (g) as you go above Earth surface.

 Variation in g above Earth Surface
From the above figure mg’  = GMₑm/(Rₑ+h)²  or  g’  = GMₑ/(Rₑ+h)²  see as you will go above the Earth surface, value of h will increase and hence value of g’ will decrease, and it is also logical that as you will be far distance from Earth surface gravity g field effect will be less on you. So it is clear that above the Earth surface gravity g will decrease.

Now compare the value of g’ with original value of g at Earth surface, So you know the value of g at Earth surface g  =  GMₑ/Rₑ²  now from here you can write GMₑ = gRₑ²  now put this value in the new g’ expression .

g’  = GMₑ/(Rₑ+h)²   = gRₑ²/(Rₑ+h)²  =  g/(1+h/Rₑ)²  after arranging the expression you can
So in terms of height, you can write new value of g’ like this.

g’  =   g/(1+h/Rₑ)²  now it is important ,if the height from the earth surface value of h is about 1km up to 100 km value of g’ will be nearly g, So no effect of gravity value is change near the Earth surface within this range.

But when you will go up to 500 km and more then value of g’ will change and its effect will seen. Now i will make some assumption see below
If  h<< Rₑ   you can write  g’  = g(1+h/Rₑ)⁻²  now you know from binomial expansion
(1+x)⁻ⁿ  = (1-nx)  if   x<<1 font=”” h=”” of=”” similarly=”” value=””>Rₑ <<1 span=””>
So you can write g’  = g(1-2h/Rₑ) . See below the question.

Q Find the height above the Earth surface, where gravity ‘g’ drops to 25% of g at surface .

Solution for any numerical question, first you should understand well the question then you relate the given parameter So as from the question it is given that new value of gravity g’ 25% of at Earth surface hence  g’  = gx25/100 =  g/4   (1)

You also know that  g’  =  g/(1+h/Re)²    (2)
hence equate expression (1) and (2) so you can write .
g/(1+h/Re)²  = g/4  or    (1+h/Re)²  = 4 or  (1+h/Re)  = 2
h/Re  = 2-1   = 1  or  h  = Re  So at radius of Earth height value of gravity g’ will be 25% of Earth surface.

### Variation in gravity as you go below the Earth surface.

 Variation of gravity g inside the Earth
From figure you are h depth inside the Earth and now you are r distance from the centre of the Earth.
Now from the law of gravitation you can write mg’  = GM’m/r²  understand the concept, the mass of the Earth with which now Earth will attract you will be M’ not Mₑ, only inside circle mass will attract, outer mass will not attract you, Because due to Gauss theorem in a shell gravitational field is zero.

This is also important outer shell mass will not pull you out side because gravitational field is zero inside a shell whether it is solid or hollow in both the cases gravitational field will be zero inside a shell.

Now from expression mg’  = GM’m/r²  or g’  = GM’/r²
Suppose Earth is a uniform sphere means equal mass distribution everywhere but it is not like that just we assume.

now the density of Earth is 𝛒  everywhere assumption hence M’ = volume x𝛒.  =  4𝛑r³/3x𝛒
M’  = 4𝛑r³/3x𝛒
g’  = GM’/r²  =  Gx4𝛑r³/3x𝛒/(r²) =  g’ =  G𝛒4𝛑r/3  here you see g’ is directly proportional to r its mean that as you will come from the centre of the Earth towards the surface of the Earth value of r will increase and hence value of g’ will increase.
At the surface of Earth it will be maximum.

Now you can calculate the density of Earth   𝛒 = mass/volume = Me/4𝛑Rₑ³/3 put this value in above equation  g’ =  G𝛒4𝛑r/3 = GxMe/4𝛑Rₑ³/3x4𝛑r/3 =  GMₑr/Rₑ³  here it is also clear that g’ is directly proportional to r.
You remember for always g = GMₑ/Rₑ² at the surface of Earth this is standard formula use everywhere in this topic, So from here G = gRₑ²/Mₑ , now put this value in g’ expression

g’  =   GMₑr/Rₑ³  = (gRₑ²/Mₑ)x(Mₑr/Rₑ³ )  =  (g/Rₑ)r or  g’   =  (g/Rₑ)r

Hence it clearly show as you will go inside the Earth surface value of gravity g will decrease  you have seen here g’ directly proportional to r.
Now you have to write this formula in terms of h so for this see the figure, I can write
Rₑ = r+h  or r   = Rₑ-h, put this value in above expression
g’   =  (g/Rₑ)r  =  (g/Rₑ)x(Rₑ-h)  = g(1-h/Rₑ)  or  g’  = g(1-h/Rₑ) .

Now one question are generally asked, what will value of gravity g at the centre of the Earth ?
So you are looking the formula  g’  = g(1-h/Rₑ)  at the centre of Earth h =  Rₑ hence g’ =0

Hence it is very much clear that at the centre of Earth g’ will be zero, and as move from the centre it will increase and at the surface it will be maximum g’ = g = GMₑ/Rₑ², now from surface to above height again value of g’ will decrease, you have already seen above.

#### Variation of acceleration due to gravity g with distance

See below the graph plotted variation of gravity with respect to distance, here you can easily see how value of g is changing with respect to distance.

 Variation of gravity g with distance

#### Variation in gravity g due to Earth rotation

Due to rotation of Earth value of g decreases but its value is very small due to angular velocity value is very small 𝛚  = 2𝛑/T = 2×3.14/(24x60x60) = 6.28/86400 = 7.28×10⁻⁵ rad/s

Every point on the Earth surface will have different circle of rotation, and due to centrifugal force on body, the effective value of g will decrease.
Important point due to rotation, effective g is not along the centre of the Earth, it will deviate slightly from the centre of the Earth.

After calculation g effective value will be g’ =  (g-Rₑ𝛚²cos²ϴ) now at equator put ϴ =0 then
g’ =  (g-Rₑ𝛚²) , now at pole  ϴ = 90⁰  So g’ = g. refer below picture.

 Variation of gravity due to Earth rotation
The reason of gravity g different at pole and equator is due to rotation of the Earth as you have seen above.
Hence finally you have seen that gravity g varies above the Earth surface, inside the Earth and due to rotation of the Earth, In all the cases gravity g decreases, at the centre of Earth g value is zero and at the surface of the Earth maximum g = 9.8 m/s²  , not a constant value.

I hope you have enjoyed learning acceleration due to gravity .I will continue post with more hidden concepts, I want Your feedback, comment, likes and shares, Thanks for sharing, learn and grow.

Dated 23rd Dec 2018.

format: plain


text:
Polynomials with roots in convex position - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T20:46:22Z http://mathoverflow.net/feeds/question/26799 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26799/polynomials-with-roots-in-convex-position Polynomials with roots in convex position Roland Bacher 2010-06-02T08:21:03Z 2010-06-02T10:18:29Z
Let $\mathcal P_n$ denote the set of all monic polynomials of degree $n$ with real or complex coefficients such that $P\in\mathcal P_n$ if for all $k\in\lbrace 0,1,\dots,n-2\rbrace$ the $n-k$ roots of $P^{(k)}=\left(\frac{d}{dx}\right)^kP$ are in strictly convex position (ie are the $n-k$ vertices of a convex polygon with $n-k$ extremal vertices).

The set $\mathcal P_n$ is clearly an open subset of all monic polynomials of degree $n$ over $\mathbb R$ or $\mathbb C$.

What is the geometry and topology of $\mathcal P_n$?

Facts:

(1) Over the reals, $\mathcal P_n$ has at least $2^{n-1}$ connected components: Indeed, consider a very fast decreasing sequence (I guess $n\longmapsto 1/((1+n)^{(1+n)^{1+n}})!$ will probably work) of strictly positive reals $\alpha_0>\alpha_1\dots$ and a sequence of signs $\epsilon_0,\epsilon_1,\dots\in\lbrace \pm 1\rbrace^{\mathbb N}$. Then
 $$x^n+\sum_{k=0}^{n-2}\epsilon_k\alpha_k x^k\in \mathcal P_n(\mathbb R)$$ and different choices of signs correspond to different connected components. Are there other connected components?

(2) Over the complex numbers, all the polynomials described in (1) are in the same connected component. Choosing $\epsilon_i$ on the complex unit circle suggests however that $\pi_1(\mathcal C_n)$ might be $\mathbb Z^{n-1}$ where $\mathcal C_n$ denotes the connected component of $x^n+\sum_{k=0}^{n-2}\alpha_kx^k$ in $\mathcal P_n(\mathbb C)$. Do we have $\mathcal C_n=\mathcal P_n(\mathbb C)$?

(3) We have the equalities $\mathcal P_{n-1}=\lbrace P'/n|P\in\mathcal P_n\rbrace$.


text:
# Math Help - Finding the derivative from an intergral.

1. ## Finding the derivative from an intergral.

I want to make sure I'm doing this right, and if I'm not, what I'm doing wrong. My notes on this section were terrible...

Find the derivative of the following function of x.

$F(x) = \int_2^{x^3}\cos(t^2)dt$

So $F'(x) = \cos(x^4)*2x$ , that's what's in my notes as far as I can tell... not sure why it's not the -sin(x^4) or something. Maybe I just wrote it down wrong.

Any help is appreciated.

2. $\frac{d}{dx}\int_{f(x)}^{g(x)}f(t)dt=g'(x)f(g(x))$

What I am trying to say is:

$\frac{d}{dx}\int_{2}^{x^{3}}cos(t^{2})dt=3x^{2}cos (x^{6})$


text:
### question 16

Hello,

why isn't the last remark correct? Isn't logistic regression faster if we have less input variables? (which is the case going from BoW to vector representation

thanks a lot

Page 1 of 1


text:
# zbMATH — the first resource for mathematics

A unified approach to Bermudan and barrier options under stochastic volatility models with jumps. (English) Zbl 1401.91533
Summary: Many financial assets, such as currencies, commodities, and equity stocks, exhibit both jumps and stochastic volatility, which are especially prominent in the market after the financial crisis. Some strategic decision making problems also involve American-style options. In this paper, we develop a novel, fast and accurate method for pricing American and barrier options in regime switching jump diffusion models. By blending regime switching models and Markov chain approximation techniques in the Fourier domain, we provide a unified approach to price Bermudan, American options and barrier options under general stochastic volatility models with jumps. The models considered include Heston, Hull-White, Stein-Stein, Scott, the 3/2 model, and the recently proposed 4/2 model and the $$\alpha$$-Hypergeometric model with general jump amplitude distributions in the return process. Applications include the valuation of discretely monitored contracts as well as continuously monitored contracts common in the foreign exchange markets. Numerical results are provided to demonstrate the accuracy and efficiency of the proposed method.

##### MSC:
 91G20 Derivative securities (option pricing, hedging, etc.) 91G80 Financial applications of other theories 93E11 Filtering in stochastic control theory 93E20 Optimal stochastic control
Full Text:
##### References:
 [1] Ballestra, L. V.; Pacelli, G., Pricing European and American options with two stochastic factors: a highly efficient radial basis function approach, J. Econ. Dyn. Control, 37, 6, 1142-1167, (2013) [2] Barraclough, K.; Whaley, R. E., Early exercise of put options on stocks, J. Finance, 67, 4, 1423-1456, (2012) [3] Bates, D. S., Jumps and stochastic volatility: exchange rate processes implicit in deutsche mark options, Rev. Financ. Stud., 9, 1, 69-107, (1996) [4] Battauz, A.; De Donno, M.; Sbuelz, A., Real options and American derivatives: the double continuation region, Manage. Sci., 61, 5, 1094-1107, (2014) [5] Broadie, M.; Detemple, J., Option pricing: valuation models and applications, Manage. Sci., 50, 1145-1177, (2004) [6] Broadie, M.; Detemple, J.; Ghysels, E.; Tores., O., American options with stochastic dividends and volatility: a nonparametric investigation, J. Econ., 94, 5392, (2000) [7] Broadie, M.; Glasserman, P., Pricing American-style securities by simulation, J. Econ. Dyn. Control, 21, 1323-1352, (1997) · Zbl 0901.90009 [8] Buffington, J.; Elliot, R., American options with regime switching models, Int. J. Theor. Appl. Finance, 05, 1-26, (2002) [9] Carr, P., Randomization and the American put, Rev. Financ. Stud., 11, 597-626, (1998) · Zbl 1386.91134 [10] Carr, P.; Jarrow, R.; Myneni, R., Alternative characterizations of American put options, Math. Finance, 2, 87-106, (1992) · Zbl 0900.90004 [11] Carr, P.; Sun, J., A new approach for option pricing under stochastic volatility, Rev. Deriv. Res., 10, 2, 87-150, (2007) · Zbl 1140.91353 [12] Carr, P.; Wu, L., What type of process underlies options? a simple robust test, J. Finance, 58, 6, 2581-2610, (2003) [13] Chockalingam, A.; Muthuraman, K., American options under stochastic volatility, Oper. Res., 59, 793-809, (2011) · Zbl 1233.91259 [14] Copeland, T.; Tufano, P., A real-world way to manage real options, Harv. Bus. Rev., 82, 3, 90-99, (2004) [15] Cox, J. C.; Ross, S. A.; Rubinstein, M., Option pricing: a simplified approach, J. Financ. Econ., 7, 229-263, (1979) · Zbl 1131.91333 [16] Da Fonseca, J.; Martini, C., The α-hypergeometric stochastic volatility model, Stoch. Process. Appl., 126, 5, 1472-1502, (2016) · Zbl 1345.60061 [17] Detemple, J., American-style derivatives: valuation and computation, (2005), CRC Press · Zbl 1095.91015 [18] Detemple, J.; Emmerling, T., American chooser options, J. Econ. Dyn. Control, 33, 1, 128-153, (2009) · Zbl 1170.91377 [19] Detemple, J.; Tian, W., The valuation of American options for a class of diffusion processes, Manage. Sci., 48, 7, 917-937, (2002) · Zbl 1232.91660 [20] Duffie, D.; Pan, J.; Singleton, K., Transform analysis and asset pricing for affine jump-diffusions, Econometrica, 68, 6, 1343-1376, (2000) · Zbl 1055.91524 [21] Fang, F.; Oosterlee, C., A novel pricing method for European options based on Fourier cosine series expansions, SIAM J. Sci. Comput., 31, 826-848, (2008) · Zbl 1186.91214 [22] Fang, F.; Oosterlee, C., Pricing early-exercise and discrete barrier options by Fourier-cosine series expansions, Numerische Mathematik, 114, 27-62, (2009) · Zbl 1185.91176 [23] Fang, F.; Oosterlee, C., A Fourier-based valuation method for Bermudan and barrier options under heston’s model, SIAM J. Finan. Math., 2, 439-463, (2011) · Zbl 1236.65163 [24] Feng, L.; Lin, X., Pricing Bermudan options in levy process models, SIAM J. Finan. Math., 4(1), 474-493, (2013) · Zbl 1287.91141 [25] Florescu, I.; Liu, R.; Mariani, M.; Sewell, G., Numerical schemes for option pricing in regime-switching jump diffusion models, Int. J. Theor. Appl. Finance, 16, 1-25, (2013) · Zbl 1290.91180 [26] Fujiwara, H.; Kijima, M., Pricing of path-dependent American options by Monte Carlo simulation, J. Econ. Dyn. Control, 31, 11, 3478-3502, (2007) · Zbl 1163.91396 [27] Gihman, I. I.; Skorohod, A. V., Stochastic differential equations, The Theory of Stochastic Processes III, 113-219, (1979), Springer · Zbl 0404.60061 [28] Grasselli, M., The 4/2 stochastic volatility model: a unified approach for the Heston and the 3/2 model, Math. Finance, (2016) [29] Heston, S., A closed-form solution for option pricing with stochastic volatility with application to bond and currency options, Rev. Financ. Stud., 6, 327-343, (1993) · Zbl 1384.35131 [30] Hull, J.; White, A., Pricing interest-rate derivative securities, Rev. Financ. Stud., 3, 735-792, (1990) · Zbl 1386.91152 [31] Ikonen, S.; Toivanen, J., Operator splitting methods for American option pricing, Appl. Math. Lett., 17, 809-814, (2004) · Zbl 1063.65081 [32] Ikonen, S.; Toivanen, J., Efficient numerical methods for pricing American options under stochastic volatility, Numer. Methods Partial Differ. Eq., 24, 1, 104-126, (2008) · Zbl 1152.91516 [33] Jacka, S., Optimal stopping and the American put, Math. Finance, 1, 1-14, (1991) · Zbl 0900.90109 [34] Jensen, M. V.; Pedersen, L. H., Early option exercise: never say never, J. Financ. Econ., (2016) [35] Jiang, J.; Liu, R.; Nguyen, D., A recombining tree method for option pricing with state-dependent switching rates, Int. J. Theor. Appl. Finance, 19, 1-26, (2016) · Zbl 1337.91102 [36] Khaliq, A. Q.M.; Liu, R., New numerical scheme for pricing American option under regime switching model, Int. J. Theor. Appl. Finance, 12, 3, 319-340, (2009) · Zbl 1204.91127 [37] Kirkby, J., Efficient option pricing by frame duality with the fast Fourier transform, SIAM J. Financ. Math., 6(1), 713-747, (2015) · Zbl 1320.91155 [38] Kirkby, J., 2015b. Robust barrier option pricing by frame projection under exponential Lévy dynamics. Working Paper. [39] Kirkby, J., 2016a. American and exotic option pricing with jump diffusions and other Lévy processes. Working Paper. [40] Kirkby, J., An efficient transform method for Asian option pricing, SIAM J. Finan. Math., 7(1), 845-892, (2016) · Zbl 1357.91053 [41] Kou, S., A jump-distribution model for option pricing, Manage. Sci., 48, 1086-1101, (2002) · Zbl 1216.91039 [42] Kushner, H., Numerical methods for stochastic control problems in continuous time, SIAM J. Control Optim., 28, 999-1048, (1990) · Zbl 0721.93087 [43] Lee, S. S.; Hannig, J., Detecting jumps from levy jump diffusion processes, J. Financ. Econ., 96, 2, 271-290, (2010) [44] Lindset, S.; Lund, A.-C., A Monte Carlo approach for the American put under stochastic interest rates, J. Econ. Dyn. Control, 31, 4, 1081-1105, (2007) · Zbl 1201.91203 [45] Liu, R.; Nguyen, D., A tree approach to options pricing under regime-switching jump diffusion models, Int. J. Comput. Math., 92, 12, 2575-2595, (2015) · Zbl 1335.91106 [46] Lo, C.; Skindilias, K., An improved Markov chain approximation methodology: derivatives pricing and model calibration, Int. J. Theor. Appl. Finance, 17, 407-446, (2014) [47] Longstaff, F.; Schwartz, E. S., Valuing American options by simulation: simple least-squares approach, Rev. Financ. Stud., 14, 113-147, (2001) [48] Lord, R.; Fang, F.; Bervoets, F.; Oosterlee, C., A fast and accurate FFT-based method for pricing early-exercise options under levy processes, SIAM J. Sci. Comput., 10, 1678-1705, (2008) · Zbl 1170.91389 [49] Medvedev, A.; Scaillet, O., Pricing American options under stochastic volatility and stochastic interest rates, J. Financ. Econ., 98, 1, 145-159, (2010) [50] Merton, R. C., Option pricing when underlying stock returns are discontinuous, J. Financ. Econ., 3, 1-2, 125-144, (1976) · Zbl 1131.91344 [51] Muthuraman, K., A moving boundary approach to American option pricing, J. Econ. Dyn. Control, 32, 3520-3537, (2008) · Zbl 1181.91300 [52] Myneni, R., The pricing of the American option, Ann. Appl. Probab., 2, 1-23, (1992) · Zbl 0753.60040 [53] Pun, C. S.; Chung, S. F.; Wong, H. Y., Variance swap with mean reversion, multifactor stochastic volatility and jumps, Eur. J. Oper. Res., 245, 2, 571-580, (2015) · Zbl 1346.91239 [54] Rambeericha, N.; Pantelous, A. A., A high order finite element scheme for pricing options under regime switching jump diffusion processes, J. Comput. Appl. Math., 300, 83-96, (2016) · Zbl 1331.91194 [55] Rambharat, B. R.; Brockwell, A. E., Sequential Monte Carlo pricing of American-style options under stochastic volatility models, Ann. Appl. Stat., 4, 222-265, (2010) · Zbl 1189.62164 [56] Rubinstein, M., Implied binomial trees, J. Finance, 49, 771-818, (1994) [57] Salmi, S.; Toivanen, J.; Sydow, L., An IMEX-scheme for pricing options under stochastic volatility models with jumps, SIAM J. Sci. Comput., 36, 817-834, (2014) [58] Scott, L., Option pricing when the variance changes randomly: theory, estimation, and an application, J. Financ. Quant. Anal., 22, 4, 419-438, (1987) [59] Stein, E. M.; Stein, J., Stock price distributions with stochastic volatility: an analytic approach, Rev. Financ. Stud., 4, 272-752, (1991) · Zbl 1458.62253 [60] Tavella, D.; Randall, C., Pricing financial instruments-the finite difference method, Wiley Series In Financial Engineering, (2000), John Wiley & Sons New York [61] Zeng, P.; Kwok, Y., Pricing barrier and Bermudan style options under time-changed levy processes: fast Hilbert transform approach, SIAM J. Sci. Comput., 36, 3, 450-485, (2014) · Zbl 1296.91288 [62] Zhu, S.-P., An exact and explicit solution for the valuation of American put options, Quant. Finance, 6, 3, 229-242, (2006) · Zbl 1136.91468 [63] Zhu, S.-P.; Chen, W.-T., An inverse finite element method for pricing American options, J. Econ. Dyn. Control, 37, 1, 231-250, (2013) · Zbl 1345.91083 [64] Zhylyevskyy, O., A fast Fourier transform technique for pricing American options under stochastic volatility, Rev. Deriv. Res., 13, 1-24, (2010) · Zbl 1202.91342 [65] Zvan, R.; Forsyth, P.; Vetzalb, K., Penalty methods for American options with stochastic volatility, J. Comput. Appl. Math., 2, 199-218, (1998) · Zbl 0945.65005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
# Closed form for integral $\int_{0}^{\pi} \left[1 - r \cos\left(\phi\right)\right]^{-n} \phi \,{\rm d}\phi$

Is there a closed form for $$I_n =\int_{0}^{\pi} \frac{\phi}{(1 - r \cos\phi)^n} \,{\rm d}\phi$$ for $\left\vert\,r\,\right\vert < 1$ real and $n > 0$ integer ? The solution to this integral would give a closed form solution for this integral, which describes the interaction energy of vector resonant relaxation in astrophysical dynamics.

Using Mathematica and analytic methods I have derived the following result for $n=\{1,2,3,4,5,6\}$: $$\tag{1} I_n = -\frac{a_n r}{s^{2n-2}} + \frac{b_n}{s^{2n-1}}\left[\chi_2(q) +\left(-\frac{c_n}{b_n}s + {\rm arctanh}(q) \right){\rm arctanh}(r) \right]$$ where $s=\sqrt{1-r^2}$, $q=\sqrt{(1-r)/(1+r)}$, $\chi_2(x)$ is the Legendre chi function, $a_n$, $b_n$, and $c_n$ are constants given by \begin{align} a_1 &= 0, \quad b_1 = 4, \qquad c_1 = 0,\\ a_2 &= 0, \quad b_2 = 4, \qquad c_2 = 2,\\ a_3 &= 1, \quad b_3 = 4 + 2r^2, \qquad c_3 = 3,\\ a_4 &= \frac{7}{3}, \quad b_4 = 4 + 6r^2, \qquad c_4= \frac{11}{3} + \frac{4}{3}r^2,\\ a_5 &= \frac{23}{6}+\frac{11}{12}r^2, \quad b_5 = 4 + 12 r^2 + \frac{3}{2}r^4, \qquad c_5=\frac{25}{6} + \frac{55}{12}r^2,\\ a_6 &=\frac{163}{30} + \frac{47}{12}r^2, \quad b_6 = 4 + 20 r^2 + \frac{15}{2}r^4, \qquad c_6=\frac{137}{30} + \frac{607}{60}r^2 + \frac{16}{15}r^4. \end{align} Is the integral $I_n$ in the general closed form given by (1) for all $n$? If so, what are the constants $a_n$, $b_n$, and $c_n$?

-
Please don't use displaystyle in the title. Thanks. –  robjohn Nov 26 '13 at 20:40
@robjohn The same thing could have been mentioned in a more polite manner. There's nothing wrong in your statement but it came off a bit rude. No offense! –  Ahaan Rungta Nov 26 '13 at 20:43
@AhaanRungta: I did not mean it to. I said Please and Thanks. What would have been a more polite way? –  robjohn Nov 26 '13 at 20:44
a.) Please X. Thanks. b.) Could you please x so that Y? Edited this time. Thank you. <- which do you think sounds better? –  Ahaan Rungta Nov 26 '13 at 20:46
@CarlMummert: I added the context to the question. –  bkocsis Nov 27 '13 at 20:49

First lets make the integral from $-\pi/2$ to $\pi/2$. Set $x = \phi-\pi/2$. We then get $$I = \int_{-\pi/2}^{\pi/2}(1+r\sin(x))^{-n}(x+\pi/2)dx$$ Now recall that $$(1+r\sin(x))^{-n} = \sum_{k=0}^{\infty} (-1)^k \dbinom{n+k}k r^k \sin^k(x)$$ Hence, $$I = \sum_{k=0}^{\infty}(-r)^k \dbinom{n+k}k \int_{-\pi/2}^{\pi/2} (x+\pi/2)\sin^k(x)dx$$ Now from here, we can obtain $$\int_{-\pi/2}^{\pi/2} \sin^k(x) dx \text{ and }\int_{-\pi/2}^{\pi/2} x\sin^k(x) dx$$ Lets call them $I_k$ and $J_k$ respectively. Hence, $$I = \dfrac{\pi}2\sum_{k=0}^{\infty}r^{2k} \dbinom{n+2k}{2k} I_{2k} - \sum_{k=0}^{\infty}r^{2k+1} \dbinom{n+2k+1}{2k+1} J_{2k+1} \tag{\star}$$

Expression for $J_{2k+1}$ and convergence of the above summation:

We have $$J_{2k+1} = -\int_{-\pi/2}^{\pi/2}x \sin^{2k}(x) d(\cos(x)) = \int_{-\pi/2}^{\pi/2} \cos(x) \sin^{2k}(x) dx + 2k \int_{-\pi/2}^{\pi/2} x \cos^2(x) \sin^{2k-1}(x) dx$$ $$\int_{-\pi/2}^{\pi/2} \cos(x) \sin^{2k}(x) dx = \int_{-1}^1 t^{2k} dt = \dfrac2{2k+1}$$ $$\int_{-\pi/2}^{\pi/2} x \cos^2(x) \sin^{2k-1}(x) dx = J_{2k-1} - J_{2k+1}$$ Hence, $$(2k+1)J_{2k+1} = \dfrac2{2k+1} + 2k J_{2k-1}$$ Using this recurrence you can obtain $J_{2k+1}$. Also, it is easy to show that $\left \vert J_{2k+1} \right \vert \leq 2$ using induction.

Similarly, $I_{2k} = \dfrac1{4^k} \dbinom{2k}k \pi \leq \pi$.

Now, for $\vert r \vert < 1$, we have $\displaystyle \sum_{k=0}^{\infty} \dbinom{n+2k}{2k} r^{2k}$ and $\displaystyle \sum_{k=0}^{\infty} \dbinom{n+2k+1}{2k+1} r^{2k}$ converges.

This ensures $\star$ makes perfect sense.

-
I was looking for a closed form expression, i.e. a finite sum of known functions. See edited version of the question. –  bkocsis Dec 1 '13 at 17:41
@bkocsis I don't understand what you mean by closed form. The above is a closed form in my opinion. If you get the answer as $\sin(k)$ or $\cos(k)$ or $\Gamma(k)$ or $\arctan(k)$, etc, do you think that is closed form? All these are infinite series and not a closed form. By truncating the above sum, you can get an arbitrary accurate answer. –  user17762 Dec 1 '13 at 17:48
@bkocsis Also, can you remove the down-vote. My answer is a perfectly valid answer. –  user17762 Dec 1 '13 at 17:55
@bkocsis You are showing a wiki article to mean what a closed form is? I assume that you are interested in calculating the value of the integral for a fixed $r$ and $n$. If so, the infinite series above is a perfectly valid answer. –  user17762 Dec 1 '13 at 23:17
The beauty of closed form expressions is that the parameter dependencies become tractable, and that they are often calculable quickly. Most CPUs and GPUs can calculate many transcendental functions extremely efficiently. Closed form results can speed up simulations very significantly. If you can show that your sums converge for $|r|<1$ and give $J_{2k+1}$ specifically, I can remove the down vote. –  bkocsis Dec 2 '13 at 0:14

The integral can be evaluated by realizing that it is a derivative with respect to $R=1/r$, i.e. $$I_n =\int_{0}^{\pi} \frac{\phi}{(1 - r \cos\phi)^n} \,{\rm d}\phi = R^n \int_{0}^{\pi} \frac{\phi}{(R - \cos\phi)^n} \,{\rm d}\phi = \frac{(-1)^{n-1} R^n}{(n-1)!} \frac{d^{n-1}}{dR^{n-1}}\int_{0}^{\pi} \frac{\phi}{R - \cos\phi} \,{\rm d}\phi.$$ This integral can be evaluated with a Weierstrass substitution $t = \tan (\phi/2)$, $$F(R) = \int_{0}^{\pi} \frac{\phi}{R - \cos\phi} \,{\rm d}\phi = \frac{4r}{1+r}\int_0^{\infty} \frac{\arctan t}{q^2 + t^2} dt = \frac{4}{\sqrt{R^2-1}}\int_0^{\pi/2} \arctan \left(q \tan y \right) dy = \frac{4}{\sqrt{R^2-1}}\left[\chi_2(q) - {\rm arctanh}(q) \ln(q) \right] =\frac{4}{\sqrt{R^2-1}}\left[\chi_2(q) +\frac{1}{2} {\rm arccosh}(R) {\rm arctanh}(R) \right],$$ where $q=\sqrt{(1-r)/(1+r)}$ and $\chi_2(x)$ is the Legendre chi function. We can now derive the integral by taking derivatives of this function $$I_n = \frac{(-1)^{n-1} R^n}{(n-1)!} \frac{d^{n-1}}{dR^{n-1}}F(R).$$ Note that ${\rm arccosh\,}R=2{\rm arctanh\,}q$, ${\rm arccoth\,}R=\ln q$, and $$\frac{d}{dx}\chi_2(x) = \frac{{\rm arctanh}(x)}{x} \quad{\rm so\quad} \frac{d}{dR}\chi_2(q) = \frac{{\rm arctanh}(q)}{R^2 - 1} = \frac{1}{2}\frac{{\rm arccosh}(R)}{R^2 - 1}$$ $$\frac{d}{dR} {\rm arccosh}(R) = \frac{1}{\sqrt{R^2 - 1}} \quad{\rm and\quad} \frac{d}{dR} {\rm arccoth}(R) = \frac{-1}{R^2 - 1} = \frac{1}{2}\left(\frac{1}{R+1} - \frac{1}{R-1}\right).$$ The derivatives for $n\geq 3$ simplify to $$I_n = \frac{R^n}{S^{2n-2}}\left\{ \frac{4 A_{n-1}}{S}\left[\chi_2(q) - {\rm arctanh(q)\ln q}\right]\right. \\ \left.+2\sum_{k=0}^{n-2} \frac{A_k A_{n-k-2}}{k+1} \ln q + \sum_{j=0}^{n-3}\sum_{k=0}^{n-3-j}\frac{A_k A_{n-3-j-k}}{n-1-k} \frac{(R-1)^{1+j}-(R+1)^{1+j}}{1+j} \right\}$$ where $S=\sqrt{R^2-1}$ and $A_n$ is a polynomial of $R$ defined as $$A_n = \frac{(-1)^n}{n!}\left(R^2-1\right)^{n+(1/2)}\frac{d^{n}}{dR^{n}} \left(R^2-1\right)^{-1/2}\\ =\left(\frac{R+1}{4}\right)^n\sum_{s=0}^{n}\frac{(2s)!}{(s!)^2}\frac{[2(n-s)]!}{[(n-s)!]^2}q^{2s}.$$ The coefficients are related to Legendre polynomials $P_{2n}(0)=(-1)^n(2n)!/[4^n (n!)^2]$. The result simplifies to $$I_n=\left(\frac{R}{R-1}\right)^n \frac{q^2}{4^{n-2}}\left\{ a(q) [\chi_2(q) - {\rm arctanh(q)}\ln q] +b(q)\ln q + c(q)\right\}$$ where $$a(q)=\sum_{K=0}^{n-1}q^{2K-1} \frac{(2K)!}{(K!)^2} \frac{[2(n-1-K)]!}{[(n-1-K)!]^2}\,,$$ $$b(q)=\sum_{K=0}^{n-2}q^{2K} \sum_{s=0}^{K}\frac{(2s)!}{(s!)^2}\frac{[2(K-s)]!}{[(K-s)!]^2} \sum_{j=K}^{n-2}\frac{[2(j-K)]!}{[(j-K)!])^2}\frac{[2(n-2-j)]!}{[(n-2-j)!]^2}\frac{2}{j-s+1}\,,$$ $$c(q)=\sum_{K=0}^{n-3}q^{2K+2} \sum_{J=0}^{K} \frac{4^{K-J+1}}{1+K-J} \sum_{s=0}^{J}\frac{(2s)!}{(s!)^2}\frac{[2(J-s)]!}{[(J-s)!]^2}\\ \quad\times \sum_{j=K}^{n-3}\frac{[2(j-K)]!}{[(j-K)!])^2}\frac{[2(n-3-j)]!}{[(n-3-j)!]^2}\frac{1}{n-1-j+s+K-J}\\ \quad+\sum_{K=0}^{n-3}q^{2K} \sum_{J=K}^{L-3} \frac{-4^{J-K+1}}{1+J-K}\sum_{s=0}^{K}\frac{(2s)!}{(s!)^2}\frac{[2(K-s)]!}{[(K-s)!]^2}\\ \quad\times \sum_{j=J}^{n-3}\frac{[2(j-J)]!}{[(j-J)!])^2}\frac{[2(n-3-j)]!}{[(n-3-j)!]^2}\frac{1}{n-1-j+s+J-K}\,.$$

-

Not a full answer, but maybe interesting:

$I_{n}(r)$ obeys a recursion relation: $$I_{n+1}(r)=I_{n}(r)+\frac{r}{n} \frac{\partial}{\partial r}I_{n}(r)$$

A large $n$ approximation is: $$I_{n}(r)\stackrel{n \rightarrow \infty}{\sim} \int_{0}^{\pi}\phi \exp(n\, r \cos \phi)\mathrm{d}\phi,$$ which shows that for large $n$ the integral depends only on the product $n\,r$. Interestingly, also the approximation seems not to be solvable in closed form.

For the approximation I used: $$\left(1 - \frac{z}{n}\right)^{n} \stackrel{n \rightarrow \infty}{\sim} e^{- z}$$

-


text:
location:  Publications → journals
Search results

Search: MSC category 16E20 ( Grothendieck groups, $K$-theory, etc. [See also 18F30, 19Axx, 19D50] )

 Expand all        Collapse all Results 1 - 1 of 1

1. CJM 1999 (vol 51 pp. 488)

Burgess, W. D.; Saorín, Manuel
 Homological Aspects of Semigroup Gradings on Rings and Algebras This article studies algebras $R$ over a simple artinian ring $A$, presented by a quiver and relations and graded by a semigroup $\Sigma$. Suitable semigroups often arise from a presentation of $R$. Throughout, the algebras need not be finite dimensional. The graded $K_0$, along with the $\Sigma$-graded Cartan endomorphisms and Cartan matrices, is examined. It is used to study homological properties. A test is found for finiteness of the global dimension of a monomial algebra in terms of the invertibility of the Hilbert $\Sigma$-series in the associated path incidence ring. The rationality of the $\Sigma$-Euler characteristic, the Hilbert $\Sigma$-series and the Poincar\'e-Betti $\Sigma$-series is studied when $\Sigma$ is torsion-free commutative and $A$ is a division ring. These results are then applied to the classical series. Finally, we find new finite dimensional algebras for which the strong no loops conjecture holds. Categories:16W50, 16E20, 16G20
 top of page | contact us | privacy | site map |


text:
# Ordering

0th

Percentile

##### Compute vertex ordering for an undirected graph

Compute vertex ordering for an undirected graph

Keywords
models
##### Usage
cuthill.mckee.ordering(g)
minDegreeOrdering(g, delta=0)
sloan.ordering(g, w1=1, w2=2)
##### Arguments
g
an instance of the graph class with edgemode “undirected”
delta
Multiple elimination control variable. If it is larger than or equal to zero then multiple elimination is enabled. The value of delta specifies the difference between the minimum degree and the degree of vertices that are to be eliminated.
w1
First heuristic weight for the Sloan algorithm.
w2
Second heuristic weight for the Sloan algorithm.
##### Details

The following details were obtained from the documentation of these algorithms in Boost Graph Library and readers are referred their for even more detail. The goal of the Cuthill-Mckee (and reverse Cuthill-Mckee) ordering algorithm is to reduce the bandwidth of a graph by reordering the indices assigned to each vertex.

The minimum degree ordering algorithm is a fill-in reduction matrix reordering algorithm.

The goal of the Sloan ordering algorithm is to reduce the profile and the wavefront of a graph by reordering the indices assigned to each vertex.

The goal of the King ordering algorithm is to reduce the bandwidth of a graph by reordering the indices assigned to each vertex.

##### Value

cuthill.mckee.ordering
returns a list with elements:
reverse cuthill.mckee.ordering
the vertices in the new ordering
original bandwidth
bandwidth before reordering vertices
new bandwidth
bandwidth after reordering of vertices
minDegreeOrdering
return a list with elements:
inverse_permutation
the new vertex ordering, given as the mapping from the new indices to the old indices
permutation
the new vertex ordering, given as the mapping from the old indices to the new indices
sloan.ordering
returns a list with elements:
sloan.ordering
the vertices in the new ordering
bandwidth
bandwidth of the graph after reordering
profile
profile of the graph after reordering
maxWavefront
maxWavefront of the graph after reordering
aver.wavefront
aver.wavefront of the graph after reordering
rms.wavefront
rms.wavefront of the graph after reordering

##### References

Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )

The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine; (Addison-Wesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0-201-72914-8

##### Aliases
• cuthill.mckee.ordering
• minDegreeOrdering
• sloan.ordering
• kingOrdering
##### Examples
con <- file(system.file("XML/dijkex.gxl",package="RBGL"), open="r")
coex <- fromGXL(con)
close(con)

coex <- ugraph(coex)
cuthill.mckee.ordering(coex)
minDegreeOrdering(coex)
sloan.ordering(coex)

Documentation reproduced from package RBGL, version 1.48.1, License: Artistic-2.0

### Community examples

Looks like there are no examples yet.


text:
# Solving $n!+m!+k^2=n!m!$ for positive integers $n,m,k$

I have been running in circles with this for a while now.

It seems that the only solution is $(n,m,k)=(2,3,2)$ but I don't know how to prove it.

Things I have noticed: WLOG $n\geq m$ we see that $k^2$ is a multiple of $m!$. I have a feeling that this might be key; maybe there is a restriction on squares and factorials which is only possible for $n=k=2$... I tried manipulating things, the only potentially useful expression I could come up with was:

$$(n!-1)(m!-1)=1+k^2$$

I have tried modular arithmetic on both sides to get some additional conditions but nothing useful came up. Maybe we could make use of $m!n!<(m+n)!$ to bound $k^2?$ (I doubt it though since the RHS blows up too fast).

I don't know if any of this information is useful though.

-
Technically, this is not a Diophantine equation, since diophantine equations only allow polynomials, and $n!$ is not a polynomial in $n$. –  Thomas Andrews Mar 4 '13 at 18:21
In your WLOG, you should have $k^2$ is a multiple of $m!$ –  Ross Millikan Mar 4 '13 at 18:33
@RossMillikan Thanks. –  Little miss sunshine Mar 4 '13 at 18:44

When $n\geq 4$, $n!-1\equiv -1\pmod 4$, so when $n\geq 4$, some prime $p\equiv -1\pmod 4$ divides $n!-1$ and hence divides $k^2+1$. But that can't be true for $p\equiv -1 \pmod 4$.
So we know $m,n<4$. Now just try all the cases.


text:
3 M needs to be positive, not just hermitian

Assume $M$ is an invertible Hermitian positive matrix of rank $N$. The Von Neumann entropy $H$ of a matrix $M$ with eigenvalues ${ \lambda_n }$is

$H[M] = -\sum_{n=1}^N \lambda_n \ln \lambda_n$.

In principle, the eigenvalues are encoded in the characteristic polynomial

$\phi_t (M) = \mathrm{det}(tI-M) = \prod_n(t-\lambda_n) = t^{N} + a_{N-1} t^{N-1} \cdots + a_1 t +a_0$.

The trace $\mathrm{Tr}\, M$ is given by the coefficient $a_{N-1}$ in the characteristic polynomial:

$\lim_{t \to \infty} \frac{\phi_t (M)-t^N}{t^{N-1}} = a_{N-1} = (-1)^{N-1} \, \mathrm{Tr}\, M = (-1)^{N-1} \sum_n \lambda_n$.

Is there a similar relationship between the entropy and the characteristic polynomial?

Assume $M$ is an invertible Hermitian matrix of rank $N$. The Von Neumann entropy $H$ of a matrix $M$ with eigenvalues ${ \lambda_n }$is

$H[M] = -\sum_{n=1}^N \lambda_n \ln \lambda_n$.

In principle, the eigenvalues are encoded in the characteristic polynomial

$\phi_t (M) = \mathrm{det}(tI-M) = \prod_n(t-\lambda_n) = t^{N} + a_{N-1} t^{N-1} \cdots + a_1 t +a_0$.

The trace $\mathrm{Tr}\, M$ is given by the coefficient $a_{N-1}$ in the characteristic polynomial:

$\lim_{t \to \infty} \frac{\phi_t (M)-t^N}{t^{N-1}} = a_{N-1} = (-1)^{N-1} \, \mathrm{Tr}\, M$.= (-1)^{N-1} \sum_n \lambda_n$. Is there a similar relationship between the entropy and the characteristic polynomial? 1 # Is there a simple relation between the entropy of a matrix and its characteristic polynomial? The Von Neumann entropy$H$of a matrix$M$with eigenvalues${ \lambda_n }$is$H[M] = -\sum_{n=1}^N \lambda_n \ln \lambda_n$. In principle, the eigenvalues are encoded in the characteristic polynomial$\phi_t (M) = \mathrm{det}(tI-M) = \prod_n(t-\lambda_n) = t^{N} + a_{N-1} t^{N-1} \cdots + a_1 t +a_0 $. The trace$\mathrm{Tr}\, M$is given by the coefficient$a_{N-1}$in the characteristic polynomial:$\lim_{t \to \infty} \frac{\phi_t (M)-t^N}{t^{N-1}} = a_{N-1} = (-1)^{N-1} \, \mathrm{Tr}\, M \$.

Is there a similar relationship between the entropy and the characteristic polynomial?


text:
# A homogeneously charged pyramid

Consider a regular pyramid charged with constant volume charge density. The potential at point P, the top of the pyramid is $$1V$$. What would be the potential at point P if we removed the top part, so the pyramid is instead truncated at a height $$h=0.6 H$$?

Hint: You don't need to do any integration, but instead can deduce the result logically.

×


text:
# 2021-07-24 An anatomy of the request

Early Internet protocols were simple. In order to make a request, you contact a machine on a particular port, and send some bytes, terminated by a carriage return (CR or \r) and a line feed (LF or \n). We can simulate this using echo and nc (netcat) to make these requests ourselves.

This is a request for user information using the finger protocol. Here, we’re sending a name to the server. The response is plain text.

echo -ne "alex\r\n" | nc alexschroeder.ch 79

Gopher, at the protocol level, is the same thing. Here, we’re sending a selector to the server. The response is plain text.

echo -ne "page/Alex_Schroeder\r\n" | nc alexschroeder.ch 70

HTML 1.0, at the protocol level, is already a lot more complicated. We’re sending the “method” (in our case, “GET”), the resource we’re interested in, the procotol version, HTTP headers (in our case, none), and an empty line, i.e. another CRLF:

echo -ne "GET /wiki/Alex_Schroeder HTTP/1.0\r\n\r\n" | nc alexschroeder.ch 80

The response in this case is actually a redirect to the HTTPS URL. We’ll talk about this down below. For now, let’s just note that we got a response that we can act upon.

All these protocols mentioned above cannot do virtual hosting. Virtual hosting is when multiple domains are served on the same machine. We’re used to this, on the web. We know that “http://alexschroeder.ch/” and “http://campaignwiki.org/” result in a different response; I know that this is surprising because they are both hosted on the same server. How is this possible? This is not possible using HTTP/1.0, that’s for sure: the server doesn’t know what host you think you’re talking to. If we try it, both requests get redirected to the page on “alexschroeder.ch”, the default domain.

echo -ne "GET /wiki/Alex_Schroeder HTTP/1.0\r\n\r\n" | nc alexschroeder.ch 80
echo -ne "GET /wiki/Alex_Schroeder HTTP/1.0\r\n\r\n" | nc campaignwiki.org 80

You could argue that this is a bit of security concern. After all, somebody doing this request for “campaignwiki.org” now knows that it’s being hosted on the same server as “alexschroeder.ch”. I’m going to ignore that, however.

In any case, the technical reason for all of this is that at the TCP/IP level, domain names do not exist. We tell “nc” to send the request to “alexschroeder.ch” port 80, but what it actually does is look it up using the domain name system (DNS) and then it uses the IP number instead.

We can do our own lookup using “dig”:

dig alexschroeder.ch

The answer is “178.209.50.237” if you’re using IPv4. By default, that’s the answer you get because type “A” is the default. To get the IPv6 answer, you need to specify type “AAAA”.

dig -t AAAA alexschroeder.ch

The answer is “2a02:418:6a04:178:209:50:237:1” if you’re using IPv6.

We can verify the results above by substituting the IP numbers ourselves:

echo -ne "GET /wiki/Alex_Schroeder HTTP/1.0\r\n\r\n" | nc 178.209.50.237 80

The solution, as far as HTTP was concerned, is the use of additional headers. HTTP has a ton of headers to tell servers whether they already have a resourced cached and how old it is, what sort of languages they’d prefer to get back, what sort of MIME types they’d like to get back, and so on. One of these headers tells the server what host we think we’re talking to.

Here’s how to do the requests with a host header:

echo -ne "GET /wiki/Alex_Schroeder HTTP/1.0\r\nhost: alexschroeder.ch\r\n\r\n" | nc alexschroeder.ch 80
echo -ne "GET /wiki/Alex_Schroeder HTTP/1.0\r\nhost: campaignwiki.org\r\n\r\n" | nc campaignwiki.org 80

The request for “campaignwiki.org” now has a redirect to the same resource on “campaignwiki.org”. You can double check by using the IP number:

echo -ne "GET /wiki/Alex_Schroeder HTTP/1.0\r\nhost: campaignwiki.org\r\n\r\n" | nc 2a02:418:6a04:178:209:50:237:1 80

What about Gemini? It doesn’t have headers to send along, but instead of just naming the path of the resource on the server like Gopher does, it names the URL it is requesting. Sadly, we can’t illustrate this unless we use TLS. If you are lucky, your “netcat” or “nc” has the “--ssl” option and we can keep using it.

First, let’s just quickly show that HTTPS is HTTP over SSL or TLS, on a different port:

echo -ne "GET /wiki/Alex_Schroeder HTTP/1.0\r\nhost: alexschroeder.ch\r\n\r\n" | nc --ssl alexschroeder.ch 443
echo -ne "GET /wiki/Alex_Schroeder HTTP/1.0\r\nhost: campaignwiki.org\r\n\r\n" | nc --ssl campaignwiki.org 443

And so we get to Gemini. As you can see, we got rid of the complication using HTTP headers.

echo -ne "gemini://alexschroeder.ch/page/Alex_Schroeder\r\n" | nc --ssl alexschroeder.ch 1965

All right! 🚀🚀😃🎉

I hope you can see how using the command line tools helped me understand these things.

Now you know how a server like Phoebe can look at the first line of the request it gets and determine whether to serve a Finger response, a Gopher response, a Web response, or a Gemini response.

References, linking to the older RFCs because they’re often simpler to read:

RFCs, yo! I head Gemini might get one, eventually?

If you don’t have an --ssl option on nc you can try:

echo -ne "gemini://alexschroeder.ch/page/Alex_Schroeder\r\n" \
| openssl s_client alexschroeder.ch:1965

Fails needing a client certificate, but then I assume nc --ssl would fail that way too. I also assume an option on openssl would allow adding one but haven’t looked into it.

Ed Davies 2021-07-24 19:37 UTC

I think it works if you add the -quiet option and ignore stderr:

echo -ne "gemini://alexschroeder.ch/page/Alex_Schroeder\r\n" \
| openssl s_client -quiet alexschroeder.ch:1965 2>/dev/null

At the time I was experimenting with bash functions as clients, but I have since abandoned it.

At least I think there’s nothing in my personal setup, nothing in my “~/.ssh/config” file that modifies s_client.

– Alex 2021-07-24 20:58 UTC

Actually, /b wrote in letting me know that the key part is not --quiet but that --quiet also turns on --ign_eof, and that’s the important one.

– Alex 2021-07-28 07:50 UTC

Please make sure you contribute only your own work, or work licensed under the GNU Free Documentation License. Note: in order to facilitate peer review and fight vandalism, we will store your IP number for a number of days. See Privacy Policy for more information. See Info for text formatting rules. You can edit the comment page if you need to fix typos. You can subscribe to new comments by email without leaving a comment.