Document Open Access Logo

On the Skolem Problem for Reversible Sequences

Author George Kenison

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.61.pdf
  • Filesize: 0.66 MB
  • 15 pages

Document Identifiers

Author Details

George Kenison
  • Institute of Logic and Computation, TU Wien, Vienna, Austria

Funding

Work supported by WWTF ICT19-018 grant ProbInG and ERC Consolidator Grant ARTIST 101002685.

Acknowledgements

I am grateful to both Adam Keilthy and Florian Luca for their feedback and many helpful discussions. I also thank the anonymous reviewers for their constructive feedback.

Cite AsGet BibTex

George Kenison. On the Skolem Problem for Reversible Sequences. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 61:1-61:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.61

Abstract

Given an integer linear recurrence sequence ⟨X_n⟩, the Skolem Problem asks to determine whether there is a natural number n such that X_n = 0. Recent work by Lipton, Luca, Nieuwveld, Ouaknine, Purser, and Worrell proved that the Skolem Problem is decidable for a class of reversible sequences of order at most seven. Here we give an alternative proof of their result. Our novel approach employs a powerful result for Galois conjugates that lie on two concentric circles due to Dubickas and Smyth.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
  • Computing methodologies → Algebraic algorithms
Keywords
  • The Skolem Problem
  • Linear Recurrences
  • Verification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Akshay, Nikhil Balaji, and Nikhil Vyas. Complexity of Restricted Variants of Skolem and Related Problems. In Kim G. Larsen, Hans L. Bodlaender, and Jean-Francois Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), volume 83 of Leibniz International Proceedings in Informatics (LIPIcs), pages 78:1-78:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.78.
  2. M. Baake. A brief guide to reversing and extended symmetries of dynamical systems. In Ergodic theory and dynamical systems in their interactions with arithmetics and combinatorics, volume 2213 of Lecture Notes in Math., pages 117-135. Springer, Cham, 2018. Google Scholar
  3. Vincent D. Blondel and Natacha Portier. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and its Applications, 351-352:91-98, 2002. Fourth Special Issue on Linear Systems and Control. URL: https://doi.org/10.1016/S0024-3795(01)00466-9.
  4. Christos Christopoulos and James McKee. Galois theory of Salem polynomials. Mathematical Proceedings of the Cambridge Philosophical Society, 148(1):47-54, 2010. URL: https://doi.org/10.1017/S0305004109990284.
  5. Henri Cohen. A course in computational algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1993. Google Scholar
  6. Ryan C. Daileda. Algebraic integers on the unit circle. Journal of Number Theory, 118(2):189-191, June 2006. URL: https://doi.org/10.1016/j.jnt.2005.09.002.
  7. A. Dubickas and C. J. Smyth. On the Remak height, the Mahler measure and conjugate sets of algebraic numbers lying on two circles. Proc. Edinb. Math. Soc. (2), 44(1):1-17, 2001. URL: https://doi.org/10.1017/S001309159900098X.
  8. Graham Everest, Alf van der Poorten, Igor Shparlinski, and Thomas Ward. Recurrence sequences, volume 104 of Mathematical Surveys and Monographs. Amer. Math. Soc., Providence, RI, 2003. Google Scholar
  9. P. Fatou. Sur les séries entières à coefficients entiers. Comptes Rendus Acad. Sci. Paris, 138(130):342-344, 1904. Google Scholar
  10. Ronald Ferguson. Irreducible polynomials with many roots of equal modulus. Acta Arith., 78(3):221-225, 1997. URL: https://doi.org/10.4064/aa-78-3-221-225.
  11. Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki. Skolem’s problem-on the border between decidability and undecidability. Technical report, Turku Centre for Computer Science, 2005. Google Scholar
  12. David Joyner. Zeros of some self-reciprocal polynomials. In Excursions in harmonic analysis. Volume 1, Appl. Numer. Harmon. Anal., pages 329-348. Birkhäuser/Springer, New York, 2013. URL: https://doi.org/10.1007/978-0-8176-8376-4_17.
  13. Anatole Katok and Boris Hasselblatt. Introduction to the Modern Theory of Dynamical Systems. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1995. URL: https://doi.org/10.1017/CBO9780511809187.
  14. G. Kenison, R. Lipton, J. Ouaknine, and J. Worrell. On the Skolem Problem and prime powers. In International Symposium on Symbolic and Algebraic Computation, ISSAC `20. ACM, 2020. URL: https://doi.org/10.1145/3373207.3404036.
  15. David Kirby. Integer matrices of finite order. Rend. Mat., 2(6):403-408, 1969. Google Scholar
  16. L. Kronecker. Zwei Sätze über Gleichungen mit ganzzahligen Coefficienten. Journal für die reine und angewandte Mathematik (Crelles Journal), 1857(53):173-175, January 1857. URL: https://doi.org/10.1515/crll.1857.53.173.
  17. J S W Lamb. Reversing symmetries in dynamical systems. Journal of Physics A: Mathematical and General, 25(4):925-937, February 1992. URL: https://doi.org/10.1088/0305-4470/25/4/028.
  18. Christer Lech. A note on recurring series. Arkiv för Matematik, 2:417-421, 1953. Google Scholar
  19. Richard J. Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, and James Worrell. On the Skolem Problem and the Skolem Conjecture. To appear in the Symposium on Logic in Computer Science (LICS), 2022. Google Scholar
  20. Florian Luca, Joël Ouaknine, and James Worrell. Universal Skolem Sets. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1-6. IEEE, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470513.
  21. C. R. MacCluer and Charles J. Parry. Units of modulus 1. Journal of Number Theory, 7(4):371-375, November 1975. URL: https://doi.org/10.1016/0022-314x(75)90040-2.
  22. K. Mahler. Eine arithmetische Eigenschaft der Taylor-koeffizienten rationaler Funktionen. Proc. Akad. Wet. Amst., 38:50-69, 1935. Google Scholar
  23. K. Mahler and J. Cassels. On the Taylor coefficients of rational functions. Mathematical Proceedings of the Cambridge Philosophical Society, 52(1):39-48, 1956. Google Scholar
  24. Maurice Mignotte, Tarlok Shorey, and Robert Tijdeman. The distance between terms of an algebraic recurrence sequence. Journal für die Reine und Angewandte Mathematik, pages 63-76, 1984. Google Scholar
  25. Joël Ouaknine and James Worrell. Decision problems for linear recurrence sequences. In Reachability problems, volume 7550 of Lecture Notes in Computer Science, pages 21-28. Springer, Heidelberg, 2012. Google Scholar
  26. Joël Ouaknine and James Worrell. On the Positivity Problem for Simple Linear Recurrence sequences,. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming, pages 318-329, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. Google Scholar
  27. Joël Ouaknine and James Worrell. On linear recurrence sequences and loop termination. ACM SIGLOG News, 2(2):4-13, April 2015. Google Scholar
  28. Igor Rivin. Walks on groups, counting reducible matrices, polynomials, and surface and free group automorphisms. Duke Mathematical Journal, 142(2):353-379, 2008. Google Scholar
  29. Igor Rivin. Large Galois groups with applications to Zariski density, 2015. URL: http://arxiv.org/abs/1312.3009.
  30. A. Schinzel. Polynomials with Special Regard to Reducibility. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2000. URL: https://doi.org/10.1017/CBO9780511542916.
  31. Thoralf Skolem. Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen und diophantischer Gleichungen. 8de Skand. Mat. Kongress, Stockholm (1934), pages 163-188, 1934. Google Scholar
  32. C. Smyth. Conjugate algebraic numbers on conics. Acta Arithmetica, 40(4):333-346, 1982. Google Scholar
  33. I. Stewart and D. Tall. Algebraic number theory and Fermat’s last theorem. CRC Press, Boca Raton, FL, fourth edition, 2016. Google Scholar
  34. The PARI Group, Univ. Bordeaux. PARI/GP version 2.13.3, 2021. available from URL: http://pari.math.u-bordeaux.fr/.
  35. Nikolai Vereshchagin. Occurrence of zero in a linear recursive sequence. Mathematical notes of the Academy of Sciences of the USSR, 38(2):609-615, August 1985. Google Scholar
  36. Paulo Viana and Paula Murgel Veloso. Galois theory of reciprocal polynomials. The American Mathematical Monthly, 109(5):466-471, 2002. URL: https://doi.org/10.1080/00029890.2002.11919875.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact