Opened 4 years ago
Closed 17 months ago
#27940 closed enhancement (fixed)
get kregular sequence from certain recurrence relations
Reported by:  Gabriel Lipnik  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  combinatorics  Keywords:  
Cc:  Daniel Krenn  Merged in:  
Authors:  Gabriel F. Lipnik, Daniel Krenn  Reviewers:  Clemens Heuberger, Daniel Krenn 
Report Upstream:  N/A  Work issues:  
Branch:  488123c (Commits, GitHub, GitLab)  Commit:  488123c86d1fea21cf8e00492a746f00b5b440f4 
Dependencies:  #21295, #21203  Stopgaps: 
Description (last modified by )
Code for constructing the linear representation of kregular sequences given by certain recurrence relations.
See also Meta ticket #21202.
Change History (71)
comment:1 Changed 4 years ago by
Type:  PLEASE CHANGE → enhancement 

comment:2 Changed 3 years ago by
Milestone:  sage8.8 

comment:3 Changed 3 years ago by
Commit:  3b7c866efb138160546f1234f617e8a0236184f5 → d367496e87a296bd378a0faa245c128d17e0fbd6 

comment:4 Changed 3 years ago by
Commit:  d367496e87a296bd378a0faa245c128d17e0fbd6 → 7d47dbe10eac8d72f97da84f8f407f11623ca01e 

comment:5 Changed 3 years ago by
Commit:  7d47dbe10eac8d72f97da84f8f407f11623ca01e → c2d99036fc8362355cb2c0ab39459f69085cc740 

Branch pushed to git repo; I updated commit sha1. New commits:
c2d9903  add another example

comment:6 Changed 3 years ago by
Commit:  c2d99036fc8362355cb2c0ab39459f69085cc740 → 98c24d13edf8e8d21ed3f714f728cf419b2489e3 

Branch pushed to git repo; I updated commit sha1. New commits:
98c24d1  start_values > initial_values

comment:7 Changed 3 years ago by
Commit:  98c24d13edf8e8d21ed3f714f728cf419b2489e3 → 060ca255156048704e1f96c08f119926053a6db7 

Branch pushed to git repo; I updated commit sha1. New commits:
060ca25  add docstrings

comment:8 Changed 22 months ago by
Commit:  060ca255156048704e1f96c08f119926053a6db7 → 6aff6b459a343a2bdd3db81c96b71e4ab0c21727 

comment:9 Changed 22 months ago by
Commit:  6aff6b459a343a2bdd3db81c96b71e4ab0c21727 → b0f0e1bc18bf0cc768c85d9bbdc64912500f9c33 

comment:10 Changed 22 months ago by
Commit:  b0f0e1bc18bf0cc768c85d9bbdc64912500f9c33 → b36adac731c5942b7cd366773ff0ca43fd760f76 

comment:11 Changed 22 months ago by
Commit:  b36adac731c5942b7cd366773ff0ca43fd760f76 → d0fe273b9a73f002bac4067f3a9a15d15776346e 

Branch pushed to git repo; I updated commit sha1. New commits:
d0fe273  adapt construction of W and J

comment:12 Changed 22 months ago by
Commit:  d0fe273b9a73f002bac4067f3a9a15d15776346e → 2edf0cf7c99f54f65b5deb6867bed7b77fb333a0 

comment:13 Changed 22 months ago by
Commit:  2edf0cf7c99f54f65b5deb6867bed7b77fb333a0 → 9b454f995a67f9165e536cee795830fb915f6f36 

Branch pushed to git repo; I updated commit sha1. New commits:
9b454f9  some more changes in the docstring...

comment:14 Changed 22 months ago by
Commit:  9b454f995a67f9165e536cee795830fb915f6f36 → 1e43197edc1d133de87998dca357c4f27f0829ea 

comment:15 Changed 22 months ago by
Status:  new → needs_review 

comment:16 Changed 22 months ago by
Commit:  1e43197edc1d133de87998dca357c4f27f0829ea → c0fdfbb4fe30272b41e6aea62b580416b85f48cd 

Branch pushed to git repo; I updated commit sha1. New commits:
c0fdfbb  n0 > offset

comment:17 followup: 42 Changed 20 months ago by
Milestone:  → sage9.4 

Reviewers:  → Clemens Heuberger 
Status:  needs_review → needs_work 
 Dependencies: It seems that many more branches are merged here than necessary. Please fill out the dependencies field here.
 Fix patchbot findings
recursions
: description of theequations
parameter: I am not sure whether writing it assum(...)
can cause any confusion. I propose to write some summands with...
.
recursions
: description of theequations
parameter: I guess you want to include some coefficients in front of the terms on the right hand side.
recursions
: dead link tominimized()
in description of parameterminimize
_parse_recursions_
: catchAttributeError
when a nonelement of the symbolic ring is given as an equation:Seq2._parse_recursions_([42], f, n)
_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 catchingException
.
_parse_recursion_
:base_ring[var](left_side.operands()[0])
I am unsure whetherbase_ring
is the correct ring here. After all, arguments of a regular sequence will alwys be the integers. A few lines later, there isZZ[var](left_side.operands()[0])
which seems to be the ring we need to use. So my suggestion is to always useZZ[var]
andpolynomial_left
and removingpoly_left
. Also,polynomial_left in base_ring
does not seem to be the correct ring.
_parse_recursion_
:initial_values.update({polynomial_left: right_side})
I suggest to check whether an initial value is repeatedly given.
_parse_recursion_
:if M != log(base_power_M, base=k):
I suggest to replace the right hand side byM_new
which has just been defined one line before.
_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 overZZ
anyway. In particular,Seq2._parse_recursions_([f(2*n+1/2) == f(n)], f, n)
leads toValueError: 2*n + 1/2 is not a polynomial in n.
_parse_recursion_
:else: # check this again
I do not understand the comment.
_parse_recursion_._parse_multiplication_
: I think thatif op.operator() != mul_vararg or len(op.operands()) != 2: raise ValueError("")
is unreachable, so I suggest to replace this byassert op.operator() == mul_vararg and len(op.operands()) == 2
.
_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.
_parse_recursion_._parse_one_summand_
: It should be checked thatlen(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.
_parse_recursion_
: Branchif 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.
__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)
_parse_recursion_
: docstring: I think that even for a private method, the contents of the namedtuple should be explained.
_get_ind_
docstring: I think that even for a private method, the output should be explained.
_get_matrix_from_recursions_
docstring: inputsvar
andfunction
are not explained.
_get_matrix_from_recursions_
docstring: Please explain what the role of the parametercorrect_offset
is.
_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.
_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.
_get_matrix_from_recursions_
: the linen1 = recursion_rules.n1
appears twice.
_get_matrix_from_recursions_
: I think that the lines which definetemp
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 vectorarguments
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 havefunction
andvar
as parameters of this method.
_get_matrix_from_recursions_
: the condition for construction the matrixJ
could be simplified: the conditionsi>= rem
andi % k == rem
can be omitted, because they follow fromj*k == irem
. Additionally, it might be simpler to construct this matrix by the version of the matrix constructor which takes a function as an argument.
_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 parameterfunction
might then be redundant.
recursions
: example SternBrocot: The initial valuef(2)
should not be required.
recursions
: example Odd Entries in Pascal's Triangle: onlyf(0)
andf(1)
should be required as initial values.
recursions
: example Unbordered Factors: one equation per line (cf. 21)
recursions
: example Unbordered Factors: initial values (cf. 22)
recursions
: docstring: "in the a Generalized" remove "a"
recursions
: "[TODO: reference]" please resolve TODO.
recursions
: example Generalized Pascal's Triangle: only initial valuesf(0)
andf(1)
should be required.
recursions
:mu
could be constructed as a list comprehension instead of appending to a list.
 This ticket adds quite a number of private methods to
kRegularSequenceSpace
which are only useful for the public methodrecursions
. For clarity's sake, I propose to introduce a "see also" block in all auxiliary private methods which refers torecursions
.
 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).
 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 kregular sequence from a recursion? Perhapsfrom_recursion
or possibly more precisefrom_recurrence
would be a better name.
 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).
 Test raising "Initial value ... is missing".
 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 theValueError
of this code here.
comment:18 Changed 20 months ago by
Dependencies:  → #21295, #21203 

comment:19 Changed 20 months ago by
Commit:  c0fdfbb4fe30272b41e6aea62b580416b85f48cd → a4ea50353838b6a2f26c0550ede78dce5cc03a60 

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

comment:20 Changed 20 months ago by
Commit:  a4ea50353838b6a2f26c0550ede78dce5cc03a60 → 988aa854cc1880933a3d68b5a58955187f1a0a86 

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

comment:21 Changed 20 months ago by
Description:  modified (diff) 

comment:22 Changed 20 months ago by
Summary:  get kregular sequence from recursions → get kregular sequence from certain recurrence relations 

comment:23 Changed 20 months ago by
Commit:  988aa854cc1880933a3d68b5a58955187f1a0a86 → 66847f1f2689a71c974111dbbeda60cc50783673 

comment:24 Changed 20 months ago by
Commit:  66847f1f2689a71c974111dbbeda60cc50783673 → 8706ea1ab9e631c656b441775facfaae78d06259 

comment:25 Changed 20 months ago by
Commit:  8706ea1ab9e631c656b441775facfaae78d06259 → 296427083f100271d3bb3f5df5eff66474e9e5a9 

comment:26 Changed 20 months ago by
Commit:  296427083f100271d3bb3f5df5eff66474e9e5a9 → e495b2e05cb5221fd6c3601216ffec9780bc3fd7 

Branch pushed to git repo; I updated commit sha1. New commits:
e495b2e  13: add assert

comment:27 Changed 20 months ago by
Commit:  e495b2e05cb5221fd6c3601216ffec9780bc3fd7 → 9be7469499b8093d81a6c95ba7001dffa1418d1d 

comment:28 Changed 20 months ago by
Commit:  9be7469499b8093d81a6c95ba7001dffa1418d1d → ab940aa3fc983f71babd80b7d5072ec2ae1380ee 

Branch pushed to git repo; I updated commit sha1. New commits:
ab940aa  add some docstring, minor changes

comment:29 Changed 20 months ago by
Commit:  ab940aa3fc983f71babd80b7d5072ec2ae1380ee → 96fbad885a9cdbe5a6543830979bdac8a01d3824 

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

comment:30 Changed 20 months ago by
Commit:  96fbad885a9cdbe5a6543830979bdac8a01d3824 → 8f538875eb20bcf814a0da297bdbed9741e692a8 

comment:31 Changed 20 months ago by
Commit:  8f538875eb20bcf814a0da297bdbed9741e692a8 → c63d08e221968e689464531e045e7aefdae7e0ce 

comment:32 Changed 20 months ago by
Commit:  c63d08e221968e689464531e045e7aefdae7e0ce → 92ef82fb6f016836bce103236bc17ccc471c572e 

Branch pushed to git repo; I updated commit sha1. New commits:
92ef82f  remove redundant arguments of _get_matrix_

comment:33 Changed 20 months ago by
Status:  needs_work → needs_review 

comment:34 Changed 20 months ago by
Commit:  92ef82fb6f016836bce103236bc17ccc471c572e → d9a5322d62dc039cd93ebf250f874ed9ce24b8ed 

Branch pushed to git repo; I updated commit sha1. New commits:
d9a5322  recursion > recurrence

comment:35 Changed 20 months ago by
Commit:  d9a5322d62dc039cd93ebf250f874ed9ce24b8ed → 9ade52bec3c9a2b8eb07a11abd2ea8d3803c0683 

Branch pushed to git repo; I updated commit sha1. New commits:
9ade52b  further doctests

comment:36 followup: 39 Changed 20 months ago by
Branch:  u/galipnik/kregularrecursions → u/cheuberg/kregularrecursionsrebased 

Commit:  9ade52bec3c9a2b8eb07a11abd2ea8d3803c0683 → 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/kregularrecursions on top of that.
@galpnik: Please crossreview this rebase.
I will review your changes after that.
Last 10 new commits:
d0676a8  simplify _get_matrix_from_recurrence_

430d0f2  add negative initial values

85e2200  fix identation of docstring

3f074fe  add further doctests

15a3607  some further improvements

