Opened 2 years ago

Last modified 25 hours ago

#27940 needs_review enhancement

get k-regular sequence from certain recurrence relations

Reported by: galipnik Owned by:
Priority: major Milestone: sage-9.4
Component: combinatorics Keywords:
Cc: dkrenn Merged in:
Authors: Gabriel F. Lipnik Reviewers: Clemens Heuberger
Report Upstream: N/A Work issues:
Branch: u/galipnik/k-regular-recurions-rebased (Commits, GitHub, GitLab) Commit: 2c36297b26affe1927841d34d696569c47261af5
Dependencies: #21295, #21203 Stopgaps:

Status badges

Description (last modified by galipnik)

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

See also Meta ticket #21202.

Change History (54)

comment:1 Changed 2 years ago by galipnik

  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 2 years ago by embray

  • Milestone sage-8.8 deleted

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).

comment:3 Changed 17 months ago by git

  • Commit changed from 3b7c866efb138160546f1234f617e8a0236184f5 to d367496e87a296bd378a0faa245c128d17e0fbd6

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

9e0f817Merge tag '8.8' into u/galipnik/k-regular-recursions
0b03904ccMerge tag '8.9' into u/galipnik/k-regular-recursions
d367496n0 as input for _parse_recursions_

comment:4 Changed 17 months ago by git

  • Commit changed from d367496e87a296bd378a0faa245c128d17e0fbd6 to 7d47dbe10eac8d72f97da84f8f407f11623ca01e

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

c2c47e0implement correction for n0
7d47dbeadd examples

comment:5 Changed 17 months ago by git

  • Commit changed from 7d47dbe10eac8d72f97da84f8f407f11623ca01e to c2d99036fc8362355cb2c0ab39459f69085cc740

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

c2d9903add another example

comment:6 Changed 17 months ago by git

  • Commit changed from c2d99036fc8362355cb2c0ab39459f69085cc740 to 98c24d13edf8e8d21ed3f714f728cf419b2489e3

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

98c24d1start_values --> initial_values

comment:7 Changed 17 months ago by git

  • Commit changed from 98c24d13edf8e8d21ed3f714f728cf419b2489e3 to 060ca255156048704e1f96c08f119926053a6db7

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

060ca25add doc-strings

comment:8 Changed 3 months ago by git

  • Commit changed from 060ca255156048704e1f96c08f119926053a6db7 to 6aff6b459a343a2bdd3db81c96b71e4ab0c21727

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

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

comment:9 Changed 3 months ago by git

  • Commit changed from 6aff6b459a343a2bdd3db81c96b71e4ab0c21727 to b0f0e1bc18bf0cc768c85d9bbdc64912500f9c33

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

b411bdafix bug from merge
5a7d293add n1 to recursion_rules
b0f0e1bsome fixes for n1 and dim

comment:10 Changed 3 months ago by git

  • Commit changed from b0f0e1bc18bf0cc768c85d9bbdc64912500f9c33 to b36adac731c5942b7cd366773ff0ca43fd760f76

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

9ced30cadapt tests
0bdf2e1adapt definition of l and u
a29d29badd _get_ind_
b36adacfix constructions

comment:11 Changed 3 months ago by git

  • Commit changed from b36adac731c5942b7cd366773ff0ca43fd760f76 to d0fe273b9a73f002bac4067f3a9a15d15776346e

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

d0fe273adapt construction of W and J

comment:12 Changed 2 months ago by git

  • Commit changed from d0fe273b9a73f002bac4067f3a9a15d15776346e to 2edf0cf7c99f54f65b5deb6867bed7b77fb333a0

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

49850ebadapt docstring
78e21acmore changes in docstrings
2edf0cfrefactor

comment:13 Changed 2 months ago by git

  • Commit changed from 2edf0cf7c99f54f65b5deb6867bed7b77fb333a0 to 9b454f995a67f9165e536cee795830fb915f6f36

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

9b454f9some more changes in the docstring...

comment:14 Changed 2 months ago by git

  • Commit changed from 9b454f995a67f9165e536cee795830fb915f6f36 to 1e43197edc1d133de87998dca357c4f27f0829ea

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

