Polynomials that Vanish on Distinct n th Roots of Unity
Combinatorial NullstellensatzGröbner basesHamiltonian cycles in graphsLatin transversals in Latin squaresperfect matchings in bipartite graphspermutation polynomialspolynomials vanishing on tuples of distinct roots of unity
Enumerative combinatorics (05A99) Orthogonal arrays, Latin squares, Room squares (05B15) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Polynomials in number theory (11C08) Polynomials over commutative rings (13B25) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Polynomials and rational functions of one complex variable (30C10)
Let \(\mathbb C\) denote the field of complex numbers and, for \(0\leq t\leq n-1\), \(J(n,t+1)\subset \mathbb C[x_0,\dots,x_t]\) the ideal of those polynomials in \(x_0,\dots,x_t\) that vanish on \((t+1)\) tuples of distinct \(n\)th roots of unity. Define \(f_0=x_0^n-1\) and for \(1\leq k\leq t\) the polynomial \(f_k=\sum_{a_0+\dots+a_k=n-k}{x_0^{a_0}\cdot\ldots\cdot x_k^{a_k}}\) (i.e., the full symmetric polynomial in \(x_0,\dots,x_k\) of degree \(n-k\)). Then \(G=\{f_0,f_1,\dots,f_t\}\) is a Gröbner basis for \(J(n,t+1)\) and the lexicographic term order with \(x_0<\dots<x_t\). The proof given in the appendix uses the characterization \(f\in J(n,t+1)\iff f\,V\in \langle x_0^n-1,\dots,x_t^n-1\rangle\) where \(V=\prod_{1\leq i<j\leq t}{(x_i-x_j)}\) is the Vandermonde polynomial. As main result the authors prove a combinatorial Nullstellensatz for such ideals, i.e., a characterization of polynomials \(f=\sum_\alpha{c_\alpha x^\alpha}\in \mathbb C[x_0,\dots,x_t]\) with \(f\not\in J(n,t+1)\) in terms of their coefficients: To each monomial \(x^\alpha=x_0^{\alpha_0}\ldots x_t^{\alpha_t}\) associate a function \(\pi_\alpha: \mathbb Z_n\rightarrow \mathbb Z_n\) defined by \(\pi_\alpha(i)\equiv i+\alpha_i\pmod{n}\) and define \(\Lambda=\Lambda_{t+1}= \{\alpha\in \mathbb Z_{\geq 0}^{t+1} : \pi_\alpha\) is a permutation of \(\{0,1,\dots,t\}\}\). Then \(f\not\in J(n,t+1)\) if and only if there exists some reduced with respect to \(G\) monomial \(x^\beta\) (i.e., \(\beta_i<n-i\) for all \(i=0,\dots,t\)) such that \(c=\sum_{\alpha+\beta\in\Lambda} {c_\alpha\,\text{ sgn}(\pi_{\alpha+\beta})}\neq 0\). Note that \(c\) is actually NF\((x^\beta f,G)(0,\dots,0)\) where NF is the normal form operator with respect to \(G\). The proof uses the stronger result that the matrix \(M(n,t+1)=\| m_{\beta\beta'}\| \) is invertible where \(m_{\beta\beta'}= \text{NF}(x^\beta x^{\beta'},G)(0,\dots,0)\) and \(x^\beta, x^{\beta'}\) run over all monomials reduced with respect to \(G\). As applications, four problems are sketched that can be reduced to membership questions of polynomials in \(J(n,t+1)\) for certain \(n,t\): the description of the coefficient variety of permutation polynomials, i.e., (univariate) polynomials \(g(x)=\sum_{i=0}^{n-1}{\rho_ix^i}\) that permute the \(n\)th roots of unity; perfect matchings in bipartite graphs; Latin transversals in Latin squares of odd order; Hamiltonian cycles in graphs.
- Infinitely many roots of unity are zeros of some Jones polynomials
- The lex game and some applications
- Roots of unity and the polynomials with coefficients in \(\mathbb{T}\)
- All roots of unity are detected by the A-polynomial
- Binary polynomial power sums vanishing at roots of unity
- Polynomials that vanish to high order on most of the hypercube
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
This page was built for publication: Polynomials that Vanish on Distinct $n$ th Roots of Unity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4812339)