4e33084  rename k to j in some indices

0d6707c  further minor improvements

72d8e32  remove redundant arguments of _get_matrix_

642b4d3  recursion > recurrence

fa9bed3  further doctests

comment:37 Changed 20 months ago by
Branch:  u/cheuberg/kregularrecursionsrebased → u/galipnik/kregularrecurionsrebased 

comment:38 Changed 20 months ago by
Commit:  fa9bed3c3c213b827af048ea0585daa459eed63b → 61d6c6ef938f864f0ba6637d9d8a40e85571678b 

comment:39 Changed 20 months ago by
Replying to cheuberg:
@galpnik: Please crossreview this rebase.
Thank you! Three new commits pushed, the rest LGTM.
comment:40 Changed 19 months ago by
Status:  needs_review → needs_work 

comment:41 Changed 19 months ago by
Commit:  61d6c6ef938f864f0ba6637d9d8a40e85571678b → 43e892e0fd690a3721ab016f4b0b4546c42d2ac1 

comment:42 Changed 19 months ago by
Here is a more detailed answer to your review:
Replying to cheuberg:
 Dependencies: It seems that many more branches are merged here than necessary. Please fill out the dependencies field here.
Done. See also comment:36.
 Fix patchbot findings
Done.
recursions
: description of theequations
parameter: I am not sure whether writing it assum(...)
can cause any confusion. I propose to write some summands with...
.
Done and printed in LaTeX.
recursions
: description of theequations
parameter: I guess you want to include some coefficients in front of the terms on the right hand side.
Done.
recursions
: dead link tominimized()
in description of parameterminimize
Fixed.
_parse_recursions_
: catchAttributeError
when a nonelement of the symbolic ring is given as an equation:Seq2._parse_recursions_([42], f, n)
Done and test case added.
_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 catchingException
.
Done.
_parse_recursion_
:base_ring[var](left_side.operands()[0])
I am unsure whetherbase_ring
is the correct ring here. After all, arguments of a regular sequence will alwys be the integers. A few lines later, there isZZ[var](left_side.operands()[0])
which seems to be the ring we need to use. So my suggestion is to always useZZ[var]
andpolynomial_left
and removingpoly_left
. Also,polynomial_left in base_ring
does not seem to be the correct ring.
Done.
_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.
_parse_recursion_
:if M != log(base_power_M, base=k):
I suggest to replace the right hand side byM_new
which has just been defined one line before.
Done.
_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 overZZ
anyway. In particular,Seq2._parse_recursions_([f(2*n+1/2) == f(n)], f, n)
leads toValueError: 2*n + 1/2 is not a polynomial in n.
Fixed.
_parse_recursion_
:else: # check this again
I do not understand the comment.
Removed.
_parse_recursion_._parse_multiplication_
: I think thatif op.operator() != mul_vararg or len(op.operands()) != 2: raise ValueError("")
is unreachable, so I suggest to replace this byassert op.operator() == mul_vararg and len(op.operands()) == 2
.
Yes, I agree. Done.
_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.
_parse_recursion_._parse_one_summand_
: It should be checked thatlen(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.
_parse_recursion_
: Branchif 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.
__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.
_parse_recursion_
: docstring: I think that even for a private method, the contents of the namedtuple should be explained.
Done.
_get_ind_
docstring: I think that even for a private method, the output should be explained.
Done.
_get_matrix_from_recursions_
docstring: inputsvar
andfunction
are not explained.
These inputs are not needed anymore.
_get_matrix_from_recursions_
docstring: Please explain what the role of the parametercorrect_offset
is.
Done.
_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.
_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.
_get_matrix_from_recursions_
: the linen1 = recursion_rules.n1
appears twice.
Removed.
_get_matrix_from_recursions_
: I think that the lines which definetemp
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 vectorarguments
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 havefunction
andvar
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.
_get_matrix_from_recursions_
: the condition for construction the matrixJ
could be simplified: the conditionsi>= rem
andi % k == rem
can be omitted, because they follow fromj*k == irem
. 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.
_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 parameterfunction
might then be redundant.
Done.
recursions
: example SternBrocot: The initial valuef(2)
should not be required.
Removed.
recursions
: example Odd Entries in Pascal's Triangle: onlyf(0)
andf(1)
should be required as initial values.
Removed.
recursions
: example Unbordered Factors: one equation per line (cf. 21)
Done.
recursions
: example Unbordered Factors: initial values (cf. 22)
Done.
recursions
: docstring: "in the a Generalized" remove "a"
Done.
recursions
: "[TODO: reference]" please resolve TODO.
Done.
recursions
: example Generalized Pascal's Triangle: only initial valuesf(0)
andf(1)
should be required.
Done.
recursions
:mu
could be constructed as a list comprehension instead of appending to a list.
Done.
 This ticket adds quite a number of private methods to
kRegularSequenceSpace
which are only useful for the public methodrecursions
. For clarity's sake, I propose to introduce a "see also" block in all auxiliary private methods which refers torecursions
.
Done.
 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.
 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 kregular sequence from a recursion? Perhapsfrom_recursion
or possibly more precisefrom_recurrence
would be a better name.
Changed to from_recurrence
.
 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.
 Test raising "Initial value ... is missing".
This exception is removed now, because the method _get_values_from_recurrence_
checks this.
 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 theValueError
of this code here.
Done.
comment:43 Changed 19 months ago by
Status:  needs_work → needs_review 

comment:44 followup: 47 Changed 19 months ago by
Status:  needs_review → needs_work 

Thank you for your changes and comments.
One reply and a few more comments which came up while reading your changes.
_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**(M1)*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)
 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 ofequations
).
 Naming of the variable in exceptions: Some exceptions have a hardcoded
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.
_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#thedocstringofafunctioncontent)
from_recurrence
: Please document parameteroffset
explicitly (e.g. "an integer (default:0
). See explanation inequations
above")
_get_values_from_recurrence_
:if _coeff_(r, j) != 0
could be replaced byif _coeff_(r, j)
_get_values_from_recurrence_
: the checkf_n not in base_ring
could come earlier (when checking the provided parameters, not (possibly repeatedly) on usage
_parse_recurrence_
: docstring: replace "vector" by "tuple"
_parse_recurrence_
: why isremainders
a list instead of a set?
_parse_recurrence_
:elif M and not m:
I think that this should be replaced byelif M and m is None:
: Otherwise, I fear that legitimate situations such asM=3
,m=0
with a bunch of equations might be erroneously corrected toM=3
,m=2
.
_get_parameters_from_recurrence_
:offset = max(0, l/k**m)
: possibly take ceiling ofl/k**m
to have an integer offset?
 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.
 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).
