Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Meta ticket: k-regular sequences #21202

Open
dkrenn opened this issue Aug 10, 2016 · 58 comments
Open

Meta ticket: k-regular sequences #21202

dkrenn opened this issue Aug 10, 2016 · 58 comments
Labels
c: combinatorics p: major / 3 t: enhancement

Comments

@dkrenn
Copy link
Contributor

dkrenn commented Aug 10, 2016 •
edited
Loading

Implementation of k-regular sequences (https://en.wikipedia.org/wiki/K-regular_sequence).

Roadmap:

Depends on #21203
Depends on #21204
Depends on #21295
Depends on #21318
Depends on #21319
Depends on #21325
Depends on #21343
Depends on #22964
Depends on #27940
Depends on #31787
Depends on #32198
Depends on #32921

CC: @behackl @cheuberg @galipnik

Component: combinatorics

Author: Daniel Krenn, Gabriel F. Lipnik

Branch/Commit: u/dkrenn/k-regular-trunk @ f3564a3

Issue created by migration from https://trac.sagemath.org/ticket/21202
@dkrenn dkrenn added this to the sage-7.4 milestone Aug 10, 2016
@dkrenn

This comment has been minimized.

Sign in to view
@dkrenn
Copy link
Contributor Author

dkrenn commented Aug 10, 2016

Dependencies: #21203, #21204

@dkrenn

This comment has been minimized.

Sign in to view
@dkrenn

This comment has been minimized.

Sign in to view
@videlec
Copy link
Contributor

videlec commented Aug 12, 2016

comment:6

Please, try to not add one more class for sequences. There are already

  • lazy lists in sage.misc.lazy_list
  • words in sage.combinat.words
  • C finite sequence in sage.rings.cfinite_sequence
  • paths of directed graphs in quivers.paths.pyx
    Would be nice to unify them at some point.

@dkrenn
Copy link
Contributor Author

dkrenn commented Aug 16, 2016

comment:7

Replying to @videlec:

Please, try to not add one more class for sequences.

None of the below does what k-regular sequence do, so how to accomplish working with k-regular sequences by not adding another class? ;)

To make it clear: A k-regular sequence is a very concrete object with rules how to manipulate them. I am not intending to add a kind of metaclass for sequences.

There are already

  • lazy lists in sage.misc.lazy_list

Are more like a data structure behind; do not fit into the parent/element scheme of SageMath.

  • words in sage.combinat.words

Of course, generalizing words sufficiently, then more or less every sequence is a word. k-regular sequences have values in ZZ or QQ or something else. Moreover, they have a kind of rich arithmetic structure, which has to be implemented.

  • C finite sequence in sage.rings.cfinite_sequence

This is probably closest to k-regular sequences, but in some sense, k-regular sequence are more general, in some sense, they are orthogonal to C-finite sequences. Thus this cannot be used very well.

  • paths of directed graphs in quivers.paths.pyx

Never seen before, but for sure something different.

Would be nice to unify them at some point.

I completely agree. Any ideas how to accomplish this? The category framework might help...

@dkrenn
Copy link
Contributor Author

dkrenn commented Aug 19, 2016

Changed dependencies from #21203, #21204 to #21203, #21204, #21295

@dkrenn

This comment has been minimized.

Sign in to view
@dkrenn
Copy link
Contributor Author

dkrenn commented Aug 23, 2016

Changed dependencies from #21203, #21204, #21295 to #21203, #21204, #21295, #21318, #21319

@dkrenn

This comment has been minimized.

Sign in to view
@dkrenn

This comment has been minimized.

Sign in to view
@dkrenn
Copy link
Contributor Author

dkrenn commented Aug 24, 2016

Changed dependencies from #21203, #21204, #21295, #21318, #21319 to #21203, #21204, #21295, #21318, #21319, #21325

@dkrenn

This comment has been minimized.

Sign in to view
@dkrenn

This comment has been minimized.

Sign in to view
@dkrenn
Copy link
Contributor Author

dkrenn commented Aug 25, 2016

Branch: u/dkrenn/k-regular-trunk

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Aug 25, 2016

Commit: cfeca16

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Aug 25, 2016

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

