Counting polynomials with distinct zeros in finite fields (Q503699): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
Let \(F_q\) be a finite field with \(q=p^e\) elements, \(p\) a prime. Fix integers \(\ell\) and \(n\), \(0 < \ell < n < q\), and fix \(u(x)=x^n+u_{n-1}x^{n-1}+\cdots + u_{\ell +1}x^{\ell +1}\in F_q[x]\). Let \(N_k(u(x), \ell )\) be the number of \(v_{\ell}(x)\in F_q[x]\) such that \(\deg v_{\ell} \leq \ell\) and \(u(x)+v_{\ell}(x)\) has exactly \(k\) roots in \(F_q\). \(N_k(u, \ell)\) appears in graph theory, for computing the spectrum of certain Wenger graphs, and in coding theory where \(N_k(u, \ell)\) is the number of codewords \(v_{\ell}\) in a \([q, \ell +1]\) Reed-Solomon code of distance \(q-k\) from the received word \(u(x)\). When \(n-\ell =1\), a formula for \(N_k(u, \ell)\) was given by \textit{A. Knopfmacher} and \textit{J. Knopfmacher} [Linear Multilinear Algebra 26, No. 4, 287--292 (1990; Zbl 0699.12028)]. Here the authors give a formula for \(N_k(u, \ell )\) when \(n-\ell =2\) and when \(n-\ell =3\), \(p\) odd, \(e\) even and \(u(x)=x^n\). The proofs use the inclusion-exclusion principle (which also yields a simple proof of the \(n-\ell =1\) case) and results on the number of zeros of a quadratic form that lie in a hyperplane. | |||
Property / review text: Let \(F_q\) be a finite field with \(q=p^e\) elements, \(p\) a prime. Fix integers \(\ell\) and \(n\), \(0 < \ell < n < q\), and fix \(u(x)=x^n+u_{n-1}x^{n-1}+\cdots + u_{\ell +1}x^{\ell +1}\in F_q[x]\). Let \(N_k(u(x), \ell )\) be the number of \(v_{\ell}(x)\in F_q[x]\) such that \(\deg v_{\ell} \leq \ell\) and \(u(x)+v_{\ell}(x)\) has exactly \(k\) roots in \(F_q\). \(N_k(u, \ell)\) appears in graph theory, for computing the spectrum of certain Wenger graphs, and in coding theory where \(N_k(u, \ell)\) is the number of codewords \(v_{\ell}\) in a \([q, \ell +1]\) Reed-Solomon code of distance \(q-k\) from the received word \(u(x)\). When \(n-\ell =1\), a formula for \(N_k(u, \ell)\) was given by \textit{A. Knopfmacher} and \textit{J. Knopfmacher} [Linear Multilinear Algebra 26, No. 4, 287--292 (1990; Zbl 0699.12028)]. Here the authors give a formula for \(N_k(u, \ell )\) when \(n-\ell =2\) and when \(n-\ell =3\), \(p\) odd, \(e\) even and \(u(x)=x^n\). The proofs use the inclusion-exclusion principle (which also yields a simple proof of the \(n-\ell =1\) case) and results on the number of zeros of a quadratic form that lie in a hyperplane. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11T06 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C50 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 94B15 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6676809 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
polynomials | |||
Property / zbMATH Keywords: polynomials / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
quadratic forms | |||
Property / zbMATH Keywords: quadratic forms / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Reed-Solomon codes | |||
Property / zbMATH Keywords: Reed-Solomon codes / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Wenger graphs | |||
Property / zbMATH Keywords: Wenger graphs / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
spectrum of graphs | |||
Property / zbMATH Keywords: spectrum of graphs / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
inclusion-exclusion principle | |||
Property / zbMATH Keywords: inclusion-exclusion principle / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
moments subset-sum | |||
Property / zbMATH Keywords: moments subset-sum / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2559135948 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1702.02327 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4398864 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Linearized Wenger graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of Decoding Positive-Rate Primitive Reed–Solomon Codes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Deterministic Reduction for the Gap Minimum Distance Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the spectrum of Wenger graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Deep holes in Reed-Solomon codes based on Dickson polynomials / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Counting polynomials with a given number of zeros in a finite field / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New examples of graphs without small cycles and of large size / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Explicit construction of graphs with an arbitrary large girth and of large size / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An infinite series of regular edge- but not vertex-transitive graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the subset sum problem over finite fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On error distance of Reed-Solomon codes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new sieve for distinct coordinate counting / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the error distance of extended Reed-Solomon codes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4344108 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the diameter of Wenger graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computing Error Distance of Reed-Solomon Codes / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 08:31, 13 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting polynomials with distinct zeros in finite fields |
scientific article |
Statements
Counting polynomials with distinct zeros in finite fields (English)
0 references
23 January 2017
0 references
Let \(F_q\) be a finite field with \(q=p^e\) elements, \(p\) a prime. Fix integers \(\ell\) and \(n\), \(0 < \ell < n < q\), and fix \(u(x)=x^n+u_{n-1}x^{n-1}+\cdots + u_{\ell +1}x^{\ell +1}\in F_q[x]\). Let \(N_k(u(x), \ell )\) be the number of \(v_{\ell}(x)\in F_q[x]\) such that \(\deg v_{\ell} \leq \ell\) and \(u(x)+v_{\ell}(x)\) has exactly \(k\) roots in \(F_q\). \(N_k(u, \ell)\) appears in graph theory, for computing the spectrum of certain Wenger graphs, and in coding theory where \(N_k(u, \ell)\) is the number of codewords \(v_{\ell}\) in a \([q, \ell +1]\) Reed-Solomon code of distance \(q-k\) from the received word \(u(x)\). When \(n-\ell =1\), a formula for \(N_k(u, \ell)\) was given by \textit{A. Knopfmacher} and \textit{J. Knopfmacher} [Linear Multilinear Algebra 26, No. 4, 287--292 (1990; Zbl 0699.12028)]. Here the authors give a formula for \(N_k(u, \ell )\) when \(n-\ell =2\) and when \(n-\ell =3\), \(p\) odd, \(e\) even and \(u(x)=x^n\). The proofs use the inclusion-exclusion principle (which also yields a simple proof of the \(n-\ell =1\) case) and results on the number of zeros of a quadratic form that lie in a hyperplane.
0 references
polynomials
0 references
quadratic forms
0 references
Reed-Solomon codes
0 references
Wenger graphs
0 references
spectrum of graphs
0 references
inclusion-exclusion principle
0 references
moments subset-sum
0 references