_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?
 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_
.
_get_right_from_recurrence_
: It seems that the last linereturn vector(right)
could be replaced byreturn right
because all code paths seem to guarantee thatright
is already a vector.
_get_ind_from_recurrence_
: The description of the input parameters does not match the signature of the method.
_get_matrix_from_recurrence_
: input parametersfunction
,var
are explained, but not part of the signature.
_get_parameters_from_recurrence_
: description of namedtuple missesoffset
.
_v_eval_n_from_recurrence_
: missing output section in docstring.
from_recurrence
:minimize
: The same argument which led to the removal oftranspose=True
in #21295 (Review item 6) is also applicable here.
 There is a number of ReStissues because constructions like
``n``th
and`i`th
are not translated correctly and lead to "WARNING: Inline interpreted text or phrase reference startstring without endstring.". I suggest to insert hyphens in these situations.
 In lines 486 and 493,
....:
should be replaced by...
comment:45 Changed 19 months ago by
Commit:  43e892e0fd690a3721ab016f4b0b4546c42d2ac1 → de1d901e7c3ea90baad40f2b97185fd45b3a04d3 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
e42a389  Trac #27940: review item 54: replace _parse_recurrence_ by

aadf467  Trac #27940: add k again...

7aacbc2  Trac #27940: review item 55: remove conversion to vector

8d52eb7  Trac #27940: review item 56: correct input block

fd678d4  Trac #27940: review item 57: remove function and var from input block

2cbde29  Trac #27940: review item 58: add offset in output block

d14f0c1  Trac #27940: review item 59: add ouput block

5aaf111  Trac #27940: review item 60: remove minimizeoption