73ad7bdMerge branch 'u/dkrenn/sequences/k-regular' into u/dkrenn/sequences/k-regular-guess
c349170fix code and doctests to adapt with upstream recognizable series
15e4008Merge branch 'u/dkrenn/sequences/k-regular' into u/dkrenn/sequences/k-regular-guess
eaf8df2Merge branch 'u/dkrenn/sequences/k-regular' into u/dkrenn/sequences/k-regular-guess
355d24dsimplify code by using features of recognizable series better (and adapting to removing None-sense)
348fcffsolve transpositioning problem
2e99c5canother example
a68e20dMerge branch 't/21203/sequences/k-regular' into t/21204/sequences/k-regular-guess
816fcfdMerge branch 't/21325/sequences/k-regular-subseq' into t/21204/sequences/k-regular-guess
cfeca16Merge branch 't/21204/sequences/k-regular-guess' into t/21202/k-regular-trunk

@dkrenn

This comment has been minimized.

Sign in to view
@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Aug 25, 2016

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

a8e6334MatrixSpace.some_elements
520aaf1FreeModule_generic.some_elements
5afda8eMerge branch 'u/dkrenn/matrices-some-elements' into t/21319/sequences/rec-hash
1e5754ban_element and some_elements
becce48pickling support
a4ccbecTestSuite
c2f9c62Merge branch 't/21325/sequences/k-regular-subseq' into t/21319/sequences/rec-hash
80861bcMerge branch 't/21319/sequences/rec-hash' into t/21202/k-regular-trunk

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Aug 25, 2016

Changed commit from cfeca16 to 80861bc

@dkrenn

This comment has been minimized.

Sign in to view
@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Aug 25, 2016

Changed commit from 80861bc to 1863001

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Aug 25, 2016

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

65da1e7Merge branch 'u/dkrenn/sequences/k-regular' into u/dkrenn/sequences/k-regular-guess
3e955e1guessing partial sums
0d5fbedMerge ../7.2 into t/21204/sequences/k-regular-guess
9818d94Merge branch 't/21319/sequences/rec-hash' into t/21204/sequences/k-regular-guess
90e4ed5doctests
899e56efinish .guess (docstrings etc)
1863001Merge branch 't/21204/sequences/k-regular-guess' into t/21202/k-regular-trunk

@dkrenn
Copy link
Contributor Author

dkrenn commented Aug 26, 2016

Changed dependencies from #21203, #21204, #21295, #21318, #21319, #21325 to #21203, #21204, #21295, #21318, #21319, #21325, #21343

@dkrenn

This comment has been minimized.

Sign in to view
@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Aug 26, 2016

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

5444e7bactivate logging
edd773fsome doctests
ddb8f8cremove zero()
6470f09correct creation of element in transposed
f66840dmethods for dealing with healthyness
ecd22e8use logging more correctly
b2b167bequip element constructor with a warning
92a33feadd some doctests related to health
7a6340fMerge branch 't/21204/sequences/k-regular-guess' into u/dkrenn/k-regular-warning
6b7ac91Merge branch 't/21343/k-regular-warning' into t/21202/k-regular-trunk

@dkrenn
Copy link
Contributor Author

dkrenn commented Mar 29, 2019

comment:33

This is now on 8.7.

Dependency chain: #21295 #21203 #21318 #21325 #21319 #21204 #21343 #22964.

@galipnik

This comment has been minimized.

Sign in to view
@galipnik

This comment has been minimized.

Sign in to view
@galipnik

This comment has been minimized.

Sign in to view
@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented May 11, 2021

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

ad29c70Trac #22964: fix text between examples
6322a79Trac #22964: intends also in other file
05f7b24Trac #22964: fix test
f7c4a41Trac #22964: specify description of multiplicities in test cases
e9a5580Trac #22964: remove weird desription
6da9317Trac #22964: change test case
75d8245Merge branch 'u/dkrenn/k-regular-warning' into u/galipnik/k-regular-bounded
b44bdadMerge branch 't/21343/k-regular-warning' into t/22964/k-regular-bounded
a585f01Trac #22964: fixup degenerated sequences
478b8b1Merge branch 't/22964/k-regular-bounded' into t/21202/k-regular-trunk

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented May 11, 2021

