3
$\begingroup$

I have series of values which, by visual inspection, appear to be sums of certain constants, not divisible by each other, with rational weights. I want to convert these sums to vectors of weights for a specific basis vector.

I have an initial solution based on FindInstance, which works reasonably but I think is not necessarily elegant:

ClearAll[splitSumCoefficients];
splitSumCoefficients[sum_, basis_] := 
  With[{cvals = c /@ basis}, 
   cvals/d /. # & /@ 
    FindInstance[
     d sum == basis.cvals && d != 0, {Sequence @@ cvals, d}, 
     Integers]];

It works fine for a case where vector values could actually be extracted using expression rewriting:

# -> splitSumCoefficients[#, {1, 1/E, E}] & /@ 
 Table[TrigExpand@
   SeriesCoefficient[
    Sin[x] + Sqrt[1 - x^2] Sinh[Sqrt[1 - x^2]]/(x + 1),
    {x, 0, n}], {n, 0, 5}]

$$\begin{array}{c} \frac{e}{2}-\frac{1}{2 e}\to \left( \begin{array}{ccc} 0 & -\frac{1}{2} & \frac{1}{2} \\ \end{array} \right) \\ 1+\frac{1}{2 e}-\frac{e}{2}\to \left( \begin{array}{ccc} 1 & \frac{1}{2} & -\frac{1}{2} \\ \end{array} \right) \\ -\frac{1}{2 e}\to \left( \begin{array}{ccc} 0 & -\frac{1}{2} & 0 \\ \end{array} \right) \\ \frac{1}{2 e}-\frac{1}{6}\to \left( \begin{array}{ccc} -\frac{1}{6} & \frac{1}{2} & 0 \\ \end{array} \right) \\ \frac{e}{16}-\frac{7}{16 e}\to \left( \begin{array}{ccc} 0 & -\frac{7}{16} & \frac{1}{16} \\ \end{array} \right) \\ \frac{1}{120}+\frac{7}{16 e}-\frac{e}{16}\to \left( \begin{array}{ccc} \frac{1}{120} & \frac{7}{16} & -\frac{1}{16} \\ \end{array} \right) \\ \end{array}$$

It also works in a case where expression rewriting would already be a little more tricky:

# -> splitSumCoefficients[#, {1, Sinh[1], Cosh[1]}] & /@ 
   Table[SeriesCoefficient[
     Sin[x] + Sqrt[1 - x^2] Sinh[Sqrt[1 - x^2]]/(x + 1),
     {x, 0, n}], {n, 0, 5}]

$$\begin{array}{c} \sinh (1)\to \left( \begin{array}{ccc} 0 & 1 & 0 \\ \end{array} \right) \\ 1-\sinh (1)\to \left( \begin{array}{ccc} 1 & -1 & 0 \\ \end{array} \right) \\ \frac{1}{2} (\sinh (1)-\cosh (1))\to \left( \begin{array}{ccc} 0 & \frac{1}{2} & -\frac{1}{2} \\ \end{array} \right) \\ \frac{1}{6} (-1-3 \sinh (1)+3 \cosh (1))\to \left( \begin{array}{ccc} -\frac{1}{6} & -\frac{1}{2} & \frac{1}{2} \\ \end{array} \right) \\ \frac{\sinh (1)}{2}-\frac{3 \cosh (1)}{8}\to \left( \begin{array}{ccc} 0 & \frac{1}{2} & -\frac{3}{8} \\ \end{array} \right) \\ \frac{1}{120} (1-60 \sinh (1)+45 \cosh (1))\to \left( \begin{array}{ccc} \frac{1}{120} & -\frac{1}{2} & \frac{3}{8} \\ \end{array} \right) \\ \end{array}$$

(This code can also convert above expressions between $1/sinh/cosh$ and $1/\frac{1}{e}/e$ basis automatically.)

Would there be a more practical solution than FindInstance for this problem?

EDIT:

A failing example:

