Hilbert's tenth problem for lacunary entire functions of finite order

Natalia Garcia-Fritz, Hector PastenMath. Log. Q 2024 · OpenReview

TL;DR

This paper tackles a version of Hilbert's tenth problem for a specific class of complex functions called "lacunary entire functions of finite order." The authors prove that determining if a system of equations involving these functions has a solution is undecidable, meaning no general algorithm can exist. This extends previous undecidability results to a new, broader class of functions.

What Problem Does This Paper Address?

Hilbert's tenth problem, famously solved by Matiyasevich, asked for an algorithm to determine if a polynomial equation with integer coefficients has integer solutions. This problem was proven to be undecidable, meaning no such universal algorithm can exist. This has led mathematicians to investigate similar problems for other mathematical structures, such as rings of functions.

The paper focuses on the ring of entire functions in one complex variable, denoted by $H$. While the problem is undecidable for polynomials ($C[z]$), it remains an open question for $H$. Previous work has shown undecidability for certain subrings of $H$, including polynomials and "exponential polynomials of finite order." This paper addresses a gap by considering a different type of function: lacunary entire functions of finite order. These functions have a specific sparsity pattern in their power series expansion. The authors aim to show that Hilbert's tenth problem is also undecidable for rings composed of these lacunary functions.

Methods

The core of the paper's contribution lies in proving the undecidability of the positive existential theory for rings of lacunary entire functions of finite order. This is achieved by constructing a positive existential definition of the integers ($\mathbb{Z}$) within these rings.

The authors leverage several key ideas:

  • Holonomic Functions: A significant part of the proof relies on the theory of holonomic functions, which are functions whose power series satisfy a linear differential equation with polynomial coefficients. The paper establishes that certain operations on holonomic functions preserve holonomicity.
  • Functional Pell Equation: A crucial tool is the functional Pell equation $X^2 - (z^2 - 1)Y^2 = 1$. The paper proves a key result (Theorem 1.3) stating that if $f$ and $g$ are entire functions of finite order satisfying this equation, then both $f$ and $g$ must be holonomic. This is a non-trivial result that connects the Pell equation to the properties of holonomic functions.
  • Definability of Integers: By combining the properties of holonomic functions and solutions to the functional Pell equation, the authors are able to define the integers $\mathbb{Z}$ using positive existential formulas within the ring of lacunary entire functions. This is a standard technique for proving undecidability: if you can define the integers, you can solve any problem that can be expressed in terms of integer arithmetic.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Lacunary Functions are Rich Enough: The paper demonstrates that even functions with a sparse power series expansion (lacunary functions) are sufficiently complex to encode arithmetic, leading to undecidability. This is a significant finding because lacunary functions might intuitively seem simpler than general entire functions.
  • The Pell Equation as an Arithmetic Tool: The functional Pell equation $X^2 - (z^2 - 1)Y^2 = 1$ is shown to be a powerful tool for generating and characterizing specific types of functions (holonomic functions) within the ring of entire functions. Its solutions are directly linked to the structure needed to define integers.
  • Bridging Algebra and Analysis: The work elegantly bridges algebraic concepts (Hilbert's tenth problem, polynomial rings, Pell equations) with analytic concepts (entire functions, finite order, holonomicity, lacunarity).

Key Results

The paper presents two main theorems:

  • Theorem 1.1: For any ring $A$ of entire functions of finite order where the only holonomic functions are polynomials ($A \cap H_{holonomic} = C[z]$), the positive existential theory of $A$ is undecidable. This means Hilbert's tenth problem is unsolvable for such rings.
  • Theorem 1.2: For any ring $A$ of entire functions of finite order where all functions in $A$ are lacunary ($A \subseteq H_{lacunary}$), the positive existential theory of $A$ is undecidable. This is a direct consequence of Theorem 1.1 and the fact that lacunary and holonomic entire functions are precisely polynomials.

Limitations and Future Work

  • Specific Class of Functions: The results are specific to "lacunary entire functions of finite order." The question of decidability for the full ring of entire functions $H$ or other broader classes of functions remains open.
  • Positive Existential Theory: The paper focuses on the positive existential theory. While this is a strong result, it doesn't directly address the full first-order theory.
  • Future Work: The authors' work opens avenues for exploring similar undecidability results for other classes of functions or related structures. The techniques used, particularly the connection between the Pell equation and holonomic functions, could be applied to other problems in the field.

Summary updated

BibTeX
@inproceedings{garciafritz2024hilbert,
  author = {Natalia Garcia-Fritz and Hector Pasten},
  title = {{Hilbert's tenth problem for lacunary entire functions of finite order}},
  booktitle = {Math. Log. Q},
  year = {2024},
  url = {https://openreview.net/forum?id=r29kDvhBYo},
}
Figure