Changed commit from d622b78 to 478b8b1

@dkrenn
Copy link
Contributor Author

dkrenn commented Jun 25, 2021

comment:39

This is now on 9.3.

Dependency chain: #21295 #21203 #21318 #21325 #21319 #21204 #21343 #22964.

@galipnik

This comment has been minimized.

Sign in to view
@galipnik

This comment has been minimized.

Sign in to view
@galipnik
Copy link
Contributor

Changed dependencies from #21203, #21204, #21295, #21318, #21319, #21325, #21343 to #21203, #21204, #21295, #21318, #21319, #21325, #21343, #22964, #27940, #31787, #32198, #32921

@galipnik

This comment has been minimized.

Sign in to view
@galipnik
Copy link
Contributor

Changed author from Daniel Krenn to Daniel Krenn, Gabriel F. Lipnik

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 13, 2022

Changed commit from 478b8b1 to f3564a3

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 13, 2022

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

3b7c431Trac #21325 review comment 13: use .linear representation in examples partial_sum
33d4daeTrac #21325 review comment 14+15: rewrite construction dict
ecb3663Trac #21325 review comment 17: simpler (more readable) construction of block matrix
96df7b3Trac #21325 review comment 18: deal with remaining block vectors
26e2d6fTrac #21325 review comment 19: shift_left, shift_right
b4f83e4Merge branch 'u/dkrenn/sequences/k-regular-subseq' into t/21319/sequences/rec-hash
9fefcceFollow-up from Trac #21325 review comment 19: shift_left+right: test equality
3c634dfMerge branch 't/21319/sequences/rec-hash' into t/21204/sequences/k-regular-guess
4af416cMerge branch 't/21204/sequences/k-regular-guess' into t/21343/k-regular-warning
f3564a3Merge remote-tracking branch 'trac/u/dkrenn/k-regular-warning' into u/dkrenn/k-regular-trunk

@mkoeppe mkoeppe removed this from the sage-7.4 milestone Dec 29, 2022
This was referenced Jun 6, 2021
Closed
Closed
Closed
Closed
Closed
Closed
This was referenced Jan 5, 2022
Open
Closed
Closed
Closed
This was referenced Jul 4, 2023
Merged
Merged
Open
vbraun pushed a commit that referenced this issue Jul 30, 2023
66baa6a 
gh-35896: deal with bad chosen representations of k-regular sequences
    
### 📚 Description

It deals with the situation when mu[0]*right != right in k-regular
sequences.

Fixes #21343. This PR is created from the branch/code that has been on
the corresponding trac ticket + merging in a current SageMath version.

See also meta issue #21202.

### 📝 Checklist

- [x] The title is concise, informative, and self-explanatory.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation accordingly.

### ⌛ Dependencies

- #21204: guessing k-regular sequences from the first few values

No formal dependencies, but there are trivial merge conflicts---in both
branches, methods are inserted at the same position in the code---
between:
- #21343: deal with mu[0]*right != right in k-regular sequences
- #35894: Regular sequences: implement convolution / ring structure
    
URL: #35896
Reported by: Daniel Krenn
Reviewer(s): cheuberg, Daniel Krenn
vbraun pushed a commit that referenced this issue Aug 5, 2023
edc4c57 
gh-35894: Regular sequences: implement convolution / ring structure
    
### 📚 Description

Add/implement convolution of two regular sequences, therefore making the
parent a ring.

Details of the algorithm: [convolution-sagemath-pr-
35894.pdf](https://github.com/sagemath/sage/files/12216984/convolution-
sagemath-pr-35894.pdf)

See also meta issue #21202.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. It should be `[x]` not `[x
]`. -->

- [x] The title is concise, informative, and self-explanatory.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation accordingly.

### ⌛ Dependencies

No formal dependencies, but there are trivial merge conflicts---in both
branches, methods are inserted at the same position in the code---
between:
- #21343: deal with mu[0]*right != right in k-regular sequences
- #35894: Regular sequences: implement convolution / ring structure
    
URL: #35894
Reported by: Daniel Krenn
Reviewer(s): cheuberg, Daniel Krenn
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: combinatorics p: major / 3 t: enhancement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@videlec @mkoeppe @dkrenn @galipnik