ec7a722  Trac #27940: review item 62: colons removed

de1d901  Trac #27940: review item 61: fix "nth" and "ith"

comment:46 Changed 19 months ago by
Commit:  de1d901e7c3ea90baad40f2b97185fd45b3a04d3 → 1d7b158ae8edb2fa18227d9362d2e9a20815922d 

Branch pushed to git repo; I updated commit sha1. New commits:
1d7b158  Trac #27940: some modifications in the docstrings

comment:47 Changed 19 months ago by
Replying to cheuberg:
Again thank you very much for your review!
Here are my answers and some comments:
 [...]
It meant rewriting it as follows: [...]
Done (and fixed the some indices in your suggestion because ind
is 1based), thank you.
 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 ofequations
).
Done.
 Naming of the variable in exceptions: Some exceptions have a hardcoded
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.
_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#thedocstringofafunctioncontent)
Done.
from_recurrence
: Please document parameteroffset
explicitly (e.g. "an integer (default:0
). See explanation inequations
above")
Done.
_get_values_from_recurrence_
:if _coeff_(r, j) != 0
could be replaced byif _coeff_(r, j)
Done.
_get_values_from_recurrence_
: the checkf_n not in base_ring
could come earlier (when checking the provided parameters, not (possibly repeatedly) on usage
Done.
_parse_recurrence_
: docstring: replace "vector" by "tuple"
Done.
_parse_recurrence_
: why isremainders
a list instead of a set?
What would be the advantage of a set here?
_parse_recurrence_
:elif M and not m:
I think that this should be replaced byelif M and m is None:
: Otherwise, I fear that legitimate situations such asM=3
,m=0
with a bunch of equations might be erroneously corrected toM=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.
_get_parameters_from_recurrence_
:offset = max(0, l/k**m)
: possibly take ceiling ofl/k**m
to have an integer offset?
Done.
 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.
 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.
_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.
 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.
_get_right_from_recurrence_
: It seems that the last linereturn vector(right)
could be replaced byreturn right
because all code paths seem to guarantee thatright
is already a vector.
Done.
_get_ind_from_recurrence_
: The description of the input parameters does not match the signature of the method.
Fixed.
_get_matrix_from_recurrence_
: input parametersfunction
,var
are explained, but not part of the signature.
Removed.
_get_parameters_from_recurrence_
: description of namedtuple missesoffset
.
Added.
_v_eval_n_from_recurrence_
: missing output section in docstring.
Added.
from_recurrence
:minimize
: The same argument which led to the removal oftranspose=True
in #21295 (Review item 6) is also applicable here.
Ok, minimize
option removed.
 There is a number of ReStissues because constructions like
``n``th
and`i`th
are not translated correctly and lead to "WARNING: Inline interpreted text or phrase reference startstring without endstring.". I suggest to insert hyphens in these situations.
Resolved.
 In lines 486 and 493,
....:
should be replaced by...
Done.
comment:48 Changed 19 months ago by
Status:  needs_work → needs_review 

comment:49 followup: 50 Changed 19 months ago by
Status:  needs_review → 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 1based), thank you.
When writing done my suggestion yesterday, I was exactly afraid of making such offbyoneerrors.
When I first reviewed the ticket, it was not clear to me whether having a 1based ind
has any
advantages over having it 0based. 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
0based (because this SageMath code lives in a 0based world?)
 Naming of the variable in exceptions: Some exceptions have a hardcoded 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.
_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.
 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.
 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.
 In lines 486 and 493,
....:
should be replaced by...
Done. 62
There are still 4 instead of 3 dots.
 Please merge the dependency #21203 once more (there seems to be a merge conflict).
 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#thedocstringofafunctioncontent
 Please add an arXiv identifier to reference HKL2021 once it is available.
comment:50 Changed 19 months ago by
Authors:  Gabriel Lipnik → Gabriel F. Lipnik 

Replying to cheuberg:
[...] So: sorry for the late stage question, but would it not make life simpler to have
ind
0based (because this SageMath code lives in a 0based world?)
Changed now. (The initial motivation for implementing it 1based was consistency with the corresponding paper, but this is better now.)
_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.
 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 beraise ValueError(...)
