DIFFERENCE INDICES OF QUASI-REGULAR DIFFERENCE ALGEBRAIC SYSTEMS

Jie WangJournal of Mathematical Sciences Advances and Applications 2017 · DOI

Abstract

This paper is devoted to studying difference indices of quasi-regular difference algebraic systems. We give the definition of difference indices through a family of pseudo-Jacobian matrices. Some properties of difference indices are proved.

Introduction

In the study of differential-algebraic equations (DAEs), the "differential index" serves as a fundamental metric for system complexity. It quantifies the number of times a system must be differentiated to reveal the underlying algebraic constraints necessary for finding a solution. While this concept is well-established in continuous-time systems, its discrete-time counterpart—the difference index—has historically lacked a unified, rigorous framework.

This paper addresses this gap by establishing a formal definition of the difference index for quasi-regular difference algebraic systems. By leveraging the properties of pseudo-Jacobian matrices and the theory of $\sigma$-ideals, the author provides a robust method for measuring the complexity of discrete transformations, such as those found in difference equations involving shifts (e.g., $f(x+1)$).

The Problem of Hidden Constraints

Difference algebra deals with systems where variables undergo discrete shifts or transformations. A primary challenge in solving these systems is the presence of "hidden" algebraic constraints. These are relations that every solution must satisfy but are not explicitly stated in the original equations.

In differential algebra, these constraints are uncovered through differentiation. In difference algebra, they are revealed through repeated applications of the shift operator. The "difference index" ($\omega$) is defined as the minimum number of transforms required to capture all such hidden relations up to a specific order. Without reaching this index, analytical or numerical solvers may fail to account for the full algebraic structure of the system, leading to incomplete or incorrect solutions.

Methodology: Pseudo-Jacobian Matrices and Rank Chains

The core of the paper’s methodology lies in the construction and analysis of a family of pseudo-Jacobian matrices, denoted as $J_{k,i}$. These matrices represent the partial derivatives of the system's equations with respect to variables at various transform orders (shifts).

Rank Stabilization

The author analyzes the sequence of ranks of these matrices. A critical insight is that the dimensions of the kernels associated with these Jacobian matrices form a non-decreasing chain that eventually becomes stationary. The point at which this chain stabilizes defines the p-difference index ($\omega$). This stabilization ensures that the difference index is a well-defined, finite value, even for systems that appear infinitely complex at first glance. This approach adapts techniques previously used in differential algebra (specifically the work of D’Alfonso et al.) to the discrete case.

Ideal Theory Integration

To prove the validity of this index, the paper employs commutative algebra and the theory of $\sigma$-ideals. By demonstrating that the index correctly identifies when the algebraic relations of the system are fully captured within the ideal generated by the system, the author bridges the gap between symbolic algebra and discrete-time system analysis.

Key Results and Bounds

The research yields several significant theoretical results that provide both qualitative and quantitative insights into difference algebraic systems.

1. Jacobi-type Upper Bound

One of the most important contributions is the establishment of a "Jacobi-type" upper bound for the system's complexity. The author proves that: $$\omega + \text{ord}(\mathfrak{p}) \leq J(\mathcal{E}_0) + e - \min\{\epsilon_{ij}\}$$ where $\omega$ is the difference index, $\text{ord}(\mathfrak{p})$ is the order of the system, $J(\mathcal{E}_0)$ is the Jacobi number of the system's order matrix, and $e$ is the maximal order. This bound allows researchers to estimate the maximum effort required to fully characterize a system based on its initial structure.

2. Hilbert-Levin Regularity

The paper proves that the Hilbert-Levin regularity—a measure of the point at which the dimension polynomial of the difference system stabilizes—is bounded by $e - 1$. This result links the difference index to classical measures of algebraic complexity in difference algebra.

3. Effective Bound for the Membership Problem

For computer scientists working in symbolic computation, the paper provides an effective bound for the difference ideal membership problem. This bound specifies exactly how many transforms are necessary to determine if a given polynomial belongs to the ideal generated by the difference system, providing a theoretical foundation for more efficient algorithms in computer algebra systems.

Limitations and Future Directions

While this work provides a rigorous foundation for the difference index, it is constrained by several factors:

  • Quasi-Regularity: The current framework is specifically tailored to quasi-regular systems, where Jacobian matrices maintain full rank under specified conditions. The behavior of non-quasi-regular (singular) difference systems remains a more difficult challenge.
  • Field Characteristics: The proofs assume a field of characteristic zero. Extending these results to fields of prime characteristic—relevant in areas like coding theory—is not addressed.
  • Computational Implementation: The paper focuses on theoretical bounds. Developing optimized algorithms for calculating these indices in high-performance software environments (like Maple or Mathematica) remains a task for future development.

Conclusion

By introducing a formal definition of the difference index through pseudo-Jacobian matrices, this paper provides a vital tool for the study of quasi-regular difference algebraic systems. The established bounds and properties not only clarify the relationship between differential and difference algebra but also offer practical limits for solving the ideal membership problem in discrete-time contexts.

Summary updated

Abstract

This paper is devoted to studying difference indices of quasi-regular difference algebraic systems. We give the definition of difference indices through a family of pseudo-Jacobian matrices. Some properties of difference indices are proved.
BibTeX
@article{wang2017difference,
  author = {Jie Wang},
  title = {{DIFFERENCE INDICES OF QUASI-REGULAR DIFFERENCE ALGEBRAIC SYSTEMS}},
  journal = {Journal of Mathematical Sciences Advances and Applications},
  year = {2017},
  doi = {10.18642/jmsaa\_7100121832},
}
Figure