basic element and parent for k-regular sequences

[dkrenn]

Implement minimal element and parent classes for working with k-regular sequences

See also Meta ticket #21202.

Depends on #21164
Depends on #21180
Depends on #21200
Depends on #21295

CC: @rwst @galipnik

Component: combinatorics

Author: Daniel Krenn

Branch/Commit: d532b56

Reviewer: Clemens Heuberger

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

[dkrenn]

Branch: u/dkrenn/sequences/k-regular

[dkrenn]

Dependencies: #21164, #21180, #21200

[dkrenn]

Commit: 9c64180

[dkrenn]

Last 10 new commits:

965ec0f	Merge branch 'u/dkrenn/lazy_list-unbound-formatter' into u/dkrenn/sequences/k-regular
d8ae454	make product_of_matrices a private method
03c6418	docstring of _product_of_matrices_
16e041b	phrase error message and test it
091a276	use lazy_list_formatter in _repr_
e233dfd	write the missing docstrings
1818628	modify docstring at top of file
1e5efc8	rename to kRegularSequenceSpace
c14eceb	__classcall__ and __init__
9c64180	write remaining docstrings

[sagetrac-git]

Changed commit from 9c64180 to b92ff44

[sagetrac-git]

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

d3e2df6	Trac #21200: simplify requirements for input (only iterable needed)
7e166c3	Merge branch 'u/dkrenn/lazy_list-unbound-formatter' into u/dkrenn/sequences/k-regular
4102e47	__iter__ method
b92ff44	simplify `_repr_` code

[sagetrac-git]

Changed commit from b92ff44 to b4d5590

[sagetrac-git]

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

a2c8e91	new repr
089a0ea	remove output_function
6b67851	adapt docstring of transposed
800a329	Merge branch 'u/dkrenn/sequences/recognizable' into u/dkrenn/sequences/k-regular
28149c9	import of recognizable series
a26a051	matrices --> mu
9128d28	initial, selection --> left, right
5cf8f56	split `__normalize__` from `__classcall__` (to deal better with inheritance)
4bc0749	Merge branch 'u/dkrenn/sequences/recognizable' into u/dkrenn/sequences/k-regular
b4d5590	use new code for RecognizableSeries

[dkrenn]

Changed dependencies from #21164, #21180, #21200 to #21164, #21180, #21200, #21295

[sagetrac-git]

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

5f06dac	minor rewrite in _repr_
b18d3aa	check input of RecognizableSequenceSpace and document it
85c1a03	checks for creating recognizable series
eec776e	fix doctests
7d96697	coverage to 100%
4a1db0e	reorder imports
62ebcda	complete documentation
4331957	Merge branch 'u/dkrenn/sequences/recognizable' into u/dkrenn/sequences/k-regular
dab4db8	complete docstrings and 100% coverage
9afc4ac	cross-references

[sagetrac-git]

Changed commit from b4d5590 to 9afc4ac

[sagetrac-git]

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

fd4f541	move "transpose" in docstring to correct place
4eb1544	Merge branch 'u/dkrenn/sequences/recognizable' into u/dkrenn/sequences/k-regular
cf1b8cc	correct one link

[sagetrac-git]

Changed commit from 9afc4ac to cf1b8cc

[sagetrac-git]

Changed commit from cf1b8cc to 71aef7f

[sagetrac-git]

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

863d57a	remove None-sense to simplify code
aec95ce	extend element constructor
9e12383	add experimental warning
69289fe	Merge branch 'u/dkrenn/sequences/recognizable' into u/dkrenn/sequences/k-regular
71aef7f	fix doctests

[sagetrac-git]

Changed commit from 71aef7f to 5919120

[sagetrac-git]

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

41874ba	fix a typo
0f538a9	rearrange __getitem__
7495635	Merge branch 'u/dkrenn/sequences/recognizable' into u/dkrenn/sequences/k-regular
e53b906	update `__getitem__` to follow recognizable series
1794766	flag to skip multiplication with left/right
b060652	minor rewrite in minimized
31e2fcf	Merge branch 'u/dkrenn/sequences/recognizable' into u/dkrenn/sequences/k-regular
893bd5c	experimental warning in k_regular_sequence
189ce50	pass keywords to coefficient_of_word
5919120	doctesting all parameters in coefficient_of_word

[sagetrac-git]

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

c7243a6	Merge tag '7.4.beta1' into t/21295/sequences/recognizable
4012778	Merge branch 't/21295/sequences/recognizable' into t/21203/sequences/k-regular

[sagetrac-git]

Changed commit from 5919120 to 4012778

[sagetrac-git]

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

5dbedab	fix doctests (experimental warning)
143ea73	fix building of docs (no idea why it failed)

[sagetrac-git]

Changed commit from 4012778 to 143ea73

[sagetrac-git]

Changed commit from 143ea73 to d5c378d

[sagetrac-git]

Changed commit from 9e82a65 to c4bf7ae

[dkrenn]

comment:35

Replying to @cheuberg:

8. One more very minor detail: docstring of __getitem__: Apparently `n`th is not recognised correctly: there is an error message "docstring of sage.combinat.k_regular_sequence.kRegularSequence.__getitem__:1: WARNING: Inline interpreted text or phrase reference start-string without end-string." when running ./sage --docbuild --underscore reference/combinat html, and no LaTeX formatting occurs.

Fixed

[dkrenn]

comment:36

Replying to @cheuberg:

1. Example Binary sum of digits: It would be helpful to explain why this is a linear representation of the binary sum of digits. (However: why not choosing a simpler representation having the sum of digits and a constant sequence in the vector? Here, the first component is one minus the sum of digits)

Example changed (easier representation used) and more explanations.

2. Example Number of odd entries in Pascal's triangle: u(n) seems to be the number of odd entries up to row n-1. This could be made more explicit and the linear representation as well as the recursive formula could be explained, possibly with a reference.

Linear representation changed and some text added. For sure more could always be made...

3. kRegularSequence: please add an explanation on how to access elements of the sequence to the documentation of the class (it is now in the documentation of the module, but without explanation, and the docstrings of __getitem__ and __iter__ are not shown in the documentation.

Example added.

4. kRegularSequenceSpace: I think that to the casual user, the use of the word "coefficient" might be surprising.

Yes, indeed. Naming is not that easy here. Everything with "base" seems to be no option was we have "k" that is called base as well. I now give "coefficient_ring" a try (also changed at at #21295), but I am very open to other, better suggestions.

5. _n_to_index_: I would prefer a ValueError with meaningful message instead of an OverflowError.

Changed.

[cheuberg]

comment:38

Thank you for your changes.

I have one question and another minor suggestion.

9. What was the motivation to remove "If not specified (None), then the integer ring is used." ?

10. I suggest to use raise ... from None where appropriate (e.g., the OverflowError caught in _n_to_index_) to avoid lengthy stack traces like

...
/local/cheuberg/local/sage-9.3.rc3/local/lib/python3.6/site-packages/sage/combinat/words/word_char.pyx in sage.combinat.words.word_char.WordDatatype_char._set_data (build/cythonized/sage/combinat/words/word_char.c:3830)()
    110         for i in range(self._length):
--> 111             self._data[i] = data[i]
    112 

OverflowError: can't convert negative value to unsigned char

During handling of the above exception, another exception occurred:

ValueError                                Traceback (most recent call last)
<ipython-input-1-b7387a9417cd> in <module>
      2 Seq2._n_to_index_(Integer(6))
      3 word: Integer(11)
----> 4 Seq2._n_to_index_(-Integer(1))

/local/cheuberg/local/sage-9.3.rc3/local/lib/python3.6/site-packages/sage/combinat/k_regular_sequence.py in _n_to_index_(self, n)
    353             return W(n.digits(self.k))
    354         except OverflowError:
--> 355             raise ValueError('value {} of index is negative'.format(n))

ValueError: value -1 of index is negative

[sagetrac-git]

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

89f656b	Trac #21295 review issue 33: rename to number_of_zeros (as it should be)
2ddb686	Trac #21295 review issue 7: document accessing coefficients
13ad4a1	Trac #21295 review issue 29: notice minimize vs field
42606e3	Merge tag '9.3' into t/21295/sequences/recognizable
1dbecfd	Merge branch 't/21295/sequences/recognizable' into t/21203/sequences/k-regular

[sagetrac-git]

Changed commit from c4bf7ae to 1dbecfd

[sagetrac-git]

Changed commit from 1dbecfd to d532b56

[sagetrac-git]

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

d532b56

Trac #21203 review issue 10: use "raise ... from None" where approriate

[dkrenn]

comment:41

Replying to @cheuberg:

Thank you for your changes.
9. What was the motivation to remove "If not specified (None), then the integer ring is used." ?

I believe that there is no obvious/canonical base ring for regular sequences, so I think, there should not be set a somehow artificial choice. (BTW, never used in the the tests, except for one specific test on this default argument.)

10. I suggest to use raise ... from None where appropriate (e.g., the OverflowError caught in _n_to_index_) to avoid lengthy stack traces like [...]

Yes, indeed, this output is quite lengthy and does not bring anything. Done.

[cheuberg]

comment:42

Thank you, all seems to be fine. For the record: the lint warnings do not concern the files changed in this ticket.

[vbraun]

Changed branch from u/dkrenn/sequences/k-regular to d532b56