in these checks because we are not handling another exception here.
Changed.
56 [...]
Please replace
u
byuu
in the description of the input parameters.
Done.
 In lines 486 and 493, [...]
There are still 4 instead of 3 dots.
Sorry, fixed now.
 Please merge the dependency #21203 once more (there seems to be a merge conflict).
Done and conflict resolved.
 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#thedocstringofafunctioncontent
Done.
 Please add an arXiv identifier to reference HKL2021 once it is available.
Will be done as soon as the paper is on arXiv.
comment:51 Changed 19 months ago by
Commit:  1d7b158ae8edb2fa18227d9362d2e9a20815922d → 3d13b964418d3700e31bb328e3381889dd5c6005 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
5e8b236  Trac #21203 review issue 1: better binary sum of digits

a6a8c3b  Trac #21203 review issue 2: extend odds in Pascal's triangle

be462dc  Trac #21203 review issue 3: example for __getitem__ and __iter__

cbd187f  Trac #21295: rename to coefficient_ring

38743c1  Merge branch 't/21295/sequences/recognizable' into t/21203/sequences/kregular

c4bf7ae  Trac #21203 review issue 4: rename to coefficient ring

00ad382  Merge branch 'u/dkrenn/sequences/kregular' into u/galipnik/kregularrecurionsrebased

acf0c45  Trac #27940: move references to index.rst

00f5ad3  Trac #27940: add "F." to my name...

3d13b96  Trac #27940: fix identation error from merge

comment:52 Changed 19 months ago by
Status:  needs_work → needs_review 

comment:53 Changed 19 months ago by
Commit:  3d13b964418d3700e31bb328e3381889dd5c6005 → 2c36297b26affe1927841d34d696569c47261af5 

Branch pushed to git repo; I updated commit sha1. New commits:
2c36297  Trac #27940: remove assignment of base_ring

comment:54 Changed 19 months ago by
Thank you for your changes.
I have no further comments, so the only open issues are
 arXiv identifier once available
 wait for dependency #21203
comment:55 Changed 19 months ago by
Commit:  2c36297b26affe1927841d34d696569c47261af5 → 288995ee87d5b49107ac12a865c112b0095b79fc 

comment:56 Changed 19 months ago by
Three new commits pushed.
 [...] It might also be good to have one test with different names for function and variable.
