interpret output of the guessing package

[Ralf Hemmecke]

Martin, Waldek,

can you tell me how I am supposed to interpret the result of this:

(153) -> guess([2,3,5,7,11,13,17,19])

(153)
[
s - 1 p - 1 s - 1
n - 1 8 7 6
--+ ++-++ --+ ++-++
> | | > - | | [f(p ): (p - 1)f(p ) + p - 1
= 0] + 2
--+ | | --+ | | 5 5 5 5
s = 0 p = 0 s = 0 p = 0
8 7 6 5
+
2
]

Thank you
Ralf

[Waldek Hebisch]

Martin can probably give better explanation, but I will try. 'guess'
tries to represent seqence as sums or product of simpler sequence
and is doing this recursivly. So we have sum of products of sums
of producs where inner term is f(p_5) and f satifies given
equation. There is display problem: first 2 is added to inner sum
(so we really should have parentheses around inner sum + 2).
Scalar term should be put before sum (but unfortunately current
diplay logic puts them last creating extra confusion).

Also, equation defines rational function. Looking at InputForm
I see that this is reccurence equation of order 0. 'guess'
probably should simplify this to rational function (in this case
constant 1).

Of course, as ususal there is trouble if we have enough data
to support out guess. Funnily, if I add next prime I get
the same formula, so it passes normal sanity check.

--
Waldek Hebisch

[Ralf Hemmecke]

OK the part inside the [] brackets should be interpreted as (let me
solve that equation): f(p5)=(1-p5)/(p5-1). So except for p5=1 f(p5)=-1
and can be anything if p5=1. Hmmm... Does that make sense? f(1) arbitrary?

I think the guessing package must improve on the output. Have you seen
that there is a minus sign in front of the last \prod symbol. That was
what confused me most. But probably that minus is just

(-1)*\prod [...]

. And, of course, the + 2 + 2 looks pretty strange.

Unfortunately, I cannot find where the display of %defprod is defined.

In fact, I find it pretty hard to work with the result. How to take that
apart to use in further computation if needed? Needs a tutorial.

Ralf

[Neven Sajko]

When I played around with Guess, I always used the LaTeX output
instead of the algebra output, it's possible that switching to tex
output fixes some of the issues.

Regards,
Neven

[Neven Sajko]

BTW, QuickLaTeX may be more convenient than a real TeX installation
for cases like these:

https://quicklatex.com

[Martin R]

The reason that the innermost terms (i.e., the factors in the product indexed by p_5 in your output) are given as a recurrence rather than the seemingly equivalent function f(p_5) = 1 is that they are in fact not equivalent.

The recurrence (p - 1) f(p) + p - 1 = 0 is satisfied also by f(0) = 1, f(1) = 1783, f(2) = f(3) = 1:

guessRec([1,1783,1,1])
[[f(n): (- n + 1)f(n) + n - 1 = 0]]
 

In general, if you get such a result, it is very likely wrong, but we cannot exclude the possibility that it is correct.

All the best, Martin

[Ralf Hemmecke]

> The reason that the innermost terms (i.e., the factors in the product
> indexed by p_5 in your output) are given as a recurrence rather than the
> seemingly equivalent function f(p_5) = 1 is that they are in fact not
> equivalent.

Yes, I understand this recurrence aspect.

> The recurrence (p - 1) f(p) + p - 1 = 0 is satisfied also by f(0) = 1, f(1)
> = 1783, f(2) = f(3) = 1:
>
> guessRec([1,1783,1,1])
> [[f(n): (- n + 1)f(n) + n - 1 = 0]]

> In general, if you get such a result, it is very likely wrong, but we
> cannot exclude the possibility that it is correct.

That raises the question, whether for the inner sequence you can do
something with initial values or do "arbitrary" values just appear and
are "summmed-away" by the possible outer sums?

A recurrence for the primes is of course a dream, but why does guess
gives me something for

guess([2,3,5,7,11,13])

and

guess([2,3,5,7,11,13,17,19])

but returns the empty list for guess([2,3,5,7,11,13,17])?
Is ist that you have not enough values to come up with the same formula
as with guess([2,3,5,7,11,13,17,19]) and one value too much to verify
that the formula for guess([2,3,5,7,11,13]) does not generate
[2,3,5,7,11,13,17]?

Still there is the question, how am I supposed to take the result apart
for further computation. That should be explained somewhere. You cannot
expect your users to know how the internals of Expression(Integer) are
to be handled.

Ralf

[Martin R]

I do not know how to take the result apart for further computations.  What you can do is "eval(result, n=17)".  Also, there is "getEq$RECOP" which gives you the equation of a recurrence.

The result is obtained by taking quotients and differences and then applying interpolation to the resulting sequence.  The degrees for interpolation are chosen so that the last term of the sequence can be used for checking.  I think the default is that the degrees are chosen as evenly as possible.  You have some control on the choice of degrees by using options.  For example, setting allDegrees to true will try all possible degree combinations.

In the case at hand, applying differences, quotients, differences, quotients (in this order) to [2, 3, 5, 7, 11, 13, 17, 19] you will obtain

[-1, -3/2, -1, -1]

Next, we apply a recurrence relation guesser to this list.  We successively try larger orders for the recurrence relation.  With order one, we are looking for a relation of the form

p(n) f(n) + q(n) = 0, with polynomials p and q.

Since we have 3 terms for the interpolation, we can choose p(n) and q(n) of degree 1, since this gives 3 unknowns a0, b1, b0 (note that we can multiply the equation with any nonzero number), i.e.,

(n + a0) f(n) + (b1 n + b0) = 0 for n=0, n=1 and n=2.

This gives

-a0 + b0 = 0,

-3/2 - 3/2 a0 + b1 + b0 = 0 and

-2 - a0 + 2 b1 + b0 = 0

and thus the result.  Since the final term of the original sequence also matches, guess yields the answer.

Martin

[Waldek Hebisch]

On Wed, Aug 24, 2022 at 09:42:54AM +0200, Ralf Hemmecke wrote:
>
> Still there is the question, how am I supposed to take the result apart for
> further computation. That should be explained somewhere. You cannot expect
> your users to know how the internals of Expression(Integer) are to be
> handled.

Well, at top level this is general expression, not different
from other expressions. You can get at details using 'kernels',
'operator' and 'arguments':

(8) -> guess([2,3,5,7,11,13,17,19])

(8)

[
s - 1 p - 1 s - 1
n - 1 8 7 6
--+ ++-++ --+ ++-++
> | | > - | | [f(p ): (p - 1)f(p ) + p - 1 = 0] + 2
--+ | | --+ | | 5 5 5 5
s = 0 p = 0 s = 0 p = 0
8 7 6 5
+
2
]

Type: List(Expression(Integer))
(9) -> res := %(1)

(9)

s - 1 p - 1 s - 1
n - 1 8 7 6
--+ ++-++ --+ ++-++

> | | > - | | [f(p ): (p - 1)f(p ) + p - 1 = 0] + 2 + 2

--+ | | --+ | | 5 5 5 5
s = 0 p = 0 s = 0 p = 0
8 7 6 5

Type: Expression(Integer)
(10) -> kernels(res)

(10)

s - 1 p - 1 s - 1
n - 1 8 7 6
--+ ++-++ --+ ++-++

[ > | | > - | | [f(p ): (p - 1)f(p ) + p - 1 = 0] + 2]

--+ | | --+ | | 5 5 5 5
s = 0 p = 0 s = 0 p = 0
8 7 6 5

Type: List(Kernel(Expression(Integer)))
(11) -> k1 := kernels(res)(1)

(11)

s - 1 p - 1 s - 1
n - 1 8 7 6
--+ ++-++ --+ ++-++
> | | > - | | [f(p ): (p - 1)f(p ) + p - 1 = 0] + 2
--+ | | --+ | | 5 5 5 5
s = 0 p = 0 s = 0 p = 0
8 7 6 5

Type: Kernel(Expression(Integer))
(12) -> operator(k1)

(12) %defsum
Type: BasicOperator
(13) -> argument(k1)

(13)

p - 1 s - 1

%M - 1 7 6
++-++ --+ ++-++
[ | | > - | | [f(p ): (p - 1)f(p ) + p - 1 = 0] + 2, %M, s ,
| | --+ | | 5 5 5 5 8

p = 0 s = 0 p = 0

7 6 5
0, n - 1]
Type: List(Expression(Integer))


For inner reccurence it is a bit more tricky as several interesting
things are hidden inside operator.

One can better see structure converting to InputForm:

(14) -> res::InputForm

(14)
(+

(sum

(product

(+

(sum

(* - 1

(product (rootOfRec %J (%inforec2))
(equation %J (SEGMENT 0 (+ %K - 1))))
)

(equation %K (SEGMENT 0 (+ %L - 1))))

2)

(equation %L (SEGMENT 0 (+ %M - 1))))

(equation %M (SEGMENT 0 (+ n - 1))))

2)
Type: InputForm

You can also use OutputForm, but it is more verbose and slightly
less informative. Note that OutputForm is OK, display problems
are in formatters.

--
Waldek Hebisch

[Kurt Pagani]

On 24.08.2022 09:42, Ralf Hemmecke wrote:
>> The reason that the innermost terms (i.e., the factors in the product

>

> Still there is the question, how am I supposed to take the result apart for
> further computation. That should be explained somewhere. You cannot expect your
> users to know how the internals of Expression(Integer) are to be handled.

Not? ;-)

Maybe, most simple:

f.1

(13)

s - 1 p - 1 s - 1
n - 1 8 7 6
--+ ++-++ --+ ++-++

> | | > - | | [f(p ): (p - 1)f(p ) + p - 1 = 0] + 2 + 2

--+ | | --+ | | 5 5 5 5
s = 0 p = 0 s = 0 p = 0
8 7 6 5

Type: Expression(Integer)
g:=f.1::InputForm

(15)

(+

(sum

(product

(+

(sum

(* - 1

(product (rootOfRec %F (%inforec1))
(equation %F (SEGMENT 0 (+ %G - 1))))
)

(equation %G (SEGMENT 0 (+ %H - 1))))

2)

(equation %H (SEGMENT 0 (+ %I - 1))))

(equation %I (SEGMENT 0 (+ n - 1))))

2)
Type: InputForm
car g

(16) +
Type: InputForm
cdr g

(17)
(

(sum

(product

(+

(sum

(* - 1

(product (rootOfRec %F (%inforec1))
(equation %F (SEGMENT 0 (+ %G - 1))))
)

(equation %G (SEGMENT 0 (+ %H - 1))))

2)

(equation %H (SEGMENT 0 (+ %I - 1))))

(equation %I (SEGMENT 0 (+ n - 1))))

2)
Type: InputForm




>
> Ralf
>

[Ralf Hemmecke]

> Note that OutputForm is OK, display problems are in formatters.

I have already found a stupid bug in my formatters. I had set a
precedence to MIN instead of p. :-(

Suppose we have the following:

f := operator 'f;
s1 := sum(f(i*j)+f(1), i=1..n1)
s2 := sum(s1+f(2), j=1..n2)

With my change I get the following as output.

\sum_{j=1}^{n2}
{\left(
\sum_{i=1}^{n1}
{\left(
f(i j)
+
f(1)
\right)}
+
f(2)
\right)}

If one adds the convention that "if \sum_{...}^{...} has a complex
argument it is enclosed in parentheses", then one can read that
expresssion without ambiguity. The convention basically says that
"\sum_{...}^{...}" is considered a function symbol where one can avoid
the parentheses around the argument if the argument is "simple". That is
somehow actually the SPAD way of avoiding parenthesis for univariate
functions.

Of course, without that convention, the expression might still look a
bit ambiguous for an ordinary mathematician. Is the "+f(2)" also summed
over in the inner sum?

However, adding too many parentheses looks generally ugly. And if I
simply convince the formatter to move the second open parenthesis in
front of the second sum sign, results in an unclear argument for the
inner sum (would the f(1) be under the inner sum or not?).

I think that the above convention would be a good compromise.

What's the opinion of others?

Ralf

[Waldek Hebisch]

On Wed, Aug 24, 2022 at 09:42:54AM +0200, Ralf Hemmecke wrote:
>

> A recurrence for the primes is of course a dream, but why does guess gives
> me something for
>
> guess([2,3,5,7,11,13])
>
> and
>
> guess([2,3,5,7,11,13,17,19])
>
> but returns the empty list for guess([2,3,5,7,11,13,17])?

Some values are used for checking, by default one value. You
can use more values if you specify safety paramenter. With
safety == 2 (two values for checking) most guesses are eliminated.
But still:

guess([2,3,5,7,11,13, 17, 19, 23], safety == 2)

gives result.

--
Waldek Hebisch