46fc3e5fix link to :meth:minimized
1e43197some more updates

comment:15 Changed 2 months ago by galipnik

  • Status changed from new to needs_review

New commits:

46fc3e5fix link to :meth:minimized
1e43197some more updates

comment:16 Changed 2 months ago by git

  • Commit changed from 1e43197edc1d133de87998dca357c4f27f0829ea to c0fdfbb4fe30272b41e6aea62b580416b85f48cd

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

c0fdfbbn0 --> offset

comment:17 follow-up: Changed 3 weeks ago by cheuberg

  • Milestone set to sage-9.4
  • Reviewers set to Clemens Heuberger
  • Status changed from needs_review to needs_work
  1. Dependencies: It seems that many more branches are merged here than necessary. Please fill out the dependencies field here.
  1. Fix patchbot findings
  1. 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 ....
  1. recursions: description of the equations parameter: I guess you want to include some coefficients in front of the terms on the right hand side.
  1. recursions: dead link to minimized() in description of parameter minimize
  1. _parse_recursions_: catch AttributeError when a non-element of the symbolic ring is given as an equation: Seq2._parse_recursions_([42], f, n)
  1. _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.
  1. _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.
  1. _parse_recursion_: initial_values.update({polynomial_left: right_side}) I suggest to check whether an initial value is repeatedly given.
  1. _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.
  1. _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.
  1. _parse_recursion_: else: # check this again I do not understand the comment.
  1. _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.
  1. _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.
  1. _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.
  1. _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.
  1. __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)
  1. _parse_recursion_: docstring: I think that even for a private method, the contents of the namedtuple should be explained.
  1. _get_ind_ docstring: I think that even for a private method, the output should be explained.
  1. _get_matrix_from_recursions_ docstring: inputs var and function are not explained.
  1. _get_matrix_from_recursions_ docstring: Please explain what the role of the parameter correct_offset is.
  1. _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.
  1. _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.
  1. _get_matrix_from_recursions_: the line n1 = recursion_rules.n1 appears twice.
  1. _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.
  1. _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.
  1. _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.
  1. recursions: example Stern--Brocot: The initial value f(2) should not be required.
  1. recursions: example Odd Entries in Pascal's Triangle: only f(0) and f(1) should be required as initial values.
  1. recursions: example Unbordered Factors: one equation per line (cf. 21)
  1. recursions: example Unbordered Factors: initial values (cf. 22)
  1. recursions: docstring: "in the a Generalized" remove "a"
  1. recursions: "[TODO: reference]" please resolve TODO.
  1. recursions: example Generalized Pascal's Triangle: only initial values f(0) and f(1) should be required.
  1. recursions: mu could be constructed as a list comprehension instead of appending to a list.
  1. 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.
  1. 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).
  1. 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.
  1. 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).
  1. Test raising "Initial value ... is missing".
  1. 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.

comment:18 Changed 3 weeks ago by galipnik

  • Dependencies set to #21295, #21203

comment:19 Changed 3 weeks ago by git

  • Commit changed from c0fdfbb4fe30272b41e6aea62b580416b85f48cd to a4ea50353838b6a2f26c0550ede78dce5cc03a60

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

f624a5514: correct error message
2e9d12015: check if function has exactly one argument, add more test cases
3bdbc4217: simplify updates of dictionary
a22157920: fix docstring
467efdc21: explain what the role of the parameter correct_offset
e9bc2e522: one equation per line
208a01223: remove one n1
96a7df323: move n1
b7a3b6525a: simplify defintion of J
a4ea503one equation per line

comment:20 Changed 3 weeks ago by git

  • Commit changed from a4ea50353838b6a2f26c0550ede78dce5cc03a60 to 988aa854cc1880933a3d68b5a58955187f1a0a86

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

247f1d131: remove "a"
945a5f932: add reference
90f3b3534: list comprehension for mu
b3439dbfix references
a65480335: add "see also" blocks
342c2d336: _get_ind_ --> _get_ind_from_recursions_
175567e37: rename main method to from_recurrence
ab93a1237: recursion --> recurrence
ee4c13139: add test for missing initial value
988aa8538: add some info

comment:21 Changed 2 weeks ago by galipnik

  • Description modified (diff)

comment:22 Changed 2 weeks ago by galipnik

  • Summary changed from get k-regular sequence from recursions to get k-regular sequence from certain recurrence relations

comment:23 Changed 2 weeks ago by git

  • Commit changed from 988aa854cc1880933a3d68b5a58955187f1a0a86 to 66847f1f2689a71c974111dbbeda60cc50783673

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

d5f4e773 + 4: change description of from_recurrence
7a057223 + 4: change description again
e037de75: fix link
5ceaac7minor improvement in docstrings
66847f122a: start implementing method for initial values

comment:24 Changed 2 weeks ago by git

  • Commit changed from 66847f1f2689a71c974111dbbeda60cc50783673 to 8706ea1ab9e631c656b441775facfaae78d06259

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

04d7688Revert "22a: start implementing method for initial values"
f9d878118: add description to namedtuple
8706ea119: add description for the output

comment:25 Changed 2 weeks ago by git

  • Commit changed from 8706ea1ab9e631c656b441775facfaae78d06259 to 296427083f100271d3bb3f5df5eff66474e9e5a9

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

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

comment:26 Changed 2 weeks ago by git

  • Commit changed from 296427083f100271d3bb3f5df5eff66474e9e5a9 to e495b2e05cb5221fd6c3601216ffec9780bc3fd7

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

e495b2e13: add assert

comment:27 Changed 12 days ago by git

  • Commit changed from e495b2e05cb5221fd6c3601216ffec9780bc3fd7 to 9be7469499b8093d81a6c95ba7001dffa1418d1d

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

476da16more specific description of initial values
b9bcd44validate offset
17fc95badd tests for offset
b75b729modify one test
41c133achange docstring
9be7469start refactoring

comment:28 Changed 12 days ago by git

  • Commit changed from 9be7469499b8093d81a6c95ba7001dffa1418d1d to ab940aa3fc983f71babd80b7d5072ec2ae1380ee

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

ab940aaadd some docstring, minor changes

comment:29 Changed 11 days ago by git

  • Commit changed from ab940aa3fc983f71babd80b7d5072ec2ae1380ee to 96fbad885a9cdbe5a6543830979bdac8a01d3824

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

368da7amany adaptations...
88bc3e922b: remove redundant initial values
da8e9e127, 28, 30, 33: remove redundant initial values
626130224a: add method
56c1d8624 + 26: simplify a lot
d7c9e9fsimplify _get_matrix_from_recurrence_
96fbad8add negative initial values

comment:30 Changed 11 days ago by git

  • Commit changed from 96fbad885a9cdbe5a6543830979bdac8a01d3824 to 8f538875eb20bcf814a0da297bdbed9741e692a8

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

b3d2cbefix identation of docstring
6bd41cdadd further doctests
8f53887some further improvements

comment:31 Changed 11 days ago by git

  • Commit changed from 8f538875eb20bcf814a0da297bdbed9741e692a8 to c63d08e221968e689464531e045e7aefdae7e0ce

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

1d9a42crename k to j in some indices
c63d08efurther minor improvements

comment:32 Changed 11 days ago by git

  • Commit changed from c63d08e221968e689464531e045e7aefdae7e0ce to 92ef82fb6f016836bce103236bc17ccc471c572e

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

92ef82fremove redundant arguments of _get_matrix_

comment:33 Changed 11 days ago by galipnik

  • Status changed from needs_work to needs_review

comment:34 Changed 11 days ago by git

  • Commit changed from 92ef82fb6f016836bce103236bc17ccc471c572e to d9a5322d62dc039cd93ebf250f874ed9ce24b8ed

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

d9a5322recursion --> recurrence

comment:35 Changed 10 days ago by git

  • Commit changed from d9a5322d62dc039cd93ebf250f874ed9ce24b8ed to 9ade52bec3c9a2b8eb07a11abd2ea8d3803c0683

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

9ade52bfurther doctests