Done. (Note that the comparison for kRegularSequence
is implemented in #21319, which is no dependency of this ticket.)
 arXiv identifier once available
Done.
comment:57 Changed 19 months ago by
Branch:  u/galipnik/kregularrecurionsrebased → u/dkrenn/kregularrecurionsrebased 

comment:58 Changed 18 months ago by
Commit:  288995ee87d5b49107ac12a865c112b0095b79fc → 86c5df7d75cdeca195f6f1a743745925bcee9dae 

Branch pushed to git repo; I updated commit sha1. New commits:
cb590ee  Trac #27940 move commit: move from_recurrence docstring up

9cc888d  Trac #27940: restructure and bring code running

6ff29ba  Trac #27940: fix doctests (use RecurrenceParser)

22cb3f0  Trac #27940: remove underscores from helper methods

293905a  Trac #27940: remove "_from_recurrence" from method names

75fe130  Trac #27940: remove "get_" from method names

952d724  Trac #27940: consistently use coefficient_ring

fbf3a81  Trac #27940: adapt/complete docstrings

16de2ab  Trac #27940: unify input parameters

86c5df7  Trac #27940: fix indention (due to renamings)

comment:59 Changed 18 months ago by
Authors:  Gabriel F. Lipnik → Gabriel F. Lipnik, Daniel Krenn 

Reviewers:  Clemens Heuberger → Clemens Heuberger, Daniel Krenn 
As discussed, I've slightly refactored the code to have the parser and all helper methods in a separate class. I suggest to review the changes above commitwise.
comment:60 followup: 62 Changed 18 months ago by
Status:  needs_review → needs_info 

I reviewed the refactored code, fine for me except for one suggestion:
RecurrenceParser.__call__
: I suggest to keep the signature of the output consistent with the signature of the input of kregular sequences, i.e.,(mu, left, right)
. Otherwise, I think that the linesleft, mu, right = RP(*args, **kwds) return self(mu, left, right)
in
kRegularSequenceSpace.from_recurrence
are surprising.
comment:61 Changed 18 months ago by
Commit:  86c5df7d75cdeca195f6f1a743745925bcee9dae → 6db5f58601a1c630fd69ac2c00460adb6580ccca 

Branch pushed to git repo; I updated commit sha1. New commits:
6db5f58  Trac #27940 review 67: change signature of output of RecurrenceParser.__call__

comment:62 Changed 18 months ago by
Replying to cheuberg:
I reviewed the refactored code, fine for me except for one suggestion:
RecurrenceParser.__call__
: I suggest to keep the signature of the output consistent with the signature of the input of kregular sequences, i.e.,(mu, left, right)
. Otherwise, I think that the linesleft, mu, right = RP(*args, **kwds) return self(mu, left, right)in
kRegularSequenceSpace.from_recurrence
are surprising.
Changed. (Note that RecognizableSeries.linear_representation
uses left, mu, right
; if this should be changed as well (on a followup ticket to the whole kregular stuff #21202), then now would be a good time as it is not yet merged in a stable release, only in a beta. Any thoughts?)
comment:63 Changed 18 months ago by
Yes, in the last iteration of the other ticket (#21238), I was also thinking about the inconsistency between the input of kregular sequences and the output of linear_representation
.
It seems that the order left, mu, right
for linear_representation
has not been invented within this series of tickets, but is defined in that way at least somewhere in the literature (e.g. Berstel and Reutenauer p. 10). So in my opinion if we aim for consistency, then the signature of element creation in regular sequences should be changed. And, as you say, if it is done, then it should be done very soon.
comment:64 Changed 18 months ago by
Status:  needs_info → needs_review 

As discussed earlier offsite: linear_representation
should stick to the ordering in the literature (left, matrices, right); construction of recognizable series should stick to the current implementatoin (matrices, left, right): if we ever decide to make left
and right
optional, this ordering is required.
This means that we do not change anything here; we just wait for the patchbot.
comment:65 followup: 66 Changed 18 months ago by
@galipnik: could you please also have a look on dkrenn's changes?
comment:66 Changed 18 months ago by
Replying to cheuberg:
@galipnik: could you please also have a look on dkrenn's changes?
Done, the changes are fine for me. Thank you!
comment:67 Changed 17 months ago by
Branch:  u/dkrenn/kregularrecurionsrebased → u/galipnik/kregularrecurionsrebased 

Commit:  6db5f58601a1c630fd69ac2c00460adb6580ccca → 288995ee87d5b49107ac12a865c112b0095b79fc 
comment:68 Changed 17 months ago by
Commit:  288995ee87d5b49107ac12a865c112b0095b79fc → 488123c86d1fea21cf8e00492a746f00b5b440f4 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
6ff29ba  Trac #27940: fix doctests (use RecurrenceParser)

22cb3f0  Trac #27940: remove underscores from helper methods

293905a  Trac #27940: remove "_from_recurrence" from method names

75fe130  Trac #27940: remove "get_" from method names

952d724  Trac #27940: consistently use coefficient_ring

fbf3a81  Trac #27940: adapt/complete docstrings

16de2ab  Trac #27940: unify input parameters

86c5df7  Trac #27940: fix indention (due to renamings)

6db5f58  Trac #27940 review 67: change signature of output of RecurrenceParser.__call__

488123c  Trac #27940: remove redundant line

comment:69 Changed 17 months ago by
Sorry for the late change, but I incidentally found a redundant line of code and removed it in the last commit 488123c. I've restarted the patchbot.
comment:70 Changed 17 months ago by
Status:  needs_review → positive_review 

488123c is fine. Patchbot is happy. Time to set it to positive.
comment:71 Changed 17 months ago by
Branch:  u/galipnik/kregularrecurionsrebased → 488123c86d1fea21cf8e00492a746f00b5b440f4 

Resolution:  → fixed 
Status:  positive_review → closed 
As the Sage8.8 release milestone is pending, we should delete the sage8.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 (sage8.9).