Counting polynomials with distinct zeros in finite fields (Q503699): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
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 |
Revision as of 02:00, 1 July 2023
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