Algorithms for discrete differential equations of order 1 - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2022

## Algorithms for discrete differential equations of order 1

Alin Bostan
• Function : Author
• PersonId : 831654
Frédéric Chyzak
• Function : Author
• PersonId : 1130794
Mohab Safey El Din
• Function : Author

#### Abstract

Discrete differential equations of order 1 are equations relating polynomially $F(t,u)$, a power series in $t$ with polynomial coefficients in a catalytic'' variable~$u$, and one of its specializations, say~$F(t,1)$. Such equations are ubiquitous in combinatorics, notably in the enumeration of maps and walks. When the solution $F$ is unique, a celebrated result by Bousquet-M\'elou, reminiscent of Popescu's theorem in commutative algebra, states that $F$ is \emph{algebraic}. We address algorithmic and complexity questions related to this result. In \emph{generic} situations, we first revisit and analyze known algorithms, based either on polynomial elimination or on the guess-and-prove paradigm. We then design two new algorithms: the first has a geometric flavor, the second blends elimination and guess-and-prove. In the \emph{general} case (no genericity assumptions), we prove that the total arithmetic size of the algebraic equations for $F(t,1)$ is bounded polynomially in the size of the input discrete differential equation, and that one can compute such equations in polynomial time.

### Dates and versions

hal-03616406 , version 1 (22-03-2022)
hal-03616406 , version 2 (20-05-2022)

### Identifiers

• HAL Id : hal-03616406 , version 2

### Cite

Alin Bostan, Frédéric Chyzak, Hadrien Notarantonio, Mohab Safey El Din. Algorithms for discrete differential equations of order 1. ISSAC 2022 - 47th International Symposium on Symbolic and Algebraic Computation, Jul 2022, Lille, France. pp.101-110. ⟨hal-03616406v2⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

216 View
{"ft_lang_label":"__label__en","ft_lang_prob":0.880797,"math_prob":0.96760863,"size":1283,"snap":"2023-14-2023-23","text_gpt3_token_len":295,"char_repetition_ratio":0.12900704,"word_repetition_ratio":0.011428571,"special_character_ratio":0.208106,"punctuation_ratio":0.11504425,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9927992,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-10T22:29:13Z\",\"WARC-Record-ID\":\"<urn:uuid:86d452c4-d453-46e5-ac66-02e3e99620b5>\",\"Content-Length\":\"96407\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:f390998f-c382-4b4f-8f57-bd17557df5c8>\",\"WARC-Concurrent-To\":\"<urn:uuid:b0e3b6f4-40b8-43c3-b2cf-d35606c84c9a>\",\"WARC-IP-Address\":\"193.48.96.10\",\"WARC-Target-URI\":\"https://inria.hal.science/hal-03616406\",\"WARC-Payload-Digest\":\"sha1:DIOZDDZPZVCY4YX6RSE4L3QNZMZIX5NF\",\"WARC-Block-Digest\":\"sha1:E2BHMX7D2HKLQMCCU3ORZR7WBDQCNNLL\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224646350.59_warc_CC-MAIN-20230610200654-20230610230654-00027.warc.gz\"}"}