comment:36 follow-up: Changed 9 days ago by cheuberg

  • Branch changed from u/galipnik/k-regular-recursions to u/cheuberg/k-regular-recursions-rebased
  • Commit changed from 9ade52bec3c9a2b8eb07a11abd2ea8d3803c0683 to fa9bed3c3c213b827af048ea0585daa459eed63b

I rebased the branch such that it only contains material from the dependencies #21295, #21203 plus the changes pertinent to this ticket.

More precisely, I rebased commits from 4fe100c576 to eb44f15e6e onto #21203 and then commits from 0b039048e6 until the current branch u/galipnik/k-regular-recursions on top of that.

@galpnik: Please cross-review this rebase.

I will review your changes after that.


Last 10 new commits:

d0676a8simplify _get_matrix_from_recurrence_
430d0f2add negative initial values
85e2200fix identation of docstring
3f074feadd further doctests
15a3607some further improvements
4e33084rename k to j in some indices
0d6707cfurther minor improvements
72d8e32remove redundant arguments of _get_matrix_
642b4d3recursion --> recurrence
fa9bed3further doctests

comment:37 Changed 9 days ago by galipnik

  • Branch changed from u/cheuberg/k-regular-recursions-rebased to u/galipnik/k-regular-recurions-rebased

comment:38 Changed 9 days ago by git

  • Commit changed from fa9bed3c3c213b827af048ea0585daa459eed63b to 61d6c6ef938f864f0ba6637d9d8a40e85571678b

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

da90fc5Trac #27940: import cached_function again
8225c71Trac #27940: change order of elements in output dictionaries of some tests
61d6c6eTrac #27940: remove superfluous import of ceil

comment:39 in reply to: ↑ 36 Changed 9 days ago by galipnik

Replying to cheuberg:

@galpnik: Please cross-review this rebase.

Thank you! Three new commits pushed, the rest LGTM.

comment:40 Changed 5 days ago by galipnik

  • Status changed from needs_review to needs_work

comment:41 Changed 3 days ago by git

  • Commit changed from 61d6c6ef938f864f0ba6637d9d8a40e85571678b to 43e892e0fd690a3721ab016f4b0b4546c42d2ac1

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

6031c8cTrac #27940: fix pyflakes findings
43e892eTrac #27940: 40: add "from None"

comment:42 in reply to: ↑ 17 Changed 3 days ago by galipnik

Here is a more detailed answer to your review:

Replying to cheuberg:

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

Done. See also comment:36.

  1. Fix patchbot findings

Done.

  1. 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 ....

Done and printed in LaTeX.

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

Done.

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

Fixed.

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

Done and test case added.

  1. _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.

Done.

  1. _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.

Done.

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

Done: If the values are different for same n, then an exception is raised.

  1. _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.

Done.

  1. _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.

Fixed.

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

Removed.

  1. _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.

Yes, I agree. Done.

  1. _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.

I have modified this.

  1. _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.

Exception added.

  1. _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.

No, this can also happen for the zero sequence, like f(2*n) == 0, f(2*n + 1) == 0. After refactoring the parsing method, this case is handled in lines 835 and 933 now.

  1. __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)

Done.

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

Done.

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

Done.

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

These inputs are not needed anymore.

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

Done.

  1. _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.

Done.

  1. _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.

New method _get_values_from_recurrence_ has been implemented now. Consequently, only values up to f(23) are needed.

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

Removed.

  1. _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.

New method _v_eval_n_from_recurrence_ has been implemented now. Consequently, _get_matrix_from_recursions_ is much simpler now.

  1. _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.

I removed the redundant conditions. I do not understand the suggestion in your last sentence.

  1. _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.

Done.

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

Removed.

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

Removed.

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

Done.

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

Done.

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

Done.

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

Done.

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

Done.

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

Done.

  1. 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.

Done.

  1. 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).

Done.

  1. 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.

Changed to from_recurrence.

  1. 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).

Done.

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

This exception is removed now, because the method _get_values_from_recurrence_ checks this.

  1. 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.

Done.

comment:43 Changed 3 days ago by galipnik

  • Status changed from needs_work to needs_review

