research-article

On some decidable and undecidable problems related to q-difference equations with parameters

Author:

S. A. AbramovAuthors Info & Claims

ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

Pages 311 - 317

https://doi.org/10.1145/1837934.1837993

Published: 25 July 2010 Publication History

Abstract

We consider linear q-difference equations with polynomial coefficients depending on parameters. For the case when the ground field is Q(q) we propose an algorithm recognizing whether or not there exist numerical values of parameters for which a given equation has a non-zero polynomial solution (alternatively, a rational-function solution). We prove that there exists no such algorithm if the parameter values are polynomials or rational functions of q.

References

[1]

S. A. Abramov. Rational solutions of linear difference and q-difference equations with polynomial coefficients. Programming and Comput. Software, 21, No 6, 273--278 (1995).

[2]

S. A. Abramov. On an undecidable problem connected with differential and difference equations. Proceedings of XIII International conference on differential equations (Erugin readings - 2009), May 26--29, 2009, Pinsk, Belarus, p. 118 (in Russian) (2009).

[3]

S. A. Abramov. On an undecidable problem related to difference equations with parameters, Programming and Computer Software, 36, No. 2 (2010).

Digital Library

[4]

S. A. Abramov. A direct algorithm to compute rational solutions of first order linear q-difference systems, Discrete Math., 246, 3--12 (2002).

Digital Library

[5]

S. A. Abramov, M. Bronstein. Hypergeometric dispersion and the orbit problem, ISSAC'00 Proceedings, 8--13 (2000).

Digital Library

[6]

S. A. Abramov, M. Bronstein and M. Petkovšek. On polynomial solutions of linear operator equations, ISSAC'95 Proceedings, 290--296 (1995).

Digital Library

[7]

S. A. Abramov, M. van Hoeij. A method for the integration of solutions of Ore equations, ISSAC'97 Proceedings, 172--175 (1997).

Digital Library

[8]

S. A. Abramov, M. van Hoeij. Integration of solutions of linear functional equations, Integral Transformations and Special Functions, 8, No 1--2, 3--12 (1999).

[9]

S. A. Abramov, S. P. Polyakov. Improved universal denominators, Programming and Computer Software, 33, No. 3, 123--137 (2007).

Digital Library

[10]

G. E. Andrews. The Theory of Partitions. Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley, Reading, Mass., 1976.

[11]

G. E. Andrews. q-Series: Their Development and Application in Analysis, Number Theory, Combinatorics, Physics, and Computer Algebra. CBMS Regional Conference Series, No. 66, AMS, R.I., 1986.

[12]

M. Barkatou. Rational solutions of matrix difference equations: problem of equivalence and factorization, ISSAC'99 Proceedings, 277--282 (1999).

Digital Library

[13]

D. Boucher. About the polynomial solutions of homogeneous linear differential equations depending on parameters, ISSAC'99 Proceedings, 261--268 (1999).

Digital Library

[14]

B. Buchberger. Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory. In: Recent Trends in Multidimentional System Theory, D. Reidel, Dordrecht, 1985.

[15]

J. Denef. The diophantine problem for polynomial rings and fields of rational functions, Transactions of the American Mathematical Society, 242, 391--399 (1978).

[16]

L. van den Dries. Alfred Tarski's elimination theory for real closed fields. J. Symbolic Logic, 53, 7--19 (1988).

[17]

J. von zur Gathen, J. Gerhard. Modern Computer Algebra (Second Edition). Cambridge University Press, 2003.

Digital Library

[18]

M. van Hoeij. Rational solutions of linear difference equations, ISSAC'98 Proceedings, 120--123 (1998).

Digital Library

[19]

Yu. V. Matiyasevich. Hilbert's Tenth Problem. MIT Press, Cambrige, MA, 1993.

Digital Library

[20]

B. Mishra. Algorithmic Algebra. Springer-Verlag, 1993.

Digital Library

[21]

M. Petkovšek, H. S. Wilf, D. Zeilberger. A = B, A K Peters, 1996.

[22]

T. Pheidas and K. Zahidi. Undecidability of existential theories of rings and fields: A survey. Contemporary Mathematics, 270, 49--106 (2000).

[23]

Maple online help: http://www.maplesoft.com/support/help/

Cited By

Abramov SRyabenko A(2013)Linear q-difference equations depending on a parameterJournal of Symbolic Computation10.1016/j.jsc.2011.12.01749(65-77)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.jsc.2011.12.017
Abramov SPetkovšek M(2012)On polynomial solutions of linear partial differential and (q-)difference equationsProceedings of the 14th international conference on Computer Algebra in Scientific Computing10.1007/978-3-642-32973-9_1(1-11)Online publication date: 3-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-32973-9_1

Index Terms

On some decidable and undecidable problems related to q-difference equations with parameters
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

Linear q-difference equations depending on a parameter

We consider linear q-difference equations with polynomial coefficients depending on a parameter. We discuss an algorithm recognizing the existence of numerical values of the parameter for which a given equation has a non-zero rational function solution. ...
Difference equations of q-Appell polynomials

In this paper, we study some properties of the q-Appell polynomials, including the recurrence relations and the q-difference equations which extend some known classical ( q = 1 ) results. We also provide the recurrence relations and the q-difference ...
Linear partial q-difference equations on q-linear lattices and their bivariate q-orthogonal polynomial solutions

Orthogonal polynomial solutions of an admissible potentially self-adjoint linear second-order partial q-difference equation of the hypergeometric type in two variables on q-linear lattices are analyzed. A q-Pearson's system for the orthogonality weight ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

July 2010

366 pages

ISBN:9781450301503

DOI:10.1145/1837934

Program Chair:
Wolfram Koepf
London, Ontario, Canada

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Gesellschaft fur Informtatik

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ECONET
Russian Foundation for Basic Research

Conference

ISSAC '10

Sponsor:

ISSAC '10: International Symposium on Symbolic and Algebraic Computation

July 25 - 28, 2010

Munich, Germany

Acceptance Rates

ISSAC '10 Paper Acceptance Rate 45 of 110 submissions, 41%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
76
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Abramov SRyabenko A(2013)Linear q-difference equations depending on a parameterJournal of Symbolic Computation10.1016/j.jsc.2011.12.01749(65-77)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.jsc.2011.12.017
Abramov SPetkovšek M(2012)On polynomial solutions of linear partial differential and (q-)difference equationsProceedings of the 14th international conference on Computer Algebra in Scientific Computing10.1007/978-3-642-32973-9_1(1-11)Online publication date: 3-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-32973-9_1

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents