Group Abstract Group Abstract

Message Boards Message Boards

[GIF] Plotting the Contours of Deformed Hyperspheres

Posted 10 years ago

Considered as a series reversion ( Cf. Mathworld, A&S ) of implicit equation $$E = \frac{1}{2}\Psi^2 + \sum_{n=3}^{\infty} f_n(\phi,\theta,\ldots)\;\Psi^n,$$ function A276738 determines the radius $\Psi$ of a hypersurface that limits in small $E$ to the shape of a perfect hypersphere, a circle, a sphere, etc...

Examples in 2,3 dimensions lend themselves well to depiction. Let's see the Henon Heiles Potential, and an octahedral Energy Surface.

Basic Functions

RExp[n_] := Expand[b Plus[R[0], Total[b^# R[#] & /@ Range[n]]]]

RCalc[n_] := 
With[{basis = Subtract[Tally[Join[Range[n + 2], #]][[All, 2]],
Table[1, {n + 2}]] & /@ IntegerPartitions[n + 2][[3 ;; -1]]},
Total@ReplaceAll[Times[-2, Multinomial @@ #, v[Total[#]],
Times @@ Power[RSet[# - 1] & /@ Range[n + 2], #]] & /@ basis,
{Q^2 -> 1, v[2] -> 1/4}]]

AbsoluteTiming[RSet[0] = 1;   Set[RSet[#], Expand@RCalc[#]] & /@ Range[20];][[1]]

Surface[Nexp_, rep_] :=   RExp[Nexp] /. R -> RSet /. 
v[n_] :>  Function[{a}, 
Total[v[#, a - #] Q^# P^(a - #) & /@ Range[0, a]]][n] /. 
rep /. {P -> Sin[\[Phi]], Q -> Cos[\[Phi]]};

HyperSurface[Nexp_, rep_] :=   RExp[Nexp] /. R -> RSet /. v[n_] :>    Function[{a}, 
Total[Flatten@          Table[v[a - i - j, i, j] X^(a - i - j) Y^i Z^j, {i, 0,  a}, {j, 0, a - i}]]][n] /. 
rep /. {X -> Sin[\[Theta]] Cos[\[Phi]], 
Y -> Sin[\[Theta]] Sin[\[Phi]], Z -> Cos[\[Theta]]};

Print Pictures

ViewV = {1, 2, 2};

TrigWords = 
Flatten[Expand[      Surface[20, {v[2, 1] -> 3 \[Epsilon], v[0, 3] -> -\[Epsilon], 
v[_, _] -> 0}]] /. Plus -> List /. Times -> List];

TrigLines20 = 
With[{surf =     Surface[20, {v[2, 1] -> 1/2, v[0, 3] -> -1/3/2, v[_, _] -> 0}]},
(surf /. b -> (#/10)) & /@ Range[5]];

g1 = Show[
Graphics[{Lighter@Gray,  Text[#, RandomReal[{-1/2, 1}, 2]] & /@ TrigWords}, 
PlotRange -> {{-1/2, 1}, {-1/2, 1}}], Graphics[{Thick,
{Dashed,  Line[Part[RotationMatrix[{{0, 0, 1}, ViewV}].#, 
1 ;; 2] & /@ {{0, 0, -1/4}, {0, 0, 5/4}}]},
Thickness[.005],  MapThread[
Line[Function[{a},     N[Part[RotationMatrix[{{0, 0, 1}, 
ViewV}].{#1 Cos[\[Phi]], #1 Sin[\[Phi]], #2/
10} /. {\[Phi] -> a}, 1 ;; 2]]] /@ (Range[0, 200]/
200 2 Pi)] &,
{TrigLines20, Range[5]}]}], ImageSize -> 800];

OctSurf6 =   HyperSurface[
20, {v[4, 0, 0] -> \[Epsilon] 2/5, v[0, 4, 0] -> \[Epsilon] 2/5, 
v[0, 0, 4] -> \[Epsilon] 2/5,
v[2, 2, 0] -> \[Epsilon] 6/5, v[2, 0, 2] -> \[Epsilon] 6/5, 
v[0, 2, 2] -> \[Epsilon] 6/5, 
v[_, _, _] -> 0} /. {\[Epsilon] -> -1/2}] /. b -> 6/10;

OctSurf3 =   HyperSurface[
20, {v[4, 0, 0] -> \[Epsilon] 2/5, v[0, 4, 0] -> \[Epsilon] 2/5, 
v[0, 0, 4] -> \[Epsilon] 2/5,
v[2, 2, 0] -> \[Epsilon] 6/5, v[2, 0, 2] -> \[Epsilon] 6/5, 
v[0, 2, 2] -> \[Epsilon] 6/5, 
v[_, _, _] -> 0} /. {\[Epsilon] -> -1/2}] /. b -> 3/10;

OctWords =   Flatten[Expand[
HyperSurface[  10, {v[4, 0, 0] -> \[Epsilon] 2, v[0, 4, 0] -> \[Epsilon] 2, 
v[0, 0, 4] -> \[Epsilon] 2 ,
v[2, 2, 0] -> \[Epsilon] 6 , v[2, 0, 2] -> \[Epsilon] 6 , 
v[0, 2, 2] -> \[Epsilon] 6 , v[_, _, _] -> 0}]] /. 
Plus -> List /. Times -> List];

g2 = Show[   Graphics[{Lighter@Gray, 
Text[#, RandomReal[{-2, 2}, 2]] & /@ OctWords}, 
PlotRange -> 2 {{-1, 1}, {-1, 1}}],
Graphics[{     Thick, {Dashed, 
Line[Part[RotationMatrix[{{0, 0, 1}, ViewV}].#, 1 ;; 2] & /@ {{0, 0, 2}, {0, 0, -2}}]},
Thickness[.005],
Line /@       Outer[N[Part[
RotationMatrix[{{0, 0, 1}, 
ViewV}].{Sin[\[Theta]] Cos[\[Phi]], 
Sin[\[Theta]] Sin[\[Phi]], 
Cos[\[Theta]]} OctSurf3 /. {\[Theta] -> #1, \[Phi] ->  #2}, 1 ;; 2]] &, 
Range[1, 9] Pi/10, Range[0, 100] 2 Pi/100, 1],
Line /@       Outer[N[Part[
RotationMatrix[{{0, 0, 1}, 
ViewV}].{Sin[\[Theta]] Cos[\[Phi]], 
Sin[\[Theta]] Sin[\[Phi]], 
Cos[\[Theta]]} OctSurf6 /. {\[Theta] -> #1, \[Phi] ->   #2}, 1 ;; 2]] &, 
Range[1, 9] Pi/10, Range[0, 200] 2 Pi/200, 1]
}], ImageSize -> 800];

Henon Heiles

Henon Heiles

Octahedral

enter image description here

What's more curious than these graphics? The new conjecture: that A276738 can be defined in terms of A028338.

POSTED BY: Brad Klee
13 Replies
Posted 10 years ago

Deformation Animation

Deformation Animation

Time animation condition: $$ \frac{d}{dt} \Psi \approx \pm c_1, $$ along direction of maximum deformation, $(1,1,1)$. This requires, $$ \frac{d}{dt} E \neq c_2, $$
with arbitrary constants $ c_1, c_2 $.

Color Gradient Surface Tilings

Colored Tiling

Inspired by Old Veteran Paul Klee Einsame Blute .

POSTED BY: Brad Klee
Posted 10 years ago

Lifting Megabytes in the Gymnasium Pt. 2

Confer: A283298, A283247.

Stronger Defintion for Symbolic Reversion of Power Series ( conjecture )

By analogy to the above, we rework the case with leading linear term, as presented on Mathworld, and in Abramowitz and Stegun.

PolysA257635[n_] :=  Expand[-#! Binomial[2 # - x, #] & /@ Range[0, n - 1]]
TA283298[n_] := With[{polys = PolysA257635[n]},   Table[polys[[j]] /. x -> 2 j + i, {i, 1, n}, {j, 1, i}]]

Functions for Comparison

InvExp = InverseSeries[ Series[f[x], {x, 0, 11}] /. (D[f[x], {x, n_}] /. x -> 0) :> (n! \[Epsilon][n]) /.
{  f[0] -> 0, \[Epsilon][1] -> 1}];

RingGens[n_] := Times @@ (\[Epsilon] /@ #) & /@ (IntegerPartitions[n] /. x_Integer :> x + 1)

Basis[n_] := 
Total /@ Map[
Times[(*2^(Length[#]-1)*)1/Times @@ (Tally[#][[All, 2]]!), 
Times @@ (# /. x_Integer :> \[Epsilon][x + 1])] &, 
Function[{a}, Select[IntegerPartitions[n], Length[#] == a &]] /@ 
Range[n], {2}]

A111785[n_] := Expand[x + Dot[
MapThread[Dot, {TA283298[n], Basis[#] & /@ Range[n]}],
x^Range[2, n + 1]     ]];

A111785T[n_] :=  With[{exp = A111785[n]},  
Function[{a},    Coefficient[Coefficient[exp, x, a + 1], #] & /@ RingGens[a]] /@  Range[n]]

Brute Force

In[] = SameQ[A111785[10], Expand[Normal[InvExp]]]
Out[] = True

Application to Arctangent

\[Epsilon]List[
n_] := \[Epsilon][#] -> 
Coefficient[Normal@Series[Tan[x], {x, 0, n + 1}], x, #] & /@ 
Range[n + 1];

fList = A111785[#] /. \[Epsilon]List[#] & /@ (2 Range[15]);

Colors = Blend[{Yellow, Orange}, #/15] & /@ Range[15];

Show[
Plot[ArcTan[x], {x, -Pi/2, Pi/2}, PlotStyle -> Red],
MapThread[
Plot[#1, {x, -Pi/2, Pi/2}, PlotStyle -> #2] &, {fList, Colors}],
ImageSize -> 800
]

Arctangent

Time Test and ByteCount

Time Test

The following command practically hangs on my personal computer:

In[] = AbsoluteTiming[ N[ByteCount[    Expand[Normal[
InverseSeries[       Series[f[x], {x, 0, 15}] /. (D[f[x], {x, n_}]
/. x -> 0) :> (n! \[Epsilon][n]) /. {     f[0] -> 0, \[Epsilon][1] -> 1}]]]]/10^6]]
Out[]= $Aborted

How about the strong man function, how many Megabytes?

In[]= AbsoluteTiming[ N[ByteCount[A111785[35]]/10^6]]
Out[]= {6.73205, 47.5168}

Almost 50 in under 10s. Now that's a Powerful Power series! Conjectural magic and mysterious binomial number theory wins again !

POSTED BY: Brad Klee
Posted 10 years ago

To be clear... around 1:00 a.m. 3/7/2017 I did forget to type out the definition of RExp, and later edited it in today.

Temper, ha! My current preference is distemperment. To each his own.

To sum things up, one more point :

  • If the built-in functions don't meet user specifications, it's easy for users to code their own improvements using the basic functionality of Mathematica.

Thanks again for your comments, I will keep working on improving the definitions for these algorithms.

Brad

POSTED BY: Brad Klee
POSTED BY: Daniel Lichtblau
Posted 10 years ago
POSTED BY: Brad Klee
POSTED BY: Daniel Lichtblau
Posted 10 years ago
POSTED BY: Brad Klee
POSTED BY: Daniel Lichtblau
Posted 10 years ago

Now that I am just talking about numbers and not drawing any pictures, I think this thread may be losing interest. Also we haven't heard from the relevant experts as to why / how I am out-competing a usually-strong Mma function. But I talked breifly with Peter Luschny who found an interesting connection to the Pochammer function. Working from there and searching the OEIS more I obtained the following closed form in terms of MultiFactorial:

MultiFactorial[n_, nDim_] := 
Times[n, If[n - nDim > 1, MultiFactorial[n - nDim, nDim], 1] ]

AlternateGeneralT[n_, nLead_] := 
Table[MultiFactorial[i + nLead j + 2, nLead]/
MultiFactorial[i + 2, nLead], {i, 0, n}, {j, 0, i}] // TableForm

And the following Prints:

Grid[Partition[(Abs@GeneralT[5, #] // TableForm) & /@ Range[12], 4], 
 Frame -> All]

Grid[Partition[AlternateGeneralT[4, #] & /@ Range[12], 4], 
 Frame -> All]

Yield the same triangles

Number Triangles

Thank you Wolfram Community Moderation Team, for showing me a little bit of respect.

Conclusion

To reiterate my points:

  • What is the Mathematica Algorithm?
  • Why is Mathematica going so slow?
  • Can we change the Mma Source Code to use one of my definitions or something similar?
  • Why aren't any of the triangles above already in OEIS?
  • Is this reduction known?

I find the discovery enjoyable, and look forward to finding out just why it works this way. More work ahead . . .

Next, I'm going back to physics research, where I apply these triangles of numbers to perturbation calculations of planetary motion. Furthermore, I have another idea for applying series inversion to make it easy to compute integrals along Rotational Energy Surfaces.

POSTED BY: Brad Klee
Posted 10 years ago

HAKMEM: General Algorithms for Leading Term $x^n$

Series

$$ y = x^n + c_{n+1}\; x^{n+1}+ c_{n+2} \;x^{n+2} + c_{n+3}\; x^{n+3} + \ldots $$

Mathematica Built In

MmaExpand[m_, nLead_] := Expand[Refine[Normal[
     InverseSeries[ Series[f[x], {x, 0, m + nLead}] /. Join[
        {f[0] -> 0, (D[f[x], {x, nLead}] /. x -> 0) -> (nLead!)},
        (D[f[x], {x, #}] /. x -> 0) -> 0 & /@ Range[1, nLead - 1],
        ((D[f[x], {x, #}] /. x -> 0) -> #! c[#]) & /@ 
         Range[nLead + 1, m + nLead]]]] /. x -> y^nLead, y > 0]]

Conceptually Simple Multinomial Method

RExp[n_] := Expand[y Plus[R[0], Total[y^# R[#] & /@ Range[n]]]]

RCalc[0, _] = 1;
RCalc[n_, nLead_] := With[{basis = Subtract[Tally[Join[Range[n + nLead], #]][[All, 2]],
Table[1, {n + nLead}]] & /@ Select[IntegerPartitions[n + nLead], Length[#] > nLead - 1 &][[2 ;; -1]]},
Total@ReplaceAll[Times[-1/nLead, Multinomial @@ #, c[Total[#]],
Times @@ Power[RSet[# - 1] & /@ Range[n + nLead], #]] & /@     basis, {c[nLead] -> 1}]]

MultinomialExpand[n_, nLead_] := ( Clear@RSet; Set[RSet[#], Expand@RCalc[#, nLead]] & /@ Range[0, n];
Expand[RExp[n] /. R[m_] :> RCalc[m, nLead]])

Frobenius-Stirling Conjectural Magic

Also see Peter Luschny, Stirling-Frobenius Cycle Numbers.

SF[0, 0, m_] = 1;
SF[n_, k_, m_] := SF[n, k, m] = If[Or[k > n, k < 0], 0,
If[And[n == 0, k == 0], 1,
SF[n - 1, k - 1, m] + (m*n - 1)*SF[n - 1, k, m]
]]

GeneralPolys[n_, nLead_] := MapThread[Dot, {
Table[SF[i, j, nLead], {i, 0, n - 1}, {j, 0, i}],
Table[ x^j, {i, 0, n - 1}, {j, 0, i}]}]

GeneralT[n_, nLead_] := With[{ps = GeneralPolys[n, nLead]},
Table[(-1)^j  ps[[j]] /. {x -> i + 2}, {i, 1, n}, {j, 1, i} ]
]

Basis[n_, nLead_] := Total /@ Map[
Times[nLead^(-Length[#]) 1/Times @@ (Tally[#][[All, 2]]!),
Times @@ (# /. x_Integer :> c[x + nLead])] &, Function[{a},
Select[IntegerPartitions[n], Length[#] == a &]] /@ Range[n], {2}]

MagicExpand[n_, nLead_] := Expand[y + Dot[MapThread[Dot,
{GeneralT[n, nLead], Basis[#, nLead] & /@ Range[n]}], 
y^Range[2, n + 1]]];

Compare

In[]:= ColumnForm[MmaExpand[2, #] /. y -> (# y) & /@ Range[5]]
ColumnForm[MultinomialExpand[2, #] /. y -> (# y) & /@ Range[5]]
ColumnForm[MagicExpand[2, #] /. y -> (# y) & /@ Range[5]]

Out[]= ColumnForm[{
y - y^2 c[2] + 2 y^3 c[2]^2 - y^3 c[3], 
2 y - 2 y^2 c[3] + 5 y^3 c[3]^2 - 4 y^3 c[4], 
3 y - 3 y^2 c[4] + 9 y^3 c[4]^2 - 9 y^3 c[5], 
4 y - 4 y^2 c[5] + 14 y^3 c[5]^2 - 16 y^3 c[6], 
5 y - 5 y^2 c[6] + 20 y^3 c[6]^2 - 25 y^3 c[7]}]

Out[]= ColumnForm[{
y - y^2 c[2] + 2 y^3 c[2]^2 - y^3 c[3], 
2 y - 2 y^2 c[3] + 5 y^3 c[3]^2 - 4 y^3 c[4], 
3 y - 3 y^2 c[4] + 9 y^3 c[4]^2 - 9 y^3 c[5], 
4 y - 4 y^2 c[5] + 14 y^3 c[5]^2 - 16 y^3 c[6], 
5 y - 5 y^2 c[6] + 20 y^3 c[6]^2 - 25 y^3 c[7]}]

Out[]= ColumnForm[{
y - y^2 c[2] + 2 y^3 c[2]^2 - y^3 c[3], 
2 y - 2 y^2 c[3] + 5 y^3 c[3]^2 - 4 y^3 c[4], 
3 y - 3 y^2 c[4] + 9 y^3 c[4]^2 - 9 y^3 c[5], 
4 y - 4 y^2 c[5] + 14 y^3 c[5]^2 - 16 y^3 c[6], 
5 y - 5 y^2 c[6] + 20 y^3 c[6]^2 - 25 y^3 c[7]}]

In[]:= AbsoluteTiming[SameQ[
MagicExpand[15, #] & /@ Range[5],
MultinomialExpand[15, #] & /@ Range[5]
]]

Out[]= {4.61176, True}

In[]:= AbsoluteTiming[SameQ[
MmaExpand[10, #] & /@ Range[5],
MultinomialExpand[10, #] & /@ Range[5]
]]

Out[]= {9.79921, True}

Timing test for $n=1,2,3,4,5$

Time test

Time Vs. order of magnitude.

Not only is the mystery method the fastest, apparently it is also the most stable under change of leading term. I may try to prove this Stirling-Frobenius connection in my dissertation, but before I get into that I'm wondering: Is this algorithm already proven somewhere? Did Ferdinand Frobenius know about this? Are there Mma experts around here with an answer? Maybe Daniel Lichtblau will care to comment? Considering that Mma is going relatively slow and the optimization code is easy, I'm thinking that there's a possibility the methods here are not well known, possibly new.

POSTED BY: Brad Klee
Posted 10 years ago

Adapted Multinomial Algorithm

Comparing $n=2$ case above, and $n=1$ case here, it seems like the following simple algorithm could easily be generalized to revert any series with leading term order $n$ :

RExp[n_] := Expand[b Plus[R[0], Total[b^# R[#] & /@ Range[n]]]]
RCalc[n_] := 
With[{basis = Subtract[Tally[Join[Range[n + 1], #]][[All, 2]],
Table[1, {n + 1}]] & /@ IntegerPartitions[n + 1][[2 ;; -1]]},
Total@(Times[-1, Multinomial @@ #, v[Total[#]],
Times @@ Power[RSet[# - 1] & /@ Range[n + 1], #]] & /@ basis)]
InvSeries[n_] := AbsoluteTiming[
Clear@RSet; RSet[0] = 1; 
Set[RSet[#], Expand@RCalc[#]] & /@ Range[n];
Expand[RExp[n] /. R -> RSet]]

Updated Time Test

Time Test

Conceptually Simple method using multinomial coefficients fits in between slower Mma code and faster unproven method. This is the same time-behavior as seen in the case with leading quadratic term.

Challenge: Calculate series reversion with leading cubic leading term. Is there a regularization of the partition structure? Assuming yes, what is it? How does it relate to results for $n=1,2$ ?

POSTED BY: Brad Klee

enter image description here - Congratulations! This post is now Staff Pick! Thank you for your wonderful contributions. Please, keep them coming!

POSTED BY: EDITORIAL BOARD
Posted 10 years ago

Timing Test

Mysterious Mathematica Function ( ? )

Fast[m_] := Expand[Refine[Normal[
InverseSeries[ Series[f[x], {x, 0, m + 2}] /. Join[
{f[0] -> 0, (D[f[x], x] /. x -> 0) -> 
0, (D[f[x], {x, 2}] /. x -> 0) -> 
1/2}, ((D[f[x], {x, #}] /. x -> 0) -> #! \[Epsilon][#]) & /@
Range[3, m + 2]]]] /. x -> b^2/4, b > 0]]

Multinomial Method, A276738

(* with functions above *)
Faster[n_] := Module[{},
Clear@RSet; RSet[0] = 1; Set[RSet[#], Expand@RCalc[#]] & /@ Range[n];
Expand[b + RExp[n] /. R -> RCalc /. v -> \[Epsilon]]
]

Mystery via Triangle A028338 ( conjecture )

A028338[n_, k_] := Sum[(-2)^(n - i) Binomial[i, k] StirlingS1[n, i], {i, k, n}]

Polys[n_] := Total /@ Table[
A028338[i, j] (-1)^(j + 1) x^(j), {i, 0, n - 1}, {j, 0, i}];

T2[n_] := With[ {polys = Polys[n]},
Table[polys[[j]] /. x -> (2 j + i), {i, 1, n}, {j, 1, i}] ]

Basis[n_] := Total /@ Map[
Times[2^(Length[#] - 1)/Times @@ (Tally[#][[All, 2]]!), 
Times @@ (# /. x_Integer :> \[Epsilon][x + 2])] &,
Function[{a}, Select[IntegerPartitions[n], Length[#] == a &]] /@ 
Range[n],{2}]

Fastest[n_] := Expand[Plus[b,
Total@With[{tab = T2[n]}, 
2 Expand[Basis[#].tab[[#]] b^(# + 1)] & /@ Range[n]]]]

Output

In[14]:= Fast[2]
Faster[2]
Fastest[2]

Out[14]= b - 2 b^2 \[Epsilon][3] + 10 b^3 \[Epsilon][3]^2 - 
2 b^3 \[Epsilon][4]

Out[15]= b - 2 b^2 \[Epsilon][3] + 10 b^3 \[Epsilon][3]^2 - 
2 b^3 \[Epsilon][4]

Out[16]= b - 2 b^2 \[Epsilon][3] + 10 b^3 \[Epsilon][3]^2 - 
2 b^3 \[Epsilon][4]

More Testing

In[17]:= SameQ[Fast[5], Faster[5]]
SameQ[Faster[10], Fastest[10]]

Out[17]= True

Out[18]= True

Racing Functions

tFast = AbsoluteTiming[
Fast[#]
][[1]] & /@ Range[11]

tFaster = AbsoluteTiming[
Faster[#]
][[1]] & /@ Range[22]

tFastest = AbsoluteTiming[
Fastest[#]
][[1]] & /@ Range[35];

ListLinePlot[{tFast, tFaster, tFastest}, PlotRange -> All, 
ImageSize -> 600]

Race

So we see that $ T_{Mma} \gg T_{A276738} \gg T_{A028338} \approx 2(sec) $, where $T$ is the time to expand $30$ orders of magnitude !

Looks like it could be possible to improve the timing of "InverseSeries", at least in this interesting and useful case. It's also worthwhile to note that my code here for the mystery method could still be slow as it is easy to generate coefficients for $100$ orders of magnitude:

In[65]:= AbsoluteTiming[T2[100]][[1]]
Out[65]= 0.896722  

Wow! That is really fast.

I've seen GOSPER around here talking about fractals again. I'm wondering if we will hear from him regarding A028338, which he originally authored. For what purpose, Bill ?

POSTED BY: Brad Klee