More Like this

1. Reduction with Respect to the Effective Order and a New Type of Dimension Polynomials of Difference Modules

   https://doi.org/10.1145/3476446.3535497  

   Levin, Alexander (July 2022, 2022 International Symposium on Symbolic and Algebraic Computation)

   General Chair: Marc Moreno Chair: Lihong Zhi (Ed.)

   We introduce a new type of reduction in a free difference module over a difference field that uses a generalization of the concept of effective order of a difference polynomial. Then we define the concept of a generalized characteristic set of such a module, establish some properties of these characteristic sets and use them to prove the existence, outline a method of computation and find invariants of a dimension polynomial in two variables associated with a finitely generated difference module. As a consequence of these results, we obtain a new type of bivariate dimension polynomials of finitely generated difference field extensions. We also explain the relationship between these dimension polynomials and the concept of Einstein’s strength of a system of difference equations. 

   more » « less
2. Generalized characteristic sets and new multivariate difference dimension polynomials

   https://doi.org/10.1007/s00200-023-00628-0  

   Levin, Alexander (October 2023, Applicable Algebra in Engineering, Communication and Computing)

   We introduce a new type of characteristic sets of difference polynomials using a generalization of the concept of effective order to the case of partial difference polynomials and a partition of the basic set of translations σ. Using properties of these characteristic sets, we prove the existence and outline a method of computation of a multivariate dimension polynomial of a finitely generated difference field extension that describes the transcendence degrees of intermediate fields obtained by adjoining transforms of the generators whose orders with respect to the components of the partition of σ are bounded by two sequences of natural numbers. We show that such dimension polynomials carry essentially more invariants (that is, characteristics of the extension that do not depend on the set of its difference generators) than previously known difference dimension polynomials. In particular, a dimension polynomial of the new type associated with a system of algebraic difference equations gives more information about the system than the classical univariate difference dimension polynomial. 

   more » « less
3. Generalized Gröbner Bases and New Properties of Multivariate Difference Dimension Polynomials

   https://doi.org/10.1145/3452143.3465544  

   Levin, Alexander (July 2021, ISSAC '21: Proceedings of the 46th International Symposium on Symbolic and Algebraic Computation)

   null (Ed.)

   We present a method of Gröbner bases with respect to several term orderings and use it to obtain new results on multivariate dimension polynomials of inversive difference modules. Then we use the difference structure of the module of Kahler differentials associated with a finitely generated inversive difference field extension of a given difference transcendence degree to describe the form of a multivariate difference dimension polynomial of the extension. 

   more » « less
4. Hilbert-Type Dimension Polynomials of Intermediate Difference-Differential Field Extensions

   https://doi.org/10.1007/978-3-030-43120-4_7  

   Levin, Alexander (December 2019, Lecture notes in computer science)

   null (Ed.)

   Let K be an inversive difference-differential field and L a (not necessarily inversive) finitely generated difference-differential field extension of K. We consider the natural filtration of the extension L/K associated with a finite system \eta of its difference-differential generators and prove that for any intermediate difference-differential field F, the transcendence degrees of the components of the induced filtration of F are expressed by a certain numerical polynomial \chi_{K, F,\eta}(t). This polynomial is closely connected with the dimension Hilbert-type polynomial of a submodule of the module of K\"ahler differentials $\Omega_{L^{\ast}|K} where L^{\ast} is the inversive closure of L. We prove some properties of polynomials \chi_{K, F,\eta}(t) and use them for the study of the Krull-type dimension of the extension L/K. In the last part of the paper, we present a generalization of the obtained results to multidimensional filtrations of L/K associated with partitions of the sets of basic derivations and translations. 

   more » « less
5. Polynomial Identity Testing via Evaluation of Rational Functions

   https://doi.org/10.4086/toc.2024.v020a001  

   Hu, Ivan; Melkebeek, Dieter van; Morgan, Andrew (July 2024, Theory of Computing)

   We introduce a hitting set generator for Polynomial Identity Testing based on evaluations of low-degree univariate rational functions at abscissas associated with the variables. We establish an equivalence up to rescaling with a generator introduced by Shpilka and Volkovich, which has a similar structure but uses multivariate polynomials. We initiate a systematic analytic study of the power of hitting set generators by characterizing their vanishing ideals, i.e., the sets of polynomials that they fail to hit. We provide two such characterizations for our generator. First, we develop a small collection of polynomials that jointly produce the vanishing ideal. As corollaries, we obtain tight bounds on the minimum degree, sparseness, and partition class size of set-multilinearity in the vanishing ideal. Second, inspired by a connection to alternating algebra, we develop a structured deterministic membership test for the multilinear part of the vanishing ideal. We present a derivation based on alternating algebra along with the required background, as well as one in terms of zero substitutions and partial derivatives, avoiding the need for alternating algebra. As evidence of the utility of our analytic approach, we rederive known derandomization results based on the generator by Shpilka and Volkovich and present a new application in derandomization / lower bounds for read-once oblivious algebraic branching programs. 

   more » « less