Zero testing and equation solving for sparse polynomials on rectangular domains
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917689438502912 |
|---|---|
| author | Aichinger, Erhard Grünbacher, Simon Hametner, Paul |
| author_facet | Aichinger, Erhard Grünbacher, Simon Hametner, Paul |
| contents | We consider sparse polynomials in $N$ variables over a finite field, and ask whether they vanish on a set $S^N$, where $S$ is a set of nonzero elements of the field. We see that if for a polynomial $f$, there is $\mathbf{c}\in S^N$ with $f (\mathbf{c}) \neq 0$, then there is such a $\mathbf{c}$ in every sphere inside $S^N$, where the radius of the sphere is bounded by a multiple of the logarithm of the number of monomials that appear in $f$. A similar result holds for the solutions of the equations $f_1 = \cdots = f_r = 0$ inside $S^N$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_19669 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Zero testing and equation solving for sparse polynomials on rectangular domains Aichinger, Erhard Grünbacher, Simon Hametner, Paul Rings and Algebras 11T06, 11T41 We consider sparse polynomials in $N$ variables over a finite field, and ask whether they vanish on a set $S^N$, where $S$ is a set of nonzero elements of the field. We see that if for a polynomial $f$, there is $\mathbf{c}\in S^N$ with $f (\mathbf{c}) \neq 0$, then there is such a $\mathbf{c}$ in every sphere inside $S^N$, where the radius of the sphere is bounded by a multiple of the logarithm of the number of monomials that appear in $f$. A similar result holds for the solutions of the equations $f_1 = \cdots = f_r = 0$ inside $S^N$. |
| title | Zero testing and equation solving for sparse polynomials on rectangular domains |
| topic | Rings and Algebras 11T06, 11T41 |
| url | https://arxiv.org/abs/2305.19669 |