get k-regular sequence from certain recurrence relations

[galipnik]

Code for constructing the linear representation of k-regular sequences given by certain recurrence relations.

See also Meta ticket #21202.

Depends on #21295 Depends on #21203

CC: @dkrenn

Component: combinatorics

Author: Gabriel F. Lipnik, Daniel Krenn

Branch/Commit: 488123c

Reviewer: Clemens Heuberger, Daniel Krenn

Issue created by migration from https://trac.sagemath.org/ticket/27940

[embray]

comment:2

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3b7c866 to d367496

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

9e0f817	Merge tag '8.8' into u/galipnik/k-regular-recursions
0b03904	ccMerge tag '8.9' into u/galipnik/k-regular-recursions
d367496	n0 as input for _parse_recursions_

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c2c47e0	implement correction for n0
7d47dbe	add examples

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d367496 to 7d47dbe

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c2d9903

add another example

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7d47dbe to c2d9903

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

98c24d1

start_values --> initial_values

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c2d9903 to 98c24d1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

060ca25

add doc-strings

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 98c24d1 to 060ca25

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

eb44f15	start to implement correction for initial values
6aff6b4	Merge branch 'u/galipnik/k-regular-recursions' of git://trac.sagemath.org/sage into u/galipnik/k-regular-recursions

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 060ca25 to 6aff6b4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

b411bda	fix bug from merge
5a7d293	add n1 to recursion_rules
b0f0e1b	some fixes for n1 and dim

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6aff6b4 to b0f0e1b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

9ced30c	adapt tests
0bdf2e1	adapt definition of l and u
a29d29b	add _get_ind_
b36adac	fix constructions

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b0f0e1b to b36adac

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b36adac to d0fe273

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

d0fe273

adapt construction of W and J

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d0fe273 to 2edf0cf

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

49850eb	adapt docstring
78e21ac	more changes in docstrings
2edf0cf	refactor

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2edf0cf to 9b454f9

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

9b454f9

some more changes in the docstring...

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

46fc3e5	fix link to :meth:minimized
1e43197	some more updates

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9b454f9 to 1e43197

[galipnik]

New commits:

46fc3e5	fix link to :meth:minimized
1e43197	some more updates

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c0fdfbb

n0 --> offset

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1e43197 to c0fdfbb

[cheuberg]

Reviewer: Clemens Heuberger

[cheuberg]

comment:17

1. Dependencies: It seems that many more branches are merged here than necessary. Please fill out the dependencies field here.

2. Fix patchbot findings

3. recursions: description of the equations parameter: I am not sure whether writing it as sum(...) can cause any confusion. I propose to write some summands with ....

4. recursions: description of the equations parameter: I guess you want to include some coefficients in front of the terms on the right hand side.

5. recursions: dead link to minimized() in description of parameter minimize

6. _parse_recursions_: catch AttributeError when a non-element of the symbolic ring is given as an equation: Seq2._parse_recursions_([42], f, n)

7. _parse_recursions_ before throwing %s is not a polynomial: I think that explicitly naming the exceptions which are likely to occur in the conversion attempt to a polynomial is preferred over generically catching Exception.

8. _parse_recursion_: base_ring[var](left_side.operands()[0]) I am unsure whether base_ring is the correct ring here. After all, arguments of a regular sequence will alwys be the integers. A few lines later, there is ZZ[var](left_side.operands()[0]) which seems to be the ring we need to use. So my suggestion is to always use ZZ[var] and polynomial_left and removing poly_left. Also, polynomial_left in base_ring does not seem to be the correct ring.

9. _parse_recursion_: initial_values.update({polynomial_left: right_side}) I suggest to check whether an initial value is repeatedly given.

10. _parse_recursion_: if M != log(base_power_M, base=k): I suggest to replace the right hand side by M_new which has just been defined one line before.

11. _parse_recursion_: if r not in ZZ: raise ValueError("%s is not an integer." % (r,)): I do not think that this can be reached: r is a coefficient of a polynomial over ZZ anyway. In particular, Seq2._parse_recursions_([f(2*n+1/2) == f(n)], f, n) leads to ValueError: 2*n + 1/2 is not a polynomial in n.

12. _parse_recursion_: else: # check this again I do not understand the comment.

13. _parse_recursion_._parse_multiplication_: I think that if op.operator() != mul_vararg or len(op.operands()) != 2: raise ValueError("") is unreachable, so I suggest to replace this by assert op.operator() == mul_vararg and len(op.operands()) == 2.