splitSumCoefficients[#, {1, Sinh[1], Cosh[1]}] &@
 SeriesCoefficient[
  Sin[x] + Sqrt[1 - x^2] Sinh[Sqrt[1 - x^2]]/(x + 1), {x, 0, 143}]

{}

(That is, no solutions from FindInstance.)

$\endgroup$
  • $\begingroup$ If your solution works for the cases you are interested in, then I can hardly think of a more practical solution :P Can you describe the improvements you seek? $\endgroup$ – Marius Ladegård Meyer Aug 11 '18 at 13:39
  • 1
    $\begingroup$ @MariusLadegårdMeyer I just now remembered what was the alternative, and why it doesn't seem to work for me. FindIntegerNullVector does work for small inputs, but fails for bigger ones as it seems to be essentially numerical method. A working example: -Rest@#/First@# &@ FindIntegerNullVector[{1/6227020800 + 27007/(92160 E) - (731 E)/ 18432, 1, 1/E, E}] ... (* {1/6227020800, 27007/92160, -(731/18432)} *) $\endgroup$ – kirma Aug 11 '18 at 13:49
  • $\begingroup$ @MariusLadegårdMeyer And my primary improvement in mind was elegance, or a particularly suitable algorithm for the task. I suspect FindInstance might also fail for some inputs! $\endgroup$ – kirma Aug 11 '18 at 13:50
  • $\begingroup$ I'm not sure if this will be of any use for your problem, but I have old code doing purely structural decomposition: decomposeInternal = GroupBy[Replace[ Factor@Replace[ Expand@#, {sum_Plus :> List @@ sum, expr_ :> {expr}}], {(c : _Integer | _Rational | _Real) x_. :> {c, x}, Complex[re_, im_] x_. :> Sequence[{re, x}, {im, I x}], x_ :> {1, x}}, {1}], Last -> First, Total] &; decompose@l_List := {Values@#, Keys@First[#, <||>]} &@ KeyUnion[decomposeInternal /@ l, 0 &]; decompose@expr_ := {Values@#, Keys@#} &@decomposeInternal@expr; $\endgroup$ – jkuczm Aug 11 '18 at 22:08
  • $\begingroup$ Sorrfy, I didn't pay attention to the comments. You already knew about FindIntegerNullVector. My guess is it failed because the Automatic precision is too low. $\endgroup$ – Daniel Lichtblau Aug 11 '18 at 22:36
5
$\begingroup$

Could use FindIntegerNullVector.

s143 = SeriesCoefficient[
   Sin[x] + Sqrt[1 - x^2] Sinh[Sqrt[1 - x^2]]/(x + 1), {x, 0, 143}];
ff = FindIntegerNullVector[{1, Sinh[1], Cosh[1], s143}, 
 WorkingPrecision -> 2000]

(* Out[141]= {1, \
3961260330770617476883241243800272591914813378841561500324133049366105\
0123701401772607848046869189487230434065769624598074056818708818344785\
0696665716427876426887640556807563267222769242157291176636056668271262\
5711003773130484745502258300781250000, \
-301687271813430245298615167128172580774085014946504395637814915763577\
7158504130808243502776912161388156812463524288595215733594917752859937\
3098739537990205122300228063774095483218191584013468406883227014757659\
90607108694209686634044834136962890625, \
3854370717180072770521565736493325081944432179154696438432688127620284\
5420193798918144180166658987031965483631719296696351202501036957071818\
6035253548159443361661549763406518875415055453101304885936693315514033\
76640000000000000000000000000000000000} *)

It is straightforward to check that this is the correct result. The desired form is simply -Most[ff]/Last[ff].

$\endgroup$
  • 1
    $\begingroup$ Is s18 supposed to be s143 (or vice versa)? And I think you want a minus sign on s18. $\endgroup$ – Michael E2 Aug 11 '18 at 22:37
  • $\begingroup$ @MichaelE2 Yes...I'll fix the s18 (a holdover from initial experiments). A minus sign can of course be used, or not, so long as one keeps track. I'll fix that too. $\endgroup$ – Daniel Lichtblau Aug 12 '18 at 14:12
3
$\begingroup$

This is really an extended comment to @DanielLichtblau's answer, touching the subject of WorkingPrecision. I arrived at this completely separately...

Essentially the improvement here is calculating necessary $MaxExtraPrecision on basis of input:

ClearAll[splitSumCoefficients];
splitSumCoefficients[sum_, basis_] := 
  Block[{$MaxExtraPrecision = (Length[basis] + 1) Ceiling[
       Length[basis] + 
        Log10[Max[1, #] &@
           Max@Cases[Expand@Simplify@sum, 
             x_Integer | x_Rational :> 
              Max[Abs@Numerator@x, Denominator@x], Infinity]/
          Min@Abs@basis]]}, 
   Quiet@FindIntegerNullVector[
      Append[-basis, 
       sum]] /. {_FindIntegerNullVector -> {},
                 {most__: 1, last_} :> {{most}/last}}];

(Returning {} on failure, and handling special cases gracefully like one -element basis and no-integer/rational sum too.)

Testing it:

FullSimplify[# == {1, Sinh[1], Cosh[1]}.First@
      splitSumCoefficients[#, {1, Sinh[1], Cosh[1]}]] &@
 SeriesCoefficient[
  Sin[x] + Sqrt[1 - x^2] Sinh[Sqrt[1 - x^2]]/(x + 1), {x, 0, 143}]

True

Examples of use:

splitSumCoefficients[5/3, {1}]

{{5/3}}

splitSumCoefficients[1 + 5 E, {1, E}]

{{1, 5}}

splitSumCoefficients[E, {1, Sqrt[2]}]

{}

splitSumCoefficients[E, {Sinh[1], Cosh[1]}]

{{1, 1}}

($e=\sinh (1)+\cosh (1)$)

$\endgroup$
  • 2
    $\begingroup$ I like it (and upvoted of course). But the general rule for using PSLQ-type methods is that the internal precision required is heavily dependent on output integer sizes. In the common case where one is dealing with algebraic numbers, this is directly related to degree and height of (expected) algebraic relations. For polynomial factorization the degree and height of input give bounds on those output parameters. $\endgroup$ – Daniel Lichtblau Aug 12 '18 at 14:20
  • $\begingroup$ @DanielLichtblau Yeah, my extra precision calculations are definitely quite ad hoc, but seem to work in this case where integers in input and output are... well, for my original case, essentially identical. $\endgroup$ – kirma Aug 12 '18 at 14:25
  • 1
    $\begingroup$ You do have c^2-s^2-1 as an algebraic relation. I do not knwo if that helps for getting a bound on needed precision though. I guess it depends on how much you know about where the constant you want to match came from. $\endgroup$ – Daniel Lichtblau Aug 13 '18 at 13:39
  • 1
    $\begingroup$ I saw a recent paper that suggests somewhat more than twice the output size is in general required for working precision. There might also have been a scale factor to account for the size of the basis. I simply cannot recall the reference though (short term memory is...what was I writing?) $\endgroup$ – Daniel Lichtblau Aug 13 '18 at 15:06
  • 2
    $\begingroup$ Found it! The PSLQ algorithm for empirical data $\endgroup$ – Daniel Lichtblau Aug 13 '18 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.