comment:44 follow-up: Changed 2 days ago by cheuberg

  • Status changed from needs_review to needs_work

Thank you for your changes and comments.

One reply and a few more comments which came up while reading your changes.

  1. _get_matrix_from_recursions_ [...] Additionally, it might be simpler to construct this matrix by the version of the matrix constructor which takes a function as an argument.

[...]. I do not understand the suggestion in your last sentence.

It meant rewriting it as follows:

def entry(i, kk):
    j, d = ind [i]
    if j < M - 1:
        return int(kk == ind[(j + 1, k**j*rem + d)] - 1)
    else:
        rem_d = k**(M-1)*rem + (d%k**M)
        dd = d // k**M
        if rem_d < k**M:
            lambd = l - ind[(m, (k**m)*dd + l)]
            return _coeff_(rem_d, kk + lambd)
        else:
            lambd = l - ind[(m, k**m*dd + k**m + l)]
            return _coeff_(rem_d - k**M, kk + lambd)

mat = Matrix(base_ring, dim_without_corr, dim_without_corr, entry)
  1. Naming of the variable in docstrings. In some docstrings, we have "a symbolic variable n" or similar formulations. I think that we should not make any assumptions about the name of the variable, it is simply a variable. There might be an exception in those docstrings where equations are parsed, there I would say "symbolic variable (n in the above description of equations).
  1. Naming of the variable in exceptions: Some exceptions have a hard-coded n. I think that it would be more helpful to use the variable name provided by the user. It might also be good to have one test with different names for function and variable.
  1. _get_right_from_recurrence_: Docstring: Please move the "see also" block before the "tests" block (I think that we should adhere to the order of the blocks as described in https://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content)
  1. from_recurrence: Please document parameter offset explicitly (e.g. "an integer (default: 0). See explanation in equations above")
  1. _get_values_from_recurrence_: if _coeff_(r, j) != 0 could be replaced by if _coeff_(r, j)
  1. _get_values_from_recurrence_: the check f_n not in base_ring could come earlier (when checking the provided parameters, not (possibly repeatedly) on usage
  1. _parse_recurrence_: docstring: replace "vector" by "tuple"
  1. _parse_recurrence_: why is remainders a list instead of a set?
  1. _parse_recurrence_: elif M and not m: I think that this should be replaced by elif M and m is None:: Otherwise, I fear that legitimate situations such as M=3, m=0 with a bunch of equations might be erroneously corrected to M=3, m=2.
  1. _get_parameters_from_recurrence_: offset = max(0, -l/k**m): possibly take ceiling of -l/k**m to have an integer offset?
  1. In the old code, there were two tests
    sage: Seq2._parse_recurrence_([f(2*n) == f(n)], f, n)
    Traceback (most recent call last):
    ...
    ValueError: Recurrence relations for [f(2*n + 1)] are missing.
    
    sage: Seq2._parse_recurrence_([f(4*n) == f(n), f(4*n + 3) == 0], f, n)
    Traceback (most recent call last):
    ...
    ValueError: Recurrence relations for [f(4*n + 1), f(4*n + 2)] are missing.
    

which seem not to have survived the refactoring. If I am not mistaken, the corresponding checks are no longer there.

  1. I suggest to always call _get_values_from_recurrence_ with named parameters (there is now quite a number of parameters and we might want to avoid future mistakes). If rewriting the tests is not too costly, we might even enforce that with a * (PEP 3102).
  1. _v_eval_n_from_recurrence: would it be possible to simplify that method by using _get_ind_from_recurrence_, also guaranteeing consistency between the two methods?
  1. A number of docstring has a description like "A namedtuple generated by _parse_recurrence_()". However, this nametuple is no longer generated by _parse_recurrence_, but by _get_parameters_from_recurrence_.
  1. _get_right_from_recurrence_: It seems that the last line return vector(right) could be replaced by return right because all code paths seem to guarantee that right is already a vector.
  1. _get_ind_from_recurrence_: The description of the input parameters does not match the signature of the method.
  1. _get_matrix_from_recurrence_: input parameters function, var are explained, but not part of the signature.
  1. _get_parameters_from_recurrence_: description of namedtuple misses offset.
  1. _v_eval_n_from_recurrence_: missing output section in docstring.
  1. from_recurrence: minimize: The same argument which led to the removal of transpose=True in #21295 (Review item 6) is also applicable here.
  1. There is a number of ReSt-issues because constructions like ``n``th and `i`th are not translated correctly and lead to "WARNING: Inline interpreted text or phrase reference start-string without end-string.". I suggest to insert hyphens in these situations.
  1. In lines 486 and 493, ....: should be replaced by ...

comment:45 Changed 40 hours ago by git

  • Commit changed from 43e892e0fd690a3721ab016f4b0b4546c42d2ac1 to de1d901e7c3ea90baad40f2b97185fd45b3a04d3

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

e42a389Trac #27940: review item 54: replace _parse_recurrence_ by
aadf467Trac #27940: add k again...
7aacbc2Trac #27940: review item 55: remove conversion to vector
8d52eb7Trac #27940: review item 56: correct input block
fd678d4Trac #27940: review item 57: remove function and var from input block
2cbde29Trac #27940: review item 58: add offset in output block
d14f0c1Trac #27940: review item 59: add ouput block
5aaf111Trac #27940: review item 60: remove minimize-option
ec7a722Trac #27940: review item 62: colons removed
de1d901Trac #27940: review item 61: fix "n-th" and "i-th"

comment:46 Changed 40 hours ago by git

  • Commit changed from de1d901e7c3ea90baad40f2b97185fd45b3a04d3 to 1d7b158ae8edb2fa18227d9362d2e9a20815922d

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

1d7b158Trac #27940: some modifications in the docstrings

comment:47 in reply to: ↑ 44 Changed 40 hours ago by galipnik

Replying to cheuberg:

Again thank you very much for your review!

Here are my answers and some comments:

  1. [...]

It meant rewriting it as follows: [...]

Done (and fixed the some indices in your suggestion because ind is 1-based), thank you.

  1. Naming of the variable in docstrings. In some docstrings, we have "a symbolic variable n" or similar formulations. I think that we should not make any assumptions about the name of the variable, it is simply a variable. There might be an exception in those docstrings where equations are parsed, there I would say "symbolic variable (n in the above description of equations).

Done.

  1. Naming of the variable in exceptions: Some exceptions have a hard-coded n. I think that it would be more helpful to use the variable name provided by the user. It might also be good to have one test with different names for function and variable.

I'm not sure whether this is a good idea with respect to #31787: If alternative input parameters will be implemented in the future, the user might not provide a variable name. Therefore, I've rephrased the exception messages without using any variable name.

  1. _get_right_from_recurrence_: Docstring: Please move the "see also" block before the "tests" block (I think that we should adhere to the order of the blocks as described in https://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content)

Done.

  1. from_recurrence: Please document parameter offset explicitly (e.g. "an integer (default: 0). See explanation in equations above")

Done.

  1. _get_values_from_recurrence_: if _coeff_(r, j) != 0 could be replaced by if _coeff_(r, j)

Done.

  1. _get_values_from_recurrence_: the check f_n not in base_ring could come earlier (when checking the provided parameters, not (possibly repeatedly) on usage

Done.

  1. _parse_recurrence_: docstring: replace "vector" by "tuple"

Done.

  1. _parse_recurrence_: why is remainders a list instead of a set?

What would be the advantage of a set here?

  1. _parse_recurrence_: elif M and not m: I think that this should be replaced by elif M and m is None:: Otherwise, I fear that legitimate situations such as M=3, m=0 with a bunch of equations might be erroneously corrected to M=3, m=2.

Fixed. The same issue also occured for m (lines 848 and 851), also this should be fixed now. Two additional tests added.

  1. _get_parameters_from_recurrence_: offset = max(0, -l/k**m): possibly take ceiling of -l/k**m to have an integer offset?

Done.

  1. In the old code, there were two tests
    sage: Seq2._parse_recurrence_([f(2*n) == f(n)], f, n)
    Traceback (most recent call last):
    ...
    ValueError: Recurrence relations for [f(2*n + 1)] are missing.
    
    sage: Seq2._parse_recurrence_([f(4*n) == f(n), f(4*n + 3) == 0], f, n)
    Traceback (most recent call last):
    ...
    ValueError: Recurrence relations for [f(4*n + 1), f(4*n + 2)] are missing.
    

which seem not to have survived the refactoring. If I am not mistaken, the corresponding checks are no longer there.

Fixed again.

  1. I suggest to always call _get_values_from_recurrence_ with named parameters (there is now quite a number of parameters and we might want to avoid future mistakes). If rewriting the tests is not too costly, we might even enforce that with a * (PEP 3102).

Done.

  1. _v_eval_n_from_recurrence: would it be possible to simplify that method by using _get_ind_from_recurrence_, also guaranteeing consistency between the two methods?

Done.

  1. A number of docstring has a description like "A namedtuple generated by _parse_recurrence_()". However, this nametuple is no longer generated by _parse_recurrence_, but by _get_parameters_from_recurrence_.

Fixed.

  1. _get_right_from_recurrence_: It seems that the last line return vector(right) could be replaced by return right because all code paths seem to guarantee that right is already a vector.

Done.

  1. _get_ind_from_recurrence_: The description of the input parameters does not match the signature of the method.

Fixed.

  1. _get_matrix_from_recurrence_: input parameters function, var are explained, but not part of the signature.

Removed.

  1. _get_parameters_from_recurrence_: description of namedtuple misses offset.

Added.

  1. _v_eval_n_from_recurrence_: missing output section in docstring.

Added.

  1. from_recurrence: minimize: The same argument which led to the removal of transpose=True in #21295 (Review item 6) is also applicable here.

Ok, minimize-option removed.

  1. There is a number of ReSt-issues because constructions like ``n``th and `i`th are not translated correctly and lead to "WARNING: Inline interpreted text or phrase reference start-string without end-string.". I suggest to insert hyphens in these situations.

Resolved.

  1. In lines 486 and 493, ....: should be replaced by ...

Done.

comment:48 Changed 40 hours ago by galipnik

  • Status changed from needs_work to needs_review

comment:49 follow-up: Changed 35 hours ago by cheuberg

  • Status changed from needs_review to needs_work

Thank you for your changes and your comments.

I have a few comments on the previous items and list a few new items (which are only relevant now that we seem to converge soon).

25.

I meant rewriting it as follows: [...]

Done (and fixed the some indices in your suggestion because ind is 1-based), thank you.

When writing done my suggestion yesterday, I was exactly afraid of making such off-by-one-errors. When I first reviewed the ticket, it was not clear to me whether having a 1-based ind has any advantages over having it 0-based. It seems to me that in this usage here, we always use ind[j, k] - 1 when using the map in one direction and always use ind[i+1] in the other direction. So: sorry for the late stage question, but would it not make life simpler to have ind 0-based (because this SageMath code lives in a 0-based world?)

  1. Naming of the variable in exceptions: Some exceptions have a hard-coded n. I think that it would be more helpful to use the variable name provided by the user. It might also be good to have one test with different names for function and variable.

I'm not sure whether this is a good idea with respect to #31787: If alternative input parameters will be implemented in the future, the user might not provide a variable name. Therefore, I've rephrased the exception messages without using any variable name.

This is better, thank you.

  1. _parse_recurrence_: why is remainders a list instead of a set?

What would be the advantage of a set here?

Semantically, a python set seems to be a better fit to what is done here (check whether certain elements are present). Performance is probably not an issue here.

  1. Fixed. The same issue also occured for m (lines 848 and 851), also this should be fixed now. Two additional tests added.

Thank you. One remark, though, when reading the new tests: I think that the casual user might not be very happy with an error message "2 does not equal 1" because it might be difficult to see where the problem comes from. It might help to print the offending equation and the offending term: "Term 'f(2*n)' in the equation 'f(8*n + 1) == f(2*n)': 2 does not equal 1." Sorry for not thinking about this earlier.

  1. In the old code, there were two tests [...] which seem not to have survived the refactoring. If I am not mistaken, the corresponding checks are no longer there.

Fixed again.

I think that raise ValueError(...) from None should be raise ValueError(...) in these checks because we are not handling another exception here.

56 _get_ind_from_recurrence_: The description of the input parameters does not match the signature of the method.

Fixed.

Please replace u by uu in the description of the input parameters.

  1. In lines 486 and 493, ....: should be replaced by ...

Done. 62

There are still 4 instead of 3 dots.

  1. Please merge the dependency #21203 once more (there seems to be a merge conflict).
  1. Please move references to src/doc/en/reference/references/index.rst as per the developer's guide ​https://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content
  1. Please add an arXiv identifier to reference HKL2021 once it is available.

comment:50 in reply to: ↑ 49 Changed 29 hours ago by galipnik

  • Authors changed from Gabriel Lipnik to Gabriel F. Lipnik

Replying to cheuberg:

[...] So: sorry for the late stage question, but would it not make life simpler to have ind 0-based (because this SageMath code lives in a 0-based world?)

Changed now. (The initial motivation for implementing it 1-based was consistency with the corresponding paper, but this is better now.)

  1. _parse_recurrence_: why is remainders a list instead of a set?

What would be the advantage of a set here?

Semantically, a python set seems to be a better fit to what is done here (check whether certain elements are present). Performance is probably not an issue here.

Ok, changed.

Thank you. One remark, though, when reading the new tests: I think that the casual user might not be very happy with an error message "2 does not equal 1" because it might be difficult to see where the problem comes from. It might help to print the offending equation and the offending term: "Term 'f(2*n)' in the equation 'f(8*n + 1) == f(2*n)': 2 does not equal 1." Sorry for not thinking about this earlier.

Hm, good point. Changed a lot in the error messages now to make the errors clearer.

  1. In the old code, there were two tests [...] which seem not to have survived the refactoring. If I am not mistaken, the corresponding checks are no longer there.

Fixed again.

I think that raise ValueError(...) from None should be raise ValueError(...) in these checks because we are not handling another exception here.

Changed.

56 [...]

Please replace u by uu in the description of the input parameters.

Done.

  1. In lines 486 and 493, [...]

There are still 4 instead of 3 dots.

Sorry, fixed now.

  1. Please merge the dependency #21203 once more (there seems to be a merge conflict).

Done and conflict resolved.

  1. Please move references to src/doc/en/reference/references/index.rst as per the developer's guide ​https://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content

Done.

  1. Please add an arXiv identifier to reference HKL2021 once it is available.

Will be done as soon as the paper is on arXiv.

Last edited 29 hours ago by galipnik (previous) (diff)

comment:51 Changed 29 hours ago by git

  • Commit changed from 1d7b158ae8edb2fa18227d9362d2e9a20815922d to 3d13b964418d3700e31bb328e3381889dd5c6005

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

5e8b236Trac #21203 review issue 1: better binary sum of digits
a6a8c3bTrac #21203 review issue 2: extend odds in Pascal's triangle
be462dcTrac #21203 review issue 3: example for __getitem__ and __iter__
cbd187fTrac #21295: rename to coefficient_ring
38743c1Merge branch 't/21295/sequences/recognizable' into t/21203/sequences/k-regular
c4bf7aeTrac #21203 review issue 4: rename to coefficient ring
00ad382Merge branch 'u/dkrenn/sequences/k-regular' into u/galipnik/k-regular-recurions-rebased
acf0c45Trac #27940: move references to index.rst
00f5ad3Trac #27940: add "F." to my name...
3d13b96Trac #27940: fix identation error from merge

comment:52 Changed 29 hours ago by galipnik

  • Status changed from needs_work to needs_review

comment:53 Changed 29 hours ago by git

  • Commit changed from 3d13b964418d3700e31bb328e3381889dd5c6005 to 2c36297b26affe1927841d34d696569c47261af5

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

2c36297Trac #27940: remove assignment of base_ring

comment:54 Changed 25 hours ago by cheuberg

Thank you for your changes.

I have no further comments, so the only open issues are

  1. arXiv identifier once available
  2. wait for dependency #21203
Note: See TracTickets for help on using tickets.