14. _parse_recursion_._parse_one_summand_: raise ValueError('%s does not have integer coefficients.' % (op.operands()[0],)): The error message does not seem to fit all cases of failing conversion to an integer polynomial; e.g., Seq2._parse_recursions_([f(2*n+1) == 2*f(1/n)], f, n) yields `ValueError: 1/n does not have integer coefficients.

15. _parse_recursion_._parse_one_summand_: It should be checked that len(op.operands()) == 1; currently, Seq2._parse_recursions_([f(2*n+1) == 2*f(n+4, 5), f(2*n) == f(n)], f, n) does not yield an error.

16. _parse_recursion_: Branch if not coeffs: As far as I understand, this means that no general equations have been given, only initial values. I do not understand why we do not raise an error in this case.

17. __get_ind_: I would replace the two consecutive .update calls to the same dictionary by one single call .update({(j, d): pos, pos: (j, d)}) (twice)

18. _parse_recursion_: docstring: I think that even for a private method, the contents of the namedtuple should be explained.

19. _get_ind_ docstring: I think that even for a private method, the output should be explained.

20. _get_matrix_from_recursions_ docstring: inputs var and function are not explained.

21. _get_matrix_from_recursions_ docstring: Please explain what the role of the parameter correct_offset is.

22. _get_matrix_from_recursions_ example on the number of unbordered factors in the Thue–Morse sequence: please only put one recurrence equation per line in order to make the recurrences more readable.

23. _get_matrix_from_recursions_ example on the number of unbordered factors in the Thue–Morse sequence: why are there so many initial values? If my calculations are correct, then the "largest" component of the linear representation corresponds to the sequence f(4n+9); for n=3, this is f(21). It might be that this large number of initial values is required in the current code, but I think that the original recurrences could and should be used to compute as many auxiliary values as required. This means that only initial values up to 15 should be required.

24. _get_matrix_from_recursions_: the line n1 = recursion_rules.n1 appears twice.

25. _get_matrix_from_recursions_: I think that the lines which define temp twice in different ways are rather hard to read. If (as suggested in 22) the required auxiliary values are computed from the initial values in a separate method, then I imagine that these lines could be simply replaced by suitable list comprehensions. The symbolic vector arguments could be replaced by a function taking an argument and returning a vector, so no substitutions would be required. Then it might not be necessary to have function and var as parameters of this method.

26. _get_matrix_from_recursions_: the condition for construction the matrix J could be simplified: the conditions i>= rem and i % k == rem can be omitted, because they follow from j*k == i-rem. Additionally, it might be simpler to construct this matrix by the version of the matrix constructor which takes a function as an argument.

27. _get_right_from_recursions_: The same comment about initial values as mentioned in 22 applies. If a separate method for computing the vector of the linear representation for given arguments is implemented as proposed in 24, then this method here could be shortened considerably. The parameter function might then be redundant.

28. recursions: example Stern--Brocot: The initial value f(2) should not be required.

29. recursions: example Odd Entries in Pascal's Triangle: only f(0) and f(1) should be required as initial values.

30. recursions: example Unbordered Factors: one equation per line (cf. 21)

31. recursions: example Unbordered Factors: initial values (cf. 22)

32. recursions: docstring: "in the a Generalized" remove "a"

33. recursions: "[TODO: reference]" please resolve TODO.

34. recursions: example Generalized Pascal's Triangle: only initial values f(0) and f(1) should be required.

35. recursions: mu could be constructed as a list comprehension instead of appending to a list.

36. This ticket adds quite a number of private methods to kRegularSequenceSpace which are only useful for the public method recursions. For clarity's sake, I propose to introduce a "see also" block in all auxiliary private methods which refers to recursions.

37. The method _get_ind_ should be renamed such that it clearly relates to the main public method (this is now the case for all other private methods except this one).

38. I am not yet convinced that kRegularSequenceSpace.recursions is a good description of the method. Wouldn't one expect to get recursions by such a method, instead of getting a k-regular sequence from a recursion? Perhaps from_recursion or possibly more precise from_recurrence would be a better name.

39. Please extend the docstring of recursions in such a way that a clearer link is provided to [HKL2021]. For instance, the docstring could state that such recurrence relations uniquely define a k regular sequence (provided that enough initial values are provided).

40. Test raising "Initial value ... is missing".

41. Consider using raise ValueError(...) from None (once this code runs under python3) in order to supress printing of the detailed exceptions which are explained by the ValueError of this code here.

[galipnik]

Dependencies: #21295, #21203

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

f624a55	14: correct error message
2e9d120	15: check if function has exactly one argument, add more test cases
3bdbc42	17: simplify updates of dictionary
a221579	20: fix docstring
467efdc	21: explain what the role of the parameter correct_offset
e9bc2e5	22: one equation per line
208a012	23: remove one n1
96a7df3	23: move n1
b7a3b65	25a: simplify defintion of J
a4ea503	one equation per line

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c0fdfbb to a4ea503

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a4ea503 to 988aa85

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

247f1d1	31: remove "a"
945a5f9	32: add reference
90f3b35	34: list comprehension for mu
b3439db	fix references
a654803	35: add "see also" blocks
342c2d3	36: `_get_ind_` --> _get_ind_from_recursions_
175567e	37: rename main method to from_recurrence
ab93a12	37: recursion --> recurrence
ee4c131	39: add test for missing initial value
988aa85	38: add some info

[galipnik]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
-Code for constructing the linear representation of k-regular sequences given by recursions.
+Code for constructing the linear representation of k-regular sequences given by certain recurrence relations.

 See also Meta ticket #21202.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 988aa85 to 66847f1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

d5f4e77	3 + 4: change description of from_recurrence
7a05722	3 + 4: change description again
e037de7	5: fix link
5ceaac7	minor improvement in docstrings
66847f1	22a: start implementing method for initial values

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

04d7688	Revert "22a: start implementing method for initial values"
f9d8781	18: add description to namedtuple
8706ea1	19: add description for the output

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 66847f1 to 8706ea1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8706ea1 to 2964270

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

5001b6c	fix parsing intial values
2964270	Merge branch 'u/galipnik/k-regular-recursions' of trac.sagemath.org:/sage into u/galipnik/k-regular-recursions

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2964270 to e495b2e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

e495b2e

13: add assert

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e495b2e to 9be7469

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

476da16	more specific description of initial values
b9bcd44	validate offset
17fc95b	add tests for offset
b75b729	modify one test
41c133a	change docstring
9be7469	start refactoring

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

ab940aa

add some docstring, minor changes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9be7469 to ab940aa

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

368da7a	many adaptations...
88bc3e9	22b: remove redundant initial values
da8e9e1	27, 28, 30, 33: remove redundant initial values
6261302	24a: add method
56c1d86	24 + 26: simplify a lot
d7c9e9f	simplify _get_matrix_from_recurrence_
96fbad8	add negative initial values

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ab940aa to 96fbad8