Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Jintai Ding , Dieter Schmidt

ABSTRACT

In this paper, we try to clarify some of the questions related to a key concept in multivariate polynomial solving algorithm over a finite field: the degree of regularity. By the degree of regularity, here we refer to a concept first presented by Dubois and Gama, namely the lowest degree at which certain nontrivial degree drop of a polynomial system occurs. Currently, it is somehow commonly accepted that we can use this degree to estimate the complexity of solving a polynomial system, even though we do not have systematic empirical data or a theory to support such a claim. In this paper, we would like to clarify the situation with the help of experiments. We first define a concept of solving degree for a polynomial system. The key question we then need to clarify is the connection of solving degree and the degree of regularity with focus on quadratic systems. To exclude the cases that do not represent the general situation, we need to define when a system is degenerate and when it is irreducible. With extensive computer experiments, we show that the two concepts, the degree of regularity and the solving degree, are related for irreducible systems in the sense that the difference between the two degrees is indeed small, less than 3. But due to the limitation of our experiments, we speculate that this may not be the case for high degree cases. More... »

PAGES

34-49

References to SciGraph publications

Book

TITLE

ISBN

978-3-642-42000-9
978-3-642-42001-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-42001-6_4

DOI

http://dx.doi.org/10.1007/978-3-642-42001-6_4

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1009557142


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Chongqing University", 
          "id": "https://www.grid.ac/institutes/grid.190737.b", 
          "name": [
            "Chongqing University, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ding", 
        "givenName": "Jintai", 
        "id": "sg:person.010723403013.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Cincinnati", 
          "id": "https://www.grid.ac/institutes/grid.24827.3b", 
          "name": [
            "University of Cincinnati, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schmidt", 
        "givenName": "Dieter", 
        "id": "sg:person.015464666561.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015464666561.44"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-45539-6_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000285811", 
          "https://doi.org/10.1007/3-540-45539-6_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-88403-3_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000585614", 
          "https://doi.org/10.1007/978-3-540-88403-3_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-88403-3_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000585614", 
          "https://doi.org/10.1007/978-3-540-88403-3_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-48910-x_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020614953", 
          "https://doi.org/10.1007/3-540-48910-x_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-48910-x_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020614953", 
          "https://doi.org/10.1007/3-540-48910-x_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-12868-9_99", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030833923", 
          "https://doi.org/10.1007/3-540-12868-9_99"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0001-8708(82)90048-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031151173"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-27800-9_24", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037706749", 
          "https://doi.org/10.1007/978-3-540-27800-9_24"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-27800-9_24", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037706749", 
          "https://doi.org/10.1007/978-3-540-27800-9_24"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-22792-9_41", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038551007", 
          "https://doi.org/10.1007/978-3-642-22792-9_41"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-22792-9_41", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038551007", 
          "https://doi.org/10.1007/978-3-642-22792-9_41"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-4049(99)00005-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040947089"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-38616-9_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041359545", 
          "https://doi.org/10.1007/978-3-642-38616-9_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-17373-8_32", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041554151", 
          "https://doi.org/10.1007/978-3-642-17373-8_32"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-17373-8_32", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041554151", 
          "https://doi.org/10.1007/978-3-642-17373-8_32"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-14423-3_7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041918753", 
          "https://doi.org/10.1007/978-3-642-14423-3_7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-14423-3_7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041918753", 
          "https://doi.org/10.1007/978-3-642-14423-3_7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-30539-2_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050327206", 
          "https://doi.org/10.1007/978-3-540-30539-2_23"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-30539-2_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050327206", 
          "https://doi.org/10.1007/978-3-540-30539-2_23"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "In this paper, we try to clarify some of the questions related to a key concept in multivariate polynomial solving algorithm over a finite field: the degree of regularity. By the degree of regularity, here we refer to a concept first presented by Dubois and Gama, namely the lowest degree at which certain nontrivial degree drop of a polynomial system occurs. Currently, it is somehow commonly accepted that we can use this degree to estimate the complexity of solving a polynomial system, even though we do not have systematic empirical data or a theory to support such a claim. In this paper, we would like to clarify the situation with the help of experiments. We first define a concept of solving degree for a polynomial system. The key question we then need to clarify is the connection of solving degree and the degree of regularity with focus on quadratic systems. To exclude the cases that do not represent the general situation, we need to define when a system is degenerate and when it is irreducible. With extensive computer experiments, we show that the two concepts, the degree of regularity and the solving degree, are related for irreducible systems in the sense that the difference between the two degrees is indeed small, less than 3. But due to the limitation of our experiments, we speculate that this may not be the case for high degree cases.", 
    "editor": [
      {
        "familyName": "Fischlin", 
        "givenName": "Marc", 
        "type": "Person"
      }, 
      {
        "familyName": "Katzenbeisser", 
        "givenName": "Stefan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-42001-6_4", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-42000-9", 
        "978-3-642-42001-6"
      ], 
      "name": "\u2018", 
      "type": "Book"
    }, 
    "name": "Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields", 
    "pagination": "34-49", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-42001-6_4"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "2d86d54efb33d92cbff26b983015f6ef4453bd00b08569852b628b1453790532"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009557142"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-42001-6_4", 
      "https://app.dimensions.ai/details/publication/pub.1009557142"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T17:11", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8678_00000249.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-42001-6_4"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-42001-6_4'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-42001-6_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-42001-6_4'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-42001-6_4'


 

This table displays all metadata directly associated to this object as RDF triples.

126 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-42001-6_4 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nbb5b6204c29c4a8f9a596c479b742711
4 schema:citation sg:pub.10.1007/3-540-12868-9_99
5 sg:pub.10.1007/3-540-45539-6_27
6 sg:pub.10.1007/3-540-48910-x_15
7 sg:pub.10.1007/978-3-540-27800-9_24
8 sg:pub.10.1007/978-3-540-30539-2_23
9 sg:pub.10.1007/978-3-540-88403-3_14
10 sg:pub.10.1007/978-3-642-14423-3_7
11 sg:pub.10.1007/978-3-642-17373-8_32
12 sg:pub.10.1007/978-3-642-22792-9_41
13 sg:pub.10.1007/978-3-642-38616-9_4
14 https://doi.org/10.1016/0001-8708(82)90048-2
15 https://doi.org/10.1016/s0022-4049(99)00005-5
16 schema:datePublished 2013
17 schema:datePublishedReg 2013-01-01
18 schema:description In this paper, we try to clarify some of the questions related to a key concept in multivariate polynomial solving algorithm over a finite field: the degree of regularity. By the degree of regularity, here we refer to a concept first presented by Dubois and Gama, namely the lowest degree at which certain nontrivial degree drop of a polynomial system occurs. Currently, it is somehow commonly accepted that we can use this degree to estimate the complexity of solving a polynomial system, even though we do not have systematic empirical data or a theory to support such a claim. In this paper, we would like to clarify the situation with the help of experiments. We first define a concept of solving degree for a polynomial system. The key question we then need to clarify is the connection of solving degree and the degree of regularity with focus on quadratic systems. To exclude the cases that do not represent the general situation, we need to define when a system is degenerate and when it is irreducible. With extensive computer experiments, we show that the two concepts, the degree of regularity and the solving degree, are related for irreducible systems in the sense that the difference between the two degrees is indeed small, less than 3. But due to the limitation of our experiments, we speculate that this may not be the case for high degree cases.
19 schema:editor N55cf20212af444a2a135b838af279084
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf Ncedb66bd184b40e08b76770f9ccdcaf2
24 schema:name Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields
25 schema:pagination 34-49
26 schema:productId N147cadd1f101428d908a465215b229cd
27 N771b73f16aec435fb394ad64b4924d86
28 N834e591964e7404a86443fc0b671d43d
29 schema:publisher N1e536411b3f4476e96d3613e78b7aa87
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009557142
31 https://doi.org/10.1007/978-3-642-42001-6_4
32 schema:sdDatePublished 2019-04-15T17:11
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N21b4847e6f1b4a8ea83d1da7253c6a51
35 schema:url http://link.springer.com/10.1007/978-3-642-42001-6_4
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N06605a76b07146a9b38c210f2f9a0b2a rdf:first N83c60cd750a4497b9b7a55ef8ed3f708
40 rdf:rest rdf:nil
41 N147cadd1f101428d908a465215b229cd schema:name dimensions_id
42 schema:value pub.1009557142
43 rdf:type schema:PropertyValue
44 N1e536411b3f4476e96d3613e78b7aa87 schema:location Berlin, Heidelberg
45 schema:name Springer Berlin Heidelberg
46 rdf:type schema:Organisation
47 N21b4847e6f1b4a8ea83d1da7253c6a51 schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 N55cf20212af444a2a135b838af279084 rdf:first N716dff02f34d496787f201def7d22d3e
50 rdf:rest N06605a76b07146a9b38c210f2f9a0b2a
51 N716dff02f34d496787f201def7d22d3e schema:familyName Fischlin
52 schema:givenName Marc
53 rdf:type schema:Person
54 N771b73f16aec435fb394ad64b4924d86 schema:name readcube_id
55 schema:value 2d86d54efb33d92cbff26b983015f6ef4453bd00b08569852b628b1453790532
56 rdf:type schema:PropertyValue
57 N834e591964e7404a86443fc0b671d43d schema:name doi
58 schema:value 10.1007/978-3-642-42001-6_4
59 rdf:type schema:PropertyValue
60 N83c60cd750a4497b9b7a55ef8ed3f708 schema:familyName Katzenbeisser
61 schema:givenName Stefan
62 rdf:type schema:Person
63 Nbb5b6204c29c4a8f9a596c479b742711 rdf:first sg:person.010723403013.04
64 rdf:rest Nbb7f68f74d1d427785ae1da8d5793462
65 Nbb7f68f74d1d427785ae1da8d5793462 rdf:first sg:person.015464666561.44
66 rdf:rest rdf:nil
67 Ncedb66bd184b40e08b76770f9ccdcaf2 schema:isbn 978-3-642-42000-9
68 978-3-642-42001-6
69 schema:name
70 rdf:type schema:Book
71 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
72 schema:name Mathematical Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
75 schema:name Pure Mathematics
76 rdf:type schema:DefinedTerm
77 sg:person.010723403013.04 schema:affiliation https://www.grid.ac/institutes/grid.190737.b
78 schema:familyName Ding
79 schema:givenName Jintai
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
81 rdf:type schema:Person
82 sg:person.015464666561.44 schema:affiliation https://www.grid.ac/institutes/grid.24827.3b
83 schema:familyName Schmidt
84 schema:givenName Dieter
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015464666561.44
86 rdf:type schema:Person
87 sg:pub.10.1007/3-540-12868-9_99 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030833923
88 https://doi.org/10.1007/3-540-12868-9_99
89 rdf:type schema:CreativeWork
90 sg:pub.10.1007/3-540-45539-6_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285811
91 https://doi.org/10.1007/3-540-45539-6_27
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/3-540-48910-x_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020614953
94 https://doi.org/10.1007/3-540-48910-x_15
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/978-3-540-27800-9_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037706749
97 https://doi.org/10.1007/978-3-540-27800-9_24
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/978-3-540-30539-2_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050327206
100 https://doi.org/10.1007/978-3-540-30539-2_23
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/978-3-540-88403-3_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000585614
103 https://doi.org/10.1007/978-3-540-88403-3_14
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/978-3-642-14423-3_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041918753
106 https://doi.org/10.1007/978-3-642-14423-3_7
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/978-3-642-17373-8_32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041554151
109 https://doi.org/10.1007/978-3-642-17373-8_32
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/978-3-642-22792-9_41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038551007
112 https://doi.org/10.1007/978-3-642-22792-9_41
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/978-3-642-38616-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041359545
115 https://doi.org/10.1007/978-3-642-38616-9_4
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1016/0001-8708(82)90048-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031151173
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1016/s0022-4049(99)00005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040947089
120 rdf:type schema:CreativeWork
121 https://www.grid.ac/institutes/grid.190737.b schema:alternateName Chongqing University
122 schema:name Chongqing University, China
123 rdf:type schema:Organization
124 https://www.grid.ac/institutes/grid.24827.3b schema:alternateName University of Cincinnati
125 schema:name University of Cincinnati, USA
126 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...